智能优化算法是一类借鉴自然界物理现象、生物进化、群体行为等过程的启发式优化技术，如模拟退火、遗传算法、粒子群优化等．它们通过迭代搜索和自我调整策略，在复杂、高维、非线性等问题空间中寻找最优解，尤其适用于传统优化方法难以有效解决的全局优化问题和离散优化问题．因其具有较强的全局寻优能力和对初值不敏感等特点，在工程设计、机器学习、运筹学等领域有广泛应用．
7.1.1 连续非凸优化问题与经典组合优化问题
最优化问题也可分为连续优化问题和组合优化问题两大类，其中连续优化问题的变量是一定区间的连续变量，而组合优化问题（或离散优化问题）的变量则是解空间中的离散变量．前面研究的整数线性规划问题即是组合优化问题．
7.1.1.1 几个经典多峰函数
连续优化问题通常可描述为：令S为\mathbb R^n上的有界子集（即变量的定义域），f:S\to\mathbb R为n维实值连续函数，函数f在S上的全局最小化就是寻求点\mathbf x_{\min} \in S，使得f(\mathbf x_{\min})在S上是全局最小，即∀\mathbf x\in S:f(\mathbf x_{\min})≤f(\mathbf x)．
连续的的全局最小化是非凸优化问题，下面列出几个连续的多峰函数并简述其特点．
1. Ackley Function
Ackley 函数广泛用于测试优化算法．其表达式为
f(\mathbf x)=-20 \ \text{e}^{\displaystyle\left(-0.2\times\sqrt{\frac{1}{n}\sum_{i=1}^{n}x^2_i}\right)}-\text{e}^{\displaystyle\left[\frac{1}{n}\sum_{i=1}^{n}\cos(2\pi x_i)\right]}+20+\text{e}．
其维度为n，通常定义在超立方体x_i\in[-32.768, 32.768],i = 1,2,\cdots,n上，全局最小为f(\mathbf x^*)=0, x^*=(0,0,\cdots,0)^\top．
在二维情形下，Ackley 函数的图形及其在水平面的的等值线如图 7-1-1附录 / 附录程序中左图所示，它的特点是外部区域几乎平坦，中心有一个大洞．该函数会给优化算法带来风险，尤其是，可能会陷入其众多局部最小值之一．
Ackley 函数Ackley 函数2维图形及在水平面上的等值线。
Griewank函数Griewank函数2维图形及在水平面上的等值线。
0 / 0图7-1-1Ackley 和 Griewank 函数（2维）图形及在水平面上的等值线
2. Griewank Function
Griewank函数的表达式为
f(\mathbf x)=\displaystyle\frac{1}{4000}\sum_{i=1}^{n}x^2_i-\prod_{i=1}^{n}\cos\left(\frac{x_i}{\sqrt{i}}\right)+1，
其维度为n，该函数通常定义在超立方体x_i \in[-600,600], i = 1,2,\cdots,n上，全局最小为f(x∗)=0,x∗=(0,0,⋯,0)^⊤．
Griewank 函数具有许多广泛且规则分布的局部最小值．在二维情形下，函数的图形如图 7-1-1中右图所示
3. Rastrigin Function
Rastrigin 函数的表达式为
f(\mathbf x)=\displaystyle\sum_{i=1}^{n}\left[x^2_i-10\cos\left(2\pi x_i\right)+10\right].
其维度为n，该函数通常定义在超立方体x_i \in [-5.12, 5.12], i = 1,2,\cdots,n上， 全局最小为f(\mathbf x^*)=0, x^*=(0,0,\cdots,0)^{\top}．
Rastrigin 函数有许多局部最小值．它是高度多峰的，但这些最小值的位置有规律地分布．其二维情形下的图形如图 7-1-2附录 / 附录程序中左图．
Rastrigin 函数Rastrigin 函数。
Schaffer 函数Schaffer 函数。
0 / 0图7-1-2Rastrigin 和 Schaffer 函数（2维）图形及在水平面上的等值线
4. Schaffer Function N2
Schaffer N2 函数的表达式为
f(\mathbf x)=0.5+\frac{\sin^2\left(\displaystyle\sqrt{x^2_1+x^2_2}\right)-0.5}{\left[1+0.001\left(x^2_1+x^2_2\right)\right]^2}，
其维度为2，该函数通常定义在x_i \in [-100, 100], i=1,2上i = 1,2上， 全局最小为f(\mathbf x^*)=0, \mathbf x^*=(0,0)^\top．
Schaffer N2 函数有许多局部最小值，函数图形如图 7-1-2中右图．
5. Six-Hump Camel Function
Six-Hump Camel 函数表达式为
f(\mathbf x)=4x^2_1-2.1x^4_1+\frac{1}{3}x^6_1+x_1x_2-4x^2_2+4x^4_2
其维度为2，该函数通常在矩形区域x_1 \in [-3, 3], x_2 \in [-2, 2]上， 全局最小解有两个，即\mathbf x^* \approx (\pm0.0898420,\mp0.7126564)^\top，最优值f(\mathbf x^*) = -1.031628．
该函数共有六个局部最小值，其中两个是全局最小值，其图形如图 7-1-3附录 / 附录程序所示．
图7-1-3Six-Hump Camel 函数（2维）图形
在其它文献中可以发现更多测试函数．
7.1.1.2 经典组合优化问题
组合优化问题 (Combinatorial optimization problem) 是一类在离散状态下求极值的最优化问题，其数学模型如下所示：
\begin{aligned}&\min F(\mathbf x) \\ &\text{s.t.} \begin{cases}\mathbf G(\mathbf x) \geq \mathbf 0 \\ \mathbf x \in \mathbf D \end{cases}\end{aligned}，
其中\mathbf x为决策变量、F(\mathbf x)为目标函数、\mathbf G(\mathbf x)为约束条件，\mathbf D表示离散的决策空间，为有限个点组成的集合．如在第3章中学习的整数线性规划问题即为组合优化问题．
组合优化问题的决策空间为有限点集，直观上可以通过穷举法得到问题的最优解，但是由于可行解数量随问题规模呈指数型增长，无法在多项式时间内穷举得到问题的最优解．多数组合优化问题属于．
1. 旅行商问题
旅行商问题（Traveling Salesman Problem, 简记为）又称为货郎担问题，是最基本的路线问题，该问题是在寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径成本．
假定有n个城市，城市i,j之间的距离或成本c_{ij}，希望找一条起点和终点重合的旅行路线，使得路线的总距离最短或总花费最少．其数学模型为
\begin{aligned} &\min \displaystyle \sum_{i=1}^n \sum_{j=1}^n c_{ij} x_{ij} \\ &\text{s.t.} \begin{cases} \displaystyle\sum_{i=1}^n x_{ij} =1, \ j=1,2\cdots,n \ \ \ &(1)\\ \displaystyle\sum_{j=1}^n x_{ij} =1, \ i=1,2\cdots,n \ \ \ &(2)\\ \displaystyle\sum_{i,j\in S} x_{ij} \le |S|-1, \ \forall S\subseteq V,\ 1<|S|<n \ \ \ &(3)\\ x_{ij} \in \{0,1\},\ i\in V, j \in V \end{cases} \end{aligned}．
其中x_{ij}取1表示包含从城市i到城市j的路线，取0表示不包含从城市i到城市j的路线；V=\{1,2,\cdots,n\}表示城市标签集合；约束(1)和(2)保证每个城市只进出一次，约束(3)保证任意子图不存在子回路，从而保证所有点构成一个回路．这是一个0-1整数规划问题．
图7-1-4中国34个城市的TSP问题的解
TSP问题在物流中的描述是对应一个物流配送公司，欲将n个客户的订货沿最短路线全部送到，如何确定最短路线．图 7-1-4显示了中国34个城市TSP问题的一个解．
2. 车辆路径问题
车辆路线问题（Vehicle Routing Problem, 简记为VRP）最早是由Dantzig和Ramser于1959年首次提出，它是指一定数量的客户，各自有不同数量的货物需求，配送中心向客户提供货物，由一个车队负责分送货物，组织适当的行车路线，目标是使得客户的需求得到满足，并能在一定的约束下，达到诸如路程最短、成本最小、耗费时间最少等目的．如图 7-1-5是一个简单的VRP示意图．
车辆路线问题自1959年提出以来，一直是网络优化问题中最基本的问题之一，由于其应用的广泛性和经济上的重大价值，一直受到国内外学者的广泛关注．不难看出，旅行商问题(Traveling Saleman Problem,TSP)是VRP的特例，由于Gaery已证明TSP问题是NP难题，因此，VRP也属于NP难题．
图7-1-5VRP的一个实例
对于 VRP 问题，已知参数为：
n: 客户点的数量（不包括起始点）；
m: 车辆的数量；
d_{i}: 客户点i的需求量；
c_{i,j}: 客户点i到客户点j的距离或成本．
设决策变量设为x_{ij}^k，若车辆k在访问客户点i后移动到客户点j，则x_{ij}^k为1，否则为 0．
目标函数为最小化总行驶距离或成本，即
\displaystyle\min\sum_{k=1}^{m}{\sum_{i=0}^{n}{\sum_{j=0}^{n}{c_{i,j}\cdot x_{ij}^{k}}}}．
约束条件：
（1）每个客户点必须被访问且仅被访问一次：\displaystyle\sum_{k=1}^{m}{\sum_{j=1}^{n}{x_{ij}^{k}}}=1,\forall i=1,\cdots,n
（2）每辆车的路径必须从起始点开始，并在终点结束：
\displaystyle\sum_{j=1}^{n}{x_{0j}^{k}}=1,\forall k=1,\cdots,m\\ \displaystyle\sum_{i=1}^{n}{x_{i0}^{k}}=1, \forall k=1,\cdots,m
（3）Binary(0-1)约束：
x_{ij}^{k}\in\left\{ 0,1\right\},\forall i=0,\cdots,n, \forall j=0,\cdots,n, \forall k=0,\cdots,m
在VRP中，问题的目标是找到一种车辆分配方案，使得每辆车都从一个起始点开始，途中访问一系列客户点，最终返回起始点．
3. 车间作业调度问题
车间作业调度问题（Job Shop Scheduling Problem，简记为JSSP）是许多实际生产调度问题的抽象模型，是典型的NP-hard问题之一，其应用领域极其广泛，如机场飞机调度，港口码头货船调度，汽车加工流水线等．
JSSP问题描述：一个加工系统有m台机器，要求加工n个作业，其中，各工序的加工时间已确定，并且每个作业必须按照工序的先后顺序加工．调度的任务是安排所有作业的加工调度排序，约束条件被满足的同时，使性能指标得到优化．
JSSP常用的数学模型如下：
\begin{aligned}
&\max (\min)\ objective\\
&\text{s.t.} \begin{cases}
t_{kj} ≥ t_{ij} + p_{ij}, \ \forall (i,j),(k,j) \in A &\qquad(1)\\
t_{ij} ≥ t_{ik} + p_{ik}, \ \forall (i,j),(i,k) \in N &\qquad(2)\\
t_{ik} ≥ t_{ij} + p_{ij}, \ \forall (i,j),(i,k) \in N &\qquad(3)\\
t_{ij} ≥ 0, \ \forall (i,j) \in N &\qquad(4)
\end{cases}
\end{aligned}
其中，
objective表示完成所有工件加工后的要求目标；
p_{ij}表示工件j机器i上的加工时间；
t_{ij}表示工件j在机器i上的开始加工时间；
N表示操作工序(i,j)的集合；
A表示工件j在机器k上加工前必须在机器i上加工操作依赖关系对(i,j)→(k,j)的集合．
约束（1）表示第k个工件在机器j上加工，且必须在其前一道工件i加工完成后才能开始加工；约束（2）表示某一时刻1台机器只能加工1个作业；约束（3）表示每个作业只能在1台机器上加工1次；约束（4）表示所有工序的开始时间必须大于零．
4. 背包问题
背包问题（Knapsack Problem）是在多个件物品取出若干件放在特定空间的背包里，每件物品的体积和与之相对应的价值已知．问放哪些物品到包里，使得总价值最大．
0-1背包是背包问题中最简单的一种，其约束条件是给定几种物品，每种物品有且只有一个，并且有权值和体积两个属性．0-1背包问题数学表述为：给定n件物品，第i件物品的重量为w_i、价值为c_i．现挑选物品放入背包中，假定背包能承受的最大重量为W，问应该如何选择装入背包中的物品，使得装入背包中物品的总价值最大？
从数学规划的角度来进行理解，求解0-1背包实际上就是求如下的数学规划问题：
\begin{aligned}
&\max \ \sum_{i=1}^n c_i x_i \\
&\text{s.t.} \begin{cases}
\sum_{i=1}^n w_i x_i \le W \\
x_i \ge 0, x_i \in \mathbb N, \ \forall i.
\end{cases}
\end{aligned}
5. 装箱问题
装箱问题（Bin packing）是一个经典的组合优化问题，有着广泛的应用．设有许多具有同样结构和负荷的箱子B_1, B_2,\cdots,B_k，其数量足够供所达到目的之用．每个箱子的负荷（可为长度、重量等）为C，今有n个负荷为w_j，0 < w_j < C，j = 1,2,\cdots,n的物品J_1, J_2,\cdots,J_n需要装入箱内．装箱问题就是指寻找一种方法，使得能以最小数量的箱子数将J_1, J_2,\cdots,J_n全部装入箱内．
装箱问题可以分为一维、二维、三维、多维等．
一维装箱问题是最常见的，只考虑一个因素，比如重量、体积、长度等．
二维装箱问题考虑两个因素——给定一张矩形的纸（布料、皮革），要求从这张纸上剪出给定的大小不一的形状，求一种剪法使得剪出的废料的面积总和最小．
三维装箱问题考虑三个因素——一般指长、宽、高．装车、装船、装集装箱等f均需要考虑这三个维度．
图7-1-6三维装箱问题
多维装箱问题要考虑多个因素——比如既包括体积因素长、宽、高，又包括重量．
装箱问题的整数整数规划模型为：
\begin{aligned}
&\max (\min)\ \sum_{i=1}^n y_i \\
&\text{s.t.} \begin{cases}
\sum_{i=1}^n w_i x_{ij} \le Cy_i, \ j=1,2\cdots,n \ \ \ &(1)\\
\sum_{i=1}^n x_{ij}=1, \ j=1,2\cdots,n \ \ \ &(2)\\
x_i \in\{0,1\}, y_i\in\{0,1\} \ \ \ &(3)
\end{cases}
\end{aligned}
其中
x_{ij}取1表示物品i放到箱子j中，否则取0；
y_{i}取1表示物品i放到箱子j中，否则取0；
约束条件（1）表示：一旦箱子i被使用，放入箱子i中的物品总负荷不超过V；
约束条件（2）表示：每个物品恰好放入一个箱子中．
装箱问题广泛存在于工业生产，包括服装行业的面料裁剪、运输行业的集装箱货物装载、加工行业的板材型材下料、印刷行业的排样和现实生活中包装、整理物件等．在计算机科学中，多处理器任务调度、资源分配、文件分配、内存管理等底层操作均是装箱问题的实际应用．
7.1.2 求解组合优化问题数学方法分类
求解组合优化问题可以通过利用各种数学方法，寻找离散事件的最优编排、分组、次 序或筛选等．目前常用的优化算法可以分为以下四类：
（1）精确算法
精确算法是指能够求出问题最优解的算法．当问题的规模较小时，精确算法能够在可接受的时间内得到最优解；当问题的规模较大时，精确算法一方面可以提供问题的可行解，另一方面可以为启发式算法提供初始解，以便搜索到更好的解．
常用的精确算法有分支定界法、割平面法、动态规划法等．
（2）启发式算法
启发式算法是一种基于直观或经验构造的算法，能在可接受的计算成本内尽可能地．近最优解，得到一个相对优解，但无法预计所得解与最优解的近似程度．启发式算法通常是以问题为导向的，也就是说，没有一个通用的框架，针对不同的问题设计不同的启发式算法，通常被用来解组合优化问题。
启发式算法包括构造性方法、局部搜索算法、松弛方法、解空间缩减算法等．
（3）元启发式算法
元启发式算法主要指一类通用型的启发式算法，它对启发式算法进行了改进，是随机算法与局部搜索算法相结合的产物．这类算法的优化机理不过分依赖与算法的组织结构信息，可以广泛地应用到函数的组合优化和函数计算中．
元启发式算法包括禁忌搜索算法、模拟退火算法、遗传算法、粒子群算法、蚁群算法、人工神经网络等．
对于结构化的组合优化问题，其解空间的规模能够得到控制，使用精确算法可以求得最优解．但是在企业实际面临的应用场景中，问题规模往往很大，求得最优解需要的计算量与存储空间的增长速度非常快，易产生“组合爆炸”，于是学界和业界多尝试通过构建启发式算法（含元启发式算法）进行处理．
