Evolutionary Algorithms for Pattern Recognition

Angelo Marcelli

DIIIE - Universita’di Salerno

Claudio De Stefano

DAEIIMI – Universita’ di Cassino

Overview

Many pattern recognition problems can be reformulated as optimization problems and then fit within the framework of evolutionary computation. Evolutionary algorithms (EA) use a metaphor of natural evolution, seen as the nature’s answer to an optimization problem, and exploit such a metaphor to tackle this class of problem. The implementation of such a metaphor requires general criteria to decide when EA can be conveniently used, some basic machinery, namely the evolutionary cycle and the genetic operators, and specific rules for setting the EA parameters in order to maximize the algorithm performance.

When using EA in the framework of pattern recognition, there are two further issues that must be addresses: the reformulation of typical pattern recognition problems as optimization ones and the crucial role played by both the encoding of the solution into the genotype and the definition of the fitness function on the attainable performance. In many cases of interest, moreover, this mapping naturally leads to a multimodal fitness function, and therefore the further issue of making an evolutionary algorithm able to search for many optima arises.

The tutorial addresses all the above mentioned issues and is articulated into four parts. The introduction summarizes the basic idea behind evolutionary computation and illustrates how pattern recognition problems can be reformulated as optimization problems and then fit within the framework of evolutionary computation. Part I illustrates the metaphor used by evolutionary computation to tackle optimization problem, and the basic machinery of an EA. From them, general criteria to decide when EA can be conveniently used, and specific suggestions for setting the EA parameters in order to maximize the algorithm performance are given. Examples of use (and misuse) of EA in pattern recognition are also presented. Part II is the core material of the tutorial and is entirely devoted to address the use of EA for pattern recognition. In particular, it illustrates the crucial role played by both the encoding of the solution into the genotype and the definition of the fitness function on the attainable performance. It is then shown that in many cases of interest the reformulation of a pattern recognition problem in terms of evolutionary computation naturally leads to a multimodal fitness function, and therefore the provisions proposed in the literature to make an evolutionary algorithm able to search for many optima are illustrated, focusing on fitness sharing, which is the most widely adopted one. A methodology for selecting the optimal value of the sharing parameters to maximize the algorithm performance which follows from the dynamics of an EA embedding a fitness sharing mechanism is then illustrated. Eventually, Part III reports some examples of successful applications of EA, with particular emphasis on the methodological issues addressed during their development.

As results of the final discussion, the participants should bring home the lesson that EA may provide effective and low cost solutions to many pattern recognition problems, but that they are not a panacea. On the contrary, a successful application requires a preliminary evaluation of the suitability of those algorithms to solve the problem at hand, a sound methodology to avoid “magic numbers” in setting the value of the algorithm parameters and a careful choice of the fitness function. Eventually, the EA is expected to find the optima of the adopted fitness function, and this may be even harder than solving the original pattern recognition problem when the fitness function is too hard or when there is not a consistent mapping between the (unknown) fitness optima and the (unknown) solutions of the problem at hand.

Engineers, mathematicians, analysts, programmers, and technical managers will all benefit by learning about how to evaluate this new computational tool. No special programming background is assumed.

Outline

Introduction: Evolutionary Algorithms and Pattern Recognition

Part I: Fundamental on Evolutionary Algorithms

Mimicking nature.
The evolutionary machinery.
Put EA to work: plus and minus.

Part II: Evolutionary Algorithms for Pattern Recognition

Pattern Recognition as an optimization problem
Getting harder: multimodal optimization problems
Niching methods: fitness sharing
Tuning methodology

Part III: Case study

Dynamic selection of classifiers in multi classifier system
Automatic prototyping for character recognition
Wireless network configuration optimization
Graph modelling

Discussion and final remarks

Biography

Angelo Marcelli is Associate Professor of Computer Engineering at Department of Electrical and Information Engineering of the University of Salerno, where he is also the Head of the Natural Computation Laboratory. At NCLab he leads a number of projects on using neural networks and evolutionary algorithms to solve pattern recognition related problems, such as OCR, cursive script recognition, multi-classifier systems, graph-based representation and recognition.

Dr. Marcelli received the Ph.D. in Electronic and Computer Engineering from the Department of Computer and System Engineering, University of Napoli "Federico II", Italy, in 1987. His doctoral dissertation dealt with detection and correction of shape deformations introduced by skeletonization algorithms. From 1987 to 1989 he was Leading Scientist of the Computer Vision Lab at CRIAI, where he has developed image analysis and processing systems to be deployed in industrial settings for diverse applications, such as PCB visual inspections, public telephones assembly line quality control, classification of ancient buildings degradation. From 1989 to 1997 he was appointed Assistant Professor of Computer Engineering at the Department of Computer and System Engineering, University of Napoli "Federico II", Italy, He has been Visiting Scholar at many institutions, such as the Institute of Engineering Cybernetics, Minsk (BELARUS), the Image Analysis Lab at SUNY, Stony Brook (USA), Document Analysis Lab at RPI, Troy, (USA).

Dr. Marcelli has published more than 100 technical papers on skeletonization algorithms, texture analysis, handwriting recognition, theory and application of evolutionary algorithms and neural networks, active vision model and natural computation.

Dr. Marcelli is an Area Editor for the International Journal of Document Analysis and Recognition, serves regularly as reviewer for many international journals and has been in the program committee of many international conferences. He is a member of the IEEE, the IAPR, the Italian Association for Artificial Intelligence, and President-elect of the International Graphonomics Society.

Claudio De Stefano is Associate Professor of Computer Engineering and Artificial Intelligence at the School of Engineering of the University of Cassino.

Dr. De Stefano received the Laurea degree with honors in Electronic Engineering in 1990 and the Ph.D. in Electronic and Computer Engineering in 1994, both from the University of Naples “Federico II”, Italy. From 1994 to 1996 he was Assistant Professor of Computer Science at the Department of Computer Science and Systems of the University of Naples "Federico II". In 1996 he joined the Faculty of Computer Engineering in Benevento, University of Sannio, where he has been Assistant Professor of Computer Science. Since 2001 he has been with the University of Cassino.

Dr. De Stefano has been active in the fields of pattern recognition, image analysis, machine learning and parallel computing. His current research interests include on-line and off-line handwriting recognition, cursive script segmentation, neural networks and evolutionary learning systems. He authored over 80 research papers in International Journals and Conference Proceedings.