Shulou(Shulou.com)06/01 Report--

This article mainly introduces "what is the basic concept and implementation method of Java genetic algorithm". In daily operation, I believe many people have doubts about the basic concept and implementation method of Java genetic algorithm. I have consulted all kinds of materials and sorted out simple and easy to use operation methods. I hope to help you answer the doubts of "what is the basic concept and implementation method of Java genetic algorithm"! Next, please follow the small series to learn together!

As shown in the figure above (left), the individual of the genetic algorithm consists of multiple chromosomes, each chromosome consisting of multiple genes. The image above (right) shows how chromosomes divide and combine._

Concept of Genetic Algorithm

The process of natural selection begins by selecting the individuals in the population who are best suited to their environment. Offspring inherit the traits of their parents and these traits are added to the next generation. If parents are more adaptable, their offspring will be more likely to survive. Iterative through this process of natural selection, we end up with a generation of individuals who are best suited to their environment.

This concept can be applied to search problems. We consider many solutions to a problem and search for the best one.

The genetic algorithm consists of the following five steps:

initialization

Individual evaluation (calculation of fitness function)

selection operation

crossover operation

mutation operation

initialization

The process starts with a group of individuals of the population, each of which is a candidate solution to the problem to be solved.

Individuals are characterized by a set of parameters (variables) called genes, which in tandem form chromosomes (solutions to problems).

In genetic algorithms, the genomes of individual individuals are presented as strings, usually encoded in binary (strings of ones and zeros), i.e. a binary string represents a chromosome string. Thus we can say that we encode the characteristics of the gene string or candidate solution in chromosomes.

Populations, chromosomes and genes

Individual evaluation (calculation of fitness function)

Individual evaluation uses fitness functions to assess an individual's fitness to the environment (ability to compete with others). Each individual has a fitness score, and the likelihood that an individual will be selected for reproduction depends on its fitness score. The larger the fitness function, the higher the quality of the solution. Fitness function is the driving force of genetic algorithm evolution, and also the only criterion of natural selection. Its design should be combined with the requirements of solving the problem itself.

selection operation

The goal of selection operations is to select the most adaptable individuals and have them pass genes on to the next generation. Based on their fitness scores, we select multiple pairs of superior individuals (parents). Individuals with higher fitness are more likely to be selected for reproduction, i.e., to pass on genes from better parents to the next generation.

crossover operation

Crossover operation is the most important phase of genetic algorithm. For each pair of parents, there are randomly selected crossover points for genes.

For example, the intersection of the following graph is 3:

Parents swap genes before the crossover point, producing offspring.

Genes are exchanged between parents, and new offspring are added to the population.

mutation operation

In some of the new offspring formed, some of their genes may be affected by low-probability variation factors. This means that certain bits in the binary bit string may flip.

before and after mutation operation

Variation operations can be used to maintain diversity within populations and prevent premature convergence.

termination

The algorithm terminates when the population converges (no offspring are produced within the population that differ significantly from the previous generation). That is, genetic algorithms provide solutions to a set of problems.

Case realization

The population size is constant. As new generations form, the least adapted individuals die, leaving room for offspring. The sequence of these stages is repeated over and over again to produce a new generation superior to the previous one.

Pseudocode for this iterative process:

STARTGenerate the initial populationCompute fitnessREPEAT Selection Crossover Mutation Compute fitnessUNTIL population has convergedSTOP

Example implementation in Java

The following is a sample implementation of genetic algorithms in Java, which we can debug and modify at will. Given a set of five genes, each gene can hold a binary value of 0 or 1. The fitness here is the number of 1s in the genome. If there are five 1s in the genome, the fitness of the individual reaches a maximum.

If there is no 1 in the genome, then the fitness of the individual reaches a minimum. The genetic algorithm hopes to maximize fitness and provide a population of individuals with maximum fitness. Note: In this example, after crossover and mutation, the least fit individual is replaced by a new, most fit offspring.

import java.util.Random;/** * * @author Vijini*///Main classpublic class SimpleDemoGA { Population population = new Population(); Individual fittest; Individual secondFittest; int generationCount = 0; public static void main(String[] args) { Random rn = new Random(); SimpleDemoGA demo = new SimpleDemoGA(); //Initialize population demo.population.initializePopulation(10); //Calculate fitness of each individual demo.population.calculateFitness(); System.out.println("Generation: " + demo.generationCount + " Fittest: " + demo.population.fittest); //While population gets an individual with maximum fitness while (demo.population.fittest

< 5) { ++demo.generationCount; //Do selection demo.selection(); //Do crossover demo.crossover(); //Do mutation under a random probability if (rn.nextInt()%7 < 5) { demo.mutation(); } //Add fittest offspring to population demo.addFittestOffspring(); //Calculate new fitness value demo.population.calculateFitness(); System.out.println("Generation: " + demo.generationCount + " Fittest: " + demo.population.fittest); } System.out.println("\nSolution found in generation " + demo.generationCount); System.out.println("Fitness: "+demo.population.getFittest().fitness); System.out.print("Genes: "); for (int i = 0; i < 5; i++) { System.out.print(demo.population.getFittest().genes[i]); } System.out.println(""); } //Selection void selection() { //Select the most fittest individual fittest = population.getFittest(); //Select the second most fittest individual secondFittest = population.getSecondFittest(); } //Crossover void crossover() { Random rn = new Random(); //Select a random crossover point int crossOverPoint = rn.nextInt(population.individuals[0].geneLength); //Swap values among parents for (int i = 0; i < crossOverPoint; i++) { int temp = fittest.genes[i]; fittest.genes[i] = secondFittest.genes[i]; secondFittest.genes[i] = temp; } } //Mutation void mutation() { Random rn = new Random(); //Select a random mutation point int mutationPoint = rn.nextInt(population.individuals[0].geneLength); //Flip values at the mutation point if (fittest.genes[mutationPoint] == 0) { fittest.genes[mutationPoint] = 1; } else { fittest.genes[mutationPoint] = 0; } mutationPoint = rn.nextInt(population.individuals[0].geneLength); if (secondFittest.genes[mutationPoint] == 0) { secondFittest.genes[mutationPoint] = 1; } else { secondFittest.genes[mutationPoint] = 0; } } //Get fittest offspring Individual getFittestOffspring() { if (fittest.fitness >

secondFittest.fitness) { return fittest; } return secondFittest; } //Replace least fittest individual from most fittest offspring void addFittestOffspring() { //Update fitness values of offspring fittest.calcFitness(); secondFittest.calcFitness(); //Get index of least fit individual int leastFittestIndex = population.getLeastFittestIndex(); //Replace least fittest individual from most fittest offspring population.individuals[leastFittestIndex] = getFittestOffspring(); }}//Individual classclass Individual { int fitness = 0; int[] genes = new int[5]; int geneLength = 5; public Individual() { Random rn = new Random(); //Set genes randomly for each individual for (int i = 0; i

< genes.length; i++) { genes[i] = rn.nextInt() % 2; } fitness = 0; } //Calculate fitness public void calcFitness() { fitness = 0; for (int i = 0; i < 5; i++) { if (genes[i] == 1) { ++fitness; } } }}//Population classclass Population { int popSize = 10; Individual[] individuals = new Individual[10]; int fittest = 0; //Initialize population public void initializePopulation(int size) { for (int i = 0; i < individuals.length; i++) { individuals[i] = new Individual(); } } //Get the fittest individual public Individual getFittest() { int maxFit = Integer.MIN_VALUE; for (int i = 0; i < individuals.length; i++) { if (maxFit individuals[maxFit1].fitness) { maxFit2 = maxFit1; maxFit1 = i; } else if (individuals[i].fitness >

individuals[maxFit2].fitness) { maxFit2 = i; } } return individuals[maxFit2]; } //Get index of least fittest individual public int getLeastFittestIndex() { int minFit = 0; for (int i = 0; i

< individuals.length; i++) { if (minFit >

= individuals[i].fitness) { minFit = i; } } return minFit; } //Calculate fitness of each individual public void calculateFitness() { for (int i = 0; i < individuals.length; i++) { individuals[i].calcFitness(); } getFittest(); }} At this point, the study of "what is the basic concept and implementation method of Java genetic algorithm" is over, hoping to solve everyone's doubts. Theory and practice can better match to help everyone learn, go and try it! If you want to continue learning more relevant knowledge, please continue to pay attention to the website, Xiaobian will continue to strive to bring more practical articles for everyone!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.