1、关于遗传算法的一般性介绍,报告人:杨再跃报告时间:2003.1,主要内容,1 GA的起源及发展2 GA的基本思想3 GA的几个近亲4 SGA的实现方法5 GA的特点和适用范围6 需要注意的几个问题7 一些改进后的算法8 GA在控制工程中的应用,1 GA的起源及发展,1950年，图灵提出可以通过模拟进化和自然选择过程自动生成智能程序。1960s1970s，基于进化和自然选择思想的各种算法的提出和应用。1975年，Holland发表Adaptation in Nature and Artificial Systems，完整描述了GA的原理及实现步骤。1975年，De Jong提出了5个评价GA效率
2、的测试函数。1987年，Goldberg发表Genetic Algorithms in Search，Optimization and Machine Learning,详细介绍了GA在工程上的应用。,2 GA的基本思想,GA的思想本源是自然界中的“优胜劣汰”现象。各种生物在自然选择的压力下，器官和结构不断演变以适应环境，最终实现从简单到复杂、从不适应到适应的进化过程。GA中的几个术语。个体：进化的最小单元；种群：个体的集合；个体适应度：评价每个个体优劣的标量值；选择：从种群中根据适应度选取一定数量的个体组成新种群；遗传操作：包括重组和变异两种操作；重组：一对个体按某种方式结合生成一对新个体；
3、变异：单个个体随机发生变化。,2 GA的基本思想,GA是一种模拟自然选择和进化过程来求解问题的计算模型。GA求解问题的过程：随机产生一个种群，其中的个体代表问题的可行解；根据问题确定评价个体适应度的方式，并对个体赋以适应度值；根据个体适应度选择一定数量的个体参加遗传操作；被选个体通过重组或者变异操作生成新个体；新个体连同以前的个体，按照某种方式保存一部分到下一代。重复前面的步骤，直到满足终止条件，得到最佳个体，即问题的近似最优解。,3 GA的几个近亲及其特点,遗传编程（Genetic Programming），个体为一段程序。演化策略（Evolution Strategies），只有一个个体，
4、通过变异不断进化。演化规划（Evolutionary Programming），根据以前的状态估计未来的状态，个体长度不断增加。硬件演化（Evolvable Hardware），结合PLD实现硬件本身自动地改变结构以适应环境的变化。,4 SGA的实现步骤,4.1 编码4.2 种群设定4.3 适应度函数4.4 选择4.5 遗传操作4.6 个体保存方式,4.1 编码,把问题的解转换成GA可以操作的对象的过程叫做编码。编码是一种将解同个体、将解空间同染色体空间、将表现型同基因型对应起来的映射。在SGA中，一般直接用二进制数表示问题的解；或者用Gray码表示问题的解。目前在工程上使用最广泛的是浮点数直
5、接编码方式，这是因为它在概念上更靠近解空间，同时也便于使用封闭的算子。,4.2 种群设定,种群规模（即所包含的个体数目）与问题的搜索空间正相关，一般选取为20100之间的一个常数。确定种群规模后，随机初始化种群，即随机产生指定数量的可行个体。可以通过选择代沟（generation gap）确定选取多少个体参加遗传操作，代沟通常为0.70.9之间的常数。,4.3 适应度函数,适应度函数用于根据问题（目标函数）赋给个体相应的适应度值。常见的几种适应度函数类型：线性定标形式；幂乘形式；排序赋值等。其中以排序赋值使用最为广泛。,4.4 选择,从群体中根据个体适应度依概率选取一部分个体参加遗传操作的过程
6、叫做选择。选择的个体数量等于种群规模与代沟的乘积。常用的选择方法有：轮盘赌选择法，期望值法，最优个体选择法，排序选择法，部分放回随机选择法，随机均匀选择法，联赛选择法，排挤法等。,4.5 遗传操作,遗传操作是按概率执行的，它包括重组和变异两部分，可以根据实际情况选择执行两种操作或者其中的某一种操作。如何确定遗传操作一直是学术界争论的焦点，或者说由于GA针对性太强而无法给出普适性的结论。总的说来，重组操作趋向于在深度方向进行搜索，变异操作趋向于在广度方向进行搜索。,4.5 遗传操作,重组操作是指将个体两两配对，重新组合生成新个体的过程。重组操作的设计需要结合编码方式来考虑。例如针对二进制形式的编
7、码，通常是将两个体对应位相互交换而生成新个体，如001和010 011和000。习惯上称这种重组方式为交叉，交叉又可以细分为单点交叉、两点交叉和多点交叉。而对于浮点数编码，重组操作通常是将两个个体分别乘以系数后相加，如3.14和4.13 3.14 +4.13 和3.14 +4.13 ，通常1。,4.5 遗传操作,变异操作是指依概率从参加遗传操作的种群中指定一定数量的个体，然后随机改变这些个体的某些位的过程。变异操作通常也需要结合编码方式来考虑。针对二进制编码，可通过将某位取非来实现变异，如0111；而对于浮点数编码，则可以通过增加或者减去指定幅度（步长）以内的一个随机数来实现变异，如3.14
8、3.14+0.01，其中0.01为步长， 1 1，且服从某种概率分布 。,4.6 个体保留,为了维持种群规模恒定（也有少数GA种群规模是变化的），只能新个体和老个体中间的一部分保留到下一代，因此需要按照某种适当的方式实现个体保留过程。由于个体保留同选择过程在操作基本相同，因此可以沿用选择操作。,5 GA的特点和适用范围,GA是一种迭代自适应概率性搜索算法。它无需了解问题的数学模型，不依赖于梯度信息。因此，它适合解决传统搜索方法不能很好处理的问题，例如系统具有严重的非线性，或者难以建模分析等；反之，则GA并不适宜。GA是一种实验性较强的算法，并没有完备的数学理论作为基础，因此GA的设计更针对具体
9、问题，而没有一种普适性的设计方案。一般说来，在目前的计算能力下，GA运算相对时间较长，难以进行在线求解。,6 需要注意的几个问题,编码应该遵循以下原则：基因型与表现型应是一一映射，并且应该确保二者的变化是一致的。这是为了避免在编码译码过程中出现误解。二进制数编码存在“海明悬崖”问题，例如：两个解为7、8，对应的4位二进制数为0111、1000，即表现型与基因型之间变化并不一致。评价选择机制优劣应遵循Baker提出的三条准则：偏差、延伸度和复杂度。偏差是指个体实际被选择的概率与期望概率之差的绝对值；延伸度是指个体在演化中可能经历的代数；复杂度是指选择算法的复杂程度。那么，优越的选择机制应该是：零
10、偏差，小延伸度，低复杂度。随机均匀选择较为理想。,6 需要注意的几个问题,GA的搜索过程是一个动态过程，在不同阶段对搜索的方向和力度有不同的要求，可以使用动态参数提高搜索效率；但另一方面，这势必会增加算法的复杂度。,7 一些改进后的算法,1.7.1 多种群GA1.7.2 自适应GA1.7.3 GA的二级参数控制1.7.4 各种混合GA,7.1 多种群GA,将种群划分成多个子种群，每个种群独立进化，然后按照一定的方式交换子种群中的个体（遗传信息）；周而复始直到算法终止。该模型来源于这样的思想：近亲结合产生的后代常常有缺陷，而混血儿通常更为优秀。该模型比较适合在并行系统上运行，可以求解运算量较大的
11、问题。同时也比较适合解决多峰问题，有助于逃离局部最优解，求得全局最优解。,7.2 自适应GA,为了迎合GA搜索过程中的内在动态特性，因此根据搜索状态自动修正各个参数值。GA在各个阶段对搜索的方向和力度有不同的要求。总的说来，在初始阶段应在较广的范围内进行较粗的搜索，而在搜索后期，则应该集中于某一较小区域进行较细致的搜索。主要使用自适应参数的是选择和变异操作。,7.3 GA的二级参数控制,基本思想是用一个GA去优化另一个GA的各个参数。由于GA的各个参数相互关联，而且参数对搜索进程的影响并不十分明朗，即：GA的参数设置本身就是一个复杂的、人们不太了解的问题，而求解这类问题正是GA所擅长的。显然，
12、这种参数设计方式会很耗时间。同时，这种方法并没有从根本上解决GA参数设计难题。,7.4 各种混合GA,将GA同其它算法结合起来，扬长避短，以寻求更高的搜索效率。针对性较强，不具有普遍意义。,8 遗传算法在控制工程中的应用,8.1 控制器设计8.2 系统辨识8.3 其他,8.1 控制器设计,基于GA的控制器设计主要是指控制器的参数优化（也有利用GA设计控制器的结构）。对于复杂的控制系统，通常难以在控制器参数与控制性能指标之间建立准确的数学联系，这也就为GA提供了施展本领的舞台，即：以某些性能指标为目标函数（单目标或多目标），利用GA搜索最佳的参数组合。但是由于GA求解时间较长，限制了这种方法的在线应用。,8.2 系统辨识,在系统辨识中，GA可以用于选择模型结构，也可以用于估计模型参数，或者同时选择结构、估计参数。对于参数估计，GA主要用于参数非线性的系统，且技术相当成熟，目前已能实现在线参数估计。利用GA选择模型结构仍然处于进一步研究中。,8.3 其他,GA也被用于故障诊断，系统可靠性分析，鲁棒稳定性分析以及机器人控制等。,THE ENDThanks,
