基于蚁群算法的随机Petri网最优路径序列寻找  

Optimum Route Sequence Search in SPN Based on Ant Colony Algorithm

作　　者：黄光球[1] 何星[1] 苏海洋[1] 

机构地区：[1]西安建筑科技大学管理学院,西安710055

出　　处：《系统仿真学报》2008年第17期4555-4559,4581,共6页Journal of System Simulation

基　　金：高等学校博士点学科专项科研基金课题(20070703009);陕西自然科学基金项目(2007E217);陕西省教育厅自然科学专项基金项目(07JK076)

摘　　要：根据蚁群算法对SPN进行了一定的扩展,为SPN网络中的变迁增加了过滤和保留信息功能,为库所增加了过滤信息的功能,得出了一种带有记忆性的连续时间随机Petri网(MESPN)。当MESPN运行时,利用充足量的托肯在网络中行走并且在行走过程中留下信息素来调整托肯路径的选择,使大量蚂蚁的行走路线不断逼近SPN网中时间延迟更短的变迁序列,最终在最短变迁序列上形成清晰的蚁路,从而在一定程度上解决了复杂SPN网的最优路径寻找问题。该算法充分考虑了每个变迁真正实施时间的概率特性,可以计算任意网型的变迁延迟时间概率分布。仿真结果表明,托肯可以有效地在最短延时路径上形成蚁路并且能够求得从初始库所到网络中任意库所的最短路径。Based on the ant colony optimization algorithm and expansion of SPN, a memory extended and continuously timed SPN （MESPN）, whose transitions could filter and save information and places could filter information, was proposed When MESPN is running, enough ants （tokens） walk and leave odor in MESPN so that route selections of tokens can be adjusted, in this way it makes lots of ant walk routes approach to transition sequences with less delay. At last a clear ant walk route can be found on the transition sequence with least delay, and the route search problem of complex SPN is solved to a certain extend. The algorithm gives full consideration on the probability characteristics of each transition ＂s real firing time, can determine the probability distribution that each transition＇s delay time obeys for any type of SPN. The result of simulation shows that the ant walk route is found along the least delay route effectively by tokens, and the shortest route from initial places to every place of MESPN can be gotten.

关 键 词：蚁群算法 随机PETRI网 路径序列 优化 

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