电商网站建设方向,宁德市人社局官网,wordpress云建站系统,贵阳网站app制作实例讲解 一、准备工作 1、问题实体 问题实体包含编号、类型#xff08;类型即题型#xff0c;分为五种#xff1a;单选#xff0c;多选#xff0c;判断#xff0c;填空#xff0c;问答#xff0c; 分别用1、2、3、4、5表示#xff09;、分数、难度系数、知识点。一…实例讲解 一、准备工作 1、问题实体 问题实体包含编号、类型类型即题型分为五种单选多选判断填空问答 分别用1、2、3、4、5表示、分数、难度系数、知识点。一道题至少有一个知识点为简单易懂知识点用List 表示知识点编号集合。 代码如下
public class Problem
{public Problem(){ID 0;Type 0;Score 0;Difficulty 0.00;Points new Listint();}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/// 编号/// /summarypublic int ID { get; set; }/// summary/// 题型1、2、3、4、5对应单选多选判断填空问答/// /summarypublic int Type { get; set; }/// summary/// 分数/// /summarypublic int Score { get; set; }/// summary/// 难度系数/// /summarypublic double Difficulty { get; set; }/// summary/// 知识点/// /summarypublic Listint Points { get; set; }} 2、题库 为了简单这里没有用数据库题目信息临时创建保存在内存中。因为对不同层次的考生一道题目在不同试卷中的分数可能不一样因此题目分数一般是老师出卷时定的不保存在题库中。且单选多选判断题每题分数应该相同填空题一般根据空数来定分数而问答题一般根据题目难度来定的因此这里的单选、多选、判断分数相同填空空数取1-4间的随机数填空题分数即为空数问答题即为该题难度系数*10取整。这里各种题型均为1000题具体应用时改为数据库即可。 代码如下
public class DB
{/// summary/// 题库/// /summarypublic ListProblem ProblemDB;public DB(){ProblemDB new ListProblem();Problem model;Random rand new Random();Listint Points;for (int i 1; i 5000; i){model new Problem();model.ID i;//试题难度系数取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);}//问答题分数为难度系数*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 Listint();//每题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、 试卷实体 试卷一般包含试卷编号试卷名称考试时间难度系数知识点分布总题数 总分数各种题型所占比率等属性这里为简单去掉了试卷名称跟考试时间。其中的知识点分布即老师出卷时选定本试卷要考查的知识点这里用List知识点编号集合表示。 代码如下
public class Paper
{/// summary/// 编号/// /summarypublic int ID { get; set; }/// summary/// 总分/// /summarypublic int TotalScore { get; set; }/// summary/// 难度系数/// /summarypublic double Difficulty { get; set; }/// summary/// 知识点/// /summarypublic Listint Points { get; set; }/// summary/// 各种题型题数/// /summarypublic int[] EachTypeCount { get; set; }
} 二、开始遗传算法组卷之旅 准备工作已经OK下面就按上一篇介绍的流程进行操作啦1、产生初始种群 这里保证题数跟总分达到出卷要求即可但为操作方便这里再定义一个种群个体实体类Unit包含编号、适应度、题数、总分、难度系数、知识点分布、包含的题目等信息也可以修改一下试卷实体用试卷实体表示
public class Unit{public Unit(){ID 0;AdaptationDegree 0.00;KPCoverage 0.00;ProblemList new ListProblem();}/// summary/// 编号/// /summarypublic int ID { get; set; }/// summary/// 适应度/// /summarypublic double AdaptationDegree { get; set; }/// summary/// 难度系数本试卷所有题目分数*难度系数/总分/// /summarypublic double Difficulty{get{double diff 0.00;ProblemList.ForEach(delegate(Problem p){diff p.Difficulty * p.Score;});return diff / SumScore;}}/// summary/// 题目数量/// /summarypublic int ProblemCount{get{return ProblemList.Count;}}/// summary/// 总分/// /summarypublic int SumScore{get{int sum 0;ProblemList.ForEach(delegate(Problem p){sum p.Score;});return sum;}}/// summary/// 知识点分布/// /summarypublic double KPCoverage { get; set; }/// summary/// 题目/// /summarypublic ListProblem ProblemList { get; set; }
}下面即来产生初始种群按个体数量期望试卷知识点分布各类型题目数等限制产生初始种群
/// summary
/// 初始种群
/// /summary
/// param namecount个体数量/param
/// param namepaper期望试卷/param
/// param nameproblemList题库/param
/// returns初始种群/returns
public ListUnit CSZQ(int count, Paper paper, ListProblem problemList)
{ListUnit unitList new ListUnit();int[] eachTypeCount paper.EachTypeCount;Unit unit;Random rand new Random();for (int i 0; i count; i){unit new Unit();unit.ID i 1;unit.AdaptationDegree 0.00;//总分限制while (paper.TotalScore ! unit.SumScore){unit.ProblemList.Clear();//各题型题目数量限制for (int j 0; j eachTypeCount.Length; j){ListProblem 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){//选择不重复的题目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);}//计算知识点覆盖率及适应度unitList GetKPCoverage(unitList, paper);unitList GetAdaptationDegree(unitList, paper, kpcoverage, difficulty);return unitList;
} 2、计算种群个体的适应度 在上面的代码中最后调用了两个方法GetKPCoverage跟GetAdaptationDegree这两个方法分别是计算种群中个体的知识点覆盖率跟适应度。
关于种群个体的知识点覆盖率在上一篇文章中已经说过了知识点分布用一个个体知识点的覆盖率来衡量例如期望本试卷包含N个知识点而一个个体中所有题目知识点的并集中包含M个MN则知识点的覆盖率为M/N。具体算法如下
/// summary/// 计算知识点覆盖率
/// /summary
/// param nameunitList种群/param
/// param namepaper期望试卷/param
/// returnsList/returns
public ListUnit GetKPCoverage(ListUnit unitList, Paper paper)
{Listint kp;for (int i 0; i unitList.Count; i){kp new Listint();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;}return unitList;
}
适应度方法的确定上一篇文章里已经说过即 f1-(1-M/N)*f1-|EP-P|*f2
其中M/N为知识点覆盖率EP为期望难度系数P为种群个体难度系数f1为知识点分布的权重f2为难度系数所占权重。当f10时退化为只限制试题难度系数当f20时退化为只限制知识点分布。 实现代码如下
/// summary/// 计算种群适应度
/// /summary
/// param nameunitList种群/param
/// param namepaper期望试卷/param
/// param nameKPCoverage知识点分布在适应度计算中所占权重/param
/// param nameDifficulty试卷难度系数在适应度计算中所占权重/param
/// returnsList/returns
public ListUnit GetAdaptationDegree(ListUnit unitList, Paper paper, double KPCoverage, double Difficulty)
{unitList GetKPCoverage(unitList, paper);for (int i 0; i unitList.Count; i){unitList[i].AdaptationDegree 1 - (1 - unitList[i].KPCoverage) * KPCoverage - Math.Abs(unitList[i].Difficulty - paper.Difficulty) * Difficulty;}return unitList;
}3、选择算子 这里选择算子采用轮盘赌选择法即适应度越大的被选择到的概率越大。比如说种群中有20个个体那么每个个体的适应度除以20个个体适应度的和得到的就是该个体的被选择的概率。轮盘赌选择时每个个体类似于轮盘中的一小块扇形扇形的大小与该个体被选择的概率成正比。那么扇形越大的个体被选择的概率越大。这就是轮盘赌选择法。 算法实现代码如下
/// summary
/// 选择算子轮盘赌选择
/// /summary
/// param nameunitList种群/param
/// param namecount选择次数/param
/// returns进入下一代的种群/returns
public ListUnit Select(ListUnit unitList, int count)
{ListUnit selectedUnitList new ListUnit();//种群个体适应度和double AllAdaptationDegree 0;unitList.ForEach(delegate(Unit u){AllAdaptationDegree u.AdaptationDegree;});Random rand new Random();while (selectedUnitList.Count ! count){//选择一个0—1的随机数字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){//不重复选择if (!selectedUnitList.Contains(unitList[j])){selectedUnitList.Add(unitList[j]);}break;}}}return selectedUnitList;
} 4、交叉算子 交叉算子在上一篇也做了说明写程序时为方便略做了一点更改即把多点交叉改为单点交叉。在交叉过程在有几个地方需要注意一是要保正总分不变二是保证交叉后没有重复个体算法实现如下 /// summary/// 交叉算子/// /summary/// param nameunitList种群/param/// param namecount交叉后产生的新种群个体数量/param/// param namepaper期望试卷/param/// returnsList/returnspublic ListUnit Cross(ListUnit unitList, int count, Paper paper){ListUnit crossedUnitList new ListUnit();Random rand new Random();while (crossedUnitList.Count ! count){//随机选择两个个体int indexOne rand.Next(0, unitList.Count);int indexTwo 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);//保证交叉的题目分数合相同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);}}}//过滤重复个体crossedUnitList crossedUnitList.Distinct(new ProblemComparer()).ToList();}//计算知识点覆盖率及适应度crossedUnitList GetKPCoverage(crossedUnitList, paper);crossedUnitList GetAdaptationDegree(crossedUnitList, paper, kpcoverage, difficulty);return crossedUnitList;}上面过滤重复个体中用到了ProblemComparer类这是一个自定义的比较类代码如下 public class ProblemComparer : IEqualityComparerUnit{public bool Equals(Unit x, Unit y){bool result true;for (int i 0; i x.ProblemList.Count; i){if (x.ProblemList[i].ID ! y.ProblemList[i].ID){result false;break;}}return result;}public int GetHashCode(Unit obj){return obj.ToString().GetHashCode();}
}5、 变异算子 在变异过程中主要是要保证替换题目至少包含一个被替换题的有效知识点期望试卷中也包含此知识点并要类型相同分数相同而题号不同。 算法实现代码如下
/// summary
/// 变异算子
/// /summary
/// param nameunitList种群/param
/// param nameproblemList题库/param
/// param namepaper期望试卷/param
/// returnsList/returns
public ListUnit Change(ListUnit unitList, ListProblem problemList, Paper paper)
{Random rand new Random();int index 0;unitList.ForEach(delegate(Unit u){//随机选择一道题index rand.Next(0, u.ProblemList.Count);Problem temp u.ProblemList[index];//得到这道题的知识点Problem problem new Problem();for (int i 0; i temp.Points.Count; i){if (paper.Points.Contains(temp.Points[i])){problem.Points.Add(temp.Points[i]);}}//从数据库中选择包含此题有效知识点的同类型同分数不同题号试题var otherDB from a in problemListwhere a.Points.Intersect(problem.Points).Count() 0select a;ListProblem 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){int changeIndex rand.Next(0, smallDB.Count);u.ProblemList[index] smallDB[changeIndex];}});//计算知识点覆盖率跟适应度unitList GetKPCoverage(unitList, paper);unitList GetAdaptationDegree(unitList, paper, kpcoverage, difficulty);return unitList;
} 遗传算法主要算法上面都已实现现在就是调用了。调用过程按如下流程图进行 这里初始种群大小设定为20最大迭代次数为500适应度为0.98选择算子选择次数为10次交叉算子产生的个体数量为20期望试卷难度系数为0.72总分为100分各种题型题数为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/// 调用示例/// /summarypublic void Show(){//题库DB db new DB();//期望试卷Paper paper new Paper(){ID 1,TotalScore 100,Difficulty 0.72,Points new Listint() { 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 }};//迭代次数计数器int count 1;//适应度期望值double expand 0.98;//最大迭代次数int runCount 500;//初始化种群ListUnit unitList CSZQ(20, paper, db.ProblemDB);Console.WriteLine(\n\n -------遗传算法组卷系统(http://www.cnblogs.com/durongjian/)---------\n\n);Console.WriteLine(初始种群);ShowUnit(unitList);Console.WriteLine(-----------------------迭代开始------------------------);//开始迭代while (!IsEnd(unitList, expand)){Console.WriteLine(在第 (count) 代未得到结果);if (count runCount){Console.WriteLine(计算 runCount 代仍没有结果请重新设计条件);break;}//选择unitList Select(unitList, 10);//交叉unitList Cross(unitList, 20, paper);//是否可以结束有符合要求试卷即可结束if (IsEnd(unitList, expand)){break;}//变异unitList Change(unitList, db.ProblemDB, paper);}if (count runCount){Console.WriteLine(在第 count 代得到结果结果为\n);Console.WriteLine(期望试卷难度 paper.Difficulty \n);ShowResult(unitList, expand);}} 最后在控制台中调用此方法即可。 7、其他辅助方法 在上面的代码中还调用了几个辅助方法下面一并给出
#region 是否达到目标/// summary/// 是否达到目标/// /summary/// param nameunitList种群/param/// param nameendcondition结束条件适应度要求/param/// returnsbool/returnspublic bool IsEnd(ListUnit unitList, double endcondition){if (unitList.Count 0){for (int i 0; i unitList.Count; i){if (unitList[i].AdaptationDegree endcondition){return true;}}}return false;}#endregion#region 显示结果/// summary/// 显示结果/// /summary/// param nameunitList种群/param/// param nameexpand期望适应度/parampublic void ShowResult(ListUnit unitList, double expand){unitList.OrderBy(o o.ID).ToList().ForEach(delegate(Unit u){if (u.AdaptationDegree expand){Console.WriteLine(第 u.ID 套);Console.WriteLine(题目数量\t知识点分布\t难度系数\t适应度);Console.WriteLine(u.ProblemCount \t\t u.KPCoverage.ToString(f2) \t\t u.Difficulty.ToString(f2) \t\t u.AdaptationDegree.ToString(f2)\n\n);}});}#endregion#region 显示种群个体题目编号/// summary/// 显示种群个体题目编号/// /summary/// param nameu种群个体/parampublic void ShowUnit(Unit u){Console.WriteLine(编号\t知识点分布\t难度系数);Console.WriteLine(u.ID \t u.KPCoverage.ToString(f2) \t\t u.Difficulty.ToString(f2));u.ProblemList.ForEach(delegate(Problem p){Console.Write(p.ID \t);});Console.WriteLine();}#endregion #region 题目知识点是否符合试卷要求
/// summary
/// 题目知识点是否符合试卷要求
/// /summary
/// param namepaper期望试卷/param
/// param nameproblem一首试题/param
/// returnsbool/returns
private bool IsContain(Paper paper, Problem problem)
{for (int i 0; i problem.Points.Count; i){if (paper.Points.Contains(problem.Points[i])){return true;}}return false;
}
#endregion
