Saturday, September 15, 2007

Learnable Evolution Model Non-Darwinian Evolutionary Computation

Learnable Evolution Model
A Non-Darwinian Evolutionary Computation
Guided by Machine Learning

(Michalski, Wojtusiak, Kaufman)

The Learnable Evolution Model (LEM) is a novel, non-Darwinian methodology for evolutionary computation that employs machine learning to guide the generation of new individuals (candidate problem solutions). Unlike standard, Darwinian-type evolutionary computation methods that use random or semi-random operators for generating new individuals (such as mutations and/or recombinations), LEM employs hypothesis generation and instantiation operators.

The hypothesis generation operator applies a machine learning program to induce descriptions that distinguish between high-fitness and low-fitness individuals in each consecutive population. Such descriptions delineate areas in the search space that most likely contain the desirable solutions. Subsequently the instantiation operator samples these areas to create new individuals.

Figure 1 presents a diagram of LEM3, the newest implementation of Learnable Evolution Model. LEM3 can be viewed as a multistrategy evolutionary program because in addition to creating new individuals through hypothesis generation and instantiation operators (red module in the diagram), it can also create them through probing operators (implementing some forms of mutations and recombinations) and randomization operators (that generate random individuals). In the future, we plan to implement also local search operators.


Figure 1: LEM3 flowchart.


Figure 2: Learn & Instantiate action flowchart.

In our experimental studies concerning complex function optimization (with the number of variables ranging between 10 and 1000), LEM3 significantly outperformed other evolutionary computation methods, sometimes by two or more orders of magnitude in terms of the evolution length (defined as the number of fitness evaluations needed to reach a desired solution).

The LEM methodology was also used to implement specialized systems, ISHED and ISCOD, for optimizing designs of heat exchangers. This work has been done in collaboration with the National Institute for Standards and Technology (see Learnable Evolution Model in Engineering Design).

LEM has the potential for application to a wide range of problems, in particular, to domains in which fitness function evaluation is costly or time-consuming, such as engineering design, economics, drug design, evolvable hardware, software engineering and optimization, and data mining.

Selected References:

Wojtusiak, J. and Michalski R.S., "The LEM3 System for Non-Darwinian Evolutionary Computation: A Method Description and Application to Very Complex Function Optimization Problems," to be submitted to: Evolutionary Computation.

Michalski, R. S., "Optimizing Complex Systems by Intelligent Evolution:The LEMd Method and Case Study," Bulletin of the Polish Academy of Sciences, November 2006.

Michalski, R. S., Wojtusiak, J. and Kaufman, K., "Intelligent Optimization via Learnable Evolution Model," Proceedings of The 18th IEEE International Conference on Tools with Artificial Intelligence, Washington D.C., November 13-15, 2006.

Michalski, R.S. and Kaufman, K., "INTELLIGENT EVOLUTIONARY DESIGN: A New Approach to Optimizing Complex Engineering Systems and its Application to Designing Heat Exchangers," International Journal of Intelligent Systems, Volume 21, Issue 12, 2006.

Michalski, R. S., Wojtusiak, J. and Kaufman, K., "Progress Report on the Learnable Evolution Model," Reports of the Machine Learning and Inference Laboratory, MLI 06-5, George Mason University, Fairfax, VA, 2006.

Wojtusiak, J. and Michalski, R.S., "The LEM3 Implementation of Learnable Evolution Model and Its Testing on Complex Function Optimization Problems," Proceedings of Genetic and Evolutionary Computation Conference, GECCO 2006, Seattle, WA, July 8-12, 2006.

Wojtusiak, J., "Initial Study on Handling Constrained Optimization Problems in Learnable Evolution Model," Proceedings of The Graduate Student Workshop at Genetic and Evolutionary Computation Conference, GECCO 2006, Seattle, WA, July 8-12, 2006.

Wojtusiak, J. and Michalski, R.S., "The LEM3 System for Non-Darwinian Evolutionary Computation and Its Application to Complex Function Optimization," Reports of the Machine Learning and Inference Laboratory, MLI 05-2, George Mason University, Fairfax, VA, October, 2005.

Domanski, P.A., Yashar, D., Kaufman K. and Michalski R.S., "An Optimized Design of Finned-Tube Evaporators Using the Learnable Evolution Model," Reports of the Machine Learning and Inference Laboratory, MLI 04-1, George Mason University, Fairfax, VA, February, 2004.

Kaufman K. and Michalski R.S., "Applying Learnable Evolution Model to Heat Exchanger Design," Proceedings of the Seventeenth National Conference on Artificial Intelligence (AAAI-2000) and Twelfth Annual Conference on Innovative Applications of Artificial Intelligence (IAAI-2000), Austin, TX, pp. 1014-1019, 2000.

Kaufman K., Cervone G. and Michalski R.S., "Experimental Validations of the Learnable Evolution Model," 2000 Congress on Evolutionary Computation, San Diego CA, pp 1064-1071, July 2000.

Michalski R.S., "LEARNABLE EVOLUTION MODEL Evolutionary Processes Guided by Machine Learning," Machine Learning , 38, pp 9-40, 2000.

Michalski R.S. and Zhang, Q., "Initial Experiments with the LEM1 Learnable Evolution Model: An Application to Function Optimization and Evolvable Hardware," Reports of the Machine Learning and Inference Laboratory, MLI 99-4, George Mason University, Fairfax, VA, ay 1999.

Michalski, R.S., " Learnable Evolution: Combining Symbolic and Evolutionary Learning," Proceedings of the Fourth International Workshop on Multistrategy Learning (MSL'98), Desenzano del Garda, Italy, pp. 14-20, June 11-13, 1998.

For more references, see Publication section.

No comments: