Méthode de comparaison statistique des performances d'algorithmes évolutionnaires

Barrette, Mathieu (2008). Méthode de comparaison statistique des performances d'algorithmes évolutionnaires. Mémoire de maîtrise électronique, Montréal, École de technologie supérieure.

Prévisualisation	PDF Télécharger (35MB) | Prévisualisation
Prévisualisation	PDF Télécharger (6MB) | Prévisualisation

Résumé

Il existe un nombre impressionnant de métaheuristiques pour l'optimisation globale. Les performances de ces algorithmes varient énormément, et comme le stipule le No Free Lunch Theorem, elles sont intimement liées à la structure du problème à optimiser et au paramétrage de l'algorithme. Le choix d'une métaheuristique et de son paramétrage pour un problème donné est une tâche complexe qui nécessite une bonne connaissance des algorithmes et du problème à optimiser. Une compréhension approfondie des comportements des métaheuristiques, de leur performance et de leur spécificité (le No Free Lunch Theorem) constitue une première étape vers une meilleure utilisation de celles-ci. Toutefois, étant des processus stochastiques itératifs, l'évaluation des performances de ces algorithmes requiert l'utilisation d'outils statistiques appropriés. Il n'existe actuellement aucune méthodologie universelle de comparaison des performances des métaheuristiques. Nous proposons donc ici une méthodologie générique statistiquement rigoureuse de comparaison relative des performances avec un risque d'erreur contrôlé. La méthodologie proposée est non paramétrique et utilise le rang des observations pour évaluer leurs différences. L'utilisation du rang permet ici à la fois de faire une étude non paramétrique mais permet aussi de consolider sous un seul indice de qualité, sans ajout de pondérations, les trois mesures de performance généralement observées, soit le nombre d'itérations moyen requis pour l'atteinte de l'optimum global, le niveau d'optimisation moyen et finalement, le taux d'atteinte de l'optimum global. Nous proposons également une étude complète pour une plage de paramétrage temporel choisi. Contrairement aux comparaisons habituelles d'un seul
paramétrage temporel, cette façon de faire reflète beaucoup mieux le comportement temporel global des métaheuristiques et rend l'étude beaucoup plus complète.

Titre traduit

Evolutionary algorithms performance evaluation using rank-based multiple comparison procedure

Résumé traduit

An impressive number of metaheuristics for global optimization have been developed since the apparition of the concept in the early 60's. As the No Free Lunch Theorem proved it, the performance of a metaheuristic is strongly related to its parameterization and to the structure of the problem to optimize. The choice of the optimal metaheuristic and its best parameterization for a specifie problem is still a complex task and rely almost only on the intuition and the experience of the practitioner. A performance evaluation procédure of those processes can significantly help to understand the specificity and the evolving scheme of the metaheuristics. As metaheuristics are stochastic process, it must be done with the proper statistical tools. We propose a statistically rigorous methodology to compare the performance of different stochastic optimization algorithms. Our methodology is nonparametric and uses the rank of the data. The use of the rank instead of the true value of the data is statistically less powerfiil but it has the advantage to unify the three major performance criteria under a unique ranking number, without the use of arbitrary artifacts such as weighting coefficients. We also extend the analysis to a complete temporal range which gives an accurate representation of the performance on a complete range of temporal variations.

Type de document:	Mémoire ou thèse (Mémoire de maîtrise électronique)
Renseignements supplémentaires:	"Mémoire présenté à l'École de technologie supérieure comme exigence partielle à l'obtention de la maîtrise en génie électrique." Bibliogr : f. [118]-121.
Mots-clés libres:	Algorithmes Performances. Statistique Méthodologie. Métaheuristiques. algorithme évolutionnaire, comparaison de performance, comparaison multiple, optimisation, test d'hypothese
Directeur de mémoire/thèse:	Directeur de mémoire/thèse Wong, Tony
Codirecteur:	Codirecteur De Kelper, Bruno
Programme:	Maîtrise en ingénierie > Génie électrique
Date de dépôt:	04 août 2010 13:28
Dernière modification:	02 déc. 2016 20:41
URI:	https://espace.etsmtl.ca/id/eprint/156

Gestion Actions (Identification requise)

Dernière vérification avant le dépôt