Back to Search
Start Over
Population Based Methods for Optimising Infinite Behaviours of Timed Automata
- Publication Year :
- 2018
- Publisher :
- Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Wadern/Saarbruecken, Germany, 2018.
-
Abstract
- Timed automata are powerful models for the analysis of real time systems. The optimal infinite scheduling problem for double-priced timed automata is concerned with finding infinite runs of a system whose long term cost to reward ratio is minimal. Due to the state-space explosion occurring when discretising a timed automaton, exact computation of the optimal infinite ratio is infeasible. This paper describes the implementation and evaluation of ant colony optimisation for approximating the optimal schedule for a given double-priced timed automaton. The application of ant colony optimisation to the corner-point abstraction of the automaton proved generally less effective than a random method. The best found optimisation method was obtained by formulating the choice of time delays in a cycle of the automaton as a linear program and utilizing ant colony optimisation in order to determine a sequence of profitable discrete transitions comprising an infinite behaviour.
Details
- Language :
- English
- Database :
- OpenAIRE
- Accession number :
- edsair.doi...........3e95558fc99b76ac8eebc992a08896fa
- Full Text :
- https://doi.org/10.4230/lipics.time.2018.22