Petri網(wǎng)路徑尋優(yōu).pdf

1、當(dāng)Petri網(wǎng)的變遷與一個(gè)時(shí)間延遲相關(guān)聯(lián)，我們就稱它為賦時(shí)Petri網(wǎng)。在賦時(shí)Petri網(wǎng)中從輸入庫所到輸出庫所耗時(shí)最短的路徑被稱為主干路徑。它是貫穿系統(tǒng)的效率最高的路徑，在很大程度上決定著系統(tǒng)的性能。在許多應(yīng)用中我們都必須通過系統(tǒng)的主干路徑來研究系統(tǒng)。Petri網(wǎng)的運(yùn)行不僅是簡單的順序或分支結(jié)構(gòu)，而是具有順序，并行，分支，回路，權(quán)值，協(xié)作，沖突等多種特征的網(wǎng)系統(tǒng)，所以其主干路徑的尋找就比一般的路徑搜索顯得更為復(fù)雜。
　　 本文

2、針對主干路徑尋找這個(gè)主線而展開對賦時(shí)Petri網(wǎng)的研究。
　　 首先，文章分析了固定時(shí)間變遷的Petri網(wǎng)特點(diǎn)，說明了在尋優(yōu)時(shí)選用蟻密算法的原因，以及對環(huán)路的消解，速度的協(xié)調(diào)，選路策略，信息素更新，庫所更新等問題的探討和解決，然后以精確的數(shù)學(xué)形式提出了固定延時(shí)Petri網(wǎng)的路徑尋優(yōu)算法，最后編程實(shí)現(xiàn)算法，證明了算法的有效性。
　　 固定延時(shí)Petri網(wǎng)是以理想的大腦對理想問題解答。實(shí)踐中很多事件的發(fā)生并非固定延時(shí)，而是隨

3、機(jī)的，其中服從指數(shù)分布居多。我們接下來就研究SPN的路徑尋優(yōu)。對于SPN，我們首先分析了SPN中各個(gè)變遷實(shí)施時(shí)刻的分布規(guī)律，提出了計(jì)算該時(shí)刻分布的一種方法。當(dāng)完成了對SPN的分析后，我們根據(jù)分析結(jié)果來重新設(shè)計(jì)新的蟻密算法。提出了在SPN環(huán)境中使用的各個(gè)網(wǎng)元素的數(shù)據(jù)結(jié)構(gòu)，然后重新解決上述的環(huán)路消解等問題，最后提出在SPN環(huán)境中新的蟻群算法，尋找到SPN中效率最高路徑。
　　 當(dāng)Petri網(wǎng)的路徑尋找被解決后，另一個(gè)問題出現(xiàn)了，如果

4、可靠度低的路徑為主干路徑，那么就會(huì)錯(cuò)誤的引導(dǎo)Petri分析。于是我們引入最能描述可靠度變化的Weibull模型。然后用結(jié)合可靠度的路徑尋優(yōu)提出了新的路徑選擇公式，使token的路徑選擇不僅僅根據(jù)信息素，延時(shí)，還加入了可靠度。最終使蟻路在成本收益率最好的路徑上收斂。就進(jìn)一步提高Petri網(wǎng)對實(shí)際問題的識(shí)別能力。其實(shí)我們在本章也暗示了一種能更廣泛使用本算法的方式，需要細(xì)心的讀者自行發(fā)覺。
　　 經(jīng)過三次使用具有記憶特性的Petri網(wǎng)