Logo des Repositoriums

Auflistung nach Schlagwort "Genetic algorithm"

1 - 4 von 4
  • Zeitschriftenartikel
    A Multi-objective Genetic Algorithm for Build Order Optimization in StarCraft II
    (KI - Künstliche Intelligenz: Vol. 27, No. 3, 2013) Köstler, Harald; Gmeiner, Björn
    This article presents a modified version of the multi-objective genetic algorithm NSGA II in order to find optimal opening strategies in the real-time strategy game StarCraft II. Based on an event-driven simulator capable of performing an accurate estimate of in-game build-times the quality of different build lists can be judged. These build lists are used as chromosomes within the genetic algorithm. Procedural constraints e.g. given by the Tech-Tree or other game mechanisms, are implicitly encoded into them. Typical goals are to find the build list producing most units of one or more certain types up to a certain time (Rush) or to produce one unit as early as possible (Tech-Push). Here, the number of entries in a build list varies and the objective values have in contrast to the search space a very small diversity. We introduce our game simulator including its graphical user interface, the modifications necessary to fit the genetic algorithm to our problem, test our algorithm on different Tech-Pushes and Rushes for all three races, and validate it with empirical data of expert StarCraft II players.
  • Zeitschriftenartikel
    Extracting Maritime Traffic Networks from AIS Data Using Evolutionary Algorithm
    (Business & Information Systems Engineering: Vol. 62, No. 5, 2020) Filipiak, Dominik; Węcel, Krzysztof; Stróżyna, Milena; Michalak, Michał; Abramowicz, Witold
    The presented method reconstructs a network (a graph) from AIS data, which reflects vessel traffic and can be used for route planning. The approach consists of three main steps: maneuvering points detection, waypoints discovery, and edge construction. The maneuvering points detection uses the CUSUM method and reduces the amount of data for further processing. The genetic algorithm with spatial partitioning is used for waypoints discovery. Finally, edges connecting these waypoints form the final maritime traffic network. The approach aims at advancing the practice of maritime voyage planning, which is typically done manually by a ship’s navigation officer. The authors demonstrate the results of the implementation using Apache Spark, a popular distributed and parallel computing framework. The method is evaluated by comparing the results with an on-line voyage planning application. The evaluation shows that the approach has the capacity to generate a graph which resembles the real-world maritime traffic network.
  • Zeitschriftenartikel
    Robuste multikriterielle Dienstkomposition in Informationssystemen
    (Wirtschaftsinformatik: Vol. 56, No. 3, 2014) Ramacher, René; Mönch, Lars
    Dienstkompositionen werden dazu verwendet, Geschäftsprozesse in einer Vielzahl von Anwendungsdomänen zu implementieren. Die Quality-of-Service (QoS)-basierte Auswahl von Diensten berücksichtigt mehrere, typischerweise konfliktäre und möglicherweise unsichere QoS-Attribute. Ein multikriterieller Lösungsansatz ist wünschenswert, um eine Menge alternativer Dienstselektionen zu ermitteln. Außerdem ist festzustellen, dass die Unsicherheit von QoS-Attributen in existierenden Ansätzen vernachlässigt wird. Daraus folgt, dass es erforderlich ist, Dienst-Rekonfigurationen zu betrachten, um eine Verletzung von QoS-Restriktionen zu vermeiden. Das in der Arbeit untersuchte Problem ist NP-schwer. Der Artikel stellt einen heuristischen multikriteriellen Dienstauswahlansatz vor, der dazu entworfen wurde, eine Pareto-Front alternativer Dienstselektionen mit vertretbarem Rechenaufwand zu ermitteln. Die erhaltenen Dienstselektionen sind robust bezüglich einer eingeschränkten Ausführungsdauer, wenn unsichere Antwortzeiten berücksichtigt werden. Der vorgeschlagene Lösungsansatz basiert auf einem Nondominated Sorting Genetic Algorithm (NSGA-II)-Ansatz, der problemspezifische Eigenschaften ausnutzt. Die Anwendbarkeit des vorgeschlagenen Lösungsansatzes wird durch eine Simulationsstudie gezeigt.AbstractService compositions are used to implement business processes in a variety of application domains. A quality of service (QoS)-aware selection of the service to be composed involves multiple, usually conflicting and possibly uncertain QoS attributes. A multi-criteria solution approach is desired to generate a set of alternative service selections. In addition, the uncertainty of QoS-attributes is neglected in existing solution approaches. Hence, the need for service reconfigurations is imposed to avoid the violation of QoS restrictions. The researched problem is NP-hard. This article presents a heuristic multi-criteria service selection approach that is designed to determine a Pareto frontier of alternative service selections in a reasonable amount of time. Taking into account the uncertainty of response times, the obtained service selections are robust with respect to the constrained execution time. The proposed solution approach is based on the Non-dominated Sorting Genetic Algorithm (NSGA)-II extended by heuristics that exploit problem specific characteristics of the QoS-aware service selection. The applicability of the solution approach is demonstrated by a simulation study.
  • Zeitschriftenartikel
    Solving Practical Railway Crew Scheduling Problems with Attendance Rates
    (Business & Information Systems Engineering: Vol. 59, No. 3, 2017) Hoffmann, Kirsten; Buscher, Udo; Neufeld, Janis Sebastian; Tamke, Felix
    Arising from a practical problem in German rail passenger transport, a prototype for a multi-period railway crew scheduling problem with attendance rates for conductors is developed and evaluated in this paper. The consideration of attendance rates is of increasing importance in regional transport networks and requires decision support. For this purpose business analytics is applied in order to offer an approach to transform real-world data to concrete operational decision support (action). The focus here is on the analysis step using a new set covering model with several essential restrictions integrated for the first time. A hybrid column generation approach is applied, which solves the pricing problem by means of a genetic algorithm. The artifact is evaluated with the help of a case study of three real-world transport networks. It is shown that the hybrid solution approach is able to solve the problem more effectively and efficiently compared to conventional approaches used in practice.