基于基因表达式编程的混合蚁群算法

周海燕

摘 要：蚁群算法具有分布式并行全局搜索能力，通过信息素的积累和更新收敛于最优路径上，但初期信息素匮乏，求解速度慢。针对此问题，本文提出了一种先用基因表达式编程生成信息素分布，再利用蚁群算法求优化解的新的混合算法。并通过求解复杂TSP问题的仿真数据实验验证了这种基于基因表达式编程的混合蚁群算法的高效性。

关键词：蚁群算法；基因表达式编程；GEP

Hybrid ant colony algorithm based on gene expression programming

Zhou haiyan

（Shool of Computer and Information Engineering，Guangxi Teachers Education University，Nanning 530023，China）

Abstract：Ant colony algorithm has capability of distributed parallel global search ，converges to the optimal path by accumulating and updating the pheromone，but lack of initial pheromone，slow convergence speed.To solve this problem，This paper presents a new hybrid algorithm which generate pheromone distribution by gene expression programming first，then take advantage of the ant colony algorithms to find optimal solutions.By solving complex TSP problem of simulation data experiments ，it proved the the efficiency of the hybrid ant colony algorithm based on gene expression programming.

Key words：Ant colony algorithm；gene expression programming；GEP

葡萄牙進化生物学家Ferreira通过借鉴生物遗传的基因表达规律，将遗传算法GA（Genetic Algorithm ）和遗传编程GP（Genetic Programming）的优点融合在其中，经过五年时间的研究，在2000年提出了进化计算家族中的革命性的新成员基因表达式编程GEP（gene expression programming）。

基因表达式编程GEP是借鉴生物界的自然选择和遗传机制，在GA和GP的基础上发展起来的全新的随机搜索和优化算法。它虽然具有跟传统GA和GP相似的计算机理，但是在个体的编码方法和结果的表现上有着明显的区别。在GEP中，计算机程序被编码成固定长度的线性符号串（染色体），然后在进行个体适应度计算时，被表示成不同形状和大小的表达树，从而解决问题。这种把基因型（染色体）和表现型（表达式树）既分离又互相转化的结合，使得GEP克服了GA损失功能复杂性的可能性和GP难以再产生新的变化的可能性，提高了解决问题的能力和效率。Ferreira指出基因表达式编程的效率比传统的遗传算法和遗传编程高出100～60000倍，实现了又一次跨学科的革新。

蚁群算法是通过信息素的累积和更新而收敛于最优路径，具有分布、并行、全局收敛能力。但初期信息素匮乏、导致算法速度慢，为了克服蚁群算法的缺陷。为此首先利用基因表达式编程的随机搜索、快速性、全局收敛性产生有关问题的初始信息素分布。然后，充分利用蚁群的并行性、正反馈机制以及求解效率高等特征。这样融合后的算法，在时间效率和求解效率都比较好的启发式算法。

1 基因表达式编程简介

1.1 GEP算法工作原理

跟所有的演化算法一样，GEP算法的基本步骤也是从随机产生的一定数量的染色体个体（初始种群）开始；然后对这些染色体进行表达，依据一个适应度样本集（问题的输入）计算出每个个体的适应度；最后个体按照适应度值被选择，进行遗传操作，产生具有新特性的后代。该过程一直重复若干代，直到发现一个最优解。

GEP的核心技术就是将变异过程和评估过程完全分开。它的变异过程使用定长的线性符号串，而评估过程采用表达式树ET（Expression Tree），两者之间可以通过规则进行相互转化。对每个具体问题来说，算法执行之前必须确定产生染色体的符号，即选择适合问题解的函数集和终点集；确定基因的结构及基因的头长，每个染色体中的基因数和各基因的连接运算符号；最后还要选择一个适应度函数，确定遗传控制参数。

1.2 GEP的基因结构

GEP遗传操作的基本单位是染色体，染色体由一个或多个基因构成。基因由线性定长的字符串组成。GEP的基因型个体由定长的头部和尾部组成，头部元素∈{函数集F}∪{终结符集T}，尾部元素∈{终结符集T}（其中函数集F由求解问题需要的所有函数运算符组成，终止符集T由描述问题的解的已知符号变量或常数组成），并且头部长度h和尾部长度t须满足以下关系：

其中nmax为函数集F的最大操作数目，在个体表现型中表现为树型结构中节点的最大分支数，这一设计使得基于基因型个体的遗传操作都具有很好的合法性。GEP的个体表现型被称为ET树。ET树是通过顺序扫描基因型个体的字符，按照层次顺序构成。例如，若定义函数集F={*，/，+，-，Q}（依次为乘除加减和开方运算），终止符集T={c，d，e，f}，则nmax=2，取头部长h=5由式（1）得到尾部长t=6假定有基因型个体：Q/+-cfed，它可以转化为如图1所示的ET树：

1.3 GEP算法基本步骤

⑴输入相关参数，创建初始化群体；

⑵计算每个个体的适应度函数，若不符合结束条件，继续下一步，否则结束；

⑶保留最好个体；

⑷选择操作；

⑸变异；

⑹插串操作（IS插串RIS插串Gene插串）；

⑺重组（1-点重组2-点重组多基因重组）；

⑻若达到设定最大进化代数或计算精度，则进化结束，否则转到步骤2）。

2 基于基因表达式编程的混合蚁群算法

2.1 基本思想

蚁群算法是群集智能算法的一种，它属于自然计算中的一类，模拟的是生物系统——社会系统，即利用群体与环境以及个体之间的互动行为来搜寻最优解。GEP算法则属于演化计算一个重要分支，它模拟基因进化过程，利用种群进化来搜寻最优解。首先利用GEP算法的随机搜索、快速性、全局收敛性在大范围内寻找一组粗略解，然后以这组粗略解为蚁群算法的初始路径，利用蚂蚁算法的并行性、正反馈机制以及求解效率高等特性求解出最优解。

2.2 基于GEP算法的混合蚁群算法原理及流程

GEP算法一开始，先随机的产生种群。对于TSP问题，种群里面的每一个个体（或叫染色体）都代表一组城市的排列，其质量高低用一个适应函数来评价。每一个个体按照一定的概率，通常是按照适应值被选择进行交叉、倒串、插串、变异产生新的下一代种群。适应值高的个体更有机会来繁殖下一代，随着连续的繁殖，种群趋于收敛于高的那些种群，从而找到可能的最优解。

（1）编码与适应值函数。结合待解决问题，采用十进制实数编码，适应值函数结合目标函数而定。在 TSP问题中以城市的遍历次序作为遗传算法的编码，例如：（7，4，9，5，6，1，2，8，10）代表从城市7出发，经由城市4-9-5-6-1-2-8-10，最后又回到城市4的一条路径。适应值函数取为：

其中L为遍历所有城市的路径长度。

（2）种群生成与染色体选择。利用随机函数生成一定数量的十进制实数编码种群，根据适应值函数选择一对染色体父串进行交配。在此利用轮盘式选择策略（roulette wheel selection）进行选择，根据适应函数值选择准备进行交配的染色体父串。

⑶变异算子。变异作用在单个染色体上，对染色体的每一位进行随机测试，当满足变异概率时，讲重新产生该位的编码。如果变异位在基因头部，可以重新选择所有的符号，否则只能选择终结符。

⑷倒串算子。倒串算子作用于染色体某个基因的头部，它随机地在基因头部选择一段子串，然后以该子串中间字符为对称中心各字符位置顺序对调。

⑸插串算子。插串是GEP所特有的遗传算子。它随机在基因中选择一段子串，然后将该子串插入头部随机指定的一个位置（但不能是第一个位置），将头部的其他符号向后顺延，超过头部长度的编码将被截去。

⑹单点重组。单点重组作用在两个父代染色体上，随机选择一个交叉位置，互换交叉点后面的染色体部分，得到两个子代染色体。

⑺信息素的初值设置。根据GEP算法的执行，得到了一定的路径信息素。另外，为了防止算法过早收敛，陷入局部最优解，这里采用最大-最小蚂蚁系统（MMAS）中的方法，即将各路径信息素初值设为最大值τmax。综合这两部分，信息素的初值τs设置为：

其中：τc是一个常数，相当于MMAS算法中的τmin，τG是遗传算法求解出的最优解所转换的信息素值。

⑻信息素的更新.采用蚁周模型进行信息素的更新公式如公式（2.3），路径上的轨迹更新方程为公式（2.4）。

τij（t）为t时刻边e（i，j）上外激素的强度，Δτkij表示第K只蚂蚁在本次循环中留在路径ij上的信息素，Δτij表示本次循环中路径ij上的信息增量，ρ表示轨迹的持久性。

2.3 算法流程

步骤1参数初始化。令时间t=0，循环次数nc=0，设置最大初循环次数ncmax，信息素Q，将m只蚂蚁置于n个元素（城市）组成的集合C中，令有向图上每条边（i，j）的初始化信息量τij（t）=const，且初始时刻Δτij（0）=0，其中const为常数；

步骤2 循环次数nc=nc+1；

步骤3 蚂蚁的禁忌表索引号k=1；

步骤4 蚂蚁数目k=k+1；

步骤5 蚂蚁个体根据状态转移式计算的概率选择元素（城市）并前进，j∈{c-tabuk}；

步骤6 修改禁忌表指针，将蚂蚁移动到新的元素（城市），并把该元素（城市）移动到该蚂蚁个体的禁忌表中；

步骤7 若k

步骤8 选出本次循环中的最优路径和次优路径，按照交叉算子中的方法进行交叉运算，并保留最优路径，记其为L；

步骤9 按照2.2中的方法进行变异运算；

步骤10 根据式（2.3）、（2.4）、（2.5）局部更新每条路径上的信息量；

步骤11 根据式（2.3）、（2.4）、（2.5）全局更新每条路径上的信息量；

步骤12 若满足结束条件，即如果循环次数nc≥ncmax，则循环结束并输出程序计算结果，否则清空禁忌表并跳转到步骤2。

3 实验结果与分析

本文通过对TSPLIB数据库中Oliver30问题和Eil51问题进行仿真研究，平均运行30次作为仿真结果，来验证GEP蚁群混合算法的有效性。实验中所采取的各项参数如下：α=1，β=6，Q=140，Oliver30问题中蚂蚁数目m=20，设置最大循环次数300次；在Eil51问题中蚂蚁数目m=30，設置最大循环次数600次。实验数据结果如表1所示。

對实验结果的数据进行分析可以看出，本文提出的算法求出的平均解和最优解都要优于基本的蚁群算法的求解结果，同时本文算法收敛性能也比基本蚁群算法好，本文给出的一类融入GEP算法的蚁群算法的全局性和收敛性比基本蚁群算法都有所提高，因此是一种有效的改进算法。

4 结束语

蚁群算法是一种新型的进化算法，它与其它进化算法同样存在易陷入局部最优值，存在过早收敛的现象。本文通过融入GEP算法，引入交叉算子和变异算子扩大了算法的搜索空间，同时在交叉运算中保留解中的公共最优路径加快了算法的收敛速度，改进后蚁群算法可以提高算法的全局搜索能力和收敛性能。通过对TSP问题的仿真表明本文算法是一种有效的改进算法。

[参考文献]

[1]Li M，Wang H，Li P.Tasks mapping in multi-core based system：Hybrid ACO&GA approach[C].Beijing，China：Proceedings of the 5th International Conference on ASIC，2003：355-340.

[2]Pilat M L，White T.Using genetic algorithms to optimize ACS-TSP [C].Brussels，Belgium：Proceedings of 3rd International Workshop on ant Algorithms/ANTS2002，LNCS，2002：282-287.

[3]元昌安.基于GEP的函数发现的智能模型库关键技术研究[D].成都：四川大学博士论文，2006.

[4]左劼.基因表达式核心技术研究[D].成都，四川大学计算机学院，2004.

[5]唐常杰，张天庆，左吉力，等.基于基因表达式编程的知识发现沿革、成果和发展方向，2004，24（10）：7-10.

[6]Li Minqiang，Kou Jisong，Lin Dan，et al.The theory and ap -plication of genetic algorithm [M].Beijing：Science Press，2002.

[7]李敏强，寇纪淞，林丹，等.遗传算法的基本理论与应用[M].北京：科学出版社，2002.336～343.

[8]丁建立，陈增强，袁著祉.遗传算法与蚂蚁算法的融合[J].计算机研究与发展，2003，40（9）：1351-1356.