学位论文 > 优秀研究生学位论文题录展示

不同编码机制下动态优化问题的进化计算方法研究及应用

作　者: 闫杨
导　师: 汪定伟
学　校: 东北大学
专　业: 系统工程
关键词: 动态环境动态优化问题编码方式智能体进化搜索差分进化计算自组织迁移算法缺陷检查
分类号: O224
类　型: 博士论文
年　份: 2010年
下　载: 313次
引　用: 0次
阅　读: 论文下载

内容摘要

现实世界中的许多复杂优化问题多为动态的,会随时间发生随机变化,例如,接连到达的工件需要被加入到原有的调度中,机器可能会发生随机故障或逐渐磨损,原材料的性能可能会随时间发生改变,生产过程中需要考虑生产限度的影响等等。由于动态优化问题(DOPs)在现实生产和生活中具有广泛的应用背景,因而,近些年来,对于动态环境中优化问题的求解已经引起了学者的广泛关注。求解此类问题最简单直接的方法是将每次环境变化都看作是一个新问题重新求解。然而变化后新问题的最优解与旧问题的最优解可能相差不多,如果每次微小的变化都需要对问题重新进行求解是非常不经济的。进化计算方法是一类模拟生物进化过程中自然选择机制和遗传信息传递规律的优化方法,在运行过程中不断累积并利用曾经获取的信息来增强其在问题求解中的能力,属于自适应、自学习的求解方法,并已经被广泛应用于求解工业和工程领域中的各种复杂优化问题。因而进化计算自然就成为解决各种动态优化和不确定优化问题的一种选择。然而经典进化计算方法随着迭代的进行,种群会逐渐收敛,失去了对环境变化的适应能力这是进化算法在动态环境中所面临的主要挑战。鉴于动态优化问题存在的普遍性以及其在实际工业生产、经济、以及信息科学领域中存在的重要性,本文遵循综述—算法研究—算法应用的思路,对于动态环境中的进化计算方法进行了系统研究,并针对适合于不同编码机制的动态优化问题进行了探讨,具体研究工作内容如下:(1)对动态环境、动态优化问题以及动态环境中进化计算方法的相关研究进行了详细综述。首先对动态环境的概念进行了介绍,详细阐述了动态优化问题的主要特征。然后对动态环境中的编码方式和主要研究问题进行了综述。最后,对几类求解动态环境的进化计算方法的起源发展进行了介绍。(2)对适合采用0-1编码的动态优化问题进行了研究,提出了一种基于多智能体的进化搜索算法(AES)。为智能体设计了竞争行为以及两种基于统计概率的学习模型,并将两种多样性策略(随机移民策略以及自适应对偶映射方法)引入AES。通过对一组动态测试函数、震荡动态背包问题以及一类利用不同映射机制生成的新型动态背包问题的仿真实验,验证了AES算法在求解采用0-1编码的动态优化问题时能够表现出较强的鲁棒性,适合于采用0-1编码的DOPs问题的求解。(3)顺序编码方式通常被用于描述组合优化领域中的动态优化问题。动态TSP问题和调度问题都属于可以采用顺序编码的动态组合优化问题。首先,本文利用基于不同对偶映射机制的方法生成了一组DTSP问题,提出了包含复合重组算子以及局域更新规则的AES算法,通过实验证明了这两种机制有助于引导算法更好的适应不断变化的环境,具有较快的收敛能力。接下来,针对交货期可变的动态调度问题,设计了基于并行技术的多种群DE-Memetic算法,通过仿真实验说明了算法的可行性,基于并行计算的方法能够更好地利用双核处理器的运行能力,进而有效减少算法的运行时间。通过这几类具有较强实际背景的动态组合优化问题的研究,能够对系统工程以及控制领域中的实际动态优化问题有一定指导意义。(4)实数编码适合于描述多维连续实数空间中的动态优化问题。能够采用实数编码的动态多峰优化问题在动态优化领域中受到了广泛的重视,本文对该问题进行了研究,由于自组织迁移算法(SOMA)的个体迁移过程中蕴含了空间穿越机制使得算法适合于求解多维问题。提出了多Leader机制,有助于算法在环境变化后更好的追踪多个峰值,同时提出模糊迁移策略来实现对Leader的更新。通过对一组移动峰函数的仿真实验说明了MSOMA算法的有效性。(5)印刷电路板缺陷检查问题的整个检验过程是一个持续不间断变化的过程,属于实时的动态系统。由于印刷电路板组件排布的搜索属于实数空间的动态多峰函数的优化问题,将用于求解动态多峰函数的多Leader自组织迁移算法用于印刷电路板视觉检查过程的优化,可以为PCB生产工业提供一种更有效的视觉检查方法,为问题的研究提供了一个新的思路。

不同编码机制下动态优化问题的进化计算方法研究及应用

内容摘要

全文目录

相似论文