禁忌搜索算法

背景知识

禁忌搜索(Tabu Search)是局部邻域搜索算法的推广，Fred Glover 在 1986 年提出这个概念，进而形成一套完整算法。

算法原理

利用禁忌搜索算法求解组合优化问题时，首先按照随机方法产生一个初始解作为当前解,然后在当前解的邻域中搜索若干个解，取其中的最好解作为新的当前解。

为了避免对已搜索过的局部最优解的重复，禁忌搜索算法使用禁忌表记录已搜索的局部最优解的历史信息，这使得算法可在一定程度上避开局部最优点，从而开辟新的搜索区域。

算法流程

第一步 选定一个初始解 xnow;令禁忌表；

第二步 若满足终止准则,转第四步; 否则,在 xnow 的邻域 N(xnow)中选出满足禁忌要求的候选集 C-N(xnow) ,转第三步；

第三步 在 C-N(xnow)中选一个评价值最好的解 xbest，令 xnow=xbest，更新禁忌表 H，转第二步；

第四步 输出计算结果，停止。

算法实例

问题：NFV 编排的通用模型

输入：1. 物理无向网络 G=(N,L)。每个物理顶点使用整数编号（1,2,…，N）表示，物理链路使用 Li,j 表示。物理节点资源设为 NR，链路带宽设为 LB。

SFC 服务请求目前就考虑一条链 S=(V,E)。表示方法同上。VNF 请求资源设为 VR，虚拟链路带宽请求设为 EB。

输出：部署结果（节点序列，该路径上的所有节点，包括未映射的节点）与其他信息。

程序流程图：