基于智能算法的多目标组合优化研究
VIP免费
摘 要
多目标优化问题是现实世界中普遍存在的问题，而这些问题有很多都是目前
尚缺乏一般求解方法的复杂难题，因此，如何可靠的找到 Pareto 最优解、提高算
法的搜索效率、有效的维持群体多样性，是当前研究的一个重点和难点。本文的
工作旨在研究具有实际可操作性的智能算法，用于解决若干多目标组合优化问题。
借鉴物理学、生物学思想发展起来的智能优化算法——模拟退火算法
(Simulated Annealing) 和蚂蚁算法(Ant Algorithm) 在近几年得到了很大的发展。这
两种算法具有较强的全局搜索能力，且对初始值的依赖性小，尤其蚂蚁算法本身
还具有内在的并行性优点，在多目标优化领域的应用潜力很大。本文分别针对以
上两种优化算法各自的特点，有机的结合了多目标优化的 Pareto 最优解概念，分
别提出求解多目标优化问题的两种算法——基于 Pareto 概念的模拟退火算法和基
于Pareto 概念的蚂蚁算法。这两种算法在一定程度上弥补了传统多目标优化方法
的一些缺点。
大量数值实验表明，这两种算法不仅操作简单、速度快、鲁棒性强，而且由
于其利用了多目标优化的 Pareto 最优解的概念作为寻优的判定条件，因而能够获
得更多的且分布广泛的 Pareto 最优解，给决策者提供了更多的选择。
本文的具体内容包括：
第一章 概述组合优化问题的 NP 难解性和基本求解办法，介绍本文的研究内
容。
第二章 主要介绍了多目标优化算法的基本原理及其研究现状。
第三章 详细介绍了基于 Pareto 概念的模拟退火算法和蚂蚁算法的思想，给出
了实现步骤。
第四章 运用上述两个算法求解了若干多目标组合优化问题，包括多目标旅行
商问题，多目标瓶颈旅行商问题，多目标最短路问题和多目标最小生成树问题，
并作了大量的数值试验，效果较好，得到了一些有意义的结论。
第五章 对全文的总结，给出了今后研究工作的方向。
关键词：多目标 组合优化 模拟退火 蚂蚁算法
ABSTRACT
Multi-objective optimization problems widely exist in the real world. However,
lots of these problems are very complicated and difficult to solve, and lack common
efficient algorithms. Thus, the key point for current research is to find reliable Pareto
optimal solutions, to increase algorithm search efficiency and to maintain population
diversity. This dissertation mainly focuses on developing effective and efficient
intelligent algorithm to solve types of multi-objective combinatorial optimization
problems.
In recent years, Simulated Annealing (SA) and Ant Algorithm (AA) are well
developed. The fundamental ideas come from some concepts and methods in the area of
physics and biology. The two algorithms have the advantage of having a global
searching mechanism and are independent from initial value(s). Especially the ant
algorithm, which has the characteristic of parallel calculation, thus it has a great
potential to be applied successively to multi-objective optimization problems.
Combining the characters of the two algorithms into the Pareto concept of
multi-objective optimization, we proposed two algorithms which to some extent
mitigate the limitations of the classical multi-objective algorithms.
Large number of tests and comparisons show that the algorithms are not only fast,
robust and easy to use, but also can get more extensive Pareto solutions which provide
more choices for the decision-maker.
The contents of the dissertation include:
Chapter 1 contains a brief introduction to the NP-hard characteristic and the basic
solution to the combinatorial optimization problems.
Chapter 2 describes the basic principle of the multi-objective optimization
algorithms and their development.
Chapter 3 introduces the theory of the Pareto-based simulated annealing algorithm
and ant algorithm, and also provides the steps for implementation.
Chapter 4 discusses the solution to several multi-objective combinational
optimization algorithms. These problems include multi-objective TSP, multi-objective
bottleneck TSP, multi-objective shortest path problem and multi-objective minimum
spanning tree problem. By solving a large number of instances, we get meaningful
conclusions and satisfying results.
Chapter 5 gives out the summarization of this dissertation and proposition for
further research.
KEY WORDS: Multi-objective Optimization, Simulated Annealing,
Ant Algorithm
目 录
中文摘要
ABSTRACT
第一章 绪论 ...................................................................................................................1
§ 1.1 引言................................................................................................................1
§ 1.2 相关概念........................................................................................................1
§ 1.2.1 组合优化问题......................................................................................1
§ 1.2.2 组合优化问题的求解方法..................................................................3
§ 1.2.3 NP 难解问题 ....................................................................................... 4
§ 1.2.4 NP 难解问题的求解方法 ................................................................... 6
§ 1.3 本文的主要工作及方法................................................................................6
第二章 多目标优化问题的概述 ...................................................................................8
§ 2.1 多目标优化的基本概念和数学模型............................................................8
§ 2.2 多目标优化方法的发展及研究现状............................................................9
§ 2.2.1 传统的多目标优化方法....................................................................10
§ 2.2.1.1 加权和方法(Weighted Sum Method) ......................................10
§ 2.2.1.2 目标规划法(Goal Programming) ............................................ 11
§ 2.2.1.3
ε-
约束法(
ε-
Constraint Method) ...................................... 11
§ 2.2.1.4 字典排序法(Lexicographic Ordering) .................................... 12
§ 2.2.1.5 博弈论法(Game Theory) .........................................................12
§ 2.2.1.6 最小－最大法(Min-Max Approach) ....................................... 12
§ 2.2.1.7 传统算法小结..........................................................................12
§ 2.2.2 多目标进化算法................................................................................13
§ 2.2.3 模拟退火算法与多目标优化技术的结合........................................15
§ 2.2.4 群集智能方法与多目标优化技术的结合........................................16
第三章 基于 Pareto 概念的多目标优化算法 .............................................................. 18
§ 3.1 基于 Pareto 概念的模拟退火算法 ............................................................. 18
§ 3.1.1 退火算法与固体退火........................................................................18
§ 3.1.2 多目标优化与固体退火....................................................................20
§ 3.1.3 算法描述............................................................................................21
§ 3.1.4 算法执行的步骤................................................................................21
§ 3.2 基于 Pareto 概念的蚂蚁算法 ..................................................................... 22
§ 3.2.1 蚂蚁算法与蚂蚁行为........................................................................22
§ 3.2.2 多目标优化与蚂蚁系统....................................................................24
§ 3.2.3 算法描述............................................................................................24
§ 3.2.4 算法的执行步骤................................................................................26
§ 3.3 小结..............................................................................................................27
第四章 若干多目标组合优化问题的求解 .................................................................29
§ 4.1 多目标 TSP 问题.........................................................................................29
§ 4.1.1 问题描述............................................................................................29
§ 4.1.2 算法实现............................................................................................30
§ 4.1.3 计算试验............................................................................................32
§ 4.2 多目标瓶颈 TSP 问题.................................................................................36
§ 4.2.1 问题描述............................................................................................36
§ 4.2.2 计算试验............................................................................................36
§ 4.3 多目标最短路问题......................................................................................40
§ 4.3.1 问题描述............................................................................................40
§ 4.3.2 算法实现............................................................................................41
§ 4.3.3 计算试验............................................................................................42
§ 4.4 多目标最小生成树问题..............................................................................43
§ 4.4.1 问题描述............................................................................................43
§ 4.3.2 算法实现............................................................................................44
§ 4.4.3 计算试验............................................................................................45
§ 4.5 小结..............................................................................................................46
第五章 总结 .................................................................................................................48
附录 .................................................................................................................................49
参考文献 .........................................................................................................................53
在读期间公开发表的论文和承担科研项目及取得成果 .............................................59
致谢 .................................................................................................................................60
第一章 绪论
1
第一章 绪论
§ 1.1 引言
最优化是人们在工程技术、科学研究和经济管理等诸多领域中经常遇到的问
题，长期以来一直为人们所关注。传统的数学规划理论成功地解决了部分优化问
题，但仍有一些问题比如多目标优化问题缺乏高效实用的解决办法。我们知道现
实世界中的绝大多数优化问题都涉及到多个目标的同时优化，而且这些目标并不
是独立存在的，它们往往是藕合在一起相互竞争的，每个目标具有不同的物理意
义和量纲，它们的竞争性和复杂性使得对其优化变得困难。尤其当前随着科学技
术的迅猛发展，现代系统的规模增大，约束条件增多，非线性严重，使得传统的
数学优化方法显得无能为力。
20 世纪 80 年代以来，随着人工智能、仿生学的兴起，人们从不同的角度出发
对生物系统及其行为特征进行了模拟，设计出了一系列通用性较强的智能优化方
法和模式，并逐步应用到多目标优化问题中。
智能优化算法[1]是以生物进化的观点认识和模拟智能。按照这一点，智能是在
生物的遗传、变异、生长以及外部环境的自然选择中产生的。在用进废退、优胜
劣汰的过程中，适应度高的（头脑）结构被保留下来，智能水平也随之提高。其
方法主要有人工神经网络、进化算法、模拟退火算法、蚂蚁算法以及粒子群算法
等。这些算法具有以下几个共同要素：自适应的结构、随机产生的或指定的初始
状态、适应度的评测函数、修改结构的操作、终止计算的条件、控制过程的参数
等，并具有自学习、自组织、自适应的特征和简单、通用、鲁棒性强、适于并行
处理的优点，已在并行搜索、联想记忆、模式识别、知识自动获取等方面得到了
广泛应用。
§ 1.2 相关概念
§ 1.2.1 组合优化问题
从数学模型上看，优化问题[1]可分为连续优化问题和离散优化问题。其中，连
续优化问题又可分为线性规划和非线性规划；而组合优化是一类典型的离散优化
问题，它指在离散的、有限的数学结构上，寻找一个满足给定约束条件的离散变
量的组合，使其目标函数达到最优。具体的组合优化问题由三部分组成：
① 实例集合
D
；
基于智能算法的多目标组合优化研究
2
② 对于每个实例
I D
，有一个可行解集
( )U I
；
③ 对于每个可行解
( )U I
，有一个正整数
( )C
称作
的值。
对于最小化问题（最大化问题），若
*( )U I
，使得对于所有的
( )U I
，
有：
*
( ) ( )C C
（
*
( ) ( )C C
），则称
*
是问题的最优解，
*
( )C
称作问题
的最优值。
典型的组合优化问题有：
旅行商问题
旅行商问题（Travelling Salesman Problem，简记 TSP），又称货郎担问题，是
运筹学中一个著名的问题，它的提法是：有一货物推销员从城市 1出发到城市 2、
3、…、n去推销货物，最后回到城市 1，问应怎样选择一条总行程最短的路线？
（各城市间距离 dij 为已知）。该问题有着明显的实际意义，如城市交通、运输等领
域中经常碰到的车辆路径问题，就是以 TSP 为其子问题的。有趣的是，许多问题
表面上似乎与 TSP 无关，而本质上却可归结为 TSP 来求解，如：计算机线路问题、
行车路线问题、数据聚类问题、工件排序问题等。由于推销员的每条路线可以用
一个以 1开始的排列来表示，因此所有可能的路线最多有(n-1)!/2 条，这样，假如
用穷举法来解决这一问题，即使 n不太大，用目前最高速的计算机来求解也几乎
不可能。
图着色问题
图着色问题（Graph Coloring Problem，简记 GCP）要求对给定图 G找出最少
的顶点着色数，使得图中任何两个关联顶点都具有不同的颜色。
记图的最大顶点度数为Δ，则图的最少着色数以Δ＋１为上界。
这是图论中一个源远流长的经典问题，其典型的应用就是学校的课表安排问
题，至今仍在不断的研究之中。
工件排序问题
在工件排序问题（Job-shop Scheduling Problem，简记 JSP）中，有 n个相互独
立的任务 J1
、
J2
、…、
Jn，所需加工时间分别为 T1
、
T2
、…、
Tn，均可由 m台机
器M1
、
M2
、…、
Mm中的任何一台完成，且每台机器一次仅可完成一项任务。现
要找最优任务安排，使得完成所有任务的时间最少。
该问题当 m不超过 2时，有简单有效的法则可进行求解。但一般情形下的问
题仍是一个难以处理的 NP-难题。国外一些研究机构和高校曾多次悬赏征求一些
来自生产企业部门的复杂排序问题，由此可见其实际应用的重要性。
第一章 绪论
3
二次分配问题
二次分配问题（Quadratic Assignment Problem, 简记 QAP）的原始提法为：已
知有 n个位置点和 n家工厂，各位置点之间的距离矩阵设为 D = [dij] n×n，各工
厂之间的运输量矩阵设为 F = [fij] n×n，现要将这 n家工厂建造在这 n个位置点上，
使得总费用最小，其中，工厂 i建造在位置点 k且工厂 j建造在位置点 l的费用表
示为 fij dkl 。该问题由于目标函数的非线性而变得异常困难。
度约束最小树问题
度约束最小树问题（Degree-constrained Minimum Spanning Tree Problem，简记
DCMSTP）源于网络优化中的最小生成树问题。其不同点在于对生成树的各顶点
度数加上了一定的限制条件，即不得超过预先给定的数值。组合含义为从所有的
生成树中找出顶点度符合约束条件且权总数最小的生成树。该问题的求解难度随
各顶点度约束的不同而不同：当约束至少为n−1时，即为一般的最小生成树问题；
当约束为2时，即为著名的TSP问题。
§ 1.2.2 组合优化问题的求解方法
求解组合优化问题的方法也称搜索方法，可分为解析法、枚举法和随机法[1]，
如图1-1所示。
解析法
枚举法
随机法
直接法
间接法
动态规划
搜索方法
导向随机
盲目随机
模拟退火
遗传算法
蚂蚁算法
…
图1-1 搜索方法结构图
解析法在问题求解过程中主要使用目标函数的解析性质，如一阶导数、二阶
导数等，并可分为直接法与间接法。直接法（又名爬山法），是根据目标函数的
梯度来确定下一步的搜索方向，并采用迭代改进的技术。在迭代过程中，从当前
点的邻域中选出新点（故又称邻域搜索法[1]）。若新点的目标函数值更好，则令该
点为当前点；否则选择并测试当前点的其它邻近点。若无进一步改进的可能，则
摘要：
展开>>
收起<<
摘要多目标优化问题是现实世界中普遍存在的问题，而这些问题有很多都是目前尚缺乏一般求解方法的复杂难题，因此，如何可靠的找到Pareto最优解、提高算法的搜索效率、有效的维持群体多样性，是当前研究的一个重点和难点。本文的工作旨在研究具有实际可操作性的智能算法，用于解决若干多目标组合优化问题。借鉴物理学、生物学思想发展起来的智能优化算法——模拟退火算法(SimulatedAnnealing)和蚂蚁算法(AntAlgorithm)在近几年得到了很大的发展。这两种算法具有较强的全局搜索能力，且对初始值的依赖性小，尤其蚂蚁算法本身还具有内在的并行性优点，在多目标优化领域的应用潜力很大。本文分别针对以上两种...
相关推荐
-
公务员思想政治教育研究VIP免费
2024-10-15 59 -
在线社会网络中用户行为的实证分析与机制建模研究VIP免费
2025-01-09 12 -
智能优化方法对神经网络的改进及应用研究VIP免费
2025-01-09 16 -
鲜切哈密瓜保鲜技术研究VIP免费
2025-01-09 29 -
小城镇道路网级配方法及应用研究VIP免费
2025-01-09 14 -
医学信息集成测试系统的研究与实现VIP免费
2025-01-09 18 -
余热驱动氨水吸收式制冷系统的理论及实验研究VIP免费
2025-01-09 11 -
喷雾降温技术适用性及热环境研究VIP免费
2025-01-09 13 -
收缩—扩张喷嘴的气泡雾化数值模拟VIP免费
2025-01-09 24 -
支持供应链的工作流系统结构及其计划与调度的研究与应用VIP免费
2025-01-09 43
作者：陈辉
分类：高等教育资料
价格：15积分
属性：62 页
大小：1.75MB
格式：PDF
时间：2024-11-18
相关内容
-
医学信息集成测试系统的研究与实现
分类：高等教育资料
时间：2025-01-09
标签：无
格式：PDF
价格：15 积分
-
余热驱动氨水吸收式制冷系统的理论及实验研究
分类：高等教育资料
时间：2025-01-09
标签：无
格式：PDF
价格：15 积分
-
喷雾降温技术适用性及热环境研究
分类：高等教育资料
时间：2025-01-09
标签：无
格式：PDF
价格：15 积分
-
收缩—扩张喷嘴的气泡雾化数值模拟
分类：高等教育资料
时间：2025-01-09
标签：无
格式：PDF
价格：15 积分
-
支持供应链的工作流系统结构及其计划与调度的研究与应用
分类：高等教育资料
时间：2025-01-09
标签：无
格式：PDF
价格：15 积分
