Holger Mauch

Pong was a popular table tennis video game originally released in 1972. Pong is often used as the test subject for neural networks and genetic algorithms, often in tandem. Simple games like Pong have been optimized utilizing neural networks and genetic algorithms in order to scale difficulty or to self-sufficiently "beat" the game or human opponent [3]. However, this work attempts to scale difficulty not through behavior but through geometric morphological phenotypes. We have employed an evolutionary algorithm that weighs the performance of various Pong paddle shapes. This is tested and verified in our Pong simulation. This evolutionary algorithm modifies vertex values to generate shapes with weighted probabilities, simulate their performance in the game, establish the fitness of those shapes, and breed the most fit individuals to produce new generations of paddle shapes.

Encoding for solutions of combinatorial optimization problems involving permutations or constraints that maintain the generality of operators in evolutionary computation is often difficult. In this paper, we present the Priority Encoding Scheme (PES), a general-purpose encoding scheme that encodes information used to construct solutions rather than directly encoding solutions themselves. We show that not only is PES simple to implement, but that it can be used effectively with Genetic Algorithms (GA) and Simulated Annealing (SA) to find good solutions to the multiple-constraint knapsack problem (MKP) and shows promise for finding good solutions to the traveling salesman problem (TSP).

The closest string problem is an NP-hard problem, which arises in computational molecular biology and coding theory. Its task is to find a string that minimizes maximum Hamming distance to a given set of strings. In this paper, a compounded genetic and simulated annealing algorithm (CGSA) which combines the merits of genetic algorithms and simulated annealing is presented to solve CSP. An adapting two-point crossover operator and a heuristic gene mutation operator designed by us are used in CGSA. In addition, by analyzing the optimal solution's structural features some rules are designed to pretreat the data, which reduces the problem size. We report computational results which show that the CGSA is capable of finding good solutions in a reasonable amount of time.

Dynamic programming (DP) is a very general optimization technique, which can be applied to numerous management decision problems. In order to develop a software system that automates many of the tasks a user encounters when attempting to solve an instance of an optimization problem with discrete DP an intermediate problem representation in the form of a Petri net (PN) turns out to be useful. The specialized PN model presented in this paper captures the essential components of a DP problem instance. It uses the standard semantics of place/transition nets, a low-level PN class, whereas previous work (Lew, 2002; Lew and Mauch, 2003; and Mikoljczak and Rumbut, 1997) relied on high-level PNs. This approach is illustrated by a simple financing example, but the methodology works for a wide range of management problems and can be applied to more complex instances. Among the benefits of this representation are the possibility to perform consistency checks on the PN level and the existence of a simple procedure to translate a model instance into executable code that could be integrated into existing solvers. Also, a software system currently under development automates the task of transforming a DP functional equation into the PN model suggested in this paper. Users need not construct the PN model directly.