进化策略的变异算子与仿真平台研究

摘要

论文研究进化策略中变异算子的改进。现有的变异算子都使用全基因变异，本文提出单基因变异，通过对变异成功概率、局部收敛速度、全局收敛性能、变异步长控制、计算开销、多种群技术系统地分析比较两种变异方式的优劣，建立基于递减型变异步长单基因变异算子的单种群和多种群进化策略，最后论述进化算法仿真试验平台的构建及其应用。 对进化策略及其变异算子的研究源于变异算子在进化计算中起主导作用的认识。通过对简单遗传算法的改进试验，对交叉算子作用机理的分析，证明了变异算子对交叉算子的局部和全局搜索功能的可替代性，变异算子在算法中起主导作用。 借鉴生物进化理论和基因突变思想的进化策略，其变异算子使用所有基因同时变异的全基因变异方式，本文提出了一次只随机选择其中一个基因发生变异的单基因变异方式。理论分析和仿真试验证明，对于多维优化问题，当变异步长较大时，单基因变异的成功概率大于全基因变异的成功概率，全基因变异存在进化停顿现象，而且计算开销较大，对于高维优化问题尤其突出。 理论分析证明使用Gauss分布的单基因变异算子时，保持成功概率为0.445可以获得最优的局部收敛速度，并提出相应的递减型变异步长控制策略。为了直观分析、比较进化算子的性能，提出了横向仿真技术，并用于单基因变异和全基因变异的局部收敛速度的比较研究。试验证明虽然当变异步长合适时，全基因变异算子的局部收敛速度大于单基因变异，但全基因变异算子要求变异步长较小并且范围很小，而单基因变异算子可以在变异步长较大、且在一个较大的范围内获得良好的局部收敛速度，说明单基因变异算子对变异步长具有良好的鲁棒性。通过两个反例说明Gauss分布递减型步长控制单基因变异算子全局搜索能力的不足，提出了Gauss分布递减型步长单基因变异与均匀分布变异相结合的改进进化策略(μ+λ+κ)-ES，通过一组100维典型测试函数的仿真试验，说明了(μ+λ+κ)-ES良好的局部和全局搜索能力、较少的计算开销。 为了增强(μ+λ+κ)-ES的全局搜索能力、在解多模态优化问题时获得多个全局最优解和局部最优解，在(μ+λ+κ)-ES基础上提出了多种群进化策略m×(μ+λ+κ)-ES。在基于排挤和(/或)共享的多种群技术中，共享半径是一个难以确定而又非常关键的参数，本文提出了山谷探索法，避免了共享半径的确定。建立了在给定精度下以一定的可信度判断子种群是否收敛的判据，使子种群的收敛性判别有了实用的定量依据。以一组典型多模态优化问题测试函数仿真验证了m×(μ+λ+κ)-ES准确求解全部极值点的能力。 进化算法仿真试验研究与应用平台是进化计算重要工具，本文论述了基于面向对象程序设计技术和VisualC++设计仿真计算平台的基本思路、基本结构，构建了一个通用的仿真计算平台，通过两个实例——复杂机电系统速度控制参数的优化和足球机器人的最优控制说明了平台和算法的应用。 最后给出了未来的研究方向。

目录

文摘

英文文摘

原创性声明及关于学位论文使用授权说明

第一章 绪论

1.1进化算法概述

1.2进化算法基本框架

1.3进化策略研究综述

1.3.1 ES的演变

1.3.2基本ES描述

1.3.3 ES的改进研究

1.3.4 ES理论研究进展

1.3.5应用

1.3.6现状与趋势

1.4论文主要研究内容和结构

第二章变异算子的主导作用

2.1基本遗传算法

2.2一种强化引导型的遗传算法

2.2.1 IEGA基本原理

2.2.2算法描述

2.2.3仿真计算

2.3 IEGA的进一步改进

2.4交叉算子作用机理分析

2.4.1一维时交叉算子的作用

2.4.2高维时交叉算子的作用

2.4.3交叉算子的可替代性

2.4.4无交叉算子的IEGA-2与进化策略

2.5小结

第三章单基因变异进化策略

3.1进化策略中的变异算子

3.1.1变异算子设计的一般原则

3.1.2实数搜索空间的变异算子

3.2单基因变异与全基因变异

3.2.1成功变异的概率分析

3.2.2局部搜索能力仿真分析

3.3关于变异方式的进一步探讨

3.3.1计算开销比较

3.3.2 H.Bremermann的早期研究

3.3.3进化策略的变异思想

3.3.4有关仿真计算结果的评价

3.4小结

第四章单基因变异ES的步长控制

4.1变异步长控制概述

4.2变异步长与局部搜索性能的关系

4.2.1理论分析

4.2.2横向仿真分析

4.3全局收敛性分析

4.3.1概率意义下的收敛性

4.3.2反例1变异步长减小导致早熟收敛

4.3.3反例2单基因变异导致早熟收敛

4.4均匀变异算子的引入

4.5(μ+λ+κ)-ES

4.5.1算法描述

4.5.2仿真计算

4.6小结

第五章基于(μ+λ+κ)-ES的多种群技术

5.1引言

5.2多种群技术综述

5.2.1多种群GA

5.2.2多种群ES

5.2.3多种群技术中有待解决的问题

5.3多种群进化策略m×(μ+λ+κ)-ES

5.3.1算法结构

5.3.2算法参数的设置

5.3.3子种群的消亡与再生

5.3.4算法实现

5.3.5仿真计算

5.4小结

第六章进化算法仿真平台的研究

6.1平台现状

6.2算法平台的构建

6.2.1基本要求

6.2.2程序设计

6.3应用1——复杂机电传动控制系统参数的优化组合

6.3.1系统结构与数学模型

6.3.2适应值函数

6.3.3计算过程与结果

6.4应用2——足球机器人的最优控制

6.4.1机器人运动方程

6.4.2机器人轮速的动力学方程

6.4.3最优控制的描述与实现

6.6小结

第七章总结、创新与展望

参考文献

附录1作者在攻博期间发表的论文

附录2作者在攻博期间参加的科研项目

致 谢