Le scientifique RUDN a comparé les algorithmes pour résoudre le problème de la gestion optimale

Dans les systèmes où il y a plusieurs objets qui doivent définir une séquence d’actions, la tâche dite de gestion optimale se produit. Par exemple, dans la tâche de gérer un vaisseau spatial ou le système fiscal d’un pays. Mathématiquement, cela signifie qu’il est nécessaire de minimiser ou de maximiser un paramètre du système (par exemple, minimiser le temps ou maximiser l’emploi de la population). Il n’existe pas de moyen universel généralement accepté d’analyser numériquement de tels systèmes, mais il existe de nombreuses approches et algorithmes. Les chercheurs RUDN et FITZ " Informatique et gestion" de l’Académie des sciences de Russie ont proposé deux approches basées sur plusieurs algorithmes informatiques modernes pour résoudre le problème de la gestion optimale d’un groupe de robots.

«Un groupe de robots doit passer d’un état initial donné à un état final, en évitant les obstacles, en un minimum de temps. Le problème appartient à la classe d’optimisation de dimension infinie. Il existe deux classes de méthodes pour le résoudre numériquement. Les méthodes directes sont basées sur la réduction à un problème d’optimisation de dimension finie. Les méthodes indirectes sont basées sur l’application du principe du maximum de pontriagin pour la transition vers le problème de bord et sa solution numérique ultérieure», — Sergey Konstantinov, maître de conférences au département de mécanique et de processus de gestion de la mine.

Les scientifiques ont proposé deux approches pour résoudre le problème de la gestion optimale basée sur des méthodes directes. Dans la tâche de test, les robots doivent se déplacer d’un point de départ à l’autre et ne pas rencontrer d’obstacles et d’autres robots. Dans la première approche, un groupe de robots a été considéré comme un seul objet. La tâche de contrôle optimal dans ce cas est réduite à la tâche de programmation non linéaire. Cela signifie qu’il ne peut pas être réduit à un système d’équations linéaires, ce qui complique la tâche. Dans la deuxième approche, pour chaque robot, on a d’abord recherché des attracteurs — des points spéciaux sur le plan du mouvement du robot, dont la tâche est de «suggérer» au robot comment contourner les obstacles sur le chemin. Ensuite, les résultats obtenus ont été utilisés pour résoudre l’ensemble du problème initial. Les calculs des deux approches ont été réalisés à l’aide d’algorithmes évolutifs et d’une méthode de recherche aléatoire. Les scientifiques ont effectué 10 tests pour chacun des quatre algorithmes évolutifs et de la méthode de recherche aléatoire et ont comparé leurs performances.

L’efficacité de deux approches et de cinq algorithmes (la méthode de recherche aléatoire et quatre algorithmes évolutifs: l’algorithme Génétique, la méthode de l’essaim de particules, l’algorithme des abeilles et l’algorithme du loup gris) a été évaluée sur la base de la valeur de la fonction cible — une fonction à minimiser dans le problème de contrôle optimal. Plus il est petit, mieux l’algorithme a réussi. Pour la première approche, tous les algorithmes évolutifs se sont révélés plus efficaces que la méthode de recherche aléatoire. La «méthode de l’essaim de particules» était la meilleure, la valeur de la fonction cible était en moyenne de 5,5. Pour la méthode de recherche aléatoire, cette valeur était presque trois fois supérieure à 15,83. Pour la deuxième approche, la méthode de recherche aléatoire s’est également avérée la moins efficace. Les algorithmes évolutifs ont fonctionné à peu près aussi efficacement. Dans l’un des tests, l’algorithme du loup gris a donné la valeur minimale de la fonction cible — 2,49.

«Il n’existe pas de méthodes numériques universelles pour résoudre les problèmes de gestion optimale. Nous prévoyons d’étudier plus en détail l’application des algorithmes évolutifs et d’envisager d’autres nouveaux algorithmes évolutifs, y compris les algorithmes hybrides», — Sergey Konstantinov, maître de conférences au département de mécanique et de gestion des processus de la mine.

Les résultats sont publiés dans la revue Applied Sciences.