畢業(yè)論文 Petri網(wǎng)系統(tǒng)的可達(dá)性研究

68頁(yè)共計(jì)32093字

摘 要


本文對(duì)Petri網(wǎng)系統(tǒng)的可達(dá)性問(wèn)題做了綜合性的闡述和分析， 提出了利用能量?jī)?yōu)化方法來(lái)解決可達(dá)性問(wèn)題，并在此基礎(chǔ)上結(jié)合計(jì)算代數(shù)方法和神經(jīng)計(jì)算模型對(duì)可達(dá)性問(wèn)題做了進(jìn)一步的研究。作者的主要工作在以下四個(gè)方面：1. 給出了Petri網(wǎng)到線性空間的映射規(guī)則及其可達(dá)性的等價(jià)性定理；2. 建立了能量?jī)?yōu)化模型, 將可達(dá)性判斷化為優(yōu)化問(wèn)題；3. 用神經(jīng)網(wǎng)絡(luò)來(lái)求解能量?jī)?yōu)化模型；4. 最后綜合了計(jì)算代數(shù)方法和能量?jī)?yōu)化模型的優(yōu)點(diǎn)給出一個(gè)基于計(jì)算代數(shù)和神經(jīng)計(jì)算的方法。本文的特點(diǎn)就在于提出了一種利用基于硬件的大規(guī)模并行的神經(jīng)計(jì)算來(lái)代替基于軟件的串行的數(shù)字計(jì)算的可達(dá)性判斷解決方案。
在前言中，著重闡述了可達(dá)性問(wèn)題的研究意義，主要困難和目前使用的五類研究方法，在做了簡(jiǎn)單的評(píng)價(jià)后，引出我們的研究目的和研究成果。在第一章，簡(jiǎn)要回顧了Petri網(wǎng)模型的背景知識(shí)和研究的歷史與發(fā)展?fàn)顩r，研究方法和應(yīng)用范圍等背景知識(shí)。之后，又介紹了Petri網(wǎng)模型以及相關(guān)知識(shí)，將該領(lǐng)域的知識(shí)框架做了大體說(shuō)明。
在第二章，主要介紹了計(jì)算代數(shù)方法。先描述了將Petri網(wǎng)模型映射到代數(shù)系統(tǒng)的基本思想，Petri網(wǎng)模型的行為特征對(duì)應(yīng)的代數(shù)表示，將可達(dá)性問(wèn)題歸結(jié)為代數(shù)問(wèn)題。接著講解了必要的計(jì)算代數(shù)方面的基礎(chǔ)知識(shí)，主要講解了計(jì)算代數(shù)方法的核心工具－Grobner基，以及計(jì)算Grobner基的著名數(shù)學(xué)軟件Maple的使用方法和Grobner基軟件包。最后，分析了計(jì)算代數(shù)方法的局限性。
從第三章開(kāi)始大部分是作者的工作，在第三章中主要給出了利用能量?jī)?yōu)化模型及其可達(dá)性的等價(jià)性定理來(lái)解決可達(dá)性問(wèn)題。先說(shuō)明了該方法思想的出發(fā)點(diǎn)和形成過(guò)程，之后在該模型下自然誘導(dǎo)出弱可達(dá)性概念及其性質(zhì)。提出利用整數(shù)規(guī)劃方法來(lái)處理弱可達(dá)性條件，并介紹了相關(guān)的數(shù)學(xué)軟件。最后描述了能量?jī)?yōu)化模型建立的過(guò)程和方法。
第四章是針對(duì)第三章的能量?jī)?yōu)化模型提出神經(jīng)網(wǎng)絡(luò)的模型計(jì)算方案。首先，敘述了神經(jīng)網(wǎng)絡(luò)的基礎(chǔ)知識(shí)，神經(jīng)計(jì)算的特點(diǎn)和應(yīng)用。之后介紹了神經(jīng)網(wǎng)絡(luò)的一種全連接模型－Hopield神經(jīng)網(wǎng)絡(luò)，及Hopield網(wǎng)絡(luò)在能量?jī)?yōu)化模型的應(yīng)用。接著對(duì)Hopield網(wǎng)絡(luò)求解能量?jī)?yōu)化模型的能量函數(shù)和相關(guān)參數(shù)做了計(jì)算和分析。最后對(duì)神經(jīng)計(jì)算的軟件硬件實(shí)現(xiàn)做了簡(jiǎn)單的說(shuō)明。
第五章總結(jié)了前幾章敘述的各類方法，對(duì)其優(yōu)缺點(diǎn)進(jìn)行分析比較后提出了綜合分析方法，給出了綜合分析方法的算法流程。在第六章，以停等協(xié)議的Petri網(wǎng)模型為例利用綜合分析方法對(duì)可達(dá)性問(wèn)題做了分析。最后，本文結(jié)尾對(duì)Petri網(wǎng)模型的可達(dá)性研究的存在問(wèn)題和將來(lái)需要做的工作做了簡(jiǎn)要闡述和展望。
在附錄中給出了用Matlab編寫的利用Hopield網(wǎng)絡(luò)求解能量?jī)?yōu)化模型的算法程序。
摘 要 II
ABSTRACT IV
前 言 VI
第一章 背景知識(shí) 1
§1.1 歷史與發(fā)展 1
§1.2 研究方法及應(yīng)用 1
§1.3 Petri網(wǎng)的直觀理解 2
§1.4 Petri網(wǎng)的形式化描述 2
第二章 Petri網(wǎng)與代數(shù)系統(tǒng)的關(guān)系 6
§2.1 Petri網(wǎng)模型映射到代數(shù)系統(tǒng) 6
§2.2 基于Grobner基的Petri網(wǎng)系統(tǒng)性質(zhì)分析 8
§2.3 Maple符號(hào)計(jì)算軟件介紹[14] 12
§2.4 計(jì)算代數(shù)方法的局限性 14
第三章 能量?jī)?yōu)化模型 15
§3.1 Petri網(wǎng)系統(tǒng)映射到線性空間 15
§3.2 弱可達(dá)性及其分析 17
§3.3 能量?jī)?yōu)化模型建立和分析 20
第四章 可達(dá)性的神經(jīng)網(wǎng)絡(luò)解法 24
§4.1 神經(jīng)網(wǎng)絡(luò)介紹[15] 24
§4.2 Hopfield網(wǎng)絡(luò)模型 26
§4.3 能量?jī)?yōu)化模型的神經(jīng)網(wǎng)絡(luò)解法 30
§4.4 算法的實(shí)現(xiàn) 32
第五章 綜合分析方法 34
§5.1 幾種方法的綜合比較 34
§5.2 綜合分析方法描述 34
§5.3 綜合分析方法總結(jié) 36
第六章 應(yīng)用實(shí)例分析 38
結(jié)尾 問(wèn)題與展望 48
致 謝 49
附 錄 50

關(guān)鍵詞：Petri網(wǎng)模型；可達(dá)性；Grobner基；能量?jī)?yōu)化模型；Hopield神經(jīng)網(wǎng)絡(luò)；弱可達(dá)性；綜合分析方法；

1．參考文獻(xiàn)
[16] 李人厚，張永安, “精通MATLAB--綜合輔導(dǎo)與指南”，西安交通大學(xué)出版社，1998
[17] “運(yùn)籌學(xué)”，清華大學(xué)出版社，1982
[18] Hopfield J. and Tank, D. Neural computation of decisions in optimization problems. Biological Cybernetics,1985, 52:141 - 152.
[19] T. Murata, Petri Nets: Properties, Analysis and Applications,
Proceedings of the IEEE, Vol. 77, No 4, April, 1989, pp. 541-580.
[20] Kate Smith, Marimuthu Palaniswami, and Mohan Krishnamoorthy “Neural
Techniques for Combinatorial Optimization with Applications”, IEEE Transactions On Neural Networks, Vol. 9, No. 6, November 1998 pp1301-1318
[21] 傅京孫，蔡自興，徐光祐“人工智能及其應(yīng)用”清華大學(xué)出版社，1987年。
[22] Bhubaneswar Mishra. Algorithmic Algebra. 科學(xué)出版社. 2001.
[23] 楊路, 張景中, 候曉榮. 非線性代數(shù)方程組與機(jī)器證明. 上海：上海科技教育出版社, 1996.
[24] 楊路. 全局優(yōu)化的符號(hào)算法與有限核原理. 林東岱等主編:數(shù)學(xué)與數(shù)學(xué)機(jī)械化. pp.210-220, 山東教育出版社, 2001.
[25] Yang, L., Xia, S. H.. An inequality-proving program applied to global optimization, Proceedings of the Asian Technology Conference in Mathematics, W-C. Yang et al (eds.), ATCM, Inc., Blacksburg, pp.40-51, 2000.
[26] Wu W.T., On the decision problem and the mechanization of theorem-proving in elementary geometry. Sci. Sinica 1978,21:159-172.
[27] D.Psaltis, N.Farhat, Optical information processing based on associative-memory model of neural nets with thersholding and feedback, Opt.Lett. 10, 1985, pp98-100.
[28] 宋菲軍，S.Jutamulia, “近代光學(xué)信息處理”，北京大學(xué)出版社，1998年。
[29] Neil Collings, R.Sumi,K.J. Weible, Bruno Acklin, Wei Xue, Use of optical hardware to find good solutions to the traveling，salesman problem, pp.637-641，SPIE Proceedings Vol. 1806，1993。
[30] W. K. Lai and G. G. Coghill, “Genetic breeding of control parameters for
the Hopfield/Tank neural net,” in Proc. Int. Joint Conf. Neural Networks,
1992, vol. IV, pp. 618–623.
[31] Kapur D., Saxena T, Yang L., Algebraic and geometric reasoning using Dixon resultants. In: Proc. ISSAC'94, 1994, ACM Press, 99-107.
[32] Yang L., Hou X.R., Gather-and-Sift: A symbolic method for solving polynomial systems. Proc.ATCM'95,1995,Singapore.
[33] Karmarkar N. “A new polynomial time algorithm for linear programming”, Combinatorica 4,1984, pp373-395
[34] Buchberger B., Groebner Bases: An algorithmic method in polynomial ideal theory. Chapter 6 in: Recent Trends in Multidimensional Systems Theory.Bose N.K.(ed.), D.Reidel Publ.Comp.,1985.
[35] Andrew Blais, Ph.D. (onlymice@gnosis.cx), David Mertz, Ph.D. (mertz@gnosis.cx) “An introduction to neural networks”, Gnosis Software, Inc.July 2001