Calcul évolutif pour une optimisation coûteuse : une enquête

Le terme «problème d’optimisation coûteux» (EOP) fait référence à tout problème nécessitant des coûts coûteux, voire inabordables, pour évaluer des solutions candidates. Ces problèmes existent dans de nombreuses applications significatives du monde réel.

D’une part, le « coût élevé » peut faire référence à une évaluation elle-même qui nécessite beaucoup de temps, d’argent, etc. D’autre part, le « coût élevé » est un concept relatif plutôt qu’un concept absolu dans de nombreux problèmes du monde réel.

Par exemple, lors de situations d’urgence comme des épidémies ou des catastrophes naturelles, le transport et la répartition peuvent être urgents pour soutenir les opérations quotidiennes et sauver des vies, où le coût en temps de l’optimisation deviendra trop cher à accepter pour le moment.

Résoudre plus efficacement les EOP est devenu de plus en plus essentiel dans de nombreux domaines. Cependant, en raison du coût élevé de l’évaluation des solutions candidates, l’EOP est difficile à aider pour les algorithmes d’optimisation.

Le calcul évolutionnaire (EC) a été largement adopté pour résoudre les EOP, conduisant à un domaine de recherche en pleine croissance. En général, l’EC est un type de méthodologie d’optimisation qui s’inspire de l’évolution biologique et des caractéristiques des organismes vivants. Les algorithmes EC couramment utilisés incluent les algorithmes évolutionnaires (EA) tels que les algorithmes génétiques (GA) et l’évolution différentielle (DE), ainsi que les algorithmes d’intelligence en essaim tels que l’optimisation des essaims de particules (PSO) et l’optimisation des colonies de fourmis (ACO).

En utilisant l’idée de «survie du plus apte» à partir de l’évolution naturelle, les algorithmes EC génèrent de nouveaux individus via des opérateurs évolutifs correspondants et sélectionnent les individus avec une meilleure forme physique en tant que nouvelle population pour la prochaine génération. Sur la base de cette méthode, les algorithmes EC peuvent trouver efficacement une solution satisfaisante sans avoir besoin d’informations sur le gradient, ce qui est très approprié pour résoudre des problèmes du monde réel.

À ce jour, diverses recherches sur l’EC pour l’EOP ont été menées et ont obtenu un succès considérable. Cependant, le travail d’EC pour l’EOP est encore dispersé dans la littérature et reste à consolider de manière systématique. Par conséquent, étant donné les progrès rapides et importants de la CE pour l’EOP, il est essentiel d’examiner ces progrès afin de synthétiser et de comprendre les résultats des recherches précédentes.

À cette fin, cet article tente de fournir une enquête systématique et complète pour examiner et analyser complètement comment activer et développer des algorithmes EC pour s’attaquer efficacement aux EOP difficiles. De plus, pour présenter l’examen de manière plus concise et claire, cet article sélectionne et cite des travaux connexes en tenant compte de leurs sources, des années de publication, de l’impact et de la couverture des différents aspects du sujet étudié dans cet article.

Dans l’ensemble, les principales contributions de cet article sont présentées comme suit :

Tout d’abord, cet article analyse mathématiquement le coût total élevé de l’utilisation de l’EC pour résoudre les EOP. Ensuite, sur la base de l’analyse, cet article donne en outre trois directions pour réduire le coût total : approximation et substitution du problème, conception et amélioration de l’algorithme, et calcul parallèle et distribué. Cet article est le premier à dériver les directions de recherche potentielles en analysant le coût total élevé de l’utilisation de l’EC pour résoudre les EOP.

Deuxièmement, une taxonomie systématique est introduite pour examiner systématiquement et structurellement les travaux existants en fonction de leurs efforts dans les directions susmentionnées pour résoudre efficacement les EOP. La taxonomie contient quatre parties. La première partie, approximation du problème et substitution, comprend la simplification du problème, l’approximation de la condition physique, l’approximation des contraintes et la substitution multi-fidélité.

La deuxième partie, la conception et l’amélioration des algorithmes, présente le cadre et le paradigme d’optimisation, les nouveaux opérateurs, l’héritage de fitness et les algorithmes et configurations hybrides.

La troisième partie, calcul parallèle et distribué, considère les accélérations pour l’approximation et les optimisations.

La quatrième partie, les applications du monde réel, concerne le monde réel.

Dans chaque partie, les travaux connexes existants sont ensuite classés et présentés. Par conséquent, une telle taxonomie systématique peut offrir une meilleure compréhension de pourquoi et comment les algorithmes EC ont été utilisés pour résoudre efficacement les EOP et fournir des références pour aider les chercheurs de divers domaines à résoudre les EOP plus efficacement.

Troisièmement, cet article explore et discute de certains domaines de recherche futurs et des problèmes ouverts liés à l’utilisation de la CE pour s’attaquer aux EOP. Cinq orientations futures potentielles à partir de trois niveaux (c’est-à-dire, niveau théorie-méthode-application) sont examinées et discutées dans cet article : une analyse théorique plus approfondie, une plus grande diversité de recherche, une configuration et un contrôle plus adaptatifs, un meilleur apprentissage et utilisation des connaissances, des tests supplémentaires sur différents problèmes. .

Fourni par Beijing Zhongke Journal Publishing Co.