Rapporteur, ensc, Montpellier








télécharger 0.86 Mb.
titreRapporteur, ensc, Montpellier
page14/22
date de publication22.04.2017
taille0.86 Mb.
typeRapport
c.21-bal.com > comptabilité > Rapport
1   ...   10   11   12   13   14   15   16   17   ...   22

II.Sélection par diversité de composés déjà mis en plaques


La sélection de plaques est un problème qui relève de l’optimisation. Nous avons choisi d’étudier l’efficacité de méthodes d’optimisation sur cette problématique suivant des critères de diversité. Nous allons tout d’abord traiter des méthodes d’optimisations naturelles, puis nous exposerons l’implémentation des méthodes utilisées pour la sélection, avant de présenter les résultats des différentes méthodes.

A.Méthodes d’optimisation naturelles


L’optimisation est un processus consistant à rendre quelque chose le meilleur possible. En science, on cherchera à trouver la meilleure solution possible à un problème donné. L’exemple de problème le plus fréquemment employé pour tester des algorithmes d’optimisation est le problème du voyageur de commerce. Il s’agit de trouver le trajet le plus court possible que pourrait emprunter un voyageur de commerce, sachant qu’il doit passer une seule fois dans plusieurs villes données. C’est Euler qui le premier introduisit un problème de ce type en 1759. Le problème d’Euler consistait à faire parcourir à un cavalier une seule fois toutes les cases d’un échiquier. Ce n’est cependant qu’aux alentours de 1931 que ce problème fit son apparition en mathématiques. Un algorithme d’optimisation doit répondre à deux exigences contradictoires, à savoir trouver une solution qui soit la meilleure possible, et trouver cette solution le plus rapidement possible. Le problème est qu’il existe souvent un grand nombre de solutions possibles pour un problème donné. Ainsi si l’on prend notre exemple du voyageur de commerce, il y a (N-1)! possibilités de parcourir les villes. Pour 30 villes cela fait 8.8 x 1030 solutions possibles. Si l’on suppose que l’on peut évaluer un million de solutions par seconde grâce à un ordinateur, il faudrait 8.8 x 1024 secondes pour résoudre notre problème. A titre de comparaison, l’âge de la terre est de 1.4 x 1017 secondes. Cet exemple montre qu’il est généralement impossible d’évaluer toutes les solutions d’un problème donné.

Les méthodes d’optimisation vont donc devoir, non pas parcourir toutes les solutions possibles, mais parcourir l’espace des solutions afin d’arriver, sinon à la solution idéale, au moins à une solution très proche de celle-ci. Le point de départ dans l’espace des solutions est en principe une ou des solutions aléatoires. Les différences entre les méthodes résident dans la manière de parcourir l’espace des solutions afin de converger vers la ou les meilleures. Dans ce domaine, la nature est une source d’inspiration très riche. Ainsi, toutes les techniques que nous allons présenter sont basées sur des phénomènes naturels.

Avant de présenter quelques unes de ces méthodes, il est intéressant de s’attarder sur le théorème « No free lunch » (NFL). Introduit en 1995 par Wolpert et Macready, ce théorème affirme que les performances moyennes de toutes les méthodes d’optimisation (y compris une recherche aléatoire) sur tous les problèmes sont identiques [210, 211]. Ce théorème a été le point de départ d’une grande controverse dans le domaine de l’optimisation combinatoire, certains allant même jusqu’à utiliser NFL pour réfuter la théorie de l’évolution de Darwin et favoriser celle du « Dessein intelligent » [212, 213, 214]. En se focalisant sur l’aspect purement informatique, il convient de reformuler NFL. Ce dernier affirme comme nous l’avons dit qu’il n’existe pas de méthode d’optimisation « miracle », qui pourrait résoudre tous les problèmes. Cela veut dire que chaque méthode a ses points forts et ses points faibles, et qu’il faut plus se focaliser sur le domaine d’application de la méthode qu’essayer de trouver une méthode capable de résoudre tous les types de problèmes. Le NFL n’est donc pas en contradiction avec le fait que les méthodes que nous allons présenter se révèlent être très efficaces sur certains problèmes donnés.

1.Algorithmes génétiques


Les algorithmes génétiques sont basés sur le principe de la sélection naturelle, développé par Charles Darwin en 1838. Ils ont été étudiés pour la première fois par John Holland dans le milieu des années 70 [215]. Les solutions du problème sont représentées sous forme de chromosomes. Les gènes de ces chromosomes correspondent aux variables du problème. Les valeurs de ces variables sont appelées allèles. L’algorithme s’exécute de la manière suivante :

  1. Un nombre prédéfini de chromosomes sont générés avec des allèles aléatoires. Cet ensemble de chromosomes constitue la première génération. La qualité de la solution est estimée grâce à un score, dépendant du problème traité.

  2. La génération suivante est générée. Dans un premier temps un certain pourcentage des chromosomes est conservé. Pour chaque nouveau chromosome généré, deux parents sont choisis parmi les chromosomes conservés. Un crossover est alors effectué sur les deux parents pour donner deux chromosomes enfants. On procède ensuite à une étape de mutation. Le nombre de gènes mutés est défini à partir d’un taux de mutation prédéfini. Les positions des gènes mutés sont quand à elle définies aléatoirement.

  3. L’étape précédente est répétée jusqu’à la fin de l’évolution. Plusieurs critères peuvent être utilisés pour cela :

  • Le nombre de générations prédéfini a été atteint.

  • Le score maximal est stable sur un grand nombre de générations.

  • Le score prédéfini a été atteint.

Nous allons maintenant nous attarder sur certains composants des algorithmes génétiques.
a.La sélection des parents

La sélection des parents consiste à choisir, parmi les chromosomes conservés lors de l’étape de sélection naturelle, les deux qui vont être utilisés pour donner naissance à deux nouveaux chromosomes. Il existe de nombreuses méthodes pour sélectionner les parents [216]. Les plus connus sont les suivantes :

  • Les chromosomes sont choisis deux à deux par ordre de score. Les deux chromosomes avec les meilleurs scores sont choisis en premier, puis les deux chromosomes suivants, et ainsi de suite. Cette méthode est très simple, mais ne traduit pas la complexité de ce phénomène dans la nature.

  • Les chromosomes sont choisis aléatoirement. A l’inverse de la méthode précédente qui ne laisse aucune part au hasard, dans celle-ci les chromosomes sont choisis de manière totalement aléatoire. Les chromosomes ayant les meilleurs scores ne sont pas privilégiés dans le choix, ce qui une fois encore n’est pas représentatif du mécanisme naturel.

  • On choisi les chromosomes aléatoirement avec pondération. La probabilité qu’a un chromosome d’être choisi dépend de son score. Ce type de méthode combine les avantages des deux précédentes, en faisant intervenir un choix aléatoire tout en privilégiant les chromosomes avec les scores les plus élevés. On assimile ce choix à une roue de la fortune, la taille des segments de la roue étant dépendante de la valeur du score. On distingue deux sous-méthodes pour donner un poids aux chromosomes lors de la sélection :

  • La pondération par rang. Les chromosomes sont classés en fonction de leurs scores. La probabilité de sélection des chromosomes est pondérée par leur position dans le classement, le premier étant celui qui est le plus favorisé.

  • La pondération par score. Dans ce cas ce sont les scores et non plus les classements qui sont pris en compte pour la pondération. Avec cette méthode les écarts entre les valeurs des scores entrent en jeux pour la sélection.

  • Les chromosomes sont choisis par des tournois. Pour ce type de sélection, pour chaque sélection d’un parent, deux chromosomes (ou plus) sont choisis parmi ceux ayant passé la sélection naturelle. Le meilleur est gardé comme parent. L’opération est répétée pour chaque parent à sélectionner.


b.La reproduction

Lors de l’étape de reproduction les parents mélangent leurs gènes afin de donner naissance aux enfants. Cette étape est appelée crossover. C’est une étape importante du fonctionnement des algorithmes génétiques, et différentes méthodes existent [217]. La méthode la plus simple est le crossover à un point. Dans ce cas les parents échangent une partie de leurs gènes en fonction d’un point déterminé aléatoirement, comme le montre la Figure 29.



Figure 29. Crossover un point : les chromosomes échangent les gènes qui se trouvent à droite d’un point de crossover choisi aléatoirement.

L’inconvénient du crossover un point est que les gènes qui sont très éloignés dans un même chromosome ont plus de chances de se trouver séparés que deux gènes qui sont très proches.

Ce problème peut être limité par l’utilisation du crossover deux points qui fonctionne suivant le même principe que le crossover un point (Figure 30). On notera l’existence de crossover multi points qui utilisent encore plus de points de crossover.



Figure 30. Crossover deux points : deux points sont définis aléatoirement et les gènes entre ces deux points sont échangés entre les deux chromosomes.

Le crossover uniforme fonctionne quand à lui sans utiliser de point de crossover. Dans ce cas la génération des enfants se fait en passant aléatoirement les gènes d’un parent ou de l’autre (Figure 31).



Figure 31. Crossover uniforme : un certain nombre de gènes choisis aléatoirement sont échangés.
c.Mutation

Le principe de la mutation est de modifier de manière aléatoire un certain nombre de gènes dans la population. Le but est d’éviter une convergence prématurée de l’algorithme, lui permettant ainsi de sortir des minimums locaux. Les meilleures solutions sont généralement conservées intactes, et ne sont donc pas soumises à la mutation. Le nombre de gènes mutés dépend du taux de mutation prédéfini. Les positions des gènes mutés sont choisies aléatoirement (Figure 32).



Figure 32. Exemple d’une mutation de 10 % sur une population. Le premier chromosome est le meilleur, et n’est pas modifié. Trois gènes sont donc modifiés parmi les trois gènes restants.
d.Fonction de score

La fonction de score est l’élément qui permet aux algorithmes génétiques de prendre en compte un problème donné. La conception d’une fonction de score permettant une évaluation pertinante des solutions d’un problème sous forme chiffrée est indispensable à la réussite du calcul d’optimisation.

2.Recuit Simulé


Le recuit simulé a été proposé comme technique d’optimisation globale par Kirkpatrick et son équipe en 1983 [218]. Cette méthode se base sur le phénomène de recuit des matériaux : le fait de chauffer un matériau, puis de baisser lentement sa température permet d’obtenir une structure cristalline de meilleure qualité. La première étape de l’algorithme est la génération d’une solution aléatoire. Comme pour les algorithmes génétiques, un score est calculé pour chacune des solutions générées par l’algorithme. C’est ce score qui sera optimisé par l’algorithme. Une fois la solution aléatoire générée, on procède au processus de chauffage, cela va correspondre dans notre algorithme à une modification aléatoire des variables. C’est le critère d’acceptation qui va permettre de décider si la nouvelle solution générée va remplacer ou non l’ancienne. Le critère d’acceptation le plus fréquemment utilisé est celui de Metropolis :

(Équation 7)

r est comparé à un nombre aléatoire compris entre 0 et 1, et T est la pseudo température du système. Si la condition est validée, alors la nouvelle solution remplace l’ancienne. Dans le cas contraire, l’ancienne solution est conservée. Plus la température sera élevée, plus une solution avec un mauvais score aura de chance d’être acceptée, et à l’inverse, à mesure que la température du système diminue, un score doit être de plus en plus satisfaisant pour que la solution soit acceptée.

Différents schéma d’évolution de température peuvent être utilisés, tout en gardant à l’esprit que c’est le fait de diminuer lentement la température qui permettra de maximiser les chances de s’approcher du minimum global. Nous pouvons citer trois fonctions de refroidissement [Error: Reference source not found] :

  • refroidissement linéaire : (Équation 8)

  • refroidissement géométrique : (Équation 9)

  • refroidissement Hayjek optimal : (Équation 10)

Comme pour les algorithmes génétiques, l’arrêt de l’algorithme peut se faire soit lorsque l’on considère que la convergence est atteinte, soit au bout d’un nombre d’itérations prédéterminées.

3.Optimisation par essaims particulaires


Cette technique d’optimisation a été introduite par Kennedy et Eberhart en 1995 [219]. Elle trouve ses fondements dans le comportement des animaux se déplaçant en essaims, tels que les insectes. Ce sont en fait les déplacements des individus qui sont modélisés. Cette méthode est principalement destinée à optimiser des variables continues. L'algorithme a été mis au point à partir de travaux précédents portant sur la simulation numérique de vol d'oiseaux ou de mouvements de bancs de poissons [220, 221]. De plus la base sociologique de cet algorithme est très forte. Ainsi, le sociobiologiste Wilson [222] suggère que le partage des informations entre individus, pour trouver de la nourriture par exemple, donne un avantage au groupe dans l'évolution. On peut séparer ce phénomène en deux niveaux. Le niveau supérieur permet notamment la résolution de problèmes, et le niveau inférieur correspond au comportement des individus [223], comportement qui peut se résumer en trois étapes : l’évaluation, la comparaison, et l’imitation.

Dans le cas des essaims particulaires, deux paramètres sont utilisés pour déterminer la vitesse des particules : le meilleur score rencontré par l’individu, plocal, et le meilleur score qu’une particule de l’essaim a trouvé, pglobal. On peut considérer pglobal comme étant la mémoire de l'individu. L'influence de pglobal sur le mouvement de l'individu peut s'assimiler à la nostalgie : chaque individu veut retourner vers le moment le plus agréable de son passé. Pour sa part, gbest s'assimile plutôt à une norme du groupe, que chaque individu cherche à atteindre.

A chaque itération, pour chacune des particules (donc des solutions) on calcule l’équation de mouvement suivante [224] :

  • La vitesse (ou déplacement) :

(Équation 11)

  • La valeur de chaque variable : (Équation 12)

a est la constante d’inertie, b1 et b2 deux variables aléatoires positives.

4.Colonies de fourmis


Les algorithmes de colonies de fourmis ont été introduits par Marco Dorigo [225] lors de sa thèse. Ils imitent le comportement des fourmis pour trouver de la nourriture. Ils peuvent sembler similaires à l'optimisation par essaims particulaires, mais sont cependant bien différents, et utilise notamment les notions de chemins et de phéromones. En effet, les fourmis errent pour trouver de la nourriture. Quand elles en trouvent, elles marquent le chemin entre la colonie et la nourriture. D'autres fourmis vont être attirées par ces phéromones, et vont renforcer le marquage du chemin. Parmi plusieurs chemins menant à de la nourriture, les plus courts auront une concentration en phéromones plus forte et seront donc plus marqués.
Etant donné qu'ils sont basés sur une notion de chemins, ces algorithmes trouvent leurs applications principales dans les graphes.

B.Implémentations des méthodes d’optimisations


Nous avons implémenté et testé les algorithmes génétiques et le recuit simulés. Les résultats obtenus par ces deux méthodes ont été satisfaisant, et nous n’avons pas eu besoin de tester les deux autres méthodes envisagées.

1.Algorithmes génétiques


Nous avons développé une bibliothèque d’optimisation. Cette bibliothèque devait dans un premier temps être utilisable pour la sélection de plaques. Cependant, elle devait également être suffisamment générale pour être utilisable dans d’éventuels projets futurs de chemoinformatique comme notamment le QSAR (sélection de descripteurs, optimisation de paramètres de réseaux de neurones ou de machine à support de vecteurs) et la conception de-novo. Il a dans un premier temps été envisagé d’utiliser une bibliothèque d’algorithmes génétiques existante. Cette bibliothèque devait être en Java afin de pouvoir être intégrée facilement à d’autres logiciels du laboratoire, principalement ScreeningAssistant. Notre choix s’était porté sur la librairie JGAP [226]. Cependant les résultats de nos tests ont étés décevants sur des problèmes d’optimisation simples, sans que la cause de ces mauvais résultats puisse être trouvée. Nous avons donc décidé de développer notre propre algorithme génétique, afin de disposer d’une bibliothèque dont nous connaîtrions parfaitement le code. Les résultats avec cette nouvelle bibliothèque se sont montrés très satisfaisants, et ce code a été adopté pour la suite de nos travaux. Le diagramme UML de cette bibliothèque est présenté Figure 33.





Figure 33. Diagramme UML de la bibliothèque d’algorithmes génétiques.

Les noms de toutes les classes débutent par SA, pour ScreeningAssistant, et GA, pour Genetic Algorithms. La classe SAGAPopulation est la classe principale de la bibliothèque, et permet de contrôler l’évolution de l’algorithme. Elle stocke un tableau de SAGAChromosome, qui représente donc la population à un moment donné. SAGAChromosome stocke quand à elle un tableau de SAGAGene, qui correspond au génotype. Trois classes héritent de la classe abstraite SAGAGene. Ces classes permettent de manipuler des données de type booléen, entier, ou double (réel).

La classe abstraite SAGAFitnessFunction définit une structure générale pour calculer le score d’une solution. Il faudra donc, pour chaque problème, implémenter une classe enfant de SAGAFitnessFunction qui permet de calculer le score pour une solution (c.a.d. un chromosome) du problème donné. Cette classe sera passée au constructeur de SAGAPopulation.

Les classes abstraites SAGASelection et SAGAMating permettent d’implémenter respectivement la sélection des parents, et la reproduction. Pour ces deux étapes, nous avons choisi d’implémenter des méthodes couramment utilisées. Ainsi la sélection des parents se fait par la méthode de la roue de la fortune avec une pondération basée sur les scores, et la reproduction par un crossover deux points.

Nous avons décrit les différents éléments constitutifs de notre algorithme génétique. Il y a cependant un facteur à prendre en compte, et que nous n’avons pas encore abordé : les contraintes sur les solutions. Nous avons pour l’instant comme unique contrainte dans notre système les intervalles qui sont définis pour les valeurs des gènes de types entiers et réels. Certains problèmes vont cependant nécessiter des solutions un peu plus sophistiquées. Supposons que notre algorithme génétique serve à sélectionner des descripteurs pour un modèle QSAR, ou bien des molécules pour la sélection d’un ensemble de composés divers. Le problème pourra être codé en attribuant un identificateur de type entier à chacun des éléments, les descripteurs dans un cas, et les molécules dans l’autre (on aura alors dans le premier cas un modèle QSAR avec un nombre de descripteurs prédéfini). Chacun des éléments ne devra être présent qu’une seule fois dans une même solution, car il est évidemment impensable d’avoir un modèle QSAR utilisant deux fois le même descripteur, ou bien un ensemble de molécules divers dans lequel on retrouve des doublons. Nous voyons donc que notre système doit permettre d’établir des contraintes sur les solutions. Dans nos exemples la contrainte est l’unicité des allèles. Il existe plusieurs manières de gérer ces contraintes. Ainsi JGAP [227] utilise la notion de supergène. Il s’agit d’un gène définissant une contrainte et regroupant tous les gènes concernés par la contrainte. Cette méthode a l’inconvénient de compliquer la structure des données. Nous avons pour notre part implémenté la gestion de la contrainte de manière un peu différente. Cette dernière s’effectue en étendant la classe Chromosome et en redéfinissant la méthode constraintIsRespected. Cette méthode sera appelée après chaque modification de chromosome c’est à dire pendant les étapes d’initialisation, de crossover et de mutation. Si le chromosome généré pendant une étape donnée ne respecte pas la contrainte, une autre tentative est effectuée.

On notera enfin que les performances des algorithmes génétiques peuvent être améliorées significativement par une implémentation parallèle. Dans ce cas ont utilise des sous-populations qui évoluent de manière indépendante, mais en échangeant des individus entre elles occasionnellement. Plusieurs études montrent même une augmentation superlinéaire de la vitesse d’exécution des algorithmes génétiques parallèles. Ces résultats nécessitent quelques précisions. En effet si l’on exécute sur un même processeur tous les processus d’un programme parallèle, le temps d’exécution ne peut pas être inférieur au temps d’exécution de la même tâche par un programme en série. En fait, la superlinéarité de la vitesse d’exécution peut généralement s’expliquer par le fait que les algorithmes génétiques exécutent moins de travail et ont une pression de sélection plus importante [228].

La parallélisation des algorithmes génétiques est donc très intéressante. Même si l’utilisation d’algorithmes génétiques parallèles sort du cadre de ce travail, certaines implémentations ont été réalisées afin de permettre une éventuelle parallélisation. Ainsi les classes SAGAChromosome, SAGAGene et SAGAFitnessFunction implémentent l’interface Serializable, et elles sont donc transmissibles par communication réseau.

2.Recuit Simulé


En nous basant sur les classes définies pour les algorithmes génétiques, nous avons développé un algorithme de recuit simulé (Figure 34).



Figure 34. Diagramme UML de la bibliothèque de recuit simulé.

La classe principale est ici SASASimulatedAnnealing, qui prend en charge le déroulement de l’expérience de recuit simulé. Nous avons conservé la classe SAGAChromosomes pour gérer les solutions. Bien que la notion de chromosomes n’entre pas en jeu dans les algorithmes de recuit simulé, notre classe est bien adaptée pour gérer la solution qui sera optimisée par le recuit simulé. Comme pour les algorithmes génétiques, les solutions pourront être de types entier, booléen ou double, et des contraintes pourront être appliquées. La création d’une expérience de recuit simulé nécessite de définir le schéma de refroidissement (classe abstraite SASACoolingSchedule) et le critère d’acceptation (classe abstraite SASAAcceptanceCriterion). Nous avons implémenté le critère d’acceptation de Metropolis, et un schéma de refroidissement géométrique.

C.La sélection de plaques


Alors que la sélection de composés par diversité a fait l’objet de nombreuses recherches, la sélection de plaques par diversité n’a donné lieu, à notre connaissance, qu’à une seule publication [229]. Dans cette étude, les auteurs proposent une méthode générale utilisant le recuit simulé pour la sélection de groupes de composés. Une application directe de cette méthode est la sélection de plaques.

La sélection de plaques peut être utilisée pour créer ou agrandir une chimiothèque à partir de composés déjà mis en plaques, ou bien encore pour choisir des plaques pour des tests à hauts débits. La taille de l’espace des solutions est :

(Équation 13)

n étant le nombre total de plaques et k le nombre de plaques à sélectionner. Par rapport à une sélection par diversité classique, la sélection de plaques nécessite d’évaluer la diversité qu’apporte un groupe indissociable de composés (ceux de la plaque) à un autre groupe de composés (ceux déjà sélectionnés).

Nous avons utilisé pour cette étude 125 plaques contenant des produits du fournisseur InterBioScreen.

1.Critères de sélection par diversité


Quelque soit l’algorithme utilisé pour la sélection de plaques, il faut définir le type de diversité que l’on souhaite. Afin que notre comparaison ne soit pas dépendante du type de diversité utilisé, nous avons choisi deux types de diversité différents, déjà présentés dans ce manuscrit. Le premier consiste à maximiser le nombre de frameworks. Le deuxième, consiste à maximiser le nombre de clusters obtenus à partir des fingerprints SSKey-3DS avec l’algorithme SCA.

De plus, des filtres basés sur d’autres critères peuvent être utilisés. On peut ainsi privilégier les composés « drug-like » ou encore ceux ayant des propriétés physicochimiques ou des sous-structures voulues.

2.Algorithmes


Nous avons comparé les performances de trois algorithmes différents pour traiter le problème de la sélection de plaques :

  • Classement : cet algorithme classe les plaques en fonction de la diversité qu’elles apportent à la sélection. Au départ la sélection est vide. On cherche la plaque qui a les composés les plus divers. On ajoute cette plaque à la sélection. On cherche ensuite la plaque qui apporte le plus de diversité à la sélection et on l’ajoute. On répète cette dernière étape jusqu’à ce que l’on obtienne le nombre de plaques souhaité. Dans le cas de la diversité par fingerprint on utilise l’algorithme SCA pour évaluer la diversité et dans le cas de la diversité par frameworks on compte le nombre de frameworks.

  • Algorithmes génétiques : nous utiliserons la bibliothèque d’algorithmes génétiques décrite précédemment. Elle utilise la sélection aléatoire avec pondération (roue de la fortune) et le crossover double point. Les deux chromosomes avec les meilleurs scores survivent dans la génération suivante.

  • Recuit simulé : nous utiliserons également la bibliothèque de recuit simulé présentée précédemment, avec un schéma de refroidissement géométrique, et le critère d’acceptation de Metropolis.


3.Résultats


Afin d’étudier l’influence du nombre de composés sélectionnés sur les performances des algorithmes, nous sélectionnerons dans chaque cas 30, 60 et 90 plaques. Les données ont été importées dans une base MySQL en utilisant une version spéciale de ScreeningAssistant, modifiée pour gérer les composés mis en plaques. L’algorithme est directement connecté à la base MySQL.

Le taux de sélection naturelle pour les algorithmes génétiques est de 50 % et le taux de mutation de 5 %. Entre 10 et 20 chromosomes sont utilisés en fonction des cas, et le nombre de générations est de 1500 pour la sélection de 30 plaques, et de 2000 pour les sélections de 60 et 90 plaques.

Pour le recuit simulé, la pseudo-température initiale est fixée à 800 et le nombre de pas à 2500.
a.Frameworks

La comparaison de l’évolution des scores pour les algorithmes d’optimisation mimant un phénomène naturel fait apparaître que, si la qualité des solutions des premières itérations est meilleure pour les algorithmes génétiques, le recuit simulé atteint plus rapidement sa solution optimale (Figure 35).

Algorithmes génétiques

Recuit Simulé





30 plaques

30 plaques





60 plaques

60 plaques





90 plaques

90 plaques

Figure 35. Evolutions du nombre de frameworks pour les algorithmes génétiques (colonne de gauche), et le recuit simulé (colonne de droite) pour des sélections de 30, 60 et 90 plaques.



Figure 36. Comparatifs des trois méthodes utilisées pour la sélection de plaques en optimisant le nombre de frameworks. Les résultats des sélections aléatoires sont également présentés comme références.

Le comparatif des trois algorithmes montre que tous donnent des résultats meilleurs qu’une sélection aléatoire (Figure 36). Cependant les algorithmes basés sur des méthodes d’optimisation naturelles donnent de meilleurs résultats qu’un simple classement. Il n’y a pas de différences notables entre les résultats des algorithmes génétiques et le recuit simulé. Le recuit simulé a cependant deux avantages par rapport aux algorithmes génétiques. Il est d’une part plus simple à paramétrer car les seuls critères à définir sont la température de départ et le nombre de pas. Ces paramètres sont simples à régler. D’autres parts, le nombre de pas nécessaires à la convergence est inférieur pour le recuit simulé.
b.SSKey-3DS

Si compter le nombre de frameworks uniques pour un groupe de composés est rapide, compter le nombre de clusters est plus lent. Le temps d’exécution est donc un paramètre à prendre en compte. Ce dernier est en faveur du recuit simulé. En effet lors de l’exécution de cet algorithme, le nombre de clusters est calculé une fois par pas. En revanche, pour les algorithmes génétiques, le nombre de cluster est calculé plusieurs fois par génération (autant de fois qu’il y a de nouveaux chromosomes à cette génération).

Algorithmes génétiques

Recuit Simulé





30 plaques

30 plaques





60 plaques

60 plaques





90 plaques

90 plaques

Figure 37. Evolutions du nombre de clusters pour les algorithmes génétiques (colonne de gauche), et le recuit simulé (colonne de droite) pour des sélections de 30, 60 et 90 plaques.

Bien qu’ayant des schémas d’évolution différents, les deux méthodes convergent approximativement au même nombre de pas vers leur solution maximale (Figure 37).



Figure 38. Comparatifs des trois méthodes utilisées pour la sélection de plaques en optimisant le nombre de clusters. Les résultats des sélections aléatoires sont également présentés comme références.

Les résultats obtenus en utilisant les SSKey3DS sont très comparables à ceux obtenus avec les frameworks. Les trois méthodes étudiées donnent de meilleurs résultats qu’une sélection aléatoire (Figure 38). Les méthodes d’optimisations basées sur des phénomènes naturels sont celles qui donnent les meilleurs résultats. Il n’y a pas de différences notables entre les résultats des algorithmes génétiques et ceux du recuit simulé.
1   ...   10   11   12   13   14   15   16   17   ...   22

similaire:

Rapporteur, ensc, Montpellier iconDe la franc maconnerie a montpellier
Écrit à son ami Pierre Jacques Astruc, conseiller maître en la cour des comptes, aides et finances de Montpellier

Rapporteur, ensc, Montpellier iconEconomies d’eau : Réutilisation des eaux de pluie
«Eaux» de l’Afssa 15 cnrs- umr 5119-Université Montpellier 2- montpellier 16 ehesp- rennes 17 Laboratoire de Santé publique et Environnement-Faculté...

Rapporteur, ensc, Montpellier iconÉconomies d’eau : Réutilisation des eaux de pluie
«Eaux» de l’Afssa 15 cnrs- umr 5119-Université Montpellier 2- montpellier 16 ehesp- rennes 17 Laboratoire de Santé publique et Environnement-Faculté...

Rapporteur, ensc, Montpellier iconRapporteur

Rapporteur, ensc, Montpellier iconRapporteur : Saddek Aouadi, Professeur, Université d’Annaba

Rapporteur, ensc, Montpellier iconRapporteur trigonométrique circulaire pour série générale et technologique...

Rapporteur, ensc, Montpellier iconCmi montpellier informatique

Rapporteur, ensc, Montpellier iconSociete regionale de medecine et d’hygiene du travail de montpellier

Rapporteur, ensc, Montpellier iconRapporteur : Philippe Cléris Le Grand Paris et l’Eure. Ou un début...

Rapporteur, ensc, Montpellier iconL ycee agricole prive
«blanco», équerre, compas, rapporteur, taille-crayon, crayon à papier, double décimètre, stylos noir, bleu, vert, rouge et crayons...








Tous droits réservés. Copyright © 2016
contacts
c.21-bal.com