969 - Arbres de Steiner et réseaux de neurones

N. Lygeros

La difficulté de la résolution optimale du problème de Steiner pour un ensemble donné a conduit la recherche à s’intéresser aux résolutions approchées. En effet comme le problème a une complexité du type NP~complet, plusieurs algorithmes heuristiques ayant une complexité polynomiale ont été proposés. Ces derniers ont fait apparaître le problème des contraintes à savoir la diminution de la longueur de l’arbre et la réduction du temps de calcul. Certains algorithmes utilisent les chemins les plus courts pour relier les membres d’un groupe local. Cependant, même si le temps de calcul de ce genre de constructions est toujours faible, la longueur des arbres résultants n’est pas toujours acceptable. Et cela est compréhensible puisque cela revient à faire de l’optimisation locale là où seule l’optimisation globale est nécessaire. D’autres algorithmes de construction de l’arbre approché établissent les connexions entre les sous-arbres déjà existants de l’arbre couvrant partiel à l’aide des arbres minimaux de Steiner simples. L’aboutissement de ces algorithmes revient à modifier l’heuristique de Kruskal mais aussi celle de Takahashi et Matsuyama. Néanmoins les bornes d’approximations doivent être encore améliorées.

Une autre approche pour traiter le problème de Steiner consiste à exploiter la puissance de la structure des réseaux de neurones. En effet ceux-ci sont des excellents approximateurs généraux. La méthode la plus courante pour l’apprentissage des poids des connexions est basée sur la notion de rétro-propagation de l’erreur. Seulement dans cette méthode le gain de réactualisation des valeurs est choisi le plus souvent de manière intuitive à l’instar de ce qui est effectué pour les algorithmes génétiques. Aussi, il faudrait implémenter au réseau de neurones une stratégie du choix optimal qui soit basée sur le processus d’apprentissage. L’avantage de cette manière de faire c’est l’évitement des erreurs d’approximation de l’optimisation locale. Le fonctionnement hautement non linéaire des réseaux de neurones permet d’atteindre de bonnes approximations globales. Cependant lui aussi, il doit être muni d’heuristiques et de méta-heuristiques afin de surmonter les obstacles inhérents aux problèmes complexes. Sans celles-ci, le réseau de neurones peut se stabiliser sans parvenir à un résultat intéressant. Il s’agit donc d’inculquer au réseau de neurones des schémas mentaux et non des méthodologies strictes. C’est seulement ainsi que nous pouvons espérer obtenir des résultats corrects même dans les cas les plus difficiles. Car la liberté du réseau de neurones combinée à sa puissance parallèle permet d’exploiter la structure des contraintes de la construction des arbres de Steiner. Ces derniers peuvent alors être interprétés comme des approximations d’idées mentales ainsi que nous les avons présentées dans notre article intitulé : Idées fractales dans un milieu chaotique. Cette fois, l’aspect chaotique sert d’élément dynamique à la recherche d’un élément statique qui est représenté par le fractal considéré. Ce dernier peut être alors vu comme l’aboutissement d’un processus heuristique créatif puisque la liberté permet de développer la créativité du réseau de neurones même s’il résout un problème de contraintes.