遗传算法

第六章遗传算法6.1什么是遗传算法6.2遗传算法的理论基础6.3示例及研究动态6.1概述6.1.1遗传算法的生物遗传学基础6.1.2遗传算法的基本操作6.1.3遗传算法的特点6.1.1遗传算法的生物遗传学基础遗传算法是根据生物进化的模型提出的一种优化算法。它的主要因素是：遗传、变异、选择。遗传是指子代总是和亲代相似。是生物进化的基础。变异是指子代和亲代有某些不相似的现象，是生物个体之间相互区别的基础。选择是指具有精选的能力，它决定生物进化的方向。遗传算法正是吸取了“适者生存，优胜劣汰”的进化原理，从而能够在复杂空间中进行鲁棒搜索。Gen=1初始化种群编码计算适应值是否满足终止条件否是交叉选择Gen=Gen+1开始变异结束6.1.2遗传算法的基本操作复制交叉变异复制从一个旧种群（OldPopulation）中选择生命力强的个体位串（字符串）（IndividualString）产生新种群的过程。目标函数f是期望的最大效益或好处的某种量度。它决定位串被复制或淘汰的决定因素。往往高适应度的位串更有可能在下一代中产生一个或多个子孙。编号位串（x）适应度f(x)=x2占总数的百分比（％）1234011011100001000100111695766436114.449.25.530.9总和1170100.0编号位串（x）期望的复制数实际得到的复制数1234011011100001000100110.581.970.221.231201交叉在遗传算法中起着核心的作用。是个体之间的重新组合以产生新个体。交叉前：串1：a1a2a3a4a5串2：b1b2b3b4b5交叉后：新串1：a1a2b3b4b5新串2：b1b2a3a4a5变异某个字符串某一位的值偶然的（概率很小的）随机的改变。是一种防止过度成熟而丢失重要概念的保险策略。在遗传算法中的作用是第二位的，但却必不可少。6.1.3遗传算法主要问题编码；适应度函数；遗传算子，杂交+变异；迭代次数；变异率、杂交率。主要问题求子集问题：0-1背包，装船问题，最大团。求排列问题：圆排列，tsp,工序问题，其他问题：求子集问题：0-1背包，装船。求排列问题：圆排列，工序问题其他问题：函数优化问题。