第七章 动态进化计算综述.pdfVIP

动态进化算法研究综述1 王洪峰，汪定伟 东北大学信息与工程学院系统工程研究所，沈阳（110004 ） E-mail ：hfwang@ 摘 要：现实世界中的问题是动态的，目前关于进化算法的研究大多还主要局限于静态优化 问题，然而很多对于这类时变的优化问题通常并不是要求EA 发现极值点，而是需要EA 能 够尽可能紧密地跟踪极值点在有哪些信誉好的足球投注网站空间内的运行轨迹。本论文综述了在文献中出现的使EA 适用于动态优化问题的各种方法。 关键词：动态环境，进化算法，遗传算法，多样性 1 前言 现实世界中的许多优化问题都是时变的，它们会因为目标函数、环境参数或者约束条件 的变化而随时产生变化。例如在生产调度问题中，新的工件可能会随时到达，机器可能会发 生故障或者减慢速度，原材料的质量也可能发生变化等等。这就需要算法能够持续的适应非 静态环境中解的变化。 [1] 将进化算法应用于动态环境的研究可以追溯到 1966 年 ，但是直到上世纪80 年代中期 才成为众多学者的研究热点 [2] ，近几年来许多国际会议（比如GECCO2002、WCCI2002 以 及CEC2003 等等）上都有进化算法在动态环境中应用方面的论文发表，特别是在CEC2004 上为动态进化优化方法开辟了相关的专题会议。 传统的进化算法的目标是使种群逐渐收敛，最终获得一个满意解，这样就会使种群失去 多样性，而种群的多样性恰恰是有效地探索整个可行空间的必要条件。因此传统的进化算法 当其进化后期会失去对环境变化的适应能力，这是进化算法在动态环境中所面临的主要挑 战。近些年来，许多学者使用了各种方法来解决这个问题，这些方法大体上可以分成下面几 类： EA 按照正常方式进化，一旦探测到环境中发生变化，立即采用增加种群多样性的 策略，推动种群向新的极值点移动。 EA 在进化过程中始终避免种群收敛，这是因为一个发散的种群能够更容易适应环 境中的变化。 EA 中引入某种记忆策略，使之能够回想起以前进化过程中的有用信息，这类方法 特别适用于周期变化的环境。 采用多种群策略，将整个种群分成若干个小种群，其中一部分用于追踪当前的极值 点，另一部分继续有哪些信誉好的足球投注网站整个空间，以发现新的极值点。 其他的相关方法，采用一些其他的方法来保证EA 适用于各种动态环境。 下文将详细介绍这些方法。 2 环境变化后增加种群多样性 当环境中的某个变化被探测到之后，EA 采用简单的重启当然是处理动态的一种最直接 的方式。然而如果环境的变化相对较小，那么新的极值点与旧的极值点之间可能具有一定的 1本课题得到国家自然科学基金重点项目），创新群体项目），国家支撑计划项目 （2006BAH02A09 ）的资助。 - 1 - 联系，因此通常在EA 重启时将旧种群（变化前）中的某些信息通过某种方式传递给新种群 （变化后），例如将旧种群的某些个体传递给新的初始种群作为其中的一部分。 实践[3]证明传递某些个体后EA 与采用完全简单重启策略的EA 相比能够更好的适应环 境中的变化。然而采用这种重启策略也会给 EA 带来一定的挑战，它需要 EA 能够在 exploitation （尽可能地传递信息）和exploration （引入新信息）之间达到一种平衡：如果过 多的旧信息被保留，那么由于种群中个体的相似性会使种群过早的收敛；反之，如果过多的 信息被丢弃，那么会花费更多的时间去寻找新的极值点。 [4]检验了传递到新初始种群中的个体数量 Louis 和Xu 在一个Open Shop Sche