基于整数编码的混沌粒子群优化算法及其应用研究

摘要

粒子群优化算法（Particle Swarm Optimization，简称PSO）是一种基于个体进化与群体协作和竞争的随机搜索算法。由于其过程简单明了、易于实现、计算效率高等特点，被公认为可以与遗传算法（Genetic Algorithm，简称GA）相媲美的高效算法，且已在众多领域被广泛应用。然而，值得关注的是，现有PSO算法在以组合优化为代表的离散问题求解上略显不足。为此，提出一种针对组合优化问题的整数编码混沌PSO算法（Integer encoded Chaos PSO，简称ICPSO），并深入研究其若干应用。主要研究工作包括： 1．系统分析PSO算法的基本原理及其典型的改进模型，在给出混沌理论与PSO算法结合的一般模式的基础上，以整数编码各粒子，以混沌序列指导全局搜索，以排列的改变描述粒子的飞行并更新粒子的位置，进而提出用于求解组合优化问题的整数混沌PSO算法（ICPSO）。 2．分析旅行商问题（Travelling Salesman Problem，简称TSP）基本模型，并基于排列组合进行问题描述，给出基于ICPSO的求解方法；并就典型的20个城市的TSP，与求解该问题的典型GA进行性能比较。结果表明，ICPSO能在较小的搜索范围内得到最优解。 3．分析标准装箱问题（Classic Bin Packing Problem，简称CBPP）基本的数学模型并给出基于排列组合的描述，设计基于ICPSO的求解方法；并就随机生成的30维CBPP问题，与求解该问题的典型GA进行性能比较。结果表明， ICPSO有更好的收敛性能和求解速度。 4．分析0-1背包问题（0-1 Knapsack Problem，简称0-1KP）基本的数学模型；针对0-1KP问题的特点，给出基于ICPSO的求解方法；并就随机生成50维0-1KP问题，与典型GA进行性能比较，显示了更好的求解性能。 总之，通过典型组合优化问题的求解方法的比较验证，ICPSO可以作为求解一般组合优化问题的有效方法。

目录

文摘

英文文摘

声明

第1章 绪论

1.1 组合优化问题简介

1.1.1 最优化问题及其求解方法

1.1.2 组合优化问题

1.2 群体智能理论

1.3 粒子群优化算法概述

1.3.1 粒子群优化算法简介

1.3.2 粒子群优化算法的研究现状

1.4 混沌理论概述

1.4.1 混沌的产生及其发展

1.4.2 混沌的定义

1.4.3 混沌的基本特性

1.4.4 混沌在优化问题中的应用

1.5 本文的主要内容

第2章 基于整数编码的混沌粒子群优化算法

2.1 基本PSO算法

2.1.1 算法原理

2.1.2 算法的数学描述

2.1.3 算法流程

2.1.4 算法分析

2.2 典型的PSO改进模型

2.2.1 引入惯性权重的PSO模型

2.2.2 引入收敛因子的PSO模型

2.2.3 离散的PSO模型

2.3 PSO与遗传算法的比较

2.3.1 遗传算法简介

2.3.2 PSO与GA的比较

2.4 基于整数编码的混沌PSO算法(ICPSO)

2.4.1 Logistic混沌序列

2.4.2 混沌与PSO结合的一般模式

2.4.3 基于整数编码的混沌PSO算法

2.5 本章小结

第3章 基于ICPSO的旅行商问题求解

3.1 旅行商问题(TSP)的数学模型

3.1.1 TSP的一般数学模型

3.1.2 基于排列组合的TSP模型

3.2 基于ICPSO的TSP求解算法设计

3.2.1 编码

3.2.2 适应度函数

3.2.3 粒子位置的更新

3.2.4 基于ICPSO的TSP求解流程

3.3 算法的仿真实验及分析

3.4 本章小结

第4章 基于ICPSO的装箱问题求解

4.1 标准装箱问题(CBPP)简介

4.1.1 CBPP的应用背景

4.1.2 CBPP的数学模型

4.1.3 基于排列组合的CBPP模型

4.2 基于ICPSO的CBPP求解算法设计

4.2.1 编码

4.2.2 适应度函数

4.2.3 基于ICPSO的CBPP求解流程

4.3 算法的仿真实验及分析

4.4 本章小结

第5章 基于ICPSO的背包问题求解

5.1 0-1 背包问题(0-1KP)的数学模型

5.2 基于ICPSO的0-1KP求解算法设计

5.2.1 编码

5.2.2 适应度函数

5.2.3 粒子位置的更新

5.2.4 基于ICPSO的0-1KP求解流程

5.3 算法的仿真实验及分析

5.4 本章小结

结论与展望

参考文献

攻读硕士学位期间发表或完成的论文

攻读硕士学位期间参与项目情况

致谢