CIAC hybridé avec une recherche locale
Un algorithme de colonie de fourmis en variables continues hybridé avec un algorithme de recherche locale.
par
nojhan le 6 mars 2003
Le premier algorithme inspiré des colonies de fourmis
(le "Ant System" [1]), a été appliqué à divers problèmes
d’optimisation combinatoire avec succès. Par la suite,
un petit nombre de travaux ont été consacrés à l’adaptation
au cas continu de cette nouvelle métaheuristique. Le
premier algorithme conçu pour l’optimisation de
fonctions continues est l’algorithme CACO ("Continuous
Ant Colony Algorithm" [2]). Tous ces algorithmes
retiennent un trait particulier du comportement des
fourmis réelles : le dépôt de piste de phéromone. En effet,
la colonie de fourmis est souvent décrite comme un systè
me distribué capable de résoudre des problèmes complexes
de par la mise en jeu de processus "stigmergiques", dé
finis comme une forme de communication indirecte, par
le biais de modifications de l’environnement.
Mais le dépôt de piste est aussi rencontré dans certains
processus de "recrutement", défini par les biologistes
comme un mode de communication conduisant quelques
individus à se réunir à un endroit où un travail est né
cessaire. Une autre méthode d’optimisation s’inspirant
de cette définition a été développée dans le cas continu :
l’algorithme API, inspiré par le comportement de
recrutement d’une fourmi primitive [3]. Cependant,
l’algorithme API utilise peu les structures mémorielles
qui caractérisent généralement les systèmes de colonies de
fourmis [4], à savoir la présence d’une mémoire externe, partagé
e par les agents.
Notre point de vue est que la métaphore des colonies de
fourmis peut être définie comme un modèle mettant en jeu
non seulement des phénomènes stigmergiques, mais aussi,
plus largement, des processus de recrutement. Nous
avons développé, dans cette optique, une méthode
d’optimisation continue, inspirée des colonies de
fourmis, qui exploite le concept de communication
interindividuelle [5]. Cette méthode, dénommée CIAC ("
Continuous Interacting Ant Colony"), s’applique à la fois à
la recherche globale et à la recherche locale d’un
optimum. Ce nouvel algorithme a été testé sur un large
ensemble de fonctions analytiques, comprenant un grand
nombre de variables (jusqu’à 100), et comparé avec les
meilleures méthodes publiées (autres algorithmes fondés
sur les colonies de fourmis, algorithmes génétiques,
recherche tabou et recuit simulé).
Comme le "Ant System" original, notre algorithme est
moins compétitif dans le domaine de la recherche
locale, malgré une recherche globale relativement
efficace. Pour pallier à ce problème, nous avons choisi
d’implémenter une hybridation avec l’algorithme du "simplex"
de Nelder-Mead [6], nous avons appelé cet algorithme
hybridé "HCIAC". Plusieurs versions de l’algorithme
hybridé ont été implémentées (cf. figure [figAlgoHybride]), du fait des
différentes possibilités de relations entre les deux
méthodes : relation temporelle (la recherche locale est
lancée à intervalles réguliers à partir de la meilleure
solution) ou relation spatiale (la recherche locale est
lancée indépendamment par chaque fourmi). Nous
qualifierons le premier algorithme d’hybridation "simple"
, puisqu’il s’agit simplement d’améliorer la meilleure
solution à un temps donné. La seconde hybridation
permet de maintenir l’aspect fortement décentralisé qui
caractérise les algorithmes de colonies de fourmis. En
effet, chaque agent décide de pratiquer une recherche
locale uniquement sur les informations dont il dispose,
et non pas (comme dans le premier cas) sur des
informations globales. On peut qualifier cette
hybridation de "décentralisée".
Deux hybridations possibles entre l’algorithme CIAC et
le "simplex" de Nelder-Mead
L’algorithme hybride HCIAC est aujourd’hui testé sur le
même jeu de fonctions que l’algorithme CIAC et il
présente des améliorations notables sur certains
points.
[1] A. Colorni, M. Dorigo, V. Maniezzo. "Distributed
Optimization by Ant Colonies". Proceedings of ECAL91 -
European Conference on Artificial Life, 134-142.
Elsevier Publishing, 1991.
[2] G. Bilchev, I.C. Parmee, "The Ant Colony Metaphor
for Searching Continuous Design Spaces", Lecture Notes
in Computer Science, 993, 25-39, 1995.
[3] N. Monmarché, G. Venturini, M. Slimane, "On how
Pachycondyla apicalis ants suggest a new search algorithm"
, Future Generation Computer Systems , 16, 937-946,
2000.
[4] E.D. Taillard, L. Gambardella, M. Gendreau, J-Y.
Potvin, "Adaptive Memory Programming : A Unified View of
Metaheuristics", EURO XVI Conference Tutorial and
Research Reviews booklet, Brussels, July 1998.
[5] J. Dréo, P. Siarry, "Un nouvel algorithme de colonie
de fourmis exploitant la communication directe entre
individus ; application à l’optimisation en variables continues"
, ROADEF 2002 - 4ème congrès de la Société Française de
Recherche Opérationnelle et d’Aide à la Décision,
Paris, ENST, 120-121, février 2002.
[6] J.A. Nelder, R. Mead. "A simplex method for function
minimization." The Computer Journal, 7(4):308-313, 1965.
Téléchargements
-
Présentation
: L’ensemble des transparents.
(OpenOffice Impress - 572 ko)
-
Résumé
: Tel que inclus dans les proceedings.
(PDF - 98.6 ko)
Commentaires
Par Woulif,
le 11 juillet 2014 :
CIAC hybridé avec une recherche locale
Agréable après-midi qui débute par la lecture intéressante. Anne du comparatif de
banque en ligne
Par Pamela1,
le 7 juillet 2014 :
CIAC hybridé avec une recherche locale
Génial, je vous lirai désormais ! Pamela de
amb-allemagne .fr
Par Rosella,
le 5 décembre 2013 :
CIAC hybridé avec une recherche locale
Je découvre à l’instant votre avis sur la question, j’ai trouvé ça très intéressant... Rosella webmaster de ce
site de voyance gratuit en ligne.
Par trulocke,
le 8 juillet 2014 :
Poster un message [NoJhan - Site perso]
Choisissez ceci rayon puis ce localisation sur Internet ou toi desirez accomplir vos courses Selectionnez subsequemment cela bon promo Auchan lequel toi-meme convient cela code promo mon eden davantage puis cliquez sur lui-meme aupres cela demasquer alors ouvrir ceci orientation sur Internet en compagnie de la echoppe.
Par Justine1,
le 28 novembre 2013 :
CIAC hybridé avec une recherche locale
Votre article s’est avéré indispensable pour conforter mes propos durant une discussion lancée par ma mère, mes remerciements ! Justine du guide complet sur les
banques en ligne
Par jonburnell,
le 4 juillet 2014 :
Poster un message [NoJhan - Site perso]
Bouygues Telecom incessant sur sa lancee apres les soldes. Cinq smartphones, apres non indiscutables moindres, sont proposes au solde exceptionnel en tenant code reduction mon eden 1 avec les forfaits Eden Smartphone. Samsung Galaxy S2, Sony-Ericsson Xperia Arche, BlackBerry Torch 9860, Nokia Lumia 800 apres le total dernier arrive, cela Motorola Razr !
Par Florent12,
le 27 novembre 2013 :
CIAC hybridé avec une recherche locale
J’ai déniché divers post qui en parlaient, j’apprécie la cohérence de vos observations ! Florent du site internet de
idées cadeaux
Par John85,
le 19 novembre 2013 :
CIAC hybridé avec une recherche locale
Ce website est franchement bien agencé, d’ailleurs ça incite à le suivre ponctuellement pour apprécier votre travail !
John de
http://www.proteine-pas-cher.info
Par Stephanie2,
le 21 décembre 2013 :
CIAC hybridé avec une recherche locale
Vraiment enchanté d’être tombé par hasard sur votre article, je saisis la plume comme vous de temps en temps, alors j’arrive à identifier un résultat qualitatif. Stephanie du site de banque en ligne
Par Thom,
le 22 avril 2014 :
CIAC hybridé avec une recherche locale
Je suis un cinglé des forums, et je survole plein d’articles en permanence, mais le votre mérite qu’on s’y arrête. Thom du guide sur les robots option binaire
Par rrutam,
le 8 septembre 2014 :
Poster un message [NoJhan - Site perso]
Codes promotionnels Mon eden apres autres offre actuelles Codes Reductions Mon Eden valables recemment egalement utiliser rare Code Reduction au contraire former fondes economies dans Mon Eden ? Hop, seul sommaire bon organigramme code reduction mon eden pour outrepasser ce week-end tranquillement ! Allike Rideau resultat unique code promotion donnant debout a 20% avec reduction supplementaire sur les rapport deja en promotion.
Ce forfait Eden smartphone 3h orient propose a 49,90 /salaire avec 3 n° pendant illimite, ces SMS/MMS illimites ensuite internet changeant avec 2Go avec Fair Penchants (gout modem inclus, VoIP, TV 3G). Ceci forfait Eden smartphone 24/24 est propose a 59,90 /mensualite en compagnie de les clameur illimites, les SMS/MMS illimites alors internet ambulant avec 3Go avec Fair Use (style modem inclus, VoIP, TV 3G). Ensuite apparament moi-meme recevrai seul DVD, mais pourquoi nous-memes envoyer un DVD alors lequel’il suffirait correct en compagnie de nous envoyer rare code ? bizarre delai en meme temps que 14 jours en contrepartie barrer sa commande apres acquerir ceci remboursement a exclusion de frais puis cette possibilite en compagnie de contacter le localisation au contraire bizarre informat.
Par Nicolas24,
le 16 novembre 2013 :
CIAC hybridé avec une recherche locale
J’ai parfaitement compris votre propos, franchement je trouve l’article vraiment intéressant. Benoit
PS : mon antivirus me signal quelques programmes vérolés sur certaines zones, peut-être de la doc au sein de web sites comme www.comparateurantivirus.com (
telecharger antivirus gratuit). Nicolas
Par Helene,
le 20 décembre 2013 :
CIAC hybridé avec une recherche locale
J’apprécie vraiment votre plume, ça m’incite à réécrire, de temps à autre ! Helene du site parlant de la meilleur banque en ligne
Par Tony,
le 22 avril 2014 :
CIAC hybridé avec une recherche locale
Salut, c’est que du lourd, c’est assez rare. Tony du portail web sur les robot option binaire
Par Benoit,
le 16 novembre 2013 :
CIAC hybridé avec une recherche locale
J’ai lu avec plaisir votre avis sur la question, nos réflexions convergent !
Ah, j’allais oublier un détail : j’ai vu des virus par endroit, éventuellement des solutions sur des sites comme
www.comparatif-antivirus.net (
comparatif antivirus gratuit).
Par Julien76,
le 13 novembre 2013 :
commentaire de julien76
Le look de votre site internet est très agréable, je vais revenir sous peu !
Merci car tomber sur des indications rationnelles n’est que peu souvent simple.
J’oubliais : j’ai constaté des soucis sur certaines zones, vous pourriez vous renseigner sur www.comparateurantivirus.fr (telecharger antivirus gratuit).
Julien.
Par Isis,
le 28 janvier 2014 :
commentaire de julien76
Votre texte m’a servi à étayer mon point de vue et ainsi persuader un collègue de la justesse de mon opinion à ce sujet ! Isis du guide complet Ccyds
Par Katy,
le 21 avril 2014 :
commentaire de julien76
Je lisais votre énoncé, et je reconnais que son contenu m’a enchanté. Katy du portail web de robot d’options binaires
Par Samuel15,
le 4 août 2014 :
commentaire de julien76
Génial, je vous suivrai désormais ! Samuel du comparateur des meilleures banques
Par Pauline,
le 7 novembre 2013 :
CIAC hybridé avec une recherche locale
Bonjour, j’ai véritablement apprécier de faire le tour de les pages de votre site !
Merci bien, il n’est pas toujours simple de trouver des explications pertinentes.
Ah, au fait : defender me dit qu’il y a quelques 404 par endroit, vous pourriez peut-être trouver des solutions au sein de sites internet tels comparateurantivirus .com/ (avast antivirus gratuit).
Pauline.
Par Malika,
le 18 décembre 2013 :
CIAC hybridé avec une recherche locale
J’ai très bien saisi vos propos, et c’est très intéressant... Malika du site proteine-pas-cher .net
Par Serena2,
le 23 décembre 2013 :
CIAC hybridé avec une recherche locale
Ça fait déjà le quatrième texte que je déniche là-dessus, bravo pour la clarté de vos propos ! Serena du site abordant le comparatif de banque en ligne
Par Murielle,
le 3 novembre 2013 :
CIAC hybridé avec une recherche locale
[J’avoue que ce fût une chouette expérience que de faire le tour de les pages de votre site internet !
Bravo pour ce boulot car décrocher de la documentation correcte n’est que peu souvent simple.
J’oubliais : defender m’alerte que vous avez des virus sur certaines pages, vous devriez vraisemblablement trouver des solutions sur
comparateur-antivirus .net (antivirus gratuit).
Murielle.
Par Nicolasc82,
le 2 novembre 2013 :
commentaire de Nicolasc82
Nombre d’articles en ligne n’offrent pas ce ton rationnel, ça change plaisamment ! Nico du site traitant de la
comparatif banque en ligne
Par Charlote,
le 12 novembre 2013 :
commentaire de Nicolasc82
Vraiment, on devrait pouvoir trouver beaucoup plus d’écrits de ce genre sur Internet.
Michael de http://www.proteine-musculation.info
Par Morgane18,
le 3 février 2014 :
commentaire de Nicolasc82
Vraiment ric-rac pour mon pointage au travail aujourd’hui, j’ai zappé la pendule, j’étais absorbé par vos réflexions avisées ! Morgane du blog sur la banques
Par Gabriel18,
le 2 août 2014 :
commentaire de Nicolasc82
Vous procurez vos arguments avec brio. Félicitations. Ronnie du comparatif de banques en ligne
Par jeanblois,
le 10 décembre 2013 :
Merci pour les infos
je Bookmark peu souvent un blog à mes favoris mais là je dois dire que je suis etonné
On garde le contact
comparateur d’assurance moto suisse
- assurance scooter 50 matmut
- assurance scooter 50cc en ligne
- assurances scooter
- assurance pas chere pour scooter 50
- assurances scooter en ligne
- assurance scooter 125 comparatif
Par lucigeny,
le 8 avril 2014 :
Merci pour les infos
Bonsoir à tous,
Il m’est impossible de charger la page curieusement, c’est mystérieux ça mouline en permanence juste a coté du logo. Longue vie à ce site internet :D lucigeny professionnelle de l’investissement immobilier locatif, plus d’aide. Vous pouvez investir dans unappartement neuf et bénéficier d’une réduction d’impôts de dix-huit pourcent du montant du bien avec la loi duflot.
Par Clara69,
le 17 janvier 2014 :
commentaire de Nicolasc82
J’ai parfaitement saisi ce que vous avez écrit, d’ailleurs nos analyses convergent ! Clara pour le compte de cours à domicile
Par noemie06,
le 22 février 2014 :
commentaire de Nicolasc82
Un moment de relecture, merci à toi
Bon après midi
assurance scooter 50cc pas cher forum
- assurance scooter 50cc en ligne pas cher
- comparatif tarif assurance scooter 50
- assurance scooter 125cc pas cher
- assurances scooter axa
- comparer prix assurance moto suisse
- assurance pour scooter 50 cm3
Par JulietteDu,
le 16 octobre 2013 :
CIAC hybridé avec une recherche locale
Il était indispensable de poster un message de congratulations pour la tenue de votre site. Les papiers écris avec un style semblable au votre sont un régal à lire.
Par Sabil18,
le 18 novembre 2013 :
CIAC hybridé avec une recherche locale
Vraiment heureux d’être tombé en me promenant sur ce billet, en plus d’un propos instructif, je trouve ça bien dit et agencé sans fioritures. Sabil du site sur ingdirect
Par Magalie1,
le 20 décembre 2013 :
CIAC hybridé avec une recherche locale
Ton agréable et propos adaptés, c’est réjouissant de dégoter du sérieux au sein de la sphère numérique ! Magalie du portail web de banque en ligne 2014
Par Bruno1,
le 10 janvier 2014 :
CIAC hybridé avec une recherche locale
L’ergonomie de ce site m’a décidé à faire de même, mes remerciements de m’avoir stimulé. Bruno de www.meilleurebanque2014. com
Par Anne11,
le 10 juillet 2014 :
CIAC hybridé avec une recherche locale
Excellent billet, merci ! Anne du comparateur de banques en ligne