Bài giảng Máy học nâng cao - Chương 14: Genetic Algorithm - Trịnh Tấn Đạt

Trịnh Tấn Đạt Khoa CNTT – Đại Học Sài Gòn Email: trinhtandat@sgu.edu.vn Website: https://sites.google.com/site/ttdat88/ Contents  Introduction: Genetic Algorithm (GA)  GA Operators and Parameters  Example  Homework Introduction History Of Genetic Algorithms  “Evolutionary Computing” was introduced in the 1960s by I. Rechenberg.  John Holland wrote the first book on Genetic Algorithms ‘Adaptation in Natural and Artificial Systems’ in 1975.  In 1992 John Koza used genetic algorithm to evolve programs to perform certain tasks. He called his method “Genetic Programming”. What Are Genetic Algorithms (GAs)?  GAs are search and optimization techniques based on Darwin’s Principle of Natural Selection and Genetic Inheritance.  A class of probabilistic optimization algorithms.  Widely-used in business, science and engineering. Basic Idea Of Principle Of Natural Selection “Select The Best, Discard The Rest” An Example of Natural Selection:  Rabbits are fast and smart  Some of them are faster and smarter than other rabbits. Thus, they are less likely to be eaten by foxes.  They have a better chance of survival and start breeding.  The resulting baby rabbits (on average) will be faster and smarter  Now, evolved species are more faster and smarter Genetic Algorithms Implement Optimization Strategies By Simulating Evolution Of Species Through Natural Selection Classes of Search Techniques Fibonacci Search Techniques Calculus Base Techniques Guided random search techniques Enumerative Techniques BFSDFS Dynamic Programming Tabu Search Hill Climbing Simulated Anealing Evolutionary Algorithms Genetic Programming Genetic Algorithms Sort Nature to Computer Mapping  GAs use a vocabulary borrowed from nature genetics Nature Computer (GAs) Population Set of solutions Individuals in environment Solutions to a problem Individual’s degree of adaptation to its surrounding environment Solutions quality (fitness function) Chromosome Encoding for a Solution Gene Part of the encoding of a solution Selection, crossover and mutation in nature’s evolutionary process Stochastic operators Working Mechanism Of GAs Simple Genetic Algorithm Simple_Genetic_Algorithm() { Initialize the Population; Calculate Fitness Function; While(Fitness Value != Optimal Value) { Selection;//Natural Selection, Survival Of Fittest Crossover;//Reproduction, Propagate favorable characteristics Mutation;//Mutation Calculate Fitness Function; } } Designing GAs ⚫ How to represent chromosomes? ⚫ How to create an initial population? ⚫ How to define fitness function? ⚫ How to define genetic operators? ⚫ How to generate next generation? ⚫ How to define stopping criteria? GA Operators and Parameters Search Space and Population  The search space S is the finite set of possible solutions.  Each solution x  S is called an individual  Population of size N is a subset of search space S.  Start with a population of randomly generated individuals, or use  A previously saved population  A set of solutions provided by a human expert  A set of solutions provided by another heuristic algorithm Representation (Encoding) The process of representing the solution in the form of a string (chromosome) that conveys the necessary information.  Just as in a chromosome, each gene controls a particular characteristic of the individual  Similarly, each bit in the string represents a characteristic of the solution. Binary Encoding Binary Encoding  Binary Encoding – Most common method of encoding. Chromosomes are strings of 1s and 0s  In classic genetic algorithms, binary strings of fixed length m are used.  In order to be able to encode each solution of the search space S in a one-to-one way, the inequality  For example, we have S={1,2,,15}. Choose m = 4 to represent 15 chromosomes ||2 Sm  1621528 43 == Value Encoding  Every chromosome is a string of some values.  Values can be anything connected to problem, form numbers, real numbers or chars to some complicated objects. Permutation Encoding  Permutation encoding can be used in ordering problems, such as travelling salesman problem or task ordering problem.  In permutation encoding, every chromosome is a string of numbers, which represents number in a sequence. Tree Encoding  Tree encoding is used mainly for evolving programs or expressions, for genetic programming.  In tree encoding every chromosome is a tree of some objects, such as functions or commands in programming language. Fitness function  A fitness value is assigned to each solution depending on how close it actually is to solving the problem.  A fitness function is a nonnegative function f A fitness function quantifies the optimality of a solution (chromosome) so that particular solution may be ranked against all the other solutions. f : S → R Genetic Operators  Reproduction (Selection) Copy existing chromosomes, chosen at random, to the new population.  Recombination (Crossover) Create new chromosomes by recombining randomly chosen substrings from existing chromosomes.  Mutation Create a new chromosome from an existing one by performing small random changes. Selection  The primary objective of the selection operator is to emphasize the good solutions and eliminate the bad solutions in a population, while keeping the population size constant.  “Selects The Best, Discards The Rest”.  Identify the good solutions in a population.  Make multiple copies of the good solutions.  Eliminate bad solutions from the population so that multiple copies of good solutions can be placed in the population The process that determines which solutions are to be preserved and allowed to reproduce and which ones deserve to die out Random Selection  Chromosomes are randomly selected from the population to be parents to crossover. Roulette Wheel Selection  Roulette Wheel Selection (fitness-proportional selection; stochastic sampling with replacement) is an instance of a reproduction operator:  Strings that are fitter are assigned a larger slot and hence have a better chance of appearing in the new population.  For example, after spinning 4 times, we have new population {2,4,2,1} Rank Selection  Rank selection first ranks the population and then every chromosome receives fitness from this ranking.  The worst will have fitness 1, second worst 2 etc. and the best will have fitness N (number of chromosomes in population). Elitism  When creating new population by crossover and mutation, we have a big chance, that we will loose the best chromosome.  Elitism is name of method, which first copies the best chromosome (or a few best chromosomes) to new population. The rest is done in classical way.  Elitism can very rapidly increase performance of GA, because it prevents losing the best found solution Tournament Selection  In K-Way tournament selection, we select K individuals from the population at random and select the best out of these to become a parent. Survivor Selection  The Survivor Selection Policy determines which individuals are to be kicked out and which are to be kept in the next generation  Some GAs employ Elitism. Age Based Selection  We don’t have a notion of a fitness  Each individual is allowed in the population for a finite generation where it is allowed to reproduce, after that, it is kicked out of the population no matter how good its fitness is. Fitness Based Selection  The children tend to replace the least fit individuals in the population Crossover  After selection, a specified percentage pc of chromosomes in the mating pool P'(t) is chosen at random.  The selected chromosomes are mated at random, and each pair of parents undergoes a crossover operation. It is the process in which two chromosomes (strings) combine their genetic material (bits) to produce a new offspring which possesses both their characteristics. The cross-over probability pc is another parameter of the genetic algorithm. Typical values are between 60% and 90%. One-point Crossover  A random point is chosen on the individual chromosomes (strings) and the genetic material is exchanged at this point. Two-Point Crossover  Two random points are chosen on the individual chromosomes (strings) and the genetic material is exchanged at these points. Chromosome1 11011 | 00100 | 110110 Chromosome 2 10101 | 11000 | 011110 Offspring 1 10101 | 00100 | 011110 Offspring 2 11011 | 11000 | 110110 Uniform crossover  Bits are randomly copied from the first or from the second parent Arithmetic crossover  Some arithmetic operation is performed to make a new offspring Tree crossover Partially Matched Crossover (PMX)  Used in Permutation Encoding Crossover  Crossover between 2 good solutions MAY NOT ALWAYS yield a better or as good a solution.  However, parents are good  probability of the child being good is high.  If offspring is not good (poor solution), it will be removed in the next iteration during “Selection”. Mutation  After crossover, a specified percentage pm of genes in the pool P’’(t) is chosen at random.  A selected parent chromosome undergoes a mutation. It is the process by which a string is deliberately changed so as to maintain diversity in the population set. The mutation probability pm is another parameter of the genetic algorithm. Typical values are below 1%. Mutation  The classical mutation operator is the Bit-flip Mutation Advantages Of GAs Global Search Methods:  GAs search for the function optimum starting from a population of points of the function domain, not a single one.  This characteristic suggests that GAs are global search methods.  Hill climbing (gradient descent - ascent) method  A new point is selected from the neighborhood of the current point based on its fitness value. local global GAs I am not at the top. My high is better! I am at the top Height is ... I will continue few microseconds after Advantages Of GAs Exploitation and Exploration:  Exploiting the best solutions  Takes the current search information from the experience of the last search to guide the search toward the direction that might be close to the best solutions.  From Selection operator and Crossover operator.  Exploring the search space  Widens the search to reach all possible solutions around the search space.  From Mutation operator and Crossover operator.  Important task: GAs can balance exploitation and exploration.  Too high exploitation leads to premature convergence  Too high exploration leads to non-convergence and to no fitter solution.  Hill climbing only exploits the best solution. It neglects exploration of search space. Advantages Of GAs Blind Search Methods  GAs only use the information about the fitness function to solve the optimal problem GAs use probabilistic transition rules  This makes them more robust and applicable to a large range of problems. GAs can be easily used in parallel machines  Reduce computation cost significantly. Applications Of GAs  Optimal problems  Wire routing  Scheduling  Adaptive control  Game playing  Database query optimal  Feature selection   GA Examples Maximum of Function  Let’s consider a function f Problem: find x0 such that  First derivative 1)10sin()( += xxxf  ]2,1[),()( 0 − xxfxf 0)10cos(10)10sin()(' =+= xxxxf         −−= + = = = − = ...2,1, 20 12 0 ...2,1, 20 12 0 i i x x i i x i i For x19=1.85, f(x19)=2.85 GA Examples How GAs can solve this problem ?!?  Representation (convert real numbers to chromosomes)  Using binary vectors as a chromosome  Length of chromosome m=22  The mapping from a binary string into a real number x from [-1, 2] is given by 2-1 3*106 real numbers  For example, a chromosome GA Examples  Initial population  Create randomly population, each chromosomes v is a binary string of 22 bits  Fitness function: eval(v)=f(x), 1)10sin()( += xxxf  v3 is the best of three chromosomes GA Examples  Mutation  Crossover x3’=1.721 and f(x3’)=-0.0822 x3’’=1.630 and f(x3’’)=2.343 On the other hand These offspring evaluate to The second offspring has a better evaluation than both of its parents f(v2)= 0.0788 f(v3)= 2.2506 GA Examples  Assume that pop_size=50, pc=25% and pm=1%  After 150 generations, we have GA Examples Traveling Salesman Problem (TPS) The travelling salesman must visit every city in his territory exactly once and then return back to the starting point. Given the cost of travel between all cities, how should he plan his itinerary for minimum total cost? Cost = {money, distance, time,.} GA Examples Binary Representation GA Examples Why we cannot use binary string Fail! Alternative: • Look for the most natural expression of the problem. • Create genetic operators that avoid building illegal chromosomes Nonbinary Representation GA Examples Swap Mutation The following mutation operator is adapted to the path representation: GA Examples Why we cannot use single-point crossover Fail! GA Examples PMX-Crossover Also Partially Matched Crossover (PMX) avoids building illegal chromosomes: How Do GAs Work?  Maximize a function of k variable, f(x1,,xk), where xi [ai,bi], and f(x1,,xk)>0 for all xi.  Representation (binary string) We divide [ai,bi] into (bi-ai)*10 4 equal size ranges For each xi → binary string of length mi satisfies To represent real value of a binary string Thus, each chromosome is represent by a binary string of length (bi-ai)*10 4  2mi - 1 v=(string1 string2stringk) GA Examples  Selection (Roulette wheel selection) GA Examples  Crossover(pc is probability of crossover)  Mutation (pm is probability of mutation)  For example, maximize the function [-3, 12.1] → 15.1*104 equal size ranges x1 → binary string of length 18 [4.1, 5.8] → 1.7 *104 equal size ranges x2 → binary string of length 15 GA Examples  The total length of a chromosome is m=18+15=33 bits GA Examples  Assume population of size (pop_size) equals 20. All 33 bits in all chromosome are initialized randomly Choose q11 and q4 ,etc. New population  Crossover with pc=2.5%. If r < 0.25, we select a given chromosome of crossover The chromosome v2’, v11’, v13’ and v18’ were selected for crossover  Mutation with pm=1%. We have 33*20=660 bits, we expect (on average) 6.6 mutation per generation. Generate 660 random numbers r , if r < 0.01, we mutate the bit After applying crossover and mutation, we have a new population New population Old population Conclusion  Genetic Algorithms (GAs) implement optimization strategies based on simulation of the natural law of evolution of a species by natural selection  The basic GA Operators are: Encoding Selection Crossover Mutation  GAs have been applied to a variety of function optimization problems.  GA s have been shown to be highly effective in searching a large, poorly defined search space even in the presence of difficulties such as high-dimensionality, discontinuity and noise. Homework 1) We're going to optimize a very simple problem: trying to create a list of N numbers that equal X when summed together.  EX1: N = 5 ; X = 8 ; one solution is [2, 0, 0 ,4, 2]  EX2: N = 5 and X = 200, then these would all be appropriate solutions. lst = [40,40,40,40,40] lst = [50,50,50,25,25] lst = [200,0,0,0,0] Ref : https://lethain.com/genetic-algorithms-cool-name-damn-simple/ Homework 2) Uses a genetic algorithm to maximize a function of many variables Ex 1 : Consider the function: z = f(x,y) -x^2+2x-y^2+4y Find (x*,y*) to z is maximum Ref: https://github.com/philipkiely/floydhub_genetic_algorithm_tutorial/blob/mast er/geneticmax.py Ex 2: The equation is shown below: Y = w1x1 + w2x2 + w3x3 + w4x4 + w5x5 + w6x6 Given inputs values are (x1,x2,x3,x4,x5,x6)=(4,-2,7,5,11,1). Find the parameters (weights) that maximize such equation Ref: https://towardsdatascience.com/genetic-algorithm-implementation-in- python-5ab67bb124a6 Homework 3) Evolution of a salesman Ref : https://towardsdatascience.com/evolution-of-a-salesman-a-complete- genetic-algorithm-tutorial-for-python-6fe5d2b3ca35