In Computer Science and Operations Research, a Genetic Algorithm (GA) is a metaheuristic one that is inspired by the process of natural selection that belongs to the larger class of evolutionary algorithms (EA). Genetic algorithms are commonly used to generate high-quality solutions to optimize and search problems by relying on bio-inspired operators such as mutation, crossover and selection. John Holland introduced Genetic Algorithm (GA) in 1960 based on the concept of Darwin's theory of evolution; afterwards, his student Goldberg extended GA in 1989.
Evolutionary algorithms are a family of optimization algorithms based on the principle of Darwinian natural selection. As part of natural selection, a given environment has a population of individuals that compete for survival and reproduction. The ability of each individual to achieve these goals determines their chance to have children, in other words to pass on their genes to the next generation of individuals, who for genetic reasons will have an increased chance of doing well, even better, in realizing these two objectives.
This principle of continuous improvement over the generations is taken by evolutionary algorithms to optimize solutions to a problem. In the initial generation, a population composed of different individuals is generated randomly or by other methods. An individual is a solution to the problem, more or less good: the quality of the individual in regards to the problem is called fitness, which reflects the adequacy of the solution to the problem to be solved. The higher the fitness of an individual, the higher it is likely to pass some or all of its genotype to the individuals of the next generation.
An individual is coded as a genotype, which can have any shape, such as a bit vector (genetic algorithms) or a vector of real (evolution strategies). Each genotype is transformed into a phenotype when assessing the individual, i.e. when its fitness is calculated. In some cases, the phenotype is identical to the genotype: it is called direct coding. Otherwise, the coding is called indirect. For example, suppose you want to optimize the size of a rectangular parallelepiped defined by its length, height and width. To simplify the example, assume that these three quantities are integers between 0 and 15. We can then describe each of them using a 4-bit binary number. An example of a potential solution may be to genotype 0001 0111 01010. The corresponding phenotype is a parallelepiped of length 1, height 7 and width 10.
During the transition from the old to the new generation are called variationoperators, whose purpose is to manipulate individuals. There are two distinct types of variation operators:
Evolutionary algorithms have proven themselves in various fields such as operations research, robotics, biology, nuance, or cryptography. In addition, they can optimize multiple objectives simultaneously and can be used as black boxes because they do not assume any properties in the mathematical model to optimize. Their only real limitation is the computational complexity.
What is a genetic algorithm?
Evolutionary algorithms are a family of optimization algorithms based on the principle of Darwinian natural selection. As part of natural selection, a given environment has a population of individuals that compete for survival and reproduction. The ability of each individual to achieve these goals determines their chance to have children, in other words to pass on their genes to the next generation of individuals, who for genetic reasons will have an increased chance of doing well, even better, in realizing these two objectives.
This principle of continuous improvement over the generations is taken by evolutionary algorithms to optimize solutions to a problem. In the initial generation, a population composed of different individuals is generated randomly or by other methods. An individual is a solution to the problem, more or less good: the quality of the individual in regards to the problem is called fitness, which reflects the adequacy of the solution to the problem to be solved. The higher the fitness of an individual, the higher it is likely to pass some or all of its genotype to the individuals of the next generation.
An individual is coded as a genotype, which can have any shape, such as a bit vector (genetic algorithms) or a vector of real (evolution strategies). Each genotype is transformed into a phenotype when assessing the individual, i.e. when its fitness is calculated. In some cases, the phenotype is identical to the genotype: it is called direct coding. Otherwise, the coding is called indirect. For example, suppose you want to optimize the size of a rectangular parallelepiped defined by its length, height and width. To simplify the example, assume that these three quantities are integers between 0 and 15. We can then describe each of them using a 4-bit binary number. An example of a potential solution may be to genotype 0001 0111 01010. The corresponding phenotype is a parallelepiped of length 1, height 7 and width 10.
During the transition from the old to the new generation are called variationoperators, whose purpose is to manipulate individuals. There are two distinct types of variation operators:
- the mutation operators, which are used to introduce variations within the same individual, as genetic mutations;
- the crossover operators, which are used to cross at least two different genotypes, as genetic crosses from breeding.
Evolutionary algorithms have proven themselves in various fields such as operations research, robotics, biology, nuance, or cryptography. In addition, they can optimize multiple objectives simultaneously and can be used as black boxes because they do not assume any properties in the mathematical model to optimize. Their only real limitation is the computational complexity.
Applications:
- Artificial creativity
- Audio watermark detection
- Automated design = computer-automated design
- Automated design of mechatronic systems using bond graphs and genetic programming (NSF).
- Automated design of industrial equipment using catalogs of exemplar lever patterns.
- Automated design of sophisticated trading systems in the financial sector.
- Automated design, including research on composite material design and multi-objective design of automotive components for crashworthiness, weight savings, and other characteristics.
- Bayesian inference ([1] links to particle methods in Bayesian statistics and hidden Markov chain models and [2] a tutorial on genetic particle models)
- Bioinformatics multiple sequence alignment.[1]
- Bioinformatics: RNA structure prediction.[2]
- Bioinformatics: Multiple Sequence Alignment.[3] SAGA is available on:.[4]
- Bioinformatics: Motif Discovery.[5]
- Biology and computational chemistry ([3] links to particle methods in biology and computational chemistry and [4] an article on genetic particle models)
- Building phylogenetic trees.[6]
- Calculation of bound states and local-density approximations.
- Chemical kinetics (gas and solid phases)
- Clustering. Using genetic algorithms to optimize a wide range of different fit-functions.[7]
- Code-breaking, using the GA to search large solution spaces of ciphers for the one correct decryption.[8]
- Computer-automated design [9]
- Configuration applications, particularly physics applications of optimal molecule configurations for particular systems like C60 (buckyballs).
- Construction of facial composites of suspects by eyewitnesses in forensic science.[10]
- Container loading optimization.
- Control engineering,.[11][12][13]
- Data Center/Server Farm.[14]
- Design of water distribution systems.
- Distributed computer network topologies.
- Electronic circuit design, known as evolvable hardware.
- Gene expression profiling analysis.[15]
- Feynman-Kac models ([5] links to genetic type particle interpretations, [6] a review article on genetic particle models, and a research monograph [7])
- Financial Mathematics ([8] links to particle methods in mathematical finance and [9] a tutorial on genetic particle models)
- File allocation for a distributed system.
- Filtering and signal processing ([10] links to particle filters and [11] a tutorial on genetic particle models)
- Finding hardware bugs.[16][17]
- Game theory equilibrium resolution.
- Genetic Algorithm for Rule Set Production
- Economics
- Scheduling applications, including job-shop scheduling. The objective being to schedule jobs in a sequence-dependent or non-sequence-dependent setup environment in order to maximize the volume of production while minimizing penalties such as tardiness.
- Learning robot behavior using genetic algorithms.
- Learning fuzzy rule base using genetic algorithms.
- Linguistic analysis, including grammar induction and other aspects of Natural language processing (NLP) such as word sense disambiguation.
- Marketing mix analysis
- Mechanical engineering[18][19]
- Mobile communications infrastructure optimization.
- Molecular structure optimization (chemistry).
- Multidimensional systems
- Multimodal Optimization [20][21][22]
- Multiple criteria production scheduling.[23]
- Multiple population topologies and interchange methodologies.
- Mutation testing
- Neural Networks; particularly recurrent neural networks[24]
- Operon prediction.[25]
- Optimisation of data compression systems, for example using wavelets.
- Parallelization of GAs/GPs including use of hierarchical decomposition of problem domains and design spaces nesting of irregular shapes using feature matching and GAs.
- Plant floor layout.
- Pop music record producer.[26]
- Power electronics design.[27]
- Protein folding and protein/ligand docking.[28][29]
- Quality control
- Rare event analysis ([12] links to particle rare event simulation and [13] a review article)
- Representing rational agents in economic models such as the cobweb model.
- Selection of optimal mathematical model to describe biological systems.
- Software engineering[citation needed]
- Solving the machine-component grouping problem required for cellular manufacturing systems.
- Stochastic optimization ([14] links to particle methods in regulation, optimization, and optimal control)
- Tactical asset allocation and international equity strategies.
- Timetabling problems, such as designing a non-conflicting class timetable for a large university.
- Training artificial neural networks when pre-classified training examples are not readily obtainable (neuroevolution).
- Traveling salesman problem.
- Wireless sensor/ad-hoc networks
- Artificial creativity
- Audio watermark detection
- Automated design = computer-automated design
- Automated design of mechatronic systems using bond graphs and genetic programming (NSF).
- Automated design of industrial equipment using catalogs of exemplar lever patterns.
- Automated design of sophisticated trading systems in the financial sector.
- Automated design, including research on composite material design and multi-objective design of automotive components for crashworthiness, weight savings, and other characteristics.
- Bayesian inference ([1] links to particle methods in Bayesian statistics and hidden Markov chain models and [2] a tutorial on genetic particle models)
- Bioinformatics multiple sequence alignment.[1]
- Bioinformatics: RNA structure prediction.[2]
- Bioinformatics: Multiple Sequence Alignment.[3] SAGA is available on:.[4]
- Bioinformatics: Motif Discovery.[5]
- Biology and computational chemistry ([3] links to particle methods in biology and computational chemistry and [4] an article on genetic particle models)
- Building phylogenetic trees.[6]
- Calculation of bound states and local-density approximations.
- Chemical kinetics (gas and solid phases)
- Clustering. Using genetic algorithms to optimize a wide range of different fit-functions.[7]
- Code-breaking, using the GA to search large solution spaces of ciphers for the one correct decryption.[8]
- Computer-automated design [9]
- Configuration applications, particularly physics applications of optimal molecule configurations for particular systems like C60 (buckyballs).
- Construction of facial composites of suspects by eyewitnesses in forensic science.[10]
- Container loading optimization.
- Control engineering,.[11][12][13]
- Data Center/Server Farm.[14]
- Design of water distribution systems.
- Distributed computer network topologies.
- Electronic circuit design, known as evolvable hardware.
- Gene expression profiling analysis.[15]
- Feynman-Kac models ([5] links to genetic type particle interpretations, [6] a review article on genetic particle models, and a research monograph [7])
- Financial Mathematics ([8] links to particle methods in mathematical finance and [9] a tutorial on genetic particle models)
- File allocation for a distributed system.
- Filtering and signal processing ([10] links to particle filters and [11] a tutorial on genetic particle models)
- Finding hardware bugs.[16][17]
- Game theory equilibrium resolution.
- Genetic Algorithm for Rule Set Production
- Economics
- Scheduling applications, including job-shop scheduling. The objective being to schedule jobs in a sequence-dependent or non-sequence-dependent setup environment in order to maximize the volume of production while minimizing penalties such as tardiness.
- Learning robot behavior using genetic algorithms.
- Learning fuzzy rule base using genetic algorithms.
- Linguistic analysis, including grammar induction and other aspects of Natural language processing (NLP) such as word sense disambiguation.
- Marketing mix analysis
- Mechanical engineering[18][19]
- Mobile communications infrastructure optimization.
- Molecular structure optimization (chemistry).
- Multidimensional systems
- Multimodal Optimization [20][21][22]
- Multiple criteria production scheduling.[23]
- Multiple population topologies and interchange methodologies.
- Mutation testing
- Neural Networks; particularly recurrent neural networks[24]
- Operon prediction.[25]
- Optimisation of data compression systems, for example using wavelets.
- Parallelization of GAs/GPs including use of hierarchical decomposition of problem domains and design spaces nesting of irregular shapes using feature matching and GAs.
- Plant floor layout.
- Pop music record producer.[26]
- Power electronics design.[27]
- Protein folding and protein/ligand docking.[28][29]
- Quality control
- Rare event analysis ([12] links to particle rare event simulation and [13] a review article)
- Representing rational agents in economic models such as the cobweb model.
- Selection of optimal mathematical model to describe biological systems.
- Software engineering[citation needed]
- Solving the machine-component grouping problem required for cellular manufacturing systems.
- Stochastic optimization ([14] links to particle methods in regulation, optimization, and optimal control)
- Tactical asset allocation and international equity strategies.
- Timetabling problems, such as designing a non-conflicting class timetable for a large university.
- Training artificial neural networks when pre-classified training examples are not readily obtainable (neuroevolution).
- Traveling salesman problem.
- Wireless sensor/ad-hoc networks
How can I do N- queens problem using genetic algorithm implementation in Python? - Example
The N Queen is the problem of placing N chess queens on an N×N chessboard so that no two
queens attack each other. For example, following is a solution for 4 Queen problem.
queens attack each other. For example, following is a solution for 4 Queen problem.
The expected output is a binary matrix which has 1s for the blocks where queens are placed.
For example, following is the output matrix for above 4 queen solution.
For example, following is the output matrix for above 4 queen solution.
{ 0, 1, 0, 0}
{ 0, 0, 0, 1}
{ 1, 0, 0, 0}
{ 0, 0, 1, 0}
Solution:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 | import math; import random; from bitarray import bitarray; import sys; mutate_prob = 0.05 # Small probability with which mutation will occur. class Population(object): population_list = [] # List of individuals: binary strings which represent tentative solutions. fitness_list = [] # List of the fitness values of each individual in the population. pop_size = 0 # Population Size. board_size = 0 # Size of problem. 'N' in N-Queen. pos_bits_size = 0 # Number of bits required to represent each vertical position. indv_size = 0 # The total size of an 'induvidual' binary string. def __init__(self, pop_size, board_size): self.pop_size = pop_size self.board_size = board_size self.population_list = [] self.pos_bits_size = int(math.ceil(math.log(board_size-1))) + 1 self.indv_size = board_size * self.pos_bits_size def genPopulation(self): """Generates a population of bitarray strings (individuals) to solve the N-Queen problem, here N = 'board_size'. 'pop_size' parameter decides the number of bitarray strings (individuals) generated by this function. Creates a list of bitarrray strings (individuals) representing the population for solving the N-Queen problem. 'population_list' parameter holds the list of generated individuals.""" self.population_list = [] for i in xrange(0, self.pop_size): individual = bitarray(self.indv_size) # Loop for randomizing the 'individual' string. for j in xrange(0, self.board_size): vert_pos = random.randint(0, self.board_size-1) vert_pos_bitnum = toBitArray(vert_pos, self.pos_bits_size) # print "\t\t", j, vert_pos_bitnum, vert_pos for k in range(0, self.pos_bits_size): individual[j * self.pos_bits_size + k] = vert_pos_bitnum[k] self.population_list.append(individual) # print "\t", i, individual def computeFitnessList(self,fitnessFunction): """Populates the fitness list with fitness function values of co-responding entries in the population list.""" self.fitness_list = [] cmlsum = 0 for individual in self.population_list: cmlsum = cmlsum + fitnessFunction(individual, self.board_size, self.pos_bits_size) self.fitness_list.append(cmlsum) def findInFitnessList(self, key): """Binary Search for finding appropriate index for key in fitness list.""" low = 0 high = len(self.fitness_list) mid = 0 while(low <= high): mid = (low + high)/2 if key > self.fitness_list[mid]: low = mid + 1 elif key < self.fitness_list[mid]: high = mid - 1 else: break if low > high: return low else: return mid def toBitArray(number, size): """Converts a number in int format to a bitarray of length 'size', in binary representation. Returns the bitarray.""" temp_bitnum = bitarray(64) count = 0 number = number & 0xFFFFFFFFFFFFFFFF # enforces the number to be 64 bit. while count < size: temp_bitnum[63 - count] = (number % 2) # print "digit ", count, " : ", (number % 2) number = number >> 1 count = count + 1 return temp_bitnum[-size:] def fromBitArray(bitnum): """Converts a bitarray in binary format to a number in int format, to its co-responding decimal representation. Returns the number.""" number = 0 & 0xFFFFFFFFFFFFFFFF # enforces the number to be 64 bit. idx = len(bitnum) - 1 number = number + bitnum[idx] idx = idx - 1 count = 1 while idx != -1: number = number + (bitnum[idx] << count) count = count + 1 idx = idx - 1 return number def fitnessFunction(individual, board_size, pos_bits_size): """Calculates the finess value of an individual and returns it. Has a computational complexity of O(1) per piece.""" right_diag = [0] * (2 * board_size - 1) left_diag = [0] * (2 * board_size - 1) vertical = [0] * board_size conflicts = 0 idx = 0 while idx < board_size: # print "idx: ",idx,individual[idx * pos_bits_size : idx * pos_bits_size + pos_bits_size] vpos = fromBitArray(individual[idx * pos_bits_size : idx * pos_bits_size + pos_bits_size]) # print "vpos: ", vpos + 1 if vertical[vpos] != 0: conflicts = conflicts + vertical[vpos] vertical[vpos] = vertical[vpos] + 1 if left_diag[vpos + idx] != 0: conflicts = conflicts + left_diag[vpos + idx] left_diag[vpos + idx] = left_diag[vpos + idx] + 1 if right_diag[vpos + board_size - idx - 1] != 0: conflicts = conflicts + right_diag[vpos + board_size - idx - 1] right_diag[vpos + board_size - idx - 1] = right_diag[vpos + board_size - idx - 1] + 1 idx = idx + 1 return (board_size * (board_size - 1))/2 - conflicts def geneticAlgorithm(population, fitnessFunction): global mutate_prob child = None condition = True while condition: population.computeFitnessList(fitnessFunction) new_pop = [] for i in xrange(0,len(population.population_list)): parent_x = None parent_y = None (parent_x, parent_y) = randomSelection(population) child = reproduce(parent_x, parent_y, population) if mutate_prob > random.random(): mutate(child, population) new_pop.append(child) population.population_list = new_pop condition = (fitnessFunction(child, population.board_size, population.pos_bits_size) != \ (population.board_size * (population.board_size - 1))/2) # check condition return child def randomSelection(population): rand_sel_x = random.randint(1, population.fitness_list[len(population.fitness_list) - 1]) parent_x_idx = population.findInFitnessList(rand_sel_x) range_rem = population.fitness_list[parent_x_idx] if rand_sel_x > population.fitness_list[0]: range_rem = range_rem - population.fitness_list[parent_x_idx - 1] rand_sel_y = random.randint(1, population.fitness_list[len(population.fitness_list) - 1] - range_rem) if rand_sel_y >= rand_sel_x: rand_sel_y = rand_sel_y + range_rem parent_y_idx = population.findInFitnessList(rand_sel_y) parent_x = population.population_list[parent_x_idx] parent_y = population.population_list[parent_y_idx] return (parent_x, parent_y) def reproduce(parent_x, parent_y, population): crossover_pt = random.randint(1, population.board_size - 1) # print crossover_pt return parent_x[:crossover_pt * population.pos_bits_size] + \ parent_y[crossover_pt * population.pos_bits_size:] def mutate(child, population): rand_idx = random.randint(0, population.board_size - 1) rand_vpos = random.randint(0, population.board_size - 1) temp_bitnum = toBitArray(rand_vpos, population.pos_bits_size) # print "mutate: ", rand_idx, temp_bitnum for i in range(0, population.pos_bits_size): child[rand_idx * population.pos_bits_size + i] = temp_bitnum[i] new_pop = Population(int(sys.argv[1]),int(sys.argv[2])) new_pop.genPopulation() result = geneticAlgorithm(new_pop,fitnessFunction) for i in range(0,new_pop.board_size): print fromBitArray(result[i * new_pop.pos_bits_size : i * new_pop.pos_bits_size + new_pop.pos_bits_size]) + 1, |
3 Comments
Fantastic! Your blog was very interesting to read. I appreciate you sharing it. This is great information. Here are some articles I've suggested on Click-Per-Second Rates. Using a website called Click Speed Test, you can determine how many clicks you make per second in Minecraft. To find out how fast you can click, check out CPS Test's online blog.
ReplyDeleteyou keep publishing such good speculations I will share them with my friends
ReplyDeleteMumbai | Andheri | Bandra |
You have made our job easy by publishing your good important information
ReplyDeleteMumbai | Andheri | Vashi | Bandra