Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

optimisation par colonie de fourmis

PFE
by

hiba jendoubi

on 16 June 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of optimisation par colonie de fourmis

Encadré par: Mr Ali MOUSSA
Mr Bassem KORDOGHLI

Présentation du projet de fin d'études
Ecole Nationale d'Ingénieurs de Monastir
Plan de la présentation
Plan
2
Introduction
I
Avec
1. Introduction et objetcifs
2. Algorithme des colonies de fourmis
3. Application pour un problème d'ordonnancement
4. Prèsentation et analyse des résultats
5. Conclusion et perspectives
2. Algorithme de colonie de fourmis
t = 0
t = t1
Problème de voyageur de commerce
Decription du problème


Faire une tournée de n villes en visitant chacune une seule fois.

Trouver la succession de villes avec la distance la plus minimale que possible.

Un problème trop complexe pour faire une énumération de toutes les solutions possibles.
Illustration de la Complexité du problème
Comportement des fourmis dans la nature
Nombre de villes à parcourir
Nombre de solutions possibles
Temps d'éxécution sur "K"
5
20
30
5! = 120
20! = 10^18
30! = 10^32
0.12*10^(-12) secondes
40 minutes
10^10 ans
Principe de résolution
Réalisé par JENDOUBI Hiba
Les problèmes d'optimisation combinatoire
Les méthodes exactes
Les métaheuristiques
Approche constructive
Approche de recherche locale
Approche hybride
Approche évolutive
La théorie des colonies de fourmis
L'ordonnancement
Consiste à organiser un ensemble de tâches en tenant compte de certains contraintes.
Il a pour objectif :

Organiser l'exploitation des ressources

Déterminer la chronologie des tâches

Déterminer les implantations nécessaires dans l'atelier
1. Introduction
Application de la théorie des colonies de fourmis pour une implantation plus rentable dans un atelier de confection
Le choix de la ville de départ se fait aléatoirement par chaque fourmi;

Initialisation du taux de phéromones entre les villes par la création d'une matrice;

La quantité de phéromones Δτ est déposée à la fin de chaque trajet;

L'évaporation se fait par multiplication de la matrice contenant les taux de phéromones par le paramétre d'évaporation;

Choix de la nouvelle ville :

- Plus la ville est loin moins elle a la chance d'être choisie

- Plus le chemin est couvert de phéromones plus il est choisie
Méthodes de résolution
3. Optimisation de colonie de fourmis du problème d'ordonnancement
Description du problème
Changement excessif de machines après chaque ordre de fabrication pour les entreprises travaillant des petites collections

Un nombre de commandes peut atteindre dix commandes par jour ce qui nécessite un changement courant d'implantation.
Ceci peut causer :
Une perte d'énergie
Une perte de temps
Nombre de commandes
Nombre de changements de machines
Temps de changements
5
20
80 min
10
150
600 min
880 min
220
20
Il faut chercher un ordonnancement ayant un minimum de nombre de changements de machines en appliquant la méthode de colonie de fourmis
Étapes de résolution
Avec
Commande 1
Commande 5
Commande 4
Commande 3
Commande 2
Avec
1.Choix aléatoire de la première commande
Commande 6
2. Choix de la deuxième commande
Avec:
3. Mise à jour du taux de phéromones
Cette mise à jour se fait suivant la formule:
Avec:
4. Enchaînement
Une fois le nombre de fourmis et le nombre d'itérations est atteint le programme affiche le résultat optimal.
Importance des différents paramètres
Il faut avoir suffisamment de fourmis.

La quantité de phèromones déposée Δτ permet la mémorisation des ordonnancement déjà choisis.

Le paramètre d'évaporation ρ permet de garder une quantité de phéromones raisonnable pour que les fourmis puissent y être sensibles.

La borne minimale permet de contrôler le niveau de phéromones de chaque chemin pour éviter les valeurs nulles.
ij
4. Analyse des résultats
Full transcript