最短路径TSP遗传算法.docx

该【最短路径TSP遗传算法 】是由【玥玥】上传分享，文档一共【9】页，该文档可以免费在线阅读，需要了解更多关于【最短路径TSP遗传算法 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。第四章遗传算法与组合优化
4。1

背包问题(

knapsackproblem

)
问题描绘
0/1背包问题:给出几个尺寸为S1,S2,,Sn的物体和容量为C的背包,此处
Sn和C都是正整数;要求找出n个物品的一个子集使其尽可能多地填满容量为C

S1,S2,,的背包。
数学形式:
n
最大化
SiXi
i
1
n
SiXiC,Xi{0,1},1in
知足
i
1
广义背包问题:输入由C和两个向量C=(S1,S2,,Sn)和P=(P1,P2,,Pn)构成。设X
为一整数会合,即X=1,2,3,,n,T为X的子集,则问题就是找出知足拘束条件XiC,
iT
而使

Pi

获取最大的子集

T,即求

Si和

Pi的下标子集。
iT
在应用问题中,设

S的元素是

n项经营活动各自所需的资源耗费

,C是所能供给的资源总
量,P的元素是人们从每项经营活动中获取的利润或利润,则背包问题就是在资源有限的条件下,追求总的最大利润的资源有效分派问题。
广义背包问题能够数学形式更精准地描绘以下:
n
最大化
PiXi
i
1
n
SiXiC,Xi{0,1},1in
知足
i
1
背包问题在计算理论中属于分地装入背包,即同意X,可取从

NP-完好问题,其计算复杂度为
0。00到1。00闭区间上的实数

O(2n),若同意物品能够部,则背包问题就简化为极简单
的P类问题,此时计算复杂度为

O(n).
。2遗传编码
(问题规
模),Ti(1≤i≤n)=1表示该物品装入背包,Ti=0表示不装入背包。鉴于背包问题有近似求解知识,以及考虑到遗传算法的特色(适合短定义距的、低阶的、高适应度的模式构成的积木块结构类问题),往常将Pi,Si按Pi/Si值的大小挨次摆列,即P1/S1≥P2/S2≥≥Pn/Sn。
4。1。3适应度函数
在上述编码状况下,背包问题的目标函数和拘束条件可表示以下.
n
目标函数:

J(T)

TiPi
i1
n
拘束条件:

TiSi

C
i1
依照利用处罚函数办理拘束条件的方法,我们可结构背包问题的适应度函数

(fT)以下式:
f(T)=J(T)+g(T)
式中g(T)为对T超越拘束条件的处罚函数,处罚函数可结构以下:
式中Em为Pi/S(1≤i≤n)i的最大值,β为适合的处罚系数。
(TravelingSalesmanProblem——TSP)
在遗传其法研究中,TSP问题已被宽泛地用于评论不一样的遗传操作及选择体制的性能。
之所以这样,主要有以下几个方面的原由:
(1)TSP问题是一个典型的、易于描绘却难以办理的NP完好(NP-complete)问题。有效地解
决TSP问题在可计算理论上有侧重要的理讲价值。
TSP问题是诸多领域内出现的多种复杂问题的集中归纳和简化形式。所以,迅速、有效地解决TSP问题有着极高的实质应用价值。
(3)TSP问题因其典型性已成为各种启迪式的搜寻、优化算法的间接比较标准,而遗传算法就
其实质来说,
在TSP问题求解方面的应用研究,对于结构适合的遗传算法框架、成立有效的遗传操作以及有效地解决TSP问题等有着多方面的重要意义。
问题描绘:
找寻一条最短的遍历n个城市的路径,或许说搜寻整数子集X={1,2,,n}(X的元素表示对n个城市的编号)的一个摆列π(X)={v1,v2,,vn},使
取最小值。式中的d(vi,vi+1)表示城市vi到城市vi+1的距离.
4。2。1编码与适应度函数
编码
。
如码串12345678表示自城市l开始,挨次经城市2,3,4,5,6,7,8,最后返回城市1的遍历路径。明显,。
“边”的组合方式进行编码。
比如码串24536871的第1个码2表示城市1到城市2的路径在TSP圈中,第2个码4表示城市2到城市4的路径在TSP圈中,以此类推,第8个码1表示城市7到城市1的路径
在TSP圈中.
“节点”编码方式。
以除去“一点交错”策略(或多点交错策略)惹起的非法路径问题。码串长度仍为n,定义各等位基因的取值范围为(n–i+1),i为基因序号,解码时,依据相应基因位的取值,从城市
号会合中不回放地取一个城市号,,所以现行的研究中极少采纳。
适应度函数
适应度函数常取路径长度Td的倒数,即
f=1/Td
若联合TSP的拘束条件(每个城市经过且只经过一次)
,则适应度函数可表示为:
f
=(
d
+α*N
),
1/
T
t
此中Nt
是对TSP路径不合法的胸怀(如取付Nt为未遍历的城市的个数),α为处罚系数,
常取城市间最长距离的两倍多一点
(*dmax)。
4。2。2交错策略
问题:鉴于TSP问题的次序编码(其他编码如以边的组合状态进行编码也体现相像特征),若采纳简单的一点交错或多点交错策略,必定以极大的概率致使未能完好遍历所有城市的非
法路径。
如8城市的TSP问题的两个父路径为
1234|5678
8765|4321
若采纳一点交错,且交错点随机选为4,则交错后产生的两个后辈为
87655678
12344321
明显,这两个子路径均未能遍历所有8个城市,都违犯TSP问题的拘束条件。
能够采纳上述结构处罚函数的方法,但试验成效不好。
可能的解说:这一方法将本已十分复杂的TSP问题更为复杂化了。因为知足TSP问题拘束条件的可行解空间规模为n!;而按结构处罚函数的方法,其搜寻空间规模变成nn;跟着n的增大n!与nn之间的差距是极其惊人的.
解决这一拘束问题的另一种办理方法是对交错、变异等遗传操作做适合的修正,使其自动知足TSP的拘束条件。
常用的几种交错方法:


(PMX,PartiallyMatchedCrossover)

法
PMX操作是由Goldberg和Lingle于1985年提出的。在PMX操作中,先依照平均随机散布产生两个位串交错点,定义这两点之间的地区为一般配地区,并使用地点互换操作互换两个父串的般配地区。
实例:如两父串及般配地区为
A=984|567|1320
B=871|230|9546
第一互换A和B的两个般配地区,获取
A’=984|230|l320
B'=871|567|9546
对于A’、B'两子串中般配地区以出门现的遍历重复,依照般配地区内的地点映照关系,逐个进行互换。对于A’有2到5,3到6,0到7的地点符号映照,对A’的般配区之外的2,3,0分别以5,6,7替代,则得
A”=984|230|1657
同理可得:
B”=801|567|9243
这样,每个子串的序次部分地由其父串确立。
(OX,OrderCrossover)法
与PMX法相像,Davis(1985)等人提出了一种OX法,此方法开始也是选择一个般配地区:
A=984|567|1320
B=871|230|9546
并依据般配地区的映照关系,在其地区外的相应地点标志H,获取
A’=984

|

567|1HHH
B’=8H1|230|9H4H
再挪动般配区至起点地点,且在后来预留相等于般配地区的空间(的码按其相对序次摆列在预留区后边,获取

H数量),而后将其他
A”=567HHH1984
B"=230HHH9481
最后将父串A,B的般配地区互相互换,并搁置到A",B"的预留区内,即可获取两个子代:
A”’=567|230|1984
B”’=230|567|9481
固然,PMX法与OX法特别相像,但它们办理相像特征的手段却不一样。
所希望的绝对城市地点,而OX法却趋势于希望的相对城市地点。

PMX

法趋势于
(CX,cyclecrossover)法
,使每个城市在拘束条件下进行重组.
假定两个个体:
A=123456789
B=412876935
进行交错。此后辈A’为例说明生成后辈的过程:(1)从A中取第一个元素填人A’的第一个地点:A’=1########
(2)B的第一个元素为“4”,则在A中查找“4”的地点,并将它填入A’相应的地点中:
A’=1##4#####
(3)B的第四个元素为“8”,则在A中查找“8”的地点,并将它填入A’相应的地点中:
A’=1##4###8#
4)B的第八个元素为“3",则在A中查找“3”的地点,并将它填入A’相应的地点中:A'=1#34###8#
(5)B的第三个元素为“2”,则在A中查找“2”的地点,并将它填人A’相应的地点中:
A’=1234###8#
6)B的第二个元素为“1”,而“1"在A'中已经出现,这样就构成了一个循环。此时将剩下的地点填入B中对应地点的值:
A’=123476985
同理,若以A为参照,能够获取B’。最后交错所得的后辈为:
A’=123476985
B’=412856739
循环交错算子的特色是保存了父代个体中序列的绝对地点。

这类方法是一种启迪式的交错方法,按以下规划结构后辈:
(1)随机地选用一个城市作为子代圈的开始城市。
(2)

比较父串中与开始城市毗邻的边

,选用最小的边增添到圈的路径中。
(3)重复第(2)步,假如发现按最小边选用的规划产生非法路径

(重复经过同一城市

),则
按随机法产生一合法的边,这样频频,直至形成一完好的TSP圈。
使用这一方法,可获取较好的结果。可是遗传算法的通用性和鲁棒性。

,这一方法使用了鉴于问题的一些知识,损失了
对于TSP问题的遗传交错方法还有各种各种的变形方法,一般来说,交错方法应能使父
串的待征遗传给子串,子串应能部分或所有地继承父串的结构特色和有效基因.
4。
从遗传算法的看法来看,解的进化主要靠选择体制和交错策略来达成,变异不过为选择、交错过程中可能丢掉的某些遗传基因进行修复和增补,变异在遗传算法的全局意义上不过一个背景操作。针对TSP问题,主要的变异技术以下:

变异仅以必定的概率(往常较小)对串的某些位作值的变异。

在串中随机选择两点,再将这两点内的子串按反序插入到原地点中,如串3,6,则经逆转后,变成A’

A的逆转点为
A=123|456

|

7890
A’=123

|

654

|

7890

随机选择串中的两点,互换其值(码)。对于串A
A=123456789
若对调点为4,7,则经对调后,A’为
A’=123756489

从串中随机选择1个码,将此码插入随机选择的插入点中间,对于上述
入码为5,选用插入点为2~


A'=125346789
选择体制和集体构成
在遗传算法中,最常有的选择体制是适应度比率选择体制;在有限规模的集体中,适应度较高的个体有较大的时机生殖后辈,即生物进化论上的适者生计规则。
在新一代集体构成方法方面存在:
方式:所有替代上一代集体的全刷新代际更新方式。
E方式:保存一个最好的父串的最正确保存(elitist)集体结构方式。
G方式:按必定比率更新集体中的部分个体的部分更新方式极端是每代仅删去一个最不适的个体的最劣死亡方式)。

(或称代沟方法,这类状况的
B方式:从产生的子代和父代中精选最好的若干个个体的集体构成形式.
从集体规模来看,有变化规模的方式,也有恒定规模的集体构成方式等。
一般讲,N方式的全局搜寻性能最好,但收敛速度最慢;B方式收敛速度最快,但全局搜寻性能最差;E方式和G方式的性能介于N方式和B方式之间。在求解货郎担问题的应用中,多项选择用E方式。
鉴于遗传算法求解TSP的算法实现

我们以n城市的遍历序次作为遗传算法的编码,适应度函数取为路径长度的倒数(无处罚函数)。

用随机方法产生初始种群。适应度比率选择,E方式(精英保存)产生新一代种群。

采纳的交错方法与OX法有点近似,现介绍以下:
(1)随机在串中选择一个交配地区,如两父串及交配地区选定为
A=12|3456|789
B=98|7654|321
(2)将B的交配地区加到A的前面或后边,A的交配地区加到B的前面或后边获取
A'=7654|123456789
B’=3456|987654321
(3)在A’中自交配地区后挨次删除与交配区同样的城市码,获取最后的两子串为
A'=765412389
B’=345698721

采纳连续多次对调的变异技术,使可行解有较大的次序摆列上的变化,以克制“进化逆
转”的同化作用。变异操作发生的概率获得比较小(1%左右),一旦变异操作发生,则用随机方法产生互换次数K,对所需变异操作的串进行K次对调(对调的两码位也是随机产生的).
5.“进化逆转”操作
引入“进化逆转”操作的主要目的是改良遗传算法的局部搜寻能力。在针对TSP问题的
遗传算法中,“逆转”是一种常有的“变异”技术。这里使用的“进化逆转"是一种单方向的(朝着改进的方向)和连续多次的“逆转”操作,即对于给定的串,若“逆转”使串(可行解)的适应度提升,则履行逆变换作,这样频频,,这类局部登山能力与基本遗传算法的全局搜寻能力相联合
在实验中显示了较好的成效.


实验中,集体规模定为100,,变异概率为0。003,初始可行解集体由随机法产生。实验结果表示:
(1)当n<15时,随机样本实验表示,本算法可100%搜寻到用穷举法求得的最优解.
(2)当15<M<30时,我们对一组样本进行了测试,结果表示本算法能收敛到一稳固的“最好解"(难以确认其最优性);多次实验的偏差结果为0,模拟退火法也可找到同样的“最好解”,但运转时间约为遗传算法的6倍。
(3)对n=50,M=60,M=80及M=100的测试结果表示,遗传算法在求解质量上略优于模拟退火法(α=),(GA)与模拟退火方法(SA法)的比较实验结果,表中所列TSP路径长度为相对长度,其值由下式算出:
上式中,Td为实质路径的长度,X为包括TSP所有城市的最小正方形的边长,N为TSP问题的城市数量。图为城市规模N=100的TSP问题的初始集体中的最正确路径,图为经本算法优化获取的最正确路径。