Algorithme d’optimisation de l’alimentation bactérienne

Algorithme d’optimisation de l’alimentation bactérienne

L’algorithme d’optimisation de l’alimentation bactérienne est inspiré par le comportement de recherche de nourriture de groupe de bactéries telles que E. coli et M. xanthus. Plus précisément, l’algorithme d’optimisation de l’alimentation bactérienne est inspiré par le comportement chimiotactique des bactéries qui percevront les gradients chimiques dans l’environnement (tels que les nutriments) et se déplaceront vers ou loin de signaux spécifiques.

Les bactéries perçoivent la direction de la nourriture en fonction des gradients de produits chimiques dans leur environnement. Les bactéries sécrètent des produits chimiques attirants et répulsifs dans l’environnement et peuvent percevoir de la même manière. En utilisant des mécanismes de locomotion (tels que les flagelles), les bactéries peuvent se déplacer dans leur environnement, se déplaçant parfois de manière chaotique (culbutage et rotation), et d’autres fois se déplaçant de manière dirigée, ce qui peut être appelé la natation. 

Les cellules bactériennes sont traitées comme des agents dans un environnement, utilisant leur perception de la nourriture et d’autres cellules comme motivation pour se déplacer, et le culbutage stochastique et la natation comme un mouvement pour se réinstaller. Selon les interactions cellule-cellule, les cellules peuvent envahir une source de nourriture et / ou peuvent se repousser ou s’ignorer de manière agressive.

La stratégie de traitement de l’information de l’algorithme d’optimisation de l’alimentation bactérienne est de permettre aux cellules de pulluler stochastiquement et collectivement vers les optima. Ceci est réalisé grâce à une série de trois processus sur une population de cellules simulées: 1) Chémotaxie : le coût des cellules est réduit par la proximité d’autres cellules et les cellules se déplacent une par une le long de la surface de coût, 2) Reproduction : seules les cellules qui ont bien fonctionné au cours de leur vie peuvent contribuer à la prochaine génération, et 3) Élimination-dispersion : les cellules sont jetées et de nouveaux échantillons aléatoires sont insérés avec une faible probabilité.

Le pseudocode suivant décrit l’algorithme pour minimiser une fonction de coût.

Le prochain algorithme fournit le pseudocode pour le chimiotactisme et le comportement des bactéries pour l’algorithme d’optimisation de l’alimentation bactérienne.

Le coût d’une bactérie est réduit par son interaction avec d’autres cellules. Cette fonction d’interaction (g ()) est calculée comme suit:

où cell_k est une cellule donnée, d_attr et w_attr sont des coefficients d’attraction, h_repel et w_repel sont des coefficients de répulsion, S est le nombre de cellules dans la population, P est le nombre de dimensions sur un vecteur de position de cellules donné.

Les paramètres restants de l’algorithme sont les suivants Cell_s_num est le nombre de cellules maintenues dans la population, N_ed est le nombre d’étapes d’élimination-dispersion, N_re est le nombre d’étapes de reproduction, N_c est le nombre d’étapes de chimiotaxie, N_s est le nombre des étapes de natation pour une cellule donnée, Stepsize est un vecteur de direction aléatoire avec le même nombre de dimensions que l’espace du problème avec chaque valeur dans [-1; 1], et P_ed est la probabilité qu’une cellule soit soumise à l’élimination et à la dispersion.

Étant donné les boucles de l’algorithme, il peut être configuré de nombreuses façons pour obtenir différents comportements de recherche. Il est courant d’avoir un grand nombre d’itérations de chimiotaxie et un petit nombre des autres itérations. Les coefficients par défaut pour le comportement d’essaimage (interactions cellule-cellule) sont les suivants d_attract = 0,1, w_attract = 0,2, h_repellant = d_attract et w_repellant = 10. La taille du pas est généralement une petite fraction de l’espace de recherche, telle comme 0,1.

Au cours de la reproduction, la moitié de la population ayant une métrique de santé faible est généralement éliminée et deux copies de chaque membre de la première moitié (santé élevée) de la population sont conservées. La probabilité d’élimination et de dispersion (p_ed) est généralement définie comme étant assez élevée, telle que 0,25.