遗传模拟退火蚁群三个算法求解TSP的对比.docx
- 文档编号:17869187
- 上传时间:2023-08-04
- 格式:DOCX
- 页数:29
- 大小:30.73KB
遗传模拟退火蚁群三个算法求解TSP的对比.docx
《遗传模拟退火蚁群三个算法求解TSP的对比.docx》由会员分享,可在线阅读,更多相关《遗传模拟退火蚁群三个算法求解TSP的对比.docx(29页珍藏版)》请在冰点文库上搜索。
遗传模拟退火蚁群三个算法求解TSP的对比
数学与统计学院之杨若古兰创作
智能计算及利用课程设计
设计题目:
智能计算解决旅行商成绩
摘要
本文以遗传算法、模拟退火、蚁群算法三个算法解决旅行商成绩,将三个算法进行比较分析.目前这三个算法广泛利用于各个领域中,本文以31个城市为例,应用遗传算法、模拟退火、蚁群算法分别进行了计算,将他们的计算结果进行了比较分析.
关键词:
遗传算法模拟退火蚁群算法旅行商成绩
布景:
遗传算法:
20世纪60年代初,美国Michigan大学的JohnHolland教授开始研讨天然和人工零碎的自适应行为,在从事如何建立能进修的机器的研讨过程中,受达尔文进化论的启发,逐步认识到为获得一个好的算法仅靠单个计谋建立和改进是不敷的,还要依附于一个包含很多候选计谋的群体的繁殖,从而提出了遗传算法的基本思想.
20世纪60年代中期,基于说话智能和逻辑数学智能的传统人工智能十分昌隆,而基于天然进化思想的模拟进化算法则遭到怀疑与反对,但Holland及其指点的博士仍坚持这一领域的研讨.Bagley发表了第一篇有关遗传算法利用的论文,并首先提出“遗传算法”这一术语,在其博士论文中采取双倍体编码,发展了复制、交叉、变异、显性、倒位等基因操纵算子,并敏锐地发觉到防止早熟的机理,发展了自组织遗传算法的概念.与此同时,Rosenberg在其博士论文中进行了单细胞生物群体的计算机仿真研讨,对当前函数优化颇有启发,并发展了自适应交换计谋,在遗传操纵方面提出了很多独特的设想.Hollistien在其1971年发表的《计算机控制零碎的人工遗传自适应方法》论文中首次将遗传算法利用于函数优化,并对上风基因控制、交叉、变异和编码技术进行了深入的研讨.
人们经过持久的研讨,在20世纪}o年代初构成了遗传算法的基本框架.1975年Holland出版了经典著作“AdaptationinNatureandArtificialSystem",该书具体论述了遗传算法的基本理论和方法,提出了闻名的模式理论,为遗传算法奠定了数学基础.同年,DeJong发表了次要论文“AnAnalysisoftheBehav-norofaClassofGenetieAdaptiveSystem",在论文中,他将Holland的模式理论与计算实验结合起来,并通过函数优化的利用深人研讨,将选择、交叉、变异操纵进一步完美和零碎化,并提出了代沟等新的操纵技术,所得出的很多结论至今仍具有普遍的指点意义.
进入20世纪80年代末期,随着计算机技术的发展,遗传算法的研讨再次鼓起.遗传算法以其较强的解决成绩的能力和广泛的适应性,深受浩繁领域研讨人员的看重,遗传算法的理论研讨和利用研讨已成为十分热门的课题.自1985年起,遗传算法及其利用的国际会议每两年召开一次,而且在相干的人工智能会议和刊物上大多设有遗传算法的专题.
模拟退火:
模拟退火算法来源于固体退火道理,是一种基于概率的算法,将固体加温至充分高,再让其缓缓冷却,加温时,固体内部粒子随温升变成无序状,内能增大,而缓缓冷却时粒子渐趋有序,在每个温度都达到平衡态,最初在常温时达到基态,内能减为最小.
模拟退火算法(SimulatedAnnealing,SA)最早的思想是由N.Metropolis[1] 等人于1953年提出.1983年,S.Kirkpatrick等成功地将退火思想引入到组合优化领域.它是基于Monte-Carlo迭代求解计谋的一种随机寻优算法,其出发点是基于物理中固体物资的退火过程与普通组合优化成绩之间的类似性.模拟退火算法从某一较高初温出发,陪伴温度参数的不竭降低,结合概率突跳特性在解空间中随机寻觅目标函数的全局最优解,即在局部最优解能概率性地跳出并终极趋于全局最优.模拟退火算法是一种通用的优化算法,理论上算法具有概率的全局优化功能,目前已在工程中得到了广泛利用,诸如VLSI、生产调度、控制工程、机器进修、神经收集、旌旗灯号处理等领域.
模拟退火算法是通过赋予搜索过程一种时变且终极趋于零的概率突跳性,从而可无效防止堕入局部极小并终极趋于全局最优的串行结构的优化算法.
蚁群算法:
蚁群算法(antcolonyoptimization,ACO),又称蚂蚁算法,是一种用来在图中寻觅优化路径的机率型算法.它由MarcoDorigo于1992年在他的博士论文中提出,其灵感来源于蚂蚁在寻觅食物过程中发现路径的行为.蚁群算法是一种模拟进化算法,初步的研讨标明该算法具有很多良好的性质.针对PID控制器参数优化设计成绩,将蚁群算法设计的结果与遗传算法设计的结果进行了比较,数值仿真结果标明,蚁群算法具有一种新的模拟进化优化方法的无效性和利用价值.
算法道理:
遗传算法:
遗传操纵是模拟生物基因遗传的做法.在遗传算法中,通过编码构成初始群体后,遗传操纵的任务就是对群体的个体按照它们对环境适应度(适应度评估)施加必定的操纵,从而实现优越劣汰的进化过程.从优化搜索的角度而言,遗传操纵可使成绩
遗传过程
的解,一代又一代地优化,并迫近最优解.
遗传操纵包含以下三个基本遗传算子(geneticoperator):
选择(selection);交叉(crossover);变异(mutation).这三个遗传算子有如下特点:
个体遗传算子的操纵都是在随机扰动情况下进行的.是以,群体中个体向最优解迁移的规则是随机的.须要强调的是,这类随机化操纵和传统的随机搜索方法是有区此外.遗传操纵进行的高效有向的搜索而不是如普通随机搜索方法所进行的无向搜索.
遗传操纵的后果和上述三个遗传算子所取的操纵概率,编码方法,群体大小,初始群体和适应度函数的设定密切相干.
从群体当选择优越的个体,淘汰劣质个体的操纵叫选择.选择算子有时又称为再生算子(reproductionoperator).选择的目的是把优化的个体(或解)直接遗传到下一代或通过配对交叉发生新的个体再遗传到下一代.选择操纵是建立在群体中个体的适应度评估基础上的,目前经常使用的选择算子有以
下几种:
适应度比例方法、随机遍历抽样法、局部选择法.
其中轮盘赌选择法(roulettewheelselection)是最简单也是最经常使用的选择方法.在该方法中,各个个体的选择概率和其适应度值成比例.设群体大小为n,其中个体i的适应度为,则i被选择的概率,为遗传算法
明显,概率反映了个体i的适应度在全部群体的个体适应度总和中所占的比例.个体适应度越大.其被选择的概率就越高、反之亦然.计算出群体中各个个体的选择概率后,为了选择交配个体,须要进行多轮选择.每一轮发生一个[0,1]之间均匀随机数,将该随机数作为选择指针来确定被选个体.个体被选后,可随机地构成交配对,以供后面的交叉操纵.
在天然界生物进化过程中起核心感化的是生物遗传基因的重组(加上变异).同样,遗传算法中起核心感化的是遗传操纵的交叉算子.所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操纵.通过交叉,遗传算法的搜索能力得以飞跃提高.
交叉算子根据交叉率将种群中的两个个体随机地交换某些基因,能够发生新的基因组合,期望将无益基因组合在一路.根据编码暗示方法的分歧,可以有以下的算法:
实值重组(离散重组,两头重组,线性重组,扩展线性重组).二进制交叉(单点交叉,多点交叉,均匀交叉,洗牌交叉,缩小代理交叉).
最经常使用的交叉算子为单点交叉.具体操纵是:
在个体串中随机设定一个交叉点,实行交叉时,该点前或后的两个个体的部分结构进行互换,并生成两个新个体.上面给出了单点交叉的一个例子:
个体A:
1001↑111→1001000新个体
个体B:
0011↑000→0011111新个体
变异算子的基本内容是对群体中的个体串的某些基因座上的基因值作变动.根据个体编码暗示方法的分歧,可以有以下的算法:
a)实值变异
b)二进制变异.
普通来说,变异算子操纵的基本步调如下:
a)对群中所有个体以事先设定的变异概率判断是否进行变异
b)对进行变异的个体随机选择变异位进行变异.
遗传算法引入变异的目的有两个:
一是使遗传算法具有局部的随机搜索能力.当遗传算法通过交叉算子已接近最优解邻域时,利用变异算子的这类局部随机搜索能力可以加速向最优解收敛.明显,此种情况下的变异概率应取较小值,否则接近最优解的积木块会因变异而遭到破坏.二是使遗传算法可保持群体多样性,以防止出现未成熟收敛景象.此时收敛概率应取较大值.
遗传算法中,交叉算子平面而仅靠交叉不克不及解脱时,通过变异操纵可有助于这类解脱.所谓彼此竞争,是指当通过交叉已构成所期望的积木块时,变异操纵有可能破坏这些积木块.如何无效地配合使用交叉和变异操纵,是目前遗传算法的一个次要研讨内容.
模拟退火:
模拟退火算法来源于固体退火道理,将固体加温至充分高,再让其缓缓冷却,加温时,固体内部粒子随温升变成无序状,内能增大,而缓缓冷却时粒子渐趋有序,在每个温度都达到平衡态,最初在常温时达到基态,内能减为最小.根据Metropolis原则,粒子在温度T时趋于平衡的概率为e(-ΔE/(kT)),其中E为温度T时的内能,ΔE为其改变量,k为Boltzmann常数.用固体退火模拟组合优化成绩,将内能E模拟为目标函数值f,温度T演变成控制参数t,即得到解组合优化成绩的模拟退火算法:
由初始解i和控制参数初值t开始,对当前解反复“发生新解→计算目标函数差→接受或舍弃”的迭代,并慢慢衰减t值,算法终止时的当前解即为所得近似最优解,这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程.退火过程由冷却进度表(CoolingSchedule)控制,包含控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S.模拟退火算法可以分解为解空间、目标函数和初始解三部分.模拟退火的基本思想:
(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步.
模拟退火算法新解的发生和接受可分为如下四个步调:
第一步是由一个发生函数从当前解发生一个位于解空间的新解;为便于后续的计算和接受,减少算法耗时,通常选择由当前新解经过简单地变换即可发生新解的方法,如对构成新解的全部或部分元素进行置换、互换等,留意到发生新解的变换方法决定了当前新解的邻域结构,因此对冷却进度表的拔取有必定的影响.
第二步是计算与新解所对应的目标函数差.由于目标函数差仅由变换部分发生,所以目标函数差的计算最好按增量计算.事实标明,对大多数利用而言,这是计算目标函数差的最快方法.
第三步是判断新解是否被接受,判断的根据是一个接受原则,最经常使用的接受原则是Metropolis原则:
若Δt′<0则接受S′作为新的当前解S,否则以概率exp(-Δt′/T)接受S′作为新的当前解S.
第四步是当新解被确定接受时,用新解代替当前解,这只需将当前解中对应于发生新解时的变换部分予以实现,同时批改目标函数值即可.此时,当前解实现了一次迭代.可在此基础上开始下一轮试验.而当新解被判定为舍弃时,则在原当前解的基础上继续下一轮试验.
模拟退火算法与初始值有关,算法求得的解与初始解形态S(是算法迭代的起点)有关;模拟退火算法具有渐近收敛性,已在理论上被证实是一种以概率l收敛于全局最优解的全局优化算法;模拟退火算法具有并行性.
蚁群算法:
蚁群优化算法是模拟蚂蚁觅食的道理,设计出的一种群集智能算法.蚂蚁在觅食过程中能够在其经过的路径上留下一种称之为信息素的物资,并在觅食过程中能够感知这类物资的强度,并指点本人行动方向,它们老是朝着该物资强度高的方向挪动,是以大量蚂蚁构成的集体觅食就表示为一种对信息素的正反馈景象.某一条路径越短,路径上经过的蚂蚁越多,其信息素遗留的也就越多,信息素的浓度也就越高,蚂蚁选择这条路径的几率也就越高,由此构成的正反馈过程,从而逐步的迫近最优路径,找到最优路径. 蚂蚁在觅食过程时,是以信息素作为媒介而间接进行信息交流,当蚂蚁从食物源走到蚁穴,或者从蚁穴走到食物源时,都会在经过的路径上释放信息素,从而构成了一条含有信息素的路径,蚂蚁可以感觉出路径上信息素浓度的大小,而且以较高的概率选择信息素浓度较高的路径
蚁群零碎(ACS[12])是由Dorigo等人提出来的改进的蚁群算法,它与AS的分歧的地方次要体此刻三个方面:
(1)采取分歧的路径选择规则,能更好地利用蚂蚁所积累的搜索经验.
(2)信息素挥发和信息素释放动作只在至今最优路径的边上履行,即每次迭代以后只要至今最优蚂蚁被答应释放信息素;(3)除了全局信息素更新规则外,还采取了局部信息素更新规则. 在ACS中,位于城市i的蚂蚁k,根据伪随机比例规则选择城市j作为下一个访问的城市.
设C={c1,c2,…,cn}是n个城市的集合,L={lij|ci,cjC}是集合C中的元素(城市)两两连接的集合,dij(i,j=1,1,…,n)是lij的Euclidean距离,即
G=(C,L)是一个有向图,TSP的目的是从有向图G中寻出长度最短的Hamilton圈,即一条对C={c1,c2,…,cn}中n个元素(城市)访问且只访问一次的最短封闭曲线n城市规模的TSP,存在(n-1)!
/2条分歧闭合路径设bi(t)暗示t时刻位于元素i的蚂蚁数目,τij(t)为t时刻路径(i,j)上的信息量,n暗示TSP规模,m为蚁群中蚂蚁总数,则
是t时刻集合C中元素(城市)两两连接lij上残留信息量的集合,在初始时刻各条路径上的信息量相等,并设τij(0)=const,基本蚁群算法的寻优是通过有向图g=(C,L,Γ)实现的.
蚂蚁k(k=1,2,…,m)在活动过程中,根据各条路径上的信息量决定其转移方向.这里用禁忌表tabuk来记录蚂蚁k当前所走过的城市,集合随着tabuk进化过程做动态调整.在搜索过程中,蚂蚁根据各条路径上的信息量及路径的启发信息来计算形态转移概率.在t时刻蚂蚁k由元素(城市)i转移到元素(城市)j的形态转移概率:
其中allowedk={C-tabuk}暗示蚂蚁k下一步答应选择的城市;α为信息启发式因子,暗示轨迹的绝对次要性,反映了蚂蚁在活动过程中积累的信息在蚂蚁活动时所起的感化,其值越大,则该蚂蚁越倾向于选择其它蚂蚁经过的路径,蚂蚁之间的协作性越强;β为期望启发式因子,暗示能见度的绝对次要性,反映蚂蚁在活动过程中启发信息在蚂蚁选择路径中的受看重程度,其值越大,则该形态形态转移概率越接近于贪心规则;ηij(t)为启发函数,ηij(t)=1/dij式中dij暗示相邻两个城市之间的距离.对蚂蚁k而言,dij越小,则ηij(t)越大,pijk也就越大.明显,该启发函数暗示蚂蚁从元素(城市)i转移到元素(城市)j的期望程度.
为了防止残留信息素过多惹起残留信息沉没启发信息,在每只蚂蚁走完一步或者完成对所有n个城市的遍历(也即一个轮回结束)后,要对残留信息进行更新处理.这类更新计谋模仿了人类大脑记忆的特点,在新信息不竭存人大脑的同时,存储在大脑中的旧信息随着时间的推移逐步淡化,甚至健忘.由此,t+n时刻在路径(i,j)上的信息量可按如下规则进行调整
式中,ρ暗示信息素挥发系数,则1-ρ暗示信息素残留因子,为了防止信息的无穷积累,ρ的取值范围为[0,1),Δτij(t)暗示本次轮回中路径(i,j)上的信息素增量,初始时刻Δτij(t)=0,Δτijk(t)暗示第k只蚂蚁在本次轮回中留在路径(i,j)上的信息量.
根据信息素更新计谋的分歧,DorigoM提出了三种分歧的基本蚁群算法模型,分别称之为Ant-Cycle模型、Ant-Quantity模型及Ant-Density模型,其不同在于Δτijk(t)求法的分歧.
程序
遗传算法:
clear
clc
closeall
%%加载数据
%loaddata
X=[13042312;36391315;41772244;37211399;34881535;33261556;32381229;41961004;4312790;4386570;30071970;25621756;27881491;23811676;1332695;37151678;39182179;40612370;37802212;36762578;40292838;42632931;34291908;35072367;33942643;34393201;29353240;31403550;25452357;27782826;23702975];
D=Distanse(X);%生成距离矩阵
N=size(D,1);%城市个数
%%遗传参数
NIND=100;%种群大小
MAXGEN=200;%最大遗传代数
Pc=0.9;%交叉概率
Pm=0.05;%变异概率
GGAP=0.9;%代沟
%%初始化种群
Chrom=InitPop(NIND,N);
%%画出随机解的路径图
DrawPath(Chrom(1,:
),X)
pause(0.0001)
%%输出随机解的路径和总距离
disp('初始种群中的一个随机值:
')
OutputPath(Chrom(1,:
));
Rlength=PathLength(D,Chrom(1,:
));
disp(['总距离:
',num2str(Rlength)]);
disp('~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~')
%%优化
gen=0;
figure;
holdon;boxon
xlim([0,MAXGEN])
title('优化过程')
xlabel('代数')
ylabel('最优值')
ObjV=PathLength(D,Chrom);%计算路径长度
preObjV=min(ObjV);
whilegen %%计算适应度 ObjV=PathLength(D,Chrom);%计算路径长度 %fprintf('%d%1.10f\n',gen,min(ObjV)) line([gen-1,gen],[preObjV,min(ObjV)]);pause(0.0001) preObjV=min(ObjV); FitnV=Fitness(ObjV); %%选择 SelCh=Select(Chrom,FitnV,GGAP); %%交叉操纵 SelCh=Recombin(SelCh,Pc); %%变异 SelCh=Mutate(SelCh,Pm); %%逆转操纵 SelCh=Reverse(SelCh,D); %%重拔出子代的新种群 Chrom=Reins(Chrom,SelCh,ObjV); %%更新迭代次数 gen=gen+1; end %%画出最优解的路径图 ObjV=PathLength(D,Chrom);%计算路径长度 [minObjV,minInd]=min(ObjV); DrawPath(Chrom(minInd (1),: ),X) %%输出最优解的路径和总距离 disp('最优解: ') p=OutputPath(Chrom(minInd (1),: )); disp(['总距离: ',num2str(ObjV(minInd (1)))]); disp('-------------------------------------------------------------') %%计算两两城市之间的距离 %输入a各城市的地位坐标 %输出D两两城市之间的距离 functionD=Distanse(a) row=size(a,1); D=zeros(row,row); fori=1: row forj=i+1: row D(i,j)=((a(i,1)-a(j,1))^2+(a(i,2)-a(j,2))^2)^0.5; D(j,i)=D(i,j); end end %%画路径函数 %输入 %Chrom待画路径 %X各城市坐标地位 functionDrawPath(Chrom,X) R=[Chrom(1,: )Chrom(1,1)];%一个随机解(个体) figure; holdon plot(X(: 1),X(: 2),'o','color',[0.5,0.5,0.5]) plot(X(Chrom(1,1),1),X(Chrom(1,1),2),'rv','MarkerSize',20) fori=1: size(X,1) text(X(i,1)+0.05,X(i,2)+0.05,num2str(i),'color',[1,0,0]); end A=X(R,: ); row=size(A,1); fori=2: row [arrowx,arrowy]=dsxy2figxy(gca,A(i-1: i,1),A(i-1: i,2));%坐标转换 annotation('textarrow',arrowx,arrowy,'HeadWidth',8,'color',[0,0,1]); end holdoff xlabel('横坐标') ylabel('纵坐标') title('轨迹图') boxon functionvarargout=dsxy2figxy(varargin) iflength(varargin{1})==1&&ishandle(varargin{1})... &&strcmp(get(varargin{1},'type'),'axes') hAx=varargin{1}; varargin=varargin(2: end); else hAx=gca; end; iflength(varargin)==1 pos=varargin{1}; else [x,y]=deal(varargin{: }); end axun=get(hAx,'Units'); set(hAx,'Units','normalized'); axpos=get(hAx,'Position'); axlim=axis(hAx); axwidth=diff(axlim(1: 2)); axheight=diff(axlim(3: 4)); ifexist('x','var') varargout{1}=(x-axlim (1))*axpos(3)/axwidth+axpos (1); varargout{2}=(y-axlim(3))*axpos(4)/axheight+axpos (2); else pos (1)=(pos (1)-axlim (1))/axwidth*axpos(3)+axpos (1); pos (2)=(pos (2)-axlim
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 遗传 模拟 退火 三个 算法 求解 TSP 对比