二次分配问题算法研究

VIP免费

3.0 侯斌 2024-11-19 8 4 1.46MB 125 页 15积分

侵权投诉

摘要

二次分配问题是一种易于描述却难于求解的典型组合优化问题，已被归入

NP-hard 问题。二次分配问题不仅以不同的形式存在于工厂布局，作业车间调度，

挡板布线等实际生活领域，而且综合了一大类组合优化问题的典型特征，它是一

个既有广泛的实际应用背景，又有重要的理论研究价值的优化问题。

随着二次分配问题实例规模的增长，其解空间呈现组合爆炸特征，因而通常

在多项式时间内无法求得其最优解。过去几十年，由于二次分配问题的高度求解

复杂性，已激发了人们对优化技术的研究。因此，研究二次分配问题的求解方法

对优化技术和二次分配问题自身的发展有着重要意义。

本文着重研究了以线性化技术为基础的二次分配问题的求解方法，具体包括：

(1) 详细讨论了基于匈牙利算法的二次分配问题的最优目标函数值的下界求解技

术；(2) 对原有二次分配问题的下界求解方法和二次分配问题线性化模型进行深入

研究的基础上，提出三种基于线性化技术的二次分配问题求解新方法；(3) 对输入

矩阵(流矩阵和距离矩阵)中存在零元素的二次分配问题的求解进行了探讨，为该

类特殊二次分配问题的求解提供了新的解决手段；(4) 提出使用半拉格朗日算法

求解二次分配问题的方法，这为有效求解二次分配问题提供了一种新的解决方案。

本文对所提出的二次分配问题求解方法不仅给出了其数学证明，从理论的角

度说明了各种方法的正确性，而且选用了二次分配基准问题库(QAPLIB)中的部分

实例进行了计算，将计算结果与原有方法进行比较，从实验的角度说明了本文提

出的方法对二次分配问题的求解具有较优的性能。

关键词：二次分配问题线性化下界匈牙利算法半拉格朗日松弛

ABSTRACT

Quadratic assignment problem (QAP) is one of the classical NP-hard combinatorial

optimization problems, which is simple to be described but difficult to be solved

optimally. QAP has not only been applied in various fields, including factory layout, job

shop scheduling, backboard wiring, etc., but also synthesizes a large group of typical

characteristics of the problems in combinatorial optimization. QAP is an optimization

problem with a diversity of applications and important significance of theoretical study.

With the enlargement of the scale of QAP instances, the solution space makes the

characteristic of combinatorial explosion, which therefore can not be solved in

polynomial time. Over the years, owing to its astounding computational complexity, the

QAP has drawn the researcher’s attention worldwide in improving the combinatorial

optimization algorithms and methods. Furthermore, the study on the solution methods

for the QAP plays an important role in the development of itself and the optimization

techniques.

This paper focuses on the solution methods for the QAP based on the linearization

techniques. To be more specific, which cover: (1) Several dual ascent procedures for the

lower bound of the QAP based on Hungarian algorithm are discussed in detail; (2)

Three new solution methods are proposed based on making an intensive study on the

available QAP linearization as well as the QAP lower bound methods; (3) The

resolution of the special kind of QAP in which input matrices there are many zero

elements is further studied, a new solving method, furthermore, is proposed for it; (4)

The semi-Lagrangian relaxation of the QAP is proposed, which is a new effective

solution methods for the QAP.

From the theoretical point of view, the results of mathematical derivation in this

paper show that the proposed solution methods for the QAP are feasible. From the

experimental point of view, a few of selected QAP instances in the QAPLIB are

implemented with the new proposed solution methods and some current available

methods respectively, and the investigated experimental results show that the new

proposed solution methods are more important and effective in solving the QAP.

Key Words: Quadratic assignment problem, Linearization, Lower bounds,

Hungarian algorithm, Semi-Lagrangian relaxation

中文摘要

ABSTRACT

第一章绪论.................................................................................................................1

§1.1 研究背景.............................................................................................................1

§1.2 本文主要研究内容.............................................................................................1

第二章二次分配问题.....................................................................................................5

§2.1 组合优化问题.....................................................................................................5

§2.2 算法及其分类.....................................................................................................6

§2.3 计算复杂性与 NP 完全问题 ............................................................................. 7

§2.4 二次分配问题...................................................................................................10

§ 2.4.1 QAP 模型.....................................................................................................10

§ 2.4.2 QAP 的计算复杂性.....................................................................................13

§ 2.4.3 QAP 的线性化.............................................................................................17

§ 2.4.4 QAP 的多面体描述(QAP Polytopes)........................................................ 22

§ 2.4.5 QAP 的下界计算方法.................................................................................24

§ 2.4.6 扩展 QAP 问题...........................................................................................28

§ 2.4.7 QAP 的求解方法.........................................................................................31

§ 2.4.8 QAP 的渐进特性(The Asymptotic Behavior of The QAP) ........................ 37

§2.5 小结...................................................................................................................38

第三章基于匈牙利算法的 QAP 对偶上升求解法.......................................................39

§3.1 概述...................................................................................................................39

§3.2 二次分配问题线性化模型的结构特征...........................................................39

§3.3 基于匈牙利算法的 QAP 下界对偶上升求解方法.........................................43

§ 3.3.1 匈牙利算法..................................................................................................43

§ 3.3.2 几种基于匈牙利算法的 QAP 对偶上升求解法........................................44

§3.4 算例分析...........................................................................................................53

§3.5 小结...................................................................................................................58

第四章几种求解二次分配问题的新方法...................................................................59

§4.1 概述...................................................................................................................59

§4.2 基于 Gilmore-Lawler 下界的 QAP 线性化模型 .............................................59

§ 4.2.1 Gilmore-Lawler 下界的等价形式 ...............................................................59

§ 4.2.2 QAP 问题的 Gilmore-Lawler 线性化模型 .................................................61

§ 4.2.3 算例分析......................................................................................................63

§4.3 Adams-Johnson 线性化模型的缩减与改进 ....................................................67

§ 4.3.1 Adams-Johnson 线性化模型的有效缩减 ................................................... 67

§ 4.3.2 算例分析......................................................................................................70

§4.4 一种 QAP 线性化新方法.................................................................................77

§ 4.4.1 一种 QAP 线性化新模型............................................................................77

§ 4.4.2 算例分析......................................................................................................80

§4.5 小结...................................................................................................................80

第五章稀疏二次分配问题及其求解...........................................................................83

§5.1 概述...................................................................................................................83

§5.2 稀疏二次分配问题的线性化...........................................................................83

§5.3 算例分析...........................................................................................................91

§5.4 小结...................................................................................................................96

第六章二次分配问题的半拉格朗日求解法...............................................................97

§6.1 概述...................................................................................................................97

§6.2 拉格朗日松弛方法...........................................................................................97

§6.3 半拉格朗日松弛方法(Semi-Lagrangian Relaxation).................................... 98

§6.4 求解 QAP 问题的半拉格朗日算法...............................................................102

§ 6.4.1 QAP 的半拉格朗日松弛及其对偶问题...................................................102

§ 6.4.2 QAP 的半拉格朗日松弛的核问题...........................................................104

§6.4.3 求解 QAP 的半拉格朗日松弛对偶问题的算法.......................................106

§6.5 算例分析.........................................................................................................106

§6.6 小结.................................................................................................................109

第七章结论与展望.....................................................................................................111

§7.1 全文总结.........................................................................................................111

§7.2 进一步的工作.................................................................................................112

参考文献.......................................................................................................................113

在读期间公开发表的论文和承担科研项目及取得成果...........................................125

致谢.............................................................................................................................127

第一章绪论

§1.1 研究背景

二次分配问题(quadratic assignment problem，

QAP)[1]是最经典，最具有挑战性

的组合优化问题之一[2]。自 1957 年Koopmans 和Beckmann[1]首次将 QAP 问题作

为组合优化问题提出之后，其已被广泛应用于诸多领域，许多问题象集成电路布

线[3,4]、工厂位置布局[5]、打字机键盘设计、作业调度问题[6-7]等等[2, 8-9]，都可形式

化为二次分配问题。此外，QAP 问题也被应用于统计数据分析[10]、考古数据排序[11]

和接力赛跑队的排序[12]等。另外，一些 NP-hard 组合优化问题，如旅行商问题(the

traveling salesman problem)，三角剖分问题(triangulation problem)和最大团问题

(the max clique problem)等也可以转化为二次分配问题[2, 8-9, 13]。基于 QAP 问题理论

和实际的重要性，过去几十年已激发了许多学者对其理论，应用和优化技术的研

究。

1976 年Sahni 和Gonzales[14]证明了 QAP 不仅属于 NP-hard 问题而且不存在



近似度的多项式时间近似算法(





)[15-16]。QAP 是很难求解的最优化问题，其主

要原因是所谓的“组合爆炸”现象，求解时间随问题规模呈指数增长[17]。一般而

言，当问题规模

20n

时，很难在有效的计算时间内利用经典算法找到其最优解，

如分支定界法，割平面法等[2]。为了实际可行地解决 QAP 问题，人们退而求其次，

许多启发式算法不断提出并被应用到 QAP 的求解，如：模拟退火算法[18-22]，遗传

算法[23-29]，蚂蚁算法[30-35]，粒子群算法[36-40]，禁忌搜索算法[41-46]和贪婪随机自适应

搜索算法[47-49]等。然而，这些启发式算法不能保证找到的解一定是最优解，他们

仅可以在人们可接受的时间内给出较优解。

由于 QAP 问题高度的计算复杂性和具有代表性的求解难度，许多新的算法，

理论和思想在被提出后也常常使用 QAP 作为测试其自身性能的标准，求解 QAP

问题已经成为优化技术成功的主要体现之一。

§1.2 本文主要研究内容

二次分配问题目标函数中的二次项在一定程度上增加了问题的求解复杂度，

通过一定方法将其二次项线性化，得到与原问题等价的(混合)整数规划模型，不

二次分配问题算法研究

仅会使问题的求解复杂度得到一定降低，能够应用既有的(混合)整数规划求解方

法求解 QAP 问题；而且当问题规模较大，较难求解时，可通过求解该(混合)整数

规划模型的线性松弛，求得原 QAP 问题最优解的下界值。

本文以二次分配问题的线性化技术为基础，主要研究了二次分配问题的求解

方法。本文从几种不同的角度探索并提出了多种二次分配问题的求解新方法，并

分别从理论和实验两方面讨论了各种方法的性能，为二次分配问题的求解提供了

有效的基本解决方案和手段。其整体框架内容如图 1-1 所示。

图1-1 论文整体框架内容

各章主要内容简述如下：

第一章简单介绍了本文的研究背景和本文的主要工作；

第二章对组合优化问题和二次分配问题进行了综述，介绍了目前二次分配问

题各个方面的研究现状；

研究现状

提出问题

总结与展望

第三章基于匈牙利算法

的QAP 对偶上升求解法

第二章二次分配问题

第一章绪论

第四章几种求解二次

分配问题的新方法

第五章稀疏二次分配

问题及其求解

第六章二次分配问题的半

拉格朗日求解法

第七章结论与展望

第一章绪论

第三章分析了二次分配问题线性化模型的结构特征，在此基础上，详细讨论

了几种基于匈牙利算法的二次分配问题的下界求解技术；

第四章以现有的二次分配问题线性化方法及其模型为基础，得到三种在一定

程度上改进的 QAP 线性化新模型；

第五章以二次分配问题线性化模型为基础，提出了对一类特殊二次分配问题

——稀疏二次分配问题的求解新方法；

第六章根据二次分配问题线性化模型的实际特征及半拉格朗日算法的性能，

将半拉格朗日算法用于二次分配问题的求解，并从实验的角度验证了该方法求解

二次分配问题的正确性和有效性；

第七章对本论文的研究结果进行了总结，并对后续工作的研究方向进行了展

望。

第二章二次分配问题

§2.1 组合优化问题

最优化一般是指在给定的约束条件(constraint)下，找出一个或一组决策变量

(decision variable)的值，使得被称为目标函数(objective function)的表达愿望尺度

的函数达到最大值或最小值[50]。这种问题可采用下述数学模型：

)(min xf

，

x

(2.1)

其中，

xxx ),,( 1

为

维决策向量，可行域



是问题变量

的可取值集合，目

标函数

)(xf

是定义在包含



的适当集合上的实值函数。一般来说，可行域



用与

变量

相关的等式及不等式表示，则最优化问题也可表示为：

)(min xf

(2.2)

lixgi,,1 0)( 

(2.3)

mjxhj,,1 0)( 

(2.4)

其中，

)(xgi

和

)(xhj

为约束函数。

满足约束条件

x

的

称为满足优化问题(2.1)的可行解(feasible solution)。

满足

)()( *xfxf 

(

 x

)的可行解



称为优化问题(2.1)的全局最优解

(global optimal solution)，对应的目标函数值

)( *

称为最优值。在包含可行解





的适当邻域

)(x



里，当

)()( xfxf 



(

)(xx 



)成立时，称

x

为问题(2.1)

的局部最优解(local optimal solution)，对应的目标函数值

)(xf 

称为局部最优值。

根据变量的类型，最优化问题可分为连续变量问题和离散变量问题两大类。

前者是变量取一定区间内的连续实数，称为连续最优化问题 (continuous

optimization problem)；后者是变量取一定区间内的整数或离散数，称为离散最优

化问题(discrete optimization problem)，因其多用组合性质来表示，也称为组合优

化问题(combination optimization problem)。

组合优化是运筹学的一个重要分支，至今尚未有公认的统一定义，下述是两

种较常见的定义[51-52]：

定义 2.1 组合最优化是在给定有限集的所有具备某些特性的子集中，将某种

目标找出一个最优子集的数学规划。

定义 2.2 一个组合优化问题



要么是一个极小化问题，要么是一个极大化问

题，它由下述三部分组成：

二次分配问题算法研究

（1）实例的一个集合



；

（2）对每一个实例



DI 

，有一个由

的可行解组成的有限集合

)(IS



；

（3）有一个目标函数



，对每一个实例



DI 

和每一个可行解

)(ISx





，

赋予一个有理数

),( xIf

，称为解

的目标值。

如果



是极小化问题(或极大化问题)，则实例

的最优解为这样一个可行解：



Dx 

，使得对所有

)(IDx





，都有

),(),( *xIfxIf





(或

),(),( *xIfxIf





)。

在组合优化问题里，需要从一个有限集或可数无限集里寻找一个对象——典

型地说是一个整数、一个集合、一个排列或一个图。组合优化问题往往涉及排序、

分类、筛选等问题。典型的组合优化问题有二次分配问题(QAP)、旅行商问题

(TSP)、加工调度问题(scheduling problem)、背包问题(knapsack problem)、图着

色问题(graph coloring problem)、聚类问题(cluster problem)等。这些问题具有很强

的工程背景，数学描述虽然简单，而最优化求解却很困难，其主要原因为所谓“组

合爆炸”[53]。例如，聚类问题的可能划分方式有

!/ kk n

个，加工调度问题中的

Job-shop 的可能排列方式有

n)!(

个，基于置换排列描述的

城市 TSP 问题有

种

可行排列，即便对无方向性和循环性的平面问题仍有

2/)!1( n

。

上述组合优化问题的状态数量随问题的规模呈超指数增长，因此解决这些问

题的关键在于寻求有效的优化算法，也正是这些问题的代表性和复杂性激起了人

们对组合优化理论与算法的研究。

§2.2 算法及其分类

所谓算法[52]是指一步步求解问题的通用程序，是解决问题的程序步骤的一个

清晰描述。如果存在一个算法，它对问题



的每一个实例

，在有限步后，一定可

得到该实例的关于



的提问的答案，那么称该算法解问题



。

作为一个算法，应具有以下五个重要的特征[51]：

(1) 有穷性：一个算法必须保证执行有限步骤之后结束。

(2) 确切性：算法的每一步骤必须有确切的定义。

(3) 输入：一个算法有零个或多个输入，以刻画运算对象的初始情况。

(4) 输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果，

没有输出的算法是毫无意义的。

(5) 可行性：算法原则上能够精确地运行。

就优化机制与行为而分，目前工程中常用的优化算法主要可分为[53]：经典算

法、构造型算法、改进型算法、基于系统动态演化的算法和混合型算法：

第二章二次分配问题

(1) 经典算法包括线性规划、动态规划、整数规划和分支定界等运筹学中的

传统算法，其算法计算量一般很大，只适于求解小规模问题实例，在工程中往往

不适用。

(2) 构造型算法是用构造的方法快速建立问题的解，通常算法的优化质量差，

难以满足工程需要。例如，调度问题中的典型构造型方法有：Johnson 法、Palmer

法、Gupta 法等。

(3) 改进型算法，或称邻域搜索算法。从任意解出发，对其邻域的不断搜索和

对当前解的替换来实现优化。根据搜索行为，其又可分为局部搜索法和指导性搜

索法。

局部搜索法即以局部优化策略在当前解的邻域中贪婪搜索，如只接受优于

当前解的状态作为下一当前解的爬山法；接受当前解邻域中的最好解作为

下一当前解的最陡下降法等。

指导性搜索法即利用一些指导规则来指导整个解空间中优良解的探索，如

模拟退火(SA)、禁忌搜索(TS)、遗传算法(GA)等。

(4) 基于系统动态演化的方法是将优化过程转化为系统动态的演化过程，基于

系统动态的演化来实现优化，如神经网络和混沌搜索等。

(5) 混合型算法就是将上述各算法从结构或操作上混合而产生的各类算法。

§2.3 计算复杂性与 NP 完全问题

计算复杂性通常是指计算机求解问题的难易程度[51]。其度量标准：一是计算

所需的步骤数或指令条数(称为时间复杂性)，二是计算所需的存储单元数量(称为

空间复杂性)[51]。

算法对时间和空间的需要称为算法的时间复杂性和空间复杂性。算法或问题

的复杂性一般是问题规模

的函数，时间复杂性记为

)(nT

，空间复杂性记为

)(nS

。

在算法分析和设计中，沿用实用性的复杂性概念，即把求解问题的关键操作，如

加、减、乘、比较等运算指定为基本操作，算法执行基本操作的次数则定义为算

法的时间复杂性，算法执行期间占用的存储单元则定义为算法的空间复杂性[54]。

由于同一算法求解同一问题的不同实例所需要的时间一般不相同，对于每一个可

能的输入长度，该算法解此输入长度运算最慢的一种情况称为最“坏”情况，最

“坏”情况下的时间复杂性被称为最“坏”时间复杂性。如不特别说明，一般时

间复杂性均指最“坏”情况下的时间复杂性。

算法的复杂性通常用其复杂性函数

)(np

主要的阶

))(( npO

来表示。若算法

的

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

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

15 积分 4人已下载

立即下载 VIP免费下载

摘要：

摘要二次分配问题是一种易于描述却难于求解的典型组合优化问题，已被归入NP-hard问题。二次分配问题不仅以不同的形式存在于工厂布局，作业车间调度，挡板布线等实际生活领域，而且综合了一大类组合优化问题的典型特征，它是一个既有广泛的实际应用背景，又有重要的理论研究价值的优化问题。随着二次分配问题实例规模的增长，其解空间呈现组合爆炸特征，因而通常在多项式时间内无法求得其最优解。过去几十年，由于二次分配问题的高度求解复杂性，已激发了人们对优化技术的研究。因此，研究二次分配问题的求解方法对优化技术和二次分配问题自身的发展有着重要意义。本文着重研究了以线性化技术为基础的二次分配问题的求解方法，具体包括：(...

展开>> 收起<<

二次分配问题算法研究.pdf

共125页,预览10页

还剩页未读，继续阅读

二次分配问题算法研究

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

推荐作者

热门标签

举报选择: