基于约束优化的Petri网可达性分析

doi:10.3724/SP.J.1087.2013.01128

计算机应用 ›› 2013, Vol. 33 ›› Issue (04): 1128-1131.DOI: 10.3724/SP.J.1087.2013.01128

基于约束优化的Petri网可达性分析

杨夏妮,龙法宁,张远夏

玉林师范学院计算机科学与工程学院，广西玉林 537000

收稿日期:2012-10-29 修回日期:2012-12-11 出版日期:2013-04-01 发布日期:2013-04-23
通讯作者: 龙法宁
作者简介:杨夏妮(1980-)，女，广西玉林人，讲师，硕士，主要研究方向：Petri网；龙法宁(1978-)，男，广西玉林人，讲师，硕士，主要研究方向：模式识别；张远夏(1975-)，男，广西玉林人，副教授，主要研究方向：模式识别。
基金资助:
广西壮族自治区教育厅科研项目(201106LX515);玉林师范学院青年科研项目(2010YJQN19);玉林师范学院专项(2012YJZX04)

Reachability analysis of Petri net based on constraint optimization

YANG Xia'ni,LONG Faning,ZHANG Yuanxia

School of Computer Science and Engineering, Yulin Normal University, Yulin Guangxi 537000, China

Received:2012-10-29 Revised:2012-12-11 Online:2013-04-01 Published:2013-04-23
Contact: LONG Faning

摘要/Abstract

摘要： Petri网的可达性判定问题是进行Petri网分析的基础。通过分析目前求解Petri网可达问题的判定方法和基于约束程序的Petri网可达问题判定方法，提出一种基于约束优化的Petri网可达问题判定方法，该方法是在状态方程法的基础上，利用约束程序寻求可行解，再利用优化求最优解，从而减少问题搜索的分支，达到减少状态方程的解空间的目的。最后通过实例的求解验证算法能够提高判定效率。

关键词: Petri网, 可达性, 状态方程, 约束, 优化

Abstract: The judgment of reachability is one of the fundamental issues in Petri net analysis. The paper analyzed the existing method and the method based on constraint programming for the reachability of Petri net, and then proposed the judgment method for reachability problem based on constraint optimization. The method was based on the state equation method, separately using the constraint programming and the optimization to seek the feasible solution and the optimal solution, thereby decreased the searching path and attained the purpose of reducing the solution space of the state equation. Finally an example was given to prove that the algorithm can improve the determination efficiency.

Key words: Petri net, reachability, state equation, constraint, optimization

中图分类号:

TP311

杨夏妮龙法宁张远夏. 基于约束优化的Petri网可达性分析[J]. 计算机应用, 2013, 33(04): 1128-1131.

YANG Xia'ni LONG Faning ZHANG Yuanxia. Reachability analysis of Petri net based on constraint optimization[J]. Journal of Computer Applications, 2013, 33(04): 1128-1131.

参考文献

［1］PETRI C A．Konmmunkation mit automaten［C］// Communication with Automata. Bonn：[s.n.], 1966:386-390.

［2］彭建兵,焦莉.基于极小T_不变量增加的Petri网可达性分析［J］.计算机应用研究,2010,27(10):3798-3802.

［3］袁崇义.Petri网原理与应用［M］.北京：电子工业出版社，2005.

［4］李凤英,古天龙,徐周波.Petri网的符号ZBDD可达树分析技术［J］.计算机学报,2009,32(12):2420-2428.

［5］李志武,王安荣,贾建援.Petri网不变式和状态方程的求解［J］.西安电子科技大学学报:自然科学版,2003,30(2):259-263.

［6］TALAJASHI K, ONO I, SATOH H, et al. An efficient genetic algorithm for reachability problem［C］// Proceedings of the IEEE Inter-national Conference on Robotics and Automation. Piscataway, NJ: IEEE Press, 1977:89-98．

［7］胡娟，刘力惠. Petri网可达性的综合判定法［J］. 软件学报，2005，15(7):949-955.

［8］LAN Q Y, QIN H S, ZHANG X L. Analysis for reachability problem of bounded Petri net using key constraints method［C］// IEEE ICCA'07: Proceedings of the Sixth IEEE International Conference on Control and Automation. Washington, DC: IEEE Computer Society, 2007,2:2829-2833.

［9］于枫，罗军舟，李伟.基于T_不变量消除的Petri网合法引发序列判定算法［J］.解放军理工大学学报:自然科学版，2008，9(5):522-527.

［10］于枫，罗军舟，李伟，等. 一种基于进程验证的Petri网可达性判定方法［J］.计算机学报，2010，33(2):288-299.

［11］BENASSER A，YIM P. Railway traffic planning with Petri nets and constraint programming ［J］. Journal of Européen des Systèms Automatisés: JESA, 1999,33(8/9): 959-975.

［12］BOURDEAUDHUY T, HANAFI S, YIM P. Solving the Petri nets reachability problem using the logical abstraction technique and mathematical programming ［C］// CPAIOR'04, LNCS 3011. Berlin: Springer, 2004:112-126.

［13］BOURDEAUDHUY T, YIM P, HANAFI S. Efficient reachability analysis of bounded Petri nets using constraint programming ［C］// 2004 IEEE International Conference on Systems, Man and Cybernetics. Piscataway, NJ: IEEE Press, 2004,2:1870-1875.

［14］DRISS O B, YIM P, KORBAA O, et al.Reachability search in timed Petri nets using constraint programming systems ［C］// 2004 IEEE International Conference on Systems, Man and Cybernetics. Piscataway, NJ: IEEE Press, 2004,5:4923-4928.

［15］覃海生,蓝乾艺,杨夏妮. 基于约束程序的变迁约束可达问题判定研究［J］. 广西大学学报:自然科学版, 2007, 32(3): 307-311.

[1]	李开荣, 刘爽, 胡倩倩, 唐亦媛. 基于转角约束的改进蚁群优化算法路径规划[J]. 计算机应用, 2021, 41(9): 2560-2568.
[2]	牛瑞华, 杨俊, 邢斓馨, 吴仁彪. 基于卷积注意力模块和双通道网络的微表情识别算法[J]. 计算机应用, 2021, 41(9): 2552-2559.
[3]	陈俊, 何庆. 基于余弦相似度的改进蝴蝶优化算法[J]. 计算机应用, 2021, 41(9): 2668-2677.
[4]	王怀, 王展青. 非线性约束下的准单应变换图像拼接算法[J]. 计算机应用, 2021, 41(8): 2318-2323.
[5]	罗明宇, 骆晓萌, 朱文敏, 张磊, 范秀敏. 船舶狭小空间虚拟人维修姿态建模技术[J]. 计算机应用, 2021, 41(8): 2466-2472.
[6]	张闻强, 邢征, 杨卫东. 基于多区域采样策略的混合粒子群优化求解多目标柔性作业车间调度问题[J]. 计算机应用, 2021, 41(8): 2249-2257.
[7]	李蒙蒙, 秦伟, 刘艺, 刁兴春. 结合头脑风暴优化的混合蚁群优化算法[J]. 计算机应用, 2021, 41(8): 2412-2417.
[8]	汤安迪, 韩统, 徐登武, 谢磊. 混沌精英哈里斯鹰优化算法[J]. 计算机应用, 2021, 41(8): 2265-2272.
[9]	汤安迪, 韩统, 徐登武, 谢磊. 基于混沌麻雀搜索算法的无人机航迹规划方法[J]. 计算机应用, 2021, 41(7): 2128-2136.
[10]	赵秋云, 魏乐, 舒红平. 面向制造任务的云制造虚拟车间构造方法[J]. 计算机应用, 2021, 41(7): 2003-2011.
[11]	杨震, 马健霄, 王宝杰. 设置待行区条件下双环相位信号配时优化模型[J]. 计算机应用, 2021, 41(7): 2108-2112.
[12]	张祥飞, 鲁宇明, 张平生. 基于协同进化的约束多目标优化算法[J]. 计算机应用, 2021, 41(7): 2012-2018.
[13]	张盟, 郭健全. 需求和回收不确定的闭环供应链渠道结构选择[J]. 计算机应用, 2021, 41(7): 2100-2107.
[14]	李辉, 吴传生, 刘俊, 刘文. 基于梯度曲面面积与稀疏约束的图像平滑方法[J]. 计算机应用, 2021, 41(7): 2039-2047.
[15]	蔡瑞光, 张德生, 肖燕婷. 参数独立的加权局部均值伪近邻分类算法[J]. 计算机应用, 2021, 41(6): 1694-1700.

基于约束优化的Petri网可达性分析

Reachability analysis of Petri net based on constraint optimization

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics