干货 | 到底是什么算法,能让人们如此绝望?

通俗篇

先来讲个故事

从前有座山

山里呢,有座庙

庙里有个老和尚和小和尚

老和尚派小和尚上山去化斋.......

(等等,小编,你是要跑火车吗...)

.......

好吧,其实小编是想借小和尚的故事

来对禁忌搜索进行一个形象地说明

一起来看小和尚的票圈吧!

票圈一

爬山(Hill-climbing)算法

3月1日

今天的任务是去给山顶的人家化斋,在爬山算法的帮助下,终于顺利爬到了最高点!阿弥陀佛~~⬇⬇⬇

图中小人0为当前所在位置(算法初始解);

在二维空间中,他可选择向左一步或向右一步(小红人1、2,PS:邻域),因为2的高度大于1,故他选择向右挪动(邻域选择);

持续该过程(算法迭代),他将到达小人3的位置,此时向左或向右,都无法进一步变高,故认定已到最高点,停止攀登(算法最优解)。

票圈二

爬山(Hill-climbing)算法

3月2日

化斋任务第一阶段结束~继续前行,下一个任务是去给..隔壁山顶的人家化斋

可是,我在半山坡的地方使用爬山算法,怎么每次都会回到原先那户人家啊啊啊

,阿弥陀佛,谁可以告诉我是哪里出了错吗?⬇⬇⬇

由于他一直遵循Hill-climbing算法,故这次登顶的结果会和第一次(小人1)一样(算法陷入局部最优);

但站在上帝视角的小编看来,如果小和尚先下山,再上山,爬到另一座山的山顶(小人2),会到达一个更好的位置。

票圈三

禁忌搜索

3月3日

使用禁忌搜索算法后,妈妈再也不用担心我找不到人家了

阿弥陀佛~

上帝这次创建小和尚时,倒了一点禁忌搜索(Tabu Search)算法。小和尚在半山腰时想再次尝试爬山,他发现之前走的路被自己标记了“禁止通行”的路标(禁忌策略),故成功的完成了先下后上的爬山过程,达到了更高的山峰。

票圈四

禁忌搜索

3月4日

阿弥陀佛,还好有破禁准则在...不然禁忌策略用不好,一辈子别想登顶了...

设置路标的方式多种多样(禁忌策略的设置对算法效率影响很大),这里小和尚设置的标准为方向。

当小和尚从当前山顶下到半山腰(小人0),他设置了禁止左行的标记。但在半山腰向左抬头看,他发现当前山峰的左侧有一座更高的,故忽略标记(破禁准则),向左爬行,到达最高点。

此外,禁止标记也不应无限存在,以防对解空间的限制过大。一般情况下是其过一段时间(禁忌长度)后自动消失,这里我们可以理解为“折旧“,后续的篇章会带大家继续深入了解。

严肃篇

虽说小编本着

让读者通俗易懂的角度介绍

但一些概念的权威解释

大家还是需要过一遍的

这也方便对后续实际操作的篇章做准备

(该篇中介绍的概念已被处理成大家容易了解的字段)

Tabu Search主要构成要素

(1)评价函数(Evaluation Function):评价函数是用来评价邻域中的邻居、判断其优劣的衡量指标。大多数情况下,评价函数为目标函数。但自定义的形式也可存在,算法也可使用多个评价函数,以提高解的分散性(区分度)。

(2)邻域移动(Move Operator):邻域移动是进行解转移的关键,又称“算子”,影响整个算法的搜索速度。邻域移动需要根据不同的问题特点来自定义,而整个邻近解空间是由当前解通过定义的移动操作构筑的所有邻域解构成的集合。

(3)禁忌表(Tabu Table):禁忌表记录被禁止的变化,以防出现搜索循环、陷入局部最优。对其的设计中最关键的因素是禁忌对象(禁忌表限定的对象)和禁忌步长(对象的禁忌在多少次迭代后失效)。

禁忌表是禁忌搜索算法的核心,禁忌表的对象、步长及更新策略在很大程度上影响着搜索速度和解的质量。若禁忌对象不准确或者步长过小,算法避免陷入局部最优的能力会大打折扣;若禁忌表步长过大,搜索区域将会限制,好的解就可能被跳过。

(4)邻居选择策略(Neighbor Selection Strategy):选择最佳邻域移动的规则。目前最广泛采用的是“最好解优先策略”及“第一个改进解优先策略”。前者需比较所有邻域,耗时较久,但解的收敛更有效;后者在发现第一个改进解就进行转移,耗时较少,但收敛效率弱于前者,对于邻域解空间较大的问题往往比较适合。

(5)破禁准则(Aspiration Criterion):破禁准则是对于禁忌表的适度放松。当某个被禁忌的移动可得到优于未被禁忌的移动得到的最优邻域解和历史所得到的最优解时,算法应接受该移动,不受禁忌表的限制。

(6)停止规则(Stop Criterion):禁忌搜索中停止规则的设计多种多样,如最大迭代数、算法运行时间、给定数目的迭代内不能改进解或组合策略等等。

实验篇

为方便大家

更加深入的了解禁忌搜索算法

小编请来了“旅行商问题”(TSP)做代表

(若你对他感到陌生,请参考推文

干货|十分钟快速get蚁群算法(附代码)

借助实验来证实算法的强大精髓

(求TSP的内心阴影面积2333........)

实验一

“禁忌搜索算法作为邻域搜索算法的扩展,

在融入禁忌机制后对算法的影响到底有多大?”

实验的算例采用随机生成的方式,点的规模集合取{10,20,50,100,200};为避免偶然性,每种规模的算例测试5次;算子选取Swap(交换路径中的两个节点),禁忌对象选取点的二元组(将Swap涉及的节点二元组进行禁忌),设置禁忌长度为0.2*规模,初始解采用简单随机生成法,停止规则采用最大迭代数的方式,迭代数为规模的5倍。

实验结果

注:第一行表示问题规模,第二、三行分别表示两种算法在实验中表现较优的次数(求解结果相等时同时算作较优),第四行表示TS的结果优于LS的比例,计算公式为:

结论

小规模时,LS能与TS匹敌,但随着问题规模的增大,TS的搜索能力强于LS,这与其记忆功能(禁忌部分操作)防止算法陷入局部最优有关。

为了进一步证实猜想,小编选取规模为200个点时,某次实验的目标值收敛情况。

(图中横轴表示迭代次数,纵轴表示目标值。)

因实验中TS与LS的算子相同,故前期搜索趋势一样;在300次迭代后,LS已趋于平稳(陷入局部最优),但TS的目标值仍在下降。

可见:

禁忌策略大大加强了算法的搜索能力

实验二

“ 禁忌搜索的探索能力究竟有多强大? ”

作为“禁忌搜索吹”的小编设计了实验,将算法搜索的结果与问题的精确解进行比较。

实验中,点的规模集合取{10,20,50,100,200},问题的精确解通过GUROBI求解,GUROBI是现阶段公认最好的规划问题求解工具,小编在调用其接口时,融入Cutting-Plane(切平面)算法,加速精确解求解效率。TS求解中,若目标值与问题最优解一致或当前已运行时间超过GUROBI运行时间时,停止迭代,便于实验比较。

实验结果

结果显示,点规模为10时,TS得出精确解的时间小于GUROBI,随着规模不断加大,TS在等同时间内搜索的结果差于GUROBI。

一般情况下,启发式算法应具备更强大的搜索效率,这里的结果在规模>10时不能证实的原因有

①TS算法的设计过于简单

②小编对GUROBI求解的加速机制设计较强

此外,实验中发现,规模大于500时,GUROBI求解耗时非常大,此时用TS则能在规定时间内输出一个满意解。

结论

问题规模较小时,禁忌搜索能得到最优解;

问题规模较大时,禁忌搜索能在规定时间内输出满意解。

实验三

“禁忌对象对算法效率的影响”

禁忌表作为算法的核心,禁忌对象又作为禁忌表的核心,对算法效率影响较大。小编设计了两种禁忌对象,通过实验比较其效率。

实验的两组对象分别是以二元组(细粒度——Swap涉及的节点二元组)及以点的编号(粗粒度——Swap涉及的两个节点编号)作为禁忌对象的算法,其他实验环境与情景一一致。

实验结果

规模为200个点时某次实验的目标值收敛情况比较图

结论

结果显示,此次实验,算法采用细粒度的禁忌对象的搜索能力优于粗粒度,但两者的差异较情景一小,可能原因是禁忌对象的粒度较粗时,会将解空间中的优质解排除在外。

可见:

禁忌对象的选择对算法效果存在较大影响

代码篇

最棒的福利当然要放到最后!

小编将实验二的编码(Python)在这里公布给大家

# -*- coding: utf-8 -*-
"""
@author: hxw
description:
  基于TSP,使用禁忌搜索算法及gurobi进行求解,
  比较两者的结果并输出
"""
from basic_class import Instance
from tsp_gurobi import gurobi_solve
import random
import copy
import time
import cPickle as pickle
import csv
 
def tabu_solve(inst, start_time, gurobi_time,best_obj):
    #函数功能:随机生成一个输出路径(初始解)
   def initial_route():
       route = []
       unvisited = range(n)
       count = n
       while(count != 0):
           index = random.randint(0, count - 1)
           current = unvisited[index]
           route.append(current)
           unvisited.remove(current)
           count -= 1
       return route
    #函数功能:输出路径的目标值
   def cal_distance(route):
       distance = 0.0
       for i in range(n - 1):
           distance += get_edge(i, i+1, route)
       distance += get_edge(0, n-1, route)
       return distance
    #函数功能:获取两点之间的边距
   def get_edge(index_i, index_j, route):
       if(index_i == n):
           index_i = 0
       if(index_j == n):
           index_j = 0
       return edge[route[index_i]][route[index_j]]
    #函数功能:计算邻域(按Swap算子)
   def cal_neighbor(nid_i, nid_j, route):
       #i, j means the node id, and the index_i and index_j means the node'sindex in route
       index_i = route.index(nid_i)
       index_j = route.index(nid_j)
       delta = 0
       if(index_i == index_j - 1 or index_i == index_j + n - 1):
           delta += get_edge(index_i, index_j + 1, route) + get_edge(index_i - 1,index_j, route)
           delta -= get_edge(index_i - 1, index_i, route) + get_edge(index_j,index_j + 1, route)
       elif(index_i == index_j + 1 or index_j == index_i + n -1):
           delta += get_edge(index_j, index_i + 1, route) + get_edge(index_j - 1,index_i, route)
           delta -= get_edge(index_j - 1, index_j, route) + get_edge(index_i,index_i + 1, route)
       else:
           delta += get_edge(index_j, index_i - 1, route) + get_edge(index_j,index_i + 1, route)
           delta += get_edge(index_i, index_j - 1, route) + get_edge(index_i,index_j + 1, route)
           delta -= get_edge(index_i, index_i - 1, route) + get_edge(index_i,index_i + 1, route)
           delta -= get_edge(index_j, index_j - 1, route) + get_edge(index_j,index_j + 1, route)
       return delta
           
   def output_route(info, route, distance):
       print(info, ', tour:', route, ', distance:', distance)
   
   eplison = 0.000001
   iteration = 10000 #最大迭代次数
    n= inst.n
       tabu_length= int(n * 0.2) #禁忌长度——这里设置为节点数的20%
   points = inst.points
   dist = inst.dist
   edge = [([0] * n) for i in range(n)]
   for j in range(n):
       for i in range(n):
           if(i > j):
                edge[i][j] = dist.get((i,j))
           elif(i < j):
                edge[i][j] = edge[j][i]
   
   tabu_list = [([0] * n) for i in range(n)] #定于禁忌表
   
       #best用于存储搜索最优目标值,local用于存储搜索当前目标值
   best = float('inf')
   best_route = list()
   local = 0.0
   
   ini_route = initial_route()
   local = cal_distance(ini_route)
   best = min(best, local)
   
   route = copy.copy(ini_route)
   best_route = copy.copy(ini_route)
       #计算初始邻域
   neighbors = dict()
   for i in range(n):
       for j in range(i + 1, n):
           neighbors[str(i) + ',' + str(j)] = cal_neighbor(i, j, route)
   #print(neighbors)
   
       #搜索开始
   for k in range(iteration):
       sorted_neighbors = sorted(neighbors.items(), key = lambda item :item[1])
       #print('sort_neighbors', sorted_neighbors)
       nid_i = nid_j = 0
       flag = 0
       for neighbor in sorted_neighbors:
           nids = neighbor[0].split(',')
           nid_i = int(nids[0])
           nid_j = int(nids[1])
           delta = neighbor[1]
           temp_local = local + delta
           # 破禁准则
           if(temp_local < best):
                local = temp_local
                best = local
                flag = 1
           else:
                            #禁忌表数值非零时,跳过当前邻域
                if(tabu_list[nid_i][nid_j] !=0):
                    continue
                else:
                   local = temp_local
           break
       # 根据上述邻域选择的结果,更新路径(按swap交换两个节点)
       index_i = route.index(nid_i)
       index_j = route.index(nid_j)
       route.pop(index_i)
       route.insert(index_i, nid_j)
       route.pop(index_j)
        route.insert(index_j, nid_i)
       if(flag == 1):
           best_route = copy.copy(route)
       # 更新禁忌表
       for i in range(n):
           for j in range(n - i):
                if(tabu_list[i][j] != 0):
                    tabu_list[i][j] -= 1
       tabu_list[nid_i][nid_j] = tabu_length
       # 更新邻域
       for i in range(n):
           for j in range(i + 1, n):
                neighbors[str(i) + ',' +str(j)] = cal_neighbor(i, j, route)
       end_time = time.clock()
       if(end_time - start_time > gurobi_time + eplison or abs(best_obj -best) < eplison):
           break
   
       #将TS结果按字典形式返回
   result = dict()
   result['tour'] = str(best_route)
   result['cost'] = best
   return result           
 
def multy():
   node_count_list = [10, 20, 50, 100, 200] #定义测试集
   result = dict()
   for node_count in node_count_list:
       seed_value = random.randint(1, 100000) #产生随机种子数
       inst = Instance(node_count, seed_value) #生成算例
       random.seed(inst.seed_value)
           
       start_time = time.clock()
       gurobi_result = gurobi_solve(inst) #调用gurobi求解
       end_time = time.clock()
       gurobi_time = end_time - start_time
       gurobi_result['time'] = gurobi_time
                    
       start_time = time.clock()
       tabu_result = tabu_solve(inst, start_time, gurobi_time,gurobi_result['cost']) #调用tabuSearch求解
       end_time = time.clock()
       tabu_time = end_time - start_time
       tabu_result['time'] = tabu_time
                  
       result['gurobi,' + str(node_count)] = gurobi_result
       result['tabu_search,' + str(node_count)] = tabu_result
   
    #将结果用pickle及csv存储
    f= file('result/experiment_3.pkl', 'wb')
   pickle.dump(result, f, True)
   f.close()
   table = [['node_count'], ['gurobi_obj'], ['gurobi_time'], ['ts_obj'],['ts_time'], ['avg_obj_gap']]
   for node_count in node_count_list:
       table[0].append(node_count)
       gurobi_result = result['gurobi,' + str(node_count)]
       tabu_result = result['tabu_search,' + str(node_count)]
       table[1].append(gurobi_result['cost'])
       table[2].append(gurobi_result['time'])
       table[3].append(tabu_result['cost'])
       table[4].append(tabu_result['time'])
        obj_gap = (tabu_result['cost'] -gurobi_result['cost']) / gurobi_result['cost']
       table[5].append(round(obj_gap, 3))
   print(table)
    f= open('result/experiment_3.csv', 'wb')
   writer = csv.writer(f)
   for line in table:
       writer.writerow(line)
   f.close()
       
def main():
   multy()
 
if(__name__ == '__main__'):
   main()
   print('finished')
 
#%%
import math
import random
 
#Instance类的定义方式
class Instance:
   def __init__(self, n, seed_value):
       self.n = n # the count of nodes
       self.seed_value = seed_value
       random.seed(self.seed_value)
       self.points = [(random.randint(0, 100), random.randint(0, 100)) \
                for i in range(n)]  # coordinates of nodes
       self.dist = {(i, j) : math.sqrt(sum((self.points[i][k] -self.points[j][k])**2 \
                for k in range(2))) for i inrange(n) for j in range(i)} # edges between nodes
   def __str__(self):
       pass

注:

(1)介于本次推文主题与篇幅, GUROBI求解的部分暂不公布,有需求的朋友可以给我们留言,或关注公众号后续内容;

(2)编码的主要目的是展示Tabu Search的思想,故数据结构方面未做到完善,后续想亲自实验的朋友可以将Route用链表表示,并在计算领域部分实现局部刷新,会对降低求解开销帮助很大;

(3)禁忌长度、迭代次数等实验参数以及初始解的生成方式对实验结果存在影响,大家在测试时也可进一步进行优化。

结论篇

Tabu Search作为

元启发式算法

(meta-heuristic algorithm)的一种

与经典的遗传算法、蚁群算法等一样

其灵感皆源于自然规律

因此,本着哲学观念

“存在必有道理”去辅助理解

相信能更上一层楼

• end •

编辑 | 韩雄威

排版 | 周馨匀

代码 | 韩雄威

指导老师:秦时明岳


注:本推文内容转载自公众号“数据魔术师”,如需交流,请联系:

秦时明岳(professor.qin@qq.com)

韩雄威(hanxiongwei@huawei.com)

周馨匀(179505928@qq.com)

原文发布于微信公众号 - 程序猿声(ProgramDream)

原文发表时间:2019-07-21

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券