混沌优化算法在TSP问题的应用

桂传志

摘 要：混沌是非线性系统所产生的类似随机的运动，研究表明混沌序列具有随机性、遍历性等特点。由于混沌序列的随机性、遍历性等特点，可将其应用在TSP问题的应用上。多数文章产生混沌序列采用Logistic映射，由于Logistic映射所产生的混沌序列很不均匀，该文采用逻辑自映射来产生混沌序列，大大提高了优化运算的时间。

关键词：混沌 优化算法 TSP问题 Logistic映射

中图分类号：TP18 文献标识码：A 文章编号：1674-098X（2016）07（c）-0074-02

TSP问题即旅行商问题，它求解的是旅行者经过N个城市且仅一次并回到原处总的最小行程。该文章通过逻辑自映射所产生的混沌序列来编程求解20个城市的TSP问题，得到了TSP问题的最优解。

自李兵等将混沌序列引入优化算法，成功地解决了优化算法收敛于局部极值的问题，优化算法取得了较大的进展。近年来，利用混沌序列进行优化搜索的研究也取得了一定的成就。为提高搜索效率，张彤等提出变尺度混沌优化算法，通过变尺度不断地缩小搜索范围，提高了搜索精度，加快了搜索速度。高鹰等把混沌优化算法思想引入粒子群算法，通过对粒子群进行寻优，从而使粒子群的进化速度加快。文章在前人的研究基础上，将混沌优化算法应用于解决TSP问题。

1 混沌序列

混沌序列具有遍历性、随机性、“规律性”等特点，是对初始值敏感的一种复杂序列。由于混沌序列的遍历性，使得混沌搜索可以跳出局部最优点，从而达到全局最优点。混沌序列的产生方法有Logestic映射、立方映射、逻辑自映射等方法。其表达式分别如下：

2 不同映射产生的混沌序列比较

对于Logestic映射，对随机取一初值，，Logestic映射所产生的混沌序列具有很好的遍历性，但是在用Logestic映射寻优的过程中，因为Logestic映射所产生的混沌序列具有遍历性不均匀的特点，使得寻优速度比较缓慢。

而立方映射和逻辑自映射所产生的混沌序列也具有很好的遍历性，立方映射、逻辑自映射所产生的混沌序列的遍历性要更加均匀，从而使得寻优的速度加快。各种映射所产生的混沌序列如图1所示。

衡量混沌性质的一个重要指标是李亚普诺夫指数，从李亚普诺夫指数也可以看出Logestic映射的混沌特性较其他映射更不明显。通过实验的方法得到各种映射所产生的混沌序列的均匀性是不一样的，其分布情况见表1。

3 TSP问题概述

TSP问题，即Travelling Salesman Problem，又被称为推销员问题，是数学领域中著名的N-P问题之一。假设有一个旅行商要去拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能经过一次而且必须经过一次，并且最后要回到原来出发的城市。路径的选择目标是要求得到的路径路程为所有路径之中的最小值。

建立TSP问题解决模型的方法很多，文中采用矩阵的方法。在表2的方阵中，ABCDE表示城市名称，矩阵的值为0表示在旅行时，两个城市没有直接经过；矩阵的值为1表示在旅行时，两个城市直接经过。为保证旅行过程中，每个城市仅经过一次，则要求矩阵的每行每列有且仅有一个1，其余均为0。表示经过的城市路径为A-E-D-C-B-A。

第二步：选择两个混沌序列初值（不相等），即和，其值不相等，且在（-1，1）范围之内。

第三步：将表示TSP问题的矩阵转化为单位阵，求出此时的TSP问题的解，将其设为最优解。

第四步：利用逻辑自映射函数产生两个混沌序列。并将其乘以城市数，然后取整，得到i和j。若i和j相等，重复第四步。

第五步：将表示TSP问题的矩阵的i和j行进行交换操作。

第六步：计算此时的解，如果则。

第七步：达到循环次数，结束；否则，返回第四步。

4 仿真结果

文章采用电脑随机产生20城市坐标，然后对这20城市进行TSP问题求解。这20城市的其坐标值为：16，65；11，100；68，2；58，10；10，80；28，5；30，38；30，95；98，40；28，16；41，41；71，33；63，21；19，58；8，46；91，26；79，38；29，92；63，63；43，10。

通过仿真，求得结果如图2，其最短路径的距离为561.37。

参考文献

[1] 李兵，蒋慰孙.混沌优化方法及其应用[J].控制理论与应用，1997，14（4）：613-615.

[2] 张彤，王宏伟，王子才.变尺度混沌优化方法及其应用[J].控制与决策，1999，14（3）：285-288.

[3] 高鹰，谢胜利.混沌粒子群优化算法[J].计算机科学，2004， 31（8）：13-15.

[4] 洪蕾.粒子群及人工鱼群算法优化研究[J].软件，2014（8）：83-86.