定义1.1 假设问题和解决该问题的一个算法已 经给定，若给定该问题的一个实例 I，存在多项式 函数 g(x)，使得成立，我们称该算法对实例 I 是多项式时间算法；若存在 g(x) 为多项 式函数且 对该问题任意的一个实例 I，都有 成立．则称 该算法为解决该问题的多项式时间 算法． 当不存在多项式函数 g(x) 使成立时，称相应 的算法是指数时间算法． 相比较而言，随着变量的增加，多项式函数增 长的速度比指数函数增长的速度要慢得多，因此， 我们更喜欢多项式函数 。例如，随着n的增加， nkk 的整数的增长速度远比an a 1为实 数增 长的速度慢。
其中，f(x)为目标函数， g(x)为约束函数，x为决策 变量， D表示有限个点组成的集合．
一个组合最优化问题可用三参数(D , F , f )表示， 其中D表示决策变量的定义域，F 表示可行解集合 F x xD, g(x)0，F 中的任何一个元素称为该 问题的可行解，f 表示目标函数．满足 f (x)min f (x) xF 的可行解x 称为该问题的 最优解．组合最优化的特点是可行解集合为有限 点集．
Step1的初始可行解选择可以采用随机的方法， 也可用一些经验的方法或其他算法所得到的 解．Step2中的集合S 选取可以大到是N(xbest )本 身，也可以小到只有一个元素，如用随机的方 法在N(xbest )中选一点．
例2.1 5个城市（A,B,C,D,E）的对称TSP数 据，对应的距离矩阵为
例
背包问题的贪婪算法
step1 对物品以ci ai从大到小排列，不妨把 排列 记成1,2, ,n，k1； step2 若
ai xi ak b ，则 xk 1 ；否则 xk 0.
i 1
k 1
k k 1 ；当k n 1 时，停止；否则重复step2．
(x1, x2, , xn)为贪婪算法所得解．单位体积价 值比越大越先装包是贪婪算法的原则． 这样的算法非常直观，非常容易操作．
启发式算法的性能分析
大规模计算分析 就是通过大量的实例计算,评价算法的计算效 果.算法的计算效果分成两个方面:一方面是算法 的计算复杂性,它的效果通过计算机的中央处理 器(CPU)的计算时间表现;另一个方面是计算解 的性能,它通过计算停止时输出的解表现. 对一个算法进行评价时,它的计算时间效果往 往通过目前的计算机设备能否承受,用户能否接 受现有的计算时间来衡量.对它的计算解进行评 价时,一个简单的要求是用户是否满意.
0 10 D ( d ij ) 15 6 2 10 0 8 13 9 15 8 0 20 15 6 13 20 0 5 2 9 15 5 0
初始解为xbest＝（ABCDE）， f(xbest )=45.邻域映 射定义为对换两个城市位置的2-opt．选定A城市 为起点，用全邻域搜索，即S:=N(xbest ) 第一循环： N(xbest )={(ABCDE),(ACBDE) (ADCBE),(AECDB),(ABDCE),(ABEDC), (ABCED)}，对应目标函数值为: f(x)={45,43, 45,60, 60,59,44}. xbest : = xnow=(ACBDE） 第二循环：N(xbest )={(ACBDE),(ABCDE) (ADBCE),(AEBDC),(ACDBE),(ACEDB), (ACBED)}, f(x)={43, 45, 44, 59,59,58,43}. xbest : = xnow=(ACBDE）
定义1.4 若S*满足 f (S*) ( )f (S )，其中， S N(S*) F，则称S*为 f 在 F 上的局部最小 (大)解．若 f (S*) ( )f (S )， S F，则称S*为 f 在 F 上的全局最小(大)解．
1.4 启发式算法
因为一些组合最优化问题还没有找到求最优解的 多项式时间算法，而这些组合最优化问题又有非常 强的实际应用背景，人们才不得不尝试用一些并不 一定可以求解到最优解的算法，在此称为启发式算 法，来求解组合最优化问题。 启发式算法是相对于最优算法提出的．一个问题 的最优算法求得该问题每个实例的最优解．启发式 算法可以这样定义： 一个基于直观或经验构造的算法，在可接受的花 费（指计算时间，占用空间等）下给出待解决组合 优化问题每一个实例的一个可行解，该可行解与最 优解的偏离程度不一定事先可以预计．
成个城市所有枚举为单位，则枚举时城市数与计 算时间的关系如表所示。
城市数 24 25 26 27 28 29 30 计算时间 1s 24 s 10 min 4.3h 约4.9d 136.5d 约10.8年
通过表可以看出，随着城市数的增多，计算时间 增加非常之快，当城市数增加到时，计算时间约 .年，已无法接受。所以，我们必须对计算复杂 性理论有所了解，这也是最优化的理论基础。只有 了解所研究问题的复杂性，才能有针对性地设计算 法，进而提高优化效率。主要简单介绍一下多项式 时间算法和指数时间算法。
其中(1.8)中的决策变量 xij=1 表示商人行走的路线 包含从城市i 到城市j 路径，xij=0 表示商人没有选 择走这条路．i j 的约束可以减少变量的个数，使 得共有n(n1)个决策变量. (1.5)要求商人从城市i 出来一次，(1.6)要求商人走入城市 j只有一次.
(1.5)和(1.6)表示每个城市经过一次．仅有(1.5)和 (1.6)的约束无法避免回路的产生，(1.7)约束商人 在任何一个城市子集中不形成回路．此时 D 0 , 1nn1． TSP问题解的另一种表示法为循环排列
参考书:
１．《 现代优化计算方法 》— 邢文训 谢金星
２．《 非数值并行算法
— 康立山
第一册Leabharlann — 模拟退火算法》谢云等1.1 组合最优化问题
组合最优化是通过对数学方法的研究去寻找离散 事件的最优编排、分组、次序或筛选等，该问题可 用数学模型描述为：
min f ( x ) s .t . g ( x ) 0 x D
s .t . a i x i b
i 1
n
x i 0 , 1, i 1 , , n
其中xi 1表示装第i个物品，xi 0表示不装．此时， D 0 , 1n，F为D中满足(1.2)的可行解集．
例1.2 旅行商问题(TSP,traveling salesman problem)
1.5 局部搜索算法
假设算法用以解决如下组合优化问题：
min f ( x ) s .t . g ( x ) 0 x D
其中，f (x)为目标函数，g(x)为约束函数，D定义 域． 局部搜索算法可以简单的表示为：
局部搜索算法 Step1 Step2 选一个初始可行解x0；记录当前最优解 xbest:=x0，令P=N(xbest )； 当P=时，或满足其他停止运算准则时, 输出计算结果，停止运算；否则，从 N(xbest )中选一集合S ，得到S 中的最优解 xnow；若 f (xnow)<f (xbest)，则 xbest:= xnow， P:=N(xbest )；否则；P:= P －S ；重复 step2．
N ( x ) y y x yij xij k , y D i, j
k为一个正整数．这个邻域定义使得x 最多有k 个 位置的值可以发生变化．x 的邻居有
1 2 k C n( n1) C n( n1) C n( n1) 个 .
一个商人欲到n个城市推销商品，每两个城市i 和j之间的距离为dij，如何选择一条道路使得商人 每个城市走一遍后回到起点且所走路径最短． TSP可分为对称和非对称距离两大类问题． 当 dij=dji ,i,j 时，称为对称距离TSP，否则称为 非对称距离TSP．对一般的TSP，它的一种数学模 型描述为：
复杂性分析的一个研究方向是对算法进行评价。 对于解决一个问题的算法，如何评估这个 算法 的性能？复杂性分析是评价算法的一个指标。复 杂性分析是通过从最坏实例的条件下，确定 是否存在多项式函数 g(x)，即可以叙 述为：对 一个求解问题的算法，是否存在多项 式函数 g(x) 和常数，使得对问题的任意一个实例I，都有 成立。 复杂性分析的另一个研究方向是对组合优化 问题归类。
例1.5
TSP问题解的另一种表示法为
D F s ( i1 , i2 , , in ) | i1 , i2 , , in 是 1,2, , n 的一个排列
定义它的邻域映射为2-opt，即S中的两个元素进行 2 C n 个邻居．如四个城市 对换， N(S)中共包含S 的 的 TSP问题，当 S =(1,2,3,4)时， N(S)={(2,1,3,4),(3,2,1,4),(4,2,3,1),(1,3,2,4),(1,4,3,2),(1, 2,4,3)}.
D F s ( i1 , i2 , , in ) | i1 , i2 , , in 是 1,2, , n 的一个排列
数学模型为：
min L d i j i j 1
j 1 n

(记 in1 i1 )
1.2 计算复杂性的概念
由于有些优化算法所需的计算时间和存储空间难 以承受，因此算法可解的问题在实践中并不一定可 解。由组合最优化问题的定义可知，每一个组合最 优化问题都可以通过枚举的方法求得最优解。枚举 是以时间为代价的，有的枚举时间还可以接受，有 的则不可能接受。 例如对非对称距离TSP问题，可以用另一个方法 来表示它的可行解：用n个城市的一个排列表示商 人按这个排列序推销并返回起点。若固定一个城市 为起点，则需要n个枚举。以计算机秒可以完

例1.6 对o-1背包问题，由模型 Dxx0,1n，可以定义它的一种邻域为：
n N ( x ) y y x y i x i 2 i 1
这个邻域定义使得x 最多有2个位置的值可以发 生变化．x 的邻居有
1 2 Cn Cn 个 .