甘 屹，李 胜

（上海理工大学 机械工程学院，上海 200093）

0 引言

蚁群优化(Ant Colony Optimization, ACO)是一种模拟自然界蚂蚁寻找食物的行为智能优化算法[1]。目前，对ACO 算法的研究已经由单一的旅行商问题(Traveling Salesman Problem, TSP)领域扩展到了多个应用领域。在运用蚁群算法求解问题时，参数数值的设置直接影响算法的收敛性。本文通过正交试验法获取小生境蚁群优化（Microhabitat ACO，MACO）[2,3]的参数配置，对小生境蚁群算法性能进行优化。并用以求解旅行商问题(Traveling Salesman Problem, TSP)[4,5]和车间调度问题（job shop scheduling Problems，JSSP）问题[6]。

1 小生境蚁群优化概述

针对基本蚁群算法存在的问题，MACO从蚁群信息素分布多样性、更新信息素策略、信息差突变等机制上，对基本蚁群算法进行改进，并应用于求解动态联盟伙伴选择问题和车间调度问题[2]。

MACO对经验信息和启发信息的利用是随着搜索演化进程而变化的。在蚁群搜索最优解的初期，小生境中可利用的经验信息还不多，这时蚂蚁运用初始启发信息，以“探索”为主；随着搜索的演进，小生境中经验信息增多，这时蚂蚁的搜索则以“利用”经验信息为主，加速解的收敛；而到了搜索的后期，要避免算法早熟、停滞的现象，就要在已有解的基础上“再探索”，以扩大解的搜索空间，使更优解得以突现。

MACO算法的蚂蚁更新信息素的方式有两种：局部更新和全局更新。局部更新规则是蚂蚁每移向下一个结点，就会在该路径上留下信息素；全局更新则是在每一次搜索周期结束时（即所有寻优群体都搜索结束时），更新全部路径的信息素。全局更新考虑了每一批寻优群体寻路的结果，隐含了信息反馈，使得算法更容易趋优。本文采用全局更新。

MACO算法还生成小生境信息差（Information Difference），以增加信息的多样性，扩大搜索空间。根据具体问题的特点，小生境信息差可以有不同的产生方法。对于TSP，本文对每代蚂蚁搜索的解采用遗传操作（遗传交叉，遗传变异），产生小生境信息差，扩大解的搜索空间，保证更优解的突现。 对于JSSP，本文的选择概率选择下一可达结点时，以随机概率产生小生境信息差[3]，以跳出局部最优，扩展搜索范围，保持解的多样性。

MACO算法的参数包括关于启发信息、经验信息的α0，β0，kα和kβ等，这些参数体现出蚁群优化进行寻优的同时和真实蚂蚁受环境影响一样，也受到多种因素的影响。这些参数的取值直接关系到算法的寻优效能。

2 正交试验设计

针对蚁群优化多参数的多种取值，本文运用小生境蚁群优化算法求解TSP和JSSP问题，利用正交试验法分析参数α0、β0、kα、kβ对算法寻优性能的影响。

2.1 正交试验因素与水平

在小生境蚁群优化中，一次蚂蚁搜索循环是指所有蚂蚁从初始节点出发，找到一条符合条件的路径的过程。如果最大循环次数NC_m过大，会使算法的收敛时间比较长；如果NC_m偏小，会使算法的结果随机性能增加，影响寻优性能。通过大量实例计算，一般NC_m=500时，算法性能较稳定。同样，如果蚂蚁数目越大，算法的全局搜索能力越强，但是算法的计算速度将成指数级递增。对于TSP，蚂蚁数目一般为城市规模n的2/3[7]。对于JSSP, 每代的蚂蚁数目取为工件数目[8]。通过大量实例计算，本文中，对于TSP，信息挥发率ρ=0.1,对于JSSP，ρ=0.7。

在正交试验中，选取各参数的代表性取值。取α0、β0分别以1的步长递增，lgkα、lgkβ分别取-4.699、-4、-3.699、-3、-2.699。取实验10次的平均值作为实验结果。影响MACO求解的因素与水平如表1所示。由于小生境信息差中的信息是相互关联的[2]，所以考虑α0和β0，kα和kβ，α0和kα以及β0和kβ之间可能存在交互作用，希望通过正交实验设计找出好的因素水平搭配。本文测试的仿真编程软件为MATLAB R2008b，操作系统为Windows XP，CPU为2.0GHz，内存为1.99GB。

表1 正交试验因素和水平

这是个4因素5水平的正交试验，考虑到的交互交互作用有4个，所以采用L50 (511)正交表进行试验。对应的表头设计如表2所示。

表2 L50 (511)表头设计

2.2 试验结果

表3是根据正交表 L25 (56)表头测试48个城市的Att48问题[9]的结果及分析。其中，

Tour_ length =(算法计算所得最短距离-已知最优解)/已知最优解×100%

Iteration _Time =(算法计算所得最短耗费时间-已知最优解)/已知最优解×100%

根据表3计算出每列的极差。极差最大的因素意味着它的不同水平造成的实验差别比较大，由此确定出各个因素对MACO在求解TSP问题的重要性，如表4所示。

表3 各方案的试验结果

设目标函数f(x)=minL。由表4可知，若L为旅行距离，则各因素指标影响的重要性顺序为：α0＞β0＞kα＞ kβ＞α0×β0＞β0×kβ＞α0×kα＞kα×kβ；若L为耗费时间，则各因素指标影响的重要性顺序为：α0＞ kα×kβ＞β0＞kβ＞ kα＞α0×β0＞α0×kα＞β0×kβ。这也说明求解该问题不能同时满足两个目标函数最优。

由表4可得正交水平与因素的关系，如图1所示。图1中，目标函数为f(x)=minL，若L为旅行距离，各因素的最佳组合为，α0=1，β0=3，kα=0.0002，kβ=0.001；若L为耗费时间，各因素的最佳组合为，α0=1，β0=1，kα=0.002，kβ=0.001。

表4 各方案下实验指标结果分析

图1 正交水平与因素的关系

3 计算和结果分析

3.1 计算

对于TSP问题，考虑不同的城市规模，选用4个TSP基准算例[9]：Bayg29, Att48, Kroc100,A180。目标函数f(x)=minL，L为旅行距离，得到的解如表5所示。

表5 通过正交试验得到的TSP参数配置

对于JSSP问题，选用6个JSSP基准算例[10]：FT06, FT10, FT20, LA06,LA22,LA22。目标函数为单位工时，得到的解如表6所示。

表6 通过正交试验得到的JSSP参数配置

3.2 结果分析

表7给出了目标函数f(x)=minL（L为旅行距离），利用正交试验优化配置参数，求解以上4个算例的结果。

表7 参数配置后的计算结果

注：N-城市规模，Opt.-样例的已知最优解，Best-获得的最好解，Ave. -平均最优解，Orig.-优化配置以前的结果（随机20次的平均值）。

由表7可以看出，通过优化配置参数的最优解与随机解相比，更接近已知的最优解，说明正交试验的参数配置可以在较短的计算时间获得较好的寻优结果。若目标函数f(x)=minL（L为耗费时间）也得到相似结论。

对于JSSP问题，利用表6的参数配置求解对应基准算例[10]的结果如表8所示。从表8可看出，采用所配置的参数，在求解问题规模逐渐增大时，MACO能获得的较满意的解。

表8 JSSP基准测试问题的求解结果

图2 优化配置前后的MACO进化特征曲线

图2 给出了优化配置后的MACO求解FT06和FT10的进化特征曲线。从图2可以看出优化配置之后的MACO再求解JSSP问题时用了100次的迭代的收敛速度但是一般都在30到40次收敛，随着规模的增加收敛次数会逐渐增多。

4 结论

为了提高MACO求解时的寻优性能，本文采用正交试验的方法进行MACO的参数配置。当然，采用正交试验获得的参数优选值，具有一定的局限性。这些优选值是所设定的试验所用水平的某种组合，优选结果不会超越所取水平的范围。本文通过适当选取试验水平，对不同计算规模的TSP、JSSP基准算例的求解，所得到结果证明了MACO算法及通过正交试验获得的参数配置在求解精度和收敛速度上可以获得最优和准最优解。

[1] Macro D.Thomas stutzle.ant colony optimization[J].Cambridge:MIT Press,2003.

[2] 甘屹,李胜,张志伟.小生境蚁群优化及其在JSSP中的应用研究[J].中国机械工程,2010,21(10):1173-1178.

[3] 甘屹,齐从谦,杜继涛.基于蚁群算法的动态联盟伙伴选择研究[J].系统仿真学报,2006,18(2):517-520,525.

[4] Dorigo M,Gambardella L M.Ant Colony System:A Cooperative Learning Approach to the Traveling Salesman Problem[J].IEEE Transactions on Evolutionary Computation,1997,41(1):53-66.

[5] 郑向瑜,彭勇.求解旅行Agent 问题的自适应蚁群算法[J].计算机工程与应用,2010,46(16):52-54.

[6] 许瑞,陈华平,邵浩,等.极小化总完工时间批调度问题的两种蚁群算法[J].计算机集成制造系统,2010,16(6),1255-1264.

[7] 蒋玲艳,张军,钟树鸿.蚁群算法参数分析[J].计算机工程与应用,2007,43(20),31-36.

[8] 张晓玲,杨健,杜英国.基于正交实验的蚁群算法在车间调度问题中的应用[J].计算机系统应用,2010,19(4),152-156.

[9] http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/.[10]http://people.brunel.ac.uk/~mastjjb/jeb/orlib/jobshopinfo.html.