CI-EN: Enhancement of ECJ, A High-Performance Community Metaheuristics Library for Stochastic Optimization Research

George Mason University, Fairfax VA

Investigators

Abstract

This grant funds the transformation of the popular ECJ software library into a general-purpose software tool for performing so-called "metaheuristic" optimization. Metaheuristics are methods for coming up with optimal (or close to optimal) solutions to hard problems, and particularly ones for which there are no straightforward ways to find answers. For example, imagine if we wanted to find the best walking behavior for a robot, but didn't really know how to program one, we could instead "evolve" a solution by trying many arbitrary behaviors in a simulator, then selecting the best-performing ones and breeding them to produce a new generation, then testing them in the simulator, and so on. This approach, a form of genetic programming, is an example of a metaheuristic. Metaheuristics are widely used in science and engineering for everything from robot design to protein folding to simulation of migration patterns. Metaheuristics are also popular in teaching computer science as many of them are closely related to similar notions drawn from genetics and population biology, swarms, human organizational behavior, and physics. While ECJ is particularly popular for genetic programming and related methods, there is no standard community tool for metaheuristics as a whole. This grant will enable development of such a tool. This would give students and researchers alike access to a broad range of metaheuristics algorithms to compare and use, make those algorithms usable in massively parallel environments, and provide a centralized environment for community contribution. Metaheuristics are stochastic optimization techniques in wide use for those classes of problems, such as the parameters of complex simulations, for which there is no "principled" optimization approach. ECJ is a popular tool certain subfamilies of metaheuristics, such as genetic programming and genetic algorithms, which have dominated much of the early research in the area. But much recent metaheuristics research has branched out to areas such as multiobjective optimization, combinatorial optimization, constrained methods, model-fitting, and so on, and has led to a host of new techniques. These techniques have a high degree of commonality, and the metheuristics community often seeks to "mix and match" elements from these techniques in order to customize methods for certain problems, and also to compare them against one another. However there is at present no popular common library to make this possible. This proposal aims to extend and enhance ECJ into a community metaheuristics toolkit for both researchers and educators. Enhancements will include: a testing harness and various testing facilities; new metaheuristics in single-state optimization, hybrid architectures, NEAT, combinatorial optimization, and model-fitting optimization; GUI and Eclipse environments; statistics utilities; and new benchmark problems for testing metaheuristics methods. The work will be done in conjunction with the metheuristics research community and also with teachers from high schools in the Washington D.C. area to assess the utility of the tool in STEM education.