演化计算模型及其在优化问题中应用研究

《演化计算模型及其在优化问题中应用研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、东南大学博士学位论文演化计算模型及其在优化问题中的应用研究姓名：蔚承建申请学位级别：博士专业：信号与信息处理指导教师：何振亚20020301摘要演化计算是用计算机模拟大自然的演化过程求解复杂问题的一类并行计算模型，是信息科学技术的国际自i沿热点课题，已成为信息技术未来智能化的基础。信息技术I{J大量问题在数学上表现为困难的优化河题。本文通过对经典演化算法和新一代演化模型的分析，提出了3种新的演化模型并给出了5种NP困难问题或NP完全问题的新解法。论文所做的研究工作如下：1．嵌入集群方向的快速演化规划：最初的演化规划工作在有限自动机上，后来开始使用浮点编码并依赖变

2、异算子搜索空间。姚新和刘勇提出了快速演化规划。本文在对快速演化规划分析的基础上，利用我们1998世界计算智能大会特邀论文发表的改进的粒予群优化思想提出了嵌入集群方向的快速演化规划，获得了一种更加有效的演化搜索过程。嵌入集群方向的快速演化规划的特征在于对演化搜索引入了社会认知结构。这不仅反映了生命的进化且在某种程度上反映了其文化过程。测试问题的计算表明嵌入集群方向的快速演化规划是目前演化规划的最佳模型之一。2．带性能约束的布局优化问题演化规划求解：航天器舱、组合机床、机器人待布物的靠局设计是总体设计方案的关键，它们的求解可以变换为一个转动圆桌平衡摆盘问题的求解。该

3、问题是在占典的砧局优化问题基础上附加平衡性能约束的相局优化问题。属NP．困难问题。本文使用嵌入集群方向的快速演化规划获得了该闯题简单面又有效的求解新方法。3_集值人口增量基因学习算法：概率建模的演化计算是一种新一代演化模型，它通过对搜索空间建立概率模型指引搜索过程。人口增量学习算法是一种最简单的概率建模的演化模型，它的解的表达使用固定长度的二元字符串，每个基因位只能取一个品质值。这是对自然演化系统的过强简化。在对人口增量学习算法分析的基础上，本文通过对其概率选择引入轮盘赌方法提出了集值人口增量基因学习算法。集值人口增量基因学习算法反映了生物的基因多效性。进一步，

4、对概率分布引入熵概念获得了系统可演化性的简单判别方法。4．并行多机调度问题的集值人口增量基因学习求解：并行多机调度问题是车间调度问题的一种．已经成为计算机集成制造系统研究的重要内容。该闽题已被证明属于NP完全问题。通过建立基因位和基因值与工件和机器的对应关系，本文使用集值入口增量基因学习算法简单而有效地给出了新解法。5．旅行商问题的集值人口增量基因学习求解：旅行商问题是一种典型的组合优化问题，有着广泛的应用领域，已经证明旅行商问题的求解是NP完全的。通过建立基因位和基因值与城市和其它城市的连接关系，本文使用集值人口增量基因学习算法给出了旅行商问题的新的求解方法，

5、计算了13个旅行商问题，其中10个问题是1996国际演化计算年会演化优化竞赛题目，包括对称和非对称的旅行商问题。计算结果表明．本文提出的方法可与旅行商问题求解的国际先进水平干¨比，是一种快速的高质量的旅行商问题求解方法。6．自组织鲁棒生长计算模型：自组织生长计算同样是演化计算发展的新方向，它在举型到表型的映射不是直接译码，而是有一个生长过程。R．Tateson通过对果蝇刚毛自组织生跃机理的分析，提出了自组织生长计算模型。然而，这种模型山于其确定性的选择方法易于收敛到局部最优点。因此本文用随机竞争选择方法替换了其中的确定性选择方法，得到了一种自组织鲁棒生长模型。它

6、是一种更好的臼组织生长计算模型。7．1J．JitJ’‘播调度问题的鲁棒(4-K计算：：11星广播调度是一利·约束满意问题，本质．i：难NP完全的。本文应J丑自组纵鲁棒生长计算模型自然而简单地给出了该问题新的求解方法。对不同大小问题的计算测试表明该方法能快速一致地产生极好的结果。8．信道分配问题的自组织初始化暂态混沌神经网络求解：移动通信信道分配是一种寻找最小冲突的约束满意问题，己证明属NP完全问题。本文用自组织鲁棒生长和暂态混沌神经网络相结合给出了该问题新的求解方法。自组织鲁棒生长用于限制搜索空问并给出初步解，暂态混沌神经网络用于寻找最小冲突。该成果获国际IEE

7、EAPCCAS’2000最佳论文奖。关键词：快速演化规划，集群方向，带性能约束的粕局问题，集值人口增量基因学习，熵，，i：仃多机调度问题，旅行商问题，鲁棒生长模型，卫星广播调度问题，暂态混沌神经嘲络，信道分配问题。IIABSTRACTEvolutionarycomputationiSaparallelproblemsolver,whichUSeSideasandgetsinspirationsfromnaturaIevolutionaryprocedures．tthasbeen盟activeresearchfieldofinformationscienceand

8、technologyov