Vi introducerar ett automatiserat tillvägagångssätt för tillämpning av simulering av sällsynta händelser på stokastiska Petri-nätmodeller (SPN) av mycket tillförlitliga Markovian-system (HRMS). Vi är särskilt intresserade av händelse av att nå en sällsynt uppsättning av måltillstånd (t.ex. systemfel) innan vi når en specifik uppsättning typiska tillstånd (t.ex. alla komponenter som fungerar). Tillståndsutrymmet för en HRMS-modell av ett realistiskt system kommer vanligtvis att vara mycket stort, men vi antar att det är specificerat med hjälp av hög nivå modellering formalism SPNs. Detta gör att vi kan utföra Monte Carlo simulering på SPN-nivå. Men eftersom vår händelse av intresse är sällsynt skulle vi behöva använda ett oöverkomligt stort antal prover med hjälp av standardsimulering. Därför använder vi den effektiva simuleringstekniken av betydelse provtagning. Den viktigaste idén av betydelse provtagning är att använda en annan sannolikhetsmått än den ursprungliga sådan att övergångar till det uppsatta målet görs mer sannolikt. För att göra detta behöver vi en uppfattning om avståndet till det uppsatta målet. För att formalisera detta avstånd antar vi att alla övergångshastigheter i HRMS är polynomfunktioner av en sällsynt parameter. Parametern anger det faktum att i en HRMS, graden av olika typer av övergångar tenderar att variera kraftigt (t.ex., graden av misslyckande övergångar är mycket lägre än de för reparation övergångar). Vi antar att när ↓ 0, sannolikheten för händelsen av intresse försvinner. Avståndet mellan ett tillstånd och målet som sedan kan uttryckas i termer av den minsta polynom ordningen bland sannolikheterna för stigar mellan dem. Avståndet mellan varje stat och målet satt är oklart a priori. Bestämma den kortaste vägen till målet satt för varje stat individuellt med hjälp av Dijkstra algoritm skulle vara beräkning dyrt. Därför vill vi utnyttja systemets struktur så att vi kan bestämma den kortaste vägen till det mål som ställts upp för grupper av stater samtidigt. Strukturen på SPN tillåter detta: övergångar i ett SPN beskrivs med hjälp av ett fast antal övergångstyper, som var och en har samma effekt på tillståndsvektorn (genom samma vektortillägg). Vi antar att för varje övergångstyp är alla övergångar av denna typ av samma polynom-ordning. Detta gör att vi kan dela upp tillståndet utrymme i zoner så att för varje zon, den kortaste vägen från varje tillstånd i den zonen kommer att vara sådan att en enda annan zon nås genom upprepade övergångar av samma övergångstyp. Denna zon partitionering är konstruerad iterativt, med början från målet satt. Det visar sig att på grund av SPN:s struktur kan alla zongränser och alla banlängder inom zoner uttryckas med linjära ojämlikheter. Ett exempel på algoritmens utgång ges i figur 1 ; den underliggande modellen för denna siffra är en SPN-modell av en tvånode tandem kö där måluppsättningen är lika med de stater för vilka det finns minst n kunder i den andra kön, för en given n > 1. Statrymden är tvådimensionell, med varje dimension som representerar antalet kunder i en av de två köerna. Det finns tre övergångstyper: ankomster till den första kön (som inträffar i takt λ), rörelser från den första till den andra kön (med hastighet μ) och avgångar från den andra kön (med ränta v). Vi utgår från att det finns stora skillnader mellan de tre övergångstypernas skattesatser: framför allt utgår vi från att λ =  på 2, μ =  på ( ) och v på =.(1). 1 Som kan ses i Figur 1, För vissa stater strukturen på den kortaste vägen till målet som är sådan att den andra kön töms innan n kunder anländer till den första kön (detta sker i zon z 320 ). 1 Med hjälp av Landau notation skriver vi f ( ) = ( g( )) om 0 < lim ↓0 f ( )/g( ) < ∞. Om HRMS-modellen uppfyller vissa villkor (inga hög sannolikhetscykler, alla stater tilldelas ett heltalsvärderat avstånd), kan avstånden användas för att konstruera en viktprovtagningsskattare som har den önskvärda egenskapen av begränsat relativa fel, och detta kan göras på ett automatiserat sätt. Se [1] eller [2] för en mer detaljerad diskussion om algoritmen. 2 I framtiden hoppas vi kunna lätta på metodens antaganden och utvidga den till att omfatta kö-/befolkningsmodeller (t.ex. modeller där det är ovanligt med intresse på grund av ett stort antal misslyckade övergångar som behöver göras).
En annan intressant metod är REF, som är inriktad på att simulera sällsynta händelser, även om den är begränsad till Stochastic Petri Nets.
Automated rare event simulation for stochastic petri nets
{'venue': 'QEST', 'journal': None, 'mag_field_of_study': ['Computer Science']}