动态进化计算综述

《动态进化计算综述》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、http://www.paper.edu.cn1动态进化算法研究综述王洪峰，汪定伟东北大学信息与工程学院系统工程研究所，沈阳（110004）E-mail：hfwang@mail.neu.edu.cn摘要：现实世界中的问题是动态的，目前关于进化算法的研究大多还主要局限于静态优化问题，然而很多对于这类时变的优化问题通常并不是要求EA发现极值点，而是需要EA能够尽可能紧密地跟踪极值点在搜索空间内的运行轨迹。本论文综述了在文献中出现的使EA适用于动态优化问题的各种方法。关键词：动态环境，进化算法，遗传算法，多样性1前言现实世界中的许

2、多优化问题都是时变的，它们会因为目标函数、环境参数或者约束条件的变化而随时产生变化。例如在生产调度问题中，新的工件可能会随时到达，机器可能会发生故障或者减慢速度，原材料的质量也可能发生变化等等。这就需要算法能够持续的适应非静态环境中解的变化。[1]将进化算法应用于动态环境的研究可以追溯到1966年，但是直到上世纪80年代中期[2]才成为众多学者的研究热点，近几年来许多国际会议（比如GECCO2002、WCCI2002以及CEC2003等等）上都有进化算法在动态环境中应用方面的论文发表，特别是在CEC2004上为动态进化优化方

3、法开辟了相关的专题会议。传统的进化算法的目标是使种群逐渐收敛，最终获得一个满意解，这样就会使种群失去多样性，而种群的多样性恰恰是有效地探索整个可行空间的必要条件。因此传统的进化算法当其进化后期会失去对环境变化的适应能力，这是进化算法在动态环境中所面临的主要挑战。近些年来，许多学者使用了各种方法来解决这个问题，这些方法大体上可以分成下面几类：òEA按照正常方式进化，一旦探测到环境中发生变化，立即采用增加种群多样性的策略，推动种群向新的极值点移动。òEA在进化过程中始终避免种群收敛，这是因为一个发散的种群能够更容易适应环境中的变

4、化。òEA中引入某种记忆策略，使之能够回想起以前进化过程中的有用信息，这类方法特别适用于周期变化的环境。ò采用多种群策略，将整个种群分成若干个小种群，其中一部分用于追踪当前的极值点，另一部分继续搜索整个空间，以发现新的极值点。ò其他的相关方法，采用一些其他的方法来保证EA适用于各种动态环境。下文将详细介绍这些方法。2环境变化后增加种群多样性当环境中的某个变化被探测到之后，EA采用简单的重启当然是处理动态的一种最直接的方式。然而如果环境的变化相对较小，那么新的极值点与旧的极值点之间可能具有一定的1本课题得到国家自然科学基金重点

5、项目（70431003），创新群体项目（60521003），国家支撑计划项目（2006BAH02A09）的资助。-1-http://www.paper.edu.cn联系，因此通常在EA重启时将旧种群（变化前）中的某些信息通过某种方式传递给新种群（变化后），例如将旧种群的某些个体传递给新的初始种群作为其中的一部分。[3]实践证明传递某些个体后EA与采用完全简单重启策略的EA相比能够更好的适应环境中的变化。然而采用这种重启策略也会给EA带来一定的挑战，它需要EA能够在exploitation（尽可能地传递信息）和explorat

6、ion（引入新信息）之间达到一种平衡：如果过多的旧信息被保留，那么由于种群中个体的相似性会使种群过早的收敛；反之，如果过多的信息被丢弃，那么会花费更多的时间去寻找新的极值点。[4]Louis和Xu在一个OpenShopSchedule问题中检验了传递到新初始种群中的个体数量与质量对整个算法性能影响。他们发现：当环境变化时，将旧种群中的部分个体传递给新的初始种群会使算法在早期遗传中得到显著的改进；然而若传递的数量过多，则算法失败了。[5]而且Louis还发现当问题变化较大时，传递适值较小的个体会得到更好的效果。[6]此外，Ca

7、rtwright和Tuson证明了当EA重启时，旧种群中的部分个体应该保存下来，[7]因为它们也能够在新的环境中被重用。Reeves和Karatza等人提出了利用前一阶段EA搜索到的解而得到的新初始种群会使重新开始的EA更快的搜索到新问题的最优解，但是他们[8]并没有给出算法的具体实现过程。Bierwirth等人建议校正种群中所有个体，使之满足新问题的要求，并且把它们作为求解新问题的GA的初始种群。他们将这种思想应用于一个JSSP问题：新工件会随机到达，并且当新工件到达后，所有未完成的工件和新工件就重新组成一个新的调度问题，

8、这时新工件会被随机的插入旧个体编码的某个位置。在与随机初始化的方[9]法相比较时会发现，虽然解的质量稍有不同，但是速度却大为提高。Lin，Goodman和[10]Punch对于JSSP问题也提出了一种直接校正的方法，他们利用Giffler-Thompson算法把新[11]工件加入到旧调度中