改进的遗传混合蚁群算法在tsp问题中的应用

《改进的遗传混合蚁群算法在tsp问题中的应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、改进的遗传混合蚁群算法在TSP问题中的应用摘要：为了提高基本蚁群算法的收敛性能和全局求解能力，对基本蚁群算法进行了改进，提出了一种改进的遗传混合蚁群算法。在每代进化中保留最优解和次优解的公共解集后引入遗传操作中的交叉算子进行运算，并采用自适应改变信息素挥发系数的方法，加快了算法收敛速度，提高了解的全局性。通过对TSP问题的仿真运算表明，改进的遗传混合蚁群算法在收敛速度和解的全局性上都有较大的改善。　　关键词：蚁群算法；遗传算法；交叉算子；自适应；TSP　　：TP391文献标志码：B：1006-8228（2012）11-31-02　　Applica

2、tionofimprovedgeichybridantcolonyalgorithminTSP　　XuDeming　　（HuizhouUniversity，Huizhou，Guangdong516007，China）　　Abstract：ToimprovetheefficiencyofconvergenceandtheglobalabilityofbasicACA，anovelhybridalgorithmisproposed，provedbinationofGAandACA.Crossoperatoriscalculatedafterreser

3、vingtheintersectionofthebestsolutionandthesecondbestsolutionineveryevolution，andtheadaptivechangepheromonevolatilecoefficientisaffected.Convergencespeedisacceleratedandtheglobalabilityofthealgorithmisimproved.ThesimulationsforTSPproblemshoprovedalgorithmhasbetterconvergenceef

4、ficiencyandglobalability.　　Key（ACA）；geicalgorithm（GA）；crossoperator；theadaptivechange；TSP　　0引言　　旅行商问题（TravelingSalesmanProblem，TSP）又称货郎担问题，是一个著名的组合优化问题，也是一个典型的、易于描述却难于处理的NP完全问题[1]。由于该问题的实际模型在路径、X络、分配、基因测序和机器人控制等方面有着广泛的应用[2]，故长期以来一直吸引着许多领域的研究人员对其算法改进的关注。　　蚁群算法是一种求解组合最优化问题的新型通用

5、启发式方法，该方法具有正反馈、分布式计算和贪婪启发式搜索的特点。由于蚁群算法容易出现停滞现象，即搜索进行到一定程度后，所有个体所发现的解完全一致，不能对解空间进一步搜索，不利于发现更好的解，而且蚁群中多个个体的运动是随机的，当群体规模较大或X络结构较为复杂时，要找出一条较好的路径需要较长的搜索时间。　　遗传算法因其具有良好的鲁棒性、可并行性与全局优化性而在求解组合最优化问题时获得了广泛的应用。但是，在实际应用中，遗传算法早熟收敛等缺陷没有从根本上消除，因此，通常存在计算量大的问题，从而导致定位速度慢。　　遗传算法和蚁群算法都是受生物进化论的启发而

6、提出来的仿生算法，两种算法都应用于求解组合优化问题上，并取得了一定的成果。本文在基本蚁群算法的基础上，给出一种改进的遗传混合蚁群算法，这种改进后的混合算法利用遗传算法中交叉与变异的优点，通过引入交叉算子增强蚁群算法寻找全局最优解的能力和加快算法的收敛速度，并采用自适应改变ρ值的方法提高了算法的全局搜索能力。仿真实验表明，改进后的新算法能在保证一定的收敛速度的基础上改进算法的全局收敛性。　　1基本蚁群算法原理（基本ACA）　　蚂蚁从某一地点出发，按照状态转移规则选择下一路径，该规则也被称为“随机比率规则”。蚂蚁选择路径的转移概率为：　　⑴　　式⑴中

7、τij（t）为t时刻路径（i，j）上的信息量；蚂蚁在运动过程中用禁忌表tabuk来记录蚂蚁k走过的城市；allowedk={c-tabuk}表示蚂蚁k下一步允许选择的城市；α为信息启发式因子，反映了蚂蚁在运动过程中所积累的信息在蚂蚁运动时所起的作用；β为期望启发式因子，反映了蚂蚁在运动过程中启发信息在蚂蚁选择路径中的受重视程度。ηij（t）为启发函数，其表达式如下：　　⑵　　式⑵中dij表示相邻两个城市之间的距离。对蚂蚁k而言，dij越小，则ηij（t）越大，也就越大。每只蚂蚁走完一步或者完成一次循环，要对残留的信息进行更新处理，每次迭代完成后，

8、各路径上的信息素都需要进行更新，其公式如下：　　⑶　　⑷　　式⑶中ρ表示信息素挥发系数，1-ρ表示信息素的残留因子；式⑷中表示第k只摘要