Konferenzbeitrag
Development and application of evolutionary algorithms for the optimization of material flow simulations
Vorschaubild nicht verfügbar
Volltext URI
Dokumententyp
Text/Conference Paper
Zusatzinformation
Datum
2009
Autor:innen
Zeitschriftentitel
ISSN der Zeitschrift
Bandtitel
Verlag
Shaker Verlag
Zusammenfassung
In the course of the Emporer Project at the HTW Berlin, a material flow simulator called MILAN is created based on the EMPINIA framework. With MILAN it is possible to create, edit and simulate models of production systems. A model contains entities that depict production system components like machinery (workstations, conveyors quality checkpoints), resources (transporters, workers) and products. During a simulation run, the simulated time advances in discrete time steps, determined by events that occur at the various entities of the model (e.g. a process at a certain machine begins or ends). The results of a completed simulation run can be analyzed using a set of reports that are generated during and after the run. For each task (model creation, simulation and analysis) exists a different set of tools that supports the user in the achievement of his goals.
With the given abilities of MILAN it is possible to create and validate models of production systems and simulate its behaviour over a specific time frame, starting with a specific initial state. After a model was created and validated (simulation runs with a known initial state behave approximately like the real system would do) the goal of a user is to optimize the model to yield better results than the real system.
If the changes made to the model would be applicable in the real system, the usage of MILAN could enable an owner of a production system to improve the system by experimenting with the virtual model rather than the real system. But after a production system was created the question arises, where and how to start with the optimization of the model. Even if the user has a well distinguished area or parameter of the model to start, the modification would often be more than just a certain deviation of the original value. More often the change will be in a range of values, each choice resulting in its own simulation run, or even runs, to check its impact on the end result. The process of experimenting in these cases therefore leads to a very high amount of time and effort in order to reach an optimal solution.
An approach to this sort of problems is the usage of so called 'genetic (or evolutionary) algorithms. Such an algorithm mimics nature’s basic principle of the 'optimization' of species to survive in their environment – evolution. The core concept of these algorithms is to apply the principles of evolution (mutation, recombination, 'natural' selection) to computer programs. The subject of an optimization problem needs to be available in some sort of data structure (the genome). One instance of this data structure is considered to be an individual of a population (multiple instances of the data structure). Each individual of a population is evaluated using a so called fitness function (or target function), which determines its ability to meet a desired goal for the optimization. This part of the process models the natural selection of evolution in nature. It decides which individuals (and therefore which genomes) will become extinct and which ones survive. Surviving individuals will be available to create a new population (the next generation).
After an initial population was examined, the new population is created based on the remaining individuals of the last generation using two other principles of evolution – mutation and recombination. The former changes an aspect of the genome of an individual randomly, while the latter joins the parts of the genome of two 'parent' individuals to create a complete 'child'.
With the usage of mutation or recombination functions (or both of them) a new generation of individuals is created which again is evaluated using the fitness function. These steps can be executed until an optimal solution is found or a certain number of cycles is reached (success or abort criterion). Reaching an optimal solution means, an individual performs in a way that produces a result that reaches or exceeds the optimization goal (defined by the user before the beginning of the evolutionary algorithm).
The approach of the thesis behind this is, to apply the concept of optimization via evolutionary algorithms to the domain of material flow simulation, evaluate its applicability and try to predict its usefulness in this scope. The current representation of production systems in MILAN (a model object with a set of contained entities) will be used as genome. An individual is represented by its model structure and the specific parameter set (the settings of all components).
MILAN has to be extended with a new module specific to the configuration, execution and analysis of simulation runs based on the evolutionary principle. A graphical user interface is needed, that allows the definition of fitness, mutation and recombination functions, as well as the configuration of strategies how the creation of new generations could be done. The simulation runs itself should run in an independent way that allow the automated evaluation of a big number of individuals and generations. Another question that maybe can be answered in the curse of the thesis is the applicability of the evolutionary algorithm principle for other optimization tasks and thus resulting in the creation of a generic evolutionary algorithm module for the EMPINIA framework.