Contre-exemples à l'exhaustivité des principaux algorithmes dans le problème d'optimisation de contraintes distribuées
Des chercheurs de l'Université de Tsukuba ont présenté des contre-exemples aux propriétés clés supposées de l'OPTimisation distribuée asynchrone (ADOPT) et de ses algorithmes successeurs. ADOPT est un algorithme bien connu pour résoudre des problèmes d’optimisation de contraintes distribuées.
L’équipe a démontré que ces algorithmes ne garantissent pas nécessairement les propriétés clés, à savoir la terminaison et l’optimalité. De plus, ils ont proposé une version modifiée d'ADOPT qui garantit ces propriétés. L'étude est publiée dans la revue Intelligence artificielle.
Les problèmes d’optimisation de contraintes distribuées sont cruciaux pour la modélisation de systèmes coopératifs-multiagents. L'algorithme ADOPT est considéré comme ayant deux propriétés importantes : la terminaison, qui signifie que l'algorithme se termine dans un temps fini, et l'optimalité, qui indique qu'une solution optimale est toujours obtenue lorsque l'algorithme se termine. On pensait que ces propriétés étaient valables pour les algorithmes successeurs basés sur ADOPT.
Cette étude présente des contre-exemples à la terminaison et à l'optimalité d'ADOPT et de ses algorithmes successeurs. Cela implique que les preuves données pour ADOPT et ses algorithmes successeurs sont incorrectes et qu'il existe une possibilité que l'algorithme ne se termine pas ou se termine avec une solution sous-optimale.
De plus, les chercheurs ont identifié la cause de l’existence de tels contre-exemples dans ADOPT et ont proposé un algorithme qui les corrige. De plus, ils ont prouvé la terminaison et l’optimalité de la version modifiée d’ADOPT.
En appliquant la version modifiée d'ADOPT, les échecs d'ADOPT et de ses algorithmes successeurs peuvent être évités, et la fiabilité des systèmes basés sur ces algorithmes devrait être améliorée.
