I won’t introduce the detailed principles and specific definitions of genetic algorithms here. If you want to know, you can use Baidu to learn it. Here I will briefly introduce your understanding of genetic algorithms. This article uses binary rules for gene encoding.
Algorithm ideas:
The genetic algorithm refers to Darwin's theory of evolution and believes that species are developing in a positive direction (survival of the fittest), so it can be considered that after sufficient algebra, the obtained maximum value is very close to the actual maximum value.
Algorithm steps:
Algorithm implementation-Gene part
1. Individual population (here considered chromosomes), in individuals, we add two attributes to this individual, the fitness (function value) corresponding to the individual's gene and gene.
public class Chromosome { private boolean[] gene;//gene sequence private double score;//corresponding function score} 2. Generate gene sequences randomly. Whether each position of the gene is 0 or 1, this is a completely random way to achieve it.
public Chromosome(int size) { if (size <= 0) { return; } initGeneSize(size); for (int i = 0; i < size; i++) { gene[i] = Math.random() >= 0.5; } } private void initGeneSize(int size) { if (size <= 0) { return; } gene = new boolean[size]; } 3. Convert the gene into the corresponding value, for example, the number corresponding to 101 is 5, and bit operations are used here to implement it.
public int getNum() { if (gene == null) { return 0; } int num = 0; for (boolean bool : gene) { num <<= 1; if (bool) { num += 1; } } return num; } 4. If a gene mutation occurs, the location of the mutation is completely implemented in a random way. The mutation principle is to change from 1 to 0 and 0 to 1.
public void mutation(int num) { //Allow mutation int size = gene.length; for (int i = 0; i < num; i++) { //Look for mutation location int at = ((int) (Math.random() * size)) % size; //The value after mutation boolean bool = !gene[at]; gene[at] = bool; } } 5. Cloning genes is used to produce the next generation. This step is to copy the existing genes.
public static Chromosome clone(final Chromosome c) { if (c == null || c.gene == null) { return null; } Chromosome copy = new Chromosome(); copy.initGeneSize(c.gene.length); for (int i = 0; i < c.gene.length; i++) { copy.gene[i] = c.gene[i]; } return copy; } 6. Both parents produce the next generation, and here two individuals produce two individual offspring. Which specific gene is different from the student, is completely random.
public static List<Chromosome> genetic(Chromosome p1, Chromosome p2) { if (p1 == null || p2 == null) { //There is one of the chromosomes that is empty and does not produce the next generation return null; } if (p1.gene == null || p2.gene == null) { //There is one of the chromosomes that has no gene sequence and does not produce the next generation return null; } if (p1.gene.length != p2.gene.length) { //The length of the chromosome gene sequence does not produce the next generation return null; } Chromosome c1 = clone(p1); Chromosome c2 = clone(p2); //Create cross-swap positions randomly int size = c1.gene.length; int a = ((int) (Math.random() * size)) % size; int b = ((int) (Math.random() * size)) % size; int min = a > b ? b : a; int max = a > b ? a : b; //Cromex genes at positions for (int i = min; i <= max; i++) { boolean t = c1.gene[i]; c1.gene[i] = c2.gene[i]; c2.gene[i] = t; } List<Chromosome> list = new ArrayList<Chromosome>(); list.add(c1); list.add(c2); return list; } Algorithm Implementation-Genetic Algorithm
1. For genetic algorithms, we need to have corresponding populations and some constants we need to set: population number, gene length, number of gene mutations, gene mutation rate, etc. For details, please refer to the following 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 asynchronous length private int generation = 1;//How many generations are currently inherited to? bestScore;//Best score private double worstScore;//Worst score private double totalScore;//Total score private double averageScore;//Average score private double x; //Record the best X value in historical population private double y; //Record the best Y value in historical population private int geneI;//Algebra where xy is located} 2. Initialize the population. At the beginning of the genetic algorithm, we need to initialize an original population, which is the original first generation.
private void init() { for (int i = 0; i < popSize; i++) { population = new ArrayList<Chromosome>(); Chromosome chro = new Chromosome(geneSize); population.add(chro); } caculteScore(); } 3. After the initial population exists, we need to calculate the fitness of the population, as well as the best fitness, worst fitness and average fitness, etc.
private void caculteScore() { setChromosomeScore(population.get(0)); bestScore = population.get(0).getScore(); worstScore = population.get(0).getScore(); totalScore = 0; for (Chromosome chro : population) { setChromosomeScore(chro); if (chro.getScore() > bestScore) { //Set the best gene value bestScore = chro.getScore(); if (y < bestScore) { x = changeX(chro); y = bestScore; geneI = generation; } } if (chro.getScore() < worstScore) { //Set the worst gene value worstScore = chro.getScore(); } totalScore += chro.getScore(); } averageScore = totalScore / popSize; //The average value caused by accuracy problems is greater than the best value, set the average value to the best value averageScore = averageScore > bestScore ? bestScore : averageScore; } 4. When calculating individual fitness, we need to calculate the corresponding Y value based on the gene. Here we set two abstract methods to implement the specific implementation by the implementation of the class.
private void setChromosomeScore(Chromosome chro) { if (chro == null) { return; } double x = changeX(chro); double y = caculateY(x); chro.setScore(y); } /** * @param chro * @return * @Description: Convert binary to the corresponding X */ public abstract double changeX(Chromosome chro); /** * @param x * @return * @Description: Calculate Y value based on X Y=F(X) */ public abstract double caculateY(double x); 5. After calculating population fitness, we need to use the turntable gambling method to select individuals that can produce the next generation. There is a condition here that only if the individual's fitness is not less than the average fitness, the next generation will be born (the fittest survive).
private Chromosome getParentChromosome (){ double slice = Math.random() * totalScore; double sum = 0; for (Chromosome chro : population) { sum += chro.getScore(); //Go to the corresponding position and the fitness is not less than the average fitness if (sum > slice && chro.getScore() >= averageScore) { return chro; } } return null; } 6. After selecting individuals that can produce the next generation, you must mating to produce the next generation.
private void evolve() { List<Chromosome> childPopulation = new ArrayList<Chromosome>(); //Generate the next generation population while (childPopulation.size() < popSize) { Chromosome p1 = getParentChromosome(); Chromosome p2 = getParentChromosome(); List<Chromosome> children = Chromosome.genetic(p1, p2); if (children != null) { for (Chromosome chro : children) { childPopulation.add(chro); } } } //Replace old population with new population List<Chromosome> t = population; population = childPopulation; t.clear(); t = null; //Gene mutation mutation(); //Calculate the fitness of new population caculteScore(); } 7. Genetic mutations may occur during the process of producing the next generation.
private void mutation() { for (Chromosome chro : population) { if (Math.random() < mutationRate) { // Gene mutation occurs int mutationNum = (int) (Math.random() * maxMutationNum); chro.mutation(mutationNum); } } } 8. Repeat the above steps one by one.
public void caculte() { //Initialize population generation = 1; init(); while (generation < maxIterNum) { //Popular genetic evolution(); print(); generation++; } }Write implementation classes
Since the class of the above genetic algorithm is an abstract class, we need to write an implementation class for a specific case, assuming we calculate the maximum value of Y=100-log(X) on [6,106].
1. We assume that the length of the gene is 24 (the length of the gene is determined by the effective length of the required result), so the corresponding binary maximum is 1<< 24. We make the following settings
public class GeneticAlgorithmTest extends GeneticAlgorithm{ public static final int NUM = 1 << 24; public GeneticAlgorithmTest() { super(24); } } 2. Implement the abstract method of X value
@Override public double changeX(Chromosome chro) { // TODO Auto-generated method stub return ((1.0 * chro.getNum() / NUM) * 100) + 6; } 3. Implement the abstract method of Y
@Override public double caculateY(double x) { // TODO Auto-generated method stub return 100 - Math.log(x); }Running results
Thinking about genetic algorithms
I have read a lot of introductions to genetic algorithms. The optimal solutions mentioned above are the most values of the last generation. I have a question. Why do I know that the most values among all the bands above, that is, the XY values in the program, why can't I use XY values as the final result value of the genetic algorithm?
Complete code
1. Chromosome class
/** *@Description: Genetic chromosome*/ package com.lulei.genetic.algorithm; import java.util.ArrayList; import java.util.List; public class Chromosome { private boolean[] gene;//gene sequence private double score;//corresponding function score public double getScore() { return score; } public void setScore(double score) { this.score = score; } /** * @param size * Randomly generated gene sequence*/ public Chromosome(int size) { if (size <= 0) { return; } initGeneSize(size); for (int i = 0; i < size; i++) { gene[i] = Math.random() >= 0.5; } } /** * Generate a new gene*/ public Chromosome() { } /** * @param c * @return * @Description: cloning gene*/ public static Chromosome clone(final Chromosome c) { if (c == null || c.gene == null) { return null; } Chromosome copy = new Chromosome(); copy.initGeneSize(c.gene.length); for (int i = 0; i < c.gene.length; i++) { copy.gene[i] = c.gene[i]; } return copy; } /** * @param size * @Description: Initialize gene length*/ private void initGeneSize(int size) { if (size <= 0) { return; } gene = new boolean[size]; } /** * @param c1 * @param c2 * @Description: Genetic generation to produce the next generation*/ public static List<Chromosome> genetic(Chromosome p1, Chromosome p2) { if (p1 == null || p2 == null) { //There is one of the chromosomes that is empty, and does not produce the next generation return null; } if (p1.gene == null || p2.gene == null) { //There is one of the chromosomes that has no gene sequence, and does not produce the next generation return null; } if (p1.gene.length != p2.gene.length) { //The length of the chromosome gene sequence does not produce the next generation return null; } Chromosome c1 = clone(p1); Chromosome c2 = clone(p2); //Create cross-swap positions randomly int size = c1.gene.length; int a = ((int) (Math.random() * size)) % size; int b = ((int) (Math.random() * size)) % size; int min = a > b ? b : a; int max = a > b ? a : b; //Cromex genes at positions for (int i = min; i <= max; i++) { boolean t = c1.gene[i]; c1.gene[i] = c2.gene[i]; c2.gene[i] = t; } List<Chromosome> list = new ArrayList<Chromosome>(); list.add(c1); list.add(c2); return list; } /** * @param num * @Description: Variation occurs in the num positions of gene num*/ public void mutation(int num) { //Allow mutation int size = gene.length; for (int i = 0; i < num; i++) { //Search for mutation position int at = ((int) (Math.random() * size)) % size; //The value after mutation boolean bool = !gene[at]; gene[at] = bool; } } /** * @return * @Description: Convert genes to corresponding numbers*/ public int getNum() { if (gene == null) { return 0; } int num = 0; for (boolean bool : gene) { num <<= 1; if (bool) { num += 1; } } return num; } } 2. GeneticAlgorithm class
/** *@Description: */ package com.lulei.genetic.algorithm; import java.util.ArrayList; import java.util.List; public abstract class GeneticAlgorithm { private List<Chromosome> population = new ArrayList<Chromosome>(); 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;//Average score private double x; //Record the best X value in historical population private double y; //Record the best Y value in historical population private int geneI;//Algebra where xy is located public GeneticAlgorithm(int geneSize) { this.geneSize = geneSize; } public void caculte() { //Initialize population generation = 1; init(); while (generation < maxIterNum) { //Popular genetic evolution(); print(); generation++; } } /** * @Description: Output result*/ private void print() { System.out.println("--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- System.out.println("the worst fitness is:" + worstScore); System.out.println("the average fitness is:" + averageScore); System.out.println("the total fitness is:" + totalScore); System.out.println("geneI:" + geneI + "/tx:" + x + "/ty:" + y); } /** * @Description: Initialize population*/ private void init() { for (int i = 0; i < popSize; i++) { population = new ArrayList<Chromosome>(); Chromosome chro = new Chromosome(geneSize); population.add(chro); } caculteScore(); } /** * @Author:lulei * @Description:Population for inheritance*/ private void evolve() { List<Chromosome> childPopulation = new ArrayList<Chromosome>(); //Generate the next generation of population while (childPopulation.size() < popSize) { Chromosome p1 = getParentChromosome(); Chromosome p2 = getParentChromosome(); List<Chromosome> children = Chromosome.genetic(p1, p2); if (children != null) { for (Chromosome chro : children) { childPopulation.add(chro); } } } //Replace old population with new population List<Chromosome> t = population; population = childPopulation; t.clear(); t = null; //Gene mutation mutation(); //Calculate fitness of new population caculteScore(); } /** * @return * @Description: Roulette method selects chromosomes that can inherit the next generation*/ private Chromosome getParentChromosome (){ double slice = Math.random() * totalScore; double sum = 0; for (Chromosome chro : population) { sum += chro.getScore(); if (sum > slice && chro.getScore() >= averageScore) { return chro; } } return null; } /** * @Description: Calculate population fitness*/ private void caculteScore() { setChromosomeScore(population.get(0)); bestScore = population.get(0).getScore(); worstScore = population.get(0).getScore(); totalScore = 0; for (Chromosome chro : population) { setChromosomeScore(chro); if (chro.getScore() > bestScore) { //Set the best gene value bestScore = chro.getScore(); if (y < bestScore) { x = changeX(chro); y = bestScore; geneI = generation; } } if (chro.getScore() < worstScore) { //Set the worst gene value worstScore = chro.getScore(); } totalScore += chro.getScore(); } averageScore = totalScore / popSize; //The average value caused by accuracy problems is greater than the best value, set the average value to the best value averageScore = averageScore > bestScore ? bestScore : averageScore; } /** * Gene mutation*/ private void mutation() { for (Chromosome chro : population) { if (Math.random() < mutationRate) { //The gene mutation occurs int mutationNum = (int) (Math.random() * maxMutationNum); chro.mutation(mutationNum); } } } /** * @param chro * @Description: Set chromosome score*/ private void setChromosomeScore(Chromosome chro) { if (chro == null) { return; } double x = changeX(chro); double y = caculateY(x); chro.setScore(y); } /** * @param chro * @return * @Description: Convert binary to the corresponding X */ public abstract double changeX(Chromosome chro); /** * @param x * @return * @Description: Calculate Y value based on X Y=F(X) */ public abstract double caculateY(double x); public void setPopulation(List<Chromosome> population) { this.population = population; } public void setPopSize(int popSize) { this.popSize = popSize; } public void setGeneSize(int geneSize) { this.geneSize = geneSize; } public void setMaxIterNum(int maxIterNum) { this.maxIterNum = maxIterNum; } public void setMutationRate(double mutationRate) { this.mutationRate = mutationRate; } public void setMaxMutationNum(int maxMutationNum) { this.maxMutationNum = maxMutationNum; } public double getBestScore() { return bestScore; } public double getWorstScore() { return worstScore; } public double getTotalScore() { return totalScore; } public double getAverageScore() { return averageScore; } public double getX() { return x; } public double getY() { return y; } } 3. GeneticAlgorithmTest class
/** *@Description: */ package com.lulei.genetic.algorithm; public class GeneticAlgorithmTest extends GeneticAlgorithm{ public static final int NUM = 1 << 24; public GeneticAlgorithmTest() { super(24); } @Override public double changeX(Chromosome chro) { // TODO Auto-generated method stub return ((1.0 * chro.getNum() / NUM) * 100) + 6; } @Override public double caculateY(double x) { // TODO Auto-generated method stub return 100 - Math.log(x); } public static void main(String[] args) { GeneticAlgorithmTest test = new GeneticAlgorithmTest(); test.caculte(); } }The above is a detailed introduction to Java genetic algorithm. I hope it will be helpful to everyone to learn Java genetic algorithm.