研究生遗传算法总结讲义

《研究生遗传算法总结讲义》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、相似问题及改进策略一、0-1背包问题背包问题是计算科学中的一个经典NP--hard问题,一般提法为:已知n个物品的容积及价值分别为wi和ci，背包的最大容量限制为M，如何选择物品装入背包，使得在背包最大容量限制内，所装入的物品的总价值最大?简单遗传算法的具体的步骤如下:步骤一:为物品的状态编码，迭代变量t=1。若选择进入背包，其编码为1，不选入背包，编码为O。随机初始化群体。步骤二:利用约束条件，首先判断产生的染色体是否能全部够装入背包，超出了背包容积M，则再次通过随机方法产生一些新的符合总体积约束的染色体作为替代。步骤三:计算此时种群中的各个染色体的适应值。步骤四:计

2、算选择概,以概率PoP(t)中随机产生一些染色体组成新的种群。步骤五:用改进简单交叉的方法对染色体进行交配。步骤六:用基本变异算子对上一步产生的种群中的染色体上的基因进行变异运算。步骤七:如果t达到对其迭代的要求次数，则算法结束，否则，返回步骤二继续进行计算。二、在试题组卷中的应用设立题库之前，必须首先确定学科的知识结构，在按学科知识点结构组织试题。试题的数量要足够多，在各指标属性区间内均匀分布，核心属性有：知识点、难度与认知分类。？模拟试题库的建立要如实评价算法，建立的这个模拟题库必须要尽量符合实际情况。1、试题编号：指向试题库中某试题的索引。在组卷开始的时候从数据库

3、中读出满足曝光度要求的试题的各项组卷中需要用到的各项指标，并依靠这个编号与试题的其他在组卷算法中未使用的内容相关联。在完成组卷后，对被选中的试题根据该索引获取试题的详细容并根据要求进行编排打印该参数对测试组卷算法的性能没影响，可以省略。2.题型3.所属章节4.难度5.区分度6.知识点7.认知层次8.分数9.时间组卷策略将这些试题的各个参数组成一个结构体数组，该数组中仅存放算法需要用到的参数，至于题目的正文、图表和其他备注信息则无需保存，以节省内存。在采用组卷算法得到一个合适的试卷后，根据被选中题目的编号从题库中读出试题的详细信息，并据此进行编排，从而得到一份合格的试卷。

4、*存放试题参数的结构体定义编码方案中：由于每个试题有“选中”与“未选中”两种状态，因此可以非常方便的采用二进制编码来标识该题是否选中。编码的长度就是前面建立的模拟试题*目标函数的函数值计算为了计算目标函数的函数值，必须要统计每一个试卷的各种参数分布。本文将各个参数的级别作为数组的索引，可以在一次循环中完成各个参数分布的统计。在统计完各个参数的分布后，就可以根据组卷要求计算各个参数分布的偏差，进而根据各个参数的权重，最终计算出目标函数的函数值。适应度函数的设计目标函数的定义可知为了应用前面章节中提出的改进的自适应遗传算法，将函数取负号，转化成极大值问题。交叉和变异的过程中

5、对两个个体进行交叉运算。为了保证试卷中各种题型试题的题量不变，采用段间交叉。段间交叉的方法:首先随机选择一个交叉点，检查这个交叉点处的试题属于哪一种题型，并查找该题型试题的首位置，将该首位置作为实际交叉点，进行交叉操作。若该点为“1”，则表示该题被选中;然后从该点对应的试题所在题型中再随机选取一个为“0”的点，并将该点置为“1”;最后将变异点置为“0”。若该点为“O”，则表示该题未被选中;然后从该点所对应的试题所在题型中再随机选取一个为“1”的点，并将该点置为“0”最后将变异点置为“l”。考虑：路径的为选择处即编码基因为0处在交叉和变异时是否改变。遗传算法在高级计划与排

6、程问题中的应用有K个客户订单要在N个机器上加工；对于其中一个客户订单，需要由多个作业加工完成，每个作业包括多道工序；作业内的部分工序之间的加工顺序具有优先约束；每道工序可在多个可替代的不同机器上执行；工序加工过程不可被抢占；部分机器支持外包。求解目标是，对于每个客户订单，找出最优的工序序列和排程方案，使得所有订单总完成时间最小，且满足所有约束。采用拓扑排序（TopologicalSort,TS）算法确定一个作业中的工序的加工顺序。对于一个AOV（activityonvertex）网络，采用拓扑排序算法可以对其中的顶点集合产生一个线性顶点序列。对于网络中的两个节点i和j，

7、如果i是j的前驱节点，则生成的线性顶点序列中，i也必须在v前面。这样的一个线性顶点序列称为拓扑序列，为找到拓扑序列，首先要选择一个没有入边的顶点并输出，接着将这个顶点及关联的边从图中移除。问题改进遗传算法描述思路一（设置参数考察，替换遗传操作中的染色体）首先考虑种群的多样性，用遗传算法解决问题时，由于种群小，导致算法循环一定次数过后，原本随机产生的群体现在过于集中，使用杂交的方法己经没有能力来产生不同染色体的种群，从而停滞于局部最优解，此时需要产生新的染色体来保持多样性，于是便引入了一个新的参数用于考察种群中的染色体的相似程度。其思想是如