Mise à l'échelle des techniques avancées basées sur l'IA pour résoudre des problèmes d'optimisation combinatoire complexes

Un cadre basé sur des techniques avancées d'IA peut résoudre des problèmes complexes et gourmands en calcul plus rapidement et de manière plus évolutive que les méthodes de pointe, selon une étude menée par des ingénieurs de l'Université de Californie à San Diego.

Dans le document publié dans Intelligence des machines naturelles, les chercheurs présentent HypOp, un framework qui utilise l'apprentissage non supervisé et les réseaux neuronaux hypergraphiques. Le framework est capable de résoudre les problèmes d’optimisation combinatoire beaucoup plus rapidement que les méthodes existantes. HypOp est également capable de résoudre certains problèmes combinatoires qui ne peuvent pas être résolus aussi efficacement par les méthodes précédentes.

“Dans cet article, nous abordons la tâche difficile de résoudre les problèmes d'optimisation combinatoire qui sont primordiaux dans de nombreux domaines de la science et de l'ingénierie”, a déclaré Nasimeh Heydaribeni, auteur correspondant de l'article et chercheur postdoctoral au département de génie électrique et informatique de l'UC San Diego. . Elle fait partie du groupe de recherche du professeur Farinaz Koushanfar, qui codirige le Center for Machine-Intelligence, Computing and Security de la Jacobs School of Engineering de l'UC San Diego. Le professeur Tina Eliassi-Rad de l'Université Northeastern a également collaboré avec l'équipe d'UC San Diego sur ce projet.

Un exemple de problème combinatoire relativement simple consiste à déterminer la quantité et le type de marchandises à stocker dans des entrepôts spécifiques afin de consommer le moins de gaz possible lors de la livraison de ces marchandises.

HypOp peut être appliqué à un large éventail de problèmes difficiles du monde réel, avec des applications dans la découverte de médicaments, la conception de puces, la vérification logique, la logistique et bien plus encore. Ce sont tous des problèmes combinatoires comportant un large éventail de variables et de contraintes qui les rendent extrêmement difficiles à résoudre. En effet, dans ces problèmes, la taille de l’espace de recherche sous-jacent pour trouver des solutions potentielles augmente de façon exponentielle plutôt que linéaire par rapport à la taille du problème.

HypOp peut résoudre ces problèmes complexes de manière plus évolutive en utilisant un nouvel algorithme distribué qui permet à plusieurs unités de calcul sur l'hypergraphe de résoudre le problème ensemble, en parallèle, plus efficacement.

HypOp introduit de nouveaux problèmes d'intégration exploitant les réseaux neuronaux hypergraphiques, qui ont des connexions d'ordre supérieur à celles des réseaux neuronaux graphiques traditionnels, pour mieux modéliser les contraintes du problème et les résoudre de manière plus efficace. peut également transférer l’apprentissage d’un problème pour aider à résoudre plus efficacement d’autres problèmes apparemment différents. HypOp comprend une étape supplémentaire de réglage fin, qui conduit à trouver des solutions plus précises que les méthodes existantes précédentes.

Le code pour HypOp est disponible ici.

Ci-dessous, l'équipe de recherche de l'UC San Diego sur cet article présente les résultats pour un public plus large au moyen d'une courte période de questions et réponses.

Vous notez dans le communiqué de presse que HypOp transfère également les leçons d’un type d’objectif de problème pour aider à résoudre plus efficacement d’autres fonctions de coût. Pour un expert non technique, y a-t-il autre chose à dire sur ce phénomène qui soit pertinent dans le cadre d’une conversation plus large sur la façon dont l’IA permet aux chercheurs de résoudre des problèmes et de faire des découvertes qui seraient autrement impossibles ?

La capacité de l'HypOp à transférer et apprendre d'un problème pour aider à en résoudre d'autres est un excellent exemple de la façon dont l'IA peut introduire un changement de paradigme dans la recherche et la découverte. Cette capacité, connue sous le nom d’apprentissage par transfert, permet aux systèmes d’IA de transférer les connaissances acquises lors de la résolution d’un problème à des problèmes nouveaux mais connexes avec une fonction de coût différente, ce qui les rend plus polyvalents et efficaces.

Pour les experts non techniques, réfléchissez au fonctionnement de l’expertise humaine. Par exemple, l’apprentissage du piano crée une base musicale complète qui rend l’apprentissage de la guitare plus rapide et plus efficace. Les compétences transférables comprennent les connaissances en théorie musicale, la maîtrise de la lecture, la compréhension rythmique, la dextérité des doigts et les capacités auditives. Ces compétences améliorent collectivement l’expérience d’apprentissage et conduisent à une maîtrise plus rapide et meilleure de la guitare pour quelqu’un qui sait déjà jouer du piano. En comparaison, un étudiant en musique débutant aurait une courbe d’apprentissage beaucoup plus longue.

Cette synergie entre l'intelligence humaine et l'IA amplifie la capacité des chercheurs à relever des défis interdisciplinaires complexes et à générer des progrès d'une manière qui était auparavant inimaginable. C'est l'une des raisons pour lesquelles nous sommes très enthousiasmés par les avancées et les contributions d'HypOp.

Il y a beaucoup de discussions dans de nombreux cercles différents sur l’utilisation de l’apprentissage automatique et de l’intelligence artificielle pour aider les chercheurs à faire des découvertes plus rapidement, voire même à faire des découvertes qui seraient autrement impossibles. Pour les personnes qui ne comprennent peut-être pas tous les détails techniques de votre nouvel article, quelle influence pensez-vous que cette nouvelle approche, HypOp, aura sur la manière dont l’IA est utilisée dans la résolution de problèmes et la recherche ?

Le concept global est que l’apprentissage de la structure pertinente du problème peut grandement améliorer la qualité et la rapidité des problèmes d’optimisation combinatoire. La méthodologie particulière d'HypOp présente un potentiel important pour influencer la manière dont l'IA est appliquée à la résolution de problèmes et à la recherche. En tirant parti des réseaux de neurones hypergraphiques (HyperGNN), HypOp étend les capacités des réseaux de neurones graphes traditionnels pour résoudre de manière évolutive les problèmes d'optimisation combinatoire contrainte d'ordre supérieur. Cette avancée est cruciale car de nombreux problèmes du monde réel impliquent des contraintes et des interactions complexes qui vont au-delà des simples relations par paires suggérées précédemment.

Le code pour HypOp est disponible en ligne. Pensez-vous que les gens commenceront immédiatement à utiliser le code pour résoudre des problèmes d’optimisation combinatoire ? Ou y a-t-il encore du travail à faire avant que les gens puissent commencer à utiliser le code ?

Oui, les utilisateurs peuvent immédiatement commencer à utiliser le code open source HypOp pour résoudre des problèmes d’optimisation combinatoire à grande échelle.

Quels problèmes HypOp est-il capable de résoudre et que d’autres méthodes ne peuvent pas résoudre ?

HypOp peut résoudre des problèmes d’optimisation à grande échelle avec des fonctions objectives et des contraintes génériques. La plupart des solveurs existants ne peuvent résoudre des problèmes qu'avec des fonctions objectifs spécifiques telles que des fonctions linéaires ou quadratiques et ne peuvent modéliser que des contraintes par paires. De plus, HypOp exploite des techniques de formation distribuées qui lui permettent de s'adapter à des cas de problèmes importants.

Quelles sont les prochaines étapes en termes de recherche pour HypOp ?

Nous nous concentrons sur l’extension de la généralisabilité et de l’évolutivité de HypOp. Nous y parvenons en concevant d’autres techniques d’IA avancées, capables d’apprendre en traitant des cas de problèmes plus petits et en les généralisant à des cas de problèmes plus importants.