View
631
Download
3
Category
Preview:
DESCRIPTION
Citation preview
UNIVERSITÉ DE TECHNOLOGIE DE BELFORT-MONTBÉLIARD
AG41 Challenge 2011Soutenance de projet – P2011
Ronan Fontenay - Benjamin Guillet - Samuel Le Guelvouit21 juin 2011
Úniversité de Technologie de Belfort-MontbéliardDépartement Informatique
www.utbm.fr
Environnement de travailMéthode utilisée
Résultats obtenus
Sommaire
1 Environnement de travail
2 Méthode utiliséeAlgorithme
CaractéristiquesFonctionnement général
Solutions initialesRecherche de voisinsDétection de cycles & liste tabou
3 Résultats obtenus
AG41 Challenge 2011 – Ronan Fontenay - Benjamin Guillet - Samuel Le Guelvouit 2/15 – www.utbm.fr
Environnement de travailMéthode utilisée
Résultats obtenus
Environnement de travail
• Netbeans• Subversion
AG41 Challenge 2011 – Ronan Fontenay - Benjamin Guillet - Samuel Le Guelvouit 3/15 – www.utbm.fr
Environnement de travailMéthode utilisée
Résultats obtenus
AlgorithmeSolutions initialesRecherche de voisinsDétection de cycles & liste tabou
Caractéristiques
• Recherche tabou• Multi-threadé sur plusieurs solutions initiales• Détection de cycles• Durée tabou dynamique• Entièrement déterministe
AG41 Challenge 2011 – Ronan Fontenay - Benjamin Guillet - Samuel Le Guelvouit 4/15 – www.utbm.fr
Environnement de travailMéthode utilisée
Résultats obtenus
AlgorithmeSolutions initialesRecherche de voisinsDétection de cycles & liste tabou
Fonctionnement général
AG41 Challenge 2011 – Ronan Fontenay - Benjamin Guillet - Samuel Le Guelvouit 5/15 – www.utbm.fr
Environnement de travailMéthode utilisée
Résultats obtenus
AlgorithmeSolutions initialesRecherche de voisinsDétection de cycles & liste tabou
Solution initiale 1
AG41 Challenge 2011 – Ronan Fontenay - Benjamin Guillet - Samuel Le Guelvouit 6/15 – www.utbm.fr
Environnement de travailMéthode utilisée
Résultats obtenus
AlgorithmeSolutions initialesRecherche de voisinsDétection de cycles & liste tabou
Solution initiale 2
AG41 Challenge 2011 – Ronan Fontenay - Benjamin Guillet - Samuel Le Guelvouit 7/15 – www.utbm.fr
Environnement de travailMéthode utilisée
Résultats obtenus
AlgorithmeSolutions initialesRecherche de voisinsDétection de cycles & liste tabou
Solution initiale 3
AG41 Challenge 2011 – Ronan Fontenay - Benjamin Guillet - Samuel Le Guelvouit 8/15 – www.utbm.fr
Environnement de travailMéthode utilisée
Résultats obtenus
AlgorithmeSolutions initialesRecherche de voisinsDétection de cycles & liste tabou
Solution initiale 4
AG41 Challenge 2011 – Ronan Fontenay - Benjamin Guillet - Samuel Le Guelvouit 9/15 – www.utbm.fr
Environnement de travailMéthode utilisée
Résultats obtenus
AlgorithmeSolutions initialesRecherche de voisinsDétection de cycles & liste tabou
Recherche de voisins
AG41 Challenge 2011 – Ronan Fontenay - Benjamin Guillet - Samuel Le Guelvouit 10/15 – www.utbm.fr
Environnement de travailMéthode utilisée
Résultats obtenus
AlgorithmeSolutions initialesRecherche de voisinsDétection de cycles & liste tabou
Détection de cycles & liste tabou
AG41 Challenge 2011 – Ronan Fontenay - Benjamin Guillet - Samuel Le Guelvouit 11/15 – www.utbm.fr
Environnement de travailMéthode utilisée
Résultats obtenus
Résultats obtenus
AG41 Challenge 2011 – Ronan Fontenay - Benjamin Guillet - Samuel Le Guelvouit 12/15 – www.utbm.fr
Environnement de travailMéthode utilisée
Résultats obtenus
Conclusion
L’algorithme fournit :• toujours au moins une solution valable ;• des solutions assez bonnes.
AG41 Challenge 2011 – Ronan Fontenay - Benjamin Guillet - Samuel Le Guelvouit 13/15 – www.utbm.fr
Environnement de travailMéthode utilisée
Résultats obtenus
Sources
• Études en recherche locale adaptative pour l’optimisationcombinatoire, Isabelle Devarenne ;
• Recherche tabou avec liste candidate adaptative, I.Devarenne,H. Mabed et A. Caminada.
AG41 Challenge 2011 – Ronan Fontenay - Benjamin Guillet - Samuel Le Guelvouit 14/15 – www.utbm.fr
Environnement de travailMéthode utilisée
Résultats obtenus
Remerciements
Avez-vous des questions ?
AG41 Challenge 2011 – Ronan Fontenay - Benjamin Guillet - Samuel Le Guelvouit 15/15 – www.utbm.fr
Recommended