[Accueil] - [Plan du site] - [Rechercher] - [ C O L R T S P ]  

 
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

Congrès : ROADEF 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 Woulifle 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 Pamela1le 7 juillet 2014 : CIAC hybridé avec une recherche locale
Génial, je vous lirai désormais ! Pamela de amb-allemagne .fr
Par Rosellale 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 trulockele 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 Justine1le 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 jonburnellle 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 Florent12le 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 John85le 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 Stephanie2le 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 Thomle 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 rrutamle 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 Nicolas24le 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 Helenele 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 Tonyle 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 Benoitle 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 Julien76le 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 Isisle 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 Katyle 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 Samuel15le 4 août 2014 : commentaire de julien76
    Génial, je vous suivrai désormais ! Samuel du comparateur des meilleures banques
Par Paulinele 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 Malikale 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 Serena2le 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 Muriellele 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 Nicolasc82le 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 Charlotele 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 Morgane18le 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 Gabriel18le 2 août 2014 : commentaire de Nicolasc82
      Vous procurez vos arguments avec brio. Félicitations. Ronnie du comparatif de banques en ligne

    Par jeanbloisle 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 lucigenyle 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 CorrinehDominguezle 16 décembre 2013 : Merci pour les infos

    Un article enrichissant. Continuez !

    comparatif assurance moto gratuit


    Par Clara69le 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 noemie06le 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 JulietteDule 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 Sabil18le 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 Magalie1le 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 Bruno1le 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 Anne11le 10 juillet 2014 : CIAC hybridé avec une recherche locale
    Excellent billet, merci ! Anne du comparateur de banques en ligne

Articles populaires

[Accueil] - [Plan du site] - [Rechercher] - [Admin.]       SPIP:Squelette