• Document: Conception d'un module de tests de métaheuristiques
  • Size: 1.24 MB
  • Uploaded: 2019-02-13 16:13:15
  • Status: Successfully converted


Some snippets from your converted document:

Conception d'un module de tests de métaheuristiques Rapport de stage Maîtrise d'informatique Université de Cergy-Pontoise Jean-Philippe Aumasson Sous la direction de Johann Dréo LISSI, Université Paris 12 Val-de-Marne 61, avenue du Général de Gaulle 94010, Créteil cedex tél : 01.45.17.14.94 fax : 01.45.17.14.92 Avant-propos J'ai dès le début de l'année voulu eectuer mon stage de n de diplôme dans un centre de recherche, et j'ai ainsi pris contact avec Johann Dréo n octobre 2004, une ore de stage type bac +5 étant proposée sur sa page personnelle. Après un entretien quelques jours après nous nous sommes entendus pour un stage d'une durée de deux mois, relatif à l'étude automatisée des métaheuristiques, domaine quelque peu marginal de l'optimisation. Nous reviendrons plus en dé- tails sur le sujet dans la deuxième partie du rapport. A l'époque le laboratoire se nommait encore LERISS, aujourd'hui c'est le LISSI, regroupant plusieurs ac- tivités, qui m'accueillera. Mon travail sera dans la continuité du projet Open Metaheuristic, initié par Johann Dréo en début d'année, dont le code source est disponible publiquement sur le site de l'hébergeur, à l'adresse suivante : http ://ometah.berlios.de. Comme c'est l'usage, quelques lignes seront accordées à la présentation du labo- ratoire, nous livrerons ensuite une introduction générale au stage présentant les notions théoriques, et la mission qui me sera conée. La seconde partie décrivant mon activité au cours de ces deux mois est divisée en deux chapitres : le premier concernera la partie la plus importante de mon travail, soit la conception du mo- dule de tests, le second présentera quelques algorithmes implémentés, existants ou originaux, avec des comparaisons de leurs performances. Après avoir conclu, on pourra trouver en annexe les spécications (formule et graphe) des problèmes utilisés qui n'ont pas été détaillés dans le corps du rapport, et enn de courtes portions du code produit. Table des matières I Introduction 6 1 Le laboratoire LISSI 7 2 Sujet d'étude 9 2.1 Optimisation discrète et continue . . . . . . . . . . . . . . . . . . 9 2.2 Métaheuristiques . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.3 Problèmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.3.1 Présentation . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.3.2 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.4 But du stage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.5 Outils . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.6 Le projet Open Metaheuristic . . . . . . . . . . . . . . . . . . . . 15 2.6.1 Présentation . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.6.2 Logiciel libre . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.6.3 Conception de l'interface . . . . . . . . . . . . . . . . . . 16 II Activités 18 3 Le module de test 19 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.1.1 Objectifs . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.1.2 Projets existants . . . . . . . . . . . . . . . . . . . . . . . 19 3.1.3 Critères de test . . . . . . . . . . . . . . . . . . . . . . . . 20 3 3.1.4 Contraintes . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.1.4.1 Utilisation en script . . . . . . . . . . . . . . . . 21 3.1.4.2 Limitation du temps de calcul . . . . . . . . . . 21 3.1.4.3 Compatibilité . . . . . . . . . . . . . . . . . . . . 22 3.1.5 Outils . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.2 Récupération des données . . . . . . . . . . . . . . . . . . . . . . 23 3.2.1 Interêt du XML . . . . . . . . . . . . . . . . . . . . . . . 23 3.2.2 Parsing avec le module xml . . . . . . . . . . . . . . . . . 23 3.2.3 Réecriture du traitement . . . . . . . . . . . . . . . . . . . 23 3.3 Fonctionnement . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.3.1 Structure du calcul . . . . . . . . . . . . . . . . . . . . . . 24 3.3.2 Génération d'aléatoire . . . . . . . . . . . . . . . . . . . .

Recently converted files (publicly available):