10.6 基于遗传算法的TSP问题优化.ppt

10.6基于遗传算法的TSP问题优化在第8.4.2节已经对旅行商问题进行了描述。遗传算法由于其全局有哪些信誉好的足球投注网站的特点，在解决TSP问题中有明显的优势。10.6.1TSP问题的编码设是由城市i和城市j之间的距离组成的距离矩阵，旅行商问题就是求出一条通过所有城市且每个城市只通过一次的具有最短距离的回路。在旅行商问题的各种求解方法中，描述旅行路线的方法主要有如下两种：（1）巡回旅行路线经过的连接两个城市的路线的顺序排列；（2）巡回旅行路线所经过的各个城市的顺序排列。大多数求解旅行商问题的遗传算法是以后者为描述方法的，它们大多采用所遍历城市的顺序来表示各个个体的编码串，其等位基因为N个整数值或N个记号。以城市的遍历次序作为遗传算法的编码，目标函数取路径长度。在群体初始化、交叉操作和变异操作中考虑TSP问题的合法性约束条件（即对所有的城市做到不重不漏）。10.6.2TSP问题的遗传算法设计采用遗传算法进行路径优化，分为以下几步：第一步：参数编码和初始群体设定一般来说遗传算法对解空间的编码大多采用二进制编码形式，但对于TSP一类排序问题，采用对访问城市序列进行排列组合的方法编码，即某个巡回路径的染色体个体是该巡回路径的城市序列。针对TSP问题，编码规则通常是N取进制编码，即每个基因仅从1到N的整数里面取一个值，每个个体的长度为N，N为城市总数。定义一个s行t列的pop矩阵来表示群体，t为城市个数N+1，即N+1，s为样本中个体数目。针对30个城市的TSP问题，t取值31，即矩阵每一行的前30个元素表示经过的城市编号，最后一个元素表示经过这些城市要走的距离。参数编码和初始群体设定程序为：pop=zeros(s,t);fori=1:spop(i,1:t-1)=randperm(t-1);end第二步：计算路径长度的函数设计在TSP的求解中，用距离的总和作为适应度函数，来衡量求解结果是否最优。将POP矩阵中每一行表示经过的距离的最后一个元素作为路径长度。两个城市m和n间的距离为：（10.4）用于计算路径长度的程序为chap10_1dis.m。通过样本的路径长度可以得到目标函数和自适应度函数。根据t的定义，两两城市组合数共有t-2组，则目标函数为：（10.5）自适应度函数取目标函数的倒数，即：（10.6）第三步：计算选择算子选择就是从群体中选择优胜个体、淘汰劣质个体的操作，它是建立在群体中个体适应度评估基础上。仿真中采用最优保存方法，即将群体中适应度最大的c个个体直接替换适应度最小的c个个体。选择算子函数为chap10_4select.m。第四步：计算交叉算子交叉算子在遗传算法中起着核心的作用，它是指将个体进行两两配对，并以交叉概率将配对的父代个体加以替换重组而生成新个体的操作。如果当前随机值大于，则随机选择两个个体进行交叉。有序交叉法实现的步骤是:有序交叉法实现的步骤是:步骤1随机选取两个交叉点crosspoint(1)和crosspoint(2)；步骤2两后代和先分别按对应位置复制双亲X1和X2匹配段中的两个子串A1和B1；步骤3在对应位置交换X1和X2双亲匹配段A1和B1以外的城市，如果交换后，后代中的某一城市a与子串中A1的城市重复，则在子传B1中找到与子串A1中城市a对应位置处的城市b,并用城市b取代城市a。如果城市b与子串A1中的城市还重复，则在子串B1中找到与子串A1中b处对应位置处的城市c，并用城市c取代城市b，直到中的城市均不重复为止，对后代也采用