内容发布更新时间 : 2024/12/22 20:53:56星期一 下面是文章的全部内容请认真阅读。

该矩阵，那么禁忌对象如何选择？对应3.2.2中的问题1。上章中选择城市顺序对换作为禁忌对象目的是希望不再考虑某组顺序的对换，以避免不会有更好解出现，及又回到原有解这两种可能情况。本章中的禁忌对象沿用这种选取方法，即将两个城市顺序对换作为禁忌对象。

问题2中禁忌的长度如何选取？禁忌长度的选择有很多种，长度过短会造成循环，过长会造成算法的记忆存储量增加。因此，一种禁忌长度的选择，要保证禁忌长度既不太长，也不太短。本章中用公式（3.1）定义禁忌长度，即（31*（31-1）/2）开平方再取整，得21。

TabuLength=round((CityNum*(CityNum-1)/2)^0.5) （3.1）

前面定义时提到，要将候选集个数CandidateNum，预设为一个充分大的数，本问题中我们设为200。同时初始化候选解集合Candidates为一个CandidateNum行，CityNum列的零矩阵（即200*31矩阵）。这里需要说明一下，问题3“候选集如何选取”中的候选集并非指本段提到的候选解集合Candidates，而是指后文会提到的最好候选解集合BestCandidate，因为在禁忌搜索算法中，候选集是一个不断更新并逐渐向包含最优解的集合靠近的集合，而

Candidates是包含所有解的一个集合，BestCandidate才是一个变动筛选更优候选解的集合，后文将具体分析BestCandidate是如何进行选取的。 随机产生一个CityNum长的向量S0作为初始解，将S0的值赋给最优解向量BSF，并将最优值BsetL初始化为正无穷。

现在来解决问题4，终止原则怎样给出？禁忌搜索是一个启发式算法，在可接受的计算时间内，应该使所求解尽量接近最优解。本题中我们设置一个计时器和一个计数器。计数器令循环计数变量p初始值为1，规定终止参数StopL的值为80*CityNum，每执行一次循环，p的值加1，设置一个长度为p的向量ArrBestL，并将每次循环得到的最优值BestL记录在相应位置。即当p值大于80*31时，默认循环更新最优解次数足够多，我们有理由认为此时求得的最优解集已足够包含最优解，此时的最优值即为ArrBestL中的最小值，最优解为最优值对应的解。在求得最优解的同时，若计时器计算的时间已超过一个可以接受的范围，那么该程序也是不合理的。（对应代码行37到45，152到153）

现在我们需要编写一个目标值函数，求解每一个解S0的目标值，即当前解S0的距离。初始DistanV=0，用n返回s的长度（本题n=31）。初始i=1，当i

在上章禁忌搜索算法的思想中我们提到，要建立一个位置对换表格，通过比较对换后的目标值，使目标值下降，或者虽然当前目标值上升，但有可能跳出局部最优解。现在我们来建立这个对换表格。（对应代码行47到73）

建立对换表格A，初始化为Candidates行，2列的零矩阵（即31*2矩阵）。初始化一个循环变量i=1。

Setp1 : 当循环变量i不超过候选集个数CandidateNum，进行循环，执行Setp2。 Setp2 : 先从0到31随机生成一个正整数集M（a,b）。若a=b，重新执行Setp1；若a和b不相等，

向量A的第i行第1列记录a和b中较大的数，第2列记录较小的数。如果是初始循环，即i=1，定义变量isa=0，执行Setp4；否则执行Setp3。

Setp3 : 初始化循环变量j=1，当j不超过i-1时，执行判断，如果矩阵A的第i行和第j行相等，令

isa=1，跳出循环，执行Setp4；否则isa=0。

Setp4 :如果isa为0，将i值加1，返回Setp1；否则直接返回Setp1。 注释：

1、Setp2中生成M的目的是随机生成两个城市，放在一个行向量里，要求a和b不相同，是要求用于交换的两个城市不能相同。

2、变量isa的作用是判断当前新生成的用于交换的两个城市和已经生成的城市是否重复，若重复，则取消记录，跳转下一次循环。 3、循环结束后会得到一个对换表格A，共Candidates行，每行有两个随机生成的城市，且各行均不相同。

完成了对换表格的建立，我们现在解决提出的问题3，候选集合如何选取？前面我们已经分析过了，这里的候选集合是我们定义的最好候选解集合BestCandidate。先来解释下，为什么要定义BestCandidate。在上章讲述的禁忌搜索算法的思想中，候选解集合的选取可以大到全部邻域集合本身，使得计算量增加但是比较的范围增大；也可以小到只有一个元素，使计算量减小但是可比较的范围也减小。在本章的问题中，我们将候选解集合Candidates定义为此时全部候选解的集合，但由于数据较多，计算量和计算时间过大。因此，我们需要选择一种合理的方式从Candidates中选择出合适数量的优质解组成集合BestCandidate。那么我们采用什么方法呢？本题中的方法是：先用Candidates中的全部候选解逐个调用对换表格A中的数据进行交换，将得到的解填入BestCandidate中，当BestCandidate中已满时，将后来的解顺次刷新之前较差的解，从而得到最好候选解集合BestCandidate。下面我们来实现这个过程：（对应代码行74到107）

我们将最好候选解个数BestCandidateNum设为100，即保留前100个最好候选解。将最好候选解集合BestCandidate初始化为BestCandidateNum行，4列的矩阵（即100*4矩阵）。

初始化目标值列F为零列向量，共BestCandidateNum列。

Setp1 : 初始化循环变量i=1，当i不超过BestCandidateNum时，执行循环。把候选解集

Candidates中的第i行放入当前解S0中，将候选解集的第i行第A(i,1)位置和A(I,2)位置交换（即将交换表格A中第i行的a和b值交换），调用函数Fun计算当前候选解集的第i行对应解的目标值。如果i<=BestCandidateNum，执行Setp2，否则执行Setp3。 Setp2 : 将此时的候选解填入BestCandidate中，第1列记录序号i，第2列记录目标值F(i)，第3、

4列记录当前交换的位置a和b，如下表，返回Setp1。 i 1 2 ... F( i ) F(1) F(2) ... a -> A(i,1) A(1,1) A(2,1) ... b -> A(i,2) A(1,2) A(2,2) ... Setp3 : 初始化循环变量j=1，当j不超过BestCandidateNum时，执行判断，如果当前候选解集

合的第i行对应解的目标值

Setp4 : 将BestCandidate表中第1列更新为i值，第2列更新为此时的F（i）值，第3列更

新为a值，第4列更新为b值。返回Setp1。 注释： Setp1中的判断表示，当BestCandidateNum未填满时，执行Setp2，将候选解填入BestCandidate；填满时执行Setp3，比较当前候选解的目标值和表中已有候选解的目标值，若更优则更新。

现在禁忌搜索算法中候选解集合BestCandidate建立完成，我们要通过循环开始求解最优解。首先将BestCandidate中的解按照目标函数的值从小到大排序。逐个比较BestCandidate中解的目标函数值和最优值BestL的大小，若当前解目标函数值更小，就刷新最优解；若BestL更小，就继续循环，直到满足计数器的计数变量p不小于终止参数StopL，最后，建立向量ArrBestL(p)，并将当前一次计数循环中最优值记录到ArrBestL向量的第p个位置。同时，每次循环后将禁忌表中所有非零的位置都减一，并将当次循环已执行过交换的两个城市计入禁忌表TabuList。下面我们来实现这个过程：（对应代码行105到153）

Setp1 : 执行判断，如果BestCandidate(1,2)

同时通过前述序号i追溯S0为Candidates(BestCandidate(1,1),:)对应的解，刷新最优值BSF为S0，执行Setp2；否则执行Setp6。

Setp2 : 初始化循环变量m=1，当m不超过CityNum时，执行Setp3；否则执行Setp5。

Setp3 : 初始化循环变量n=1，当n不超过CityNum时，执行Setp4；否则n值加1，返回Setp2。 Setp4 : 执行判断，如果禁忌表TabuList不为空，就将TabuList中每一位元素值减1，n值加1，

返回Setp3循环；否则直接返回Setp3。 Setp5 : 将当次循环已执行过交换的两个城市计入禁忌表TabuList，并将记录值TabuLength。 Setp6 : 初始化循环变量i=1，当i不超过BestCandidateNum时，执行判断，如果当前行的兑换

城市并未出现在禁忌表中，通过前述序号i追溯S0为Candidates(BestCandidate(1,1),:)对应的解。执行Setp2；否则i值加1，返回Setp6执行循环。 注释：

1、首先判断BestCandidate中解的目标函数值和最优值BestL的大小，若BestCandidate小，就从Setp1执行，更新最优值和最优解；否则从Setp6执行，期待跳出局部最优解，得到更优值。

2、Setp1中通过最好候选解集合BestCandidate第1列来取得序号i值，追溯到候选解集合Candidates中，从而得到当前最优值对应的最优解。

此时，计数器已经完成了一次计数，ArrBestL(p)已经记录了当前本次计数的最优值。接

下来返回代码第40行，判断循环计数变量p是否达到停止参数StopL，若未达到，则继续执行上述循环内容，从而求得更接近于最优值的解。

到这里，这个TSP问题我们已经基本解决了。现在我们来分析一下问题5，如何利用更多的信息？在算法中通过记录其他信息，如当前最好解，一个被禁对象（交换）被禁的次数，评价值的大小等，来提高算法的效率。在上述过程中，我们首先建立了一个能够容纳所有解的候选解集合Candidates，并通过一定的算法从中选择出最优质的100个解组成最好候选解集合BestCandidate。在这个过程中，我们事实上是用到了全部的解进行筛选，对于给出的信息利用率很高。同时我们建立了对换表格A来记录用于交换的两个城市，由于每两个城市都是随机生成的且数量足够多，因此，我们可以认为我们选取的信息足够完全，能非常接近最优解。之后我们还建立了禁忌表TabuList，在每次循环后都将当次经过交换的两个城市计入表格，并合理设置了禁忌长度，从而使循环避免了多次出现重复的结果，在循环次数一定的情况下，有效循环次数增加，我们可以认为有效利用的信息更多，算法效率更高。

最后，我们来分析一下这个TSP问题结果的输出。首先我们肯定需要输出最优解和最优值，但由于循环计数次数较多，完整循环到终止参数StopL次需要的时间较长，我们可以在输出的时候增加一个暂停键，使循环计数终止在任何需要的时候，输出循环次数，并输出当前的最优值和最优解。同时为了方便比较这个禁忌搜索算法的运算结果和运算效率，我们希望在停止循并环输出最优结果后，进行一个比较，即展示出从最初随机产生一个当前解到循环计数结束，最优值的变化曲线。现在我们就来完成这个作图：（对应代码行155到176） 设置一个循环变量i，当i小于城市数目CityNum时，循环输出绘图