Algorithmes evolutionnaires appliques a la
reconnaissance des formes et a la conception optique
Laval University, Quebec (QC), Canada, (May 2005)Abstract
Evolutionary Algorithms (EA) encompass a family of
robust search algorithms loosely inspired by natural
evolution. These algorithms are particularly useful to
solve problems for which classical algorithms of
optimisation, learning, or automatic design cannot
produce good results. In this thesis, we propose a
common methodological approach for the development of
EA-based intelligent systems. This methodological
approach is based on five principles: 1) to use
algorithms and representations that are problem
specific; 2) to develop hybrids between EA and
heuristics from the application field; 3) to take
advantage of multi-objective evolutionary optimization;
4) to do co-evolution for the simultaneous resolution
of several sub-problems of a common application and for
promoting robustness; and 5) to use generic software
tools for rapid development of unconventional EA. This
methodological approach is illustrated on four
applications of EA to hard problems. Moreover, the
fifth principle is explained in the study on genericity
of EA software tools.
The application of EA to complex problems requires the
use of generic software tool, for which we propose six
genericity criteria. Many EA software tools are
available in the community, but only a few are really
generic. Indeed, an evaluation of some popular tools
tells us that only three respect all these criteria, of
which the framework Open BEAGLE, developed during the
Ph.D. Open BEAGLE is organised into three main software
layers. The basic layer is made of the object oriented
foundations, over which there is the generic framework
layer, consisting of the general mechanisms of the
tool, and then the final layer, containing several
specialised frameworks implementing different EA
flavours. The tool also includes two extensions,
respectively to distribute the computations over many
computers and to visualise results.
Three applications illustrate different approaches for
using EA in the context of pattern recognition. First,
nearest neighbour classifiers are optimised, with the
prototype selection using a genetic algorithm
simultaneously to the Genetic Programming (GP) of
neighbourhood metrics. We add to this cooperative two
species co-evolution a third co-evolving competitive
species for selecting test data in order to improve the
generalisation capability of solutions. A second
application consists in designing representations with
GP for handwritten character recognition. This
evolutionary engineering is conducted with an automatic
positioning of regions in a window of attention,
combined with the selection of fuzzy sets for feature
extraction. This application is used to automate
character representation search, which is usually
conducted by human experts with a trial and error
process. For the third application in pattern
recognition, we propose an extensible system for the
hierarchical combination of classifiers into a fuzzy
decision tree. In this system, the tree topology is
evolved with GP while the numerical parameters of
classification units are determined by specialized
learning techniques. The system is tested with three
simple types of classification units. All of these
applications in pattern recognition have been
implemented using a two-objective fitness measure in
order to minimise classification errors and solutions
complexity. The last application demonstrate the
efficiency of EA for lens system design.
Self-adaptative evolution strategies, hybridised with a
specialised local optimisation technique, are used to
solve two complex optical design problems. In both
cases, the experiments demonstrate that hybridized EA
are able to produce results that are comparable or
better than those obtained by human experts. These
results are encouraging from the standpoint of a fully
automated optical design process. An additional
experiment is also conducted with a two-objectives
fitness measure that tries to maximise image quality
while minimising lens system cost.