Genetic Algorithms¶
* Genetic algorithms are search heuristics that mimic the process of natural selection.
* They are used to generate useful solutions to optimization and search problems.
* Genetic Algorithms generate solutions to optimization problems using techniques inspired by natural evolution, such as mutation or crossover.
* A candidate solution is evolved toward better and better solutions.
* Each candidate solution has a set of properties (genes) which can be mutated and altered (usually the solutions are represented in binary)
* The evolution usually starts from a population of randomly generated individuals.
* It is an iterative process –> with the population in each iteration called a generation. In each generation, the fitness of every individual in the population is evaluated.
* The fitness is usually the value of the objective function in the optimization problem being solved.
* The more fit individuals are selected from the current population, and each individual's genome is modified (recombined and possibly randomly mutated) to form a new generation.
* The new generation of candidate solutions is then used in the next iteration.
* Commonly, the algorithm terminates when either a maximum number of generations has been produced, or a satisfactory fitness level has been reached for the population.
Crossover:
Sometimes we generate a random index, and after the given index we just swap the two subarrays of bits.
Another approach: We define a crossover threshold and generate a random value for every bit. Then, if we have reached the threshold, we swap the genes with the given index
We define the crossover threshold : 0.35
Random number: 0.41; Do not swap.
Random number: 0.63; Do not swap.
Random number: 0.89; Do not swap.
Random number: 0.11 -> Swap.
Random number: 0.37; Do not swap.
If the crossover threshold is low -> We will make few changes, algorithm will be slower but maybe more accurate.
If crossover threshold is high-> We will make a lot of changes with higher probability, algorithm will be faster.
Mutation:
Random number: 0.8; Do not mutate.
Random number: 0.55; Do not mutate.
Random number: 0.43 -> Mutate.
So what is mutation? We iterate through the genes and make mutations if necessary( just flip the bits to the opposite binary number).
* Applying Genetic Algorithms to a new problem is very simple: we just have to define a new fitness function best suited to the new problem.
* Genetic Algorithms will not often get stuck in a local optimum because the crossover and mutation processes produce radically different chromosomes.
* Basically the principle of "Survival of the fittest” is used and proves to be quite effective.
* It scales well even in high dimensions! And hence it holds an advantage.
Codes of the Java files included in the program are given below:
Constants.java¶
package geneticalgorithms; public class Constants { private Constants(){ } public static final int[] SOLUTION_SEQUENCE = {0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9}; //Solution we are seeking //Initially we generate random sequence //Then with GA we find the solution after various iterations // During each iteration, we match the bits with the solution // Those bits that match are termed : fittest. public static final double UNIFORM_RATE = 0.5; public static final double MUTATION_RATE = 0.15; public static final int TOURNAMENT_SIZE = 5; public static final int GENE_LENGTH = 20; public static final int MAX_FITNESS = 20; }
Individual.java¶
package geneticalgorithms; import java.util.Random; public class Individual { private int[] genes; private int fitness = 0; //no of bits matched with the solution sequence private Random randomGenerator; //Constructor public Individual() { this.genes = new int[Constants.GENE_LENGTH]; this.randomGenerator = new Random(); } // Random sequence is generated public void generateIndividual() { for (int i = 0; i < Constants.GENE_LENGTH; ++i) { int gene = randomGenerator.nextInt(10); genes[i] = gene; } } // Calculate the fitness //matching bits with the solution sequence public int getFitness() { if (this.fitness == 0) { for (int i = 0; i < Constants.GENE_LENGTH; ++i) { if ( getGene(i) == Constants.SOLUTION_SEQUENCE[i] ) { this.fitness++; } } } return fitness; } // Bits in the sequence public int getGene(int index) { return this.genes[index]; } public void setGene(int index, int value) { this.genes[index] = value; this.fitness = 0; } // Override toString method to return the genes sequence @Override public String toString() { String geneString = ""; for (int i = 0; i < Constants.GENE_LENGTH; i++) { geneString += getGene(i); } return geneString; } }
Population.java¶
package geneticalgorithms; public class Population { private Individual[] individuals; //Contains individuals // Constructor public Population(int populationSize) { individuals = new Individual[populationSize]; } //Create individuals public void initialize(){ for (int i = 0; i < size(); i++) { Individual newIndividual = new Individual(); newIndividual.generateIndividual(); saveIndividual(i, newIndividual); } } public Individual getIndividual(int index) { return this.individuals[index]; } // O(N) // Iterate through the size of population // and get the fittest individuals/ // Basic Linear Search public Individual getFittest() { Individual fittestIndividual = individuals[0]; for (int i = 0; i < size(); ++i) { if ( fittestIndividual.getFitness() <= getIndividual(i).getFitness()) { fittestIndividual = getIndividual(i); } } return fittestIndividual; } public int size() { return this.individuals.length; } public void saveIndividual(int index, Individual individual) { this.individuals[index] = individual; } }
GeneticAlgorithm.java¶
package geneticalgorithms; import java.util.Random; public class GeneticAlgorithm { private Random randomGenerator; public GeneticAlgorithm(){ this.randomGenerator = new Random(); } // public Population evolvePopulation(Population population) { Population newPopulation = new Population(population.size()); for (int index = 0; index < population.size(); ++index) { //Random Selections Individual firstIndividual = randomSelection(population); Individual secondIndividual = randomSelection(population); // Crossover Individual newIndividual = crossover(firstIndividual, secondIndividual); newPopulation.saveIndividual(index, newIndividual); } //Mutation for (int index = 0; index < newPopulation.size(); ++index) { mutate(newPopulation.getIndividual(index)); } return newPopulation; } // Get a subset of our population and save this random population // We get the fittest out of this subset private Individual randomSelection(Population population) { Population newPopulation = new Population(Constants.TOURNAMENT_SIZE); for (int index = 0; index < Constants.TOURNAMENT_SIZE; ++index) { int randomIndex = (int) (Math.random() * population.size()); newPopulation.saveIndividual(index, population.getIndividual(randomIndex)); } Individual fittestIndividual = newPopulation.getFittest(); return fittestIndividual; } //Crossover private Individual crossover(Individual firstIndividual, Individual secondIndividual) { Individual newSolution = new Individual(); for (int geneIndex = 0; geneIndex < Constants.GENE_LENGTH; ++geneIndex) { if (Math.random() <= Constants.UNIFORM_RATE) { newSolution.setGene(geneIndex, firstIndividual.getGene(geneIndex)); } else { newSolution.setGene(geneIndex, secondIndividual.getGene(geneIndex)); } } return newSolution; } //Mutation private void mutate(Individual individual) { for (int geneIndex = 0; geneIndex < Constants.GENE_LENGTH; ++geneIndex) { if (Math.random() <= Constants.MUTATION_RATE) { int gene = randomGenerator.nextInt(10); individual.setGene(geneIndex, gene); } } } }
Main.java¶
package geneticalgorithms; public class Main{ public static void main(String[] args) { GeneticAlgorithm algorithm = new GeneticAlgorithm(); Population population = new Population(100); population.initialize(); int generationCount = 0; // While the fittest individuals is not same as solution sequence while (population.getFittest().getFitness() != Constants.MAX_FITNESS) { ++generationCount; System.out.println("Generation: " + generationCount + " Fittest: " + population.getFittest().getFitness()); System.out.println(population.getFittest()+"\n"); population = algorithm.evolvePopulation(population); } System.out.println("Solution found:"); System.out.println(population.getFittest()); } }
Output of the program is :
Generation: 1 Fittest: 7 58924689290024056701 Generation: 2 Fittest: 9 23264517640129819759 Generation: 3 Fittest: 9 23269517640122652759 Generation: 4 Fittest: 10 60634567248123896379 Generation: 5 Fittest: 11 03931546890623494759 Generation: 6 Fittest: 11 17634537845123056701 Generation: 7 Fittest: 12 85632587805123456729 Generation: 8 Fittest: 15 01134567820823496779 Generation: 9 Fittest: 14 72532567890823446789 Generation: 10 Fittest: 15 01132577820123458789 Generation: 11 Fittest: 16 01132577890823456789 Generation: 12 Fittest: 16 21234562890133416789 Generation: 13 Fittest: 16 02132562890123456789 Generation: 14 Fittest: 16 01154567890164456789 Generation: 15 Fittest: 16 05284567890121456749 Generation: 16 Fittest: 17 01237567390123456739 Generation: 17 Fittest: 17 01232567890123416784 Generation: 18 Fittest: 17 01234567840823459789 Generation: 19 Fittest: 17 01234567890623496719 Generation: 20 Fittest: 17 01204567890123439789 Generation: 21 Fittest: 16 21634567890123196789 Generation: 22 Fittest: 16 01832567899623456789 Generation: 23 Fittest: 18 21234567890323456789 Generation: 24 Fittest: 18 01234167890323456789 Generation: 25 Fittest: 18 01234567890723456785 Generation: 26 Fittest: 18 01234567893120456789 Generation: 27 Fittest: 18 01234507890123456739 Generation: 28 Fittest: 17 01234597690123456709 Generation: 29 Fittest: 18 01234567891143456789 Generation: 30 Fittest: 19 01234567690123456789 Generation: 31 Fittest: 19 01234567890123456759 Generation: 32 Fittest: 18 01234567690123456709 Generation: 33 Fittest: 19 01234567830123456789 Generation: 34 Fittest: 18 01234507890123456709 Generation: 35 Fittest: 18 01274567690123456789 Generation: 36 Fittest: 18 01274564890123456789 Generation: 37 Fittest: 18 01274567090123456789 Generation: 38 Fittest: 18 01234567890123456059 Generation: 39 Fittest: 18 01274567090123456789 Generation: 40 Fittest: 18 01734567890123416789 Generation: 41 Fittest: 19 31234567890123456789 Generation: 42 Fittest: 18 01234567090123466789 Generation: 43 Fittest: 19 51234567890123456789 Generation: 44 Fittest: 19 01234567790123456789 Generation: 45 Fittest: 18 01234367890723456789 Generation: 46 Fittest: 18 01234568890123456189 Generation: 47 Fittest: 18 01234567890123466785 Generation: 48 Fittest: 17 01235567890123456735 Generation: 49 Fittest: 19 01234567890723456789 Generation: 50 Fittest: 18 01234167893123456789 Generation: 51 Fittest: 19 01234567830123456789 Generation: 52 Fittest: 18 01234567890183456189 Generation: 53 Fittest: 19 01214567890123456789 Generation: 54 Fittest: 19 01234567890123956789 Generation: 55 Fittest: 18 01238597890123456789 Generation: 56 Fittest: 18 01234667890123456784 Generation: 57 Fittest: 18 08234565890123456789 Generation: 58 Fittest: 19 01234567890123156789 Generation: 59 Fittest: 18 01234567890625456789 Generation: 60 Fittest: 18 04204567890123456789 Generation: 61 Fittest: 19 01234547890123456789 Generation: 62 Fittest: 19 05234567890123456789 Generation: 63 Fittest: 18 01232567890123456769 Generation: 64 Fittest: 18 01234567890123426759 Generation: 65 Fittest: 19 01234567890133456789 Generation: 66 Fittest: 18 01234561890133456789 Generation: 67 Fittest: 18 01234567590123456769 Generation: 68 Fittest: 19 01234567890193456789 Generation: 69 Fittest: 18 01234267890127456789 Generation: 70 Fittest: 18 01234567800123556789 Generation: 71 Fittest: 19 01234467890123456789 Generation: 72 Fittest: 18 01264567890123456799 Generation: 73 Fittest: 19 01234527890123456789 Generation: 74 Fittest: 19 01234567890123456739 Generation: 75 Fittest: 19 01034567890123456789 Generation: 76 Fittest: 18 07234567390123456789 Generation: 77 Fittest: 17 01211567893123456789 Generation: 78 Fittest: 17 00234567890145456789 Generation: 79 Fittest: 18 01211567890123456789 Generation: 80 Fittest: 18 01231567390123456789 Generation: 81 Fittest: 19 01234567800123456789 Generation: 82 Fittest: 18 01241567890123456789 Generation: 83 Fittest: 18 01241567890123456789 Generation: 84 Fittest: 19 01234567890423456789 Solution found: 01234567890123456789