,应用交叉算子产生两个后代.把所有的后代加入Ps 3.变异:使用均匀的概率从Ps中选择m%的成员.对于选出的每个成员,在它表示中随机选择一个为取反
4.更新:P←Ps
5.评估:对于P中的每个h计算Fitness(h)
从P中返回适应度最高的假设
TSP问题的遗传算法设计与实现
3.1 TSP问题的图论描述
求最短路径问题，用图论术语描述如下：在图G(V,A)中，V表示顶点集合，V=(v1,v2,…,vn)对G中的某一边(,)，相应的有一个数d(,)，如果G中不存在边(,)，则令d(,)无穷大，如果把d(,)认为是边(,)的长度，则通路的长度定义为组成路的各条边的长度总和。
顶点,之间是否有边相连，由邻接矩阵来决定。
邻接矩阵A：对一个具有v个顶点，e条边的图G的邻接矩阵A=[]
是一个v×v阶方阵，其中=1，表示和邻接， =0表示vi和vj不相邻接（或i=j）。
3.2 染色体编码
对于一个给定的图模型，将图中各顶点序号自然排序，然后按此顺序将每个待选顶点作为染色体的一个基因，当基因值为1时，表示相应的顶点被选入该条路径中，否则反之。此染色体中的基因排列顺序即为各顶点在次条通路中出现的先后顺序，染色体的长度应等于该图中的顶点个数。
在本程序的TSP问题中一共有20个城市，也就是在图模型中有20个顶点，因此一个染色体的长度为20。
3.3 适应函数f(i)
对具有n个顶点的图，已知各顶点之间(,)的边长度d(,)，把到间的一条通路的路径长度定义为适应函数：
对该最优化问题，就是要寻找解，使f()值最小。
3.4 选择操作
选择作为交叉的双亲，是根据前代染色体的适应函数值所确定的，质量好的个体，即从起点到终点路径长度短的个体被选中的概率较大。
3.5 交叉与变异操作
将被选中的两个染色体进行交叉操作的过程是先产生一个随机数，确定交叉点，位于染色体的第几位基因上.然后在此位置进行部分基因交换。变异操作是将染色体中某位基因逆变，即由1变为0，或反之。变异的意义为在某条路径上去掉或增加某顶点.但这样做的结果并不一定能使路径的长度减少。也就是说有可能使各代中产生的比较好的方案在遗传过程中丢失，迟缓了获得最优解的速度。
为了使算法尽可能快地获得更好的解，改善遗传算法的收敛性。在变异操作时，增加了个体求优的自学习过程，即在某位基因变异后.计算新产生的染色体的适应函数值，若适应函数值更小，即获得的路径更短，则保留;否则，保持原来的解不变。如果有连续N/3次没有得到更好的解，则该过程结束。其中N表示从起点到终点的顶点数。
3.6 TSP问题的遗传算法的具体步骤
解最短路径的遗传算法如下：
Generate[p(n)];表示程序开始时要首先产生一个群体，群体个数为n
Evaluate[p(h)];表示计算每个个体适应度，h是种群中的一个个体
Repeat roof Generations times;重复下面的操作，直到满足条件为止
Select p(h) from p(n-1);表示从前一代群体中选择一对双亲，用于交叉、变异 操作，P(n)代表第n代群体
Crossover and mutation p(n);进行交叉和变异操作
Learning[p(n)];自学习过程
Evaluate[p(h)];计算新生成的种群中每个个体的适应度
End;
实验测试与结果分析
交叉率不可选择过小，否则，延缓获得最优解的过程，本程序选择=0.85。
变异率的选择对规模大的优化问题影响很大，本程序选=0.1。
群体中的个体数的选取是算法中一个很重要的参数，群体中的个体数目越大，算法就越能找到更好的解，个体数目过小，有可能找不到最优解。本程序种群大小为300。
因为有20个城市，每个城市作为染色体中的一个基因，因此在本程序中染色体的长度为20。
本程序的循环终止的条件是迭代次数不大于100，因此，最大迭代次数为100。
本程序中总共运行10次，得到每次最好的路径、回路总开销和适应度。
程序的运行结果如下：
参考文献
[1] 遗传书算法——理论、应用与软件实现,王小平、曹立明,西安交通大学出版社,2002
[2] 机器学习,Tom M.Mitchell 机械工业出版社,2009
源代码清单：
#include #include #include #include
