💻 computer science

GeoSSA: Geometric Sparrow Search Algorithm for UAV Path Planning and Engineering Design Optimization

Cet article propose l'algorithme de recherche du moineau géométrique (GeoSSA), qui améliore l'algorithme SSA original grâce à une initialisation géométrique et des stratégies de mise à jour améliorées afin d'atteindre une performance d'optimisation globale, une stabilité et une robustesse supérieures lors de tests de référence, de planification de trajectoires d'UAV et de problèmes de conception d'ingénierie.

Auteurs originaux : Junhao Wei, Wenxuan Zhu, Qingyang Xu, Yanxiao Li, Yifu Zhao, Zikun Li, Ran Zhang, Yanzhao Gu, Jinhong Song, Yapeng Wang, Zhiwen Wang, Ngai Cheong, Sio-Kei Im, Xu Yang

Publié 2026-01-28

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Junhao Wei, Wenxuan Zhu, Qingyang Xu, Yanxiao Li, Yifu Zhao, Zikun Li, Ran Zhang, Yanzhao Gu, Jinhong Song, Yapeng Wang, Zhiwen Wang, Ngai Cheong, Sio-Kei Im, Xu Yang

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous essayiez de trouver le meilleur itinéraire absolu pour un drone de livraison traversant une ville encombrée, ou que vous essayiez de concevoir une pièce de machine qui soit solide tout en utilisant le moins de matériau possible. Ce sont des « problèmes d'optimisation ». Vous avez des millions de réponses possibles, mais il n'en existe qu'une seule qui est la solution « Goldilocks » parfaite — ni trop longue, ni trop courte, juste ce qu'il faut.

Pendant des décennies, les scientifiques ont utilisé des « algorithmes métaheuristiques » pour résoudre ces énigmes. Considérez ces algorithmes comme une équipe d'explorateurs envoyés dans une forêt sombre et brumeuse pour trouver le sommet le plus élevé (la meilleure solution).

L'équipe originale : Les Moineaux

Une équipe d'explorateurs populaire s'appelle l'Algorithme de Recherche de Moineaux (SSA - Sparrow Search Algorithm). Elle imite une nuée de moineaux cherchant de la nourriture.

Producteurs : Quelques oiseaux courageux qui ouvrent la voie, cherchant de la nourriture sur de vastes zones.
Voleurs (Scroungers) : Le reste de la nuée qui suit les leaders, espérant trouver de la nourriture près d'eux.
Moineaux de bordure : Les oiseaux à l'extérieur de la nuée qui surveillent les prédateurs (dangers) et se mettent à l'abri.

Le Problème : L'équipe originale présente une faille. Parfois, les oiseaux s'installent trop confortablement dans un endroit, pensant avoir trouvé la meilleure nourriture, pour réaliser plus tard qu'ils étaient coincés dans une petite vallée alors qu'un immense sommet de montagne se trouvait juste à côté d'eux. Ils se retrouvent « bloqués » trop tôt (convergence prématurée) et ratent la véritable meilleure réponse.

La nouvelle équipe : GeoSSA (Les Moineaux Géométriques)

Les auteurs de cet article, une équipe de l'Université Polytechnique de Macao et d'autres institutions, ont décidé d'améliorer la nuée. Ils ont créé le GeoSSA (Geometric Sparrow Search Algorithm). Ils n'ont pas seulement ajusté les règles ; ils ont donné aux oiseaux trois superpouvoirs pour en faire des explorateurs plus intelligents.

1. Un départ avec une « Carte Parfaite » (Initialisation de l'ensemble de bons nœuds)

L'ancienne méthode : Lorsque la nuée originale commençait, elle était placée de manière aléatoire, comme si l'on lançait des fléchettes les yeux bandés sur une carte. Cela signifiait souvent que trop d'oiseaux atterrissaient au même endroit (regroupement) tandis que de vastes zones de la carte restaient vides.
L'amélioration GeoSSA : Au lieu d'un lancer aléatoire, ils ont utilisé un « Ensemble de Bons Nœuds ». Imaginez disposer des carreaux de grille si parfaitement que chaque pouce de la carte est couvert uniformément, sans lacunes ni regroupements.

Pourquoi cela aide : Les oiseaux commencent avec une vue parfaite de toute la forêt, garantissant qu'ils ne manquent aucune « source de nourriture » potentielle dès le début.

2. Le bond « Sinus-Cosinus » (Mise à jour améliorée des Producteurs)

L'ancienne méthode : Les oiseaux leaders (Producteurs) se déplaçaient en faisant des pas simples et prévisibles. S'ils étaient proches d'un bon endroit, ils faisaient simplement de petits pas en avant. S'ils étaient loin, ils pouvaient sauter, mais le saut n'était pas très intelligent.
L'amélioration GeoSSA : Les leaders utilisent désormais un mélange de fonctions Sinus et Cosinus (ondes mathématiques) pour décider de leur mouvement.

L'analogie : Imaginez que l'oiseau leader ne se contente pas de marcher en ligne droite. Au lieu de cela, il danse selon un motif ondulatoire. Parfois, l'onde lui dicte de faire un bond géant et balayeur vers une partie totalement nouvelle de la forêt (exploration). D'autres fois, l'onde lui dicte de faire de tout petits pas prudents pour polir un bon emplacement (exploitation).
Pourquoi cela aide : Cela empêche les oiseaux de rester coincés dans une vallée locale. Ils peuvent faire des bonds stratégiques et de grande envergure pour trouver le véritable sommet le plus élevé.

3. Le filet de sécurité du « Parcours Triangulaire » (Mise à jour améliorée de la Bordure)

L'ancienne méthode : Les oiseaux en bordure de la nuée (les plus vulnérables) se déplaçaient selon des lignes droites simples pour échapper au danger. C'était trop rigide.
L'amélioration GeoSSA : Ces oiseaux utilisent désormais un « Parcours Triangulaire ».

L'analogie : Au lieu de courir en ligne droite pour fuir un prédateur, imaginez un oiseau courant en forme de triangle. Il avance, puis angle brusquement à gauche, puis angle à droite. Cela crée un chemin en zigzag qui est beaucoup plus difficile à prédire et permet à l'oiseau d'explorer plus minutieusement la zone immédiate avant de se poser.
Pourquoi cela aide : Cela ajoute une couche de hasard et de flexibilité, aidant la nuée à échapper aux pièges complexes (optima locaux) qui auraient capturé les oiseaux originaux.

Mise à l'épreuve

Les chercheurs ont soumis cette nouvelle « Super Nuée » à trois essais majeurs :

La salle de sport mathématique (Fonctions de référence) : Ils ont testé l'algorithme sur 23 énigmes mathématiques complexes différentes.
- Résultat : GeoSSA a gagné presque à chaque fois. Il a trouvé les meilleures réponses plus rapidement et de manière plus constante que les moineaux originaux et d'autres équipes d'explorateurs célèbres (comme les Optimiseurs de Loups ou les algorithmes de Colonies de Fourmis). Il avait un « Taux de Victoire » de 95,65 %.
La course de drones (Planification de trajectoire d'UAV) : Ils ont demandé aux algorithmes de planifier une trajectoire de vol en 3D pour un drone afin qu'il vole du Point A au Point B tout en évitant des obstacles.
- Résultat : GeoSSA a tracé le chemin le plus fluide, le plus court et le plus sûr. D'autres algorithmes ont parfois percuté des murs ou emprunté des routes très longues et sinueuses. Le chemin de GeoSSA était stable et fiable.
L'atelier d'ingénierie : Ils ont utilisé l'algorithme pour résoudre quatre problèmes de conception d'ingénierie du monde réel :
- Conception d'une Cloison Ondulée (une paroi solide pour des réservoirs chimiques).
- Conception d'un Levier de Piston (une pièce pour des pompes).
- Conception d'un Réseau de Réacteurs (pour des usines chimiques).
- Conception d'un Système de Réfrigération Industrielle.
- Résultat : Dans les quatre cas, GeoSSA a trouvé les conceptions les plus efficaces (utilisant moins de matériaux ou d'énergie) et l'a fait avec le plus de constance. Il n'a pas seulement eu de la chance une fois ; il a obtenu le meilleur résultat à chaque fois qu'il a lancé le test.

L'essentiel

L'article affirme qu'en dotant l'Algorithme de Recherche de Moineaux d'une meilleure carte de départ, de règles de mouvement plus intelligentes pour ses leaders et d'une stratégie d'échappement plus flexible pour ses membres de bordure, ils ont créé un outil nettement supérieur pour résoudre des énigmes complexes.

Qu'il s'agisse de guider un drone à travers une ville ou de concevoir une pièce de machine, GeoSSA est présenté comme un moyen plus fiable, plus rapide et plus intelligent de trouver la « solution parfaite » parmi des millions de possibilités. Il ne se contente pas de deviner ; il explore tout le système de la forêt de manière méthodique et sait exactement quand faire un bond géant et quand faire un pas prudent.

Résumé Technique : Algorithme de Recherche de Moineaux Géométrique (GeoSSA) pour la Planification de Trajectoires d'UAV et l'Optimisation de la Conception d'Ingénierie

Énoncé du Problème
L'algorithme de recherche de moineaux (SSA), une métaheuristique basée sur la population inspirée des comportements de recherche de nourriture et d'anti-prédation des moineaux, est reconnu pour sa structure simple et sa facilité de mise en œuvre. Cependant, le SSA original souffre d'un équilibre insuffisant entre l'exploration (recherche globale) et l'exploitation (recherche locale). Ce déséquilibre conduit souvent à une convergence prématurée, à une progression d'optimisation lente et à une tendance à rester piégé dans des optima locaux, particulièrement lorsqu'il traite des problèmes d'optimisation multidimensionnels, complexes et multimodaux. Ces limitations entravent son efficacité dans des applications réelles critiques telles que la planification de trajectoires 3D d'Unmanned Aerial Vehicles (UAV) et l'optimisation de la conception d'ingénierie complexe, où des capacités de recherche globale robustes et une grande stabilité de solution sont requises.

Méthodologie
Pour remédier à ces déficiences, les auteurs proposent l'Algorithme de Recherche de Moineaux Géométrique (GeoSSA). Cet algorithme amélioré intègre trois stratégies spécifiques pour améliorer les performances du SSA original :

Initialisation par l'Ensemble de Bons Nœuds : Remplaçant l'initialisation traditionnelle par nombres pseudo-aléatoires, le GeoSSA utilise la méthode de l'« Ensemble de Bons Nœuds » (basée sur la théorie des nombres de Hua Luogeng). Cette approche génère une population avec une distribution spatiale plus uniforme à travers l'espace de recherche, empêchant efficacement le regroupement de la population et assurant une couverture plus large lors de la phase d'exploration initiale. Cette méthode est notée pour maintenir l'uniformité même dans des espaces de haute dimension.
Mise à jour de la Position des Producteurs par Amélioration Sinus-Cosinus : Le mécanisme de mise à jour des « producteurs » (les individus ayant le meilleur fitness) est modifié pour incorporer des fonctions sinus et cosinus. Une logique de décision basée sur la valeur d'alarme ( $R_2$ ) détermine si les fonctions sinus ou cosinus doivent être utilisées pour contrôler la mise à jour de la position. De plus, un poids d'inertie adaptatif basé sur une fonction sigmoïde est introduit. Cette stratégie améliore la diversité de la recherche globale, permettant aux producteurs de faire des sauts plus larges dans l'espace de solution pour échapper aux optima locaux tout en maintenant un équilibre entre exploration et exploitation.
Mise à jour de la Position des Moineaux de Bordure par Marche Triangulaire Améliorée : Pour les « moineaux de bordure » (individus ayant un moins bon fitness), l'algorithme introduit un mécanisme de Marche Triangulaire. Cela implique un facteur d'ajustement dynamique et un mécanisme de perturbation aléatoire basé sur des fonctions trigonométriques. Cette stratégie augmente le caractère aléatoire du processus de mise à jour de la position, brisant la limitation des perturbations de direction unique et améliorant la capacité de l'algorithme à échapper aux optima locaux tout en améliant la précision de la recherche locale lors des phases ultérieures.

Principales Contributions

Innovation Algorithmique : Le développement du GeoSSA, qui combine de manière synergique l'initialisation géométrique, la dynamique sinus-cosinus et les perturbations de marche triangulaire pour traiter les faiblesses spécifiques du SSA original.
Validation Complète : L'article procède à une évaluation rigoureuse du GeoSSA via :
- Études d'Ablation : Démontrant la contribution individuelle de chaque stratégie proposée.
- Analyse Qualitative : Analysant l'historique de recherche, les ratios exploration-exploitation et la diversité de la population sur 23 fonctions de référence standards.
- Expériences Comparatives : Évaluant le GeoSSA par rapport à des algorithmes de pointe (AROA, WOA, IWOA, MWOA, IPSO, ISSA) et au SSA original.
Application Pratique : L'application réussie du GeoSSA à deux domaines réels distincts :
- Planification de Trajectoire 3D d'UAV : Optimisation des trajectoires de vol pour minimiser la longueur et la variance de l'altitude tout en évitant les obstacles et en respectant les contraintes dynamiques.
- Optimisation de la Conception d'Ingénierie : Résolution de quatre problèmes contraints complexes : conception de cloison étanche ondulée (Corrugated Bulkhead), conception de levier de piston (Piston Lever), conception de réseau de réacteur (Reactor Network) et conception de système de réfrigération industrielle (Industrial Refrigeration System).

Résultats
Les résultats expérimentaux indiquent que le GeoSSA atteint des performances supérieures par rapport aux algorithmes comparés :

Fonctions de Référence : Sur 23 fonctions de référence, le GeoSSA a obtenu le meilleur ou le quasi-meilleur fitness moyen et écart-type. Il a obtenu le premier rang dans les tests de Friedman avec un rang moyen de 1,9514 et une efficacité globale (OE) de 95,65 %. Les tests de rang signé de Wilcoxon ont confirmé des améliorations statistiquement significatives par rapport à la plupart des concurrents.
Planification de Trajectoire d'UAV : Dans les tâches de planification de trajectoire 3D, le GeoSSA a démontré la plus grande stabilité (écart-type le plus bas de 0,95654) et a produit les trajectoires les plus courtes et les plus fluides avec un évitement d'obstacles efficace, surpassant des algorithmes comme l'IWOA, qui souffrait d'une instabilité extrême.
Conception d'Ingénierie : Dans les quatre problèmes de conception d'ingénierie, le GeoSSA a systématiquement atteint la plus haute précision de solution (fitness moyen le plus bas) et la plus forte stabilité (écart-type le plus bas), atteignant souvent des valeurs optimales théoriques ou quasi-optimales là où d'autres algorithmes peinaient à converger ou à satisfaire les contraintes.

Signification et Revendications
L'article affirme que le GeoSSA fournit un cadre de solution efficace et fiable pour les problèmes d'optimisation complexes. En équilibrant efficacement l'exploration globale et l'exploitation locale, le GeoSSA surmonte les problèmes de convergence prématurée et de stagnation inhérents au SSA original. Les auteurs affirment que l'algorithme présente une forte robustesse et une capacité de généralisation, ce qui le rend adapté non seulement aux tests de référence standards, mais aussi aux applications d'ingénierie pratique caractérisées par une haute dimensionnalité, une non-linéarité et des contraintes complexes. L'étude conclut que le GeoSSA représente une avancée significative dans l'optimisation métaheuristique, offrant un outil polyvalent pour s'attaquer à des tâches exigeantes dans la navigation d'UAV et la conception d'ingénierie.