3.3 算法随机模型与收敛性质分析

下面讨论算法的随机模型，分析算法与有限马氏链之间的关系。有关随机过程和有限马氏链的内容见文献[3]。本节中的记号及其意义见表3-1。马氏链有如下重要性质。

引理1[3]对于有限状态马氏链，不管从何状态出发，经过n步转移到任一瞬时状态的概率随着n无限增大而趋近于0，反之，离开所有瞬时状态的概率随着n无限增大而趋近于1。

性质1 在FGPACO算法中，X是有限状态马氏链。

证明：X是有限状态的；由算法的路径选择规则可知，X是马氏链。

证毕。

性质2 在FGPACO算法中，若sn, sm∈Γ，关于sn 到s m 的转移概率有以下结论：

（1）若f（H（sn））＜f（H（sm）），则=0。

（2）若H（sn）=H（sm），且存在某个弧（i, j）∈H（sn），使得G（i, j）（sn）＞G（i, j）（sm），则=0。

证明：由信息素更新规则中的（u1）、（u2）、（u3），并且由定义可以得出结论。

证毕。

这说明状态转移时，或者当前最优解改变，且目标函数值下降；或者当前最优解不变，但它对应的每段弧的信息素递增。如果当前最优解不变，由（u1）、（u3），每段弧的信息素是收敛的（由单调有界性可知）。经过有限次迭代后，所有弧的信息素将保持不变，此时当前最优解对应的弧上信息素都是τmax，其他弧上的信息素都是1。按照停留时间可以对有限马氏链的状态进行分类。

定义1（滞留态、最优态和正常态） 对于s∈Γ，如果当前最优解对应的弧上信息素都是τmax，其他弧上的信息素都是1，则称s是滞留态；特别地，当H（s）是全局最优解时，则称s为最优态，记为s*；其他状态称为正常态。

定理1（FGPACO的概率特性）对于FGPACO，具有状态sn=（τ（n）, w（n））的随机过程是有限状态马氏链，它具有以下性质：

（1）所有状态不是瞬时态，就是吸收态，并且吸收态s*是最优态，它具有正常返性。

（2）离开正常态只需一次迭代，离开每一个滞留态的迭代次数服从几何分布。

证明：（1）对于最优态s*，由（u1）、（u2）、（u3）可知它只可能转移到自己，即=1，因此是吸收态，从而具有正常返性。由性质2可知其他状态都是瞬时态。

（2）对于滞留态，记其对应的当前最优解为w。因为在离开该滞留态之前，每段弧上的信息素保持不变，从而选路概率也不变，因此它服从几何分布。

证毕。

定理2（FGPACO的收敛性） FGPACO算法收敛到全局最优解的概率随着n无限增大而趋近于1。

证明：注意到FGPACO每次迭代时，都保留了最优解，由性质2、引理1及定理1的结论（1），可知结论成立。

证毕。

对Γ中的元素按照以下约定排序：①对应目标函数值升序排列；②如果目标函数值相同，最优解对应信息素降序排列，其他弧上信息素升序排列。

性质3 概率转移矩阵P是下三角矩阵，且, Ik 是单位矩阵，B是下三角矩阵，它的最大特征值λ小于1。

证明：注意到Γ中的元素按照上面的约定排序，由性质2和定理1可知结论成立。

证毕。

由于B的最大特征值小于1，则（I-B）-1是可逆阵。记Mi=I+B+B2+…+Bi-1，则。对于任意矩阵A（行（列）向量可以看成行（列）数为1的矩阵），记其范数为‖A‖（有关矩阵范数参见文献[4]）。令B的范数为λ，算法的收敛速度满足以下结论。

定理3（FGPACO的收敛速度）πi 收敛到π*的收敛速度满足‖πi-π*‖≤O（λi），也就是说，算法以不大于λ的收敛比率收敛。

证明：‖πi-π*‖=‖π0Pi-π0P∞‖

证毕。