启发式算法和精确算法

2.098/15.093J Recitation 9

Xuan Vinh Doan

2004,10,11

1、启发式算法

整数规划一般是不容易得到最优解的。启发式算法可以在合理的计算时间内得到较优的

可行解。局域搜索启发式算法应用广泛。局域搜索的一般步骤如下：

1、 从一个初始可行解出发

2、 找出相邻的可行解

3、 从相邻的可行解中找出更好的可行解

一般地，局域搜索启发式算法会得到一个局部最优解，而这个局部最优解有时就是全局最优

解。算法的好与坏都决定于步骤3。

1.1模拟退火方法

相邻元素是随机选择的，选上的概率为， np1=∑∈Nnnp。移动的决策取决于

目标成本和退火概率：

()()()()()

()⎪⎩⎪⎨⎧=−−

xpxcycexpp

yTxcyc

yxyφ 其中温度梯度是根据一定的规则选择的，比如tCtTlog)(=或，。 tCatT=)(1πa

1.2 其它方法

其它局域搜索式方法还有很多，具体问题有相应的方法。如：禁忌搜索、遗传算法（略有不

同），蚁群优化法也是一种。

1、 禁忌搜索的组成部分：禁忌表（移动的列表或移动的特征的列表），集中化（好的解），

多样化（不好的解）。

2、遗传算法的组成部分：染色体（解的表示法），选择、交叉、变异。

3、蚁群优化：信息素轨迹和启发式愿望（收敛速度）。

1 2、 动态规划

2.1 动态规划要素

1、（最重要的）状态变量. kx

2、控制（或决策）变量，ku)(kkxUu∈。

3、随机变量. kw

4、状态转移方程),,(1kkkkkuxfxω=+

5、附加费用。 )),,()((11kkkNikNNWuxgxgEω∑−=+

2.2 Bellman最优化原理

这里我们想要分个阶段来求出总的最小费用。最后阶段的费用为。在第k阶段

状态为下，决定控制变量,使从第阶段到最后的总费用最小。按下面的递推公式： N)(NNxg

kxkuk

()(){}))),,((),,(min1kkkkkkkkkwxUukkwuxfJwuxgExJkkk+∈+=

求解VRP问题的有效算法

在物流管理领域中，车辆路径规划问题（Vehicle Routing

Problem，简称VRP）一直是研究的热点。VRP是一种NP难问题，即难以求解的组合优化问题。该问题涉及到多个车辆在多个客户之间进行货物配送的路线规划，目标是使总配送成本最小化。尽管VRP是一个难题，但是研究者们已经开发出了一系列有效的算法来解决这个问题。

一、基础VRP问题

基础的VRP问题可以被归结为以下几个部分：客户集合S，客户之间的距离为d(i, j)，每个客户有需求量d(i)，每个车辆有容量Q，每个车辆的行驶路线长度不能超过车辆的行驶范围L。对于基础VRP问题，旅行商问题（Traveling Salesperson Problem，简称TSP）可以被视为特殊情况，即只有一个车辆和所有客户都要被服务。

二、求解VRP问题的算法

1.精确算法：精确算法利用数学模型来确切地解决基础VRP问题。其中最常用的算法是分支定界法和分支定价法。

分支定界法：分枝定界法将复杂的VRP问题分解成一个大问题和若干个小问题，并通过深度优先算法搜索可行解空间以确定最优解。在搜索枚举进程中，如果找到一个解，它会被与当前最优解比较，直到找到一个更优解。分支定界法的主要优点是可以得到最优解，但它的计算复杂度非常高，因此只适用于小规模问题。

分支定价法：分支定价法是对分支定边法的一种扩展，是一种动态决策技术，其目标是在可行解空间内找到最小成本解。该算法主要基于线性规划模型及其相应的分支定界技术，通过建立合适的线性规划模型，寻找可行解空间内的最优解。

2.启发式算法：为了有更好的效率解决VRP问题，启发式算法在实践中经常被使用。这些算法主要适用于大规模问题，其中包括模拟退火，遗传算法，蚁群算法，粒子群算法等。其中，蚁群算法是求解VRP问题的最常用的启发式算法之一。

蚁群算法：蚁群算法是指模拟蚂蚁在寻找食物时的追踪行为的算法。该算法模拟了一组人工蚂蚁在一个基础VRP问题中服务所有客户的过程。蚂蚁在某个节点上释放信息素，并选择下一个节点的概率是基于其周围信息素水平和节点的距离，从而使具有更高信息素水平的路径更有可能被选择。从而，蚂蚁在搜索图中尝试多个方向移动，最终得到VRP问题的最优解。

启发式算法（heuristic）WHY：

1.有时候最优解是难以找到，甚⾄是⽆法找到的，此时我们希望去找⼀个逼近最优解的解。

2.有时⾮最优解也可接受。

WHAT：

我认为启发式算法称为「探索式算法」or「经验学习法」更加合适。

有⼀些不错的说法：

启发式⼀般⼜称⼈⼯智能算法或全局优化算法。

启发式算法是指具有⾃学习功能，可利⽤部分信息对计算产⽣推理的算法。...

ps：这部分可见：

朗⽂对heuristic的解释是：The use of experience and practical efforts to find answers to questions or to improve performance.

翻译过来就是：依赖于过去的经验来找到问题的解决⽅式或者提⾼表现。

维基百科词条heuristic，将其定义为基于经验的技巧（technique），⽤于解决问题、学习和探索。

我们可以将heuristic等同于经验⼯作法（rule of thumb）、有依据的猜测（educated guess, a guess beased on a certain amount of information, andtherefore likely to be right）和常识（由经验得来的判断⼒⽽⾮准确测量）。

启发式算法（Heuristic Algorithm）定义（我赞同的）：相对于最优化算法。启发式算法是基于直觉或已有经验的算法，能够在可接受的计算成本（计算时间、

占⽤空间等）内去搜寻最好的解，但是不保证能够找到可⾏解或最优解，在多数情况下⽆法阐述所得解⽤最优解的近似程度。

其特点是在解决问题时,利⽤过去的经验,选择已经⾏之有效的⽅法，⽽不是系统地、以确定的步骤去寻求答案（指算法）。相对于⼀般的算法把各种可能性都⼀

⼀进⾏尝试，最终能找到问题的答案，启发式算法（启发式⽅法）则是在有限的搜索空间内，⼤⼤减少尝试的数量，能迅速地达到问题的解决。但由于这种⽅法

启发式算法研究小结

0. 探究启发式算法的缘由

在选《管理优化决策》这门课的时候，我抱着很强的好奇心和巨大的求知欲，试图尝试在这门课上学到我感兴趣的知识点以及确定我今后极有可能的研究领域和大方向。很幸运的是，我找到了。为什么这么说呢？就在我选择博士专业内选修课和专业外选修课的同时我发现了管理优化决策这门课和计算机学院那边开的选修课——《启发式优化》（由吕志鹏教授讲授），有很多是相通的，发现管理界尤其是在管理科学与工程方向和计算机技术应用领域所探究的问题出奇的一致，已经很难分清，哪个是管理方面的问题，哪个是计算机技术应用的范围了。正如各位都知道的是，由于选修课最终确定前一个月是可以去试听的，然而我并没有因为两者看上去内容有些相似就匆忙退选。通过对这两门课的内容进行比较，它给了我很大的触动，也带给我巨大的好奇，到底是管理方面的研究越来越偏向运用计算机等其他学科的知识和工具，还是计算机应用研究的方面越来越偏向实际的管理优化问题了呢？亦或者两个学科的边界正在走向模糊？我想学科交叉和融合的这一说法对于我来说可能并不是很新鲜，但这的确是我亲身经历的一种美妙体验和发现。它带给我新奇的同时也无疑给了我值得我深思几点的启示：

首先，众所周知，管理学科作为一门交叉的新兴学科，它的方法和工具都是依托和借助其他领域和学科而来的，它本身并没有或者几乎没有一个完完整整的只属于管理学科的方法和工具，几乎是其它学科的知识演变而来的，这就是我们所知道的学科交叉和学科融合；然而管理领域和传统计算机研究等领域的视角并不完全一样，其中对于计算机领域的研究者们而言，他们不但在乎启发式算法是否能够解决问题、效率是否大幅提高（而管理领域的专家们更在乎这点，能用第一，好用第二，或者说管理专家们更在乎第一点——问题能够得到的解决，至于第二点就不是那么迫切。而对计算机领域的向专家们而言，可以说两者都非常重要、要求非常苛刻），更在乎它所表现出来的优越特性（就时间、空间复杂度以及算法求解过程中保持一定的集中性和分散性而言的）。然而当管理领域的学者们求解类似问题，一般来说都是和我们生活中的管理者经常遇到且直接和的决策相关的问题，因为由于管理者的决策质量好坏会往往直接导致企业和团体的效率和绩效和高低，进而导致企业和组织的竞争力强弱，所以一般企业或者个人都是基于一定的价值诉求来解决管理问题，进而提高工作效率。由于管理者们非常了解生活中并不存在完完全全的理性人和完全信息，因此他们很难也极少去尝试寻找最优解，找到满意解就可以了，这一点和启发式算法的设计思想不谋而合（由于时间、硬件资源有限，特别是遇到组合爆炸问题时短时间难于穷举和难与求解出最优解，而且短时间还必须给出解。尽管二者有所差异，但都有一些共同之处，都是资源受限）。综上所述，对于同一个所以在求解管理方面较为复杂的问题时，我们短时间很难给出精确地解析解时，这时考虑运用启发式算法也不失为一种飞常有效的方法，而且生活我们经常在用，也不断地被证明了启发式算法优良的特性（简单、迅速且解的质量较高）。