遗传算法研究综述+文献综述(3)
时间:2017-05-03 11:18 来源:毕业论文 作者:毕业论文 点击:次
经过这一系列的过程（选择、交配和突变），产生的新一代个体不同于初始的一代，并一代一代向增加整体适应度的方向发展，因为最好的个体总是更多的被选择去产生下一代，而适应度低的个体逐渐被淘汰掉。这样的过程不断的重复：每个个体被评价，计算出适应度，两个个体交配，然后突变，产生第三代。周而复始，直到终止条件满足为止。一般终止条件有以下几种： • 进化次数限制； • 计算耗费的资源限制（例如计算时间、计算占用的内存等）； • 一个个体已经满足最优值的条件，即最优值已经找到； • 适应度已经达到饱和，继续进化不会产生适应度更好的个体； • 人为干预； • 以及以上两种或更多种的组合[3]。 长度为L的n个二进制串bi(i＝1，2，…，n)组成了遗传算法的初解群，也称为初始群体。在每个串中，每个二进制位就是个体染色体的基因。根据进化术语，对群体执行的操作有三种： 1．选择(Selection) 这是从群体中选择出较适应环境的个体。这些选中的个体用于繁殖下一代。故有时也称这一操作为再生(Reproduction)。由于在选择用于繁殖下一代的个体时，是根据个体对环境的适应度而决定其繁殖量的，故而有时也称为非均匀再生(differential reproduction)。 2．交叉(Crossover) 这是在选中用于繁殖下一代的个体中，对两个不同的个体的相同位置的基因进行交换，从而产生新的个体。 3．变异(Mutation) 这是在选中的个体中，对个体中的某些基因执行异向转化。在串bi中，如果某位基因为1，产生变异时就是把它变成0；反亦反之。 遗传算法的原理可以简要给出如下： choose an intial population determine the fitness of each inpidual perform selection repeat perform crossover perform mutation determine the fitness of each inpidual perform selection until some stopping criterion applies 这里所指的某种结束准则一般是指个体的适应度达到给定的阀值；或者个体的适应度的变化率为零[4]。 4遗传算法的基本流程 1 GA的流程图 GA的流程图如下图所示 2 编码 遗传算法不能直接处理问题空间的参数，必须把它们转换成遗传空间的由基因按一定结构组成的染色体或个体。这一转换操作就叫做编码，也可以称作(问题的)表示(representation)。 评估编码策略常采用以下3个规范: a)完备性(completeness):问题空间中的所有点(候选解)都能作为GA空间中的点(染色体)表现。 b)健全性(soundness): GA空间中的染色体能对应所有问题空间中的候选解。 c)非冗余性(nonredundancy):染色体和候选解一一对应。 目前的几种常用的编码技术有二进制编码，浮点数编码，字符编码，变成编码等。 而二进值编码是目前遗传算法中最常用的编码方法。即是由二进值字符集{0, 1}产生通常的0, 1字符串来表示问题空间的候选解。它具有以下特点: a)简单易行； b)符合最小字符集编码原则； c)便于用模式定理进行分析，因为模式定理就是以基础的。 3 适应度函数 进化论中的适应度，是表示某一个体对环境的适应能力，也表示该个体繁殖后代的能力。遗传算法的适应度函数也叫评价函数，是用来判断群体中的个体的优劣程度的指标，它是根据所求问题的目标函数来进行评估的。 (责任编辑：qin) |