混沌优化算法在组合优化问题中的应用

摘 要：组合优化问题一直都受到理论界和工程界的重视，此类问题的求解方法也有很多，却各有缺点和局限性，不能满足实际应用的需要。混沌优化算法在解决数值优化问题上具有一定的普遍性，可以很快找到全局最优解，不过组合优化问题的解不是一个数值，因此在前人研究的基础上，提出求解组合优化问题的混沌优化算法。首先分析混沌优化，并针对组合优化问题中的TSP问题，提出一种混沌优化策略，探讨在TSP问题中应用混沌优化算法的方法。结果表明了该方法的有效性。

关键词：混沌优化算法；组合优化；TSP;数值优化

中图分类号：TP18 文献标识码：B 文章编号：1004373X(2008)1806803

Application of Chaos Optimization Algorithm in the Solution of

Combination Optimization Problems

CHEN Shuang1,GUO Jianqin2

(1.School of Computer Science and Technology,Shandong University,Jin′an,250014,China;

2.Shandong College of Electronic Technology,Jin′an,250014,China)

Abstract：The combination optimization problems have been paid more attention in the field of theory and the engineering,there also has many solutions of this kind of problems,but actually they all have their disadvantages and limitations,so they cannot satisfy the need of the practical application.The chaos optimization algorithm has certain universality in the solution of the value optimization problems,and they can find the globally optimal solution very quickly,but the solution of the combination optimization problems is not a value,therefore this article proposes the solution of the combination optimization problems chaos optimization algorithm on the studies of the predecessors.This article first analyzes the chaos optimization,and aims at the TSP problems in the combination optimization problems,proposes one kind of strategy of the chaos optimization,and discusses application ofchaos optimization algorithm in the TSP problems,and finally it indicates that this method is effective.

Keywords：chaos optimization algorithm;combination optimization;TSP;value optimization

1 引 言

许多实际工程问题都可以转换成组合优化问题加以解决，例如目标识别、特征点匹配、以及路径优化，火力分配等问题。对于组合优化问题\，通常采用神经网络或模拟退火等方法才能进行求解。这些算法虽然具有较快的寻优速度，但通常存在易于陷入局部极小等缺点。混沌在优化计算中具有独特的性能\，混沌的随机性可使优化算法具有跳出局部极小的能力，混沌的遍历性可使优化算法到达全局最优解附近。

2 混沌优化

混沌是指在确定系统中出现的一种貌似无规则，类似随机的现象，是存在于非线性系统中的一种较为普遍的现象。混沌并不是一片混乱，而是有着精致内在结构的一类现象，混沌是非线性动力学系统在一定条件下所表现的一种运动形式，是系统处于非平衡过程中所呈现的随机行为；产生混沌的机制往往又是简单的非线性，是丝毫不带随机因素的固定规则\。

混沌运动具有遍历性、随机性、规律性等特点，混沌运动能在一定范围内按其自身的规律不重复地遍历所有状态。混沌的遍历性特点可被用来进行优化搜索且能避免陷入局部极小，因此，混沌优化搜索方法已成为一种新颖的优化技术，混沌优化就是根据其遍历性和规律性特点采用混沌变量在一定范围内进行搜索，促使混沌变量的搜索跳出局部极小点，最终达到全局最优点。

用混沌优化方法求解优化问题min f(x)，寻优变量x一般都有一定的取值范围，故需构造混沌变量t与寻优变量x取值区间的映射关系。本文的混合优化算法使用x=c＋d*t映射形式。其中c，d是当混沌变量在区间(0，1)遍历时寻优变量x均能在指定范围内变化的常向量\。

混沌优化方法的迭代步骤为：

Step 1 设置控制误差ε，给定混沌初始向量t0，令k=0；

Step 2 将t0映射到x0的优化区间：x0=c+dt0，并令x*=x0，f*=f0；

Step 3 用混沌变量进行迭代搜索得出xk和fk，如果|fk－fk－1|<ε，则x*=xk，f*=fk，结束。否则转Setp 4;

Step 4 令k=k+l，转Step 3。

混沌优化方法求解组合优化问题的基本思想是：首先研究组合优化问题解的空间的特点，产生初始解；再利用混沌变量产生新的解或对初始解，进行混沌扰动，求新解的适应值，得到目前最优解；经过多次迭代，求出全局最优值。在组合优化过程中，混沌优化算法不必像随机搜索方法那样根据某种概率转移来摆脱局部极小，混沌优化搜索不存在局部极小，用混沌二次载波搜索的优化方法能很好地求解无约束优化问题。

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

旅行商问题\（Traveling Salesman Problem，TSP）是图论中有代表性的组合优化问题，已经被证明有NP完全计算复杂性，并且许多实际问题都可以转化为旅行商问题。

例如：铁路运营、管道铺设、线路的选择、计算机网络的拓扑结构、邮递员送信和火炬接力等。因此，该问题高效的全局优化算法的研究，一直被科技界和工程界所高度重视。

3.1 TSP问题描述及其计算复杂度

（1） TSP问题描述

问题描述：给定n个城市的集合{1,2,…,n}及城市之间环游的花费C_ij(1≤i≤n,1≤j≤n,i≠j)，需要找到1条经过每个城市1次且回到起点的最小花费的环游\。

对于大规模TSP，可以进行分区分层研究，即把大规模问题分为若干层次和区域，每区用己有的有效算法求解，然后把通一层次各的各区视为又一个TSP进行优化，再用相应算法处理各区的连接，如此逐层处理以渴求得到大规模问题的次优解。

（2） TSP问题计算复杂度

如果采用最简单的穷举发来解决此问题，需要把所有的路径方案的长度都求出来，从中选择一个最短的。则由组合数学理论可知，这是一个n个城市沿闭合路径排列的计算问题，它共有1n(n!)=(n－1)！种方案。如果将沿同一闭合路径但是方向相反的方案只算为一个方案，则穷举法的方案数为12(n－1)！

（3） TSP问题的拓展

在旅行商问题的研究中，有一类多路旅行商问题(Multiple Traveling Salesman Problem，MTSP)。所谓多路旅行商问题是指m个推销员从同一城市(或不同城市)出发，分别走一条旅行线路，使得每个城市都有且仅有1个推销员走过(出发城市除外)，且总路径最短。

多路旅行商问题的研究将对运筹学、铁路运输规划的研究，对于加速推动运输线代化有一定的促进意义。

对于TSP问题，也有一些启发式算法，如最邻近搜索、截面搜索、凸包分析、自适应方法等。这些算法都有一定的效果，特别是对平面上的TSP问题，可以利用其位置信息、三角不等式或几何特性来减小算法的复杂度，但对一般的TSP问题，即只有距离信息而无位置信息或不满足三角不等式的不可度量的大规模TSP，还没有有效的算法。

3.2 用混沌优化算法解决TSP问题的流程

（1） 将一个TSP问题映射成为一个混沌优化系统可以用以下步骤完成：

将TSP问题的每一条可能路径用1个换位矩阵表示，并给出相应的距离表示式；

将TSP问题的换位矩阵集合与由n个神经元阵列相对应；每一条路经所对应的换位阵的个元素与相应的神经元稳态输出对应；

找出一个反映TSP约束优化问题的能量函数；

求出使能量函数取最小值的神经网络连接权值矩阵和偏置参数。

这样由上述步骤设计的神经网络可用于相应的TSP问题的求解，网络的稳态输出就是TSP问题的局部优化解，同时它也是相应能量函数的最小点。网络的搜索时间即是稳定态的时间，计算过程就是网络动力学过程。

（2） 用混沌优化求解TSP算法步骤如下：

给定TSP的城市数目和城市坐标，从tsp.dat文件中读入数据，其中包括城市数目n，城市坐标{C₁(x,y),C₂(x,y),…，C_n(x,y)},（这里(x,y)代表实际的二维地理坐标）；然后初始化一个n×n规模的混沌网络，包括输入矩阵y_ij和输出矩阵xij；

归一化城市坐标{C₁(x,y),C₂(x,y),…C_n(x,y)},为{c1(x,y),c₂(x,y),…，c_n(x,y)},，再计算归一化后的距离矩阵d_ij。用随机化方法给y_ij(0)赋一个n×n的随机初值矩阵；

通过设定混沌衰减参数终止值zend，可以求得混沌神经网络最终收敛需要的周期数，计算方法为：Cycle(tend)=log1－β(z(tend)/z0)；

如果Cycle=1，计算xij(0)：计算本周期能量函数；否则，计算dE/dx；再计算本周期y_ij(t+1),xij(t+1)和本周期能量函数E；

迭代从1：Cycle，判断如果n

具有大量并行计算能力的神经网络，在硬件中采用时，能够很快找到最优解。而且，计算时间不取决于问题的复杂度，而是取决于网络的内部反馈连接。

对于不同城市数目的TSP问题，应尽量将参数z0和β调整到一个合适的范围内。例如，对于城市数目比较大的TSP问题，z0的设定也相对大一点，因为由于神经网络阶数越多，参与计算的神经元数目越多，由于状态空间的搜索区域比较大，而这时不应性自衰减因子若太小，造成的扰动和混沌态就会过小，从而降低混沌遍历搜索的效果；β的值稍微小一点，是为了有利于进行比较细的搜索。

4 结 语

混合优化算法是一种具有全局收敛性且收敛速度快的算法，它具有的许多优点。混沌优化对于连续变量的优化是有效的，其优化原理具有普遍性，能够更有效地寻找到全局最优解。

参 考 文 献

［1］刘传文.基于Hopfield神经网络的遥感图像超分辨率识别算法［J］.武汉理工大学学报，2005，29(6)：970973.

［2］张国钢，耿英三，王建华.基于蚁群并行算法的电气接线路径优化及仿真［J］.系统仿真学报，2003，15(8)：1 0911 094.

［3］高海昌，冯博琴，朱利.智能优化算法求解TSP问题［J］.控制与决策，2006，21(3)：241247.

［4］徐耀群，刘健.一种混沌神经网络及其在旅行商问题中的应用\.中国控制与决策学术年会论文集\，2004.

［5］王凌.智能优化算法及其应用［M］.北京：清华大学出版社，2001.

［6］梁瑞鑫，郑德玲.基于区间套混沌搜索的混合优化方法［J］.北京科技大学学报，2002，24(3)：342344.

［7］尤勇，王孙安，盛万兴.新型混沌优化方法的研究及应用［J］.西安交通大学学报，2003，37(1)：6972.

［8］王丽侠.混沌优化算法及在0/1背包问题中的应用［J］.仪器仪表学报，2006（S3）：580581.

［9］何国光，朱萍，曹志彤，等.混沌神经网络的Lyapunov指数与混沌区域［J］.浙江大学学报：理学版，2004，31（4）：387390.

［10］胡志坤，桂卫华，彭小奇.混沌梯度组合优化算法\.控制与决策，2004，19（12）：1 3371 340.

作者简介 陈 双 女，1975年出生，山东大学计算机科学与技术学院。主要研究方向为计算机原理及应用。

郭建勤 女，1974年出生，山东省电子职业技术学院电子系，讲师。

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文

推荐访问:优化 组合 混沌 算法