Evolutionary Optimization through Simulation
Real-life optimization problems involve complex systems and many variables. Often a designer knows the parameters that can be varied and an objective measure of the quality of a design. However, incomplete knowledge of how the interdependent parameters affect the final quality preclude use of many mathematical optimization techniques. We have explored using genetic algorithms in conjunction with a simulation system to attack such optimization problems. Our focus is on problems that involve machines and mechanisms in the physical world, for example: varying parameters of an assembly line to maximize throughput, varying parameters of a coin-sorting mechanism to maximize robustness, or varying control programs of industrial robots to maximize energy efficiency.
Background & Objective: This research examines the problem of exploring a large parameter space to find high quality solutions to a design problem. Such problems are ubiquitous in all disciplines of engineering. As a sample problem, our method was used to generate effective control programs for two robotic vehicles.
Technical Discussion: Genetic algorithms provide a heuristic means of finding good solutions when the relationship between parameters and output is unknown or too complicated to model explicitly. In this case, accurate simulation is needed to determine the output corresponding to a given set of parameters. We tested our algorithms on the problem of learning control programs for two robotic vehicles: a pursuer and an evader. The above figure depicts overlayed time-lapsed images taken during a simulation which pitted particular pursuer and evader designs against one another. Related to the explorations of large parameter spaces is the Design Gallery methodology. Here, a quality measure is replaced by a similarity measure, and the computer's task is to find solutions that span the range of possibilities.
Outside Collaborations: This research was conducted in conjunction with the Dynamical & Evolutionary Machine Organization (DEMO) Group at Brandeis University.
Contact: Joseph Katz
Technology Areas:
Artificial Intelligence
Graphics
Modification Date: September 12, 2007
