Résolution de problèmes combinatoires avec les grands modèles de langage
Mahmoud Masoud, Ahmed Abdelhay, Mohammed Elhenawy·
Cette recherche explore l’utilisation de GPT-3.5 Turbo pour résoudre le problème du voyageur de commerce (TSP) à l’aide d’approches zero-shot, few-shot et de raisonnement en chaîne de pensée (chain-of-thought). Le fine-tuning améliore les performances sur des instances de taille similaire et permet une certaine généralisation. L’auto-ensemble renforce la précision sans nécessiter d’entraînement supplémentaire. L’étude évalue différentes techniques de prompting, mettant en évidence le potentiel des grands modèles de langage dans l’optimisation combinatoire ainsi que leur accessibilité pour des utilisateurs non experts. Les principaux défis concernent la mise à l’échelle, les hallucinations et les limitations liées aux tokens, tandis que les travaux futurs suggèrent des améliorations en matière de performances, d’ingénierie des prompts et d’intégration avec d’autres méthodes.
L’article vise à relever les défis liés à la résolution du problème du voyageur de commerce (Travelling Salesman Problem, TSP) à mesure que la taille du problème augmente, comme en témoigne une tendance à la hausse constante de l’écart médian observé avec différentes techniques. Le TSP en lui-même n’est pas un problème nouveau ; toutefois, l’étude se concentre sur l’exploration de nouvelles approches basées sur les grands modèles de langage afin d’en améliorer la résolution à grande échelle.
L’article cherche à valider l’efficacité d’une approche appelée algorithmes évolutionnaires pilotés par des grands modèles de langage (LLM-driven Evolutionary Algorithms, LMEA) pour résoudre le problème du voyageur de commerce (TSP).
L’article propose d’utiliser les grands modèles de langage (Large Language Models, LLMs) comme optimiseurs combinatoires évolutionnaires, en introduisant le concept d’algorithmes évolutionnaires pilotés par LLM (LMEA) pour résoudre le problème du voyageur de commerce (TSP).
En complément, l’étude suggère d’exploiter les LLMs en tant qu’optimiseurs via une approche appelée PROmpting (OPRO).
Les algorithmes LMEA proposés montrent des performances compétitives par rapport aux heuristiques traditionnelles pour la recherche de solutions de haute qualité sur des instances du TSP allant jusqu’à 20 nœuds. LMEA repose sur la sélection de solutions parentes à partir d’une population existante, l’application d’opérations de croisement et de mutation pour générer de nouvelles solutions, puis l’évaluation de ces solutions pour constituer la génération suivante.
Par ailleurs, l’article indique que la combinaison de techniques d’apprentissage en contexte (in-context learning) avec le fine-tuning des LLMs permet d’améliorer la précision des réponses, soulignant ainsi le potentiel de cette approche pour la résolution de problèmes combinatoires.
Oui, plusieurs travaux de recherche connexes existent. Des études ont notamment examiné l’application des grands modèles de langage (Large Language Models, LLMs) à la résolution de problèmes combinatoires tels que le problème du voyageur de commerce (Travelling Salesman Problem, TSP), y compris avec GPT-3.5 Turbo. D’autres recherches ont analysé les améliorations de performance obtenues grâce à des méthodes d’auto-ensemble, consistant à ajuster la température du modèle et à le solliciter plusieurs fois sur une même instance. Par ailleurs, certaines études se sont penchées sur l’impact des modèles en ensemble entraînés sur des instances de taille fixe, comparés à des modèles fine-tunés sur des instances de taille variable pour des tâches complexes. Parmi les chercheurs notables dans ce domaine figurent Chengrun Yang, Xuezhi Wang, Yifeng Lu, Hanxiao Liu, Quoc V. Le, Denny Zhou et Xinyun Chen. La clé de la solution proposée dans l’article repose sur l’exploitation des grands modèles de langage pour résoudre des problèmes combinatoires comme le TSP, en utilisant des approches telles que l’apprentissage en contexte zero-shot, few-shot et le raisonnement en chaîne de pensée (chain-of-thought, CoT). Ces méthodes visent à optimiser les réponses des LLMs en fournissant des prompts contextuels capables de guider le modèle vers des résultats plus précis pour des tâches complexes.
Les expériences ont été conçues pour évaluer les difficultés liées à la résolution du problème du voyageur de commerce (TSP) à mesure que la taille du problème augmente. Elles intègrent des techniques telles que le raisonnement en chaîne de pensée (CoT), l’apprentissage few-shot et l’apprentissage few-shot combiné au CoT, mettant en évidence une tendance à la hausse constante de l’écart médian lorsque la taille des instances croît. L’étude a également procédé au fine-tuning du modèle GPT-3.5 sur des instances du TSP de taille 10, puis évalué ses performances sur 30 instances de tailles variables, avec 11 réponses issues de l’auto-ensemble pour chaque instance. Enfin, certaines instances résolues ont été visualisées afin de faciliter l’interprétation et l’analyse des résultats.
Le jeu de données utilisé pour l’évaluation quantitative correspond à l’ensemble des réponses associées à un trajet donné dans le jeu de test, désigné sous le nom Response_Arr. Le caractère open source du code utilisé dans cette recherche n’est pas explicitement mentionné dans les informations disponibles. En l’absence de précisions supplémentaires, il n’est pas possible de confirmer si le code a été rendu public.
Les expériences et les résultats présentés dans l’article apportent un soutien solide aux hypothèses scientifiques examinées. L’étude analyse le potentiel des grands modèles de langage (Large Language Models, LLMs) pour résoudre le problème du voyageur de commerce (Travelling Salesman Problem, TSP) à l’aide de GPT-3.5 Turbo, en mobilisant différentes approches telles que l’apprentissage en contexte zero-shot, few-shot et le raisonnement en chaîne de pensée (chain-of-thought, CoT). Les résultats expérimentaux mettent en évidence une augmentation progressive de la difficulté de résolution du TSP à mesure que la taille du problème croît, ce qui témoigne d’une exploration approfondie des hypothèses formulées. Dans l’ensemble, la conception expérimentale et les résultats obtenus fournissent des éléments cohérents et pertinents pour étayer les hypothèses scientifiques évaluées dans l’article.
L’article explore le potentiel des grands modèles de langage (Large Language Models, LLMs) pour la résolution de problèmes combinatoires, en se concentrant plus particulièrement sur le problème du voyageur de commerce (Travelling Salesman Problem, TSP) à l’aide de GPT-3.5 Turbo. Il analyse différentes approches, notamment l’apprentissage en contexte zero-shot, few-shot et le raisonnement en chaîne de pensée (chain-of-thought, CoT), afin d’optimiser les réponses générées à partir de prompts contextuels. L’étude examine également l’efficacité de la combinaison de techniques d’apprentissage en ensemble avec l’apprentissage en contexte pour améliorer la précision des réponses.
Les recherches futures devraient se concentrer sur l’amélioration des performances du modèle pour des instances de plus grande taille, notamment par l’optimisation de l’ingénierie des prompts afin de mieux gérer les contraintes liées au nombre de tokens, ainsi que par l’exploration d’autres LLMs open source susceptibles d’offrir une meilleure efficacité. Par ailleurs, l’intégration d’algorithmes évolutionnaires comme outil d’optimisation externe, ou l’utilisation du LLM lui-même pour faire évoluer des solutions à partir des sorties d’auto-ensemble, constitue une piste prometteuse. Enfin, rendre le modèle plus accessible aux utilisateurs non experts, en particulier dans des contextes de petites entreprises, pourrait contribuer à démocratiser l’accès à des outils computationnels avancés et à en améliorer l’utilisabilité.
Le résumé ci-dessus a été généré automatiquement par Powerdrill.
Cliquez sur le lien pour voir la page de résumé et d'autres articles recommandés.