matlab遗传算法代码,解决优化问题

如何安排访问次序

问题：

已知n个城市之间的相互距离，推销员必须遍访这n个城市，且每个城市

只能访问一次，最后又必须返回出发城市。如何安排访问次序，可使其

旅行路线的总长度最短？

用图论的术语来说，假设有一个图g=(v,e)，其中v是顶点集，e是边集，设d=(dij) 是由顶点i和顶点j之间的距离所组成的距离矩阵，旅行商问题就是求出一条通过所有顶 点且每个顶点只通过一次的具有最短距离的回路。

这个问题可分为对称旅行商问题(dij=dji,,任意i,j=1,2,3，…,n)和非对称旅行商 问题(dij≠dji,,任意i,j=1,2,3，…,n)。

若对于城市v={v1,v2,v3,…,vn}的一个访问顺序为t=(t1,t2,t3,…,ti,…,tn),其中 ti∈v(i=1,2,3,…,n)，且记tn+1= t1，则旅行商问题的数学模型为：

min l=σd(t(i),t(i+1)) （i=1,…,n）

旅行商问题是一个典型的组合优化问题，并且是一个np难问题，其可能的路径数目

与城市数目n是成指数型增长的，所以一般很难精确地求出其最优解，本文采用遗传算法 求其近似解。

遗传算法：

初始化过程：用v1,v2,v3,…,vn代表所选n个城市。定义整数pop-size作为染色体的个数

，并且随机产生pop-size个初始染色体，每个染色体为1到18的整数组成的随机序列。 适应度f的计算：对种群中的每个染色体vi，计算其适应度，f=σd(t(i),t(i+1)). 评价函数eval(vi)：用来对种群中的每个染色体vi设定一个概率，以使该染色体被选中 的可能性与其种群中其它染色体的适应性成比例，既通过轮盘赌，适应性强的染色体被 选择产生后台的机会要大，设alpha∈(0,1)，本文定义基于序的评价函数为eval(vi)=al

pha*(1-alpha).^(i-1) 。[随机规划与模糊规划]

选择过程：选择过程是以旋转赌轮pop-size次为基础，每次旋转都为新的种群选择一个 染色体。赌轮是按每个染色体的适应度进行选择染色体的。

step1 、对每个染色体vi,计算累计概率qi，q0=0;qi=σeval(vj) j=1,…,i;i=1, …pop-size.

step2、从区间(0,pop-size)中产生一个随机数r；

step3、若qi-1 step4、重复step2和step3共pop-size次，这样可以得到pop-size个复制的染色体。

grefenstette编码：由于常规的交叉运算和变异运算会使种群中产生一些无实际意义的 染色体，本文采用grefenstette编码《遗传算法原理及应用》可以避免这种情况的出现 。所谓的grefenstette编码就是用所选队员在未选（不含淘汰）队员中的位置，如： 8 15 2 16 10 7 4 3 11 14 6 12 9 5 18 13 17 1

对应：

8 14 2 13 8 6 3 2 5 7 3 4 3 2 4 2 2 1。

交叉过程：本文采用常规单点交叉。为确定交叉操作的父代，从 到pop-size重复以下过