用改进遗传算法求解TSP问题,并编制了完整的Matlab程序予以仿真实现.程序中选择算子采用最佳个体保存与赌轮选择相结合的策略,最后分析了最佳个体保存比例对寻优效果的影响.

第 2卷第 2期 1 2 1年 6月 01

湖南工程学院学报

Vo . 1 No 2 12 _ . J n 0 1 u e2 1

J u n l fHu a n tt t fEn ie r g o r a n n I si eo g n e i o u n

改进遗传算法求解 TS问题的 M a lb程序设计 P ta 缪桂根，高羽佳 (徽农业大学信息与计算机学院物流工程系，肥 2 0 3 )安合 30 6

摘要：用改进遗传算法求解 TS P问题，并编制了完整的 Malb程序予以仿真实现.序中选择算子 t a程采用最佳个体保存与赌轮选择相结合的策略，最后分析了最佳个体保存比例对寻优效果的影响. 关键词：改进遗传算法； P问题； t b程序 TS Mal a中图分类号：TP 9 31文献标识码：A 文章编号：1 7一 l9 2 1 ) 2 O 2 4 6 1 1X( O 1 0一O 4—0

0引言 旅行商问题 ( a eig ae n P o lm, Trv l S lma rbe n TS )又叫货郎担问题， P,是最基本的路线问题，问该

2遗传算法的运行过程 遗传算法是一种”成+检测”生的迭代搜索算法，运算流程可用图 1其来表示.

题是在寻求单一旅行者由起点出发，过所有给定通 的城市之后，最后再回到原点的最小路径成本 .问该题具有广泛的应用性，物流中的配送车辆调度问如

题就可看成一个约束性多路旅行商问题 .此，因对 T P问题求解具有一定的现实意义. S

T P问题属于组合优化问题， S随着问题规模增 大，可行解空间也急剧扩大，时在当前的计算机其有

上用枚举法很难甚至不能求出最优解，用启发式而算法求解这类问题的满意解是一个很好的方式，遗

传算法就是寻求这种满意解的最佳工具之一 .传遗 算法模拟自然进化过程来搜索最优解[,本质是 1其] 一

种高效、并行、局搜索的方法.文采用遗传算全本

法求解 TS P问题并编制 Malb程序进行仿真试 t a 验. 图 1遗传算法的程序

1 T P问题的数学模型 S TS P问题即寻找一条最短的遍历个城市的

3 T P问题的 Malb实现 S t a 参数说明： OP I E表示群体规模， I I

S P SZ NC T E 表示城市数目， o示初始种群，MAX N表示 p p表 GE进化代数， c示个体交叉概率， m表示个体变异 P表 P 概率 .

最短路径，得：使 n 1 - =

∑ d- 1 f+ l+ f 1=

取最小值，+表示两城市 i i之间的距离 . d。和+l

收稿日期：0 1 0— 1 21- 1 7基金项目：徽农业大学青年科学基金资助项目(0 9r7安 20 z3 )作者简介：桂根 (9 4,,士，教，究方向：流系统优化、流与供应链管理缪 1 8一)女硕助研物物