数学建模 遗传算法解决TSP问题相关论文
!20!
法运行,输出最优解。
说明:Step3可以取不同的策略,以上只是一种而已。同时为了保证算法的快速收敛性,在计算中将每次得到的最优解都取为下次计算的一个粒子。
机床与液压#2006 No 8
(TO(2,3))所起的作用就一样。显然对任意两个解序列T1、T2,总可以找到一个交换序列TT,而且还不止一个,使得T2=T1+TT,在所有满足这个等式的交换序列中包含交换子最少的交换序列TT称为两个解序列的差,记为T2-T1。按自然顺序排列的解序列称为基本解序列,记为T0。对两个解序列T1与T2,把
T0+(T1-T0)+(T2-T0)
称为两个解序列的和,记为T2+T1。一个数 (0与1之间)与一个交换序列TT的乘积 TT规定为:设交换序列TT含有n个交换子,把[0,1]分成n等份,则 TT的结果为:当 <
1
是空交换序列(即n
1 n
3 动态规划粒子算法求解PCB数控钻孔最佳走刀路线问题
3 1 动态规划粒子群算法用于求解离散优化问题
旅行商问题(travelingsalesmanproblem,TSP)是典型的NP-Hard问题;可描述为:设有n个城市a1,a2, ,an,每两个间都有路径相连,从某一城市出发,每个城市都经一次且仅一次,最终回到最先开始的城市,寻找一种走法,使总路程最短;走法可记为(ai1,ai2, ,ain,ai1),其中ai1,ai2, ,ain是a1,a2, ,an的一种排列,常称ai1,ai2, ,ain为解序列。
对n个城市的TSP问题的解序列T=(ai1,ai2, ,ain),用TO(i1,i2)表示交换T中的点ai1和ai2的一种变换,并用T+TO(i1,i2)表示解T经变换TO(i1,i2)操作后所得的新解;称TO(i1,i2)为交换子。一个或多个交换子的有序列(TO1,TO2, ,TOn)称为交换序列;用符号TT表示。一个交换序列TT作用于一个TSP解序列T就是用这个交换序列中的每一个交换子依次作用于该解序列上,即
T =T+TT=T+(TO1,TO2, ,TOn)=[(T+TO1)+TO2]+ +TOn
不同的交换序列可能起到的作用一样,例如TT1
=(TO(1,2),TO(1,3),TO(1,2))与TT2=
序号坐标X坐标Y
1
2
3
4
5
6
它作用于任一个解还是得到原来的解序列);当 <当
2
,是保留TT的第一个交换子所得的交换序列;n
23
<是保留TT的第一个与第二个交换子nn
所得的交换序列;以下依次类推。一个数 (0与1之间)与一个解序列T的乘积 T规定为:
T=T0+ (T-T0)
通过这样的操作,上面的算法就可用于求解像旅行商这样离散优化问题。
3 2 算法的性能测试与讨论
利用文献[7]的14个点的TSP标准问题来测试算法的有效性。14点TSP的问题描述列于表1。
7
8
9
10
11
12
13
14
表1 14个点的位置表
16 4716 4720 0922 3925 2322 0020 4717 2016 3014 0516 5321 5219 4120 0996 1094 4492 5493 3797 2496 0597 0296 2997 3898 1297 3895 5997 1394 55
用该方法连续做8次实验,其中参数设置为 1=0 53、 1=0 35、 2=0 45,初始种群的个数为600,设定最大迭代次数为300,结果如表2。
表2 实验结果
实验序数获得最好值30 8785的代数每次都获得的最优路径
158
230
358
458
558
658
793
8196
上面的测试表明DPSO能跳出局部极值最终得到问题的最优解,这主要是通过把高维优化转化为低维优化的作用,在保持一些分量不变的情况下,对其余分量进行优化;这样不断地交替进行,增强了算法对高维问题的优化能力。改进后的算法只是在计算策略上作了一些改进,未对算法增加额外的计算和处理,保持了PSO算法的简洁性;同时把一个高维优化问题转化为几个维数低的优化问题进行处理,在计算量上和原来是一样的。
6-12-7-13-8-11-9-10-1-2-14-3-4-5
表3
算法分析表

3 3 动态规划粒子群算法求解PCB数控钻孔最佳走刀路线问题
20孔的坐标如表4,PCB(No City=20)按一般PCB-,图3、图4分别是10次计;
: 水库优化调度是一个典型的 具有多约束条件的、 动态的、 非线性的优化问题...动态规划粒子群算法解 PCB 数控钻孔 最佳走刀路线问题 [ J]. 机床与液压, ...
陈光明 基于数控加工的工艺设计原则及方法研究[期刊论文]-制造业自动化 2005(09) 3.莫愿斌;陈德钊 动态规划粒子群算法解PCB数控钻孔最佳走刀路线问题[期刊论文]...
智能优化算法(蚁群算法和粒子群算法)_交通运输_工程科技_专业资料。主要介绍智能...提出了许多用以解决 复杂优化问题的新方法,如进化规划、进化策略、 遗传算法等,...
基于改进粒子群算法的智能机器人路径规划摘 要:针对机器人路径规划问题,为了使机器人能在较短的时间里,经过最短的 路径,且较平滑的从起始位置运动到目标位置。本...
20 08 双层 规划 问题 的粒子 群 算法研 究李相 勇 , ? 田 澎 , ( 上海 交通 大学安 泰经 济 与管 理学 院 摘要 : 上海 . 20 0 5 2 ) 提 ...
暂无评价 5页 7下载券 适于车辆路径规划的改进... 暂无评价 6页 免费喜欢...粒子群优化算法 计算车辆路径问题摘要粒子群优化算法中,粒子群由多个粒子组成,...
关键词:粒子群算法 PCB实时检 该付费资源由维普网提供 中国最大最早的专业...如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处...
24, No. 3 March 2007 基于量子粒子群算法求解整数规划* 刘静, 须文波, ...出了 量子 粒子 群优 化算 法( QPSO) , 并用于 求解 整数 规划 问题 。...
另一方面又具有进化算法的特 点,和遗传算法、进化策略、进化规划等算法有 相似...粒子群优化算法伪代码 //说明:本例以求问题最小值为目标 //参数:N为群体规模...
热门文档