Les algorithmes évolutionnaires (AE) constituent une famille d’algorithmes inspirés
de l’évolution naturelle. Ces algorithmes sont particulièrement utiles pour la résolution
de problèmes où les algorithmes classiques d’optimisation, d’apprentissage ou de
conception automatique sont incapables de produire des résultats satisfaisants. On propose
dans cette thèse une approche méthodologique pour le développement de systèmes
intelligents basés sur les AE. Cette approche méthodologique repose sur cinq principes :
1) utiliser des algorithmes et des représentations adaptés au problème ; 2) développer
des hybrides entre des AE et des heuristiques du domaine d’application ; 3) tirer profit
de l’optimisation évolutionnaire à plusieurs objectifs ; 4) faire de la co-évolution pour
résoudre simultanément plusieurs sous-problèmes d’une application ou favoriser la robustesse
; et 5) utiliser un outil logiciel générique pour le développement rapide d’AE
non conventionnels. Cette approche méthodologique est illustrée par quatre applications
des AE à des problèmes difficiles. De plus, le cinquième principe est appuyé par l’étude
sur la généricité dans les outils logiciels d’AE.
Le développement d’applications complexes avec les AE exige l’utilisation d’un outil
logiciel générique. Six critères sont proposés ici pour évaluer la généricité des outils
d’AE. De nombreux outils logiciels d’AE sont disponibles dans la communauté, mais peu
d’entre eux peuvent être véritablement qualifiés de génériques. En effet, une évaluation
de quelques outils relativement populaires nous indique que seulement trois satisfont
pleinement à tous ces critères, dont la framework d’AE Open BEAGLE, développée
durant le doctorat. Open BEAGLE est organisé en trois couches logicielles principales,
avec à la base les fondations orientées objet, sur lesquelles s’ajoute une framework gén
érique comprenant les mécanismes généraux de l’outil, ainsi que plusieurs frameworks
spécialisées qui implantent différentes saveurs d’AE. L’outil comporte également deux
extensions servant à distribuer des calculs sur plusieurs ordinateurs et à visualiser des
résultats.
Ensuite, trois applications illustrent différentes approches d’utilisation des AE dans
un contexte de reconnaissance des formes. Premièrement, on optimise des classifieurs basés sur la règle du plus proche voisin avec la sélection de prototypes par un algorithme
génétique, simultanément à la construction de mesures de voisinage par programmation
génétique (PG). À cette co-évolution coopérative à deux espèces, on ajoute la
co-évolution compétitive d’une troisième espèce pour la sélection de données de test,
afin d’améliorer la capacité de généralisation des solutions. La deuxième application
consiste en l’ingénierie de représentations par PG pour la reconnaissance de caractères
manuscrits. Cette ingénierie évolutionnaire s’effectue par un positionnement automatique
de régions dans la fenêtre d’attention jumelé à la sélection d’ensembles flous pour
l’extraction de caractéristiques. Cette application permet d’automatiser la recherche de
représentations de caractères, opération généralement effectuée par des experts humains
suite à un processus d’essais et erreurs. Pour la troisième application en reconnaissance
des formes, on propose un système extensible pour la combinaison hiérarchique de classifieurs
dans un arbre de décision flou. Dans ce système, la topologie des arbres est
évoluée par PG alors que les paramètres numériques des unités de classement sont détermin
és par des techniques d’apprentissage spécialisées. Le système est testé avec trois
types simples d’unités de classement. Pour toutes ces applications en reconnaissance
des formes, on utilise une mesure d’adéquation à deux objectifs afin de minimiser les
erreurs de classement et la complexité des solutions.
Une dernière application démontre l’efficacité des AE pour la conception de syst`
emes de lentilles. On utilise des stratégies d’évolution auto-adaptatives hybridées avec
une technique d’optimisation locale spécialisée pour la résolution de deux problèmes
complexes de conception optique. Dans les deux cas, on démontre que les AE hybrides
sont capables de générer des résultats comparables ou supérieurs à ceux produits par
des experts humains. Ces résultats sont prometteurs dans la perspective d’une automatisation
plus poussée de la conception optique. On présente également une expérience
supplémentaire avec une mesure à deux objectifs servant à maximiser la qualité de
l’image et à minimiser le coût du système de lentilles. / 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 optimization, 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 organized 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 specialized frameworks implementing
different EA flavors. The tool also includes two extensions, respectively to distribute
the computations over many computers and to visualize results.
Three applications illustrate different approaches for using EA in the context of
pattern recognition. First, nearest neighbor classifiers are optimized, with the prototype
selection using a genetic algorithm simultaneously to the Genetic Programming (GP) of
neighborhood metrics. We add to this cooperative two species co-evolution a third coevolving
competitive species for selecting test data in order to improve the generalization 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
minimize classification errors and solutions complexity.
The last application demonstrate the efficiency of EA for lens system design. Selfadaptative
evolution strategies, hybridized with a specialized 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 maximize image
quality while minimizing lens system cost.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QQLA.2005/22701 |
| Date | 05 1900 |
| Creators | Gagné, Christian |
| Contributors | Parizeau, Marc |
| Publisher | Université Laval |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | French |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation |
| Format | text/html, application/pdf |
| Rights | © Christian Gagné, 2005 |
Page generated in 0.003 seconds