Je ne présenterai pas les principes détaillés et les définitions spécifiques des algorithmes génétiques ici. Si vous voulez savoir, vous pouvez utiliser Baidu pour l'apprendre. Ici, je présenterai brièvement votre compréhension des algorithmes génétiques. Cet article utilise des règles binaires pour le codage des gènes.
Idées d'algorithmes:
L'algorithme génétique fait référence à la théorie de l'évolution de Darwin et estime que les espèces se développent dans une direction positive (survie des plus en forme), il peut donc être considéré qu'après une algèbre suffisante, la valeur maximale obtenue est très proche de la valeur maximale réelle.
Étapes d'algorithme:
Algorithme Implémentation-Gene partie
1. Population individuelle (ici considérée comme chromosomes), chez les individus, nous ajoutons deux attributs à cet individu, la forme physique (valeur de la fonction) correspondant au gène et au gène de l'individu.
classe publique chromosome {gène booléen privé []; // séquence de gènes score double privé; // score de fonction correspondant} 2. Générez des séquences de gènes au hasard. Que chaque position du gène soit 0 ou 1, c'est un moyen complètement aléatoire de l'atteindre.
Chromosome public (int size) {if (size <= 0) {return; } initgeneceSize (taille); pour (int i = 0; i <size; i ++) {gène [i] = math.random ()> = 0,5; }} private void initgeneSize (int size) {if (size <= 0) {return; } gène = new boolean [taille]; } 3. Convertir le gène en valeur correspondante, par exemple, le nombre correspondant à 101 est 5, et les opérations de bits sont utilisées ici pour l'implémenter.
public int getnum () {if (gène == null) {return 0; } int num = 0; for (boolean bool: gène) {num << = 1; if (bool) {num + = 1; }} return num; } 4. Si une mutation du gène se produit, l'emplacement de la mutation est complètement mis en œuvre de manière aléatoire. Le principe de mutation est de passer de 1 à 0 et 0 à 1.
Mutation publique void (int num) {// Autoriser la mutation int size = gène.length; pour (int i = 0; i <num; i ++) {// recherchez l'emplacement de mutation int à = ((int) (math.random () * taille))% taille; // la valeur après mutation boolean bool =! Gène [at]; gène [at] = bool; }} 5. Les gènes de clonage sont utilisés pour produire la prochaine génération. Cette étape consiste à copier les gènes existants.
Clone chromosome statique public (chromosome final c) {if (c == null || c.gene == null) {return null; } Chromosome copie = nouveau chromosome (); copy.InitGenenesize (C.Gene.Length); for (int i = 0; i <c.gene.length; i ++) {copy.gene [i] = c.gene [i]; } return copy; } 6. Les deux parents produisent la prochaine génération, et ici deux individus produisent deux descendants individuels. Quel gène spécifique est différent de l'élève, est complètement aléatoire.
LISTE STATIQUE PUBLIQUE <CHROMOSOME> GÉNÉTIQUE (Chromosome P1, chromosome P2) {if (p1 == NULL || P2 == NULL) {// Il y a l'un des chromosomes qui est vide et ne produit pas la prochaine génération Null; } if (p1.gene == null || p2.Gene == null) {// Il y a l'un des chromosomes qui n'a pas de séquence de gène et ne produit pas le retour null de prochaine génération; } if (p1.gene.length! = p2.Gene.length) {// La longueur de la séquence du gène chromosome ne produit pas la prochaine génération de retour nul; } Chromosome c1 = clone (p1); Chromosome c2 = clone (p2); // Créer des positions de bilan croisé au hasard Int size = c1.gene.length; int a = ((int) (math.random () * taille))% taille; int b = ((int) (math.random () * taille))% taille; int min = a> b? B: A; int max = a> b? R: B; // gènes CROMEX en positions pour (int i = min; i <= max; i ++) {booléen t = c1.gene [i]; c1.gene [i] = c2.Gene [i]; C2.Gene [i] = T; } List <chromosome> list = new ArrayList <bromosome> (); list.add (c1); list.add (c2); Liste de retour; } Algorithme Implémentation GÉNÉTIQUE Algorithme
1. Pour les algorithmes génétiques, nous devons avoir des populations correspondantes et certaines constantes que nous devons définir: numéro de population, longueur du gène, nombre de mutations génétiques, taux de mutation du gène, etc. Pour plus de détails, veuillez vous référer au code suivant:
classe abstraite de la classe génétique Geneticalgorithme {Liste privée <Hromosome> Population = New ArrayList <bromosome> (); // Population private int popsize = 100; // nombre de populations private int genesesize; // maximum longueur private int maxiternum = 500; // maximum iteation double mutationrate = 0,01; // Probabilité de la mutation génétique privée int maxmutnenu = 3; longueur asynchrone private int Generation = 1; // Combien de générations sont actuellement héritées? BestScore; // Best Score Private Double PireScore; // le pire score privé Double TotalScore; // Score total Private Double AveragesCore; // Score moyen Private Double X; // enregistrer la meilleure valeur x dans la population historique double y; // Enregistrez la meilleure valeur y dans la population historique int private genei; // algèbre où xy est situé} 2. Initialiser la population. Au début de l'algorithme génétique, nous devons initialiser une population originale, qui est la première génération d'origine.
private void init () {for (int i = 0; i <PopSize; i ++) {Population = new ArrayList <bromosome> (); Chromosome chro = nouveau chromosome (GeneSize); population.add (chro); } cacultescore (); } 3. Une fois la population initiale, nous devons calculer la forme physique de la population, ainsi que la meilleure forme physique, pire forme physique et forme physique moyenne, etc.
Vide privé cacultescore () {setchromosomescore (population.get (0)); BestScore = Population.get (0) .getScore (); PiRSCORE = POPOPOSION.GET (0) .getScore (); totalScore = 0; pour (chromosome chro: population) {setchromosomescore (chro); if (chro.getScore ()> bestScore) {// Définissez la meilleure valeur de gène BestScore = chro.getScore (); if (y <bestscore) {x = changex (chro); y = bestscore; Genei = génération; }} if (chro.getScore () <pireScore) {// Définissez la pire valeur de gène pireScore = chro.getScore (); } totalCore + = chro.getScore (); } AVERAGESCORE = TOTALSCORE / POPSIZE; // La valeur moyenne causée par les problèmes de précision est supérieure à la meilleure valeur, définissez la valeur moyenne sur la meilleure valeur AveragesCore = AveragesCore> BestScore? BestScore: AveragesCore; } 4. Lors du calcul de la forme physique individuelle, nous devons calculer la valeur Y correspondante en fonction du gène. Ici, nous définissons deux méthodes abstraites pour implémenter l'implémentation spécifique par l'implémentation de la classe.
private void setChromosomescore (chromosome chro) {if (chro == null) {return; } double x = changex (chro); double y = caculatey (x); chro.setscore (y); } / ** * @param chro * @return * @Description: Converti Binary en X * / public abstract double Changex (chromosome chro); / ** * @param x * @return * @description: calculer la valeur y basée sur x y = f (x) * / public abstrait double caculatey (double x); 5. Après avoir calculé la forme physique de la population, nous devons utiliser la méthode de jeu de platine pour sélectionner des individus qui peuvent produire la prochaine génération. Il y a une condition ici que si la forme physique de l'individu n'est pas inférieure à la forme physique moyenne, la prochaine génération naîtra (la plus apte survive).
chromosome privé getparentChromosome () {double tranche = math.random () * totalCore; double somme = 0; pour (chromosome chro: population) {sum + = chro.getScore (); // Accédez à la position correspondante et la forme physique n'est pas inférieure à la fitness moyen if (sum> Slice && chro.getScore ()> = AveragesCore) {return chro; }} return null; } 6. Après avoir sélectionné des individus qui peuvent produire la prochaine génération, vous devez vous accoupler pour produire la prochaine génération.
private void evolve () {list <chromosome> childpopulation = new ArrayList <bromosome> (); // générer la population de prochaine génération while (childpopulation.size () <popsize) {chromosome p1 = getparentChromosome (); Chromosome p2 = getparentChromosome (); List <chromosome> enfants = chromosome.genetic (p1, p2); if (enfants! = null) {for (chromosome chro: enfants) {childpopulation.add (chro); }}} // Remplacez la population ancienne par une nouvelle liste de population <chromosome> t = population; Population = Population d'enfants; T.Clear (); t = null; // mutation de mutation génique (); // calculer la forme physique de la nouvelle population cacultescore (); } 7. Des mutations génétiques peuvent se produire pendant le processus de production de la prochaine génération.
Mutation vide privée () {pour (chromosome chro: population) {if (math.random () <mutationrate) {// La mutation du gène se produit int mutationNum = (int) (math.random () * maxmutationNum); chro.mutation (mutationNum); }}} 8. Répétez les étapes ci-dessus une par une.
public void caculte () {// initialiser la génération de population = 1; init (); while (génération <maxiternum) {// Évolution génétique populaire (); imprimer(); génération ++; }}Écrire des classes d'implémentation
Étant donné que la classe de l'algorithme génétique ci-dessus est une classe abstraite, nous devons écrire une classe d'implémentation pour un cas spécifique, en supposant que nous calculons la valeur maximale de y = 100 log (x) sur [6 106].
1. Nous supposons que la longueur du gène est 24 (la longueur du gène est déterminée par la longueur effective du résultat requise), donc le maximum binaire correspondant est 1 << 24. Nous faisons les paramètres suivants
classe publique GeneticalGorithMtest étend GeneticalGorithm {public static final int num = 1 << 24; public geneticalgorithmtest () {super (24); }} 2. Implémentez la méthode abstraite de la valeur x
@Override public Double Changex (chromosome chro) {// TODO Méthode générée automatique Stub return ((1.0 * chro.getnum () / num) * 100) + 6; } 3. Implémentez la méthode abstraite de Y
@Override public Double Caculatey (Double X) {// TODO Méthode générée automatique Stume RETOUR 100 - MATH.LOG (X); }Résultats en cours d'exécution
Penser aux algorithmes génétiques
J'ai lu beaucoup de présentations aux algorithmes génétiques. Les solutions optimales mentionnées ci-dessus sont les plus valeurs de la dernière génération. J'ai une question. Pourquoi est-ce que je sais que le plus de valeurs parmi toutes les bandes ci-dessus, c'est-à-dire les valeurs XY dans le programme, pourquoi ne puis-je pas utiliser les valeurs XY comme valeur de résultat finale de l'algorithme génétique?
Code complet
1. Classe chromosomique
/ ** * @ Description: chromosome génétique * / package com.lulei.genetic.algorithm; import java.util.arraylist; Importer java.util.list; classe publique Chromosome {gène booléen privé []; // séquence de gènes score double privé; // score de fonction correspondant public double getScore () {return score; } public void setScore (double score) {this.score = score; } / ** * @param Taille * Séquence de gènes générée aléatoire * / chromosome public (int size) {if (size <= 0) {return; } initgeneceSize (taille); pour (int i = 0; i <size; i ++) {gène [i] = math.random ()> = 0,5; }} / ** * générer un nouveau gène * / public chromosome () {} / ** * @param c * @return * @description: Gene de clonage * / Clone chromosome statique public (Null Null) {If (c == Null || c.Gene == NULL) {retour null; } Chromosome copie = nouveau chromosome (); copy.InitGenenesize (C.Gene.Length); for (int i = 0; i <c.gene.length; i ++) {copy.gene [i] = c.gene [i]; } return copy; } / ** * @param size * @description: initialiser la longueur du gène * / private void initgeneSize (int size) {if (size <= 0) {return; } gène = new boolean [taille]; } / ** * @param c1 * @param c2 * @description: génération génétique pour produire la prochaine génération * / Liste statique publique <gromosome> génétique (chromosome p1, chromosome p2) {if (p1 == null || p2 == null) {// il existe un des chromosomes qui est vide, et ne produit pas la génération suivante; } if (p1.gene == null || p2.Gene == null) {// Il y a l'un des chromosomes qui n'a pas de séquence de gène, et ne produit pas le retour null de prochaine génération; } if (p1.gene.length! = p2.Gene.length) {// La longueur de la séquence du gène chromosome ne produit pas la prochaine génération de retour nul; } Chromosome c1 = clone (p1); Chromosome c2 = clone (p2); // Créer des positions de bilan croisé au hasard Int size = c1.gene.length; int a = ((int) (math.random () * taille))% taille; int b = ((int) (math.random () * taille))% taille; int min = a> b? B: A; int max = a> b? R: B; // gènes CROMEX en positions pour (int i = min; i <= max; i ++) {booléen t = c1.gene [i]; c1.gene [i] = c2.Gene [i]; C2.Gene [i] = T; } List <chromosome> list = new ArrayList <bromosome> (); list.add (c1); list.add (c2); Liste de retour; } / ** * @param num * @description: la variation se produit dans les positions num du gène num * / public void mutation (int num) {// permettre la mutation int size = gène.length; pour (int i = 0; i <num; i ++) {// Rechercher la position de mutation int at = (int) (math.random () * taille))% taille; // la valeur après mutation boolean bool =! Gène [at]; gène [at] = bool; }} / ** * @return * @Description: Convertir les gènes en nombres correspondants * / public int getnum () {if (gène == null) {return 0; } int num = 0; for (boolean bool: gène) {num << = 1; if (bool) {num + = 1; }} return num; }} 2. Classe de Geneticalgorithme
/ ** * @ Description: * / package com.lulei.genetic.algorithm; import java.util.arraylist; Importer java.util.list; classe abstraite publique GeneticalGorithm {List privé <Chromosome> Population = new ArrayList <bromosome> (); private int popsize = 100; // nombre populaire private int genesesize; // maximum gène longueur private int maxiternum = 500; // nombre maximum de itérations private double mutationrate = 0,01; // probabilité de gène mutation private int maxmutationnum = 3; // maximum variant asynchronous landle private generation = 1; // combien de générations sont actuellement dans la variante? Double BestScore privé; // meilleur score privé Double PireScore; // le pire score privé double totalcore; // score total Double privé AveragesCore; // score moyen Private Double X; // enregistrer la meilleure valeur x dans la population historique double y; // Enregistrez la meilleure valeur y dans la population historique int private genei; // algèbre où xy est situé public génétique Geneticalgorithme (int genesize) {this.geneSize = geneSize; } public void caculte () {// initialiser la génération de population = 1; init (); while (génération <maxiternum) {// Évolution génétique populaire (); imprimer(); génération ++; }} / ** * @description: résultat de sortie * / private void print () { System.out.println("--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- System.out.println ("La pire fitness est:" + PireSCore); @Description: Initialise Population * / private void init () {pour (int i = 0; i <PopSize; i ++) {Population = New ArrayList <fromosome> (); void Evolve () {list <chromosome> childpopulation = new ArrayList <fromosome> (); P2); If (Enfants! @Return * @Description: la méthode de la roulette sélectionne les chromosomes qui peuvent hériter de la prochaine génération * / chromosome privé getparentChromosome () {Double Slice = Math.Random () * TotalsCore; {return chro;}} return null;} / ** * @description: Calculer la fitness de la population * / Priva SetChromosoMescore (chro); Chro.getScore ();} TotalScore + = chro.getScore ();} AveragesCore = TotalsCore / PopSize; (Chromosome chro: population) {if (math.random () <mutationrate) {// La mutation du gène se produit int mutationNum = (int) (math.random () * maxmutationNum); SetChromosoMescore (chromosome chro) {if (chro == null) {return;} double x = changex (chro); @param x * @return * @Description: Calculer la valeur basée sur x y = f (x) * / public abstrait double caculatey (Double X); Population publique SetPopulation (List <Chromosome> = GeneSize;} public Void SetMaxiternum (int maxiternum) {this.Maxiternum = maxiternum; GetBestScore () {return BestScore;} public Double GetWorksCore () {RETOUR 3. Classe génétique de la santé
/ ** * @ Description: * / package com.lulei.genetic.algorithm; classe publique GeneticalGorithMtest étend GeneticalGorithm {public static final int num = 1 << 24; public geneticalgorithmtest () {super (24); } @Override public Double Changex (chromosome chro) {// TODO Méthode générée automatique Stub return ((1.0 * chro.getnum () / num) * 100) + 6; } @Override public Double Caculatey (Double X) {// TODO Méthode générée automatique Stub Retour 100 - Math.log (x); } public static void main (String [] args) {geneticalgorithmtest test = new GeneticalGorithMtest (); test.caculte (); }}Ce qui précède est une introduction détaillée à l'algorithme génétique Java. J'espère qu'il sera utile à tout le monde d'apprendre l'algorithme génétique Java.