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

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

作　　者：石立宝[1] 张舒[1] 姚良忠[2] 倪以信[1] Masoud Bazargan 

机构地区：[1]清华大学深圳研究生院电力系统国家重点实验室深圳研究室,深圳518055 [2]AREVA输配电集团技术中心,英国斯塔福德郡ST17 4LX

出　　处：《系统仿真学报》2011年第11期2400-2405,共6页Journal of System Simulation

基　　金：国家重点基础研究发展规划资助(2004CB217900);高等学校博士学科点专项科研基金-新教师基金资助课题(200800031068)

摘　　要：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.

关 键 词：蚁群算法(ACO) TABU搜索 PETRI网 变迁 令牌 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]