第一章

绪论
优化问题的分类与描述 Benchmark问题介绍 优化算法及其分类 邻域函数与局部搜索 计算复杂性与NP、NP-hard、NP-Complete
by 谢广明 ， 2005~2006学年度第一学期
1
1.1 优化问题分类
严格数学化以后的狭义优化问题 函数优化问题 组合优化问题 混合型优化问题
i 1
29
Generalized Rastrigin’s Function： f 9 ( X )
[ x
i 1
30
2 i
10cos(2xi ) 10] ， xi 5.12
Ackley’s Function： f10 ( X ) 20 exp 0.2

30 2 x / 30 exp cos(2xi ) / 30 20 e ， xi 32 i i 1 i 1

by 谢广明 ， 2005~2006学年度第一学期
2
函数优化问题 1

本质
– 求解自变量为连续变量的函数的最小值

定义
n 令 S 为 R 上的有界子集，f : S R 为 维实值 S 域上全局最小化就是 函数，所谓函数 f 在 寻求点 X S 使得 f ( X ) 在S 域上全局最 小，即 X S : f ( X ) f ( X ) 。
30
f (X )
2 sin 2 x12 x2 0.5 2 2 [1 0.001 ( x12 x 2 )]
0.5 ， xi 100
Step Function： f 6 ( X )
(x
i 1
30
i
0.5) 2 ， xi 100
by 谢广明 ， 2005~2006学年度第一学期
定义 令 {s1 , s 2 ,...,s n } 为所有状态构成的解 si 对应的目标函数 空间，C ( si ) 为状态 值， 要求寻找最 优解 s* ， 使得 s i , C ( s*) min C ( s i ) 。 组合爆炸！

by 谢广明 ， 2005~2006学年度第一学期
(1) 把问题的约束在状态的表达形式中体现出来，并设计专门的 算子，使状态所表示的解在搜索过程中始终保持可行性。这种方 法最直接，但适用领域有限，算子的设计也较困难。 (2) 在编码过程中不考虑约束，而在搜索过程中通过检验解的可 行性来决定解的弃用。这种方法一般只适用于简单的约束问题。 (3) 采用惩罚的方法出来约束越界问题。这种方法比较通用，适 当选择惩罚函数的形式可得到较好的结果。譬如罚函数法可将受
by 谢广明 ， 2005~2006学年度第一学期
11
max f ( x, y ) [
3 2 2 2 2 ] ( x y ) , x, y [ 5.12,5.12] 2 2 (0.05 x y )
by 谢广明 ， 2005~2006学年度第一学期
12
组合优化Benchmark问题
min f ( X ) h 2 ( X ) [min{ 0, g ( X )}] 2 约束问题转化为无约束问题 X S .
， 因此
函数优化通常以无约束问题的研究为主。
by 谢广明 ， 2005~2006学年度第一学期
5
组合优化问题

本质
– 求解自变量为离散变量的函数的最小值
30 城市 TSP 问题 (d*=423.741 by D B Fogel) 41 94； 37 84； 54 67； 25 62； 7 64；2 99； 68 58； 71 44； 54 62； 83 69；64 60；18 54；22 60；83 46；91 38；25 38；24 42；58 69； 71 71； 74 78； 87 76； 18 40； 13 40； 82 7； 62 32； 58 35；45 21； 41 26； 44 35； 4 50
9
f (X )
2 sin 2 x12 x 2 0 .5 2 2 [1 0.001( x12 x 2 )]
0.5 ， xi 100 , x2 0
by 谢广明 ， 2005~2006学年度第一学期
10
2 sin 2 x12 x 2 0 .5 0 .5) ， x i 100 max f ( X ) ( 2 2 2 [1 0 .001( x1 x 2 )]
组合问题
旅行商问题(TSP) 加工调度问题 背包问题 装箱问题 着色问题 聚类问题
实际问题
生产线、交通、网络路由、VLSI等
by 谢广明 ， 2005~2006学年度第一学期
13
TSP(Traveling Salesman Problem)
给定n 个城市和两两城市间的距离，要求确定一条 经过各城市当且仅当一次的最短路线。 其图论描述 A V 为：给定图G ＝(V ， A) ，其中 为顶点集， 为各顶 点相互连接组成的边集，已知各顶点间的连接距 离，要求确定一条长度最短的 Hamilton 回路，即 遍历所有顶点当且仅当一次的最短回路。
– – – – – – – – – 单极小 非凸 非线性 多极小 高维 强振荡 噪声 不可微 平台
by 谢广明 ， 2005~2006学年度第一学期
8
Generalized Rosenbrock’s Function：
f 5 ( X ) [100 ( xi 1 xi2 ) 2 (1 xi ) 2 ] ， xi 30
n
min
min
min
by 谢广明 ， 2005~2006学年度第一学期
3
函数优化问题 2

有约束和无约束
– 是否存在一些限制自变量取值的约束条件，一 般以不等式和等式形式出现 – g(x)<0, h(x)=0
by 谢广明 ， 2005~2006学年度第一学期
4
函数优化问题 3

有约束转化为无约束的处理6来自1.2 Benchmark问题

含义
– 基准研究对象 – 很多科学研究和实际事物都有

意义
– 具有一些典型特征，便于验证有关方法 – 便于比较不同方法的性能优略

产生
– 最先研究者提出 – 后来者加以改进
7
by 谢广明 ， 2005~2006学年度第一学期
函数优化Benchmark问题

典型特点