文档介绍：解模式在蚂蚁算法中的应用
　　摘要：在对二次分配问题(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分析过程。
　　
　　QAP是一个组合优化问题[5],其问题描述如下：将n个设施适当的建制在n个位置，每个位置两两之间有不同的流量和距离，运送代价定义为流量和距离的乘积，QAP问题的目标就是求解一个最佳指派(设施和位置的对应关系)，使得总体运送代价最小。形式化描述如下：
　　
　　适应度地形可以定义如下：
　　如果地形中具有很多的局部最优解，或者相邻解之间的相关性比较低，则适应度地形被认为是“凸凹不平”的，文献[3]提出了自相关函数来度量地形的凸凹不平度。文献[8，9]提出采用执行随机步的概念来考察地形结构的相关性。
　　另外一种度量地形的方法,即适应度函数值和到最优解的距离的相关性由文献[3，10]提出，在基因算法中，这种相关性一般叫做FDC(Fitness―DistanceCorrelation)[10]。相关性可以通过适应度函数值和距离的相关系数来得到，相关系数定义如下：
　　表1列