遗传算法讲义523

1、Technical ReportTSP问题的遗传算法求解马广才，大连大学数学建模工作室一、序言本材料简单介绍了遗传算法的概念和算法的流程，结合2010年东北三省数学建模联赛B题:周游全中国，给出了用遗传算法求解TSP问题的matlab二、遗传算法的概念遗传算法(Genetic Algorithm)是一类借鉴生物界的进化规律(适者 生存，优胜劣汰遗 传机制)演化而来的随机化 搜索方法。它是由美国的 J.Holland教授1975年首先提出。它将问题域中的可能解看作是群体的个体， 并将个体编码成符号串形式(即染色体)，模拟生物进化过程，对群体反复 进行杂交等操作，根据预定的适应度函数对每个个体进行

2、评价，依据优胜 劣汰的进化规则，不断得到更优的群体，同时搜索优化群体中的最优个体， 求得满足要求的最优解。三、遗传算法的基本流程初始化：设置进化代数计数器t=0，设置最大进化代数T，随机生成M 个个体作为初始群体P(0)。个体评价：计算群体P(t)中各个个体的适应度。选择运算：将选择算子作用于群体。选择的目的是把优化的个体直接 遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建 立在群体中个体的适应度评估基础上的。交叉运算；将交叉算子作用于群体。所谓交叉是指把两个父代个体的 部分结构加以替换重组而生成新个体的操作。遗传算法中起核心作用的就是 交叉算子。变异运算：将变异算子作用于

3、群体。即是对群体中的个体串的某些基 因座上的基因值作变动。群体P(t)经过选择、交叉、变异运算之后得到下一 代群体P(t 1)。终止条件判断：若tT,则以进化过程中所得到的具有最大适应度个体 作为最优解输出，终止计算。四、问题描述TSP问题，又称旅行商问题，旅行推销员问题，是指对于给定的n个城 市，旅行商从某一城市出发不重复的访问其余城市后回到出发的城市，要求找出一条旅行路线，使总的旅行路程最短。2010年东北三省数学建模联赛B题：周游全中国，即为一个典型的TSP 问题，图论中，将地图视为一个附权图，该问题就是求该图的一个最短哈密 尔顿圈。到目前为止，哈密尔顿图的非平凡的充分必要条件尚不知道，

4、因此TSP 问题还没有有效的方法，现在的解决方法都是寻找一个近似最优的哈密尔顿圈。同时，TSP问题属于组合优化为范畴，目前流行的求解算法有模拟退火算法、 蚁群算法、遗传算法等启发式算法。下面我们将给出用遗传算法求解该问题的 MATLAB 程序。遗传算法的一般算法流程五、求解程序1、种群规模、最大繁殖代数等基本参数的设定我们设定种群的规模为50，即种群中有50个个体，一个个体对应问题 的一个解。基因长度为34，即问题中我们要走访34个城市。最大的繁殖后 代为第1000代。个体发生杂交的概率为0.9，发生变异的概率为0.15。读 入距离矩阵distance，距离矩阵是一个34*34，主对角线为0的

5、对称矩阵。PopSize=50;City=34;k=20;Max_gen=1000;PcX=0.9;Pm=0.15;distance=xlsread(distance.xls);2、种群的初始化这里我定义了一个函数Initialize.m用来初始化种群。function Pop=Initialize(PopSize,City)Pop二zeros(PopSize,City);for i=1:PopSizePop(i,:)二randperm(City);endPop=Pop,zeros(PopSize,1);Pop先设为PopSize行，City列的全0矩阵。之后，Pop的每一行为1 City的随

6、机序列。最后在Pop矩阵加一列0，该列用以存放对应个体的适 应值。1718233023PopSize 行1718233023PopSize 行1425City+1 列3、初始种群适应值的计算为计算种群的适应值，我定义了一个 Caculate.m函数。对种群中的每 个个体，对应Pop矩阵中的每一行，分别计算按照该行的路径走的总路程， 并存于该行的最后一个位置。for i=1:sdd=0;for j=1:t-2dd=dd+distance(Pop(i,j),Pop(i,j+1);enddd=dd+distance(Pop(i,1),Pop(i,t-1);Pop(i,t)=dd;End1718233

7、023dd1dd 214251718233023dd1dd 21425dd (i)4、适者生存，优胜劣汰4.1、杂交算子杂交算子在遗传算法中起核心作用，它是指将个体进行两两配对，并以 交叉概率Pc把配对的父代个体加以替换重组而生成新个体的操作。这里采 用的是有序交叉法。步骤1.随机选取两个交叉点pointa和pointb ；步骤2.两后代先分别按对应位置复制双亲x1和x2匹配段中的两个子串Al 和 B1 ；步骤3.在对应位置交换双亲匹配段以外的城市。如果交换后，后代x1_new中的某一城市a与子串A1中的城市重复，则将该城市取代子串B1与Al中的城市a具有相同位置的新城市，直到与子串A1中的城

8、市均不重复为 止。对后代x2_new亦然，如下图所示（以10个城市为例）。xi：X2:98871 41 1546107 1 |3 2|3926105Fx1_new:831 4567 1 |9102x2_new:981 14103 2|756核心代码:s,t=size(Pop);Pop1= Pop;point二randperm(t-3)+1;point二point(1:2);pointa二min(point);pointb二max(point);x1=Pop1(i,:);x2=Pop1(i+1,:);x1_new=zeros(size(x1);x2_new=zeros(size(x2);x1_n

9、ew(pointa:pointb)=x1(pointa:pointb);x2_new(pointa:pointb)=x2(pointa:pointb);for j=1:pointa-1x1_new(j)=x2(j);x2_new(j)=x1(j);for k=pointa:pointbif x1_new(j)=x1_new(k)x1_new(j)=x2(k);endif x2_new(j)=x2_new(k)x2_new(j)=x1(k);endendendfor j=pointb+1:t-1for k=pointa:pointbif x1_new(j)=x1_new(k)x1_new(j)=

10、x2(k);endif x2_new(j)=x2_new(k) x2_new(j)=x1(k);endendend为表示遗传中的杂交过程，我定义了一个函数Cross.m来模拟这一过程。4.2、变异算子变异操作是以变异概率Pm对群体中个体串某些基因位上的基因值作变 动，若变异后子代的适应度值更加优异，则保留子代染色体，否则，仍保留 父代染色体。这里采用的方法是倒置变异法。仍以10个城市为例，假设当前个体x 为(1 3 7 4 8 10 5 9 6 2)。如果randPm，那么随机选择来自同一个体的 两个点a和b，比如说3和7,倒置a和b之间的部分，产生下面的子体x_new 为(1 3 5 10

11、8 4 7 9 6 2)。核心代码：for i=1:sp=rand;if pPm;qujian二randperm(t-1);b=max(qujian(1:2);a=min(qujian(1:2);Pop1(i,a:b)=Pop1(i,b：-1:a);endend4.3、选择算子选择就是从群体中选择优胜个体、淘汰劣质个体的操作，它是建立在群 体中个体适应度评估基础上。这里采用方法是最优保存方法。算法就是首先 将群体中适应度最大的k个个体直接替换适应度最小的k个个体。核心代码：m11=Pop(:,t);num=1;while numk+1xuhao二find(m11=max(m11);mmax(num)=xuhao(1);m11(mmax(num)=0;num=num+1;endnum=1;m11=Pop(:,t);while numk+1xuhao二find(m11=min(m11);mmin(num)=xuhao(1);m11(mmin(num)