Page 1
Lecture 9Lecture 9 Evolutionary Computation:Evolutionary Computation: Genetic algorithmsGenetic algorithms Introduction, or canIntroduction, or can evolutionevolution bebe intelligent?intelligent? Simulation of naturalSimulation of natural evolutionevolution Genetic algorithmsGenetic algorithms Case studyCase study:: maintenancemaintenance schedulingscheduling withwith genetic algorithmsgenetic algorithms SummarySummary Negnevitsky, Pearson Education, 2002Negnevitsky, Pearson Education, 2002 1
Page 2
Can evolution be intelligent?Can evolution be intelligent? Intelligence can be defined as the capability of aIntelligence can be defined as the capability of a system to adapt its behaviour to ever-changingsystem to adapt its behaviour to ever-changing environment. According to Alan Turing, the formenvironment. According to Alan Turing, the form or appearance of a system is irrelevant to itsor appearance of a system is irrelevant to its intelligence.intelligence. Evolutionary computation simulates evolution on aEvolutionary computation simulates evolution on a computer. The result of such a simulation is acomputer. The result of such a simulation is a series of optimisation algorithms, usually based onseries of optimisation algorithms, usually based on a simple set of rules. Optimisation iterativelya simple set of rules. Optimisation iteratively improves the quality of solutions until an optimal,improves the quality of solutions until an optimal, or at least feasible, solution is found.or at least feasible, solution is found. Negnevitsky, Pearson Education, 2002Negnevitsky, Pearson Education, 2002 2
Page 3
The behaviour of an individual organismThe behaviour of an individual organism isis anan inductive inference about some yet unknowninductive inference about some yet unknown aspects of its environment. If,aspects of its environment. If, over successiveover successive generations, the organism survives, we can saygenerations, the organism survives, we can say that this organism is capable of learning to predictthat this organism is capable of learning to predict changes in its environment.changes in its environment. The evolutionary approach is based onThe evolutionary approach is based on computational models of natural selection andcomputational models of natural selection and genetics. We call themgenetics. We call them evolutionaryevolutionary computationcomputation, an umbrella term that combines, an umbrella term that combines genetic algorithmsgenetic algorithms,, evolution strategiesevolution strategies andand genetic programminggenetic programming.. Negnevitsky, Pearson Education, 2002Negnevitsky, Pearson Education, 2002 3
Page 4
Simulation of naturalSimulation of natural evolutionevolution On 1 July 1858,On 1 July 1858, Charles DarwinCharles Darwin presented hispresented his theory of evolution before the Linneantheory of evolution before the Linnean Society ofSociety of London. This day marks the beginning of aLondon. This day marks the beginning of a revolution in biology.revolution in biology. Darwin’s classicalDarwin’s classical theory of evolutiontheory of evolution, together, together with Weismann’swith Weismann’s theory of natural selectiontheory of natural selection andand Mendel’s concept ofMendel’s concept of geneticsgenetics, now represent the, now represent the neo-Darwinian paradigm.neo-Darwinian paradigm. Negnevitsky, Pearson Education, 2002Negnevitsky, Pearson Education, 2002 4
Page 5
Neo-DarwinismNeo-Darwinism is based on processes ofis based on processes of reproduction, mutation, competition and selection.reproduction, mutation, competition and selection. The power to reproduce appears to be an essentialThe power to reproduce appears to be an essential property of life. The power to mutate is alsoproperty of life. The power to mutate is also guaranteed in any living organism that reproducesguaranteed in any living organism that reproduces itself in a continuously changing environment.itself in a continuously changing environment. Processes of competition and selection normallyProcesses of competition and selection normally take place in the natural world, where expandingtake place in the natural world, where expanding populations of different species are limited by apopulations of different species are limited by a finite space.finite space. Negnevitsky, Pearson Education, 2002Negnevitsky, Pearson Education, 2002 5
Page 6
Evolution can be seen as a process leading to theEvolution can be seen as a process leading to the maintenance of a population’smaintenance of a population’s ability to surviveability to survive and reproduce in a specific environment. Thisand reproduce in a specific environment. This ability is calledability is called evolutionary fitnessevolutionary fitness.. Evolutionary fitness can also be viewed as aEvolutionary fitness can also be viewed as a measure of the organism’s ability to anticipatemeasure of the organism’s ability to anticipate changes in its environment.changes in its environment. The fitness, or the quantitative measure of theThe fitness, or the quantitative measure of the ability to predict environmental changes andability to predict environmental changes and respond adequately, can be considered as therespond adequately, can be considered as the quality that is optimisedquality that is optimised in natural life.in natural life. Negnevitsky, Pearson Education, 2002Negnevitsky, Pearson Education, 2002 6
Page 7
How is a population with increasingHow is a population with increasing fitness generated?fitness generated? Let us consider a population of rabbits. SomeLet us consider a population of rabbits. Some rabbits are faster than others, and we may say thatrabbits are faster than others, and we may say that these rabbits possess superior fitness, because theythese rabbits possess superior fitness, because they have a greater chance of avoiding foxes, survivinghave a greater chance of avoiding foxes, surviving and then breeding.and then breeding. If two parents have superior fitness, there is a goodIf two parents have superior fitness, there is a good chance that a combination of their genes willchance that a combination of their genes will produce an offspring with even higher fitness.produce an offspring with even higher fitness. Over time the entire population of rabbits becomesOver time the entire population of rabbits becomes faster to meet their environmental challenges in thefaster to meet their environmental challenges in the face of foxes.face of foxes. Negnevitsky, Pearson Education, 2002Negnevitsky, Pearson Education, 2002 7
Page 8
Simulation of naturalSimulation of natural evolutionevolution All methods of evolutionary computation simulateAll methods of evolutionary computation simulate natural evolution by creatingnatural evolution by creating a population ofa population of individuals, evaluating their fitness, generating aindividuals, evaluating their fitness, generating a new population through genetic operations, andnew population through genetic operations, and repeating this process a number of times.repeating this process a number of times. We will start withWe will start with Genetic AlgorithmsGenetic Algorithms (GAs) as(GAs) as most of the other evolutionary algorithms can bemost of the other evolutionary algorithms can be viewed as variations of genetic algorithmsviewed as variations of genetic algorithms.. Negnevitsky, Pearson Education, 2002Negnevitsky, Pearson Education, 2002 8
Page 9
Genetic AlgorithmsGenetic Algorithms In the early 1970s, John Holland introduced theIn the early 1970s, John Holland introduced the concept of genetic algorithms.concept of genetic algorithms. His aim was to make computers do what natureHis aim was to make computers do what nature does. Holland was concerned withdoes. Holland was concerned with algorithmsalgorithms that manipulate strings of binary digits.that manipulate strings of binary digits. Each artificial “chromosomes” consists of aEach artificial “chromosomes” consists of a number of “genes”, and each gene is representednumber of “genes”, and each gene is represented by 0 or 1:by 0 or 1: 1 0 1 1 0 1 0 0 0 0 0 1 0 1 0 1 Negnevitsky, Pearson Education, 2002Negnevitsky, Pearson Education, 2002 9
Page 10
Nature has an ability to adapt and learn withoutNature has an ability to adapt and learn without being told what to do. In other words, naturebeing told what to do. In other words, nature finds good chromosomes blindly. GAsfinds good chromosomes blindly. GAs do thedo the same. Two mechanisms link a GA to the problemsame. Two mechanisms link a GA to the problem it is solving:it is solving: encodingencoding andand evaluationevaluation.. The GA uses a measure of fitness of individualThe GA uses a measure of fitness of individual chromosomes to carry out reproduction. Aschromosomes to carry out reproduction. As reproduction takes place, the crossover operatorreproduction takes place, the crossover operator exchanges parts of two single chromosomes, andexchanges parts of two single chromosomes, and the mutation operator changes the gene value inthe mutation operator changes the gene value in some randomly chosen location of thesome randomly chosen location of the chromosome.chromosome. Negnevitsky, Pearson Education, 2002Negnevitsky, Pearson Education, 2002 10
Page 11
Basic geneticBasic genetic algorithmsalgorithms Step 1:Step 1: Represent the problem variable domain asRepresent the problem variable domain as a chromosome of a fixed length, choose the sizea chromosome of a fixed length, choose the size of a chromosome populationof a chromosome population NN, the crossover, the crossover probabilityprobability pp and the mutation probabilityand the mutation probability pp .. cc mm Step 2Step 2:: Define a fitness function to measure theDefine a fitness function to measure the performance, or fitness, of an individualperformance, or fitness, of an individual chromosome in the problem domain. The fitnesschromosome in the problem domain. The fitness function establishes the basis for selectingfunction establishes the basis for selecting chromosomes that will be mated duringchromosomes that will be mated during reproduction.reproduction. Negnevitsky, Pearson Education, 2002Negnevitsky, Pearson Education, 2002 11
Page 12
Step 3:Step 3: Randomly generate an initial population ofRandomly generate an initial population of chromosomes of sizechromosomes of size NN:: xx ,, xx , . . . ,, . . . , xx 11 22 NN Step 4:Step 4: Calculate the fitness of each individualCalculate the fitness of each individual chromosome:chromosome: ff ((xx ),), ff ((xx ), . . . ,), . . . , ff ((xx )) 11 22 NN Step 5:Step 5: Select a pair of chromosomes for matingSelect a pair of chromosomes for mating from the current population. Parentfrom the current population. Parent chromosomes are selected with a probabilitychromosomes are selected with a probability related to their fitness.related to their fitness. Negnevitsky, Pearson Education, 2002Negnevitsky, Pearson Education, 2002 12
Page 13
Step 6:Step 6: Create a pair of offspring chromosomes byCreate a pair of offspring chromosomes by applying the genetic operatorsapplying the genetic operators −− crossovercrossover andand mutationmutation.. Step 7:Step 7: Place the created offspring chromosomesPlace the created offspring chromosomes in the new population.in the new population. Step 8:Step 8: RepeatRepeat Step 5Step 5 until the size of the newuntil the size of the new chromosome population becomes equal to thechromosome population becomes equal to the size of the initial population,size of the initial population, NN.. Step 9:Step 9: Replace the initial (parent) chromosomeReplace the initial (parent) chromosome population with the new (offspring) population.population with the new (offspring) population. Step 10Step 10:: Go toGo to Step 4Step 4, and repeat the process until, and repeat the process until the termination criterion is satisfied.the termination criterion is satisfied. Negnevitsky, Pearson Education, 2002Negnevitsky, Pearson Education, 2002 13
Page 14
Genetic algorithmsGenetic algorithms GA represents an iterative process. Each iteration isGA represents an iterative process. Each iteration is called acalled a generationgeneration. A typical number of generations. A typical number of generations for a simple GA can range from 50 to over 500. Thefor a simple GA can range from 50 to over 500. The entire set of generations is called aentire set of generations is called a runrun.. Because GAs use a stochastic search method, theBecause GAs use a stochastic search method, the fitness of a population may remain stable for afitness of a population may remain stable for a number of generations before a superior chromosomenumber of generations before a superior chromosome appears.appears. A common practice is to terminate a GA after aA common practice is to terminate a GA after a specified number of generations and then examinespecified number of generations and then examine the best chromosomes in the population. If nothe best chromosomes in the population. If no satisfactory solution is found, the GA is restarted.satisfactory solution is found, the GA is restarted. Negnevitsky, Pearson Education, 2002Negnevitsky, Pearson Education, 2002 14
Page 15
Genetic algorithmsGenetic algorithms:: casecase studystudy A simple example will help us to understand howA simple example will help us to understand how a GA works. Let us find the maximum value ofa GA works. Let us find the maximum value of the function (15the function (15xx −− xx22) where parameter) where parameter xx variesvaries between 0 and 15. For simplicity, we maybetween 0 and 15. For simplicity, we may assume thatassume that xx takes only integer values. Thus,takes only integer values. Thus, chromosomes can be built with only four genes:chromosomes can be built with only four genes: Integer Binary code Integer Binary code Integer Binary code 1 0 0 0 1 6 0 1 1 0 11 1 0 1 1 2 0 0 1 0 7 0 1 1 1 12 1 1 0 0 3 0 0 1 1 8 1 0 0 0 13 1 1 0 1 4 0 1 0 0 9 1 0 0 1 14 1 1 1 0 5 0 1 0 1 10 1 0 1 0 15 1 1 1 1 Negnevitsky, Pearson Education, 2002Negnevitsky, Pearson Education, 2002 15
Page 16
Suppose that the size of the chromosome populationSuppose that the size of the chromosome population NN is 6, the crossover probabilityis 6, the crossover probability pp equals 0.7, andequals 0.7, and cc the mutation probabilitythe mutation probability pp equals 0.001. Theequals 0.001. The mm fitness function in our example is defined byfitness function in our example is defined by ff((xx) = 15) = 15 xx −−−−−−−− xx22 Negnevitsky, Pearson Education, 2002Negnevitsky, Pearson Education, 2002 16
Page 17
The fitness function and chromosome locationsThe fitness function and chromosome locations C hrom osom e C hrom osom e Decoded C hrom osom e Fitness label string integer fitness ratio, % X1 1 1 0 0 12 36 16.5 X2 0 1 0 0 4 44 20.2 X3 0 0 0 1 1 14 6.4 X4 1 1 1 0 14 14 6.4 X5 0 1 1 1 7 56 25.7 X6 1 0 0 1 9 54 24.8 f(x) 60 60 50 50 40 40 30 30 20 20 10 10 0 0 0 5 10 15 0 5 10 15 x x (a) Chromosome initia l locations. (b) Chromosome final locations. Negnevitsky, Pearson Education, 2002Negnevitsky, Pearson Education, 2002 17
Page 18
In natural selection, only the fittest species canIn natural selection, only the fittest species can survive, breed, and thereby pass their genes on tosurvive, breed, and thereby pass their genes on to the next generation. GAsthe next generation. GAs use a similar approach,use a similar approach, but unlike nature, the size of the chromosomebut unlike nature, the size of the chromosome population remains unchanged from onepopulation remains unchanged from one generation to the next.generation to the next. The last column in Table shows the ratio of theThe last column in Table shows the ratio of the individual chromosome’s fitness to theindividual chromosome’s fitness to the population’s total fitness. This ratio determinespopulation’s total fitness. This ratio determines the chromosome’s chance of being selected forthe chromosome’s chance of being selected for mating. The chromosome’s average fitnessmating. The chromosome’s average fitness improves from one generation to the next.improves from one generation to the next. Negnevitsky, Pearson Education, 2002Negnevitsky, Pearson Education, 2002 18
Page 19
Roulette wheelRoulette wheel selectionselection The most commonly used chromosome selectionThe most commonly used chromosome selection techniques is thetechniques is the roulette wheel selectionroulette wheel selection.. 100 0 X1: 16.5% 16.5 X2: 20.2% 75.2 X3: 6.4% X4: 6.4% X5: 25.3% 36.7 X6: 24.8% 49.5 43.1 Negnevitsky, Pearson Education, 2002Negnevitsky, Pearson Education, 2002 19
Page 20
Crossover operatorCrossover operator In our example, we have an initial population of 6In our example, we have an initial population of 6 chromosomes. Thus, to establish the samechromosomes. Thus, to establish the same population in the next generation, the roulettepopulation in the next generation, the roulette wheel would be spun six times.wheel would be spun six times. Once a pair of parent chromosomes is selected,Once a pair of parent chromosomes is selected, thethe crossovercrossover operator is applied.operator is applied. Negnevitsky, Pearson Education, 2002Negnevitsky, Pearson Education, 2002 20
Affichage des 20 premières pages. Téléchargez le document pour le voir en entier.
Commentaires (0)
Aucun commentaire pour le moment. Soyez le premier !