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

《基于基因表达式编程的混合蚁群算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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

2、mationEngineering，GuangxiTeachersEducationUniversity，Nanning530023，China）Abstract：Antcolonyalgorithmhascapabilityofdistributedparallelglobalsearch，convergestotheoptimalpathbyaccumulatingandupdatingthepheromone，butlackofinitialpheromone，slowconvergencespeed.Tosolvethisproblem，

3、Thispaperpresentsanewhybridalgorithmwhichgeneratepheromonedistributionbygeneexpression11programmingfirst，thentakeadvantageoftheantcolonyalgorithmstofindoptimalsolutions.BysolvingcomplexTSPproblemofsimulationdataexperiments，itprovedthetheefficiencyofthehybridantcolonyalgorithm

4、basedongeneexpressionprogramming.Keywords：Antcolonyalgorithm；geneexpressionprogramming；GEP葡萄牙进化生物学家Ferreira通过借鉴生物遗传的基因表达规律，将遗传算法GA（GeneticAlgorithm）和遗传编程GP（GeneticProgramming）的优点融合在其中，经过五年时间的研究，在2000年提出了进化计算家族中的革命性的新成员基因表达式编程GEP（geneexpressionprogramming）。11基因表达式编程GEP是借鉴生物界的自

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

6、0000倍，实现了又一次跨学科的革新。蚁群算法是通过信息素的累积和更新而收敛于最优路径，具有分布、并行、全局收敛能力。但初期信息素匮乏、导致算法速度慢，为了克服蚁群算法的缺陷。为此首先利用基因表达式编程的随机搜索、快速性、全局收敛性产生有关问题的初始信息素分布。然后，充分利用蚁群的并行性、正反馈机制以及求解效率高等特征。这样融合后的算法，在时间效率和求解效率都比较好的启发式算法。1基因表达式编程简介1.1GEP算法工作原理跟所有的演化算法一样，GEP算法的基本步骤也是从随机产生的一定数量的染色体个体（初始种群）开始；然后对这些染色体进行表达，依据

7、一个适应度样本集（问题的输入）计算出每个个体的适应度；最后个体按照适应度值被选择，进行遗传操作，产生具有新特性的后代。该过程一直重复若干代，直到发现一个最优解。GEP的核心技术就是将变异过程和评估过程完全分开。它的变异过程使用定长的线性符号串，而评估过程采用表达式树ET（Expression11Tree），两者之间可以通过规则进行相互转化。对每个具体问题来说，算法执行之前必须确定产生染色体的符号，即选择适合问题解的函数集和终点集；确定基因的结构及基因的头长，每个染色体中的基因数和各基因的连接运算符号；最后还要选择一个适应度函数，确定遗传控制参数。

8、1.2GEP的基因结构GEP遗传操作的基本单位是染色体，染色体由一个或多个基因构成。基因由线性定长的字符串组成。GEP的基因型个体由定长