用遗传算法求解TSP问题.ppt

文档介绍：用遗传算法求解TSP问题
遗传算法简称GA( ic Algorithm),在本质上是一种求解问题的高效并行全局搜索方法。
遗传算法的两大主要特点是群体搜索策略和群体中个体之间的信息相互交换,它实际上是模拟由个体组成的群体的整体学****过程,其中每个个体表示给定问题搜索空间中的一个解。
begin
initialization
产生一个初始群体
计算第一代群体中各个个体的适应度
repeat
选择父代
交叉操作
子代变异
计算子代的适应度
子代取代父代,形成新的一代个体
until some stopping criterion applies
end
TSP问题可描述为:已知K个城市各城市间的距离,某一旅行商从某个城市出发访问每个城市一次且仅一次,最后回到出发城市,怎样
安排才使其所走路线最短。
遗传操作包括以下三个基本遗传算子:
1、选择算子
(1)按比例的适应度计算
(2)基于排序的适应度计算
(3)期望值方法
(4)锦标赛选择方法
2. 交叉算子
(1)单点交叉。
(2)多点交叉
(3)均匀交叉
(4)顺序交叉
3、变异算子
(1)启发式变异
(2)交换变异
(3)插入变异
(4)替换变异
在掌握了遗传算法和TSP问题的基础知识后,用JAVA语言实现了一种应用“***赌”选择操作,顺序交叉操作、启发式变异操作和位置重排变异操作求解TSP问题的遗传算法。
采用以遍历城市的次序排列进行编码的方法,并将n座城市的数字表示形式转化为字母表示形式,这样可以借助Java语言的强大字符串处理函数来降低算法设计难度。
即数字0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,
15,16,17,18,19⋯⋯25,26⋯分别对应字母序列A,B,C,D,E,F,G,H,I,J,K,L,M,N,0,P,Q,R,S,T,⋯⋯Z,a⋯。
单个个体的遍历路径以字符串形式存储,种群中的全部个体的遍历路径存储在字符串数组中。
1、选择操作
2、顺序交叉
3、启发式变异操作