Upload
josee-bruneau
View
104
Download
0
Embed Size (px)
Citation preview
Par Soumaya Chaffar, Alicia Heraz, Roxane Kouassi, Janice Ng Ka-Yee, Yannick Solari
Université de Montréal ~ Faculté Arts & sciences ~ Département Informatique & Recherche opérationnelle
IFT6251 Sujets en génie logiciel ~ 15 décembre 2004 ~ Professeur Houari SAHRAOUI
Genetic ALgorithm Optimized for Portability and Parallelism System
Genetic Algorithms Research and Applications Group
Migration de GALOPPS du C vers JAVA (Phase
2)
Migration de GALOPPS du C vers JAVA (Phase 2) Page 2 / 30
Plan de la présentation
• Répartition des classes• Divergences entre C et JAVA• Implémentation sous JAVA• Intégration des classes• Difficultés rencontrées• Parties non réalisées • Parties réalisées• Déboguage et Tests avec JUnit• Diagrammes initial et final de classes• Interface GALOPPS• Conclusion
S
Migration de GALOPPS du C vers JAVA (Phase 2) Page 3 / 30
Répartitions des Classes 1/7
• Selon l’affectation initiale des fichiers dans la phase 1Chaque membre a été chargé d’implémenter les classes qu’il avait identifié à l’étape précédente du projet
• Priorité d’implémentationLes classes les plus fréquemment utilisées sont les premières à être implémentées : RandomExt, Parameters, Chromosome et Population.Les classes qui viennent en seconde position sont celles qui représentent les fonctionnalités de GALOPPS
• Les classes traitant du parallélisme Mise à part la classe Migration, les classes traitant du parallélisme n’ont pas été implémentée
S
Migration de GALOPPS du C vers JAVA (Phase 2) Page 4 / 30
Répartitions des Classes 2/7[Soumaya Chaffar]
• InversionAppliquée sur Chromosome, elle permet d’inverser ses champs.Elle implémente les méthodes d’inversion.
• InputBufferReprésente le tampon d’entrée, elle implémente la fonction ffscanf qui permet de déterminer le type inclut dans une chaîne de caractère.
• APPRelative à l’application réalisée pour manipuler l’api GALOPPS. Elle implémente la fonction objective.
• InterfacePermet d’afficher certains attributs de la classe Parameters, de les modifier et de la mis à jour. C’est l’aspect visuel de notre application.
S
Migration de GALOPPS du C vers JAVA (Phase 2) Page 5 / 30
Répartitions des Classes 3/7[Alicia Heraz]
• PopulationImplémente les méthodes appliquées sur une population
• Population_VBReprésente l’ensemble des chromosomes VB
• Population_PBReprésente l’ensemble des chromosomes PB
• MigrationImplémente les méthodes permettant de migrer un chromosome d’une population à une autre. Les méthodes de cette classe ne peuvent être exécutées que dans le mode parallèle
A
Migration de GALOPPS du C vers JAVA (Phase 2) Page 6 / 30
Répartitions des Classes 4/7[Roxane Kouassi]
• ChromosomeC’est un individu de population, il existe sous deux types
• Chromosome_VBReprésente un chromosome basé sur la valeur
• Chromosome_PBReprésente un chromosome basé sur les permutations
• CrossoverImplémente l’opération de croisement. Cette classe est mère de chacune des deux sous-classes : Crossover_VB et Crossover_PB.
• RandomExtImplémente des opérations sur les nombre aléatoires
R
Migration de GALOPPS du C vers JAVA (Phase 2) Page 7 / 30
Répartitions des Classes 5/7[Janice Ka-Yee NG 1/2]
• SelectionElle implémente des méthodes de sélection de chromosomes lors de la génération d'une population.
Elle est la classe mère des 5 classes suivantes : RankedBasedSelection, RouletteWheelSelection, StochasticUniversalSelection, StochasticRemainderSelection et TournamentSelection.
• StatisticsElle est utile pour déterminer des propriétés relatives au fitness des chromosomes d'une population, telles que leurs valeurs minimum, maximum et moyenne.
J
Migration de GALOPPS du C vers JAVA (Phase 2) Page 8 / 30
Répartitions des Classes 6/7[Janice Ka-Yee NG 2/2]
• InitializationUtilisée pour initialiser des variables dont les valeurs sont précisées dans un fichier, telles que la taille de la population popsize, pcross, permproblem, chromsize, taille des structure de données (tableaux).
• OneStartElle est la classe principale de démarrage, contenant entre autres l'application développée par l'usager.
• ScaleCalcule la valeur calibrée (scaled) relative aux fitnesses des chromosomes d'une population.Elle est la classe mère des 4 types de scale suivants: WindowScale, SigmaTruncation, LinearScale et BoltzmannScale.
J
Migration de GALOPPS du C vers JAVA (Phase 2) Page 9 / 30
Répartitions des Classes 7/7[Yannick Solari]
• ParametersContient les attributs statiques et les méthodes de lecture des paramètres d’entrée
• MutationImplémente les méthodes de mutation de chromosome, c’est la classe mère de chacune de :
• Mutation_VBManipule les chromosome de type value_based
• Mutation_PBManipule les chromosomes de type permutation_based
Y
Migration de GALOPPS du C vers JAVA (Phase 2) Page 10 / 30
Divergences entre C et JAVA
• Il n’y a pas de pointeurs en JAVA• La gestion de mémoire transparente en JAVA• Les structures et les types définis (typedef) en C
deviennent des objets en JAVA• L’encapsulation des données, l’héritage et le
polymorphisme fournis par le langage JAVA, facilitent la programmation
• Le langage C est un langage faiblement typé• Le langage JAVA est beaucoup moins rapide que C, il
perd en rapidité ce qu'il gagne en portabilité...
Y
Migration de GALOPPS du C vers JAVA (Phase 2) Page 11 / 30
Implémentation sous JAVA 1/8[Soumaya Chaffar]
• Inversion– Elle implémente deux méthodes d’inversion InverCir et
InverCla.– Implémentation en C
• Deux fichiers séparés qui implémentent la fonctionnalité d’inversion.Void Inversion (int *map)– Nouvelle implementation en java
• Création de la classe InversionInversionCir( int [] map, Population oldpop )InversionCla( int [] map, Population oldpop )
• APPIl n’y a pas eu de changements majeurs lors de la migration du code de C vers JAVA, juste au niveau des pointeurs et d’allocation mémoire.
S
Migration de GALOPPS du C vers JAVA (Phase 2) Page 12 / 30
Implémentation sous JAVA 2/8[Soumaya Chaffar]
• InputBuffer– Elle implémente la méthode ffscanf– Changements majeurs, puisque cette classe contient
beaucoup de manipulation sur les chaînes de caractères. Il fallait trouver l’équivalence de chacune dans l’API de Java.
• InterfaceImplémentation direct en Java, pas d’équivalent dans le code C.
S
Migration de GALOPPS du C vers JAVA (Phase 2) Page 13 / 30
Implémentation sous JAVA 3/8[Alicia Heraz]
• Population, Population_VB et Population_PBCes fonctions n’avaient pas de paramètres, lorsqu’elles étaient implémentées en C
- void generate(Inversion i, Selection s, Mutation m, Crossover c)
- void usualgen(Inversion i, Selection s, Mutation m, Crossover c)
• MigrationCertains types de paramètres ont été changé
- boolean GetMigrants(Chromosome IndArray, int donorpop, char []filename, int number_to_migrate, boolean want_best, int migration_incest_reduction, int migration_crowding_amount)
A
Migration de GALOPPS du C vers JAVA (Phase 2) Page 14 / 30
Implémentation sous JAVA 4/8[Roxane Kouassi 1/2]
• Chromosome, Chromosome_VB, Chromosome_PB– un chromosome n’est plus une simple structure mais un objet
qui encapsule ses attributs et ses méthodes.– Un tableau d’entiers pour représenter le contenu d’un
chromosome : des bits.– Les bits sont regroupés ensemble pour former les champs d’un
chromosome.– Problématique: la manipulation des bits, la taille d’un entier, la
longueur d’un champ, …
• RandomExt Elle dérive de la classe Random, définie dans le paquetage java.util de l’API JAVA.
R
Migration de GALOPPS du C vers JAVA (Phase 2) Page 15 / 30
Implémentation sous JAVA 5/8
• Crossover, Crossover_VB, Crossover_PBUne opération de croisement est représentée par une classe car il y a plusieurs méthodes de croisement, qui s’appliquent à différents types de chromosomes.– Implémentation en C
crossover(parent1, parent2, child1, child2, jcross);
– Nouvelle implémentation en JAVA
Crossover c = new Crossover_PB();
c.setParent1(parent1);
c.setParent2(parent2);
c.crossover(child1, child2, jcross);
[Roxane Kouassi 2/2]
R
Migration de GALOPPS du C vers JAVA (Phase 2) Page 16 / 30
Implémentation sous JAVA 6/8[Janice Ka-Yee NG 1/2]
• SelectionNe dépend plus du fichier inclus lors de la compilation tel qu’il est en C, mais dépend plutôt de l’instance de l’objet Sélection au moment de l’exécution.
• InitializationLa méthode initialize se charge de l’initialisation de toutes les variables paramètres possiblement lues à partir d’un fichier. À cette étape, on remarque que les allocations de mémoire en C sont transformées principalement en l’initialisation de tableaux en Java.
Cette classe fait appel à deux fonctions utilitaires du fichier
Report.c, pouvant permettre l’affichage des données relatives à une population et ses chromosomes.
J
Migration de GALOPPS du C vers JAVA (Phase 2) Page 17 / 30
Implémentation sous JAVA 7/8
• OneStartContient le main du programme.
Appelle principalement les méthodes d’initialisation pour construire la base du programme et ensuite les différentes méthodes à propos de la génération d’une nouvelle population.
• ScaleLe type de scaling effectué dépend de l’instance de l’objet Scale créé.
• Statistics Le calcul des statistiques n’a pas impliqué un changement majeur entre les deux versions du programme
[Janice Ka-Yee NG 2/2]
J
Migration de GALOPPS du C vers JAVA (Phase 2) Page 18 / 30
Implémentation sous JAVA 8/8[Yannick Solari]
• ParametersLa classe de paramètres possède plusieurs fonctions pour lire différents groupe de paramètres. Les fonctions du fichier FFSCANF.C sous beaucoup utilisées par la classe Parameters.- Beaucoup de manipulation de String- Utilisation de pointeurs
• MutationUne opération de mutation est représentée par une classe car il y a plusieurs types de mutation, qui s’appliquent à différents types de chromosomes.– Mutation_VB– Mutation_PB
Y
Migration de GALOPPS du C vers JAVA (Phase 2) Page 19 / 30
Intégration des classes
• Les classes les plus importantes étaient utilisées et mises à jour par chaque membre de l’équipe.
• Chaque groupe de classes devaient être correctement compilé avant d’être rajouté aux autres groupes.
• Finalement les classes ont été intégrées manuellement :– Conflits dans les noms et la visibilité des attributs et des
paramètres. – Variables non initialisées.– Déboguage
Y
Migration de GALOPPS du C vers JAVA (Phase 2) Page 20 / 30
Difficultés rencontrées
• Emplacement, portée et pertinence des attributs Selon le champ et la fréquence d’utilisation des attributs, nous avons modifié la portée et l’emplacement de certains. D’autres ont été carrément supprimés car ils n’étaient plus utilisés
• Gestion de la mémoire Les méthodes liées à la gestion de la mémoire ont été supprimées et le code a été réadapté
• Redéfinition des types d’attributA cause de l’absence de certains types (comme les pointeurs), nous avons du redéfinir certains.
• Intégration des implémentations individuellesAttributs redéclarés, classes se référant à un module versus à plusieurs modules
Y
Migration de GALOPPS du C vers JAVA (Phase 2) Page 21 / 30
Parties non réalisées
Faute de temps, les fonctionnalités suivantes n'ont pas été réalisées :
• Les utilitaires restart et checkpointLes modules qui gèrent les fichiers qui sauvegardent les résultats intermédiaires n'ont pas été repris comme CheckHDR.c et CheckRD.c et CheckWT.c
• Les applications scénario APP*.cUne seule application scénario a été implémentée
• ParallélismeMise à part la classe Migration, nous n’avions pas pu implémenter toutes les fonctionnalités du mode parallèle
R
Migration de GALOPPS du C vers JAVA (Phase 2) Page 22 / 30
Parties réalisées
Chromosome
Sélection
PopulationPopulation
Mutation Croisement
Inversion
Migration
R
Migration de GALOPPS du C vers JAVA (Phase 2) Page 23 / 30
Déboguage et Tests
• L’outil JUnit a été utilisé pour développer des tests unitaires sur la classe Chromosome. La majorité des méthodes de cette classe (sauf les get() et les set()) ont été testées.
• En plus de l’outil JUnit, l’outil de déboguage fourni par Eclipse, nous a été d’une grande aide pour détecter les erreurs déclenchées lors de l’exécution de notre code intégré.
A
Migration de GALOPPS du C vers JAVA (Phase 2) Page 24 / 30
public void testChromosome() {
assertEquals(" numfields ", 4, c.getNumFields());
assertEquals(" tabInts.length ", 1, (c.getTabInts()).length);
assertEquals(" fields_ends.length ", 4, (c.getFieldsEnds()).length);
}
Exemple de Test avec JUnitA
l’équivalence entre les paramètres calculés par la fonction
qui exécute le calcul et les valeurs attendues
Migration de GALOPPS du C vers JAVA (Phase 2) Page 25 / 30
Crossover_VB
Crossover_PB
Chromosome_VB
Population_VB
Chromosome_PB
Population_PB
CheckPointHeader FileStats UtilityFileRestart Memory
FileManager
InputBuffer
Inversion
OneStart
Random
ManyStart
Initialization
CheckPointHeader
Migration
File
1..n
1
1..n
10..n
1..n
0..n
1..n
Field1..n0..n 1..n0..n
Chromosome
1..n 0..n1..n 0..n0..n
1..n0..n
1..n
Start
1..n
1
1..n
1
1..n
1
1..n
1
AlgoParametersParallelParameter
ChromParameter10..n
10..n
ParameterReader
0..1
0..*
0..1
0..*
LinearScale
WindowScale
SigmaTruncation
BoltzmannScale RankBasedSelection
RouletteWheelSelection
StochasticRemainderSelection
StochasticUniversalSeletion
TournamentSelectionParallel_Initialization
Scale
Crossover
Parallel_Population
10..n10..n
Single_Initialization
Statistics
1..*11..*1
SelectionPopulation
1
0..n
1
0..n
1
0..n
1
0..n
1..n0..n 1..n0..n11..*11..*
Diagramme initial de classesJ
Migration de GALOPPS du C vers JAVA (Phase 2) Page 26 / 30
Diagramme final de classesJ
AboutDialog
BoltzmannScale
Chromosome_PB
Chromosome_VB
Crossover_PBCrossover_VB
InputBuffer
Interface
LinearScale
Mutation_PBMutation_VB
APP
Param
Population_PB
Population_VB
QuitDialog
RandomExt
RankBasedSelection
Result
RouletteWheelSelection
SigmaTruncationStochasticRemainderSelection
StochasticUniversalSelection
TournamentSelection
Utilities
WindowScale
Crossover Inversion
Mutation
Scale Statistics
Selection
Migration
OneStart
$app
Population
Chromosome
Initialization
Parameters
Migration de GALOPPS du C vers JAVA (Phase 2) Page 27 / 30
Interface de l’API réaliséeS
Migration de GALOPPS du C vers JAVA (Phase 2) Page 28 / 30
Conclusion
• Les divergences entre C et JAVA ont été résolues • Les parties qui traitent du parallélisme, de la sauvegarde
des calculs intermédiaires et certaines des applications scénario n’ont pas été réalisées. L'interface n'a pas pu être integrée à la classe principale
• Le diagramme intégral a été revu et corrigé, il a été généré grâce à l’outil de Reverse Engineering via l’environnement Rational Rose
• Nous espérons qu’une brillante équipe continuera notre travail et finalisera la migration de GALOPPS sous JAVA
A
Migration de GALOPPS du C vers JAVA (Phase 2) Page 29 / 30
Références
• Java Tête la première de Kathy Sierra, Bert Bates, Marie-Cécile Baland. Éditions O’REILLY
• Les Cahiers du programmeur : Java (2), conception et déploiement J2EE de Jérôme Molière
• Les Cahiers du programmeur (1 livre + 1 CD-Rom) : Java 1.4 et 5.0 de Emmanuel Puybaret
• Programmer en Java (1Cédérom) de Claude Delannoy• http://java.sun.com• http://javasoft.com• http://www.commentcamarche.net
A
Par Soumaya Chaffar, Alicia Heraz, Roxane Kouassi, Janice Ng Ka-Yee, Yannick Solari
Université de Montréal ~ Faculté Arts & sciences ~ Département Informatique & Recherche opérationnelle
IFT6251 Sujets en génie logiciel ~ 15 décembre 2004 ~ Professeur Houari SAHRAOUI
Genetic ALgorithm Optimized for Portability and Parallelism System
Genetic Algorithms Research and Applications Group
Migration de GALOPPS du C vers JAVA (Phase
2)