现代优化算法学习心得（正式）

现代优化算法学习心得

年级：2009级工程硕士 姓名：龚强 学号：G0843011200091090102

在科技高度发展的今天，计算机在人们之中的作用越来越突出。在这个学期里，我专门学习了现代优化算法。

现代优化算法包括禁忌搜索（tabu search）、模拟退火（simu-lated annclaing)、遗传算法（genetic algorithms）、神经网络(neural networks)、拉格朗日松弛等算法。这些算法涉及生物进化、人工智能、数学和物理科学、神经系统和统计力学等概念，都是以一定的直观基础而构成的算法，我们称之为启发算法。启发算法的兴起于计算复杂性理论的形式有密切的联系，当人们不满足常规算法求解复杂问题时，现代优化算法开始体现其作用。我在这里就以禁忌搜索这种算法来谈谈现代优化算法在计算复杂性理论问题时所体现的优越性。

禁忌搜索(rabu scarch)算法是局部邻域搜运算法的推广，是人工智能在组合优化算法中的一个成功应用。Glover 在1986年首次提出这一概念，进而形成一套完整算法，详见文献[2，3]。禁忌搜索算法的特点是采用了禁忌技术。所谓禁忌就是禁止重复前面的工作。为了回避局部邻域搜索陷入局部最优的主要不足，禁忌搜索算法用一个禁忌表记录下已达到过的局部最优点，在下一次搜索中，利用禁忌表中的信息不再或有选择地搜索这些点，以此来跳出局部最优点。禁忌搜索算法是一种人工智能

的算法，因此，从以下方面来谈谈禁忌搜索算法。

1．局部搜索

除特别强调外，我们都假设算法用以解决如下组合最优化问题：

其中?(X)为目标数，g（x）为约束方程，D为定义域。 因为禁忌搜索算法中用到局部搜索算法，我们首先介绍局部搜索算法。该算法可以简单的表示为：

局部搜索算法

STEP1 选下一个初始可行解x0；记录当前最优解xbest：= x0，

令P=N（xbest）；

STEP2 当P=Ф时，或满足其他停止运算准则时，输出计

算结果，停止运算；否则，从N（xbest）中选一集合S，得到S中的最优解 xbest；若?xbest＜?xbest，则xbest：=xnow，P：= N（xbest）；否则，P：=P-S；重复STEP2。

在局部搜索算法中，STEP1的初始可行解选择可以采用随机的方法，也可用一些经验的方法或是其他算法所得到的解。STEP2中的集合S选取可以大到是N（xbest）本身，也可以小到只有一个元素，如用随机的方法在N（xbest）中选一点，从直观可以看出，S选取得小将使每一步的计算量减少，但可比较的范

围很小；S选取大时每一步计算时间增加，比较的范围自然增加，这两种情况的应用效果依赖于实际问题。在STEP2中，其他停止准则是除STEP2的P=Ф以外的其他准则。这些准则的给出往往取决于人们对算法的计算时间、计算结果的要求，通过下面的例子来理解局部搜索算法。

例2．1 5个城市的对称TSP数据 如图2.1

对应的距离矩阵为

初始解为xbest=（ABCDE），（fxbest

）=45。在本例中，邻域映射定义为对换两个城市位置的2-OPT，选定A城市为起点，我们用两种情况解释局部搜索算法。

情况1 全部域搜运，即S=- N（xbest）。

此时，P= N（xbest）—S为空集，于是所得解为（ADCBE），目标值为43。

情况2 一步随机搜索 xbest=（ABCDE），f xbest =45

第一循环：由于采用N（xbest）中的一步随机搜索，可以不再计算N（xbest）中每一点的值，若从中随机选一点，如xnow=（ACBDE）。因f（xbest）=43＜45，所以xbest：=（ACBDE）。 第二循环：若从N（xbest）中又随机选一点xnow=（ACBDE），f（xnow）=44＞43。P= N（xbest）-{xnow}，最后得到的解为（ACBDE）。

局部搜索算法的优点是简单易行，容易理解，但其缺点是无法保证全局最优性。

2.禁忌搜索

禁忌搜索是一种人工智能算法，是局部搜索算法的扩展，它的一个重要思想是标记已得到的局部最优解，并在进一步的选代中避开这些局部最优解，如何避开和记忆这些点是本章主要讨论的问题，首先，用一个示例来理解禁忌搜索算法。

例2.3（例2.2续）假设：初始解x0=（ABCD），邻域映射为两个城市位置对换，始终点都为A城市，目标值为f（x0）-4，城市间的距离为：

第1步：

解的形式 禁忌对象及长度 候选集

此处评价值为目标值，由天假设了A城市为起终点，故候选集中最多有两两城市对换对3个。分别对换城市顺序并按目标值由小到大排列，三个评价值劣于原值，在原有的局部搜索算法中，此时已达到局部最优解而停止，但现在，我们允许从候选集中选一个最好的对换—CD城市的位置交换，用★标记入选的对换，此时，解从（ABCD）变化为（ABDC），目标值上升，但此法可能跳出局部最优。

第2步：

由于第1步中选择了CD交换，于是，我们希望这样的交换在下面的若干次迭代中不再出现，以避免计算中的循环，CD成为禁忌对象并限定在3次迭代计算中不允许CD或DC对换。在对应位置记录3，在N（x1）中又出现被禁忌的CD对换，故用

本文来源：https://www.bwwdw.com/article/7umd.html