|
Géomarketing : localisation commerciale multiple( Télécharger le fichier original )par Jérôme Baray Université de Rennes I - Doctorat 2002 |
5.3 Résolution du modèle p-médian par l'algorithme génétiqueLe logiciel Sitation part d'une population de solutions tirées au hasard. Au début, plusieurs ensembles de noeuds répondant au problème sont sélectionnés aléatoirement. La taille de la population de cet ensemble de solutions du début a été prise à 50. Chaque solution est codifiée sous forme de 0 et de 1 ce qui signifie qu'un noeud ayant été sélectionné pour recevoir un site commercial prend la valeur 1 et sinon 0 (le nombre de 1 dans chaque solution correspond donc au nombre de sites à placer).
Fig. 5.4 - Schéma d'une itération de l'algorithme génétique654 Ensuite, on a fixé à 200 le nombre d'itérations possibles sachant qu'à chaque itération s'effectue un croisement aléatoire entre des sous-ensembles de ces solutions prises deux à deux avec une probabilité de 0,9 de se croiser et une prépondérance de ces croisements entre les ensembles de solutions ayant la meilleure fonction objectif (la plus faible). En parallèle au processus de croisement, on fait intervenir une mutation dans un cas sur 400 (taux de probabilité 0,25) : un zéro est alors transformé en un et un en zéro de temps en temps. En résumé, les paramètres pris pour faire tourner l'algorithme génétique ont été les suivants : É Taille de population : 50 É Nombre d'itérations maximales : 200 É Probabilité de croisement : 0,9 É Probabilité de mutation : 0,25 La photo d'écran qui suit montre les étapes franchies au départ par l'algorithme génétique pour parvenir à une solution dans le cas de l'implantation de cinq points de vente : 654 http://perso.wanadoo.fr/matt95/algogen/AGintro.htm
Fig. 5.5 - Etapes de recherche de l'algorithme de recherche avec les localisations optimales provisoires obtenues Au départ (voir fig. 5.5), on considère d'une solution aléatoire : les noeuds 1, 3, 10, 13, 23 ont été tirés au hasard pour 5 sites commerciaux à placer. Puis, peu à peu, les solutions s'améliorent pour se rapprocher de l'optimal. A la 9ème itération, on obtient les noeuds 1, 6, 10, 13, 24 pour une fonction objective de 1 548 269. La solution obtenue en définitive au bout de 20 itérations est de placer les points de vente aux noeuds 1, 6, 10, 18, 22 conformément au résultat obtenu par les autres algorithmes. Le processus est un peu plus long que par les multiplicateurs de Lagrange qui ne prenaient que quelques secondes pour parvenir à un résultat. Si la population initiale est de 50 au lieu de 200, la solution n'est trouvée qu'en 42 itérations ce qui est logiquement plus long puisque le nombre de solutions passées en revue à la seconde est moindre qu'avec une population initiale importante. Avec les paramètres pris au départ, l'algorithme génétique donne de moins bons résultats que l'algorithme de voisinage ou l'algorithme par les multiplicateurs de Lagrange. La solution obtenue au bout de 91 itérations est de placer les points de vente aux noeuds 1, 3, 7, 9, 10, 12, 13, 22 et 23 pour une valeur de la fonction objectif de 684 927 au lieu des noeuds 1, 3, 7, 9, 10, 12, 18, 22, 23 pour une valeur de la fonction objectif plus petite et meilleure de 679 238. Le tableau suivant récapitule les résultats pour une recherche de 9 localisations et montre la similitude en terme de performance de l'algorithme par les multiplicateurs de Lagrange, de l'algorithme flou et l'algorithme de voisinage.
Tableau 5.3 - Comparatif des résultats de recherche de localisations effectuée les différents algorithmes
|
| ||||||||||||||||||||||||||||||||||||
