一种基于征税机制的蚁群优化方法

摘要

本发明涉及一种基于征税机制的蚁群优化方法。现有的算法容易出现停滞现象。本发明方法首先初始化蚂蚁个数、挥发系数和每条边上的信息素，并随机放置m个蚂蚁到n个城市上，其次让蚂蚁随机选择转移到城市j，将j插入到tabu_k(s)中，将城市j从allowed_k中删除，并对第k个蚂蚁经过的路径进行信息素浓度局部更新；然后计算每只蚂蚁的总路线长度，更新找到的最短路径，利用征税算子对路径上的信息素浓度进行调整，得到征税后的信息素浓度；最后满足h大于设定的值或者所有的蚂蚁选择同一条路径，则结束本次算法，同时输出全局优化的最佳路径。本发明方法能有效提高全局搜索能力和搜索速度。

主权项

1.一种基于征税机制的蚁群优化方法，其特征在于该方法包括如下步骤：步骤1、初始化蚂蚁个数m、挥发系数ρ和每条边上的信息素τ_ij(0)，随机放置m个蚂蚁到n个城市上；步骤2、初始化禁忌表tabu_k(s)，令s＝1，tabu_k表示第k个蚂蚁的禁忌表，tabu_k(s)表示禁忌表中第s个元素；步骤3、蚂蚁k(k＝1，2...m)随机选择转移到城市j，在时刻t蚂蚁k由城市i转移到城市j的概率为$P_{\mathrm{ij}}^k\left(t\right)=\frac{{\left[{\tau }_{\mathrm{ij}}\left(t\right)\right]}^{\alpha }·{\left[{\eta }_{\mathrm{ij}}\right]}^{\beta }}{\underset{k\in {\mathrm{allowed}}_k}{\Sigma }{\left[{\tau }_{\mathrm{ik}}\left(t\right)\right]}^{\alpha }·{\left[{\eta }_{\mathrm{ik}}\right]}^{\beta }}$其中τ_ij(t)表示时刻t时路径(i，j)上信息素浓度，启发因子η_ij＝1/C_ij，C_ij为路径(i，j)的距离，α为控制信息素浓度参数，β为路径长度参数，allowed_k＝{0，1，...，n-1}表示蚂蚁k下一步允许选择的城市集；然后将j插入到tabu_k(s)中，将城市j从allowed_k中删除，并对第k个蚂蚁经过的路径进行信息素浓度局部更新，得到${\tau }_{\mathrm{ij}}^{\prime }\left(t\right)=(1-\xi )·{\tau }_{\mathrm{ij}}\left(t\right)+\xi ·{\tau }_0$式中，ξ∈[0，1]，L_nn表示最近的相邻城市路径长度，如此重复直到每只蚂蚁都遍历n个城市；步骤4、计算每只蚂蚁的总路线长度，更新找到的最短路径，更新时刻t至t+1，对最优蚂蚁经过的路径进行全局更新，得到t+1时刻的信息素浓度τ_ij(t+1)，所述最优蚂蚁经过的路径为所有蚂蚁经过的最短路径；τ_ij(t+1)＝ρ·τ_ij(t)+(1-ρ)Δτ_ij式中，ρ为一个取值范围在0到1之间的常数系数，L_gb为到目前为止找出的全局最优路径；步骤5、利用征税算子(式4)对路径上的信息素浓度进行调整，得到征税后的信息素浓度其中，τ_cen(t)是时刻t的征税标准信息素浓度，ε表示征税税率，满足0＜ε＜1；步骤6、将Δτ_ij置零，重复步骤2至步骤5，记重复的次数为h，如果h大于设定的值或者所有的蚂蚁选择同一条路径，则结束本次算法，同时输出全局优化的最佳路径。