研究生遗传算法总结讲义.ppt

类似问题和改进策略，1，0-1背包问题背包问题是计算科学中一个经典的NP难问题，一般来说：被认为是n个物品的体积和价值分别是wi和ci，背包的最大容量被限制为m，如何选择物品装载到背包中，使装载物品的总价值在背包的最大容量限制内最大？简单遗传算法的具体步骤如下：步骤：-步骤：用迭代变量t=1对物品的状态进行编码。如果你选择进入背包，它的代码是1，如果你不选择进入背包，它的代码是o。随机初始化人口。步骤2 :利用约束条件，首先判断生成的所有染色体是否都可以装入背包并超过背包体积m，然后用随机方法再次生成一些符合总体积约束的新染色体作为替代。步骤3 :计算此时种群中每条染色体的适应值。计算选择概率，并以概率PoP(t)随机产生一些染色体，形成一个新的群体。用改进的简单杂交方法交配染色体。步骤6 :使用基本突变算子对上一步生成的群体中染色体上的基因进行突变操作。步骤7 :如果T达到所需的迭代次数，算法结束，否则，计算返回到步骤2继续。在建立题库之前，我们必须首先确定学科的知识结构，并根据学科的知识结构组织问题。试题的数量应该足够大，以便在每个索引属性区间内均匀分布。核心属性包括知识点、难度和认知分类。什么？模拟试题库的建立必须真实评估算法，建立的模拟试题库必须尽可能符合实际情况。1.项目编号：指项目库中项目的索引。在试卷生成开始时，从数据库中读出满足暴露要求的每一次试卷生成所需的索引，并且这些索引与试卷生成算法中未使用的试卷的其他内容相关联。试卷生成完成后，所选试题将按照索引给出详细内容，并按照要求进行排列和打印。该参数对试卷生成算法的性能没有影响，可以省略。为了节省内存，这些问题的每个参数被组织成一个结构数组，它只存储算法所需的参数，而不需要保存问题的文本、图表和其他注释。在使用试卷生成算法获得合适的试卷后，根据所选题目的数量从试卷库中读出试卷的详细信息，并进行相应的排列，从而获得合格的试卷。*用于存储试题参数的结构定义。在编码方案中：由于每个试题有“已选”和“未选”两种状态，使用二进制编码来识别试题是否被选中非常方便。代码长度是预先建立的模拟试卷*目标函数的函数值计算。为了计算目标函数的函数值，必须计算每张试卷的各种参数分布。本文以每个参数的级别作为数组的索引，每个参数分布的统计可以在一个周期内完成。统计各参数的分布后，根据试卷要求计算各参数分布的偏差，最后根据各参数的权重计算目标函数的函数值。适应度函数设计目标函数的定义表明，为了应用前几章提出的改进自适应遗传算法，将函数的负号转化为最大值问题。在交叉和变异过程中，两个个体进行交叉操作。为了确保试卷中各种类型的问题数量相同，采用了横截面。横截面方法：首先随机选择一个横截面点，检查该横截面点处的问题属于哪个问题类型，并找到该问题的标题位置如果这一点是“0”，这意味着问题没有被选择。然后从与该点对应的问题类型中随机选择一个“1”点，将该点设置为“0”，最后将变化点设置为“L”。考虑：选择路线，即在杂交和突变时编码基因是否改变。遗传算法在高级计划和调度问题中的应用，有k个客户订单需要在n台机器上处理；对于一个客户订单，需要进行多道工序处理，每道工序包括多道工序；操作中某些操作之间的处理顺序有优先级限制；每个过程可以在多个可选的不同机器上执行；进程不能被抢占。有些机器支持外包。该解决方案的目标是找出每个客户订单的最优操作顺序和调度方案，从而使所有订单的总完成时间最小化并满足所有约束。拓扑排序(ts)算法用于确定作业中操作的处理顺序。对于AOV(activityonvertex)网络，可以使用拓扑排序算法为顶点集生成线性顶点序列。对于网络中的两个节点I和j，如果我是j的前体节点，那么在生成的线性顶点序列中，我也必须在v之前。这种线性顶点序列称为拓扑序列。为了找到拓扑序列，首先应该选择并输出一个没有输入边的顶点，然后从图中删除该顶点及其相关边。首先，考虑人口的多样性。当用遗传算法解决问题时，由于种群规模小，原来随机产生的种群经过一定的算法循环后现在过于集中。混合方法没有能力生成不同染色体的群体，因此停滞在局部最优解中。这时，需要产生新的染色体来保持多样性。因此，引入一个新的参数来研究群体中染色体的相似性。其思想是，如果待杂交的染色体过于相似，那么根据适者生存的原则，一条或多条适应度函数最低或较低的染色体将被淘汰，然后产生新的染色体进行补充。这样做的优点是，通过比较可以看出染色体之间的相似性，从而可以保留需要改变适应值的染色体。通过对上述算法的调整，可以在保持种群多样性的同时，实现对优秀个体的保留。1982年，KirkPatrick等人将固体退火的思想引入到组合优化领域，提出了一种有效的近似算法来解决大规模组合优化问题，尤其是NP完全组合优化问题。固体退火过程的物理图像和统计特性是模拟退火算法的物理背景。接受准则使算法跳出局部优化的“陷阱”。当固体温度高时(遗传算法的早期阶段)，具有相似适应度的个体产生后代的概率相似；然而，当温度持续下降时，具有相似适应度的个体之间的适应度差异将扩大，从而使突出的个体优势更加明显。该算法框架考虑到在之前提出的捕食策略中，通过改变交叉和变异率来调整搜索策略，并且可以考虑调整种群适应值的分布以及交叉和变异的位置的方法，这种方法是人为设置的，有利于初始阶段的粗搜索和后期阶段的精搜索。然而，也有人认为，粗略搜索时，最佳解容易丢失，精细搜索时，最佳解容易陷入局部极小值。为了解决一些问题，可以考虑小生境技术的最优解保持策略来解决算法中最优解容易丢失的缺点，并利用其汉明距离排除策略来增强解的多样性。在计算过程中，自适应值函数的自适应调整是根据组自适应值的分布自适应的。引入自适应常数Cmin，根据群体中每个个体自适应值的分布自适应调整算法。Cmin越大，越小小生境技术，小生境技术是将每一代个体分成几个类，每个类选择若干个适应度较大的个体作为一个类的优秀代表，形成一个种群，然后通过杂交和变异在种群中和不同种群之间产生新一代个体群。同时，采用预选机制、挤出机制或共享机制来完成选择操作。首先，比较小组中个体之间的距离。如果距离在预先指定的距离L内(引入汉明距离)，则比较两者之间的适应度，并对适应度较低的个体应用强罚函数，从而大大降低其适应度。因此，对于在预定距离L内的两个个体，较差的个体在处理后的适应度变得更差，并且在随后的进化过程中被消除的概率很大。也就是说，在距离L内将只有一个优秀的个体，从而保持群体的多样性，保持个体之间的一定距离，并使个体分散在整个约束空间中。