智能算法-禁忌搜索算法(2)

语言: CN / TW / HK

theme: Chinese-red

一起养成写作习惯!这是我参与「掘金日新计划 · 4 月更文挑战」的第15天,点击查看活动详情

1. 禁忌搜索算法

本文主要介绍禁忌搜索算法中关键步骤的选取。

首先简单回顾一下禁忌搜索算法的大体思路:一群兔子向要到达最高的山峰,他们从出发点(初始解)开始探索,每找一步,他们相互告知,在目前所到的最高处座上记号(禁忌),然后再商量下一步往哪里找,短时间内他们不会重复再去探索已经做了记号的地方(记号就相当于被禁忌了),就这样他们重复刚才的方式继续探索,最终找到最高峰。

该算法中”禁忌“是指:禁止重复前面的工作,相当于某个解被关进“小黑屋”了,需要等一段时间(禁忌长度)才能放出来,从而为了跳出局部最优点。

禁忌搜索算法基本介绍及实例详解请参考智能算法-禁忌搜索算法 - 掘金 (juejin.cn)

2. 关键步骤

2.1 禁忌对象的选取

禁忌对象是指禁忌表中被禁的那些变化元素,禁忌对象主要可以选择一下几种: - 解的简单变化:同样的解在一定禁忌长度内(期限)不能再出现。如$ABCDE$上一轮出现,在禁忌长度内就不能再出现$ABCDE$这个解。 - 解向量分量的变化:同样的解的变化方式不能连续出现。如解$ABCDE$通过交换$BC$得到解$ACBDE$,即交换$BC$分量的操作不能连续出现。 - 目标值变化:相同的目标值在一定禁忌长度内不能出现。如将 $X1$ 代入目标函数得到100,将 $X2$ 代入目标函数也得到100,将 $X3$ 代入目标函数也得到100,因为得到的目标值都一样,则$X1$,$X2$,$X3$在禁忌长度内需要被禁忌。

注意:解的简单变化比解的分量变化和目标值变化的受禁范围要小,可能造成计算时间的增加,但也给予了较大的搜索范围; 解分量的变化和目标值变化的禁忌范围大,减少了计算时间,可能导致陷在局部最优点(搜索的不全)。

2.2 禁忌长度的选取

禁忌长度是指禁忌的步数,通俗来讲就是关进小黑屋的期限,也就是在多少轮迭代中不能再用这个解。禁忌长度的选取主要有以下三种方式: 1. $t$可以为常数,易于实现;(t固定不变了) 2. $t$在$[tmin,tmax]$范围内,t是可以变化的数,tmin和tmax是确定的。$tmin$和$tmax$需要根据问题的规模确定,t的大小主要依据实际问题、实验和设计者的经验。(t在上下限之间变化) 3. $tmin$和$tmax$的动态选择。(上下限的大小动态调整) 禁忌长度对解的影响: - 禁忌长度过短,一旦陷入局部最优点,出现循环无法跳出(想象一下禁忌长度为0,就反复选择同一个最优解) - 禁忌长度过长,造成计算时间较大,也可能造成计算无法继续下去(相当于都被禁忌了,下一步迭代没有解可以选了)。

2.3 候选集合的确定

每一轮迭代都要进行新的探索,那将要探索的地方是哪里呢?将要探索的地方也就是候选解集。候选集主要有以下几个方式来确定: 1. 从邻域中选择若干目标值最佳的邻居入选; 2. 在邻域中的一部分邻居中选择若干目标值最佳的状态入选; 3. 随机选取。

2.4 评价函数

每一轮迭代探索了很多新的地方,那这些地方的好坏怎么判断呢?需要用评价函数来计算这个解的好坏,起到了一个“评价”的作用。评价函数选择方式从大的角度来说主要分为两种: 1. 直接评价函数,通过目标函数的运算得到评价函数; 2. 间接评价函数,构造其他评价函数替代目标函数,应反映目标函数的特性,减少计算复杂性。