Le problème de la prise de décision est au coeur des systèmes analytiques. Il s'agit notamment d'aider les choix par "extraction de connaissances" à partir de données, structurées ou non : c'est, défini très grossièrement, le rôle du datamining.
Les méthodes les plus classiques sont probabilistes ou, de plus en plus, liés à des processus associés à ce qu'on appelle "l'intelligence artificielle" (lire l'article correspondant de notre dossier). Parmi ces derniers processus figurent les algorithmes génétiques.
Ceux-ci sont des algorithmes d'optimisation (capables de réussir là où d'autres méthodes échouent) ou d'affectation, et ont donc un rôle particulier (ils cherchent à découvrir des connaissances dirigées) qui diffère de celui des arbres de décisions ou des réseaux de neurones, souvent utilisés en amont à des fins (non dirigées) de profiling, de diagnostic, voire des fins prédictives.
Ils sont appelés génétiques car ils reposent sur les principes darwiniens de l'évolution des espèces.
Rappelons que ceux-ci stipulent que ce sont les espèces les mieux "adaptées" qui perdurent, et que le renouvellement d'une espèce est essentiellement dû à ses "meilleurs individus" (soit les plus "adaptés" au sein de la population de l'espèce).
| Optimiser un réseau d'agences ou de transport |
Etudiés depuis quelques dizaines d'années seulement, les algorithmes génétiques recherchent le ou les extrema d'une fonction définie sur un espace de données à l'aide d'un ensemble de paramètres, et fonctionnent en appliquant aux données (codées par l'algorithme de manière appropriée) des opérateurs dits de sélection, de croisement ou de mutation, ceci afin d'évaluer le résulat et d'éliminer ceux qui n'aboutissent pas à une solution optimisée.
Appliquons cela à une base de données contenant des informations sur un réseau d'agences : il s'agira par exemple de définir le nombre et la localisation de celles-ci pour que le taux de couverture soit maximal, et le coût d'exploitation minimal. Les données feront état des localisations, couvertures, liens, coûts fixes & variables et contraintes d'exploitation des agences du réseau (par agence, cela peut représenter plusieurs dizaines de paramètres), la fonction à optimiser étant celle définie plus haut et un ensemble de solutions de départ (la "population initiale") sera choisi aléatoirement pour initier le processus d'optimisation.
On fera donc évoluer, via l'algorithme génétique, la population initiale. Par des sélections (choix de paires d'éléments de population - les "parents" - distinguées par leur adaptabilité au regard de la fonction à optimiser), des croisements (aboutissant à la "descendance" des parents, et introduisant là aussi une part de hasard) et des mutations (variations également aléatoires de paramètres, permettant d'explorer l'espace des solutions possibles).
| Aboutir à une génération ayant héritée des meilleurs caractéristiques de sa descendance |
Cela aboutira finalement à une population finale ayant progressivement hérité des "meilleures" caractéristiques des générations précédentes, l'algorithme s'arrêtant dès que ces caractéristiques répondent de manière satisfaisante au problème à résoudre.
D'autres applications sont envisageables : on pense par exemple à l'optimisation d'un emploi de temps (un transporteur notamment pourra ainsi gérer au plus fin les tournées de collecte ou de livraison), mais également au traitement d'image ou au contrôle de systèmes évolutifs (comme une chaîne de production), sans que cette liste soit bien sûr exhaustive.
Pour autant, les algorithmes nécessitent au préalable la collecte de données suffisamment pertinentes, et surtout la définition, pour celles-ci, d'un "principe de codage" (l'analogue de l'ADN pour les espèces vivantes) qui peut-être complexe à déterminer. Ils ne s'appliquent pas avec un égal à bonheur à toutes les collections de données, pour lesquels d'autres techniques d'optimisation pourront s'avérer plus rapides car moins approximatives, et sont à réserver, en général, à des problèmes relativement complexes.
|
De la classification à l'apprentissage, l'éventail des méthodes décisionnelles
|
|
Les systèmes décisionnels doivent d'aborder classifier (structurer), le cas échéant, les données. L'approche qui consiste à décrire la connaissance sous forme de règles qui forme un système expert, lequel est alors utilisé pour classifier de nouveaux cas, était en vogue dans les années 80. Elle a été supplantée par des techniques inductives dont le principe est la production d'une procédure de classification générale à partir d'exemples, ce qui caractérise une bonne technique de ce type étant à la fois sa capacité à classifier correctement et son pouvoir prédictif
satisfaisant pour les nouveaux entrants dans la base de données.
Pour le traitement des données structurées, les méthodes de natures probabilistes ou statistiques qui, la plupart du temps, émettent des hypothèses sur les distributions des données, se distinguent des méthodes
issues de "l'intelligence artificielle" (si tant est que le terme soit approprié), lesquelles sont, traditionnellement, divisées en deux catégories : symboliques (arbres de décision) et adaptatives (réseaux de neurones et algorithmes génétiques).
Les arbres de décisions et les réseaux de neurones doivent permettre d'extraire des profils (par exemple établir un profil client pour le marketing, un profil d'emprunteur pour décider de l'attribution ou non par la banque d'un prêt à ce dernier), voire des formes dans une image, de diagnostiquer des pannes (c'est le rôle des systèmes de contrôle de processus), ou d'effectuer des prévisions (financières à partir de l'évolution des marchés).
Enfin les algorithmes génétiques, dont nous venons de voir le rôle, permettent en sus "l'apprentissage" des réseaux de neurones, ceci afin d'optimiser la capacité de ces derniers à extraire ou prédire.
|
|
Sciences & Informatique
