Project: Genetic Algorithms in the Synthesis of Probabilistic Systems


Operators of production units in complex production facilities (e.g. steel plants) are supposed to base their decisions on an enterprise-specific set of rules. In practice, however, it is often unclear to which extent these rules are being adhered to – knowledge of this extent, however, is a crucial prerequisite for evaluating the quality of the rule set. It would therefore be useful to be able to infer a predictive behavioural model from the actual observed behaviour of the operator. The same holds for the entire production chain, composed of environment parameters such as frequency of requests for certain products, various machines and their operators, and the interconnection of the machines. It seems sensible to model the behaviour of both the environment and the machine operators probabilistically – observable information about the former is only available in statistical form anyway, and the latter will in all likelihood not behave completely deterministically in all situations. We therefore propose to develop methods for synthesizing probabilistic systems that realize the observed behaviour of the system as accurately as possible. One method that seems particularly suitable for this purpose is to use genetic algorithms to generate probabilistic system models, denoted in the input language of a probabilistic model checker such as Prism. We can then apply the model checker to determine the degree of agreement between a given probabilistic system and the observed actual behaviour, and use the result as a fitness function for the genetic algorithm. If this program is successful, it would not only generate added value in the target application domain, but it would also constitute substantial scientific progress in computer science, the main novelties being

  • the use of genetic algorithms to synthesize any form of behavioural model, and in particular probabilistic models
  • the use of model checkers as a backend for the calculation of fitness functions

Related Work

Classical work e.g. by Fogel on discovering finite state machines

Older work on induction of (Markov) decision processes (learning classifier systems, LCS) via genetic programming seems to be aimed at clustering scenarios rather than fitting the machine to an observed behaviour.


Last modified 11 years ago Last modified on 09.11.2010 14:20:14