SOFT COMPUTING Evolutionary Computing（PPT讲稿）

SOFT COMPUTING Evolutionary Computing G

1 SOFT COMPUTING Evolutionary Computing

What is a ga? O GAs are adaptive heuristic search algorithm based on the evolutionary ideas of natural selection and genetics Q As such they represent an intelligent exploitation of a random search used to solve optimization problems o Although randomized, gas are by no means random instead they exploit historical information to direct the search into the region of better performance within the search space

What is a GA? ❑ GAs are adaptive heuristic search algorithm based on the evolutionary ideas of natural selection and genetics. ❑ As such they represent an intelligent exploitation of a random search used to solve optimization problems. ❑ Although randomized, GAs are by no means random, instead they exploit historical information to direct the search into the region of better performance within the search space

What is a ga? a The basic techniques of the GAs are designed to simulate processes in natural systems necessary for evolution, specially those follow the principles first laid down by Charles Darwin of survival of the fittest a Since in nature, competition among individuals for scanty resources results in the fittest individuals dominating over the weaker ones

What is a GA? ❑ The basic techniques of the GAs are designed to simulate processes in natural systems necessary for evolution, specially those follow the principles first laid down by Charles Darwin of "survival of the fittest.". ❑ Since in nature, competition among individuals for scanty resources results in the fittest individuals dominating over the weaker ones

Evolutionary Algorithms Genetic Evolution Programming Strategies Genetic Algorithms Classifier Evolutionary Systems Programming genetic representation of candidate solutions genetic operators selection scheme problem domain

Evolutionary Algorithms Genetic Programming Evolution Strategies Genetic Algorithms Evolutionary Programming Classifier Systems • genetic representation of candidate solutions • genetic operators • selection scheme • problem domain

History of GAs a Genetic Algorithms were invented to mimic some of the processes observed in natural evolution. Many people, biologists included, are astonished that life at the level of complexity that we observe could have evolved in the relatively short time suggested by the fossil record. a The idea with GA is to use this power of evolution to solve optimization problems. The father of the original Genetic Algorithm was John holland who invented it in the early 1970s

History of GAs ❑ Genetic Algorithms were invented to mimic some of the processes observed in natural evolution. Many people, biologists included, are astonished that life at the level of complexity that we observe could have evolved in the relatively short time suggested by the fossil record. ❑ The idea with GA is to use this power of evolution to solve optimization problems. The father of the original Genetic Algorithm was John Holland who invented it in the early 1970's

Classes of Search Techniques Search techniques Calculus-based techniques Guided random search techniques Enumerative techniques irect methods Indirect methods Evolutionary algorithms Simulated annealin Dynamic programming FS. BFS acci Newton I Evolutionary strategies Genetic algorithms Tabu Search Hill Climbing Genetic Programming Parallel Sequent Centralized Distributed Steady-stateGenerational

Classes of Search Techniques Finonacci Newton Direct methods Indirect methods Calculus-based techniques Evolutionary strategies Centralized Distributed Parallel Steady-state Generational Sequential Genetic algorithms Evolutionary algorithms Simulated annealing Guided random search techniques Dynamic programming Enumerative techniques Search techniques Tabu Search Hill Climbing DFS, BFS Genetic Programming

Early History of EAs Q 1954: Barricelli creates computer simulation of life- Artificial Life o 1957: Box develops Evolutionary Operation(EvOP), a non-computerised evolutionary process Q 1957: Fraser develops first Genetic Algorithm o 1958: Friedberg creates a learning machine through evolving computer programs Q 1960s, Rechenverg: evolution strategies aa method used to optimize real-valued parameters for devices 0 1960s, Fogel, Owens, and Walsh: evolutionary programming o to find finite- state machines Q 1960s, John Holland: Genetic Algorithms a to study the phenomenon of adaptation as it occurs in nature(not to solve specific problems) 1965: Rechenberg Schwefel independently develop Evolution Strategies Q 1966: L Fogel develops Evolutionary Programming as a means of creating artificial intelligence 0 1967: Holland and his students extend GA ideas further

Early History of EAs ❑ 1954: Barricelli creates computer simulation of life – Artificial Life ❑ 1957: Box develops Evolutionary Operation (EVOP), a non-computerised evolutionary process ❑ 1957: Fraser develops first Genetic Algorithm ❑ 1958: Friedberg creates a learning machine through evolving computer programs ❑ 1960s, Rechenverg: evolution strategies ❑ a method used to optimize real-valued parameters for devices ❑ 1960s, Fogel, Owens, and Walsh: evolutionary programming ❑ to find finite-state machines ❑ 1960s, John Holland: Genetic Algorithms ❑ to study the phenomenon of adaptation as it occurs in nature (not to solve specific problems) ❑ 1965: Rechenberg & Schwefel independently develop Evolution Strategies ❑ 1966: L. Fogel develops Evolutionary Programming as a means of creating artificial intelligence ❑ 1967: Holland and his students extend GA ideas further

The Genetic Algorithm a Directed search algorithms based on the mechanics of biological evolution a Developed by John Holland, University of Michigan(1970s) a To understand the adaptive processes of natural systems a To design artificial systems software that retains the robustness of natural systems a The genetic algorithms, first proposed by Holland (1975), seek to mimic some of the natural evolution and selection a The first step of Holland's genetic algorithm is to represent a legal solution of a problem by a string of genes known as a chromosome

The Genetic Algorithm ❑ Directed search algorithms based on the mechanics of biological evolution ❑ Developed by John Holland, University of Michigan (1970’s) ❑ To understand the adaptive processes of natural systems ❑ To design artificial systems software that retains the robustness of natural systems ❑ The genetic algorithms, first proposed by Holland (1975), seek to mimic some of the natural evolution and selection. ❑ The first step of Holland’s genetic algorithm is to represent a legal solution of a problem by a string of genes known as a chromosome

Evolutionary Programming o First developed by lawrence Fogel in 1966 for use in pattern learning a Early experiments dealt with a number of Finite State Automata a FSA were developed that could recognise recurring patterns and even primeness of numbers a Later experiments dealt with gaming problems (coevolution) a More recently has been applied to training of neural networks, function optimisation path planning problems

Evolutionary Programming ❑ First developed by Lawrence Fogel in 1966 for use in pattern learning ❑ Early experiments dealt with a number of Finite State Automata ❑ FSA were developed that could recognise recurring patterns and even primeness of numbers ❑ Later experiments dealt with gaming problems (coevolution) ❑ More recently has been applied to training of neural networks, function optimisation & path planning problems

Biological Terminology gene functional entity that codes for a specific feature e.g. eye color set of possible alleles ·aee value of a gene e.g. blue, green, brown codes for a specific variation of the gene/feature · locus position of a gene on the chromosome genome set of all genes that define a species the genome of a specific individual is called genotype the genome of a living organism is composed of several chromosomes population set of competing genomes/individuals

Biological Terminology • gene • functional entity that codes for a specific feature e.g. eye color • set of possible alleles • allele • value of a gene e.g. blue, green, brown • codes for a specific variation of the gene/feature • locus • position of a gene on the chromosome • genome • set of all genes that define a species • the genome of a specific individual is called genotype • the genome of a living organism is composed of several chromosomes • population • set of competing genomes/individuals