Développement d'un logiciel d'expertise technique d'installation frigorifiques de chambre froides

I.4.2 Les algorithmes génétiques

C'est au début des années 1960 que John Holland de l'Université du Michigan a commencé à s'intéresser à ce qui allait devenir les algorithmes génétiques. Ces algorithmes font partie du champ de l'Intelligence Artificielle (IA). Il s'agit d'IA de bas niveau, inspirée par « l'intelligence » de la nature. Ils sont basés sur le concept de sélection naturelle élaboré par Charles Darwin. Le vocabulaire employé est donc directement calqué sur celui de la théorie de l'évolution et de la génétique. Un tel algorithme est définit par :

· Des individus : ce sont des solutions potentielles du problème ;

· Des gènes : un gène est un ensemble de bits. Ils constituent le génotype des individus, généralement exprimés sous forme binaire. Notre problème étant multidimensionnel, un gène sera représenté par une composante codée sous forme binaire ;

· Une fonction de codage, permettant de retrouver le génotype de chaque individu ;

· Une fonction de décodage, permettant de retrouver un individu (son phénotype) à partir de son génotype ;

· Une population : c'est un ensemble d'individus ;

· Une fonction de fitness: c'est la fonction positive à optimiser. Elle mesure pour un individu donné son adaptation au problème posé.

L'idée fondamentale est la suivante : le pool génétique d'une population donnée contient potentiellement la solution, ou plutôt une meilleure solution, à un problème adaptatif donné. Cette solution n'est pas exprimée, car la combinaison génétique sur laquelle elle repose est dispersée chez plusieurs individus. Elle ne le sera que par l'association de ces combinaisons génétiques au cours d'une évolution tendant à améliorer les individus (les rendre plus adaptés au problème posé).

Les étapes de l'algorithme consistent donc à faire évoluer une population initiale, de façon à ce que les individus soient de plus en plus adaptés au fil des générations. Les étapes que nous nous avons suivit sont les suivantes :

1. Genèse de la population : une population de taille N est tirée au hasard, déjà codée sous forme binaire.

2. Décodage et évaluation de la population : chaque individu est décodé, et son fitness évalué. Nous avons utilisé ici un codage binaire pur sur 16 bits, autorisant donc une représentation dont les valeurs décimales correspondantes sont comprises entre 0 et 2¹⁶-1. Pour une variable X telle que Xmin < X < Xmax, nous avons utilisé un codage linéaire où _Xmin représente 0 et _Xmax représente 2¹⁶-1.

3. Sélection - élimination : on met en oeuvre une procédure de sélection, à l'issue de laquelle seule une moitié de la population sera retenue pour la génération suivante. Il existe de nombreuses procédures de sélection, mais nous avons retenu ici la technique dite de « sélection par tournoi avec élitisme ». Dans cette technique, deux individus sont choisis au hasard par tirage avec remise, et combattent (on compare leurs fonctions d'adaptation) pour accéder à la génération intermédiaire. Le plus adapté l'emporte avec une probabilité de sélection p_s (0,5 < p_s < 1) fixée. Cette étape est répétée jusqu'à ce que la génération intermédiaire soit remplie (N/2 individus). Si l'individu le plus adapté ne se retrouve pas dans cette génération intermédiaire, alors il y est introduit en remplacement d'un autre pris au hasard. Il est tout à fait possible que certains individus participent à plusieurs tournois : s'ils gagnent plusieurs fois, ils auront donc le droit d'être copiés plusieurs fois dans la génération intermédiaire, ce qui favorisera la pérennité de leurs gènes.

4. Croisement : une fois la génération intermédiaire remplie, les individus sont répartis en couples (soit N/4 couples). Dans chaque couple, les gènes des parents sont copiés et recombinés de façon à former deux descendants possédant des caractéristiques issues des deux parents. On obtient ainsi les N/2 fils devant compléter la génération intermédiaire pour obtenir une nouvelle génération (N individus). Nous avons utilisé la technique de croisement en deux points, où les deux points de croisement sont choisis au hasard. Ce croisement s'effectue tel que présenté à la figure I.3 qui suit.

Figure I.3 : Principe du croisement en deux points

5. Mutation : une mutation est l'inversion d'un bit dans le génotype d'un individu (Figure I.4). Les mutations jouent le rôle de bruit et empêchent l'évolution de se figer. Elles permettent d'assurer une recherche aussi bien globale que locale, selon le poids et le nombre des bits mutés. De plus, elles garantissent mathématiquement que l'optimum global peut être atteint. La procédure de mutation consiste à muter chaque bit de chaque individu avec une probabilité p_m (généralement comprise entre 0,001 et 0,1). Une probabilité de mutation élevée en début d'évolution est souhaitable pour une bonne exploration de l'espace de recherche. Mais elle doit en suite diminuer afin de stabiliser l'évolution et faire converger l'algorithme. C'est pourquoi les techniques d'auto adaptation des probabilités de mutation sont très intéressantes. Celle que nous avons utilisée associe à chaque gène d'un individu un autre gène représentant sa probabilité de mutation. Ces gènes des probabilités suivant aussi les mêmes opérateurs de croisement et de mutation que ceux de l'individu.

Figure I.4 : Principe d'une mutation

6. Retour à l'étape 2. : jusqu'à ce qu'un nombre de génération fixé soit atteint.

I.5 Le génie logiciel

I.5.1 Principes généraux du génie logiciel

En informatique, les systèmes logiciels sont contrairement aux apparences très complexes. C'est ce qui a conduit à ce qu'on appelle souvent « crise du logiciel» («software crisis"). En effet :

· Le coût et les délais de développement d'un logiciel sont très difficiles à prévoir. On note souvent (STROHMEIER, 1996) des dépassements des coûts et délais prévus de 70% et 50% respectivement ;

· La qualité du logiciel, difficile à maîtriser, fait souvent défaut : insatisfaction des besoins de l'utilisateur, consommation excessive de ressources matérielles, taux de pannes élevé, ... ;

· La réutilisation de composants existant pour confectionner de nouveaux systèmes n'est pas chose facile, pourtant indispensable pour amortir les coûts de conception sur plusieurs projets.

Dans ce contexte, le génie logiciel se défini alors comme une science offrant des outils et démarches pour la maîtrise des systèmes logiciels sur tout leur cycle de vie (conception, exploitation et retrait de service). Comme toute science de l'ingénieur, elle est aussi régie par un ensemble de principes et de normes. C'est ainsi qu'on peut trouver dans la littérature :

· Des principes sur le management des projets de développements informatiques ;

· Des principes sur le management et l'évaluation de la qualité du logiciel ;

· Des principes sur la conception d'interfaces graphiques ;

· Et bien d'autres encore ... .

Ce sont les principes exposés dans (STROHMEIER, 1996) qui nous ont guidés dans ce travail.

I.5.2 Outils de développement client-serveur

Les outils de développement informatique se classent selon les types d'applications. Pour les applications fonctionnant autour d'une base de données, les outils de développement client-serveur sont les plus appropriés. Il s'agit (GARDARIN, 2000) :

· Les outils d'interrogation de la base de données, constitués principalement d'un médiateur assurant la connexion entre la base de données (serveur) et l'application (client). Et aussi d'un langage d'interrogation (généralement SQL : Structured Query Language), permettant d'envoyer des requêtes à la base de données ;

· Les langages de programmation permettant d'écrire le code proprement dit de l'application. Les langages utilisés actuellement sont ceux de quatrième génération (L4G) et les ateliers de génie logiciel (AGL). Les L4G offrent en général toutes les fonctionnalités des langages de troisième génération (constructions procédurales, programmation modulaire, ...) tels que PASCAL, ou FORTRAN. En plus, elles sont conçues pour faciliter la conception d'interfaces graphiques, et supportent le modèle objet facilitant ainsi la réutilisation de composants. Visual Basic de Microsoft et Delphi de Borland sont deux exemples de L4G. Les AGL sont plus élaborés, et offrent en plus des fonctionnalités des L4G un référentiel permettant de manager le

cycle de vie des applications. Visual Basic dans sa version Entreprise et Designer/2000 d'oracle sont des exemples d'AGL.

~ Les langages de programmation dédiés à des développements spécifiques. Selon les fonctionnalités de l'application, il se peut que le L4G ou l'AGL utilisé ne soit pas adapté pour certaines tâches. Dans ce cas, le module objet correspondant sera écrit et compilé dans un autre langage, puis relié au module principal par une technique de liaison appropriée. Par exemple, Visual Basic est un langage peu approprié pour des tâches de calcul importantes. Ces tâches pourront donc très bien être écrites en C ou en FORTRAN, puis compilées, et connectées ensuite au reste du programme écrit en Visual Basic. Sous Windows, cette connexion peut être faite en utilisant une technique de liaison dynamique, exposée au paragraphe suivant.

I.5.3 La liaison dynamique sous Windows : les DLL

Le problème ici est de savoir quand et comment le code machine d'un programme en un langage donné sera lié à des fonctions utiles situées dans une bibliothèque de routines.

Une première solution est la liaison statique (static binding). Ici, le compilateur (ou plus précisément l'éditeur de liens) assemble le programme compilé avec le code objet de la bibliothèque de routines et les écrits dans un ficher exécutable commun. Il se crée ainsi une paire indissociable. La liaison statique fonctionne à merveille, mais présente cependant quelques inconvénients. Premièrement, les fonctions intégrées en provenance de la bibliothèque de routines ne peuvent plus être modifiées ultérieurement. Si l'on constate une erreur ou si l'on souhaite modifier ou étendre l'action d'une fonction, il faut entièrement recréer le ficher exécutable et le transmettre à l'utilisateur. Deuxièmement, le même code des fonctions de routines est intégré dans de nombreux programmes et sera ainsi chargé plusieurs fois en mémoire si l'on lance simultanément plusieurs programmes. On gaspille ainsi un précieux espace mémoire.

Une meilleure solution est la liaison dynamique (dynamic binding). Ici, le code objet de la bibliothèque de routines n'est pas intégré à la compilation, mais seulement à l'exécution. La bibliothèque de routines est ainsi disponible dans un fichier séparé, appelé bibliothèque de liens dynamiques (Dynamic Link Library : DLL). Lors de l'exécution, le programme accède à la DLL, ce qui lui permet d'appeler les fonctions qu'elle contient par le biais d'un mécanisme prédéfini.

En cas de modification de la bibliothèque de routines, il n'est donc plus nécessaire de recompiler tout le programme, le remplacement du fichier DLL est suffisant. Les fonctions issues de la DLL ne sont plus chargées plusieurs fois, car plusieurs programmes peuvent se référer simultanément à une instance de la DLL présente en mémoire.

Le domaine d'application de cette technique s'étend bien plus loin que les bibliothèques de routines du compilateur. Windows lui même utilise le même principe en intégrant tout son système d'interface de programmation (Application Programming Interface : API) composé de plus d'un millier de fonctions, sous la forme de nombreuses DLL.