【《几种典型的改进蚁群算法综述》1900字】

第一章前言几种典型的改进蚁群算法综述目录TOC\o"1-3"\h\u7122几种典型的改进蚁群算法综述 1150861.1带精英策略的蚂蚁系统 1245261.2蚁群系统 2250261.3最大最小蚂蚁系统 3257551.4基于排序蚂蚁系统 3近年来，为了提升蚁群算法求解TSP的性能，不少学者提出了改进版本的蚁群算法，接下来将对当前四种经典改进蚁群算法做个简要介绍。1.1带精英策略的蚂蚁系统带精英策略的蚂蚁系统(AntSystemWithElitistStrategy,ASelite)作为一种典型的改进蚁群算法，其提升算法性能的手段来源于优化算法信息素更新规则。精英策略最早出现于遗传算法中，是为了避免算法中较优个体的丢失而选择直接将其保留至下一代中，有效避免较优基因被破坏从而提升算法的性能。蚁群算法的精英策略则略有不同，算法中定义寻找最优路径的若干数量的蚂蚁称为精英蚂蚁，算法会对精英蚂蚁获取的路径给以额外的信息素，加大最优路径上信息素，加速算法寻优，具体方式如下：(2-7)(2-8)式中，见公式(2-3)，表示采用精英策略对路径进行额外信息素增益，表示精英蚂蚁的数目，表示最优解所对应的路径，表示最优解的路径长度。带精英策略的蚂蚁系统通过加大最优路径上的信息素，能够有效提升算法求解速度，缩短了算法收敛的时间，但算法往往受到精英蚂蚁数目的影响。一般来说，精英蚂蚁数目设置过小，算法性能提升不够明显，相反，精英蚂蚁数目设置过大，容易导致算法因过快集中于次最优解周围搜索而陷入早熟收敛，因此选择一个合适的精英蚂蚁数目对该算法尤为重要。1.2蚁群系统蚁群系统(AntColonySystem,ACS)最早由M.Dorigo提出[61]，是当前算法性能最为有效的改进蚁群算法之一，它和基本蚁群算法之间区别主要包括以下几点：采用伪随机比例公式作为蚂蚁选择下个城市的策略，与基本蚁群算法状态转移规则相比存在不同的是，蚂蚁将以一定的概率直接从的最大值来选择下个城市，而不再是单纯地使用轮盘赌法，减少了算法搜索的随机性，提升了算法寻优的速度。算法伪随机比例公式S如下：(2-9)式中，q表示(0,1)之间的随机数，q0是(0,1)之间的常数，即当满足时，算法直接从剩余城市中选择最大值作为下个城市，否则依据(见公式(2-1))选择下个城市。引入信息素局部更新规则，一旦蚂蚁完成一次城市选择，立马对之前所走路径的信息素进行更新，更新方式具体如下：(2-10)(2-11)式中，表示局部信息素挥发速率，表示算法初始信息素，设置方式如公式(2-11)所示，其中N表示城市总数目，表示采用最近邻启发式算法得到的路径长度。算法在局部信息素更新的作用下，有效减少之间搜索过路径上的信息素，加大算法搜索其他路径的概率，从而提升算法搜索的多样性，改善算法的性能。为了提升算法寻优速度，算法只选取全局最优解进行全局信息素更新，更新方式如下：(2-12)蚁群系统通过改进全局信息素更新和状态转移规则、引入局部信息素更新，减少了算法运行时间，极大地提升了算法收敛速度，由于算法只对全局最优解进行信息素更新，算法因搜索多样性不足易陷入局部最优。不仅如此，先验知识概率对算法性能有着一定的影响，如选取过大，算法将过大集中于次优解周围探索从而发生早熟收敛，选取过小，算法状态转移规则退化为基本蚁群算法状态转移规则，算法性能下降。因此需要对进行合理选取。1.3最大最小蚂蚁系统最大最小蚂蚁系统(Max-MinSystem,MMAS)最早由ThomasStutzle提出[62]，是目前最常用的蚁群算法之一，其与基本蚁群算法存在如下区别：引入信息素上下界，即为了避免算法搜索过程中因路径上信息素差异过大致使算法陷入局部最优或发生早熟收敛，则需要对各个路径上的信息素设置在。初始信息素设置为。为了同时兼顾算法多样性和收敛速度，最大最小蚂蚁系统只选取一个解用以信息素更新，这个解来源于全局最优解或循环最优解，这和基本蚁群算法信息素更新方式存在很大不同，基本蚁群算法中会对所有蚂蚁获取的路径进行信息素更新。本节算法信息素更新方式如下：(2-13)式中，代表全局最优解或循环最优解的长度。最大最小蚂蚁系统最大的特点是将算法运行过程中的信息素值限制在内，从而有效避免算法因各个路径信息素差异过大而陷入局部最优。1.4基于排序蚂蚁系统 为了提升蚁群算法求解TSP的性能，近年来，有学者提出了基于优化排序蚂蚁系统(Rank-BasedVersionofAntSystem,ASrank)[63]。ASrank的核心思想是首先对所有蚂蚁得到的解进行评价并按照优劣性进行排序，选择部分数量的较优解进行全局信息素更新，其中信息素增益与解的优劣性正相关。定义表示较优解数目，信息素更新方式具体如下：(2-14)(2-15)其中，见公式(2-8)，表示t时刻排序为r的蚂蚁得到的解，为对应的路径长度。基于优化排序的蚂蚁系统，只选取较优的个解用以信息素更新，综合考虑了算法搜索多样性和收敛速度，有利于算法朝着全局最