文档介绍：数理分析方法第七讲
组合最优化问题
魏丽******@sfruc.
中国人民大学财政金融学院
主要内容
•组合最优化问题概论
•现代最优化计算方法
–禁忌搜索(tabu search)
–模拟退火(simulated annealing)
–遗传算法(ic algorithms)
–人工神经网络(works)
–拉格朗日松弛算法(Lagrange slack arithmetic)
组合最优化问题概论
• binatorial optimization)
–是通过对数学方法的研究去寻找离散事件的最优编排、分
组、次序或筛选等
–组合最优化问题的数学模型
)x(fmin )x(fmin
0g(x) . ≥ 0g(x)
D x ∈ D
其中,f(x)为目标函数,g(x)为约束函数,x为决策变量,D
表示有限个点组成的集合
组合最优化问题概论
• binatorial optimization)
–一个组合最优化问题可用三参数(D,F,f)表示,其中D表示
决策变量的定义域,F表示可行解区域= ∈≥}0)x(g,Dx|x{F
F中的任何一个元素称为该问题的可行解,f表示目标函数。
满足* = ∈}Fx|x)(f{min)x(f 的可行解x* 称为该问题的最
优解
–组合最优化的特点是:可行解集合为有限点集
–有可行解一定有最优解
组合最优化问题概论
•组合最优化问题
例1.(最优投资问题)设一个人的财富为b,现有n只价
格为 i = L )n,2,1i(a 、预期收益分别为 i = L )n,2,1i(c 的
股票,如何选择投资策略使得该人投资收益最大?
解:用数学模型表示为:
n
xcmax ∑ xcmax ii (1)
=1i
n
,bxa . ∑ ii ≤,bxa (2)
=1i
(3)n ,2,1i },1,0{ xi },1,0{ =∈,2,1i L (3)n
组合最优化问题概论
•组合最优化问题
例2.(旅行商问题)一个商人欲到n个城市推销商品,
每两个城市i和j之间的距离为dij ,如何选择一条道路
使得商人每个城市走一遍后回到起点且所走路经最短。
注:旅行商问题还可以细分为对称和非对称距离两大类
问题。当= jiij ,dd ∀ j,i 时,称为对称距离旅行商问
题,否则称为非对称距离旅行商问题。
组合最优化问题概论
•组合最优化问题
例2.(旅行商问题)解:用数学模型表示为:
xdmax ∑ xdmax ijij (4)
≠ ji
n
1,2,i ,1x . ∑ ij ,1x == 1,2,i L n (5)
=1j
n
1,2,j ,1x ∑ ij ,1x == 1,2,j L n (6)
=1i
(7) }n 1,2,{is 2,-ns2 ,1-sx ∑ ij ,1-sx 2,-ns2 =⊂≤≤≤ 1,2,{is L }n (7)
∈sji,
x i },1,0{ =∈,2,1i L n (8)
禁忌搜索算法(tabu search)
•局部领域搜索算法的推广,是人工智能在组合优化算
法中的一个成功应用
•Glover在1986年首次提出这一概念,进而形成一套完
整算法,该算法的特点是采用了禁忌技术
•禁忌就是禁止重复前面的工作
•为了回避局部领域搜索陷入局部最优的主要不足,禁
忌搜索算法用一个禁忌表记录下已经到达过的局部最
优点,在下一次搜索中,利用禁忌表中的信息不再或
有选择地搜索这些点,以此来跳出局部最优点。
禁忌搜索算法(tabu search)
•应用实例:
–图节点着色问题
–车间作业调度问题
•参考文献:
– Glover F. Tabu search: part I. ORSA Journal puting,
1989, 1, 190~206
– Glover F. Tabu search: part II. ORSA Journal puting,
1990, 2, 4~32
模拟退火算法(simulated annealing)
•是一个全局最优算法
•最早由Metropolis在1953年提出,Kirkpatrick在1983年成功地
应用在组合最优化问题中
•退火是一种物理过程,一种金属物体在加热至一定的温度后,
它的所有分子在状态空间D中自由运动,随着温度的下降,这
些分子逐渐停留在不同的状态,在温度最低时,分子重新以一
定的结构排列
•组合优化问题同金属物