Developing Genetic Algorithms and Mixed Integer Linear Programs for Finding Optimal Strategies for a Student’s “Sports” Activity


Butter, Thomas ; Rothlauf, Franz ; Grahl, Jörn ; Hildenbrand, Tobias ; Arndt, Jens


[img]
Vorschau
PDF
workingpaper.pdf - Veröffentlichte Version

Download (135kB)

URL: https://ub-madoc.bib.uni-mannheim.de/1638
URN: urn:nbn:de:bsz:180-madoc-16380
Dokumenttyp: Arbeitspapier
Erscheinungsjahr: 2006
Titel einer Zeitschrift oder einer Reihe: None
Sprache der Veröffentlichung: Englisch
Einrichtung: Fakultät für Betriebswirtschaftslehre > Sonstige - Fakultät für Betriebswirtschaftslehre
MADOC-Schriftenreihe: Area Information Systems and Institute for Enterprise Systems > Working Papers Lehrstuhl für ABWL und Wirtschaftsinformatik (Heinzl) (bis 2011)
Fachgebiet: 004 Informatik
Normierte Schlagwörter (SWD): Genetischer Algorithmus , Gemischt-ganzzahlige Optimierung , Programmierung
Abstract: An important advantage of genetic algorithms (GAs) are their ease of use, their wide applicability, and their good performance for a wide range of different problems. GAs are able to find good solutions for many problems even if the problem is complicated and its properties are not well known. In contrast, classical optimization approaches like linear programming or mixed integer linear programs (MILP) can only be applied to restricted types of problems as non-linearities of a problem that occur in many real-world applications can not appropriately modeled. This paper illustrates for an entertaining student “sports” game that GAs can easily be adapted to a problem where only limited knowledge about its properties and complexity are available and are able to solve the problem easily. Modeling the problem as a MILP and trying to solve it by using a standard MILP solver reveals that it is not solvable within reasonable time whereas GAs can solve it in a few seconds. The game studied is known to students as the so-called “beer-run”. There are different teams that have to walk a certain distance and to carry a case of beer. When reaching the goal all beer must have been consumed by the group and the winner of the game is the fastest team. The goal of optimization algorithms is to determine a strategy that minimizes the time necessary to reach the goal. This problem was chosen as it is not well studied and allows to demonstrate the advantages of using metaheuristics like GAs in comparison to standard optimization methods like MILP solvers for problems of unknown structure and complexity.
Zusätzliche Informationen:




Das Dokument wird vom Publikationsserver der Universitätsbibliothek Mannheim bereitgestellt.




Metadaten-Export


Zitation


+ Suche Autoren in

+ Download-Statistik

Downloads im letzten Jahr

Detaillierte Angaben



Sie haben einen Fehler gefunden? Teilen Sie uns Ihren Korrekturwunsch bitte hier mit: E-Mail


Actions (login required)

Eintrag anzeigen Eintrag anzeigen