智能优化算法中的蚁群与混沌混合

混沌是自然界广泛存在的一种非线性现象，它看似混沌，却有着精致的内在结构，具有“随机性”、“遍历性”及“规律性”等特点，对初始条件极度敏感，能在一定范围内按其自身规律不重复地遍历所有状态，利用混沌运动的这些性质可以进行优化搜索。根据混沌特性，融入到其他算法中，提出了一系列新的优化方法，如混沌遗传算法。本节将混沌融入蚁群优化算法中，提出混沌蚁群（Chaos Ant Colony Optimization，CACO）算法，利用混沌初始化进行改善个体质量和利用混沌扰动避免搜索过程陷入局部极值。

Logistic映射就是一个典型的混沌系统，迭代公式如下

式中，μ为控制参量，当μ=4，0≤Z0≤1时，Logistic完全处于混沌状态。利用混沌运动特性可以进行优化搜索，其基本思想是首先产生一组与优化变量相同数目的混沌变量，用类似载波的方式将混沌引入优化变量使其呈现混沌状态，同时把混沌运动的遍历范围放大到优化变量的取值范围，然后直接利用混沌变量搜索。由于混沌运动具有随机性、遍历性、对初始条件的敏感性等特点，基于混沌的搜索技术无疑会比其他随机搜索更具优越性。本书将利用μ=4时的混沌特性，取式（3.20）的Logistic映射为混沌信号发生器。

1.混沌初始化

蚁群优化算法初始化时，各路径的信息素取相同值，让蚂蚁以等概率选择路径，这样使蚂蚁很难在短时间内从大量的杂乱无章的路径中找出一条较好的路径，所以收敛速度较慢。假如初始化时就给出启发性的信息量，可以加快收敛速度。改进的方法是利用混沌运动的遍历性，进行混沌初始化，每个混沌量对应于一条路径，产生大量的路径（如100条），从中选择比较优的路径（如30条），使这些路径留下信息素（与路径长度和成反比），各路径的信息量就不同，以此引导蚂蚁进行选择路径。

每个混沌量对于一条路径是利用全排列构造的理论。首先以（1，2，3，4）的全排列为例，讨论其构造，给出转换算法。所有不同排列的总计数为4！=24，其构造按词典序，则构造的第一位元素取最小标号，以后各位依次增大，1234是首构造，首向量是111，含义为每次都是取剩下物件的最小标号。按词典序构造，末构造为4321，末向量为432。序号D、向量V和构造C就构成了DVC表，如表3.1所示。

表3.1　1～4排列的DVC表

续表

由DVC表知，D、V和C之间是有关系的，它们之间有D/V、V/D、V/C、C/V、D/C、C/D六种转换，我们关心的D/C转换，目前无法直接写出转换公式，需要通过D/V转换，再经过V/C来完成。

D/V转换公式如下：

V/C转换是通过向量V的指针能来确定构造C。如

V=v1v2v3=231，则有

由式（3.20）产生混沌量zi（0≤zi≤1），则D0=n！zi，代入式（3.21），令d1=nzi得到

再由V的指针功能来确定构造C，这样Zi与C一一对应。

2.选择较优解

蚂蚁每次周游结束后，不论蚂蚁搜索到的解如何，都将赋予相应的信息增量，比较差的解也将留下信息素，这样就干扰后续的蚂蚁进行寻优，造成大量的无效的搜索。改进的方法是，只有比较好的解才留下信息素，即只有当路径长度小于给定的值时才留下信息素。

3.混沌扰动(www.xing528.com)

蚁群利用了正反馈原理，在一定程度上加快了进化进程，但也存在一些缺陷，如出现停滞现象，陷入局部最优解。改进的措施加入混沌扰动，再调整信息量，再加入混沌扰量，以使解跳出局部极值区间。更新方程修改为

其中，zij为混沌变量，由式（3.20）迭代得到；q为系数。

4.混沌蚁群优化算法

改进后的解TSP问题的混沌蚁群优化算法如下：

（1）nc←0（nc为迭代步数或搜索次数），混沌初始化，调整各路径信息素，将m只蚂蚁置于n个顶点上。

（2）将各蚂蚁的初始出发点置于当前解集中，对每只蚂蚁k（k=1，2…，m），按概率移至下一顶点j，将顶点j置于当前解集。

（3）计算各蚂蚁的路径长度Lk（k=1，2…，m），记录当前的最好解。

（4）对路径长度Lk小于给定值的路径，按更新方程（3.23），修改轨迹强度。

（5）nc←nc+1。

（6）若nc＜预定的迭代次数且无退化行为（即找到的都是相同解），则转步骤然。

（7）输出目前最好解。

5.算法测试

蚁群优化算法最早解决的就是组合优化问题，这也是目前研究最多、应用最广泛的问题之一。该算法首先在著名的TSP问题上获得成功，继而应用于一系列的离散优化问题中，表现出相当好的性能。TSP是一个经典的组合优化难题，自蚁群优化算法以求解TSP为例说明了其基本思想之后，对蚁群优化算法模型的改进研究通常都以TSP作为实例，来对比算法模型的优劣性。从简单的对称型TSP到非对称的TSP、多目标TSP等，蚁群优化算法都取得了良好的效果。

为了检验算法的有效性，来解决中国31个省及直辖市和省会城市的CTSP问题，数据来源于文献［100］和pr76.tsp（TSPLIB提供的最好解为108159）。模拟退火算法采用文献［100］的算法，起始温度T=100000，终止温度T0=1，退火速度α=0.99；遗传算法程序采用MATLAB的遗传算法工具箱，参数如下：染色体个数N=30，交叉概率Pc=0.2，变异概率Pm=0.5，迭代次数100；混沌蚁群优化算法参数：α=1.5，m=30，β=2，ρ=0.9。为了说明混沌初始化的优点，与随机初始化也作了比较，每种算法运行50次，结果如表3.2所示。从中可以看出基本蚁群优化算法上加入混沌初始化或混沌扰动后，效果比较好，同时加入混沌初始化或混沌扰动的混沌蚁群优化算法的效果更好。混沌蚁群优化算法解CTSP最好的解如图3.7所示，总路程为15383km，混沌蚁群优化算法解pr76.tsp最好的解如图3.8所示，总路程为108159。　　

表3.2　结果比较

图3.7　用混沌蚁群优化算法解CTSP最好的解

图3.8　用混沌蚁群优化算法解pr76.tsp最好的解

计算结果表明，根据混沌的随机性、遍历性及规律性等特点提出的混沌蚁群优化算法，可以显著提高计算效率，具有较大的实用价值。混沌信号产生机理简单，具有内在并行性，本书混沌信号取自Logistic映射，实际上混沌信号可以取自其他混沌系统，至于哪个更好，有待进一步研究。