禁忌搜索算法浅析 摘要:本文介绍了禁忌搜索算法的基本思想、算法流程及其实现的伪代码。禁忌搜索算法(Tabu Search或Taboo Search,简称TS算法)是一种全局性邻域搜索算法,可以有效地解决组合优化问题,引导算法跳出局部最优解,转向全局最优解的功能。 关键词:禁忌搜索算法;组合优化;近似算法;邻域搜索 1禁忌搜索算法概述 禁忌搜索算法(Tabu Search)是由美国科罗拉多州大学的Fred Glover教授在1986年左右提出来的,是一个用来跳出局部最优的搜寻方法。在解决最优问题上,一般区分为两种方式:一种是传统的方法,另一种方法则是一些启发式搜索算法。使用传统的方法,我们必须对每一个问题都去设计一套算法,相当不方便,缺乏广泛性,优点在于我们可以证明算法的正确性,我们可以保证找到的答案是最优的;而对于启发式算法,针对不同的问题,我们可以套用同一个架构来寻找答案,在这个过程中,我们只需要设计评价函数以及如何找到下一个可能解的函数等,所以启发式算法的广泛性比较高,但相对在准确度上就不一定能够达到最优,但是在实际问题中启发式算法那有着更广泛的应用。 禁忌搜索是一种亚启发式随机搜索算法,它从一个初始可行解出发,选择一系列的特定搜索方向(移动)作为试探,选择实现让特定的目标函数值变化最多的移动。为了避免陷入局部最优解,TS搜索中采用了一种灵活的“记忆”技术,对已经进行的优化过程进行记录和选择,指导下一步的搜索方向。 TS是人工智能的一种体现,是局部领域搜索的一种扩展。禁忌搜索是在领域搜索的基础上,通过设置禁忌表来禁忌一些已经历的操作,并利用藐视准则来奖励一些优良状态,其中涉及邻域(neighborhood)、禁忌表(tabu list)、禁忌长度(tabu 1ength)、候选解(candidate)、藐视准则(candidate)等影响禁忌搜索算法性能的关键因素。迄今为止,TS算法在组合优化、生产调度、机器学习、电路设计和神经网络等领域取得了很大的成功,近年来又在函数全局优化方面得到较多的研究,并大有发展的趋势。 2禁忌搜索算法的基本思想 禁忌搜索最重要的思想是标记对应已搜索的局部最优解的一些对象,并在进一步的迭代搜索中尽量避开这些对象(而不是绝对禁止循环),从而保证对不同的有效搜索途径的探索,TS的禁忌策略尽量避免迂回搜索,它是一种确定性的局部极小突跳策略。 禁忌搜索是对局部邻域搜索的一种扩展,是一种全局逐步寻求最优算法。局部邻域搜索是基于贪婪思想持续地在当前解的邻域中进行搜索,虽然算法通用易实现,且容易理解,但搜索性能完全依赖于邻域结构和初解,尤其会陷入局部极小而无法保证全局优化型。 禁忌搜索算法中充分体现了集中和扩散两个策略,它的集中策略体现在局部搜索,即从一点出发,在这点的邻域内寻求更好的解,以达到局部最优解而结束,为了跳出局部最优解,扩散策略通过禁忌表的功能来实现。禁忌表中记下已经到达的某些信息,算法通过对禁
基于优化问题的多目标布谷鸟搜索算法
基于优化问题的多目标布谷鸟搜索算法 关键字:布谷鸟搜索、元启发式算法、多目标、最优化 摘要:在工程设计方面,很多问题都是典型的多目标问题,而且,都是复杂的非线性问题。现在我们研究的优化算法就是为了解决多目标化的问题,使得与单一目标问题的解决有明显的区别,计算结果和函数值有可能会增加多目标问题的特性。此时,元启发式算法开始显示出自己在解决多目标优化问题中的优越性。在本篇文章中,我们构造了一个新的用于解决多目标优化问题的算法——布谷鸟搜索算法。我们通过一系列的多目标检验函数对其的有效性已经做出来检验,发现它可以应用于解决结构设计等问题中去,例如:光路设计、制动器设计等。另外,我么还对该算法的主要特性和应用做了相关的分析。 1.简介 在设计问题中经常会考虑到很多多重的复杂问题,而且这些问题往往都具有很高的非线性性。在实际中,不同的目标之间往往会有分歧和冲突,有时候,实际的最优化解决方案往往不存在,而一些折中的和近似的方案往往也可以使用。除了这些挑战性和复杂性以外,设计问题还会受到不同设计目标的约束,而且还会被设计代码、设计标准、材料适应性、和可用资源的选择,以及
设计花费等所限制,甚至是关于单一目标的全局最优问题也是如此,如果设计函数有着高度的非线性性,那么全局最优解是很难达到的,而且,很多现实世界中的问题经常是NP-hard的,这就意味着没有一个行之有效的算法可以解决我们提出的问题,因此,对于一个已经提出的问题,启发式算法和科学技术与具体的学科交叉知识经常被用于其中,用来作为解决问题的向导。 另一方面,元启发算法在解决此类优化问题方面是非常有效的,而且已经在很多刊物和书籍中得以运用,与单一目标的优化问题相反的是,多目标优化问题具有典型的复杂性和困难性,在单一目标的优化问题中我们必须去找出一个最优化的解决方法,此方法在问题的解决中存在着一个单一的点,并且在此问题中不包括那些多重的、平均优化的点,对于一个多目标的优化问题,存在着名为Pareto-front的多重的复杂的优化问题,为了了解我们所不熟悉的Pareto-front问题,我们需要收集并整理很多不同的方法,从而,此计算结果将会随着近似解的变化、问题的复杂度和解决方法的多样性而有所变化甚至增加。在理论上,此类解决方法应包括问题并且应相对的有一致无分歧的分布情况,然而,还没有科学的方法可以证明这种解决方法可以在实际中得以应用。 从问题的出发点我们可以得知,算法可以在单一目标优化问题中运行的很好,但是却不能在多目标的优化问题中直接的运用,除非是在特殊的环境与条件下才可以应用。例如,使用一些
随机直接搜索优化算法NLJ 辨识算法 NLJ 优化算法是随机直接搜索优化算法的一种,它是由随机数直接搜索算法算法发展而来,可以有效地解决各种复杂的问题。因其结构简单以及收敛迅速使其在随机搜索算法中始终占有一席之地。这种算法的核心思想是利用收缩变量来缩小搜索域,找到次优解,然后再基于次优解重复上述过程直到最终获得最优解。 假设待辨识的系统模型为: 1110 1 ()(0,1,...,)n n n H s i n a s a s a s a -= =++ ++ (3.1) 其中,01,,...,n a a a 表示待辨识模型的系数值。 该算法主要有以下步骤: Step 1、初始化参数。根据辨识数据,通过手工调整模型参数大致拟合出一个初始模型,确定模型初始参数(0)k i a ,其次,确定参数搜索范围c 。()k i a j 表示参数i a 在第k 次迭代的搜索结果,0,1,...,k p =,j 表示迭代组数,0,1,...,j m =。参数的搜索范围可由设定参数初始值的倍数决定,具体规则如下: 0l i i r ca = ,当 时,1k k k i i i r ca v -=?。 (3.2) 其中,根据经验知识,c 取值为2。 Step 2、计算性能指标。选择如式(3.3)所示的输出误差指标,作为辨识性能指标式,将待辨识的参数带入系统模型,求解估计值()y t 。 0[()()]N t J y t y t ==-∑ (3.3) 其中,()y t 为t 时刻的实际数据。 Step 3、计算参数估计值。在第k 代计算参数估计参数k l a ,其中rand 是在 [0.5,0.5]-之间分布的随机数,k i a 由下式给出: 1()()k k k l i i a j a j rand r -=+? (3.4) 在第k 次迭代计算后,计算m 组性能指标,选择使得性能指标最小的参数值作为下一次迭代的初始值: 11min[(())](0)|k i k k i i J a j a a --= (3.5) Step 4、修改搜索范围。在第k 次搜索前需要根据下式(3.6)对搜索范围进行修正防止局限的搜索范围导致搜索陷入局部极值。 (3.6) 在此处引入变化率η,首先,计算判断每组参数幅值的变化率,并选择变化 3k >1k k k i i i r cr v -=
禁忌搜索算法评述(一) 摘要:工程应用中存在大量的优化问题,对优化算法的研究是目前研究的热点之一。禁忌搜索算法作为一种新兴的智能搜索算法具有模拟人类智能的记忆机制,已被广泛应用于各类优化领域并取得了理想的效果。本文介绍了禁忌搜索算法的特点、应用领域、研究进展,概述了它的算法基本流程,评述了算法设计过程中的关键要点,最后探讨了禁忌搜索算法的研究方向和发展趋势。 关键词:禁忌搜索算法;优化;禁忌表;启发式;智能算法 1引言 工程领域内存在大量的优化问题,对于优化算法的研究一直是计算机领域内的一个热点问题。优化算法主要分为启发式算法和智能随机算法。启发式算法依赖对问题性质的认识,属于局部优化算法。智能随机算法不依赖问题的性质,按一定规则搜索解空间,直到搜索到近似优解或最优解,属于全局优化算法,其代表有遗传算法、模拟退火算法、粒子群算法、禁忌搜索算法等。禁忌搜索算法(TabuSearch,TS)最早是由Glover在1986年提出,它的实质是对局部邻域搜索的一种拓展。TS算法通过模拟人类智能的记忆机制,采用禁忌策略限制搜索过程陷入局部最优来避免迂回搜索。同时引入特赦(破禁)准则来释放一些被禁忌的优良状态,以保证搜索过程的有效性和多样性。TS算法是一种具有不同于遗传和模拟退火等算法特点的智能随机算法,可以克服搜索过程易于早熟收敛的缺陷而达到全局优化1]。 迄今为止,TS算法已经广泛应用于组合优化、机器学习、生产调度、函数优化、电路设计、路由优化、投资分析和神经网络等领域,并显示出极好的研究前景2~9,11~15]。目前关于TS 的研究主要分为对TS算法过程和关键步骤的改进,用TS改进已有优化算法和应用TS相关算法求解工程优化问题三个方面。 禁忌搜索提出了一种基于智能记忆的框架,在实际实现过程中可以根据问题的性质做有针对性的设计,本文在给出禁忌搜索基本流程的基础上,对如何设计算法中的关键步骤进行了有益的总结和分析。 2禁忌搜索算法的基本流程 TS算法一般流程描述1]: (1)设定算法参数,产生初始解x,置空禁忌表。 (2)判断是否满足终止条件?若是,则结束,并输出结果;否则,继续以下步骤。 (3)利用当前解x的邻域结构产生邻域解,并从中确定若干候选解。 (4)对候选解判断是否满足藐视准则?若成立,则用满足藐视准则的最佳状态y替代x成为新的当前解,并用y对应的禁忌对象替换最早进入禁忌表的禁忌对象,同时用y替换“bestsofar”状态,然后转步骤(6);否则,继续以下步骤。 (5)判断候选解对应的各对象的禁忌情况,选择候选解集中非禁忌对象对应的最佳状态为新的当前解,同时用与之对应的禁忌对象替换最早进入禁忌表的禁忌对象。 (6)转步骤(2)。 算法可用图1所示的流程图更为直观的描述。 3禁忌搜索算法中的关键设计 3.1编码及初始解的构造 禁忌搜索算法首先要对待求解的问题进行抽象,分析问题解的形式以形成编码。禁忌搜索的过程就是在解的编码空间里找出代表最优解或近似优解的编码串。编码串的设计方式有多种策略,主要根据待解问题的特征而定。二进制编码将问题的解用一个二进制串来表示2],十进制编码将问题的解用一个十进制串来表示3],实数编码将问题的解用一个实数来表示4],在某些组合优化问题中,还经常使用混合编码5]、0-1矩阵编码等。 禁忌搜索对初始解的依赖较大,好的初始解往往会提高最终的优化效果。初始解的构造可以
基于禁忌搜索算法的车辆路径选择 摘要:本文从VRP的提出背景与求解方法出发,阐释了禁忌搜索算法的原理与影响算法性能的关键因素,进而将禁忌搜索算法的思想运用于解决车辆路径问题,在VRP问题初始解的基础上,用禁忌搜索算法优化车辆配送路线,设计出直观且策略易于理解的客户直接排列的解的表示方法,最后将该算法用C语言实现并用于求解VRP问题,测试结果表明该算法可行且解的质量较高。 关键词:车辆路径问题;禁忌搜索;邻域;禁忌表 1.引言 物流配送过程的成本构成中,运输成本占到52%之多,如何安排运输车辆的行驶路径,使得配送车辆依照最短行驶路径或最短时间费用,在满足服务时间限制、车辆容量限制、行驶里程限制等约束条件下,依次服务于每个客户后返回起点,实现总运输成本的最小化,车辆路径问题正是基于这一需求而产生的。求解车辆路径问题(Vehicle Routing Problem简记VRP)的方法分为精确算法与启发式算法,精确算法随问题规模的增大,时间复杂度与空间复杂度呈指数增长,且VRP问题属于NP-hard问题,求解比较困难,因此启发式算法成为求解VRP问题的主要方法。禁忌搜索算法是启发式算法的一种,为求解VRP提供了新的工具。本文通过一种客户直接排列的解的表示方法,设计了一种求解车辆路径问题的新的禁忌搜索算法。 因此研究车辆路径问题,就是要研究如何安排运输车辆的行驶路线,使运输车辆依照最短的行驶路径或最短的时间费用,依次服务于每个客户后返回起点,总的运输成本实现最小。 2.车辆路径问题的禁忌搜索算法 2.1 车辆路径问题的描述 车辆路径问题的研究目标是对一系列送货点或取货点,确定适当的配送车辆行驶路线,使车辆有序地通过它们,在满足一定的约束条件(如货物需求量、发送量交发货时间、车辆容量限制、行驶里程限制、时间限制等)下,达到一定的目标(如路程最短、费用最小、时间尽量少、使用车辆尽量少等)。参见下图2.1所示:其中0表示配送中心,1~8表示客户编号。 图2.1 车辆路径问题 在本文中为使得问题易于理解,将该问题描述为:有一定数量的客户,各自有不同数量的货物需求,且每个客户的位置和需求量一定,一个物流中心提供这些货物,并有一个车队负责分送货物,每台配送车辆的载重量一定,这里假设车辆的型号一致,即最大载重量和最
深度优先搜索和广度优先搜索的比较和优化 第一节比较 一、深度优先搜索的特点是: 1、从上面几个实例看出,可以用深度优先搜索的方法处理的题目是各种各样的。有的搜索深度是已知和固定的,如例题2-4,2-5,2-6;有的是未知的,如例题2-7、例题2-8;有的搜索深度是有限制的,但达到目标的深度是不定的。 但也看到,无论问题的内容和性质以及求解要求如何不同,它们的程序结构都是相同的,即都是深度优先算法(一)和深度优先算法(二)中描述的算法结构,不相同的仅仅是存储结点数据结构和产生规则以及输出要求。 2、深度优先搜索法有递归以及非递归两种设计方法。一般的,当搜索深度较小、问题递归方式比较明显时,用递归方法设计好,它可以使得程序结构更简捷易懂。当搜索深度较大时,如例题2-5、2-6。当数据量较大时,由于系统堆栈容量的限制,递归容易产生溢出,用非递归方法设计比较好。 3、深度优先搜索方法有广义和狭义两种理解。广义的理解是,只要最新产生的结点(即深度最大的结点)先进行扩展的方法,就称为深度优先搜索方法。在这种理解情况下,深度优先搜索算法有全部保留和不全部保留产生的结点的两种情况。而狭义的理解是,仅仅只保留全部产生结点的算法。本书取前一种广义的理解。不保留全部结点的算法属于一般的回溯算法范畴。保留全部结点的算法,实际上是在数据库中产生一个结点之间的搜索树,因此也属于图搜索算法的范畴。 4、不保留全部结点的深度优先搜索法,由于把扩展出的结点从数据库中弹出删除,这样,一般在数据库中存储的结点数就是深度值,因此它占用的空间较少,所以,当搜索树的结点较多,用其他方法易产生内存溢出时,深度优先搜索不失为一种有效的算法。 5、从输出结果可看出,深度优先搜索找到的第一个解并不一定是最优解。例如例题2-8得最优解为13,但第一个解却是17。 如果要求出最优解的话,一种方法将是后面要介绍的动态规划法,另一种方法是修改原算法:把原输出过程的地方改为记录过程,即记录达到当前目标的路径和相应的路程值,并与前面已记录的值进行比较,保留其中最优的,等全部搜索完成后,才把保留的最优解输出。 二、广度优先搜索法的显著特点是:
毕业设计[论文] 题目:基于人工智能的路径查找优化算法 学生姓名: Weston 学号:090171021XXX 学部(系):信息科学与技术学部 专业年级:计算机应用技术 指导教师:XXX 职称或学位: XX 2012 年 5 月 18 日
目录 摘要............................................................... II ABSTRACT ........................................................... III KEY WORDS .......................................................... III 1.前言 (1) 2.概述 (2) 2.1遗传算法优缺点 (2) 2.2遗传算法应用领域 (3) 2.3遗传算法基本流程 (3) 3.传统遗传算法解决旅行商问题 (5) 3.1常用概念 (5) 3.2基本过程 (5) 3.3关键步骤 (5) 3.4总结 (8) 4.改进后的遗传算法 (9) 4.1编码、设计遗传算子 (9) 4.2种群初始化 (9) 4.3评价 (10) 4.4选择复制 (10) 4.5交叉 (11) 4.6变异 (12) 4.7终结 (13) 5.系统设计与实现 (14) 5.1系统设计 (14) 5.2系统实现 (17) 5.3结果分析 (20) 6.总结 (21) 参考文献 (22) 致谢 (23)
基于人工智能的路径查找优化算法 摘要 旅行商是一个古老且有趣的问题它可以描述为:给定n个城市以及它们之间的距离(城市i到城市j的距离),求解从其中一个城市出发对每个城市访问,且仅访问一d ij 次,最后回到出发的城市,应当选取怎样的路线才能使其访问完所有的城市后回到初始的城市且走过的路程最短。 旅行商问题已被证明是属优化组合领域的NP难题,而且在现实中的许多问题都可以转化为旅行商问题来加以解决。解决旅行商问题最一般的方法就是枚举出所有可能的路线然后对每一条进行评估最后选取出路程最短的一条即为所求解。 解决旅行商问题的各种优化算法都是通过牺牲解的精确性来换取较少的耗时,其他一些启发式的搜索算法则依赖于特定的问题域,缺乏通用性,相比较而言遗传算法是一种通用性很好的全局搜索算法。 遗传算法GA( genetic algorithm) 最早由美国密歇根大学的John Holland 提出。具有自组织、自适应、自学习和群体进化功能有很强的解决问题的能,在许多领域都得到了应用。 遗传算法以其广泛的适应性渗透到研究与工程的各个领域,已有专门的遗传算法国际会议,每两年召开一次,如今已开了数次,发表了数千篇论文,对其基本的理论、方法和技巧做了充分的研究。今天,遗传算法的研究已成为国际学术界跨学科的热门话题之一。 关键词:人工智能;遗传算法;TSP;旅行商问题
目录 一、摘要 (2) 二、禁忌搜索简介 (2) 三、禁忌搜索的应用 (2) 1、现实情况 (2) 2、车辆路径问题的描述 (3) 3、算法思路 (3) 4、具体步骤 (3) 5、程序设计简介 (3) 6、算例分析 (4) 四、禁忌搜索算法的评述和展望 (4) 五、参考文献 (5)
禁忌搜索及应用 一、摘要 工程应用中存在大量的优化问题,对优化算法的研究是目前研究的热点之一。禁忌搜索算法作为一种新兴的智能搜索算法具有模拟人类智能的记忆机制,已被广泛应用于各类优化领域并取得了理想的效果。本文介绍了禁忌搜索算法的特点、应用领域、研究进展,概述了它的算法基本流程,评述了算法设计过程中的关键要点,最后探讨了禁忌搜索算法的研究方向和发展趋势。 二、禁忌搜索简介 禁忌搜索(Tabu Search或Taboo Search,简称TS)的思想最早由Glover(1986)提出,它是对局部领域搜索的一种扩展,是一种全局逐步寻优算法,是对人类智力过程的一种模拟。TS算法通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索,并通过藐视准则来赦免一些被禁忌的优良状态,进而保证多样化的有效探索以最终实现全局优化。相对于模拟退火和遗传算法,TS是又一种搜索特点不同的meta-heuristic算法。 迄今为止,TS算法在组合优化、生产调度、机器学习、电路设计和神经网络等领域取得了很大的成功,近年来又在函数全局优化方面得到较多的研究,并大有发展的趋势。 禁忌搜索是人工智能的一种体现,是局部领域搜索的一种扩展。禁忌搜索最重要的思想是标记对应已搜索的局部最优解的一些对象,并在进一步的迭代搜索中尽量避开这些对象(而不是绝对禁止循环),从而保证对不同的有效搜索途径的探索。禁忌搜索涉及到邻域(neighborhood)、禁忌表(tabu list)、禁忌长度(tabu length)、候选解(candidate)、藐视准则(aspiration criterion)等概念。 三、禁忌搜索的应用 禁忌搜索应用的领域多种多样,下面我们简单的介绍下基于禁忌搜索算法的车辆路径选择。 1、现实情况 物流配送过程的成本构成中,运输成本占到52%之多,如何安排运输车辆的行驶路径,使得配送车辆依照最短行驶路径或最短时间费用,在满足服务时间限制、车辆容量限制、行驶里程限制等约束条件下,依次服务于每个客户后返回起点,实现总运输成本的最小化,车辆路径问题正是基于这一需求而产生的。求解车辆路径问题(vehicle routing problem简记vrp)的方法分为精确算法与启发式算法,精确算法随问题规模的增大,时间复杂度与空间复杂度呈指数增长,且vrp问题属于np-hard问题,求解比较困难,因此启发式算法成为求解vrp问题的主要方法。禁忌搜索算法是启发式算法的一种,为求解vrp提供了新的工具。本文通过一种客户直接排列的解的表示方法,设计了一种求解车辆路径问题的新的禁忌搜索算法。 因此研究车辆路径问题,就是要研究如何安排运输车辆的行驶路线,使运输车辆依照最
经典优化算法:单纯形法、椭球算法(多项式算法),内点法、无约束的优化算法包括:最速下降法(steepest)、共轭梯度法、牛顿法(Newton Algorithm)、拟牛顿法(pseudo Newton Algorithms)、信赖域法。约束优化算法包括:拉格朗日乘子法(Augmented Lagrangian Algorithms),序列二次规划(SQP)等 现代:遗传算法、蚁群算法、模拟退火算法、禁忌搜索、粒子群算法、现代优化算法是人工智能的一个重要分支,这些算法包括禁忌搜索(tabu search)、模拟退火(simulated annealing)、遗传算法(genetic algorithms)人工神经网络(nearal networks)。 贪婪算法和局部搜索、模拟退火算法(Simulated Annealing Algorithm),人工神经网络(Artificial Neural Network),禁忌搜索(Tabu Search)相继出现。最近,演化算法(Evolutionary Algorithm), 蚁群算法(Ant Algorithms),拟人拟物算法,量子算法、混合算法 经典优化算法和启发式优化算法都是迭代算法,但是,它们又有很大区别:1.经典算法是以一个可行解为迭代的初始值,而启发式算法是以一组可行解为初始值;2.经典算法的搜索策略为确定性的,而启发式算法的搜索策略是结构化和随机化;3.经典算法大多都需要导数信息,而启发式算法仅用到目标函数值的信息;4.经典算法对函数性质有着严格要求,而启发式算对函数性质没有太大要求; 5.经典算法的计算量要比启发式算法小很多。比如,对于规模较大且函数性质比较差的优化问题,经典算法的效果不好,但一般的启发式算法的计算量太大。 优化算法的主要由搜索方向和搜索步长组成。搜索方向和搜索步长的选区决定了优化算法的搜索广度和搜索深度。经典优化算法和启发式优化算法的区别主要是由其搜索机制不同造成的。经典算法的搜索方向和搜索步长是由局部信息(如导数)决定的所以只能对局部进行有效的深度搜索,而不能进行有效广度搜索,所以经典的优化算法很难跳出局部最优。启发式优化算法,为了避免像经典优化算法那样陷入局部最优,采用了相对有效的广度搜索,不过这样做使得在问题规模较大的时候计算量难以承受。 纵观优化算法的发展,完美的算法是不存在的。我们评价算法好坏的标准: (1)算法收敛速度; (2)算法使用范围(普适性);
*)国家863计划专项课题(2007AA01Z330),江苏省科技厅高技术研究项目(BG2007022),江苏省高校自然科学基金项目(07KJB510095)。周 晖 博士研究生,副教授,主要研究方向为智能计算、计算机网络等;邵世煌 教授,博士生导师。 计算机科学2008V ol 35 10 自适应搜索优化算法*) 周 晖1,2 徐 晨1 邵世煌2 李丹美2 (南通大学电子信息学院 南通226019)1 (东华大学信息科学与技术学院 上海201620) 2 摘 要 自由搜索算法是一种新的群集智能优化算法,已经成功地应用于函数优化问题。针对该算法所存在的对参数敏感等问题,提出自适应搜索算法。通过自适应实时调整搜索半径、搜索步、灵敏度等参数,提高算法对环境的适应性、鲁棒性和在 探索!和 开发!之间的平衡能力。对典型函数的试验结果证明,新算法不仅降低了对参数的依赖性,而且成功率高、收敛速度快,能有效避免陷入局部次优。关键词 自由搜索(F S),自适应,群集智能,函数优化 Adaptive Free Search Algorithm ZH O U Hui 1,2 X U Chen 1 SH A O Shi huang 2 LI Dan mei 2 (S chool of Electronics and inform ation,Nanton g U nivers ity,Nantong 226019,C hina)1 (College of Inform ation Science and T ech nology,Donghu a University,Shanghai 201620,China)2 Abstract Free search is a novel swar m int elligence a lg or ithm.A new adaptiv e f ree sear ch algo rithm (A FS)w as pr es ented t o solve t he problem that the basic free search algo rithm is sensitive to so me parameter s.T he new alg or ithm (A FS),w hich is based o n adapt ively adjusting neig hbour space and steps,sensitiv ity ,can balance the g lobal sea rch and lo cal sea rch to impro ve A FS ?s co nv erg ence and roboutness.T he ex perimental r esults show that the new alg or ithm no t only solve the pr oblem of the dependence on parameter s but also has g reat adv antag e o f conver gence pro per ty over basic free search alg or ithm and particle sw ar m optimizatio n,and can av oid the premature converg ence pro blem effect ively.Keywords F ree sea rch (FS),A da ptability ,Sw arm intellig ence,Function optimizatio n 1 引言 群集智能(Sw arm Intellig ence)是计算智能领域的重要组成部分,作为一种新兴的演化计算技术已经成为越来越多研究者关注的焦点[1 3]。目前,群集智能的典型实现主要有两种:蚁群优化(A nt co lony optim izat ion,A CO )[4]和微粒群优化(P article sw arm o pt imizatio n,PSO)[5]。 英国学者K.P enev 和G.L ittlefair 基于 以不确定应对不确定,以无穷尽应对无穷尽!的思想,提出一种新的群集智能优化算法###自由搜索(F ree Sear ch,F S)[6]。该算法借鉴动物个体存在各异的嗅觉和机动性,提出了灵敏度和邻域搜索半径的概念,并利用蚂蚁释放信息素的机理,通过信息素和灵敏度的比较确定寻优目标,应用于函数优化,并显示出很好的性能[7] 。目前对自由搜索算法的研究不多,挖掘其寻优潜能很有意义[8]。进一步研究发现,若参数设置不当,该算法收敛速度慢、收敛精度低,甚至易于陷入局部极值区。 针对上述问题,为了提高种群对环境的适应性,本文提出自适应搜索(A daptive F ree Search,A FS)算法,对基本F S 算法做以下改进:实时调整搜索半径、搜索步和灵敏度等参数,精英保留,极值点判断与处理。新算法力图降低算法对设置参数的敏感性,提高其鲁棒性和搜索能力。 2 基本FS 算法 FS 的算法模型中,个体在其搜索半径内随机产生T 个 坐标,找出其中最佳适应度坐标并且计算其信息素,通过信息素和灵敏度的比较,确定个体的新坐标。动物个体在其邻域内的行为描述如下: x tj i =x 0j i - x tj i +2 x tj i ?random tj i (0,1) x tj i =R j ?(x i max -x i min )?r andom tj i (0,1) (1) 这里,r andom tj i (0,1)是(0,1)内均匀分布的随机数;x i max 和x i min 是第i 维变量的最大值和最小值;j 代表第j 只个体(j =1,2,%,m);R j 是第j 只个体在搜索空间邻域的搜索半径(R j &[R min ,R ma x ]);t 是搜索步(w alk )中的当前小步(t =1,2,%,T );T 是搜索步数。 搜索过程中,对目标函数的符号做如下规定:f tj =f (x tj i );f j =max (f tj ),这里f (x tj i )是一个个体完成搜索步后,信息素做标记位置的目标函数值。 信息素定义为 P j = f j max (f j ) (2) 这里,max (f j )是搜索步内所有个体的当前最佳值。 灵敏度定义为S j =S min + S j S j =(S max -S min )?r andom j (0,1) (3) 这里S min ,S max 是灵敏度的最小值和最大值,r andom j (0,1)是均匀分布的随机数。 信息素的最小值和最大值分别为P m in ,P m ax 。规定:S min =P m in ,S ma x =P max 。在一轮搜索结束后,确定个体j 的新坐标, ? 188?
搜索算法的通用优化方法 [DFS] [搜索剪枝] 在很多情况下,我们已经找到了一组比较好的解。但是计算机仍然会义无返顾地去搜索比它更“劣”的其他解,搜索到后也只能回溯。为了避免出现这种情况,我们需要灵活地去定制回溯搜索的边界。 *例题计算机网络连接 要将n(n<=30)台计算机连成网络,连接方法:去除首尾两台计算机与一台计算机相连以外,其他计算机只与两台计算机相连。连接的长度则为计算机连接的电缆的长度。 求:一种连接方式,使需要电缆的长度最短。 分析这个题目用回溯搜索来解决。但是,由于回溯搜索的搜索量比较大,达到了n!,是不可能搜索完n=30的情况的,所以,我们考虑对它进行优化: 假如目前搜索到了一组解,电缆总长度为kx,那么,如果说以后搜索到的连接方法(不一定是最终连接方法)的连接长度>=kx,那么这个方案的总长度一定不小于kx,那么,就不必要搜索下去了,直接换下一个结点继续搜索。 路径A1-A2-…An与路径An-An-1-…A1这两条路径是一个“正反”的关系,本质上是相同的,于是我们可以规定起点始的下标总是小于终点的下标 假如路径的A-B-C-D的长度 禁忌(Tabu Search)算法是一种亚启发式(meta-heuristic)随机搜索算法1,它从一个初始可行解出发,选择一系列的特定搜索方向(移动)作为试探,选择实现让特定的目标函数值变化最多的移动。为了避免陷入局部最优解,TS搜索中采用了一种灵活的“记忆”技术,对已经进行的优化过程进行记录和选择,指导下一步的搜索方向,这就是Tabu表的建立。 为了找到“全局最优解”,就不应该执着于某一个特定的区域。局部搜索的缺点就是太贪婪地对某一个局部区域以及其邻域搜索,导致一叶障目,不见泰山。禁忌搜索就是对于找到的一部分局部最优解,有意识地避开它(但不是完全隔绝),从而获得更多的搜索区间。兔子们找到了泰山,它们之中的一只就会留守在这里,其他的再去别的地方寻找。就这样,一大圈后,把找到的几个山峰一比较,珠穆朗玛峰脱颖而出。 当兔子们再寻找的时候,一般地会有意识地避开泰山,因为他们知道,这里已经找过,并且有一只兔子在那里看着了。这就是禁忌搜索 中“禁忌表(tabu list)”的含义。那只留在泰山的兔子一般不会就安家在那里了,它会在一定时间后重新回到找最高峰的大军,因为这个时候已经有了许多新的消息,泰山毕竟也有一个不错的高度,需要重新考虑,这个归队时间,在禁忌搜索里面叫做“禁忌长度(tabu length)”;如果在搜索的过程中,留守泰山的兔子还没有归队,但是找到的地方全是华北平原等比较低的地方,兔子们就不得不再次考虑选中泰山,也就是说,当一个没有兔子留守的地方优越性太突出,超过 了“best so far”的状态,就可以不顾及有没有兔子留守,都把这个地方考虑进来,这就叫“特赦准则(aspiration criterion)”。这三个概念是禁忌搜索和一般搜索准则最不同的地方,算法的优化也关键在这里。 伪码表达 procedure tabu search; begin initialize a string vc at random,clear up the tabu list; cur:=vc; repeat select a new string vn in the neighborhood of vc; if va>best_to_far then {va is a string in the tabu list} begin 从一个策略游戏谈搜索算法优化从一个策略游戏谈搜索算法优化 对于策略游戏性质的二人博弈问题,比如黑白棋,五子棋等,一般的解答方法就是搜索;但搜索算法的原理不同,其性能就大不一样。一般来说,如果我们对问题的本质把握的越深,算法的设计就会相对的复杂,但是效率会高很多。下面我们就通过一个二人游戏来谈这方面的体会。 一.问题的提出 问题:TwoFour[罗马尼亚奥林匹克,via Stroe,2002] Bessie有一个新的两人游戏:TwoFour.她有N(3=N=30) 堆球,每堆有nballs(0=nballs=4)个.球的总数为2*N. 玩这个游戏时,游戏者轮流执行一个有效移动.一个有效移动由下列动作组成: *第一,游戏者选择不同的两堆球. *第二,把一个球从一堆拿到另一堆.她可以这样做的前提是运完球后第二堆 的球数(包括新放上的球)不大于第一堆剩下的球的数目. 当没有移动可做时,游戏结束.实际上,在游戏的末尾,每堆将包含恰好两个球. 游戏的胜者'拥有'多数球堆.平局是可能的.当某堆有两个球并且是由于 某游戏者最近对它的的一次移动(不管移走还是放入)使其变为两个球的, 我们就说她'拥有'这堆球. 看看这些例子: *如果一个游戏者从有四个球的某球堆中移走一个球, 放到有一个球的某球堆中,那么它拥有了第二堆(有两个球). *如果一个游戏者从有三个球的某球堆中移走一个球, 放到有零个球的某球堆中,那么它拥有了第一堆,现在这堆有两个球. *如果一个游戏者从有三个球的某球堆中移走一个球, 放到有一个球的某球堆中,那么它拥有了这两堆(他们都有两个球). 拥有权能够变化.设想一个游戏者拥有两个球的一个球堆,如果另一个 游戏者选了一个有四个球的堆并把一个球移到此两个球的堆中, 那么这堆球谁也不属于了. 如果,在游戏的开头,存在有两个球的一些球堆,那么这些堆被平分给两个游戏者,剩余的堆则分给游戏者2. 游戏者1先移动. 你的程序必须判断,对一个初始的游戏状态,谁将获胜或者会否出现平局. 你的程序将处理G(1=G=1000)个游戏状态. 该问题要求使用不超过1.00 MB的内存. 问题名:twofour 输入格式: *行1:用空格隔开的两个整数:N和G. *行2.G+1:每行包含空格隔开的N个整数用于描述该游戏. 6.2基于均衡原理的LRP 算法设计 6.2.1基于均衡原理的LRP 算法整体流程 基于均衡原理的LRP 算法整体流程如下: step1:初始化,设置整体收敛性判断参数δ; step2:随机生成一组LRP 选址问题的解D ,求出相应的目标值F ; step3:根据上层解D ,利用Frank-Wolfe 算法(见6.2.3节)求出各客户的 货物总量Q j 及客户在各配送中心的货物均衡分配量x j i ,; step4:根据D 及x j i ,运用禁忌算法求解VRP 问题(见6.2.4节),得出各配送 中对各客户的单位货物配送费用C j i ,; step5:根据 x j i ,及公式(6-8)求出下层 x j i ,与 d i 的关系y d x j i i j i W ,,+ =; step6:将LRP 模型上层目标函数中用代替,并代入下层求得的Q j 和C j i ,,运用禁忌算法 求得新的LRP 选址规划的解'Z 及目标函数'F (见6.2.2节); step7:如果δ<-F F ' ,转step8,算法结束,D 、F 为LRP 的最终解和解值;否则 '':,:F F D D ==,转step3; step8:算法结束。 6.2.2 LRP 选址规划的禁忌算法 模型上层是基于0-1整数规划的选址问题。由于选址问题是NP-hard ,如果 用精确算法求解,对节点数目的限制将有严格的要求。本章根据模型的特点, 采用禁忌算法优化产业选址问题。 1.解的构造和初始解的生成 采用二进制编码,编码长度为潜在的配送中心地点数量N T ,对于编码中位置i ,1表示选中i 点作为厂址,0表示没有选中。对于解中任意点i ,产生随机数δ,如果N T N /≥δ,则置i 点为0,否则置1。重复以上步骤m 次,得到初始解。 2.邻域的搜索 根据本章选址问题的特点,设计了三种邻域操作,分别为自身取反、2-swap 交换和2-opt 交换。 1).自身取反。为单点操作,即选择解中i 点,对该点的值取反; 2).2-swap 交换。为双点操作,选择解中两点进行交换,其它位置的值不变。例如解001101中的2、6点被选中,则2-swap 交换后变为:011100; 3).2-opt 交换。为多点操作,选择解中两点进行交换,同时两点之间的值逆序改变。例如解001101中的2、6点被选中,则2-swap 交换后变为:010110; 模拟退火算法 模拟退火(Simulated Annealing,简称SA)是一种通用概率算法,用来在一个大的搜寻空间内找寻命题的最优解。 1、固体退火原理:将固体加温至充分高,再让其徐徐冷却,加温时,固体内部粒子随温升变为无序状,内能增大,而徐徐冷却时粒子渐趋有序,在每个温度都达到平衡态,最后在常温时达到基态,内能减为最小。根据Metropolis准则,粒子在温度T时趋于平衡的概率为e-ΔE/(kT),其中E为温度T时的内能,ΔE为其改变量,k为Boltzmann常数。 2、用固体退火模拟组合优化问题:将内能E模拟为目标函数值f,温度T演化成控制参数t,即得到解组合优化问题的模拟退火算法——由初始解i和控制参数初值t开始,对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代,并逐步衰减t值,算法终止时的当前解即为所得近似最优解,这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。 3、退火过程:冷却进度表(Cooling Schedule)控制,包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。 4、模拟退火算法的模型模拟退火算法可以分解为解空间、目标函数和初始解三部分。(1) 初始化:初始温度T(充分大),初始解状态S(是算法迭代的起点),每个T值的迭代次数L (2) 对k=1,……,L做第(3)至第6步: (3) 产生新解S′ (4) 计算增量Δt′=C(S′)-C(S),其中C(S)为评价函数 (5) 若Δt′<0则接受S′作为新的当前解,否则以概率exp(-Δt′/T)接受S′作为新的当前解. (6) 如果满足终止条件则输出当前解作为最优解,结束程序。终止条件常取为连续若干个新解都没有被接受时终止算法。 (7) T逐渐减少,且T->0,然后转第2步。(降温) 5、模拟退火算法新解的产生和接受: (1)由一个产生函数从当前解产生一个位于解空间的新解:为便于后续的计算和接受,减少算法耗时,通常选择由当前新解经过简单地变换即可产生新解的方法,如对构成新解的全部或部分元素进行置换、互换等,注意到产生新解的变换方法决定了当前新解的邻域结构,因而对冷却进度表的选取有一定的影响。 (2)计算与新解所对应的目标函数差:因为目标函数差仅由变换部分产生,所以目标函数差的计算最好按增量计算。 (3)判断新解是否被接受:判断的依据是一个接受准则,最常用的接受准则是Metropo1is 准则: 若Δt′<0则接受S′作为新的当前解S,否则以概率exp(-Δt′/T)接受S′作为新的当前解S。 (4)当新解被确定接受时,用新解代替当前解,这只需将当前解中对应于产生新解时的变换部分予以实现,同时修正目标函数值即可。此时,当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时,则在原当前解的基础上继续下一轮试验。6、算法的特点 模拟退火算法与初始值无关,算法求得的解与初始解状态S(是算法迭代的起点)无关;模拟退火算法具有渐近收敛性,已在理论上被证明是一种以概率l 收敛于全局最优解的全局优化算法;模拟退火算法具有并行性。 7、简单应用 作为模拟退火算法应用,讨论货郎担问题(Travelling Salesman Problem,简记为TSP):禁忌搜索算法摘录
从一个策略游戏谈搜索算法优化
禁忌搜索算法公式
智能优化搜索算法