目录

第4章 优化问题求解

4.1 引言

4.2 优化问题

4.2.1 智力游戏问题

4.2.2 现实世界问题

4.3 优化问题的求解

4.3.1 局部搜索

4.3.2 元启发式

4.3.3 群体智能

4.4 局部搜索方法

4.4.1 爬山法

4.4.2 局部束搜索

4.5 元启发式方法 

4.5.1 禁忌搜索

4.5.2 模拟退火算法

4.5.3 遗传算法

 4.6 群体智能方法

4.6.1 蚁群优化算法

4.6.2 粒子群优化算法

4.7 小结

---

第4章 优化问题求解

4.1 引言

现实世界中的许多问题，往往存在多元的解空间，从多元的解空间中提取最优选项，则称为优化问题。

变量分为两类：一类是连续变量，另一类则是离散变量。涉及离散变量的优化问题，称为离散优化问题，其中包括组合优化问题以及NP优化问题。

优化问题又可以根据其约束情况分为两种，一种是无约束优化问题，另一种是约束优化问题。

4.2 优化问题

对于一般的优化问题，通过一系列复杂的计算可以求得最优解，但对NP完或NP难的优化问题而言，人工智能的方法是一条有效的途径。

对于优化问题来说，问题的解往往与路径无关，而且也往往无法事先设定问题的目标状态。

4.2.1 智力游戏问题

大多数智力游戏具有明确的目标状态，需要找到能够达到目标状态的动作序列，然而还有一些智力游戏问题属于优化问题，它们可能存在多个目标状态，且目标状态实现未知，问题的求解是通过某种既定的方式找到符合要求的目标状态。

例4.1 旅行推销员问题

例4.2 背包问题

4.2.2 现实世界问题

现实世界的优化问题，往往涉及我们生活中的多个领域。

一部分现实世界的优化问题属于旅行推销员问题的泛化，反过来也可以说是推销员问题在现实世界中的应用。还有一些现实世界的优化问题属于背包问题的泛化。

4.3 优化问题的求解

求解优化问题主要有以下几种途径，即：局部搜索、元启发式以及群体智能。

4.3.1 局部搜索

局部搜索是针对一些难以找到全局最优解的复杂问题，采用局部最优的思想，从问题空间中的某个候选解出发，每次找出一个相邻的候选解并进行比较，直到找到一个最优解为止。

4.3.2 元启发式

元启发式指的是基于客观约束条件或模拟自然现象而构建的一类通用的算法框架，旨在解决复杂的优化问题。

4.3.3 群体智能

群体智能是受自然界中集群智能的启发而形成的一类方法。集群智能是大量的同类智能主体通过合作实现的智能。

4.4 局部搜索方法

局部搜索方法是一类启发式优化方法的总称，即对于一些难以找到全局最优解的复杂问题，采用局部最优的思想去寻找一个局部最优解。

4.4.1 爬山法

爬山法是一种迭代算法，也叫作爬山搜索算法，其主要步骤是：开始时任意选择问题的一个解作为已有解；然后通过修改已有解的某些元素来生成一个候选解；如果候选解优于已有解，则将其作为新的解；重复上述操作直到无法得到进一步的改善为止。

随机爬山法是在向上移动的过程中随机选择下一个状态；选择的概率随向上移动的斜度而变化。与最陡爬山法相比，随机爬山法的收敛速度相对较慢，但增大了找到全局最大值的可能性。

首选爬山法随机生成若干个后继，直到生成一个比当前状态好的后继，当一个状态有许多后继状态时，用此策略为好。

随机重启爬山法是从随机生成的初始状态开始，进行一系列爬山搜索，直到找到目标。

4.4.2 局部束搜索

局部束搜索也是一个迭代算法，其步骤是：开始时随机选取k个状态；再生成k个状态的全部后继，如果这些后继中存在一个局部最优解，则搜索停止；否则算法将从选取最优的k个作为下一个状态，重复上述步骤。

在局部束搜索中，有用的信息能够在搜索线程之间传递，因此还可以进行并发处理。

局部束搜索会很快地集中在状态空间的某个小区域内，使得搜索代价比爬山法还要高。

随机数搜索是局部束搜索的改进版，它模仿随机爬山法，有助于缓解上述问题。

4.5 元启发式方法 

4.5.1 禁忌搜索

禁忌搜索是一种元启发式算法，用于解决组合优化问题。它根据所指定的禁忌条件，通过局部搜索或邻域搜索过程，从一个潜在的解到改进的相邻解之间反复移动，直到满足某些停止条件。在搜索过程中，该算法使用一种被称为禁忌表的数据结构，将每一步中找到的局部最优解暂时放入禁忌表中，以期获得更大的搜索空间。

4.5.2 模拟退火算法

模拟退火的灵感来自于退火技术，是一种求得近似全局最优解的概率方法。具体而言，模拟退火是在大型空间中搜索近似全局最优解的元启发式方法，通常用于离散的搜索空间。

模拟退火算法的核心思想可以概括为：它从剧烈的抖动开始（即使之达到很高的问题），然后逐步减少抖动的强度（即逐步降低温蒂）。

模拟退火算法的具体步骤是：首先使用启发式方法随机生成一个初始解；然后再随机生成一个相邻解，这是初始解的变异；若相邻解具有较低的代价则语义接受，而具有较高的代价则以概率P接受；当解的值低于阈值，或者已达到迭代最大次数时，则停止操作。

4.5.3 遗传算法

遗传算法是一种模仿自然选择过程的启发式搜索算法，该算法可看作是随机束搜索的变体，不同之处在于其后继节点是两个状态的组合而不是由单一状态所生成，其处理过程相当于有性繁殖，而不是无性繁殖。

遗传算法开始时随机生成k个状态，称其为种群，其中，每个状态称为个体。

 4.6 群体智能方法

代表性的群体智能算法有：

4.6.1 蚁群优化算法

蚁群优化算法是一种解决计算问题的概率技术，可以用于发现一个图上的最佳路径。

蚁群优化算法是在搜索路径上积累虚拟的“嗅迹”。开始时某个“蚂蚁”选择一个节点作为初始节点，然后根据路径上嗅迹的量选择一条路径；具有较多嗅迹的路径则具有较高的被选择的概率；重复直到更多的蚂蚁在每个循环中都选择同一个路径。

4.6.2 粒子群优化算法

粒子群优化算法通过若干例子构成一个围绕搜索空间移动的群体来寻找最优解，搜索空间的每个粒子和其他粒子的经验调整其“飞行”。

人工神经网络是一种大脑神经网络的简单模拟，而反向传播算法是训练人工神经网络的方法之一。为了改进人工神经网络的训练方式，已经有大量的应用进化计算的方法，其中包括若干篇采用粒子群优化来代替反向传播算法的论文。其结果表明，粒子群优化算法是一种训练人工神经网络的有效方法，它的训练时间短，并且在多数情况下取得了较好的结果。

4.7 小结

本章介绍了三种优化问题求解的方式，分别是局部搜索、元启发式和群体智能方法。

局部搜索采用局部最优的思想去寻找一个局部最优解，并在内存中保持较少的节点而不是路径：其中爬山法仅保持一个节点的轨迹；局部束搜索算法保持k个状态的轨迹而不是仅仅一个。

元启发式是基于客观约束条件或模拟自然现象而构建的一类通用的优化算法框架，其中：禁忌搜索采用一种带约束的邻域搜索过程；模拟退火算法是一种在大搜索空间逼近全局最优解的方法；遗传算法模仿自然选择的进化过程。

群体智能是受群体智能的启发而产生的优化方法，其中：蚁群优化算法模拟蚂蚁觅食过程中的最短路径行为，可用于寻找图的最优路径；粒子群优化算法则通过若干粒子构成一个围绕搜索空间移动的群体来寻找最优解。