当前位置：文档之家› 智能优化算法求解TSP问题

智能优化算法求解TSP问题

第21卷第3期

V o l .21N o.3

　控　制　与　决　策

Con trol and D ecision

2006年3月

　M ar .2006

收稿日期:2005204225;修回日期:2005208215.

基金项目:国家863高技术研究发展计划基金项目(2003AA 1Z 2610).

作者简介:高海昌(1978—),男,江苏徐州人,博士生,从事智能优化算法、软件自动化测试的研究;冯博琴(1942—),

男,浙江温州人,教授,博士生导师,从事智能网络的研究.

文章编号:100120920(2006)0320241207

智能优化算法求解TSP 问题

高海昌a ,冯博琴a ,朱　利b

(西安交通大学a .电子与信息工程学院,b .软件学院,西安710049)

摘　要:T SP (旅行商)问题代表组合优化问题,具有很强的工程背景和实际应用价值,但至今尚未找到非常有效的

求解方法.为此,讨论了最近研究比较热门的使用各种智能优化算法(蚁群算法、遗传算法、模拟退火算法、禁忌搜索算法、Hopfield 神经网络、粒子群优化算法、免疫算法等)求解T SP 问题的研究进展,指出了各种方法的优缺点和改进策略.最后总结并提出了智能优化算法求解T SP 问题的未来研究方向和建议.

关键词:旅行商问题;蚁群算法;遗传算法;模拟退火算法;禁忌搜索算法;粒子群优化算法中图分类号:T P 301 文献标识码:A

Rev iews of the M eta -heur istic A lgor ith m s for TSP

GA O H a i 2chang a

,F EN G B o 2qin a

,ZH U L i

(a .Schoo l of E lectron ics and Info rm ati on Engineering ,b .Schoo l of Softw are ,X i’an J iao tong U n iversity ,X i’an 710049,Ch ina .Co rresponden t :GAO H ai 2chang ,E 2m ail :gaohaich @gm ail

.com )Abstract :T raveling sales m an p rob lem (T SP )is the rep resen tati on of a k ind of com b inati on op ti m izati on p rob lem s ,po ssessing a strong engineering background and p ractical app licati on value .How ever ,there is no effective co rre 2sponding so lu ti on to it .A i m at that ,the research and app licati on of the mo st popu lar m eta 2heu ristic m ethods such as an t co lony algo rithm ,genetic algo rithm ,si m u lated annealing ,tabu search ,hopfield neu ral netw o rk ,particle s w arm op ti m izati on and i m m une algo rithm ,etc .are review ed .T he advan tages and disadvan tages of each m ethod and the i m p rovem en t strategies are discu ssed .T he fu tu re research directi on and suggesti on are also given .

Key words :T SP ;A n t co lony algo rithm ;Genetic algo rithm ;Si m u lated annealing ;T abu search ;Particle s w arm op 2ti m izati on

1　引言

T SP (旅行商)问题已经被证明是一个N P 2hard 问题[1],即在P ≠N P 的假设下,找不到一个多

项式时间算法来求解其最优解.T SP 问题易于陈述但难于求解,自1932年提出以来,已引起许多学者的兴趣,但至今尚未找到非常有效的求解方法.

由于T SP 问题代表一类组合优化问题,在实际工程中有许多应用,如计算机联网、电子地图、交通诱导、电气布线、VL S I 单元布局、A TM 分组交换网等.鉴于其重要的工程与理论价值,T SP 常作为算法性能研究的典型算例.求其最优解的代价是指数级的,因此对其近似解的研究一直是算法设计的一

个重要课题.

2　TSP 问题的定义和求解方法分类

2.1　TSP 问题的定义

T SP 是典型的组合优化问题[2],给定n 个城市

以及各城市之间的距离,要求找到一条遍历所有城

市且每个城市只被访问一次的路线,并使得总路线距离最短,或表述为在有n 个结点的完全图中找出最短的H am ilton 回路.其数学描述为:设有一个城市集合C =(c 1,c 2,…,c n ),其中每对城市之间的距离d (c i ,c j )∈R +,求一对经过C 中每个城市一次的路线(c Π1,c Π2,…,c Πn ),使

m in

∑

n -1

i =1

d (c Πi ,c Π(i +1))+d (c Πn ,c Π1),

(1)

其中Π1,Π2,…,Πn 是(1,2,…,n )的一个置换.2.2　求解方法分类

大体上可以将现有的求解T SP 问题的优化算法分为两种类型[3]:与问题本身特征相关的局部启发式搜索算法和独立于问题的经典优化算法.常见的局部启发式优化算法有22op t,32op t 和L in

Kern ighan (L K )[4]等.这类优化算法对于寻找T SP 的局部最优解非常有效,通常在很短的时间内计算出上百个城市的T SP 问题的高质量的解.但是,这些算法过于依赖问题本身特征,易陷入局部最优解.随着人工智能的发展,出现了许多独立于问题的智能优化算法,如蚁群算法(A CA )[5],遗传算法(GA )

[6]

,模拟退火(SA )

[7]

,禁忌搜索(T S )

[8]

,神经

网络(NN )[9]

,粒子群优化算法(PSO )[10]

,免疫算法(I A )[11]等,通过模拟或解释某些自然现象或过程而得以发展,为解决复杂问题提供了新的思路和方法.在优化领域,由于这些算法构造的直观性和自然机理,通常被称为智能优化算法或现代启发式算法[12].这类算法虽然不能保证在有限的时间内获得最优解,但选择充分多个解验证后,错误概率可降到可以接受的程度.

3　智能优化求解方法

3.1　蚁群算法

蚁群算法(A n t co lony algo rithm ,A CA )是一种

比较新的模拟进化算法,由意大利学者Do rigo 等人首先提出[5],他们称之为蚁群系统,并用该方法求解T SP 问题,取得了较好的实验效果.受其影响,蚁群

系统模型逐渐引起其他学者的注意,并将A CA 用于指派问题、频率分配问题、电力系统故障诊断等N P 2Com p lete 问题.3.1.1　ACA 描述

以平面上的n 个城市的T SP 问题为例来说明基本A CA 模型.设m 是蚁群中蚂蚁的数量,d ij (i ,j =1,2,…,n )表示城市i 与城市j 之间的距离,Σij (t )表

示t 时刻在城市i 与城市j 连线上的信息素的浓度.初始时刻,各条路径上的信息素的浓度相同,设Σij (0)=C ,C 为常数.蚂蚁k (k =1,2,…,m )在运动过程中,根据各条路径上的信息素的浓度决定转移方向,P k ij (t )表示在t 时刻蚂蚁k 从城市i 转移到城市j 的概率,其计算公式为

P k

ij =ΣΑij (t )ΓΒ

ij (t )

∑s ∈all ow ed k

ΣΑis (t )ΓΒ

is (t ),j |tabu k ;

0,其他.

(2)

式中:tabu k (k =1,2,…,m )表示蚂蚁k 已经走过城市的集合,开始时tabu k 中只有一个元素,即蚂蚁k 的出发城市,随着进化的进行,tabu k 中的元素不断增加;allow ed k ={0,1,…,0-1}-tabu k 表示蚂蚁k 下一步允许选择的城市;Γij 是能见度,取路径(i ,j )长度的倒数;Α,Β调节信息素浓度Σ与能见度Γ的相对重要程度.

随着时间的推移,以前留在各条路径上的信息素逐渐消失,用参数1-Θ表示信息素的挥发程度.经过w 个时刻,蚂蚁完成一次循环,各路径上的信息素的浓度可根据如下公式进行调整:

Σij (t +w )=Θ Σij (t )+?Σij ,Θ∈(0,1);

(3)?Σij =

∑m

k =1

?Σk ij

(4)

式中:?Σk ij

表示第k 只蚂蚁在本次循环中留在路径(i ,j )上的信息素的浓度;?Σij 表示本次循环所有蚂蚁在路径(i ,j )上所释放的信息素浓度之和.3.1.2　ACA 的优缺点与改进

A CA 不仅利用了正反馈原理,在一定程度上可

以加快进化过程,而且是一种本质并行的算法,个体之间不断进行信息交流和传递,有利于发现较好解.单个个体容易收敛于局部最优,但多个个体通过合作,很快收敛于解空间的某一子集,有利于对解空间的进一步探索,从而不易陷入局部最优.但是A CA 也具有速度慢、易陷入局部最优等缺点.蚁群中多个个体的运动是随机的,当群体规模较大时,要找出一条较好的路径需要较长的搜索时间.

许多学者对基本A CA 进行了改进,Do rigo 等提

出了称为A n t 2Q System 的更一般的蚁群算法[13]

,每次让信息量以最大的路径、较大的概率被选中,以充分利用学习机制,强化最优信息的反馈.为了克服在A n t 2Q 中可能出现的停滞现象,Stu tzle 等提出了M A X 2M I N 蚁群系统,允许各个路径上的信息量在

一个限定的范围内变化[14].Gam bardella 等提出了一种混合型蚁群算法HA S [15],在每次循环中蚂蚁建立各自的解后,再以各自的解为起点,用某种局部搜索算法求局部最优解,作为相应蚂蚁的解,从而可以迅速提高解的质量.Gu tjah r 提出了一种以图为基础构建的蚁群系统框架来解决组合优化问题[16],在一定的条件下,每次迭代所得到的解能以近似于1的概率向最优解收敛.T sai 等提出了一种求解大规模T SP 问题的基于蚂蚁进化规则的算法[17].在国内,

吴庆洪等受遗传算法中变异算子的启发,提出了一

种采用逆转变异方式的具有变异特征的A CA [18],充分利用了22op t 简洁高效的特点,具有较快的收敛

42控制与决策

第21卷

速度.张纪会等提出了自适应A CA[19],采用确定性选择与随机选择相结合的策略,在搜索过程中动态调整选择的概率,实现了选择概率的自适应,提高了算法的速度和性能.吴斌等采用基于A CA的分段求解算法[20],提高了蚂蚁搜索的速度,为A CA的并行化奠定了基础.

作者认为,在求解大规模T SP问题时,算法会遇到搜索速度过慢的问题.虽然国内外一些学者对改进搜索速度进行了一些努力,但整体而言这些工作还不够完善,尚有待从理论上进行证明和实践的检验.

3.2　遗传算法

遗传算法(GA)的概念是由Ho lland[6]于1973年受生物进化论的启发而首次提出的.它是一种通过模拟生物界自然选择和遗传机制的随机搜索算法.GA对T SP效果比较明显.根据T SP的目的,只是求最短路径,而传统解法(如贪心法)则非常在意得到路径的过程.遗传算法直接将目标指向距离最短(因是N PC问题,只能是距离满意),因此能较快地得到问题的解答.

3.2.1　GA的描述

GA是一种比较通用的优化算法,编码技术和遗传操作比较简单,主要操作有选择、交叉和变异.以n个城市的一种排列作为一条染色体,随机构造若干条染色体构成初始种群;然后根据适应度进行优胜劣汰的选择,

代;根据一定的交叉算子和变异算子进行交叉和变异[21].以一定的迭代次数或某个到达条件作为算法终止的条件.

3.2.2　GA的优缺点与改进

GA的优点是将问题参数编码成染色体后进行优化,而不针对参数本身,从而不受函数约束条件的限制;搜索过程从问题解的一个集合开始,而不是单个个体,具有隐含并行搜索特性,可大大减少陷入局部最小的可能.GA的主要缺点是对于结构复杂的组合优化问题,搜索空间大,搜索时间比较长,往往会出现早熟收敛的情况;对初始种群很敏感,初始种群的选择常常直接影响解的质量和算法效率.

Go ldberg等首次应用GA求解T SP问题[22,23],提出了3种交叉方法:部分匹配交叉(PM X),顺序交叉(O X)和环交叉(CX).这3种交叉方法已广泛应用于自然数编码的GA中[24].实际应用中发现这几种交叉方法存在收敛速度慢而且效果不理想,为此文献[25]提出了贪婪选择交叉算子(GSX).这种方法对于对称的T SP问题效果较好,而对于非对称的T SP问题则效果不理想.文献[26]提出2种新的启发式方法,该方法对于对称和非对称T SP问题都具有较好的性能.杨辉等[27]根据最小生成树(M ST)的概念及其在T SP问题中的应用,由M ST 建立T SP问题的基因库,保存最优希望成为最优解的边,提出了一种将建立基因库(Ge)与遗传算法相结合的新算法(Ge.GA).这种基因库的思想有些类似于文献[28]提出的免疫算法,从本质上讲都是通过提取、注射疫苗来保存好的基因片段.为了使GA 能有效处理多峰函数优化问题,Cavicch i o于1970年率先在GA中引入了基于预选择机制的小生境技术;1975年,D eJong一般化了Cavicch i o的预选择机制,提出了一种称作排挤机制的小生境技术[29]; 1987年,Go ldberg提出了一种基于共享机制的小生境技术[30].这3种小生境技术对保证解的多样性无疑是有效的,提高了GA进行多峰函数优化时获得最优解的概率.

作者认为,针对GA的缺点,将GA与一些局部启发式算法相结合是一种比较有希望的做法,可以有效地提高求解大型T SP问题的质量[3].利用GA 自适应性的随机搜索性能勘探潜在的最优空间,其他启发式搜索在这些子空间内进行深入开发,在提高收敛速度和寻求全局最优之间找到一个平衡点.

3.3　模拟退火算法

模拟退火算法(SA)最早由M etropo lis于1953年提出[31].1983年,K irkpatrick等成功地将退火思想引入组合优化领域[7],提出了一种解大规模组合优化问题,特别是N P完全组合优化问题的有效近似SA.SA是局部搜索算法的扩展,从理论上讲,它是一个全局最优算法[32].SA是基于迭代求解策略的一种随机寻优算法,源于对固体退火过程的模拟[12],采用M etropo lis接受准则,并用一组称为冷却进度表的参数来控制算法的进程,使算法在多项式时间内给出一个近似最优解.

3.3.1　SA的描述

对于给定的T SP问题(S,f),S为所有回路集合,f为旅行回路的总长.任选初始旅行回路C′∈S 和给定初始温度T>0.进行随机热扰动,生成旅行回路C″∈N(C′),并依M etropo lis判据接受C″,即

若m in{1,exp(-f(C″)-f(C′)

)}>Γ,则C′=C″.其中:N(C′)

若在此温度T下M etropo lis迭代过程已经稳定,则达到热平衡.若满足算法终止判据,即退火过程结束,则输出当前旅行回路作为最优旅行回路C op t=C′,算法结束;否则,按一定方式降低温度,即

342

第3期高海昌等:智能优化算法求解T SP问题

T=T-?T,?T>0,继续进行热扰动过程.

3.3.2　SA的优缺点与改进

迭代搜索过程以Bo ltz m ann分布概率接受目标函数的“劣化解”,所以SA突出地具有脱离局域最优陷阱的能力,而且具有高效、鲁棒、通用、灵活的优点.

SA在执行过程中所遇到的一个关键问题是冷却进度表的适当选择[33,34].大多学者采用人工方式构造若干个冷却进度表;然后从中选择最好的一个.初始温度和冷却度或固定不变[33]或依赖于问题数据[35].D vis等用GA冷却进度表[34],用GA优化参数.

确定性退火求解优化问题的最优点转化为求一系列随温度变化的物理系统的自由能量函数的极小,理论上能使算法避开局部极小而得到全局极小.杨广文将确定性退火技术及聚类方法应用于T SP,给出了一种启发式求解算法[36].区别于常规改进算法的思路,高国华提出了一种新的基于空间锐化的方法[37],通过改善问题的空间结构来克服有限时操作模拟退火过程的上述缺点.

3.4　禁忌搜索算法

禁忌搜索(T S)的思想最早由Glover等于1986年首次提出[8],是一种亚启发式搜索技术.它是对局部邻域搜索的一种扩展,是一种全局逐步寻优算法. T S算法通过引入一个灵活的存储结构和相应的禁忌表来避免重复搜索,并通过藐视准则赦免一些被禁忌的优良状态.T S最重要的思想是标记对应已搜索到的局部最优解的一些对象,并在进一步的迭代搜索中尽量避开这些对象,从而保证对不同的有效搜索途径的探索,最终实现全局优化[12].

3.4.1　TS的描述

所谓禁忌就是禁止重复前面的工作.为了回避局部邻域搜索陷入局部最优的主要不足,T S用一个禁忌表来记录已经达到过的局部最优点,在下一次的搜索中,利用禁忌表中的信息不再或有选择地搜索这些点,以此来跳出局部最优点.禁忌对象、禁忌长度、邻域结构、评价函数和候选集的确定是T S设计的核心,此外还应包括特赦规则和终止规则的确定[38].

解的邻域映射为22op t,即固定起点城市,后面每两个城市进行对换,邻域中的元素个数为C2n+1;目标函数定义为巡回路径的城市间距离之和,目标函数亦作为评价函数;禁忌对象定义为目标函数所求得的目标值;禁忌长度随具体问题而定;从邻域中选最佳的禁忌长度加1个元素作为候选集;使用特赦规则(如果当前最优解未下降的次数超过给定值,则特赦禁忌表中的最优解作为下一次迭代的初始解),提高解的质量,防止出现循环;如果程序运行超过给定的迭代次数,或特赦次数超过给定的最大特赦次数,则搜索终止.

3.4.2　TS的优缺点与改进

T S对初始解的依赖性较强[12],好的初始解有助于搜索很快地达到最优解,而较坏的初始解使搜索很难或不能够达到最优解.迭代搜索过程是串行的,仅是单一状态的移动,而非并行搜索.在T S中,集中性搜索和多样性搜索是它的两个重要策略[38].其中多样性搜索尤为重要,通常的算法都是使用基于频率记忆或改变其参数来实现多样性搜索策略.在问题规模较大时,单纯应用频率记忆或改变参数来实现多样性搜索往往得不到理想的效果.近年来,许多学者对T S的改进做了大量的研究工作[39,40].另外,T S通常使用局部抖动的方法(如22op t和32op t)来构造邻域,每次只能产生一个当前解,所以尽管T S有很强的局部搜索能力,但当其陷入较深的谷中时,它很难跳出该谷.文献[41]提出了一种基于插入法的T S算法T IS,摆脱了单一利用基于频率的记忆来实现多样性搜索,使搜索程序能够很快跳出以前的搜索路径,从不同的方向继续进行搜索.

3.5　Hopf ield神经网络算法

1982年,Hopfield提出一种反馈神经网络模型(HNN)[9],并证明在高强度连接下的神经网依靠集体协同作用能自发产生计算行为.通过T SP问题的成功解决[42],开辟了神经网模型在计算机科学应用中的新天地,并受到广泛关注和应用.

3.5.1　HNN的描述

HNN是一种非线性动力学模型,它引入类似于L yap unov函数的能量函数概念,将神经网的拓扑结构(用连接权矩阵表示)与所求问题(用目标函数描述)相对应,并将其转换为神经动力学系统的演化问题.因此,使用HNN模型求解优化问题之前,必须将优化问题映射为相应的神经网.

HNN模型将T SP的合法解映射为一个置换矩阵,并给出相应的能量函数,同时将满足置换矩阵要求的能量函数最小化与T SP问题最优解相对应. Hopfield设计能量函数[42]如下:

∑

j≠i

v x i v x j+

∑

y≠x

v x i v y i+

(∑

∑

v x i-n)2+

∑

y≠x

d x y v x i(v y,i+1+v y,i-1).(5)

3.5.2　HNN的优缺点与改进

大量研究表明,基于HNN模型的优化计算易

442控制与决策第21卷

于收敛到非法解或局部极小解,以及算法对模型参数和初始条件具有很强的依赖性[43].W ilson认为HNN不能很好地求解T SP,存在严重的不稳健性[46],针对随机扰动的缺点,归一化城市坐标到(0, 1)区间,引入一个偏置到初值来改善优化性能.文献[45]提出了广义神经网,通过自适应消除回路得到全局最优.文献[46]用时变能量函数,通过自适应改变能量函数中某个参数来改善算法性能.而A iyer则通过T SP网络的动态分析修正了T SP的能量函数[47],从而获得有效解.

HNN还存在两个问题:不能学习和容易产生大量极小值.为解决极小值问题,A ck ley等将概率统计法则引入神经单元的输出取值中,提出了Bo ltz m ann机模型及其学习算法[48],但因速度太慢,难以为现实所接受.唐政在数学上对最小化问题进行过理论分析和证明,提出了登山学习算法[49].金海和针对HNN所存在的极小值问题及缺乏学习能力的问题,提出了一种学习算法[50],使网络状态能有效地从可能陷入的极小值状态中逃脱出来.

结合前面的讨论,作者认为将SA,GA和T S等随机优化算法与HNN算法合理结合,就有可能提高优化和时间性能.比如用HNN构成主算法以较快得到可行解,用SA概率性逃离局部极小进行状态转移,从而提高最终优化性能.

3.6　粒子群优化算法

粒子群优化算法(PSO)最初由Kennedy提出[10],与GA类似,是一种基于迭代的优化方法.目前已应用于多目标优化、模式识别、信号处理和决策支持等领域.PSO用于求解T SP问题是一个比较新的研究方向.

3.6.1　PS O的描述

在PSO算法中,粒子群在一个n维空间中搜索,其中的每个粒子所处的位置都表示问题的一个解.粒子通过不断地调整自己的位置X来搜索新解.每个粒子都能记住自己搜索到的最好解,记作P id,以及整个粒子群经历过的最好位置,即目前搜索到的最优解,记作P gd.每个粒子都有一个速度,记作V,即

V′id=X V id+G1 rand() (P id-X id)+ G2 rand() (P gd-X id).(6)其中:V id表示第i个粒子第d维上的速度,X为惯性权重,G1和G2为调节P id和P gd相对重要性的参数, rand()为随机生成函数.于是可以得到粒子移动的下一位置

X′id=X id+V id.(7) 粒子的移动方向由3部分决定:自己原来的速度V id,与自己最佳经历的距离(P id-X id),与群体最佳经历的距离(P gd-X id).并分别由权重系统X, G1和G2决定其相对重要性.

3.6.2　PS O的优缺点与改进

PSO优势在于简单、易于实现,没有许多参数需要调整.PSO研究处于初期,还有很多问题值得研究,如算法的收敛性、理论依据等.但从当前的应用效果看,这种模拟自然生物的新型系统的寻优思想具有光明的前景.算法与目前解决T SP问题的经典算法(如L K算法[4])相比,在解决问题的能力和速度上有一定的差距,但应用PSO算法解决T SP问题是一种崭新的尝试.

目前已提出多种PSO的改进算法[51,52],尤其是M au rice采用离散PSO算法解决T SP问题[52],取得了较好的效果.高尚提出了一种基于GA,A C和SA 思想的一种混合PSO算法来求解T SP问题[53].另外,国内外还有学者使用免疫算法(I A)进行T SP问题的求解[11,28],I A是在GA的基础上发展起来的.作为一种新的信息处理方法,与HNN和GA相比,它的研究与应用还处于起步阶段,还有待深入.

4　未来的研究方向和建议

上述7种智能优化算法只是目前求解T SP问题人们关注较多的方向,可能还有很多其他方向没有包括在内.综合考虑前面几种算法的优缺点以及T SP问题的实际工程使用,作者认为下面几个方向值得注意或具有挑战性.

(1)改进A CA的搜索速度

A CA在求解大规模T SP问题时会遇到搜索速度过慢的问题,第3.1节已给出国内外一些学者对改进搜索速度所作的努力.但从整体上看,这些工作还不够完善,还有待理论证明和实践检验.

(2)GA与局部启发式算法结合

许多研究表明,将GA与局部启发式算法相结合可以有效地提高求解大型T SP问题的质量[3],利用GA自适应性的随机搜索性,能勘探潜在的最优空间,而启发式搜索则在这些子空间内进行深入开发.这类算法在提高收敛速度与寻求全局最优之间找到了一个平衡点,所以这方面的工作是有前途的.

(3)HNN算法与其他随机优化算法结合

SA,GA和T S等随机优化算法,在全局优化性能方面有所改善,但很难确定合适的算法参数,且不良参数会导致收敛速度慢或早熟收敛等缺点.基于HNN模型的优化计算依靠神经元的协同计算功能自发产生并行计算行为,通过网络平衡态与问题最优解的对应达到优化目的.基于HNN的优化过程将优化问题映射为对应的神经网络动力系统,使目

542

第3期高海昌等:智能优化算法求解T SP问题

标函数对应于网络能量函数,网络的变化保证能量函数单调非增,因此能较快得到解,但往往收敛到局部极小.将SA与HNN算法合理结合,能提高优化和时间性能,用HNN构成主算法以较快得到可行解,用SA概率性逃离局部极小进行状态转移,从而提高最终优化性能.另外,将GA的并行搜索与HNN相结合也是一种可行的方法.此外,将混沌动态引入HNN模型,结合混沌动态的遍历性和HNN 模型的梯度下降过程也有希望构造出一种有效的优化方法.

(4)PSO和I A的深入研究

目前在求解T SP问题上,国内外使用PSO和I A算法进行研究的工作还不是很深入和系统,在这方面还有很多问题值得深入探讨和研究.改进PSO 和I A算法求解T SP问题的性能,或将PSO和I A算法与其他智能优化算法相结合,充分利用各种算法的优点,协同工作,取长补短,也是一个很有希望的研究方向.

(5)考虑T SP问题的工程背景

除从理论上和算法角度研究T SP问题外,还应强调其应用的工程背景.T SP问题的工程背景很强,随着信息高速公路的兴起和网络的发展,实际工程中往往涉及大规模T SP,动态T SP和开环T SP问题,传统算法往往无能为力,开发新算法又较为困难,利用已有算法并结合一些新的思想进行优化尚待进一步研究.对于大规模T SP问题,可以进行分区分层研究,即将大规模问题分为若干层次和区域,逐区逐层处理即可求得大规模问题的次优解.对于动态T SP问题,可以引入加权矩阵的概念,通过对各路径加权实现动态路由.此外,利用预测方法预测各路径权重,再经适当修正便可以实现动态网络,这也是解决离散时变调度问题的一个思路.对于开环问题,则可通过修改能量函数或算法结构达到目的[41].

5　结语

本文系统地叙述了目前研究比较热门的使用各种智能优化算法求解T SP问题的研究现状和进展,并指出了各种方法的优缺点与改进策略.限于篇幅,除本文介绍的7种比较常见的用于求解T SP问题的智能优化算法外,还有一些算法没有列出.本文的目的是为在这方面进行研究的学者提供一个系统的参考和建议.

参考文献(References)

[1]Garey M R,John son D S.Co m p u ters and In tractability:

A Gu id e to the T heory of N P2Co m p leteness[M].San

F rancisco:F reem an W H,1979.[2]L aw er E,L en stra J,Ronnooy K A,et al.T he T raveling

S a les m an P roble m[M].N ew Yo rk:W iley2In ternati onal Pub licati on,1985.

[3]Baraglia R,H idalgo J I,Perego R.A H yb rid H eu ristic

fo r the T raveling Salem an P rob lem[J].IE E E T rans on

E volu tiona ry Co m p u ta tion,2001,5(6):6132622.

[4]L in S,Kern ighan B W.A n Effective H eu ristic A lgo2

rithm fo r the T raveling Sales m an P rob lem[J].Op era2 tiona l R esea rch,1973,21(2):4862515.

[5]Co lo rn iA,Do rigo M,M an iezzo V.D istribu ted Op ti m iza2

ti on by A n t Co lon ies[A].P roc1st E u rop ean Conf A rti2

f icia l L if e P lans[C].F rance:E lsevier,1991:1342142.

[6]Ho lland J H.Genetic A lgo rithm s and the Op ti m al A llo2

cati on of T rials[J].S IA M J Co m p u t,1973:2(2):892 104.

[7]K irkpatrick S,Gelatt J C D,V ecch i M P.Op ti m izati on

by Si m u lated A nnealing[J].S cience,1983,220(4596): 6712680.

[8]Glover F.Fu tu re Path s fo r In teger P rogramm ing and

L ink s to A rtifical In telligence[J].Co m p u ters and Op era2 tions R esea rch,1986,13(5):5332549.

[9]Hopfield J J.N eu ral N etw o rk s and Physical System s

w ith Em ergen t Co llective Compu tati onal A b ilities[J].

P roc of the N a tiona l A cad e m y of S cience,1982,79(4): 255422558.

[10]Eberhart R,Kennedy J.A N ew Op ti m izer U sing Parti2

cles Sw arm T heo ry[A].P roc6th In t S ym p osium on M icroM ach ine and H um an S cience[C].N agoya:IEEE Service Cen ter,P iscataw ay,1995:39243.

[11]D asgup ta D,Fo rrest S.A rtif ica l Imm une S y ste m s and

T heir A pp lica tions[M].Berlin:Sp ring2V erlag,1998:

2672277.

[12]王凌.智能优化算法及其应用[M].北京:清华大学出

版社,2001.

(W ang L.In tellig en t Op ti m iz a tion A lg orithm s A pp li2 ca tions[M].Beijing:T singhaua U n iversity P ress,

2001.)

[13]Do rigo M,Gam bardella L M.A Study of Som e P roper2

ties of A n t2Q[A].P roc of the P PSN44th In t Conf on P a ra llet P roble m S olv ing f ro m N a tu re[C].Berlin:

Sp ringer V erlag,1996:6562665.

[14]Stu tzle T,Hoo s H H.M A X2M I N A n t System[J].F u2

tu re Genera tion Co m p u ter S y ste m s,2000,16(8):8892 914.

[15]Gam bardella L M,Do rigo M.A n A n t Co lony System

H yb ridized w ith a N ew L ocal Search fo r the Sequen tial

O rdering P rob lem[J].IN FORM S J on Co m p u ting,

2000,12(3):2372255.

[16]Gu tjah r W J.A Graph2based A n t System and Its Con2

vergence[J].F u tu re Genera tion Co m p u ter S y ste m,

2000,16(8):8732888.

642控制与决策第21卷

[17]T sai C F,T sai C W.A N ew A pp roach fo r So lving

L arge T raveling Sales m an P rob lem U sing Evo lu ti on

A n t R u les[J].N eu ra l N et w orks,IJ CN N2002,P roc of

the2002In t’l J oin t Conf on[C].Hono lu lu:IEEE P ress,2002,2:154021545.

[18]吴庆洪,张纪会,徐心和.具有变异特征的蚁群算法

[J].计算机研究与发展,1999,36(10):124021245.

(W u Q H,Zhang J H,Xu X H.A n A n t Co lony A lgo2 rithm w ith M u tati on Featu res[J].J of Co m p u ter R e2 sea rch and D evelopm en t,1999,36(10):124021245.) [19]张纪会,高齐圣,徐心和.自适应蚁群算法[J].控制理

论与应用,2000,17(1):123.

(Zhang J H,Gao Q S,Xu X H.A Self2adap tive A n t Co lony A lgo rithm[J].Con trol T heory and A pp lica2 tions,2000,17(1):123.)

[20]吴斌,史忠植.一种基于蚁群算法的T SP问题分段求解

算法[J].计算机学报,2001,24(12):132821333.

(W u B,Sh i Z Z.A n A n t Co lony A lgo rithm Based Par2 titi on A lgo rithm fo r T SP[J].Ch inese J Co m p u ters,

2001,24(12):132821333.)

[21]Kenneth A D ej ong.Genetic A lgo rithm s:A25Year

Perspective[A].Co m p u ta tiona l In tellig ence:Im ita ting L if e,W CC I94[C].1994:1242125.

[22]Go ldberg D E.A lleles,L oci and the T raveling Sales2

m an P rob lem[J].P roc of the1st In t Conf on Genetic

A lg orithm s and T heir A pp lica tions[C].P ittsbu rgh:

P ittsb rugh P A CarnegieM ellon U n iversity,1985:1542 159.

[23]Grefen stette J J,Gopal R,Ro s m aita B,et al.Genetic

A lgo rithm fo r T SP[J].P roc of the1st In t Conf on Ge2

netic A lg orithm s and T heir A pp lica tions[C].P itts2 bu rgh:P ittsb rugh P A Carnegie M ellon U n iversity,

1985:1602168.

[24]Go ldberg D E.Genetic A lg orithm s in S ea rch,Op ti2

m iz a tion and M ach ine L ea rn ing[M].M A:A ddison W esley R eading,1989:1210.

[25]Cheng R W,Gen M.C ro ssover on In ten sive Search and

T raveling Sales m an P rob lem[A].P roc of16th In t Conf on Co m p u ter and Ind ustria l E ng ineering[C].

Japan:N agoya In stitu te of T echno logy,1994,729:5682 579.

[26]唐立新.旅行商问题的改进遗传算法[J].东北大学学

报,1999,20(1):40242.

(T ang L X.I mp roved Genetic A lgo rithm fo r T SP[J].

J of N ortheastern U n iverstiy,1999,20(1):40242.) [27]杨辉,康立山,陈毓屏.一种基于构建基因库求解T SP

问题的遗传算法[J].计算机学报,2003,26(12):17532 1758.

(Yang H,Kang L S,Chen Y P.A Gene2based Genetic

A lgo rithm fo r T SP[J].Ch inese J of Co m p u ters,2003,

26(12):175321758.)[28]王磊,潘进,焦李成.免疫算法[J].电子学报,2000,28

(7):74278.

(W ang L,Pan J,J iao L C.T he I mm une A lgo rithm[J].

A cta E lectron ica S in ica,2000,28(7):74278.)

[29]D eJong K A.A n A na ly sis of the B ehav iou r of a C lass

of Genetic A d ap tive S y ste m s[D].M ich igan:U n iversity

of M ich igan,A nn A rbo r,1975.

[30]Go ldberg D E,R ichardson J.Genetic A lgo rithm w ith

Sharing fo r M u lti m odal Functi on Op ti m izati on[A].

P roc of the In t Conf on Genetic A lg orithm s[C].

L aw rence E rlbaum,1987:41249.

[31]M etrop lo is N,Ro senb lu th A W,Ro senbu lth M N,et

al.Equati on of State Calcu lati on s by Fast Compu ting

M ach ines[J].J of Che m ica l P hy sica,1953,21(6):

108721092.

[32]康立山,谢云,尤矢勇,等.非数值并行算法(第一册):

模拟退火算法[M].北京:科学出版社,1994:1502151.

(Kang L S,X ie Y,You S Y,et al.N onnum erica l

P a ra llel A lg orithm(P a rt ):S i m u la ted A nnea ling

A lg orithm[M].Beijing:Science P ress,1994:1502

151.)

[33]W ilhel m M R,W ard T L.So lving Q uadratic A ssign2

m en t P rob lem s by Si m u lated A nnealing[J].IE E E

T rans,1987,19(1):1072119.

[34]D vis L,R itter F.Schedu le Op ti m izati on w ith P roba2

b ilisti

c Search[A].P roc of3r

d IE E E Conf on A rtif i2

cia l In tellig ence A pp lica tions[C].O rlando,1987:2312

235.

[35]L undy M,M ess A.Convergence of an A nnealing A lgo2

rithm[J].M a the m a tica l P rog ramm ing,1986,34(1):

1112124.

[36]杨广文,郑纬民,王鼎兴,等.利用确定性退火技术的旅

行商问题求解算法[J].软件学报,1999,10(1):57259.

(Yang G W,Zheng W M,W ang D X,et al.A n A lgo2

rithm fo r T raveling Sales m an P rob lem U sing D eter2 m in istic A nnealing[J].J of S of t w a re,1999,10(1):572

59.)

[37]高国华,沈林成,常文森.求解T SP的空间锐化模拟退

火算法[J].自动化学报,1999,25(3):4252428.

(Gao G H,Shen L C,ChangW S.U sing Si m u lated A n2

nealing A lgo rithm w ith Search Space Sharp ing to

So lve T SP[J].A cta A u to m a tion S in ica,1999,25(3):

4252428.)

[38]Glover F.T abu Search:Part I[J].OR SA J on Co m2

p u ting,1989,1(3):1902206.

[39]Shane N H.A G roup T heoretic T abu S ea rch A pp roach

to the T raveling S a les m an P roble m[EB OL].h ttp: www.au.af.m il au database summ aryfile.h tm l,

2002203223.(下转第252页)

742

第3期高海昌等:智能优化算法求解T SP问题

(5):3392351.

[4]Q ian C J,L in W.P ractical O u tpu t T rack ing of N on lin2

ear System s w ith U ncon tro llab le U n stab le L inearizati on [J].IE E E T rans on A u to m a tic C ontrol,2002,47(1): 21236.

[5]W ang Q D,J ing Y W,Zhang S Y.A dap tive P ractical

O u tpu t T rack ing of a C lass of N on linear System s[J].J of C ontrol T heory and A p p lica tions,2004,2(2):1172 120.

[6]W ang Q D,J ing Y W,Zhang S Y.A dap tive and P rac2

tical O u tpu t T rack ing Con tro l of N on linear System s [J].A cta A u to m a tica S in ica,2004,30(3):3572363. [7]L in W,Q ian C J.A dap tive Con tro l of N on linearly Pa2

ram eterized System s:A N on s moo th Feedback F ram e2 w o rk[J].IE E E T rans on A u to m a tic C on trol,2002,47

(5):7572774.[8]R yan E P.A N on linear U n iversal Servom echan is m[J].

IE E E T rans on A u to m atic C on trol,1994,39(4):7532 761.

[9]Ye X D.A symp to tic R egu lati on of T i m e2varying U n2

certain N on linear System s w ith U nknow n Con tro l D i2 recti on s[J].A u to m atica,1999,35(5):9292935.

[10]N u ssbaum R D.Som e R em ark on the Con jectu re in

Param eter A dap tive Con tro l[J].S y ste m s and C on trol L etters,1983,3(4):2432246.

[11]Sam S Z,W ang G J.Robu st A dap tive T rack ing fo r

T i m e2varying U ncertain N on linear System s w ith U n2 know n Con tro l Coefficien ts[J].IE E E T rans on

A u to m a tic C on trol,2003,48(8):146321469.

[12]R yan E P.A U n iversal A dap tive Stab ilizer fo r a C lass

of N on linear System s[J].S y ste m s and C on trol L etters,

1991,16(3):2092218.

(上接第247页)

[40]M ichel G,Gilbert L,F rederic S.A T abu Search

H eu ristic fo r the U ndirected Selective T raveling Sales2

m an P rob lem[J].E u rop ean J of Op era tiona l,1998,106

(1):5392545.

[41]方永慧,刘光远,贺一,等.一种基于插入法的禁忌搜索

算法[J].西南师范大学学报,2003,28(6):8872891.

(Fang Y H,L iu G Y,H e Y,et al.A T abu Search A lgo2 rithm Based on In serti on M ethod[J].J of S ou thw est Ch ina N or m a l U n iversity,2003,28(6):8872891.) [42]Hopfield J J,T ank D W.N eu ral Compu tati on of D eci2

si on in Op ti m izati on P rob lem[J].B iol Cy bern,1985,52

(1):1412152.

[43]王凌,郑大钟.T SP及其基于Hopfield网络优化的研究

[J].控制与决策,1999,14(6):6702674.

(W ang L,Zheng D Z.Study on T SP and Op ti m izati on Based on Hopfield N eu ral N etw o rk[J].Con trol and

D ecision,1999,14(6):6702674.)

[44]W ilson V,Paw lay G S.O n the Stab ility of the T SP

P rob lem A lgo rithm of Hopfield and T ank[J].B iol Cy2 bern,1988,58(1):63270.

[45]Xu X,T saiW T.Effective N eu ral A lgo rithm s fo r the

T raveling Sales m an P rob lem[J].N eu ra l N et w ork,

1991,4(1):1932205.

[46]W ang S,T sai C M.Hopfield N ets w ith T i m e2varying

Energy Functi on fo r So lving the T raveling Sales m an P rob lem[A].In t J Conf on N eu ra l N et w orks[C].

Seattle,W ash ington,1991:8072812.

[47]A iyer S V B,N iran jan M,Fallside F.A T heo retical In2

vestigati on in to the Perfo rm ance of the HopfieldM odel

[J].IE E E T rans on N eu ra l N et w orks,1990,1(2):2042

215.

[48]A ck ley D H,H in ton G E,Sejnow sk i T J.A L earn ing

A lgo rithm fo r Bo ltz m ann M ach ines[J].Cog n itive S ci2

ence,1985,9(1):1472169.

[49]T ang Z,J in H H,M u rao K,et al.A Gradien t A scen t

L earn ing fo r Hopfield N etw o rk s[J].T rans of IE ICE

of J ap an,2000,J832A(3):3192331.

[50]金海和,陈剑,唐政,等.基于Hopfield网络的极小值问

题学习算法[J].清华大学学报,2002,42(6):7312734.

(J in H H,Chen J,T ang Z,et al.L earn ing A lgo rithm

fo r So lving L ocal M in i m um P rob lem s Based on Hop2

field N etw o rk[J].J of T sing hua U n iversity,2002,42

(6):7312734.)

[51]Sh i Y H,Eberhart R C.A M odified Particle Sw arm

Op ti m izer[A].IE E E In t Conf on E volu tiona ry Co m p u2

ta tion[C].A ncho rage,1998:69273.

[52]M au rice C lerc.D iscrete P a rticle Sw a r m Op ti m iz a tion

I llustra ted by the T raveling S a les m an P roble m[DB

OL].h ttp: www.m au https://www.doczj.com/doc/272849900.html,,2000.

[53]高尚,韩斌,吴小俊.等.求解旅行商问题的混合粒子群

优化算法[J].控制与决策,2004,19(11):128621289.

(Gao S,H an B,W u X J.et al.So lving T raveling Sales2 m an P rob lem by H yb rid Particle Sw arm Op ti m izati on

A lgo rithm[J].Con trol and D ecision,2004,19(11):

128621289.)

252控制与决策第21卷

群智能优化算法综述

现代智能优化算法课程群智能优化算法综述学生姓名：学号：班级： 2014年6月22日

摘要工程技术与科学研究中的最优化求解问题十分普遍，在求解过程中，人们创造与发现了许多优秀实用的算法。群智能算法是一种新兴的演化计算技术，已成为越来越多研究者的关注焦点，智能优化算法具有很多优点,如操作简单、收敛速度快、全局收敛性好等。群智能优化是智能优化的一个重要分支，它与人工生命，特别是进化策略以及遗传算法有着极为特殊的联系。群智能优化通过模拟社会性昆虫的各种群体行为，利用群体中个体之间的信息交互和合作实现寻优。本文综述群智能优化算法的原理、主要群智能算法介绍、应用研究及其发展前景。关键词：群智能；最优化；算法

目录摘要 (1) 1 概述 (3) 2 定义及原理 (3) 2.1 定义 (3) 2.2 群集智能算法原理 (4) 3 主要群智能算法 (4) 3.1 蚁群算法 (4) 3.2 粒子群算法 (5) 3.3 其他算法 (6) 4 应用研究 (7) 5 发展前景 (7) 6 总结 (8) 参考文献 (9)

1 概述优化是人们长久以来不断研究与探讨的一个充满活力与挑战的领域。很多实际优化问题往往存在着难解性,传统的优化方法如牛顿法、共扼梯度法、模式搜索法、单纯形法等己难以满足人们需求。因此设计高效的优化算法成为众多科研工作者的研究目标。随着人类对生物启发式计算的研究, 一些社会性动物( 如蚁群、蜂群、鸟群) 的自组织行为引起了科学家的广泛关注。这些社会性动物在漫长的进化过程中形成了一个共同的特点: 个体的行为都很简单, 但当它们一起协同工作时, 却能够“突现”出非常复杂的行为特征。基于此,人们设计了许多优化算法,例如蚁群算法、粒子群优化算法、混合蛙跳算法、人工鱼群算法,并在诸多领域得到了成功应用。目前, 群智能理论研究领域主要有两种算法: 蚁群算法(Ant Colony Optimization, ACO) 和粒子群优化算法(ParticleSwarm Optimization, PSO)。 2 定义及原理 2.1 定义群集智能优化算法源于对自然界的生物进化过程或觅食行为的模拟。它将搜索和优化过程模拟成个体的进化或觅食过程，用搜索空间中的点模拟自然界中的个体；将求解问题的目标函数度量成个体对环境的适应能力；将个体的优胜劣汰过程或觅食过程类比为搜索和优化过程中用好的可行解取代较差可行解的迭代过程。从而，形成了一种以“生成+检验”特征的迭代搜索算法，是一种求解极值问题的自适应人工智能技术。各类优化算法实质上都是建立问题的目标函数，求目标函数的最优解，因而实际工程优化问题均可转化为函数优化问题。其表达形式如下：求： ,,2,1,0)(..), (min , ,,2,1,),,,(21Lm j X g t s X f n L i x L x x X i T n i =≤== 。Ω∈X 其中， i X 为设计变量；)(X f 为被优化的目标函数；0)(≤X g j 为约束函数；Ω为设计变量的可行域。

混合群智能优化算法研究及应用

混合群智能优化算法研究及应用优化问题广泛地存在于科学研究和工程实践中。群智能优化算法是优化算法中最新的一个分支,也是最热门的发展方向。群智能优化算法是通过模拟自然界中生物间相互合作、共享信息等群体行为而建立起来的随机搜索算法,相较于经典优化算法具有结构简单、易于实现等优点。不同的群智能优化算法是模拟不同生物行为形成的,所以它们各具特点和适用场景。然而,单一的群智能优化算法均有其局限性,如搜索精度不够高、收敛速度慢、性能受参数影响较大和容易陷入局部最优等。将不同群智能优化算法有机结合,设计混合群智能优化算法是一种提高算法性能的有效方法,具有重要的研究意义。本文的主要研究内容及创新点包括以下几个方面:(1)针对单目标数值优化问题提出了一种基于跟随蜂搜索的自适应粒子群算法(Follower Bee Search Based Adapitve Particle Swarm Optimization,F-APSO)。首先在经典粒子群算法粒子飞行轨迹分析的基础上提出了一种自适应的粒子群算法(Adapitve Particle Swarm Optimization,APSO), 提高了算法在求解单峰问题时的性能。然后提出了一种针对自适应粒子群算法的稳定性分析方法,基于该方法对APSO进行了稳定性分析,给出了能够保证算法稳定的参数取值条件。接着通过引入人工蜂群算法中的跟随蜂搜索,提高了算法的开拓性,并将APSO的稳定性条件拓展到了 F-APSO中。仿真实验表明F-APSO在求解单目标数值优化问题时在解的质量和时间消耗上都具有良好表现。将F-APSO用于解决矿山生产排程优化问题,与原有生产方案相比优化后的方案在不同铁

智能优化算法

智能计算读书报告（二）智能优化算法姓名：XX 学号：XXXX 班级：XXXX 联系方式：XXXXXX

一、引言智能优化算法又称为现代启发式算法，是一种具有全局优化性能、通用性强、且适用于并行处理的算法。这种算法一般具有严密的理论依据，而不是单纯凭借专家的经验，理论上可以在一定时间内找到最优解或者近似最优解。所以，智能优化算法是一数学为基础的，用于求解各种工程问题优化解的应用科学，其应用非常广泛，在系统控制、人工智能、模式识别、生产调度、VLSI技术和计算机工程等各个方面都可以看到它的踪影。最优化的核心是模型，最优化方法也是随着模型的变化不断发展起来的，最优化问题就是在约束条件的限制下，利用优化方法达到某个优化目标的最优。线性规划、非线性规划、动态规划等优化模型使最优化方法进入飞速发展的时代。 20世纪80年代以来，涌现出了大量的智能优化算法，这些新颖的智能优化算法被提出来解决一系列的复杂实际应用问题。这些智能优化算法主要包括：遗传算法，粒子群优化算法，和声搜索算法，差分进化算法，人工神经网络、模拟退火算法等等。这些算法独特的优点和机制，引起了国内外学者的广泛重视并掀起了该领域的研究热潮，并且在很多领域得到了成功地应用。二、模拟退火算法（SA） 1. 退火和模拟退火模拟退火算法(Simulated Annealing，SA)最早的思想是由N. Metropolis 等人于1953年提出。1983 年,S. Kirkpatrick 等成功地将退火思想引入到组合优化领域。它是基于Monte-Carlo迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法从某一较高初温出发，伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。模拟退火算法是一种通用的优化算法，理论上算法具有概率的全局优化性能,目前已在工程中得到了广泛应用，诸如VLSI、生产调度、控制工程、机器学习、神经网络、信号处理等领域。模拟退火算法是通过赋予搜索过程一种时变且最终趋于零的概率突跳性，从而可有效避免陷入局部极小并最终趋于全局最优的串行结构的优化算法。模拟退火其实也是一种贪心算法，但是它的搜索过程引入了随机因素。模拟

群智能优化算法综述

现代智能优化算法课程群智能优化算法综述学生姓名: 学号: 班级: 2014年6月22日

摘要工程技术与科学研究中的最优化求解问题十分普遍,在求解过程中,人们创造与发现了许多优秀实用的算法。群智能算法就是一种新兴的演化计算技术,已成为越来越多研究者的关注焦点,智能优化算法具有很多优点,如操作简单、收敛速度快、全局收敛性好等。群智能优化就是智能优化的一个重要分支,它与人工生命,特别就是进化策略以及遗传算法有着极为特殊的联系。群智能优化通过模拟社会性昆虫的各种群体行为,利用群体中个体之间的信息交互与合作实现寻优。本文综述群智能优化算法的原理、主要群智能算法介绍、应用研究及其发展前景。关键词:群智能;最优化;算法

目录摘要 0 1 概述 (2) 2 定义及原理 (2) 2、1 定义 (2) 2、2 群集智能算法原理 (3) 3 主要群智能算法 (3) 3、1 蚁群算法 (3) 3、2 粒子群算法 (4) 3、3 其她算法 (5) 4 应用研究 (6) 5 发展前景 (6) 6 总结 (7) 参考文献 (8)

1 概述优化就是人们长久以来不断研究与探讨的一个充满活力与挑战的领域。很多实际优化问题往往存在着难解性,传统的优化方法如牛顿法、共扼梯度法、模式搜索法、单纯形法等己难以满足人们需求。因此设计高效的优化算法成为众多科研工作者的研究目标。随着人类对生物启发式计算的研究, 一些社会性动物( 如蚁群、蜂群、鸟群) 的自组织行为引起了科学家的广泛关注。这些社会性动物在漫长的进化过程中形成了一个共同的特点: 个体的行为都很简单, 但当它们一起协同工作时, 却能够“突现”出非常复杂的行为特征。基于此,人们设计了许多优化算法,例如蚁群算法、粒子群优化算法、混合蛙跳算法、人工鱼群算法,并在诸多领域得到了成功应用。目前, 群智能理论研究领域主要有两种算法: 蚁群算法(Ant Colony Optimization, ACO) 与粒子群优化算法(ParticleSwarm Optimization, PSO)。 2 定义及原理 2、1 定义群集智能优化算法源于对自然界的生物进化过程或觅食行为的模拟。它将搜索与优化过程模拟成个体的进化或觅食过程,用搜索空间中的点模拟自然界中的个体;将求解问题的目标函数度量成个体对环境的适应能力;将个体的优胜劣汰过程或觅食过程类比为搜索与优化过程中用好的可行解取代较差可行解的迭代过程。从而,形成了一种以“生成+检验”特征的迭代搜索算法,就是一种求解极值问题的自适应人工智能技术。各类优化算法实质上都就是建立问题的目标函数,求目标函数的最优解,因而实际工程优化问题均可转化为函数优化问题。其表达形式如下: 求: ,,2,1,0)(..), (min , ,,2,1,),,,(21Lm j X g t s X f n L i x L x x X i T n i =≤== 。Ω∈X 其中,i X 为设计变量;)(X f 为被优化的目标函数;0)(≤X g j 为约束函数;Ω为设计变量的可行

群体智能优化算法-群体智能总结

第十六章群体智能优化算法总结总结一下最近一段时间关于群体智能优化算法的文章，这方面的文章目前一共发表了13篇，涉及粒子群（鸟）、人工蜂群、蜘蛛猴、蚁群、布谷鸟、萤火虫群、萤火虫、蝙蝠、鱼群、蟑螂、猫群、细菌觅食和烟花算法，虽然这都是些五花八门的小东西，但也不是无规律可循，这里需要注意的是，群体智能一般是指具有生命的种群（鸟、鱼等），但也有像烟花这样的无生命个体，这里我们将所有这些个体统称为智能体，认为它们具有一定的能动性，可以在解空间中进行搜索。图1为各主要优化算法的提出时间和提出者，可以看出大多数算法诞生于2000~2010年这十年左右，随着计算机计算能力的提升，人们开始依赖于这种既能得到较优的结果又不会消耗太多计算时间的元启发式算法。图1 群体智能优化算法发展历程下面总结一下这些算法的共同点： 1、都有多个粒子，代表每种智能体； 2、每个个体通过一定的机制进行位置的变化或者移动，来对解的空间进行搜索； 3、个体之间具有一定的独立性，利用局部信息和全局信息进行交互；

4、群体在演变过程中都引入了随机数，以便进行充分地探索。其实人群也算是一种特殊的群体，只不过他不像其他的群体那样，仅仅是觅食，人作为一种高级动物，除了吃饱肚子以外，还有其他很多精神方面的需求，比如幸福度、快乐度和舒适度等等各个方面，并且人类具有的最大优势是语言沟通和学习能力，因此，基于这样的特性也可以提出基于人群的优化算法，只不过可能需要结合更多的组织行为学和行为心理学等相关的知识，对人的群集行为进行理论解释，同时可以采用更多以机器学习或人工智能为基础的高级策略，并应用于多目标优化问题。不过好像在2006年就已经有类似的算法了，至于为什么没有普及开来，可能还是人的行为太复杂了吧。对于群体智能优化方面的更新将暂时告一段落，接下来将更多的关注另一种元启发式算法-进化计算，这类算法主要是基于生物的进化理论，包括遗传算法、进化策略、进化规划等，都将在后续的内容中逐渐详细讲解。

群智能优化算法_萤火虫算法

2012年第32 期群智能算法是人们受自然界或生物界种群规律的启发，根据其原理，仿生模拟其规律而设计求解问题的算法。近几十年来，人们通过模拟自然生态系统机制以求解复杂优化问题的仿生智能算法相继被提出和研究。群智能算法有遗传算法、模拟退火算法、蚁群算法、粒子群算法等。萤火虫算法是一种新颖的仿生群智能算法，是受自然界中的萤火虫通过荧光进行信息交流这种群体行为的启发演变而来的。萤火虫算法目前有两种版本：a)由印度学者Krishnanand等人［1］提出，称为GSO(glowworm swarm optimization)；b)由剑桥学者Yang[2]提出，称为FA( firefly algorithm)。两种算法的仿生原理相同，但在具体实现方面有一定差异。本文分析了萤火虫算法的仿生原理，并从数学角度对两种版本的算法实现优化过程进行定义。 1．GSO算法 1.1算法的数学描述与分析在基本GSO中，把n个萤火虫个体随机分布在一个D维目标搜索空间中，每个萤火虫都携带了萤光素li。萤火虫个体都发出一定量的萤光相互影响周围的萤火虫个体，并且拥有各自的决策域r i d(0＜r i d ≤r s)。萤火虫个体的萤光素大小与自己所在位置的目标函数有关，荧光素越大，越亮的萤火虫表示它所在的位置越好，即有较好的目标值,反之则目标值较差。决策域半径的大小会受到邻域内个体的数量的影响，邻域内萤火虫密度越小，萤火虫的决策域半径会加大，以便找到更多的邻居；反之，则萤火虫的决策域半径会缩小。最后，大部分萤火虫会聚集在多个位置上。初始萤火虫时，每个萤火虫个体都携带了相同的萤光素浓度l0和感知半径r0。定义1萤光素更新 l i(t)=(1-ρ)l i(t-1)+γJ(x i(t))（1）其中，J(x i(t))为每只萤火虫i在t迭代的位置x i(t)对应的目标函数值；l i(t)为荧光素值转化为荧光素值；γ为荧光素更新率。定义2概率选择选择移向邻域集N i(t)内个体j的概率p ij(t)： p ij(t)=l j(t)-l i(t) k∈N i (t) Σ(l k(t)-l i(t)) （2）其中，邻域集N i（t）={j:d ij(t)

群智能优化算法综述

目录摘要 (1) 1概述 (3) 2定义及原理 (3) 2.1定义 (3) 2.2群集智能算法原理 (4) 3主要群智能算法 (4) 3.1蚁群算法 (4) 3.2粒子群算法 (5) 3.3其他算法 (6) 4应用研究 (7) 5发展前景 (7) 6总结 (8) 参考文献 (9)

1概述优化是人们长久以来不断研究与探讨的一个充满活力与挑战的领域。很多实际优化问题往往存在着难解性,传统的优化方法如牛顿法、共扼梯度法、模式搜索法、单纯形法等己难以满足人们需求。因此设计高效的优化算法成为众多科研工作者的研究目标。随着人类对生物启发式计算的研究,一些社会性动物(如蚁群、蜂群、鸟群)的自组织行为引起了科学家的广泛关注。这些社会性动物在漫长的进化过程中形成了一个共同的特点:个体的行为都很简单,但当它们一起协同工作时,却能够“突现”出非常复杂的行为特征。基于此,人们设计了许多优化算法,例如蚁群算法、粒子群优化算法、混合蛙跳算法、人工鱼群算法,并在诸多领域得到了成功应用。目前,群智能理论研究领域主要有两种算法:蚁群算法(Ant Colony Optimization,ACO)和粒子群优化算法(ParticleSwarm Optimization,PSO)。 2定义及原理 2.1定义群集智能优化算法源于对自然界的生物进化过程或觅食行为的模拟。它将搜索和优化过程模拟成个体的进化或觅食过程，用搜索空间中的点模拟自然界中的个体；将求解问题的目标函数度量成个体对环境的适应能力；将个体的优胜劣汰过程或觅食过程类比为搜索和优化过程中用好的可行解取代较差可行解的迭代过程。从而，形成了一种以“生成+检验”特征的迭代搜索算法，是一种求解极值问题的自适应人工智能技术。各类优化算法实质上都是建立问题的目标函数，求目标函数的最优解，因而实际工程优化问题均可转化为函数优化问题。其表达形式如下：求： X i=(x1,x2,L,x n)T,i=1,2,L,n, min f(X), s.t.g i(X)≤0,j=1,2,Lm, X∈Ω。其中，X i g(X)≤0为约束函数；Ω为设计变量为设计变量；f(X)为被优化的目标函数；j

群体智能方法在最优化问题的应用和未来

群体智能方法在最优化问题的应用和发展前景姓名：曾燕亭学号：201110510133 班级：11计科1班摘要：将遗传算法解决最优化问题，即将最优化问题转化为求解目标函数的最优解问题。关键词：遗传算法；最优化 1.定义 1.1定义及原理顾名思义，群体智能即群其实质是将物理问题数字化，体产生的智能，与集体智慧类似。我们可以从两个方面来理解群体智能的含义。一方面，群体智能是自然界广泛存在的一种现象，指大量简单个体构成的群体按照简单的交互规则相互协作，完成了其中任何一个个体不可能单独完成的复杂任务。以蚁群为例，正如斯坦福大学生物学家D．Gordon的概括：蚂蚁很笨，但蚁群很聪明。另一方面，人们通过对这些群体行为的研究，逐步形成了群体智能理论，即研究大量个体的简单行动如何成为群体的高智能行为的理论。群体智能理论自20世纪80年代出现以来便吸引了众多研究者的关注，是人工智能及经济、社会、生物等交叉学科的热点和前沿领域，因此设计高效的优化算法成为众多科研工作者的研究目标。随着人类对生物启发式计算的研究, 一些社会性动物( 如蚁群、蜂群、鸟群) 的自组织行为引起了科学家的广泛关注。这些社会性动物在漫长的进化过程中形成了一个共同的特点: 个体的行为都很简单, 但当它们一起协同工作时, 却能够“突现”出非常复杂的行为特征。基于此,人们设计了许多优化算法,例如蚁群算法、粒子群优化算法、混合蛙跳算法、人工鱼群算法,并在诸多领域得到了成功应用。目前, 群智能理论研究领域主要有两种算法: 蚁群算法和粒子群优化算法。群集智能优化算法源于对自然界的生物进化过程或觅食行为的模拟。它将搜索和优化过程模拟成个体的进化或觅食过程，用搜索空间中的点模拟自然界中的个体；将求解问题的目标函数度量成个体对环境的适应能力；将个体的优胜劣汰过程或觅食过程类比为搜索和优化过程中用好的可行解取代较差可行解的迭代过程。从而，形成了一种以“生成+检验”特征的迭代搜索算法，是一种求解极值问题的自适应人工智能技术。各类优化算法实质上都是建立问题的目标函数，求目标函数的最优解，因而实际工程优化问题均可转化为函数优化问题。其表达形式如下：求：

智能优化算法(蚁群算法和粒子群算法)

7.1 蚁群优化算法概述 ?7.1.1 起源 ?7.1.2 应用领域 ?7.1.3 研究背景 ?7.1.4 研究现状 ?7.1.5 应用现状

7.1.1 蚁群优化算法起源 20世纪50年代中期创立了仿生学，人们从生物进化的机理中受到启发。提出了许多用以解决复杂优化问题的新方法，如进化规划、进化策略、遗传算法等，这些算法成功地解决了一些实际问题。

20世纪90年代意大利学者M．Dorigo，V．Maniezzo，A．Colorni等从生物进化的机制中受到启发，通过模拟自然界蚂蚁搜索路径的行为，提出来一种新型的模拟进化算法——蚁群算法，是群智能理论研究领域的一种主要算法。

背景：人工生命 ?“人工生命”是来研究具有某些生命基本特征的人工系统。人工生命包括两方面的内容。 ?研究如何利用计算技术研究生物现象。?研究如何利用生物技术研究计算问题。

?现在关注的是第二部分的内容，现在已经有很多源于生物现象的计算技巧。例如，人工神经网络是简化的大脑模型，遗传算法是模拟基因进化过程的。 ?现在我们讨论另一种生物系统－社会系统。更确切的是，在由简单个体组成的群落与环境以及个体之间的互动行为，也可称做“群智能”(swarm intelligence)。这些模拟系统利用局部信息从而可能产生不可预测的群体行为（如鱼群和鸟群的运动规律），主要用于计算机视觉和计算机辅助设计。

?在计算智能(computational intelligence)领域有两种基于群智能的算法。蚁群算法(ant colony optimization)和粒子群算法(particle swarm optimization)。前者是对蚂蚁群落食物采集过程的模拟，已经成功运用在很多离散优化问题上。

智能优化方法作业——PSO算法

智能优化方法作业PSO算法实验报告课程名称：智能优化方法作者姓名：专业：控制工程

目录第一章问题描述 (1) 第二章算法设计 (1) 2.1解及目标函数的表达 (1) 2.1.1种群的编码 (1) 2.1.2初始种群的产生 (1) 2.1.3评价函数的构造 (1) 2.2 POS速度迭代公式 (2) 2.3粒子的更新 (2) 2.4惯性权重的调整 (3) 2.5停止准则 (3) 第三章算法实现及分析 (3) 3.1编译环境及界面介绍 (3) 3.2 matlab中GUI界面打开的3种方式 (4) 第四章算法分析 (5) 4.1 默认参数下的运行结果 (5) 4.2种群大小对算法的影响 (6) 4.3 最大迭代次数对算法的影响 (8) 4.4 实验得出的“最优”参数 (9)

第一章问题描述无约束5维的Rosenbrock 函数可以描述如下： ∑-=+-+-=112221))1()(100()(min n i i i i x x x x f （1）其中，5,...2,1],30,30[=-∈i x i 。要求按PSO 算法思想设计一个该问题的求解算法，并利用计算机语言实现设计的算法。将实验报告和程序代码（带有详细注释）。第二章算法设计 2.1解及目标函数的表达 2.1.1种群的编码显然对于一个粒子个体可以用一个含有5个元素的一维数组进行表示。对于一个种群这里使用pop_size×5的二维数组进行表示。其中pop_size 为种群大小。 2.1.2初始种群的产生初始种群的各个粒子均采用均匀随机产生的方式，即粒子每一位都是-30到30上的随机数。同样粒子的速度也是-40到40上的随机数。这里设置速度在-40到40内是因为限定速度的最大值为40。 2.1.3评价函数的构造这里直接采用解的函数值作为评价函数，评价函数值越小认为该解越好。评价函数如下： ∑-=+-+-=112221))1()(100()(min n i i i i x x x x f （2）其中，5,...2,1],30,30[=-∈i x i 。