基于智能算法的多目标组合优化研究

VIP免费

3.0 陈辉 2024-11-18 16 4 1.75MB 62 页 15积分

侵权投诉

摘要

多目标优化问题是现实世界中普遍存在的问题，而这些问题有很多都是目前

尚缺乏一般求解方法的复杂难题，因此，如何可靠的找到 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 引言

最优化是人们在工程技术、科学研究和经济管理等诸多领域中经常遇到的问

题，长期以来一直为人们所关注。传统的数学规划理论成功地解决了部分优化问

题，但仍有一些问题比如多目标优化问题缺乏高效实用的解决办法。我们知道现

实世界中的绝大多数优化问题都涉及到多个目标的同时优化，而且这些目标并不

是独立存在的，它们往往是藕合在一起相互竞争的，每个目标具有不同的物理意

义和量纲，它们的竞争性和复杂性使得对其优化变得困难。尤其当前随着科学技

术的迅猛发展，现代系统的规模增大，约束条件增多，非线性严重，使得传统的

数学优化方法显得无能为力。

20 世纪 80 年代以来，随着人工智能、仿生学的兴起，人们从不同的角度出发

对生物系统及其行为特征进行了模拟，设计出了一系列通用性较强的智能优化方

法和模式，并逐步应用到多目标优化问题中。

智能优化算法[1]是以生物进化的观点认识和模拟智能。按照这一点，智能是在

生物的遗传、变异、生长以及外部环境的自然选择中产生的。在用进废退、优胜

劣汰的过程中，适应度高的（头脑）结构被保留下来，智能水平也随之提高。其

方法主要有人工神经网络、进化算法、模拟退火算法、蚂蚁算法以及粒子群算法

等。这些算法具有以下几个共同要素：自适应的结构、随机产生的或指定的初始

状态、适应度的评测函数、修改结构的操作、终止计算的条件、控制过程的参数

等，并具有自学习、自组织、自适应的特征和简单、通用、鲁棒性强、适于并行

处理的优点，已在并行搜索、联想记忆、模式识别、知识自动获取等方面得到了

广泛应用。

§ 1.2 相关概念

§ 1.2.1 组合优化问题

从数学模型上看，优化问题[1]可分为连续优化问题和离散优化问题。其中，连

续优化问题又可分为线性规划和非线性规划；而组合优化是一类典型的离散优化

问题，它指在离散的、有限的数学结构上，寻找一个满足给定约束条件的离散变

量的组合，使其目标函数达到最优。具体的组合优化问题由三部分组成：

① 实例集合

；

基于智能算法的多目标组合优化研究

② 对于每个实例

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

、

、…、

Jn，所需加工时间分别为 T1

、

、…、

Tn，均可由 m台机

器M1

、

、…、

Mm中的任何一台完成，且每台机器一次仅可完成一项任务。现

要找最优任务安排，使得完成所有任务的时间最少。

该问题当 m不超过 2时，有简单有效的法则可进行求解。但一般情形下的问

题仍是一个难以处理的 NP-难题。国外一些研究机构和高校曾多次悬赏征求一些

来自生产企业部门的复杂排序问题，由此可见其实际应用的重要性。

第一章绪论

二次分配问题

二次分配问题（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]）。若新点的目标函数值更好，则令该

点为当前点；否则选择并测试当前点的其它邻近点。若无进一步改进的可能，则

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

15 积分 4人已下载

立即下载 VIP免费下载

摘要：

摘要多目标优化问题是现实世界中普遍存在的问题，而这些问题有很多都是目前尚缺乏一般求解方法的复杂难题，因此，如何可靠的找到Pareto最优解、提高算法的搜索效率、有效的维持群体多样性，是当前研究的一个重点和难点。本文的工作旨在研究具有实际可操作性的智能算法，用于解决若干多目标组合优化问题。借鉴物理学、生物学思想发展起来的智能优化算法——模拟退火算法(SimulatedAnnealing)和蚂蚁算法(AntAlgorithm)在近几年得到了很大的发展。这两种算法具有较强的全局搜索能力，且对初始值的依赖性小，尤其蚂蚁算法本身还具有内在的并行性优点，在多目标优化领域的应用潜力很大。本文分别针对以上两种...

展开>> 收起<<

基于智能算法的多目标组合优化研究.pdf

共62页,预览7页

还剩页未读，继续阅读

基于智能算法的多目标组合优化研究

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

推荐作者

热门标签

举报选择: