蚁群-条件禁忌混合计算智能算法的Petri网路径寻优

Ant Colony/Conditional Tabu Search Hybrid Computational Intelligence Method for Optimal Routing Problem in Petri Net

Petri网(PN)的路径寻优问题一直是PN研究与分析中的重点和难点,尤其是研究、开发大型复杂PN的路径寻优智能算法将面临更大的挑战。根据传统蚁群算法(ACO)路径寻优特点,结合PN变迁规则,提出一种蚁群-条件禁忌(ACO-CTS)混合计算智能算法求解Petri网路径寻优问题。算法中,Petri网中的令牌类比成ACO中的蚂蚁,令牌/蚂蚁在变迁的过程中将信息素留在所经过的变迁中,通过信息素调整、控制令牌/蚂蚁的变迁,最终找到最短时延的变迁路径。寻优过程中,引入TS算法,根据不同条件通过禁忌最优解中的变迁,使令牌/蚂蚁在寻优过程中能跳出局部最优解,从而有效防止ACO算法路径寻优过早陷入局部最优解。仿真结果验证了所提方法的正确性和有效性。

Finding the optimal routing problem is always one of the most important issues in studying and researching Petri Net （PN）. Particularly to explore and exploit the rapid and effective intelligent methods for the solution of large-scale complicated Petri Net is posing great challenges for scientists. By combing the optimization characteristics of basic Ant Colony Optimization （ACO） method with the firing rules of transition in PN, a hybrid computational intelligence method, called as ACO/Conditional Tabu Search （CTS） algorithm, was proposed for finding the optimal routing in PN. According to the proposed method, the ant used in the ACO algorithm, was considered as token in Petri Net. By tuning the phenomenon, which was deposited on the passed transitions by token/Ant, and controlling the transition of token/ant, the shortest-time transition route could be found finally. Furthermore, during optimization the Tabu Search （TS） algorithm was introduced to forbid these transitions in better feasible solutions, and search process could be prevented from being trapped in local optima happened in ACO. The simulation results demonstrate the validity and effectiveness of the proposed method.