禁忌搜索算法
组合优化算法系列:
现代优化算法 (二): 遗传算法 及应用举例
现代优化算法(三):禁忌搜索算法
现代优化算法(四):改进的遗传算法
现代优化算法(五): 蚁群算法
目录
1 禁忌搜索算法的相关概念
(1)邻域 (2)侯选集合
(3)禁忌对象和禁忌长度 (4)评价函数
(5)特赦规则 (6)记忆频率信息
2 模型及求解 2.1 问题(1)的求解
禁忌搜索算法的流程 2.2 问题(2)的求解
1 禁忌搜索算法的相关概念
禁忌搜索算法是组合优化算法的一种,是局部搜索算法的扩展。禁忌搜索算法是人 工智能在组合优化算法中的一个成功应用。禁忌搜索算法的特点是采用了禁忌技术。所 谓禁忌就是禁止重复前面的工作。禁忌搜索算法用一个禁忌表记录下已经到达过的局部最优点,在下一次搜索中,利用禁忌表中的信息不再或有选择地搜索这些点。 禁忌搜索算法实现的技术问题是算法的关键。禁忌搜索算法涉及侯选集合、禁忌 对象、评价函数、特赦规则、记忆频率信息等概念。
(1)邻域
在组合优化中,距离的概念通常不再适用,但是在一点附近搜索另一个下降的点仍 然是组合优化数值求解的基本思想。因此,需要重新定义邻域的概念。
(2)侯选集合
侯选集合由邻域中的邻居组成。常规的方法是从邻域中选择若干个目标值或评价 值最佳的邻居入选。
(3)禁忌对象和禁忌长度
禁忌表中的两个主要指标是禁忌对象和禁忌长度。禁忌算法中,由于我们要避免 一些操作的重复进行,就要将一些元素放到禁忌表中以禁止对这些元素进行操作,这些元素就是我们指的禁忌对象。禁忌长度是被禁对象不允许选取的迭代次数。一般是给被禁对象 x 一个数(禁忌长度) t ,要求对象 x 在 t 步迭代内被禁,在禁忌表中采用 tabu(x) = t 记忆,每迭代一步,该项指标做运算 tabu(x) = t −1,直到 tabu(x) = 0时 解禁。于是,我们可将所有元素分成两类,被禁元素和自由元素。禁忌长度t 的选取可以有多种方法,例如t = 常数,或t = [ ],其中 n 为邻域中邻居的个数;这种规则容易在算法中实现。
(4)评价函数
评价函数是侯选集合元素选取的一个评价公式,侯选集合的元素通过评价函数值 来选取。以目标函数作为评价函数是比较容易理解的。目标值是一个非常直观的指标, 但有时为了方便或易于计算,会采用其他函数来取代目标函数。
(5)特赦规则
在禁忌搜索算法的迭代过程中,会出现侯选集中的全部对象都被禁忌,或有一对 象被禁,但若解禁则其目标值将有非常大的下降情况。在这样的情况下,为了达到全局 最优,我们会让一些禁忌对象重新可选。这种方法称为特赦,相应的规则称为特赦规则。
(6)记忆频率信息
在计算的过程中,记忆一些信息对解决问题是有利的。如一个最好的目标值出现 的频率很高,这使我们有理由推测:现有参数的算法可能无法再得到更好的解。根据解 决问题的需要,我们可以记忆解集合、被禁对象组、目标值集合等的出现频率。 频率信息有助于进一步加强禁忌搜索的效率。我们可以根据频率信息动态控制禁 忌的长度。一个最佳的目标值出现的频率很高,有理由终止计算而将此值认为是最优值。
2 模型及求解
我们用禁忌搜索算法研究如下的两个问题:
(1)研究 1.2 中同样的问题。
我方有一个基地,经度和纬度为(70,40)。假设我方飞机的速度为 1000 公里/小时。 我方派一架飞机从基地出发,侦察完敌方所有目标,再返回原来的基地。在敌方每一目 标点的侦察时间不计,求该架飞机所花费的时间(假设我方飞机巡航时间可以充分长)。
(2)我方有三个基地,经度、纬度分别为(70,40),(72,45),(68,48)。假设我方 所有无人侦察机的速度都为 1000 公里/小时。三个基地各派出一架飞机侦察敌方目标, 怎样划分任务,才能使时间最短,且任务比较均衡。
2.1 问题(1)的求解
求解的禁忌搜索算法描述如下: (1)解空间
(2)目标函数
目标函数为侦察所有目标的路径长度。我们要求
(3)候选集合
如果要考虑当前解的全部二邻域(或三邻域)的邻居,将面临着太大的工作量。 因此我们用随机选取的方法每次选取50个邻居组成的集合作为侯选集合。而将省下的 时间作更多次搜索,这样做同样可以保证较高的精确度,同时可以大大提高算法的效率。
(4)禁忌长度及禁忌对象
我们把禁忌表设计成一个循环队列,初始化禁忌表 H = Φ 。从候选集合C 中选出 一个向量 x ,如果 x ∉ H ,并且 H 不满,则把向量 x 添加到禁忌表中;如果 H 已满, 则最早进入禁忌表的向量出列,向量 x 进入到出列的位置。
(5)评价函数
可以用目标函数作为评价函数,但是这样每选取一个新的路径都得去计算总时间, 计算量比较大。对于上述二邻域中的邻居作为侯选集合,每一个新路径中只有两条边发 生了变化,因此将目标函数的差值作为评价函数可以极大地提高算法的效率。评价函数 取为
禁忌搜索算法的流程
禁忌搜索算法的流程如下:
利用 Matlab 程序求得,我们的巡航时间大约在 41 小时左右,其中的一个巡航路径 如下图所示
2.2 问题(2)的求解
对于这个问题,我们的基本想法是,先根据敌方基地的分布特点将敌方的基地大体 划分在三个区域之内,并使三架侦察机分别对这三个区域的敌军基地进行侦察,求取各 自的最短时间。然后对任务不均衡区域之中的点做适当调整。 我们解决问题的步骤如下:
组合优化算法系列:
现代优化算法 (一):模拟退火算法 及应用举例
现代优化算法 (二): 遗传算法 及应用举例
现代优化算法(三):禁忌搜索算法
现代优化算法(四):改进的遗传算法
现代优化算法(五): 蚁群算法
胖达: 写的真好ε=ε=ε=(#>д<)ノ
weixin_69906578: 你好,我是一名研一的学生目前刚开始研究风险评估方向,像发于此相关论文,我目前是做的调查问卷做的关于一些风险因素的打分,问卷回收之后我不知道要怎么处理这个数据进一步才能做模糊集理论,所以发这个私信请问一下。
m0_74812827: 我觉得也是,按照他那么算应该是不包括教练在内的20个学员
2301_79721857: y有除了01还有限制条件吗
m0_74954978: 我现在问还能瞅见吗,哈哈哈,我看好多论文用综合得分,我做课设的时候就被老师说不能这样,但是搞毕业论文搜到的资料全是这样计算,头真的大