❖ 含义 1.2 Benchmark问题 基准研究对象 很多科学研究和实际事物都有
❖ 意义
具有一些典型特征，便于验证有关方法 便于比较不同方法的性能优略
❖ 产生
最先研究者提出 后来者加以改进
by 谢广明 ， 2005~2006学年度第一学期
❖ 典型函特点数优化Benchmark问题 单极小 非凸 非线性 多极小 高维 强振荡 噪声 不可微 平台
组合优化问题
❖ 本质 ❖ 定令空义求间解，{自sC1,变(ss2i ,)量...为,为sn状}离为态散所s变i 有对量状应的函态的数构目的成标最函的小数解值
值，要求寻找最优解 s* ，使得 。 si , C (s*) min C (si )
❖ 组合爆炸！
by 谢广明 ， 2005~2006学年度第一学期
寻 求 点 X min S 使 得 f ( X min ) 在 S 小，即 X S : f ( X min ) f ( X ) 。
域上全局最
by 谢广明 ， 2005~2006学年度第一学期
❖ 有约束和无函约束数优化问题 2
是否存在一些限制自变量取值的约束条件，一 般以不等式和等式形式出现
g(x)<0, h(x)=0
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；
by 谢广明 ， 2005~2006学年度第一学期
sin 2 f (X)
x12
x
2 2
0.5
[1
0.001 ( x12
x
2 2
)] 2
0.5 ， xi
100
,
x2 0
by 谢广明 ， 2005~2006学年度第一学期
max
f
(X
)
sin 2 (
x12 x22 0.5
[1 0.001( x12 x22 )]2
by 谢广明 ， 2005~2006学年度第一学期
❖ 有约束转化函为无数约优束的化处问理题 3
(1) 把问题的约束在状态的表达形式中体现出来，并设计专门的 算子，使状态所表示的解在搜索过程中始终保持可行性。这种方
法最直接，但适用领域有限，算子的设计也较困难。
(2) 在编码过程中不考虑约束，而在搜索过程中通过检验解的可 行性来决定解的弃用。这种方法一般只适用于简单的约束问题。
1.1 优化问题分类
❖ 严格数学化以后的狭义优化问题 ❖ 函数优化问题 ❖ 组合优化问题 ❖ 混合型优化问题
by 谢广明 ， 2005~2006学年度第一学期
函数优化问题 1
❖ 本质
求解自变量为连续变量的函数的最小值
❖ 定令义S 为Rn 上的有界子集，f : S R 为 n 维实值
函数，所谓函数 f 在S 域上全局最小化就是
实际问题
生产线、交通、网络路由、VLSI等
by 谢广明 ， 2005~2006学年度第一学期
TSP(Traveling Salesman Problem)
给定 n 个城市和两两城市间的距离，要求确定一条 经过各城市当且仅当一次的最短路线。其图论描述 为：给定图G＝(V，A) ，其中V 为顶点集，A 为各顶 点相互连接组成的边集，已知各顶点间的连接距 离，要求确定一条长度最短的 Hamilton 回路，即 遍历所有顶点当且仅当一次的最短回路。
(3) 采用惩罚的方法出来约束越界问题。这种方法比较通用，适 当选择惩罚函数的形式可得到较好的结果。譬如罚函数法可将受
约
束问题转化为无约束问题
min
f ( X ) h 2 ( X ) [min{ 0, g( X )}] 2 ，因此
X S.
函数优化通常以无约束问题的研究为主。
by 谢广明 ， 2005~2006学年度第一学期
0.5) ，xi
100
by 谢广明 ， 2005~2006学年度第一学期
max
f
(x,
y)
[
(0.05
3 x2
y2
)
]2
(x2
y2
)2
,
x,
y
[5.12,5.12]
by 谢广明 ， 2005~2006学年度第一学期
组合优化Benchmark问题
组合问题
旅行商问题(TSP) 加工调度问题 背包问题 装箱问题 着色问题 聚类问题
by 谢广明 ， 2005~2006学年度第一学期
Generalized Rosenbrock’s Function：
29
f5 ( X ) [100 (xi1 xi2 )2 (1 xi )2 ] ， xi 30 i 1
30
Generalized Rastrigin’s Function： f9 ( X ) [xi2 10 cos(2xi ) 10] ， xi 5.12 i 1
41 26；44 35；4 50
by 谢广明 ， 2005~2006学年度第一学期
❖ 所谓优1化.3算法优, 其化实就算是法一种及搜其索过分程类或规则,
它基于某种原理和机制, 通过一定的途径或规 则来得到满足用户要求的问题的解. ❖ 就优化机制与行为而分, 常用的优化算法主要 可分为: 经典算法, 构造型算法, 改进型算法, 基 于系统动态演化的算法, 混合型算法等. ❖ 从其他角度分类, 如确定性算法和不确定性算 法, 局部优化算法和全局优化算法等.
by 谢广明 ， 2005~2006学年度第一学期
❖ 如线性规划、动态经规划典、算整数法规划和分枝定界等。
❖ 其算法计算复杂性大, 只适于求解小规模问题, 在 工程中往往不实用。
by 谢广明 ， 2005~2006学年度第一学期
Ackley’s
Function：
f10
(X
)
20
exp
0.2
30 i 1
xi2
/
30
exp
30 i 1
Hale Waihona Puke cos(2xi)/
30
20
e
，
xi
32
sin 2 f (X)
x12 x22 0.5
[1 0.001(x12 x22 )]2
0.5 ，xi
100
30
Step Function： f6 ( X ) (xi 0.5)2 ，xi 100 i 1