遗传算法简介

frogfish

遗传算法
遗传算法是仿真生物遗传学和自然选择机理，通过人工方式所构造的一类搜索算法，从某种程度上说遗传算法是对生物进化过程进行的数学方式仿真。霍兰德(Holland)在他的著作《Adaptation in Natural and Artificial Systems》首次提出遗传算法，并主要由他和他的学生发展起来的。
       生物种群的生存过程普遍遵循达尔文进化准则，群体中的个体根据对环境的适应能力而被大自然所选择或淘汰。进化过程的结果反映在个体的结构上，其染色体包含若干基因，相应的表现型和基因型的联系体现了个体的外部特性与内部机理间逻辑关系。通过个体之间的交叉、变异来适应大自然环境。生物染色体用数学方式或计算机方式来体现就是一串数码，仍叫染色体，有时也叫个体；适应能力是对应着一个染色体的一个数值来衡量；染色体的选择或淘汰则按所面对的问题是求最大还是最小来进行。
       遗传算法自从1965年提出以来，在国际上已经形成了一个比较活跃的研究领域，已召开了多次比较重要的国际会议和创办了很多相关的国际刊物。
       遗传算法已用于求解带有应用前景的一些问题，例如遗传程序设计、函数优化、排序问题、人工神经网络、分类系统、计算机图像处理和机器人运动规划等。

遗传算法的基本原理
　　遗传算法类似于自然进化，通过作用于染色体上的基因寻找好的染色体来求解问题。与自然界相似，遗传算法对求解问题的本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评价，并基于适应值来选择染色体，使适应性好的染色体有更多的繁殖机会。在遗传算法中，通过随机方式产生若干个所求解问题的数字编码，即染色体，形成初始群体；通过适应度函数给每个个体一个数值评价，淘汰低适应度的个体，选择高适应度的个体参加遗传操作，经过遗传操作后的个体集合形成下一代新的种群。对这个新种群进行下一轮进化。这就是遗传算法的基本原理。
下面就是遗传算法思想：
　　(1) 初始化群体;
　　(2) 计算群体上每个个体的适应度值;
　　(3) 按由个体适应度值所决定的某个规则选择将进入下一代的个体;
　　(4) 按概率Pc进行交叉操作;
　　(5) 按概率Pc进行突变操作;
　　(6) 没有满足某种停止条件，则转第(2)步，否则进入(7)。
　　(7) 输出种群中适应度值最优的染色体作为问题的满意解或最优解。
　　程序的停止条件最简单的有如下二种：完成了预先给定的进化代数则停止；种群中的最优个体在连续若干代没有改进或平均适应度在连续若干代基本没有改进时停

遗传算法的收敛性
　　一些研究人员对进化算法的运行机理进行过研究，Radolph在文献[1]中证明了一般的遗传算法不一定收敛，只有每代保存了最优个体时才收敛。在实际应用中，使用了上述结论来保证收敛性。采用优秀个体保护法就是将每代中的最优个体，直接进入子代，相应淘汰其子代中适应度最差的个体，使种群规模不变。
　　对保存最优个体时遗传算法是收敛的结论的证明是通过对遗传算法构造马尔柯夫(markov)链，因为遗传算法的进行过程是一个马尔柯夫过程。
　　当遗传算法收敛时，求到的解通常只是所要解决问题的最优解的一个近似解，或者叫满意解。从数学分析的角度看，收敛过程是一个无限逼近过程，而计算过程是一个有限自动机，因此通过遗传算法程序求得的解总是一个近似解。近似解与问题真正的最优解的差是一个统计意义下的量，也就是说每次程序运行得到的解的质量可能是有较大的差别的。

frogfish

遗传算法的改进

         遗传算法的主要任务和目的，是设法产生或有助于产生优良的个体成员，且这些成员能够充分表现出解空间中的解，从而使算法效率提高并避免早熟收敛现象。但是，实际应用遗传算法时往往出现早熟收敛和收敛性能差等缺点。现今的改进方法，大都针对基因操作、基于知识的操作和并行化GA进行。

         对于复制操作，Dejong（1975）研究了回放式随机采样复制，其缺点是选择误差较大；同时，他又提出了无回放式随机采样复制以降低选择误差。Brindle(1981)提出了一种选择误差更小、操作简单的确定式采样以及无回放式余数随机采样方法。Back(1992)提出了与适配值大小和正负无关的均匀排序策略；同时又提出全局收敛的最优串复制策略，提高了搜索效率，但不适于非线性较强的问题。在交叉操作方面，有Goldberg(1989)提出的部分匹配交叉算子(partially mapped crossover),Starkweather等  提提出的增强边缘重组算子(enhanced  edge recombination),Davis(1991)提出的序号交叉算子( order crossover)和均匀排序交叉算子(uniform order-based crossover),Smith(1985)提出的循环交叉算子(cycle crossover),Dejong(1975)提出的单点交叉算子(one-point crossover)和多点交叉算子,Syswerda(1989)提出的双点交叉算子(two-point crossover),此外常用的交叉算子还有置换交叉,算术交叉,启发式交叉等.变异操作方面主要发展了自适应变异,多级变异等操作.为了改进算法的性能,一些高级的基因操作也得到了发展和应用,譬如双倍和显性遗传(diploid and dominance)用以把目前解群中最好的解直接放入下一代种群中,如此保证各代种群中总会有目前为止最好的解;静态繁殖(steady-state reproduction)用以在迭代过程中用部分优质子串来更新部分父串作为下一代种群以使优质的父串在下一代得以保留;没有重串的静态繁殖(steady-state without duplication)用以在形成下一代种群时不含重复的串.此外,还有多倍体结构(multiple chromosome structure),分离(segregation),异位(translocation)思想,这在分类问题中得到了应用.在基于知识的操作方面,主要是将问题的特殊信息与GA相结合,包括混合算法的构造以及在遗传算子中增加知识的操作等.

     遗传算法的结构也是很值得研究的问题.Krishnakumar(1989)为克服群体数目大造成计算时间长的缺点,提出了所谓GA的步群体方法,仿真结果显示了较高的计算效率和适于动态系统优化的潜力,但尚无严格的理论分析.Schraudolph等(1992)针对二进制编码优化精度差的缺点,提出了一种类似于对解空间进行尺度变换的参数动态编码策略,较好地提高了GA的精度,但不适于非线性较强的多极小优化问题.Androulakis等(1991)采用实数编码提出了一种扩展遗传搜索算法,把搜索方向作为独立的变量来处理以解决有约束的优化问题.Poths等(1994)为克服算法早熟收敛的缺点,提出了类似于并行实现思想的基于变迁和人工选择的遗传算法.Grefenstette(1981)全面研究了GA并行化实现的结构问题,并给出了多种结构形式,主要有同步主-仆方法(synchronous master-slave),亚同步主-仆方法(semi-synchronous master-slave),分布式异步并发方法(distributed asynchronous concurrent),网络方法(network).Goldberg(1989)提出了基于对象设计GA并行结构的思想.Muhlenbein等(1991)并行遗传算法求解高维多极小函数的全局最小解,从而提供了GA求解高度复杂化优化问题的有力实例.

     在函数优化方面,Goldberg(1989)引入分享(sharing)思想将解空间分成若干子空间,然后在子空间中产生子群体成员分别进行优化,以求得整个问题的解,避免算法只收敛到时某个局部解;DeJong(1975)提出聚集(crowding)的思想,根据群成员中的相似性来部分替换群体中的个体成员,从而将一些个体成员分别聚集于各个群集中,然后在各个群集中分别求解问题的局部解以实现与分享思想相同的目标.然而,这些方法的应用还有一定的限度,对于解是随机分布的情况就不易奏效.由此,孟庆春等(1995)提出门限变换思想,在选择个体成员进入下一代时,引入门限变换函数将某些优良成员周围的成员传到下一代以达到除劣增优的目的,从而避免搜索的盲目性.至于有约束优化问题的求解,目前的处理方法主要有:(1)把问题的约束在”染色体”的表示形式中体现出来,并设计专门的遗传算子,使”染色体”所表示的解在GA运行过程中始终保持可行性.这种方法最直接,但适用领域有限,算子的设计也较困难.(2)采用惩罚的方法来处理约束越界问题.但到目前为止,采用GA求解高维,多约束,多目标的优化问题仍是一个没有很好解决的课题,它的进展将会推动GA在许多工程领域的应用.

zhezhe

请问这一、两年遗传算法的最新研究成果有哪些呢？

yanzi621

:loveliness:不错，我决定要做一下实验一下

似水年华

学到不少知识

frogfish

原帖由 zhezhe 于 2007-10-4 20:41 发表

                               
登录/注册后可看大图

请问这一、两年遗传算法的最新研究成果有哪些呢？

你可以看看《遗传算法的进展及其在电子对抗中的应用》一文

作者总结了八个方面
(1)初始种群的产生
(2)选择算子的改进
(3)交叉算子和变异算子的改进
(4)适应度函数的改进
(5)动态调整子代个体
(6)采用小生境策略的遗传算法
(7)并行遗传算法
(8)混合遗传算法

泡泡

遗传算法是个万能的分析工具 我有个遗传算法的软件

frogfish

原帖由 泡泡 于 2007-12-10 23:50 发表

                               
登录/注册后可看大图

遗传算法是个万能的分析工具 我有个遗传算法的软件

虽然说遗传算法是一个不错的算法，不过楼上说的有点过

dongn0905

:victory:

yusky

shi de

uksseu

同意:@)

tjf741

我刚开始看遗传算法，有点傻傻的摸不着头，我做参数辨识的，就是系统辨识的一种。请问楼主：遗传算法的适用条件是什么？楼上把这算法都抬高到万能的高度了？！
还有对于停止条件而言，是不是因具体问题而议，对于求最大最小的问题，截止条件当然比较好确定，但对于如x(t)''+A*B*C*x(t)'+C*C*x(t)=0 等等类似的方程，仅已知x(t)而要确定A,B,C的值，这样如何确定呢？有通用的截止条件么

frogfish

遗传算法的优点：
1. 可以处理非光滑甚至是离散的问题,与问题领域无关,且处理速度相对较快
2. 群体搜索，具有潜在的并行性，可以进行多个个体的同时比较
3. 不需要目标函数的导数，搜索使用评价函数启发，可以通过适应度函数调节搜索方向，过程简单
4. 概率转移准则，使用概率机制进行迭代，具有随机性
5. 可扩展性强，容易与其他算法结合

遗传算法的缺点：
1. 未利用网络的反馈信息,搜索速度比较慢
2. 对初始种群的选择依赖性较强
3. 适应度函数和最优解之间没有必然联系
4. 局部搜索能力较差

frogfish

最简单的停止条件有二种：
1. 完成了预先给定的进化代数则停止
2. 种群中的最优个体在连续若干代没有改进或平均适应度在连续若干代基本没有改进时停止

flyfatfox

那么，遗传算法和进化策略有什么联系和区别？