算法,旅行商理由及其智能优化决策相关

中图分类号：C934 文献标识码：A文章编号：1007-0745（2012）02-0070-02
：典型的TSP理由，遗传算法的机理，设计特定的遗传算子，并用于该理由的求解。数值实验结果了算法设计的性、性。
词：遗传算法TSP理由智能优化
旅行商理由（TSP：treling salean problem）也称货郎担理由。该理由的最早可追溯到18世纪的欧拉年代，但直到20世纪50年代才优化技术的兴起逐渐为所认识而著名。，该理由属于NP-难理由，当理由规模时，确定性优化算法等很难求解，基于此，该理由的特点，于随机搜索算法在函数优化的优势，设计遗传算法，并用于该理由的求解。

1、理由描述及数学模型

设有n个城市，且已知各城市间的旅行费用。现要求找出一条旅行路线，使得以某城市c0出发走遍城市（仅一次）又回到出发点c0，且总费用最低。其数学描述如下：
设集合C={c0,c1,、、、，cn-1}，ci表示第i个城市，设ci,cj∈C间的费用为d(ci,cj)∈Z+，一般d(ci,cj)≠d(cj,ci)。非对称的TSP，假设以c0出发又回到c0且经过C中其他每个城市ci正好一次的路径为，则数学模型可描述如下：
（P）

2、算法论述及运转小学数学教学论文机制

遗传算法是模拟自然选择和遗传的随机搜索算法。其对在函数优化出的潜力，对于理由的初始解是随机产生，新的解由模拟进化和继承的遗传操作生成。每个解都由函数——适应度函数给予评价，而这一不断，直至达到某种形式的收敛。算法中，所求理由的解，编码被映射到染色体符号串，并构成由理由解空间到染色体符号串编码空间的映射，进而把理由解空间搜索转化为染色体符号串编码空间的搜索。染色体由基因构成，基因担负了个体的某种性状，它通常是染色体符号串的个在特定部位上、具有特定长度的子串。典型的遗传算法如下：
步1初始化，随机生成符号串群体p(t=0)；
步2基于适应度函数F(x)对第t代群体p(t)符号串评价；
步3运用一组遗传操作（繁殖、交叉、变异）生成一组新的符号串群体p(t+1)；
步4步2和步3直到解答收敛。
遗传算法的流程图如下：

3、算子设计

3.1 染色体编码

本无对于个体的编码整数编码的形式，即个体x=x1x2、、、x3,xi∈[1,n],xi≠xj表示决策案例。如x=01234，即以0号城市出发，到1号城市，再以1号城市到2号城市，以此类推，以4号城市回到出发点0号城市。

3.2 适应度函数

个体的适应值其在群体，由模型（P）可知，求解的为总费用的最小化。，为了仿生算法的特点，设定费用上界Cmax，则适应度函数定义为
F(x)=Cmax-f(x)≥0 （1）
由（1）可知，F(x)越大，所得案例对应的总费用越小。

3.3 选择算子

转盘式选择（roulette wheel select）算法。由个体适应度函数定义知，个体xi的在群体平均适应度值为，N为群体规模。随机生成r∈（0,1），找i∈[1,N]使得p0+p1+p2+、、、+pi-1≤p1+p2+、、、+pi-1+pi （2）成立，进而选择个体xi，此处假设p0=0。

3.4 交叉算子

基于改善型的单点随机交叉规则。设有两父代个体M,F，子代个体为D,S，随机产生整数1≤p＜l，l为染色体的长度，使整个染色体分成两。在交叉操作中，下一代个体D的染色体（前面P个基因值）按取自于母体M的前面p个基因值；则取自父体的基因，即以父体F的个基因开始选取，某个基因值与前面的基因值，则不选取该基因值，转而选择父体的下基因值，直至选取到(l-p)个基因值为止。便产生了可行的下一代个体D。用类似的策略教学论文另一子代个体S。
，有两个个体M=(2,4,5|1,6,3)，F=（1,3,2|5,4,6），p=3，如上规则产生两后代个体为D=(2,4,5|1,3,6)，S=(1,3,2|4,5,6)。

3.5 变异算子

变异操作的目的保持群体的多样性，防止“早熟”现象的产生。，采取两点随机交换变异的策略教学论文。设有个体x=、、i、、、j、、、，随机产生两个变量p1,p2∈（0，l），假设对应位置上的基因值为i,j，则变异后的个体为x1 =、、、j、、i、、。

4、实例仿真

对于所设计算法的参数设置为：群体规模N=80，交叉概率Pc=0.8，变异概率Pm=0.3，最大迭代数Max=1000。
理由：设有20个城市（限于篇幅，各城市的平面坐标城市之间的费用等数据略）。所的算法求解得最优案例为：0-4-1-11-6-8-14-15-13-10-16-5-19-9-18-17-3-7-2-12，对应的总费用为387。



图2 函数值搜索曲线图



图3 最优路线图
由图2可知，代数的增加，算法还可能更优解。
5、结束语
典型的TSP(NP-hard)理由，设计出特定的遗传算法对其求解，了满意的决策案例。，对于高维的其他NP-hard理由，该智能算法仍出的潜力。

文献：
施光燕，董加礼.最优化策略教学论文[M].高等教育出版社，2005
周明，孙树栋.遗传算法原理及运用[M].国防工业出版社，2000
[3]许志聪.TSP理由解法探讨.大众科技，2008（10）：50-51