具有混沌局部搜索策略的粒子群优化算法研究

摘要

如何改进粒子群优化(Particleswarmoptimization，PSO)算法，并将其用于解决现实世界的各类优化问题已成为当前的研究热点。在众多的改进方法中，一种重要的形式就是混沌PSO算法。本文对混沌PSO算法进行了定义和分类，分析了各类混沌PSO算法的特点，指出了混沌局部搜索的PSO算法是各类混沌PSO算法中最为有效的一种方法。目前，研究者们虽然提出了很多形式的混沌局部搜索算法，但是这些算法都有一个共同的特点，即每次混沌搜索时，被指定的搜索解向量的每一维都会改变。当指定的搜索解向量维数较多时，这种每维改变的方式很难实现精细搜索，为此提出了一种单维的混沌局部搜索算法。基于单维混沌局部搜索算法、PSO算法以及其它一些策略，提出了4种混合算法以解决不同类型的优化问题，具体如下:
　　1、提出了一种单维混沌局部搜索和多样性维持策略的混沌PSO算法用于解决无约束的单目标连续函数优化问题，其中采用单维的混沌局部搜索算法以增强PSO算法的局部搜索能力，采用混沌序列替换PSO算法的某些参数以增强PSO算法的全局搜索能力。同时，当混合算法陷入早熟收敛时，采用多样度维持策略改进PSO算法的多样性。提出的算法与其它三种混沌PSO算法分别对10维和30维的8个经典测试函数进行了50次求解，仿真实验结果表明了提出的算法在两种情况下所获最优解的平均误差精度和标准差均好于其它三种算法。
　　2、提出了一种混沌全局搜索和局部搜索相结合的PSO算法用于解决整数规划问题（属于约束的单目标离散函数优化问题）和混合整数规划问题（属于约束的同时包含离散变量和连续变量的单目标函数优化问题），其中混沌全局搜索算法用于增强PSO算法的全局搜索能力，混沌局部搜索算法用于增强PSO算法的局部搜索能力，这种混沌局部搜索算法与其它学者提出混沌局部搜索算法最本质的区别在于:前者能同时执行多维和单维的混沌局部搜索，后者只能执行多维的混沌局部搜索。14个整数和混合整数问题求解结果表明:提出的算法对整数规划问题能获得100％的成功率，而对混合整数规划问题不能获得100％的成功率。
　　3、考虑到提出的混沌全局搜索和局部搜索相结合的PSO算法解决混合整数规划问题时不能获得100％的成功率，提出一种融合差分进化、混沌局部搜索和PSO的混合算法用于解决一类混合整数规划问题，即可靠性冗余分配问题，其中引入差分进化算法以间接增强PSO算法的全局搜索能力，混沌局部搜索算法也是采用多维和单维结合的形式。实验比较了新算法与其它6种改进的元启发式算法对4个典型系统的可靠性冗余分配问题的求解情况，结果表明了新算法比其它6种算法中最好的算法能获得更好的或同样的系统可靠性。此外，针对已有的算法性能评价指标MPI的不足，提出了一个新的性能指标SR，SR对新算法与其它6种算法的评价结果表明了新算法是所有算法中最好的一种算法。
　　4、提出了一种基于混沌局部搜索的多目标PSO算法用于解决无约束的多目标连续函数优化问题，其中采用个体档案文件和全局档案文件分别保存个体非支配解和全局非支配解，且当个体或全局档案文件超过最大容量时为使非支配解均匀分布在解空间，采用基于相邻个体间距离之和最小删除法处理多余的非支配解。同时，为找到更多或更为接近的Pareto最优解，每代采用混沌局部搜索算法对所有粒子产生的支配解（相对于全局档案文件中非支配解）和全局档案文件中的所有非支配解进行搜索。实验对提出的算法与其它2种多目标PSO算法在解决9个基本的多目标函数优化问题时进行了比较，结果表明:在最终代距和间距性能指标的评价下，提出的算法在每个问题上都好于其它两种算法。

目录

声明

摘要

主要缩略语目录

1 绪论

1．1 研究背景与意义

1．2 混沌的定义及特点

1．3 PSO算法的基本原理

1．4 混沌PSO算法的定义

1．5 混沌PSO算法的分类

1．6 混沌PSO算法的特点

1．7 混沌PSO算法的应用

1．8 论文主要内容与组织结构

1．8．1 研究内容及创新点

1．8．2 论文组织结构

1．9 小结

2 单维混沌局部搜索和多样性维持策略的混沌PSO算法

2．1 引言

2．2 单目标函数优化问题的概念

2．3 混沌映射

2．4 求解单目标函数优化问题的三种混沌PSO算法

2．5 单维混沌局部搜索和多样性维持策略的混沌PSO算法(DMCPSO)

2．5．1 单维混沌局部搜索算法

2．5．2 多样性维持策略

2．5．3 DMGPSO算法描述

2．5．4 DMCPSO算法时间复杂度分析

2．6 仿真实验及结果分析

2．6．1 单目标测试函数

2．6．2 10维和30维实验结果

2．6．3 实验结果分析

2．7 小结

3 混沌全局搜索和局部搜索相结合的PSO算法

3．1 引言

3．2 整数规划问题及混合整数规划问题的概念

3．3 求解混合整数非线性规划问题的方法

3．3．1 非元启发式凸混合整数非线性规划问题求解方法

3．3．2 非元启发式非凸混合整数非线性规划问题求解方法

3．3．3 元启发式混合整数非线性规划问题求解方法

3．4 元启发式算法解决IP或MIP问题的约束条件处理方法

3．4．1 罚函数方法

3．4．2 专用表示方法及算子

3．4．3 修复算法

3．4．4 目标函数和约束条件分开处理的方法

3．4．5 混合方法

3．5 混沌搜索方法的特点

3．6 混沌全局搜索和局部搜索相结合的PSO算法(CLSPSO)

3．6．1 混沌全局搜索算法

3．6．2 单维和多维结合的混沌局部搜索算法

3．6．3 约束条件的处理及种群初始化方法

3．6．4 CLSPSO算法描述

3．6．5 CLSPSO算法的时间复杂度分析

3．7 仿真实验及结果分析

3．7．1 整数及混合整数测试问题

3．7．2 同类算法的比较及分析

3．7．3 异类算法的比较及分析

3．8 小结

4 一种融合差分进化、混沌局部搜索和PSO的混合算法

4．1 引言

4．2 可靠性冗余分配问题的概念

4．3 求解可靠性冗余分配问题的几种元启发式算法

4．4 差分进化算法

4．5 差分进化和粒子群优化算法相结合的混合算法

4．5．1 基于协作型的DEPSO算法

4．5．2 基于嵌入型的DEPSO算法

4．5．3 基于帮助型的DEPSO算法

4．5．4 基于协作型和嵌入型的DEPSO算法

4．6 融合DE、混沌局部搜索和PSO的混合算法(CDEPSO)

4．6．1 DE与PSO的结合方式

4．6．2 单维和多维结合的混沌局部搜索算法

4．6．3 约束条件的处理及种群初始化方法

4．6．4 CDEPSO算法描述

4．6．5 CDEPSO算法的时间复杂度分析

4．7 仿真实验及结果分析

4．7．1 四个典型系统问题

4．7．2 实验结果

4．7．3 结果分析及SR性能指标的提出

4．8 小结

5 基于混沌局部搜索的多目标PSO算法

5．1 引言

5．2 多目标优化问题的概念

5．3 多目标粒子群算法的研究现状

5．3．1 归并方法

5．3．2 字典序方法

5．3．3 子种群方法

5．3．4 基于Pareto方法

5．3．5 混合方法

5．3．6 其它方法

5．4 多目标进化算法的性能评价指标

5．5 多目标混沌局部搜索的PSO算法(MOCPSO)

5．5．1 档案文件

5．5．2 档案文件超过最大容量时的处理方法

5．5．3 个体最优位置和全局最优位置的选择

5．5．4 混沌局部搜索算法

5．5．5 MOCPSO算法描述

5．5．6 MOCPSO算法的时间复杂度分析

5．6 仿真实验及结果分析

5．6．1 多目标函数测试问题

5．6．2 实验结果

5．6．3 结果分析

5．7 小结

6 总结与展望

参考文献

攻读学位期间主要的研究成果目录

致谢