實例講解遺傳算法-基于遺傳算法的自動組卷系統(tǒng)【實踐篇】

實例講解遺傳算法——基于遺傳算法的自動組卷系統(tǒng)【實踐篇】上一篇實例講解遺傳算法——基于遺傳算法的自動組卷系統(tǒng)【理論篇】講了遺傳算法的原理及在自己動組卷系統(tǒng)中的應(yīng)用，本篇將給出上一篇中所述理論的實踐。先上兩張運行后的效果圖吧：基于遺傳算法的自動組卷系統(tǒng)運行效果圖〔1〕基于遺傳算法的自動組卷系統(tǒng)運行效果圖〔2〕一、準備工作1、問題實體問題實體包含編號、類型〔類型即題型，分為五種：單項選擇，多項選擇，判斷，填空，問答，分別用1、2、3、4、5表示〕、分數(shù)、難度系數(shù)、知識點。一道題至少有一個知識點，為簡單易懂，知識點用List<int>表示〔知識點編號集合〕。代碼如下：publicclass

Problem{public

Problem()

{

ID

=

0;

Type

=

0;

Score

=

0;

Difficulty

=

0.00;

Points

=

new

List<int>();

}public

Problem(Problem

p)

{this.ID

=

p.ID;this.Type

=

p.Type;this.Score

=

p.Score;this.Difficulty

=

p.Difficulty;this.Points

=

p.Points;

}///<summary>///編號///</summary>publicint

ID

{

get;

set;

}///<summary>///題型〔1、2、3、4、5對應(yīng)單項選擇，多項選擇，判斷，填空，問答〕///</summary>publicint

Type

{

get;

set;

}///<summary>///分數(shù)///</summary>publicint

Score

{

get;

set;

}///<summary>///難度系數(shù)///</summary>publicdouble

Difficulty

{

get;

set;

}///<summary>///知識點///</summary>public

List<int>

Points

{

get;

set;

}}2、題庫為了簡單，這里沒有用數(shù)據(jù)庫，題目信息臨時創(chuàng)立，保存在內(nèi)存中。因為對不同層次的考生一道題目在不同試卷中的分數(shù)可能不一樣，因此題目分數(shù)一般是老師出卷時定的，不保存在題庫中。且單項選擇，多項選擇，判斷題每題分數(shù)應(yīng)該相同，填空題一般根據(jù)空數(shù)來定分數(shù)，而問答題一般根據(jù)題目難度來定的，因此這里的單項選擇、多項選擇、判斷分數(shù)相同，填空空數(shù)取1-4間的隨機數(shù)，填空題分數(shù)即為空數(shù)，問答題即為該題難度系數(shù)*10取整。這里各種題型均為1000題，具體應(yīng)用時改為數(shù)據(jù)庫即可。代碼如下：publicclass

DB

{///<summary>///題庫///</summary>public

List<Problem>

ProblemDB;public

DB()

{ProblemDB

=

new

List<Problem>();

Problem

model;

Random

rand

=

new

Random();

List<int>

Points;for

(inti

=

1;

i

<=

5000;

i++)

{

model

=

new

Problem();

model.ID

=

i;//試題難度系數(shù)取0.3到1之間的隨機值model.Difficulty

=

rand.Next(30,

100)

*

0.01;//單項選擇題1分if

(i

<

1001)

{model.Type

=

1;model.Score

=

1;

}//單項選擇題2分if

(i

>

1000

&&

i

<

2001)

{model.Type

=

2;model.Score

=

2;

}//判斷題2分if

(i

>

2000

&&

i

<

3001)

{model.Type

=

3;model.Score

=

2;

}//填空題1—4分if

(i

>

3000

&&

i

<

4001)

{model.Type

=

4;model.Score

=

rand.Next(1,

5);

}//問答題分數(shù)為難度系數(shù)*10if

(i

>

4000

&&

i

<

5001)

{model.Type

=

5;

model.Score

=

model.Difficulty

>

0.3

?

(int)(double.Parse(model.Difficulty.ToString("f1"))

*

10)

:

3;

}

Points

=

new

List<int>();//每題1到4個知識點int

count

=

rand.Next(1,

5);for

(int

j

=

0;

j

<

count;

j++)

{Points.Add(rand.Next(1,

100));

}model.Points

=

Points;ProblemDB.Add(model);

}

}}3、試卷實體試卷一般包含試卷編號，試卷名稱，考試時間，難度系數(shù)，知識點分布，總題數(shù)，總分數(shù)，各種題型所占比率等屬性，這里為簡單去掉了試卷名稱跟考試時間。其中的知識點分布即老師出卷時選定本試卷要考查的知識點，這里用List<int>〔知識點編號集合〕表示。代碼如下：publicclass

Paper

{///<summary>///編號///</summary>publicint

ID

{

get;

set;

}///<summary>///總分///</summary>publicintTotalScore

{

get;

set;

}///<summary>///難度系數(shù)///</summary>publicdouble

Difficulty

{

get;

set;

}///<summary>///知識點///</summary>public

List<int>

Points

{

get;

set;

}///<summary>///各種題型題數(shù)///</summary>publicint[]

EachTypeCount

{

get;

set;

}}二、開始遺傳算法組卷之旅準備工作已經(jīng)OK，下面就按上一篇介紹的流程進行操作啦！1、產(chǎn)生初始種群這里保證題數(shù)跟總分到達出卷要求即可，但為操作方便，這里再定義一個種群個體實體類Unit，包含編號、適應(yīng)度、題數(shù)、總分、難度系數(shù)、知識點分布、包含的題目等信息〔也可以修改一下試卷實體，用試卷實體表示〕：publicclass

Unit{public

Unit()

{

ID

=

0;AdaptationDegree

=

0.00;KPCoverage

=

0.00;ProblemList

=

new

List<Problem>();

}///<summary>///編號///</summary>publicint

ID

{

get;

set;

}///<summary>///適應(yīng)度///</summary>publicdoubleAdaptationDegree

{

get;

set;

}///<summary>///難度系數(shù)〔本試卷所有題目分數(shù)*難度系數(shù)/總分〕///</summary>publicdouble

Difficulty

{get

{double

diff

=

0.00;ProblemList.ForEach(delegate(Problem

p)

{

diff

+=

p.Difficulty

*

p.Score;

});return

diff

/

SumScore;

}

}///<summary>///題目數(shù)量///</summary>publicintProblemCount

{get

{returnProblemList.Count;

}

}///<summary>///總分///</summary>publicintSumScore

{get

{int

sum

=

0;ProblemList.ForEach(delegate(Problem

p)

{

sum

+=

p.Score;

});return

sum;

}

}///<summary>///知識點分布///</summary>publicdoubleKPCoverage

{

get;

set;

}///<summary>///題目///</summary>public

List<Problem>

ProblemList

{

get;

set;

}

}下面即來產(chǎn)生初始種群，按個體數(shù)量，期望試卷知識點分布，各類型題目數(shù)等限制產(chǎn)生初始種群：///<summary>///初始種群///</summary>///<param

name="count">個體數(shù)量</param>///<param

name="paper">期望試卷</param>///<param

name="problemList">題庫</param>///<returns>初始種群</returns>public

List<Unit>

CSZQ(int

count,

Paper

paper,

List<Problem>

problemList)

{

List<Unit>

unitList

=

new

List<Unit>();int[]

eachTypeCount

=

paper.EachTypeCount;

Unit

unit;

Random

rand

=

new

Random();for

(inti

=

0;

i

<

count;

i++)

{

unit

=

new

Unit();

unit.ID

=

i

+

1;unit.AdaptationDegree

=

0.00;//總分限制while

(paper.TotalScore

!=

unit.SumScore)

{();//各題型題目數(shù)量限制for

(int

j

=

0;

j

<

eachTypeCount.Length;

j++)

{

List<Problem>

oneTypeProblem

=

problemList

.Where(o

=>

o.Type

==

(j

+

1))

.Where(p

=>

IsContain(paper,

p))

.ToList();

Problem

temp

=

new

Problem();for

(int

k

=

0;

k

<

eachTypeCount[j];

k++)

{//選擇不重復(fù)的題目int

index

=

rand.Next(0,

oneTypeProblem.Count

-

k);

unit.ProblemList.Add(oneTypeProblem[index]);

temp

=

oneTypeProblem[oneTypeProblem.Count

-

1

-

k];

oneTypeProblem[oneTypeProblem.Count

-

1

-

k]

=

oneTypeProblem[index];oneTypeProblem[index]

=

temp;

}

}

}unitList.Add(unit);

}//計算知識點覆蓋率及適應(yīng)度unitList

=

GetKPCoverage(unitList,

paper);unitList

=

GetAdaptationDegree(unitList,

paper,

kpcoverage,

difficulty);returnunitList;

}2、計算種群個體的適應(yīng)度在上面的代碼中最后調(diào)用了兩個方法，GetKPCoverage跟GetAdaptationDegree，這兩個方法分別是計算種群中個體的知識點覆蓋率跟適應(yīng)度。關(guān)于種群個體的知識點覆蓋率在上一篇文章中已經(jīng)說過了〔知識點分布用一個個體知識點的覆蓋率來衡量，例如期望本試卷包含N個知識點，而一個個體中所有題目知識點的并集中包含M個〔M<=N〕，那么知識點的覆蓋率為M/N。〕，具體算法如下：///<summary>///計算知識點覆蓋率///</summary>///<param

name="unitList">種群</param>///<param

name="paper">期望試卷</param>///<returns>List</returns>public

List<Unit>

GetKPCoverage(List<Unit>

unitList,

Paper

paper)

{

List<int>

kp;for

(inti

=

0;

i

<

unitList.Count;

i++)

{kp

=

new

List<int>();unitList[i].ProblemList.ForEach(delegate(Problem

p)

{kp.AddRange(p.Points);

});//個體所有題目知識點并集跟期望試卷知識點交集var

common

=

kp.Intersect(paper.Points);

unitList[i].KPCoverage

=

common.Count()

*

1.00

/

paper.Points.Count;

}returnunitList;

}適應(yīng)度方法確實定上一篇文章里已經(jīng)說過，即：f=1-(1-M/N)*f1-|EP-P|*f2

其中M/N為知識點覆蓋率，EP為期望難度系數(shù)，P為種群個體難度系數(shù)，f1為知識點分布的權(quán)重，f2為難度系數(shù)所占權(quán)重。當(dāng)f1=0時退化為只限制試題難度系數(shù)，當(dāng)f2=0時退化為只限制知識點分布。實現(xiàn)代碼如下：///<summary>///計算種群適應(yīng)度///</summary>///<param

name="unitList">種群</param>///<param

name="paper">期望試卷</param>///<param

name="KPCoverage">知識點分布在適應(yīng)度計算中所占權(quán)重</param>///<param

name="Difficulty">試卷難度系數(shù)在適應(yīng)度計算中所占權(quán)重</param>///<returns>List</returns>public

List<Unit>

GetAdaptationDegree(List<Unit>

unitList,

Paper

paper,

double

KPCoverage,

double

Difficulty)

{unitList

=

GetKPCoverage(unitList,

paper);for

(inti

=

0;

i

<

unitList.Count;

i++)

{

unitList[i].AdaptationDegree

=

1

-

(1

-

unitList[i].KPCoverage)

*

KPCoverage

-

Math.Abs(unitList[i].Difficulty

-

paper.Difficulty)

*

Difficulty;

}returnunitList;

}3、選擇算子這里選擇算子采用輪盤賭選擇法，即適應(yīng)度越大的被選擇到的概率越大。比方說種群中有20個個體，那么每個個體的適應(yīng)度除以20個個體適應(yīng)度的和得到的就是該個體的被選擇的概率。輪盤賭選擇時，每個個體類似于輪盤中的一小塊扇形，扇形的大小與該個體被選擇的概率成正比。那么，扇形越大的個體被選擇的概率越大。這就是輪盤賭選擇法。算法實現(xiàn)代碼如下：///<summary>///選擇算子〔輪盤賭選擇〕///</summary>///<param

name="unitList">種群</param>///<param

name="count">選擇次數(shù)</param>///<returns>進入下一代的種群</returns>public

List<Unit>

Select(List<Unit>

unitList,

int

count)

{

List<Unit>

selectedUnitList

=

new

List<Unit>();//種群個體適應(yīng)度和doubleAllAdaptationDegree

=

0;unitList.ForEach(delegate(Unit

u)

{AllAdaptationDegree

+=

u.AdaptationDegree;

});

Random

rand

=

new

Random();while

(selectedUnitList.Count

!=

count)

{//選擇一個0—1的隨機數(shù)字double

degree

=

0.00;double

randDegree

=

rand.Next(1,

100)

*

0.01

*

AllAdaptationDegree;//選擇符合要求的個體for

(int

j

=

0;

j

<

unitList.Count;

j++)

{

degree

+=

unitList[j].AdaptationDegree;if

(degree

>=

randDegree)

{//不重復(fù)選擇if

(!selectedUnitList.Contains(unitList[j]))

{selectedUnitList.Add(unitList[j]);

}break;

}

}

}returnselectedUnitList;

}

4、交叉算子交叉算子在上一篇也做了說明，寫程序時為方便略做了一點更改，即把多點交叉改為單點交叉。在交叉過程在有幾個地方需要注意，一是要保正總分不變，二是保證交叉后沒有重復(fù)個體，算法實現(xiàn)如下：///<summary>///交叉算子///</summary>///<param

name="unitList">種群</param>///<param

name="count">交叉后產(chǎn)生的新種群個體數(shù)量</param>///<param

name="paper">期望試卷</param>///<returns>List</returns>public

List<Unit>

Cross(List<Unit>

unitList,

int

count,

Paper

paper)

{

List<Unit>

crossedUnitList

=

new

List<Unit>();

Random

rand

=

new

Random();while

(crossedUnitList.Count

!=

count)

{//隨機選擇兩個個體intindexOne

=

rand.Next(0,

unitList.Count);intindexTwo

=

rand.Next(0,

unitList.Count);

Unit

unitOne;

Unit

unitTwo;if

(indexOne

!=

indexTwo)

{unitOne

=

unitList[indexOne];unitTwo

=

unitList[indexTwo];//隨機選擇一個交叉位置int

crossPosition

=

rand.Next(0,

unitOne.ProblemCount

-

2);//保證交叉的題目分數(shù)合相同double

scoreOne

=

unitOne.ProblemList[crossPosition].Score

+

unitOne.ProblemList[crossPosition

+

1].Score;double

scoreTwo

=

unitTwo.ProblemList[crossPosition].Score

+

unitTwo.ProblemList[crossPosition

+

1].Score;if

(scoreOne

==

scoreTwo)

{//兩個新個體

Unit

unitNewOne

=

new

Unit();

unitNewOne.ProblemList.AddRange(unitOne.ProblemList);

Unit

unitNewTwo

=

new

Unit();

unitNewTwo.ProblemList.AddRange(unitTwo.ProblemList);//交換交叉位置后面兩道題for

(int

i

=

crossPosition;

i

<

crossPosition

+

2;

i++)

{

unitNewOne.ProblemList[i]

=

new

Problem(unitTwo.ProblemList[i]);

unitNewTwo.ProblemList[i]

=

new

Problem(unitOne.ProblemList[i]);

}//添加到新種群集合中

unitNewOne.ID

=

crossedUnitList.Count;

unitNewTwo.ID

=

unitNewOne.ID

+

1;if

(crossedUnitList.Count

<

count)

{crossedUnitList.Add(unitNewOne);

}if

(crossedUnitList.Count

<

count)

{crossedUnitList.Add(unitNewTwo);

}

}

}//過濾重復(fù)個體

crossedUnitList

=

crossedUnitList.Distinct(new

ProblemComparer()).ToList();

}//計算知識點覆蓋率及適應(yīng)度crossedUnitList

=

GetKPCoverage(crossedUnitList,

paper);

crossedUnitList

=

GetAdaptationDegree(crossedUnitList,

paper,

kpcoverage,

difficulty);returncrossedUnitList;

}上面過濾重復(fù)個體中用到了ProblemComparer類，這是一個自定義的比擬類，代碼如下：publicclassProblemComparer

:

IEqualityComparer<Unit>{publicbool

Equals(Unit

x,

Unit

y)

{bool

result

=

true;for

(inti

=

0;

i

<

;

i++)

{if

(x.ProblemList[i].ID

!=

y.ProblemList[i].ID)

{

result

=

false;break;

}

}return

result;

}publicintGetHashCode(Unit

obj)

{returnobj.ToString().GetHashCode();

}

}5、變異算子在變異過程中主要是要保證替換題目至少包含一個被替換題的有效知識點〔期望試卷中也包含此知識點〕，并要類型相同，分數(shù)相同而題號不同。算法實現(xiàn)代碼如下：///<summary>///變異算子///</summary>///<param

name="unitList">種群</param>///<param

name="problemList">題庫</param>///<param

name="paper">期望試卷</param>///<returns>List</returns>public

List<Unit>

Change(List<Unit>

unitList,

List<Problem>

problemList,

Paper

paper)

{

Random

rand

=

new

Random();int

index

=

0;unitList.ForEach(delegate(Unit

u)

{//隨機選擇一道題

index

=

rand.Next(0,

);

Problem

temp

=

u.ProblemList[index];//得到這道題的知識點

Problem

problem

=

new

Problem();for

(inti

=

0;

i

<

;

i++)

{if

((temp.Points[i]))

{(temp.Points[i]);

}

}//從數(shù)據(jù)庫中選擇包含此題有效知識點的同類型同分數(shù)不同題號試題varotherDB

=

from

a

inproblemListwhere

a.Points.Intersect(problem.Points).Count()

>

0

select

a;

List<Problem>

smallDB

=

otherDB.Where(p

=>

IsContain(paper,

p)).Where(o

=>

o.Score

==

temp.Score

&&

o.Type

==

temp.Type

&&

o.ID

!=

temp.ID).ToList();//從符合要求的試題中隨機選一題替換if

(smallDB.Count

>

0)

{intchangeIndex

=

rand.Next(0,

smallDB.Count);u.ProblemList[index]

=

smallDB[changeIndex];

}

});//計算知識點覆蓋率跟適應(yīng)度unitList

=

GetKPCoverage(unitList,

paper);unitList

=

GetAdaptationDegree(unitList,

paper,

kpcoverage,

difficulty);returnunitList;

}6、調(diào)用例如遺傳算法主要算法上面都已實現(xiàn)，現(xiàn)在就是調(diào)用了。調(diào)用過程按如下流程圖進行：基于遺傳算法的自動組卷系統(tǒng)流程圖這里初始種群大小設(shè)定為20，最大迭代次數(shù)為500，適應(yīng)度為0.98，選擇算子選擇次數(shù)為10次，交叉算子產(chǎn)生的個體數(shù)量為20，期望試卷難度系數(shù)為0.72，總分為100分，各種題型題數(shù)為：20〔單項選擇〕,5〔多項選擇〕,10〔判斷〕,7〔填空〕,5〔問答〕，包含的知識點為：1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43,45,47,49,51,53,55,57,59,61,63,65,67,69,71,73,75,77,79,81。代碼如下：///<summary>///調(diào)用例如///</summary>publicvoid

Show()

{//題庫

DB

db

=

new

DB();//期望試卷

Paper

paper

=

new

Paper()

{

ID

=

1,TotalScore

=

100,

Difficulty

=

0.72,

Points

=

new

List<int>()

{

1,

3,

5,

7,

9,

11,

13,

15,

17,

19,

21,

23,

25,

27,

29,

31,

33,

35,

37,

39,

41,

43,

45,

47,

49,

51,

53,

55,

57,

59,

61,

63,

65,

67,

69,

71,

73,

75,

77,

79,

81

},EachTypeCount

=

new[]

{

20,

5,

10,

7,

5

}

};//迭代次數(shù)計數(shù)器int

count

=

1;//適應(yīng)度期望值double

expand

=

0.98;//最大迭代次數(shù)intrunCount

=

500;//初始化種群

List<Unit>

unitList

=

CSZQ(20,

paper,

db.ProblemDB);Console.WriteLine("\n\n

-------遺傳算法組卷系統(tǒng)(://wwwblogs/durongjian/)---------\n\n");Console.WriteLine("初始種群：");ShowUnit(unitList);Console.WriteLine("-----------------------迭代開始------------------------");//開始迭代while

(!IsEnd(unitList,

expand))

{Console.WriteLine("在第

"

+

(count++)

+

"代未得到結(jié)果");if

(count

>

runCount)

{Console.WriteLine("計算

"

+

runCount

+

"代仍沒有結(jié)果，請重新設(shè)計條件！");break;

}//選擇unitList

=

Select(unitList,

10);//交叉unitList

=

Cross(unitList,

20,

paper);//是否可以結(jié)束〔有符合要求試卷即可結(jié)束〕if

(IsEnd(unitList,

expand))

{break;

}//變異unitList

=

Change(unitList,

db.ProblemDB,

paper);

}if

(count

<=

runCount)

{Console.WriteLine("在第

"

+

count

+

"

代得到結(jié)果，結(jié)果為：\n");Console.WriteLine("期望試卷難度："

+

paper.Difficulty

+

"\n");ShowResult(unitList,

expand);

}

}最后在控制臺中調(diào)用此方法即可。7、其他輔助方法在上面的代碼中還調(diào)用了幾個輔助方法，下面一并給出：#region是否到達目標///<summary>///是否到達目標///</summary>///<param

name="unitList">種群</param>///<param

name="endcondition">結(jié)束條件〔適應(yīng)度要求〕</param>///<returns>bool</returns>publicboolIsEnd(List<Unit>

unitList,

doubleendcondition)

{if

(unitList.Count

>

0)

{for

(inti

=

0;

i

<

unitList.Count;

i++)