Ich werde hier nicht die detaillierten Prinzipien und spezifischen Definitionen genetischer Algorithmen einführen. Wenn Sie wissen möchten, können Sie Baidu verwenden, um es zu lernen. Hier werde ich kurz Ihr Verständnis von genetischen Algorithmen vorstellen. Dieser Artikel verwendet binäre Regeln für die Gen -Codierung.
Algorithmus -Ideen:
Der genetische Algorithmus bezieht sich auf Darwins Evolutionstheorie und ist der Ansicht, dass sich Arten in einer positiven Richtung entwickeln (Überleben der Stärksten), sodass nach ausreichender Algebra der erhaltene Maximalwert sehr nahe am tatsächlichen Maximalwert liegt.
Algorithmus Schritte:
Algorithmus-Implementierung-Gen-Teil
1. Individuelle Bevölkerung (hier als Chromosomen betrachtet) addieren wir bei Individuen zwei Attribute zu diesem Individuum, dem Fitness (Funktionswert), der dem Gen und Gen des Individuums entspricht.
öffentliche Klasse Chromosom {private boolean [] Gen; // Gensequenz Private Double Score; // entsprechende Funktionsbewertung} 2. Erzeugen Sie die Gensequenzen zufällig. Unabhängig davon, ob jede Position des Gens 0 oder 1 ist, ist dies ein völlig zufälliger Weg, um es zu erreichen.
public Chromosom (int Größe) {if (Größe <= 0) {return; } initgenesize (Größe); für (int i = 0; i <size; i ++) {Gene [i] = math.random ()> = 0,5; }} private void initgenesize (int size) {if (Größe <= 0) {return; } Gene = neuer Boolescher [Größe]; } 3.. Umwandeln Sie das Gen in den entsprechenden Wert, beispielsweise ist die Zahl, die 101 entspricht, 5, und hier werden Bit -Operationen zur Implementierung verwendet.
public int getnum () {if (gene == null) {return 0; } int num = 0; für (boolean bool: Gene) {num << = 1; if (bool) {num += 1; }} return num; } 4. Wenn eine Genmutation auftritt, wird der Ort der Mutation zufällig vollständig implementiert. Das Mutationsprinzip besteht darin, sich von 1 und 0 und 0 bis 1 zu ändern.
public void mutation (int num) {// Mutation int size = Gen.Length; für (int i = 0; i <num; i ++) {// Suchen Sie nach Mutationsposition int at = ((int) (math.random () * Größe) % Größe; // Der Wert nach Mutation boolean bool =! Gen [at]; Gene [at] = bool; }} 5. Klonengene werden verwendet, um die nächste Generation zu erzeugen. Dieser Schritt besteht darin, die vorhandenen Gene zu kopieren.
öffentliches statisches Chromosomenklon (endgültiges Chromosom C) {if (c == null || c.gen == null) {return null; } Chromosom copy = new Chromosome (); Copy.initgenesize (C.gene.length); für (int i = 0; i <c.gen.length; i ++) {Copy.gene [i] = C.Gene [i]; } Rückgabekopie; } 6. Beide Eltern produzieren die nächste Generation, und hier produzieren zwei Personen zwei individuelle Nachkommen. Welches spezifische Gen unterscheidet sich vom Schüler, ist völlig zufällig.
öffentliche statische Liste <Hromosoms> Genetisches (Chromosom P1, Chromosom P2) {if (p1 == null || p2 == null) {// Es gibt eines der Chromosomen, die leer sind und die nächste Generation nicht zurückgeben, Null; } if (p1.gene == null || p2.gen == null) {// Es gibt eines der Chromosomen, das keine Gensequenz hat und nicht die Rückkehr der nächsten Generation erzeugt; } if (p1.gen.length! } Chromosom C1 = Klon (p1); Chromosom C2 = Klon (P2); // Cross-Swap-Positionen zufällig int size = c1.gen.length erstellen; int a = ((int) (math.random () * Größe) % Größe; int b = ((int) (math.random () * Größe) % Größe; int min = a> b? B: a; int max = a> b? A: B; // cromex -Gene an Positionen für (int i = min; i <= max; i ++) {boolean t = c1.gene [i]; c1.gene [i] = c2.gene [i]; C2.gene [i] = t; } List <chromosom> list = new ArrayList <Hromosome> (); list.add (c1); list.add (c2); Rückgabeliste; } Algorithmus-Implementierungs-Genetikalgorithmus
1. Für genetische Algorithmen müssen wir entsprechende Populationen und einige Konstanten haben, die wir festlegen müssen: Populationsnummer, Genlänge, Anzahl der Genmutationen, Genmutationsrate usw. Weitere Informationen finden Sie im folgenden Code:
public abstract class GeneticAlgorithm { private List<Chromosome> population = new ArrayList<Chromosome>();//Population private int popSize = 100;//Population number private int geneSize;//Maximum length private int maxIterNum = 500;//Maximum iteration private double mutationRate = 0.01;//Probability of gene mutation private int maxMutationNum = 3;//Maximum mutation Asynchrone Länge Private int Generation = 1; // Wie viele Generationen werden derzeit geerbt? BestScore; // Best Score Private Double WorstScore; // Worst Score Private Double Totalscore; // Total Score Private Double AveragesCore; // Durchschnittliche Punktzahl Private Double X; // den besten X -Wert in der historischen Bevölkerung privat Double Y aufzeichnen; // zeichnen Sie den besten Y -Wert in der historischen Bevölkerung privat int genei auf; // Algebra, in der sich XY befindet} 2. Initialisieren Sie die Bevölkerung. Zu Beginn des genetischen Algorithmus müssen wir eine ursprüngliche Population initialisieren, die die ursprüngliche erste Generation ist.
private void init () {für (int i = 0; i <popsize; i ++) {Population = new ArrayList <Chromosom> (); Chromosomenchro = neues Chromosom (Genesize); Bevölkerung.ADD (CHRO); } cacultescore (); } 3. Nachdem die anfängliche Bevölkerung vorhanden ist, müssen wir die Fitness der Bevölkerung sowie die beste Fitness, die schlechteste Fitness und die durchschnittliche Fitness usw. berechnen.
private void cacultescore () {setCromosomescore (Population.get (0)); BestScore = Population.get (0) .GetScore (); WorstScore = Population.get (0) .GetScore (); sumalscore = 0; für (Chromosomenchro: Population) {setchromosomescore (chro); if (chro.getScore ()> BestScore) {// Setzen Sie den besten Genwert BestScore = chro.getScore (); if (y <BestScore) {x = changex (chro); y = BestScore; Genei = Generation; }} if (chro.getScore () <WorstScore) {// Setzen Sie den schlechtesten Genwert WorstScore = chro.getScore (); } sotalscore += chro.getScore (); } averagesCore = sotalscore / popsize; // Der Durchschnittswert, der durch Genauigkeitsprobleme verursacht wird, ist größer als der beste Wert. Setzen Sie den Durchschnittswert auf den besten Wert averagesCore = averagesCore> BestScore? BestScore: Durchschnittscore; } 4. Bei der Berechnung der individuellen Fitness müssen wir den entsprechenden Y -Wert basierend auf dem Gen berechnen. Hier setzen wir zwei abstrakte Methoden, um die spezifische Implementierung durch die Implementierung der Klasse zu implementieren.
private void setCromosomescore (Chromosom -chro) {if (chro == null) {return; } double x = changex (chro); doppelt y = kakulat (x); chro.setscore (y); } / ** * @param chro * @return * @Description: Binär in den entsprechenden x * / public abstract Double Changex (Chromosomchro) konvertieren; / ** * @param x * @return * @Description: Berechnen Sie den Y -Wert basierend auf x y = f (x) */ public abstract Double Caculate (Double X); 5. Nach der Berechnung der Bevölkerungsfitness müssen wir die Plattenspieler -Glücksspielmethode verwenden, um Personen auszuwählen, die die nächste Generation erzeugen können. Hier gibt es eine Bedingung, dass nur dann geboren wird, wenn die Fitness des Einzelnen nicht geringer ist als die durchschnittliche Fitness (die nächste Überleben).
Private Chromosom getParentchromosome () {Double Slice = Math.random () * Totalscore; doppelte Summe = 0; für (Chromosom -Chro: Population) {sum += chro.getScore (); // Gehen Sie zur entsprechenden Position und die Fitness ist nicht geringer als die durchschnittliche Fitness if (sum> Slice && chro.getScore ()> = averagesCore) {return chro; }} return null; } 6. Nachdem Sie Personen ausgewählt haben, die die nächste Generation produzieren können, müssen Sie sich eine Paarung der nächsten Generation messen.
private void evolve () {list <chromosom> childpopulation = new ArrayList <Hromosoms> (); // generieren Sie die Population der nächsten Generation, während (Kinderpopulation.size () <popsize) {Chromosom p1 = getParentchromosome (); Chromosom P2 = getParentchromosom (); Liste <Hromosoms> Kinder = Chromosom.Genetic (p1, p2); if (Kinder! }}} // Ersetzen Sie die alte Bevölkerung durch neue Bevölkerungsliste <Chromosom> T = Population; Bevölkerung = Kinderpopulation; t.clear (); t = null; // Genmutationsmutation (); // Berechnen Sie die Fitness neuer Bevölkerung Cacultescore (); } 7. Genetische Mutationen können während des Erzeugungsprozesses der nächsten Generation auftreten.
private void mutation () {for (chromosom chro: population) {if (math.random () <mutationRate) {// Genmutation kommt int mutationNum = (int) (math.random () * maxmutationnum); chro.mutation (mutationnum); }}} 8. Wiederholen Sie die obigen Schritte einzeln.
public void caculte () {// Initialisieren Sie die Bevölkerungsgenerierung = 1; init (); while (Generation <maxiternum) {// populäre genetische Evolution (); drucken(); Generation ++; }}Implementierungsklassen schreiben
Da die Klasse des obigen genetischen Algorithmus eine abstrakte Klasse ist, müssen wir eine Implementierungsklasse für einen bestimmten Fall schreiben, vorausgesetzt, wir berechnen den Maximalwert von y = 100 Log (x) auf [6,106].
1. Wir gehen davon aus, dass die Länge des Gens 24 beträgt (die Länge des Gens wird durch die effektive Länge des erforderlichen Ergebnisses bestimmt)
public class geneticalgorithmtest erweitert geneticalgorithmus {public static final int num = 1 << 24; public GeneticalgorithmTest () {Super (24); }} 2. Implementieren Sie die abstrakte Methode des X -Werts
@Override public Double Changex (Chromosom-chro) {// Todo automatisch generierte Methode Stub Return ((1.0 * chro.getNum () / num) * 100) + 6; } 3. Implementieren Sie die abstrakte Methode von y
@Override public Double Caculatey (Double x) {// Todo automatisch generierter Methode Stub return 100 - math.log (x); }Auslaufergebnisse
Denken Sie über genetische Algorithmen nach
Ich habe viele Einführungen in genetische Algorithmen gelesen. Die oben genannten optimalen Lösungen sind die meisten Werte der letzten Generation. Ich habe eine Frage. Warum weiß ich, dass die meisten Werte unter allen obigen Bändern die XY -Werte im Programm, warum ich XY -Werte nicht als Endergebniswert des genetischen Algorithmus verwenden kann?
Vollständiger Code
1. Chromosomenklasse
/ ***@Beschreibung: Genetisches Chromosom*/ Package com.lulei.genetic.algorithmus; Import Java.util.ArrayList; importieren java.util.list; public class chromosom {private boolean [] Gen; // Gensequenz Private Double Score; // entsprechende Funktionsbewertung public double getCore () {return Score; } public void setScore (doppelte Punktzahl) {this.score = Score; } / *** @param Größe* zufällig erzeugte Gensequenz* / public Chromosom (int Größe) {if (Größe <= 0) {return; } initgenesize (Größe); für (int i = 0; i <size; i ++) {Gene [i] = math.random ()> = 0,5; }} / *** generieren Sie ein neues Gen* / public Chromosome () {} / *** @param c* @return* @Description: Kloning -Gen* / public static Chromosom -Klon (endgültig Chromosom C) {if (c == null || C.Gene == NULL) {zurück) {return null; } Chromosom copy = new Chromosome (); Copy.initgenesize (C.gene.length); für (int i = 0; i <c.gen.length; i ++) {Copy.gene [i] = C.Gene [i]; } Rückgabekopie; } / *** @param Größe* @Description: Initialisieren Sie die Genlänge* / private void initgenesize (int size) {if (Größe <= 0) {return; } Gene = neuer Boolescher [Größe]; } /** * @param c1 * @param c2 * @Description: Genetische Erzeugung zur Herstellung der nächsten Generation * /public statische Liste <Chromosom> Genetische (Chromosom p1, Chromosom p2) {if (p1 == null || p2 == Null) {// Es gibt eines der Chromosomen, die die nächste Generation ergeben. } if (p1.gene == null || p2.gene == null) {// Es gibt eines der Chromosomen, das keine Gensequenz hat und die nächste Generation nicht zurückführt. } if (p1.gen.length! } Chromosom C1 = Klon (p1); Chromosom C2 = Klon (P2); // Cross-Swap-Positionen zufällig int size = c1.gen.length erstellen; int a = ((int) (math.random () * Größe) % Größe; int b = ((int) (math.random () * Größe) % Größe; int min = a> b? B: a; int max = a> b? A: B; // cromex -Gene an Positionen für (int i = min; i <= max; i ++) {boolean t = c1.gene [i]; c1.gene [i] = c2.gene [i]; C2.gene [i] = t; } List <chromosom> list = new ArrayList <Hromosome> (); list.add (c1); list.add (c2); Rückgabeliste; } /*** @param num* @Description: Variation tritt in den NUM -Positionen der Gen Num* /public void Mutation auf (int num) {// Mutation int size = Gen.length; für (int i = 0; i <num; i ++) {// Suchen Sie nach Mutationsposition int at = ((int) (math.random () * Größe) % Größe; // Der Wert nach Mutation boolean bool =! Gen [at]; Gene [at] = bool; }} / *** @return* @Description: Gene in entsprechende Zahlen konvertieren* / public int getnum () {if (gene == null) {return 0; } int num = 0; für (boolean bool: Gene) {num << = 1; if (bool) {num += 1; }} return num; }} 2. Geneticalgorithmus Klasse
/ ** *@Beschreibung: */ package com.lulei.genetic.algorithmus; Import Java.util.ArrayList; importieren java.util.list; public abstract Class Geneticalgorithmus {private list <Chromosom> Population = New ArrayList <Hromosom> (); private int popSize = 100;//Popular number private int geneSize;//Maximum gene length private int maxIterNum = 500;//Maximum number of iterations private double mutationRate = 0.01;//Probability of gene mutation private int maxMutationNum = 3;//Maximum variant asynchronous length private int generation = 1;//How many generations are currently inherited to? Private Double BestScore; // Best Score Private Double WorstScore; // Worst Score Private Double Totalscore; // Total Score Private Double AveragesCore; // Durchschnittliche Punktzahl Private Double X; // den besten X -Wert in der historischen Bevölkerung privat Double Y aufzeichnen; // den besten Y -Wert in der historischen Bevölkerung privat int genei aufzeichnen // Algebra, bei der XY das öffentliche genetische Gorithmus (int genesize) {this.genesize = genesize; } public void caculte () {// Initialisieren Sie die Bevölkerungsgenerierung = 1; init (); while (Generation <maxiternum) {// populäre genetische Evolution (); drucken(); Generation ++; }} / *** @Description: Ausgabeergebnis* / private void print () { System.out.println("--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- System.out.println ("Die schlimmste Fitness ist:" WorstScore); * @Description: Initialisieren Sie die Population*/ private void () {für (int i = 0; private void evolve () {list <chromosom> kindPopulation = new ArrayList <Cromosoms> (); p2) if (Kinder! @Return * @Description: Roulette -Methode wählt Chromosomen aus, die die nächste Generation erben können. durchschnittlich) {Return CHRO; Population) {setchromosomescore (chro); WorstScore = chro.getScore (); Mutation () {für (Chromosom -CHRO: Population) {if (math.random () <mutationrate) {// Die Genmutation tritt int mutationNum = (int) (math.random () * maxmutation auf); setChromosomescore (Chromosom -chro) {if (chro == null) {return; @param x * @return * @Description: Berechnen Sie Y -Wert basierend auf x y = f (x) */ public caculatey (Double X); = genesie; GetBestScore () {Return BestScore; 3.. Geneticalgorithmtest -Klasse
/ ** *@Beschreibung: */ package com.lulei.genetic.algorithmus; public class geneticalgorithmtest erweitert geneticalgorithmus {public static final int num = 1 << 24; public GeneticalgorithmTest () {Super (24); } @Override public Double Changex (Chromosom-Chro) {// Todo Auto-Generated-Methode Stub Return ((1.0 * chro.getNum () / num) * 100) + 6; } @Override public Double Caculatey (double x) {// Todo automatisch generierte Methode Stub return 100 - math.log (x); } public static void main (String [] args) {GeneticalGorithmTest test = new GeneticalgorithmTest (); test.caculte (); }}Das obige ist eine detaillierte Einführung in den genetischen Java -Algorithmus. Ich hoffe, es wird für alle hilfreich sein, Java -Genetikalgorithmus zu lernen.