遗传算法
遗传算法是仿真生物遗传学和自然选择机理,通过人工方式所构造的一类搜索算法,从某种程度上说遗传算法是对生物进化过程进行的数学方式仿真。霍兰德(Holland)在他的著作《Adaptation in Natural and Artificial Systems》首次提出遗传算法,并主要由他和他的学生发展起来的。
生物种群的生存过程普遍遵循达尔文进化准则,群体中的个体根据对环境的适应能力而被大自然所选择或淘汰。进化过程的结果反映在个体的结构上,其染色体包含若干基因,相应的表现型和基因型的联系体现了个体的外部特性与内部机理间逻辑关系。通过个体之间的交叉、变异来适应大自然环境。生物染色体用数学方式或计算机方式来体现就是一串数码,仍叫染色体,有时也叫个体;适应能力是对应着一个染色体的一个数值来衡量;染色体的选择或淘汰则按所面对的问题是求最大还是最小来进行。
遗传算法自从1965年提出以来,在国际上已经形成了一个比较活跃的研究领域,已召开了多次比较重要的国际会议和创办了很多相关的国际刊物。
遗传算法已用于求解带有应用前景的一些问题,例如遗传程序设计、函数优化、排序问题、人工
神经网络、分类系统、计算机图像处理和机器人运动规划等。
遗传算法的基本原理
遗传算法类似于自然进化,通过作用于染色体上的基因寻找好的染色体来求解问题。与自然界相似,遗传算法对求解问题的本身一无所知,它所需要的仅是对算法所产生的每个染色体进行评价,并基于适应值来选择染色体,使适应性好的染色体有更多的繁殖机会。在遗传算法中,通过随机方式产生若干个所求解问题的数字编码,即染色体,形成初始群体;通过适应度函数给每个个体一个数值评价,淘汰低适应度的个体,选择高适应度的个体参加遗传操作,经过遗传操作后的个体集合形成下一代新的种群。对这个新种群进行下一轮进化。这就是遗传算法的基本原理。
下面就是遗传算法思想:
(1) 初始化群体;
(2) 计算群体上每个个体的适应度值;
(3) 按由个体适应度值所决定的某个规则选择将进入下一代的个体;
(4) 按概率Pc进行交叉操作;
(5) 按概率Pc进行突变操作;
(6) 没有满足某种停止条件,则转第(2)步,否则进入(7)。
(7) 输出种群中适应度值最优的染色体作为问题的满意解或最优解。
程序的停止条件最简单的有如下二种:完成了预先给定的进化代数则停止;种群中的最优个体在连续若干代没有改进或平均适应度在连续若干代基本没有改进时停
遗传算法的收敛性
一些研究人员对进化算法的运行机理进行过研究,Radolph在文献[1]中证明了一般的遗传算法不一定收敛,只有每代保存了最优个体时才收敛。在实际应用中,使用了上述结论来保证收敛性。采用优秀个体保护法就是将每代中的最优个体,直接进入子代,相应淘汰其子代中适应度最差的个体,使种群规模不变。
对保存最优个体时遗传算法是收敛的结论的证明是通过对遗传算法构造马尔柯夫(markov)链,因为遗传算法的进行过程是一个马尔柯夫过程。
当遗传算法收敛时,求到的解通常只是所要解决问题的最优解的一个近似解,或者叫满意解。从数学分析的角度看,收敛过程是一个无限逼近过程,而计算过程是一个有限自动机,因此通过遗传算法程序求得的解总是一个近似解。近似解与问题真正的最优解的差是一个统计意义下的量,也就是说每次程序运行得到的解的质量可能是有较大的差别的。