3.2 算法描述

实验发现，MMAS和ACS具有以下共同特点：

（1）参数的设置是依赖问题的，几乎没有规律可循，而且算法对参数比较敏感。

（2）在算法的运行过程中，信息素是按照指数下降的，这是算法易于早熟的一个原因。

（3）在算法的运行过程中，大量的信息素相同或相近。实际上，如果弧上的信息素相近，它们被选取的概率差异非常小，可以近似地把它们看成是等同的。

受此启发，有限级信息素蚁群算法把信息素分成有限个级别，用完全不同的方式更新信息素，并且信息素的更新量与目标函数值无关。为了阐述其工作原理并研究其性能，以TSP为测试问题。算法的主要流程如下：

步骤1，设定参数，初始化信息素；

步骤2，按照路径选择规则构造问题的解；

步骤3，按照信息素更新规则更新信息素；

步骤4，判断停止条件是否满足，若满足，算法终止；否则返回到步骤2。

在算法实现中，信息素被分成有限个级别，不同的级别按照一定的映射关系对应不同实数值，这样相同级别的弧的信息素相同。信息素更新通过级别的变动实现，对于当前最优弧，提高其级别，对于其他的弧，降低其级别。更新时只用加、减法。记h（i, j）是弧（i, j）上的级别，g（x）是单调增的正实函数，它实现从级别到信息素的映射关系，信息素更新规则如下：

（u1）∀（i, j）:h（i, j）←h（i, j）-r1；

（u2）如果f（⌒）＞f（wt），则=wt；

（u3）对于, ∀（i, j）∈, h（i, j）←h（i, j）+r2；

（u4）∀（i, j）:h（i, j）←max（1, h（i, j））；

（u5）∀（i, j）:h（i, j）←min（M, h（i, j））；

（u6）∀（i, j）:τ（i, j）=g（h（i, j））。

其中，f为目标函数，是当前最优解，wt 是本次迭代的最优解，参数r1、r2是正整数，r1＜r2，称r1 为惩罚级别数，参数r1 固定为1, r2 为奖励级别数，参数M是最大级别数。τmax是信息素上界。约定g（M）=τmax, g（1）=1。在实验中，g（x）一般选取为。前一个函数是线性函数，后一个函数是凹函数。这两个函数可以使信息素随着级别下降而衰减速度不变或逐渐变慢。

在信息素更新规则中，通过函数g（x）、奖励级别数、惩罚级别数协调控制级别的变化，进而控制信息素的变化。一方面，使蚁群能有效地在最优解的邻域搜索；另一方面，使蚁群具有一定的探索新区域的能力。由于更新量与目标函数值无关，因此对于两个呈常数比例的目标函数，如果算法采用完全相同的参数，算法性能将相同。

基本蚁群算法用两个参数表征信息素和启发信息的相对重要程度，而在FGPACO中把第一个参数内嵌到函数g（x）中，相应的路径选择规则如下。

假设蚂蚁在第k步位于第i个结点，它按照式（3-1）计算选择弧（i, j）的概率：

其中，η（i, r）表示弧（i, r）上的启发信息。在TSP问题中，启发信息一般选取为弧长的倒数。Ji是由所有未经过的点组成的集合。