解模式在蚂蚁算法中的应用

摘要：在对二次分配问题(QAP)解空间地形分析的基础上，提出了解模式在蚂蚁算法中的应用，并且在QAP的四类问题上进行了实验。实验结果表明对于第四类问题，加入解模式后算法的性能普遍提高，而对于第二类问题算法的性能会下降。

关键词：解模式；蚂蚁算法；地形分析；组合优化

中图分类号：TP183文献标识码：A

文章编号：1001-9081(2007)04-0952-04

0引言

蚂蚁算法求解过程有一个共同的特点：在搜索的过程中探测到最好解。一般情况下使用局部搜索算法来增强蚂蚁所得到的解。最好解的探测过程为提高算法的性能提供了一个途径，那就是了解所求解问题的解空间地形[1]。对于不同的地形，采用不同的策略，或者研究算法适合于哪种问题的地形。对组合优化问题解空间地形的研究对于提高蚂蚁算法的性能具有很重要的意义。FDC(FitnessDistanceCorrelation)分析[2]是地形分析的一种方案，最早在遗传算法（GeneticAlgorithm，GA）中应用[3]，通过研究适应度函数值（Fitness）和解之间的距离（Distance）的相关性来分析组合优化问题的地形。

模式是用来表示字符串集中的串在某些位置结构相似性的模板，如1000，1001，1010，1011这四个字符串蕴含在模式10**中。模式的概念最早在GA中得到应用，GoldBerg[4]论述了GA的模式理论。将模式应用到蚂蚁算法中，称之为解模式，以表示两个解之间的相似性；从另外一个方面讲，解模式也代表了整个搜索空间的一段区域，当然也可以表示和最优解的相似性。所以FDC分析和解模式的结合有利于提高蚂蚁算法的性能。

1相关工作

蚂蚁算法通过不断探测得到最好解的特性，使得对求解问题的解空间地形分析成为提高蚂蚁算法性能的一个途径。直观的说，适应度地形就象连绵不断的山脉区域，有山顶，有山谷。蚂蚁算法求解的过程就是在这个山脉区域中进行探索和探测，对于象QAP、TSP等求解最小值的问题，就是找到一个最低的山谷，而山谷、山顶等在区域中的分布会影响算法的性能。本节以QAP问题为例来说明组合优化问题的FDC分析过程。

1.1QAP问题描述

QAP是一个组合优化问题[5],其问题描述如下：将n个设施适当的建制在n个位置，每个位置两两之间有不同的流量和距离，运送代价定义为流量和距离的乘积，QAP问题的目标就是求解一个最佳指派(设施和位置的对应关系)，使得总体运送代价最小。形式化描述如下：

1.2FDC分析

适应度地形可以定义如下：

如果地形中具有很多的局部最优解，或者相邻解之间的相关性比较低，则适应度地形被认为是“凸凹不平”的，文献[3]提出了自相关函数来度量地形的凸凹不平度。文献[8，9]提出采用执行随机步的概念来考察地形结构的相关性。

另外一种度量地形的方法,即适应度函数值和到最优解的距离的相关性由文献[3，10]提出，在基因算法中，这种相关性一般叫做FDC(Fitness―DistanceCorrelation)[10]。相关性可以通过适应度函数值和距离的相关系数来得到，相关系数定义如下：

表1列出了部分QAP实例的FDC分析结果。对应第一类问题，相关系数非常低，几乎是0，所以，解的质量仅具有很弱的指导性[1]，在这些实例上，蚂蚁算法的性能相对较弱。而对于其他三类问题，相关系数较高。图1显示了四个QAP实例的F和D的关系图。

，从左上到右下依次为：tai60a、nug30，bur26a和tai60b。横坐标表示解到最优解的距离，纵总坐标表示解的目标函数值F和D的相关系数说明，对于相关系统高的实例来说，和最优解的距离越小，则解的质量也越好，也就是说在与最优解距离较小的解附近进行探测（exploitation）有可能找到最优解。这就为解模式的应用提供了依据，解模式代表了一段搜索区域，如果当前解与最优解的距离较小，就在解模式代表的区域内执行探测过程，这样算法就具有了指导性；而如果当前解与最优解的距离较大，则执行探索（exploration）过程。

1.3解模式简介

模式在GA中得到了很多的应用，文献[4]对GA中的模式理论做了深入的研究，计算了在选择操作下模式的增长性和交叉、变异操作下模式的存活概率。在模式理论中有几个比较重要的概念，如模式、模式的阶和模式的定义距等，分别定义如下：

定义1模式。表示字符串集中的串在某些位置结构相似性的模板，同时也代表了一段搜索空间的区域。

定义2阶。模式中确定位的个数。

定义3定义距。模式中最后一个确定位的下标减去第一个确定位的下标。

2解模式的应用

2.1QAP的解模式

将模式的概念运用到蚂蚁算法中，用其定义解和解之间的相似度，称之为解模式。同时解模式也代表整个解空间的一段区域，例如对于问题规模为n的QAP实例，整个的解空间大小为n!，而当解模式的阶大于0的情况下，要搜索的解空间就会减小为(n-O(H))!。

2.2解模式参数

从数据分析来看，影响解模式有以下参数：

1)参与确定解模式的解排列个数bp:在2.1节中分别选取了20个和21个较好的解排列。

2)位确定的概率阈值Ps:在2.1节中确定的概率阈值为0.5（也即比率为0.5）。

3)不同解排列的权重W:对于解的质量不同，位的权重应该也有所不同，在2.1节的分析中没有考虑到权重，而只是考虑了出现的频率。

对于实例tai20a，Ps=0.4时解模式的阶在12左右，Ps=0.6时，解模式的阶在5左右，随着Ps的增大，解模式的阶急剧下降；在bp变化情况下，解模式的阶和定义距没有变化，说明在解模式中位上的元素比较分散。对于实例nug30，在bp增大时解模式不变，因为此类问题中，在目标函数值相同的情况下对应的解排列较多，各位上的元素分散度不大，呈交替出现，这也和此类问题中每个实例对应多个最优解的特性吻合。对于实例bur26a，每位上的概率都集中在0.5附近，当Ps≥0.6时，阶模式的阶骤然下降，Ps对解模式的影响较显著。对于实例tai30b，在Ps=0.5时，随着bp的增大，对解模式的影响不是很大，但p增大时对解模式的影响较大。

通过数据来看，四个实例有一个共同的特点，就是解模式的阶和其定义距呈正比关系。

另外权重W对解模式的影响比较复杂，它和Ps共同作用对解模式影响较大，本文不对其做相关分析。

2.3解模式生成算法

算法1解模式生成算法

1)初始化集合S=,解模式sp;

2)从已经搜索到的解排列集合中获得最好的bp个解排列;

3)统计解排列中每位上最多的元素e及其所占bp的比率，如果eS，则S=S∪{e}，否则，将次多的元素放入S中，若还存在继续此过程；

4)根据概率Ps，确定将每位上的元素放入解模式sp中。

算法2加入解模式后的蚂蚁算法框架

1)设置参数，初始化信息素矩阵;

2)While不满足终止条件do

3)根据信息素构造解；

4)应用局部搜索；

5)将解排列加入到解排列集合中，并以目标函数值以升序排列；

6)应用解模式生成算法；

7)根据解模式生成解；

8)更新信息素；

9)End

算法1是解模式生成算法，在算法中只考虑了两个参数bp和Ps，没有考虑权重。算法2为应用了解模式后蚂蚁算法的基本框架，增加了5―7行，第5行是保存已经搜索到的解排列，第6行是生成解模式即算法1，第7行是根据解模式生成一个解。在我们的算法中还增加了一个增强过程，在当前解模式代表的一段搜索区域内，对解进行局部探索。

3实验结果

从QAPLIB[6]的四类实例中各选取了5个实例运用算法2进行实验，并同FANT[11]进行比较。

表5列出了FANT算法和FANT算法加入解模式后的结果比较（带下划线表示更好的解），FANT算法运行1000代，在问题规模大于30时参数R=5，其他情况下R=3。加入解模式后的算法中，在第50代以后启动解模式生成算法（参数bp=20，Ps=0.5），其他参数设置同FANT。从实验结果看，对于第二类问题加入解模式后，算法的性能普遍下降，这主要是因为此类实例的每个目标函数值对应多个解排列，太多元素的交替现象使得解模式对算法具有了副作用；而对于第四类问题，加入解模式后算法性能普遍提升，原因是在此类实例中，使用的bp个解排列中每位上元素的交替现象不多，使得解模式的质量提高；对于第一类问题来说，加入解模式后，对于大的实例算法性能下降；对于第三类问题来说，例如kra30a，在选择的bp个解排列中有多个相同目标函数值对应多个不同解排列的情况出现，干扰了解排列的生成，使得解模式的质量下降，也使得算法的性能下降。

4结语

从GA算法中引入解模式的概念，用来在蚂蚁算法中表示解和解之间的相似性，通过FDC分析可知，解模式在蚂蚁算法中有一定的应用价值。本文对解模式生成算法的参数bp和Ps

做了具体实验分析，指出了对每类具体实例的影响特性。通过在蚂蚁算法中的应用可以看出，解模式对算法的性能有影响，对于第四类问题具有较好的性能提升，而对于第二类问题，解模式使得算法的性能下降，对于第一类和第三类问题，对算法的影响和具体的实例相关，如果在解模式生成算法中使用的bp个解排列中，相同目标函数值对应的不同解排列越多，对解模式的生成越有干扰，会使得解模式对算法的性能下降，如kra30。

通过实验，解模式对蚂蚁算法还有一定的实用价值，关键的问题是解排列的质量如何，好的解排列使得算法更快收敛到最优解，并且对算法具有正的反馈作用，否则解模式会使算法的性能下降。

在将来的研究中，将在算法中增加影响解模式的第三个参数：不同解排列的权重W，使得每个解排列对解模式生成的贡献有所不同。另外针对不同的特定实例，研究解模式的质量评价问题也是将来研究的一个重点。

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