Algorithme mémétique - Memetic algorithm

En informatique et en recherche opérationnelle , un algorithme mémétique (MA) est une extension de l' algorithme génétique traditionnel . Il utilise une technique de recherche locale pour réduire la probabilité d'une convergence prématurée.

Les algorithmes mémétiques représentent l'un des domaines de recherche en croissance récents dans le calcul évolutif . Le terme MA est maintenant largement utilisé comme une synergie d'approche évolutive ou basée sur la population avec des procédures d'apprentissage individuel ou d'amélioration locale distinctes pour la recherche de problèmes. Très souvent, les MA sont également appelées dans la littérature des algorithmes évolutionnaires (EA) baldwiniens , des EA lamarckiens, des algorithmes culturels ou une recherche locale génétique.

introduction

Inspiré à la fois des principes darwiniens de l'évolution naturelle et de la notion de mème de Dawkins , le terme algorithme mémétique (MA) a été introduit par Pablo Moscato dans son rapport technique en 1989 où il considérait MA comme étant proche d'une forme de génétique hybride basée sur la population. algorithme (GA) couplé à une procédure d'apprentissage individuelle capable d'effectuer des raffinements locaux. Les parallèles métaphoriques, d'une part, avec l'évolution darwinienne et, d'autre part, entre les mèmes et les heuristiques spécifiques au domaine (recherche locale) sont capturés dans les algorithmes mémétiques, créant ainsi une méthodologie qui équilibre bien la généralité et la spécificité du problème. Cette nature en deux étapes en fait un cas particulier d' évolution en deux phases .

Dans un contexte plus diversifié, les algorithmes mémétiques sont désormais utilisés sous divers noms, notamment les algorithmes évolutionnaires hybrides, les algorithmes évolutionnaires baldwiniens, les algorithmes évolutionnaires lamarckiens, les algorithmes culturels ou la recherche locale génétique. Dans le contexte de l'optimisation complexe, de nombreuses instanciations différentes d'algorithmes mémétiques ont été rapportées dans un large éventail de domaines d'application , en général, convergeant vers des solutions de haute qualité plus efficacement que leurs homologues évolutifs conventionnels.

En général, l'utilisation des idées de mémétique dans un cadre de calcul est appelée calcul mémétique ou calcul mémétique (MC). Avec MC, les traits du darwinisme universel sont mieux capturés. Vu dans cette perspective, MA est une notion plus contrainte de MC. Plus spécifiquement, MA couvre un domaine de la MC, traitant en particulier des domaines des algorithmes évolutifs qui marient d'autres techniques de raffinement déterministes pour résoudre des problèmes d'optimisation. MC étend la notion de mème pour couvrir les entités conceptuelles de procédures ou de représentations enrichies par les connaissances.

Le développement des AMM

1ère génération

La première génération de MA fait référence à des algorithmes hybrides , un mariage entre une recherche globale basée sur la population (souvent sous la forme d'un algorithme évolutif) couplée à une étape d'évolution culturelle. Cette première génération d'AM, bien que comprenant des caractéristiques d'évolution culturelle (sous forme de raffinement local) dans le cycle de recherche, peut ne pas être qualifiée de véritable système évolutif selon le darwinisme universel , puisque tous les principes fondamentaux de l'héritage / transmission mémétique, de la variation , et la sélection est manquante. Cela suggère pourquoi le terme MA a suscité des critiques et des controverses parmi les chercheurs lorsqu'il a été introduit pour la première fois.

Pseudo code

   Procedure Memetic Algorithm
   Initialize: Generate an initial population;
   while Stopping conditions are not satisfied do
       Evaluate all individuals in the population.
       Evolve a new population using stochastic search operators.
       Select the subset of individuals,  $\Omega _{il}$ , that should undergo the individual improvement procedure.
       for each individual in  $\Omega _{il}$  do
           Perform individual learning using meme(s) with frequency or probability of  $f_{il}$ , for a period of  $t_{il}$ .
           Proceed with Lamarckian or Baldwinian learning.
       end for
   end while

2ème génération

Les MA multi-mèmes, hyper-heuristiques et méta-lamarckiennes sont appelées MA de deuxième génération présentant les principes de la transmission mémétique et de la sélection dans leur conception. Dans Multi-meme MA, le matériel mémétique est codé comme faisant partie du génotype . Par la suite, le mème décodé de chaque individu / chromosome respectif est ensuite utilisé pour effectuer un raffinement local. Le matériel mémétique est ensuite transmis par un simple mécanisme d'héritage du parent aux descendants. D'autre part, dans une MA hyper-heuristique et méta-lamarckienne, le pool de mèmes candidats considérés sera en compétition, en fonction de leurs mérites passés à générer des améliorations locales grâce à un mécanisme de récompense, en décidant du mème à sélectionner pour procéder pour de futurs locaux. raffinements. Les mèmes avec une récompense plus élevée ont plus de chances d'être répliqués ou copiés. Pour un examen de la MA de deuxième génération; c'est-à-dire, MA considérant plusieurs méthodes d'apprentissage individuelles au sein d'un système évolutif, le lecteur est référé.

3e génération

Les AM de co-évolution et d'auto-génération peuvent être considérés comme des AM de 3e génération où les trois principes satisfaisant les définitions d'un système évolutif de base ont été pris en compte. Contrairement à la MA de 2e génération qui suppose que les mèmes à utiliser sont connus a priori, la MA de 3e génération utilise une recherche locale basée sur des règles pour compléter les solutions candidates au sein du système évolutif, capturant ainsi des caractéristiques ou des modèles régulièrement répétés dans l'espace du problème.

Quelques notes de conception

La fréquence et l'intensité de l'apprentissage individuel définissent directement le degré d'évolution (exploration) par rapport à l'apprentissage individuel (exploitation) dans la recherche MA, pour un budget de calcul limité fixe donné. De toute évidence, un apprentissage individuel plus intense offre une plus grande chance de convergence vers les optima locaux mais limite la quantité d'évolution qui peut être dépensée sans encourir des ressources de calcul excessives. Par conséquent, des précautions doivent être prises lors de la définition de ces deux paramètres pour équilibrer le budget de calcul disponible pour obtenir des performances de recherche maximales. Lorsque seule une partie de la population subit un apprentissage, la question du sous-ensemble d'individus à améliorer doit être prise en compte pour maximiser l'utilité de la recherche MA. Enfin et surtout, la procédure/mème d'apprentissage individuel utilisé favorise également une structure de voisinage différente, d'où la nécessité de décider quel(s) mème(s) utiliser pour un problème d'optimisation donné serait nécessaire.

À quelle fréquence l'apprentissage individuel doit-il être appliqué?

L'une des premières questions pertinentes à la conception d'algorithmes mémétiques est de considérer à quelle fréquence l'apprentissage individuel doit être appliqué ; c'est-à-dire la fréquence d'apprentissage individuelle. Dans un cas, l'effet de la fréquence d'apprentissage individuel sur les performances de recherche MA a été pris en compte où diverses configurations de la fréquence d'apprentissage individuel à différentes étapes de la recherche MA ont été étudiées. A l'inverse, il a été montré ailleurs qu'il peut être intéressant d'appliquer un apprentissage individuel à chaque individu si la complexité de calcul de l'apprentissage individuel est relativement faible.

Sur quelles solutions l'apprentissage individuel doit-il être utilisé?

Sur la question de la sélection des individus appropriés parmi la population EA qui devraient subir un apprentissage individuel, des stratégies basées sur la condition physique et basées sur la distribution ont été étudiées pour adapter la probabilité d'appliquer l'apprentissage individuel sur la population de chromosomes dans des problèmes de recherche paramétrique continue avec Land étendant le travail. aux problèmes d' optimisation combinatoire . Bambha et coll. a introduit une technique de chauffage simulé pour intégrer systématiquement l'apprentissage individuel paramétré dans des algorithmes évolutifs afin d'obtenir une qualité de solution maximale.

Combien de temps l'apprentissage individuel doit-il durer?

L'intensité d'apprentissage individuel , est le montant du budget de calcul alloué à une itération d'apprentissage individuel; c'est-à-dire le budget de calcul maximal autorisé pour l'apprentissage individuel à consacrer à l'amélioration d'une solution unique. ${\ displaystyle t_ {il}}$

Quelle méthode d'apprentissage individuelle ou quel mème devrait-on utiliser pour un problème ou un individu particulier?

Dans le contexte de l'optimisation continue, l'apprentissage individuel existe sous la forme d'heuristiques locales ou de méthodes énumératives exactes conventionnelles. Des exemples de stratégies d'apprentissage individuelles comprennent l'escalade, la méthode Simplex, la méthode Newton / Quasi-Newton, les méthodes de points intérieurs, la méthode de gradient conjugué, la recherche de ligne et d'autres heuristiques locales. Notez que la plupart des méthodes d'apprentissage individuelles courantes sont déterministes.

En optimisation combinatoire, en revanche, des méthodes d'apprentissage individuelles existent couramment sous la forme d'heuristiques (qui peuvent être déterministes ou stochastiques) adaptées à un problème d'intérêt spécifique. Les procédures et schémas heuristiques typiques incluent l'échange de gènes k, l'échange de bords, la première amélioration et bien d'autres.

Applications

Les algorithmes mémétiques ont été appliqués avec succès à une multitude de problèmes du monde réel. Bien que de nombreuses personnes utilisent des techniques étroitement liées aux algorithmes mémétiques, des noms alternatifs tels que les algorithmes génétiques hybrides sont également utilisés. De plus, de nombreuses personnes appellent leurs techniques mémétiques des algorithmes génétiques .

Les chercheurs ont utilisé des algorithmes mémétiques pour s'attaquer à de nombreux problèmes classiques de NP . Pour citer quelques - uns d'entre eux: le partitionnement du graphe , havresac multidimensionnel , problème du voyageur de commerce , problème d'affectation quadratique , problème de couverture ensemble , coloration graphique minimale , problème max ensemble indépendant , problème d'emballage bin , et problème d'affectation généralisée .

Les applications plus récentes incluent (mais sans s'y limiter) l'analyse commerciale et la science des données , la formation de réseaux de neurones artificiels , la reconnaissance de formes , la planification de mouvements robotiques , l' orientation du faisceau , la conception de circuits , la restauration de services électriques, les systèmes experts médicaux , la planification d'une seule machine, la planification automatique des horaires (notamment, le calendrier de la LNH ), planification de la main - d'œuvre , optimisation de la liste des infirmières , allocation des processeurs , planification de la maintenance (par exemple, d'un réseau de distribution électrique), problème de sac à dos multidimensionnel, conception VLSI , regroupement de profils d'expression génique, sélection de caractéristiques / gènes , la détermination des paramètres pour l' injection de panne matérielle, et multi-classe, multi-objectifs sélection de fonction .

Activités récentes dans les algorithmes mémétiques

Atelier IEEE sur les algorithmes mémétiques (WOMA 2009). Présidents de programme: Jim Smith, Université de l'ouest de l'Angleterre, Royaume-Uni; Yew-Soon Ong, Université technologique de Nanyang, Singapour; Gustafson Steven, Université de Nottingham ; ROYAUME-UNI; Meng Hiot Lim, Université technologique de Nanyang, Singapour; Natalio Krasnogor, Université de Nottingham, Royaume-Uni
Memetic Computing Journal , premier numéro paru en janvier 2009.
2008 IEEE World Congress on Computational Intelligence (WCCI 2008) , Hong Kong, Session spéciale sur les algorithmes mémétiques .
Numéro spécial sur « Emerging Trends in Soft Computing - Memetic Algorithm » , Soft Computing Journal, terminé et sous presse, 2008.
Groupe de travail sur les technologies émergentes de l'IEEE Computational Intelligence Society sur le calcul mémétique
Congrès IEEE sur le calcul évolutif (CEC 2007) , Singapour, Session spéciale sur les algorithmes mémétiques .
«Calcul mémétique» par les indicateurs scientifiques essentiels de Thomson Scientific en tant que domaine de recherche du front émergent.
Numéro spécial sur les algorithmes mémétiques , les transactions IEEE sur les systèmes, l'homme et la cybernétique - Partie B: Cybernétique, Vol. 37, n ° 1, février 2007.
Progrès récents des algorithmes mémétiques , série: études sur le flou et l'informatique douce, vol. 166, ISBN 978-3-540-22904-9 , 2005.
Numéro spécial sur les algorithmes mémétiques , Calcul évolutif, automne 2004, vol. 12, n° 3 : v-vi.

Languages

In other projects