L'évaluation de l'emplacement optimal des parkings est étonnamment difficile sur le plan mathématique et constitue un sous-ensemble d'un problème de complexité informatique classique avec des applications beaucoup plus larges. Une équipe de scientifiques des données a combiné le recuit quantique avec un processus qui tente d'imiter les processus sous-jacents de l'intuition humaine dans une technique qui offre une précision de solution bien supérieure aux approches conventionnelles.

La technique est décrite dans un article paru pour la première fois en ligne le 30 septembre 2022 dans Réseaux intelligents et convergés.

Le problème de localisation des installations, ou FLP, est un défi de longue date dans la recherche opérationnelle - l'application de méthodes scientifiques à la prise de décision et à la résolution de problèmes par les gestionnaires de grandes organisations commerciales, publiques ou militaires. Le FLP vise à déterminer l'emplacement optimal et le nombre d'installations dans une zone donnée, compte tenu de certaines contraintes

Les décideurs d'un système de soins de santé, par exemple, peuvent avoir à déterminer où un nouvel hôpital devrait être implanté. S'ils installent cette installation dans un endroit trop difficile d'accès pour les personnes âgées, les taux de mortalité pourraient augmenter. La contrainte ici est d'essayer de minimiser la mortalité. Mais s'ils installent l'hôpital dans un endroit plus facilement accessible, les coûts immobiliers pourraient grignoter une plus grande partie de leur budget, une autre contrainte. Cela pourrait également réduire la capacité des prestataires de soins de santé à fournir des services, augmentant encore une fois les taux de mortalité.

Il peut sembler qu'il soit mathématiquement simple d'identifier un ou même un certain nombre de zones idéales où les taux de mortalité et les dépenses sont les plus bas. Mais trouver des solutions exactes à cet exemple et à d'autres exemples de FLP - avec beaucoup plus de contraintes sur ce qui doit être optimisé que la distance et le coût - est un défi de calcul.

En fait, le FLP, un problème d'optimisation combinatoire, est classé par les spécialistes de la théorie de la complexité dans la catégorie des problèmes "NP-difficiles" - les plus difficiles qui soient. Il n'y a pas de solution unique qui puisse être appliquée à la planification d'emplacement pour différentes situations dans différents domaines.

L'emplacement optimal des parkings n'est qu'un autre exemple du FLP, qui intéresse vivement les administrateurs municipaux qui souhaitent éviter les embouteillages et, par extension, réduire les émissions de gaz à effet de serre. Moins les automobilistes passent de temps à chercher une place de stationnement, moins il y a de circulation et moins de GES. Dans de nombreuses villes des régions à urbanisation rapide, notamment dans le monde en développement, il s'agit d'une préoccupation urgente.

Les méthodes conventionnelles utilisées pour produire des solutions décentes (mais pas exactes) au problème de localisation des parkings incluent divers types d'algorithmes exécutés par l'intelligence artificielle sur des ordinateurs classiques (par opposition aux ordinateurs quantiques). Mais dès lors que le volume de données impliquées augmente significativement, les performances de ces « algorithmes intelligents classiques » diminuent fortement.

"À ce stade, l'intuition d'une personne peut surpasser l'ordinateur", a déclaré Sumin Wang, co-auteur de l'article et chercheur au Key Laboratory of Specialty Fiber Optics and Optical Access Networks de l'Université de Shanghai. "Mais une telle intuition ne devrait pas être considérée comme mystique ou comme de simples 'intuitions'. Il existe une explication scientifique solide de l'origine de l'intuition humaine, et cela peut nous inciter à essayer de l'imiter avec des ordinateurs."

Lorsqu'un ingénieur ou un architecte a le sentiment qu'un pont, un système de construction ou une autre structure technique est sur le point de tomber en panne, mais qu'il ne peut pas justifier directement pourquoi, cela peut être le résultat de décennies d'expérience. Un cycliste peut sentir exactement quand son vélo est sur le point de basculer sans être en mesure d'expliquer ce qu'il a ressenti qui lui a permis d'effectuer une telle évaluation.

La vaste expérience et les connaissances accumulées peuvent permettre à l'individu d'évaluer rapidement la totalité d'une situation et de percevoir directement un fait sans passer par un processus de raisonnement traditionnel, permettant des décisions rapides et efficaces malgré la complexité des environnements.

Ceux qui étudient l'intuition humaine décrivent ce qui se passe dans le cerveau comme une réduction rapide et nette de «l'espace de recherche» - le terme utilisé par les informaticiens pour décrire le paysage des solutions réalisables. L'expérience et les connaissances permettent aux humains de "savoir" comment s'occuper de manière sélective des aspects les plus saillants du problème, écarter le reste et ainsi simplifier les calculs nécessaires.

"L'intuition artificielle", reproduisant artificiellement l'intuition humaine, est un domaine de recherche émergent dans le domaine de l'intelligence artificielle. L'objectif est de développer des méthodes de raisonnement intuitif inspirées du cerveau humain - l'une des capacités les plus puissantes que nous possédions - qui se concentrent de la même manière sur les données de base tout en ignorant les données non importantes pour réduire l'espace de recherche.

En utilisant le problème de localisation optimale des parkings, les chercheurs ont développé ce qu'ils appellent un mécanisme d'attention sélective (SAM), inspiré de l'intuition humaine, et l'ont combiné avec le recuit quantique (QA).

L'AQ a séparément reçu beaucoup d'attention ces dernières années en tant que nouveau paradigme de calcul pour résoudre les problèmes d'optimisation classiques. Les algorithmes QA apportent des améliorations significatives en termes de temps d'exécution de l'algorithme et de qualité de la solution pour certains problèmes NP-difficiles qui sont mal résolus par les méthodes classiques.

Dans les problèmes d'optimisation, on recherche l'optimum de nombreuses combinaisons possibles, un minimum ou un maximum. Et en physique, tout est à la recherche de son état d'énergie minimum, des boules dévalant des collines aux électrons excités retournant à leur état fondamental. Cela signifie que les problèmes d'optimisation peuvent essentiellement être redéfinis comme des problèmes de minimisation de l'énergie. QA exploite simplement la physique quantique pour localiser les états d'énergie les plus bas d'un problème, et donc le minimum ou le maximum de l'attribut cible. L'AQ a déjà été déployée dans diverses applications allant de l'optimisation du trafic à la planification des ressources et à la chimie quantique.

Pour leur problème d'optimisation de parking, les chercheurs ont utilisé SAM pour réduire l'espace de recherche et fournir une direction pour la prochaine étape de recherche, et QA pour rechercher cet espace et améliorer l'efficacité de la recherche.

Ils ont appliqué leur concept à une expérience de stationnement dans le monde réel en utilisant des données de latitude et de longitude réelles du district de Luohu à Shenzhen, en Chine. Ces données gouvernementales à plate-forme ouverte comprenaient les sites à forte demande de stationnement, les emplacements de stationnement possibles, les emplacements de stationnement existants et leur capacité de stationnement. Le district de Luohu couvre une superficie d'environ 80 kilomètres carrés, une région bien trop grande pour qu'un algorithme intelligent classique avec des ressources informatiques limitées calcule directement toutes les données de la zone.

L'ensemble de la zone a d'abord été partitionné en blocs pour économiser les ressources de calcul, puis SAM a été appliqué pour se concentrer sur les points de données importants, qui ont été automatiquement filtrés et optimisés. De nouveaux résultats de localisation ont ensuite été obtenus en simulant la préférence de QA pour les états à faible énergie. Des points d'attention sélectifs ont à leur tour été mis à jour en fonction des résultats de l'emplacement de ces installations, et le processus a été répété plusieurs fois jusqu'à ce qu'une solution claire - l'emplacement d'un nouveau parking proposé dans la région - apparaisse.

Pour évaluer leur approche, les chercheurs ont utilisé une technique couramment utilisée pour mesurer la précision de la solution d'algorithmes à objectifs multiples. Par rapport aux approches concurrentes, la technique SAM plus QA a produit des ensembles de solutions plus optimaux et réalisables en un temps d'exécution plus court.

Les chercheurs veulent maintenant adopter leur approche et l'appliquer à d'autres problèmes d'implantation et applications connexes de l'intuition artificielle.

Fourni par Tsinghua University Press