generic optimization techniques lecture slides

Genetic Algorithms Natural Evolution  Charles Darwin presented his theory of evolution before the Linnean Society of London. This day marks the beginning of a revolution in biology.  Darwin’s classical theory of evolution, together with Weismann’s theory of natural selection and Mendel’s concept of genetics, now represent the neo-Darwinian paradigm.

 Neo-Darwinism is based on processes of reproduction, mutation, competition and selection.  The power to reproduce appears to be an essential property of life.  The power to mutate is also guaranteed in any living organism that reproduces itself in a continuously changing environment.  Processes of competition and selection normally take place in the natural world, where expanding populations of different species are limited by a finite space. Natural Evolution

 Evolution can be seen as a process leading to the maintenance of a population’s ability to survive and reproduce in a specific environment. This ability is called evolutionary fitness.  Evolutionary fitness can also be viewed as a measure of the organism’s ability to anticipate changes in its environment.  The fitness, or the quantitative measure of the ability to predict environmental changes and respond adequately, can be considered as the quality that is optimized in natural life. Natural Evolution

 If two parents have superior fitness, there is a good chance that a combination of their genes will produce an offspring with even higher fitness.  Genetic Algorithms follow the idea of SURVIVAL OF THE FITTEST- Better and better solutions evolve from previous generations until a near optimal solution is obtained.  Natural Evolution

Natural Evolution  All methods of evolutionary computation simulate natural evolution by  creating a population of individuals,  evaluating their fitness,  generating a new population through genetic operations,  And repeating this process a number of times.

The evolution by GA works on the principles of biology Organisms (animals or plants) produce a number of offspring which are almost, but not entirely, like themselves Variation may be due to sexual reproduction (offspring have some characteristics from each parent) in GA it is Cross Over. INTELLIGENT EVOLUTION?

Random changes Variation may be due mutation Some of these offspring may survive to produce offspring of their own, others may not . . The “better adapted” offspring are more likely to survive Over time, later generations become better and better adapted The idea of Genetic Algorithms is based on the same process to “evolve” better programs INTELLIGENT EVOLUTION?

 Intelligence can be defined as the capability of a system to adapt its behavior to ever-changing environment.  Evolutionary computation simulates evolution on a computer. The result of such a simulation is a series of optimization algorithms, usually based on a simple set of rules. Optimization iteratively improves the quality of solutions until an optimal, or at least feasible, solution is found. INTELLIGENT EVOLUTION?

 The behavior of an individual organism is an inductive inference about some yet unknown aspects of its environment. If, over successive generations, the organism survives, we can say that this organism is capable of learning to predict changes in its environment.  The evolutionary approach is based on computational models of natural selection and genetics. We call them evolutionary computation, a term that combines genetic algorithms, evolution strategies and genetic programming. INTELLIGENT EVOLUTION?

GENETIC ALGORITHMS An algorithm is a set of instructions that is repeated to solve a problem. A genetic algorithm conceptually follows steps inspired by the biological processes of evolution.

GENETIC ALGORITHMS Also known as evolutionary algorithms, genetic algorithms demonstrate self organization and adaptation similar to the way that the fittest biological organism survive and reproduce. A genetic algorithm is an iterative procedure that represents its candidate solutions as strings of genes called chromosomes. Genetic Algorithms are often used to improve the performance of other AI methods such as expert systems or neural networks. The method learns by producing offspring that are better and better as measured by a fitness function, which is a measure of the objective to be obtained (maximum or minimum).

GENETIC ALGORITHMS It’s a class of probabilistic optimization algorithms Inspired by the biological evolution process Uses concepts of “Natural Selection” and “Genetic Inheritance” Particularly well suited for hard problems where little is known about the underlying search space It is now Widely-used in business, science and engineering A genetic algorithm maintains a population of candidate solutions for the problem at hand, and makes it evolve by iteratively applying a set of stochastic operators

GENETIC ALGORITHMS AS OPTIMIZATION TECHNIQUE Search Techniqes Guided Random Search Techniqes Evolutionary Algorithms Genetic Algorithms

Stochastic operators Selection replicates the most successful solutions found in a population at a rate proportional to their relative quality Recombination decomposes two distinct solutions and then randomly mixes their parts to form novel solutions Mutation randomly perturbs a candidate solution

BIOLOGICAL Analogies with GA’s Nature Genetic Algorithm Environment Optimization problem Individuals living in that environment Feasible solutions Individual’s degree of adaptation to its surrounding environment Solutions quality (fitness function)

BIOLOGICAL Analogies with ga’s Nature Genetic Algorithm A population of organisms (species) A set of feasible solutions Selection, recombination and mutation in nature’s evolutionary process Stochastic operators Evolution of populations to suit their environment Iteratively applying a set of stochastic operators on a set of feasible solutions

Nature Genetic Algorithm Gene Each bit in chromosomes Chromosomes A string of bits Population A set of chromosomes BIOLOGICAL ANALOGIES WITH GA’s

Genotypes and phenotypes? Genes are the basic “instructions” for building an organism A chromosome is a sequence of genes Biologists distinguish between an organism’s genotype (the genes and chromosomes) and its phenotype (what the organism actually is like) “Genes” may describe a possible solution to a problem, without actually being the solution

Genotype space Phenotype space Encoding Decoding 011101001 010001001 10010010 10010001 Genotypes and phenotypes?

Genotypes and Phenotypes? Phenotype: the "outward, physical manifestation" of an organism. The physical parts, the sum of the atoms, molecules, macromolecules, cells, structures, metabolism, energy utilization, tissues, organs, reflexes and behaviors; anything that is part of the observable structure, function or behavior of a living organism. Genotype: This is the "internally coded, heritable information" carried by all living organisms. This stored information is used as a "blueprint" or set of instructions for building and maintaining a living creature.

Encoding Bit strings Real numbers Permutations of element Lists of rules Program elements Any data structure REPRESENTATION

Representing the Genotype Candidate Solutions GAs can have the following types of representations: Binary-Coded; Encoding as Vectors of integers; Vectors of real numbers; Vectors of binary bits; Combination of the previous types; Binary-Coded GAs must decode a chromosome into a candidate solution (CS), evaluate the CS and return the resulting fitness back to the binary-coded chromosome representing the evaluated CS.

Use a data structure as close as possible to the natural representation Write appropriate genetic operators as needed If possible, ensure that all genotypes correspond to feasible solutions If possible, ensure that genetic operators reserve feasibility While choosing an encoding method keep the following key ideas in consideration Representing the Genotype Candidate Solutions

Process of Genetic Algorithm • Produce an initial population of individuals • Evaluate the fitness of all individuals • while termination condition not met do • Select fitter individuals for reproduction • Recombine between individuals • Mutate individuals • Evaluate the fitness of the modified individuals • Generate a new population • End while

Process of Genetic Algorithm  Problem Definition input  Encoding principles (gene, chromosome)  Initialization procedure (creation)  Selection of parents (reproduction)  Genetic operators (mutation, recombination)  Evaluation function (environment)  Termination condition

The crossover operator exchanges parts of two single chromosomes, and the mutation operator changes the gene value in some randomly chosen location of the chromosome. GA OPERATOR The fitness of a chromosome determines how likely it is that it will reproduce. Fitness is usually measured in terms of how well the chromosome solves some goal problem. E.g., if the genetic algorithm is to be used to sort numbers then the fitness of a chromosome will be determined by how close to a correct sorting it produces. Can be applied as objective fitness level and also by subjectively by using a human operator In GA – Fitness metric is essential

SELECTION OF INITIAL POPULATION Roulette-wheel Selection Proportionate Selection Linear Ranking Tournament Selection

Crossover Example Suppose an “organisms” consist of 32-bit computer words, and we want a string with all the bits as ones How can we do it? Create 100 randomly generated computer words Repeatedly do the following: Count the 1 bits in each word Exit if any of the words have all 32 bits set to 1 Keep the ten words that have the most 1s (discard the rest) From each word, generate 9 new words as follows: Choose one of the other words Take the first half of this word and combine it with the second half of the other word

Example cntd 1. Half from one, half from the other: 0110 1001 0100 1110 1010 1101 1011 0101 1101 0100 0101 1010 1011 0100 1010 0101 0110 1001 0100 1110 1011 0100 1010 0101 2. Choose “genes” (bits) randomly: 0110 1001 0100 1110 1010 1101 1011 0101 1101 0100 0101 1010 1011 0100 1010 0101 0100 0101 0100 1010 1010 1100 1011 0101 3. Consider a “gene” to be a larger unit: 0110 1001 0100 1110 1010 1101 1011 0101 1101 0100 0101 1010 1011 0100 1010 0101 1101 1001 0101 1010 1010 1101 1010 0101

Example In the simple example (trying to get all 1s): The sexual (two-parent, no mutation) approach, if it succeeds, is likely to succeed much faster Because up to half of the bits change each time, not just one bit However, with no mutation, it may not succeed at all By pure bad luck, maybe none of the first (randomly generated) words have (say) bit 17 set to 1 Then there is no way a 1 could ever occur in this position Another problem is lack of genetic diversity Maybe some of the first generation did have bit 17 set to 1, but none of them were selected for the second generation The best technique in general turns out to be reproduction operation with a small probability of mutation operation

Example: Curve fitting with reproduction operator Consider y = ax2 + bx + c “genes” are a, b, c “chromosome” is the array [a, b, c] What’s the best way to combine two chromosomes into one? We could choose the first half of one and the second half of the other: [a, b, c] We can choose genes randomly: [a, b, c] You could compute “gene averages:” [(a+a)/2, (b+b)/2, (c+c)/2]

Basic Components of GA Encoded representation. binary encoding, real number encoding, integer encoding, data structure encoding. Generating initial population. random initialization, patterned initialization. Evaluation of design fitness. Need a consistent means of determining which designs are “better” than others. Operators for producing and selecting new designs. Ex. selection, crossover, mutation. Values for the other parameters. Ex. How much crossover and mutation, how big is population.

Basic genetic algorithms Step 1: Represent the problem variable domain as a chromosome of a fixed length, choose the size of a chromosome population N, the crossover probability pc and the mutation probability pm. Step 2: Define a fitness function to measure the performance, or fitness, of an individual chromosome in the problem domain. The fitness function establishes the basis for selecting chromosomes that will be mated during reproduction.

Step 3: Randomly generate an initial population of chromosomes of size N: x1, x2 , . . . , xN Step 4: Calculate the fitness of each individual chromosome: f (x1), f (x2), . . . , f (xN) Step 5: Select a pair of chromosomes for mating from the current population. Parent chromosomes are selected with a probability related to their fitness. Basic genetic algorithms

Step 6: Create a pair of offspring chromosomes by applying the genetic operators - crossover and mutation. Step 7: Place the created offspring chromosomes in the new population. Step 8: Repeat Step 5 until the size of the new chromosome population becomes equal to the size of the initial population, N. Step 9: Replace the initial (parent) chromosome population with the new (offspring) population. Step 10: Go to Step 4, and repeat the process until the termination criterion is satisfied. Basic genetic algorithms

Genetic algorithms GA is essentially iterative process. Each iteration is called a generation. The entire set of generations is called a run. A common practice is to terminate a GA after a specified number of generations and then examine the best chromosomes in the population. If no satisfactory solution is found, the GA is restarted. Because GAs use a stochastic search method, the fitness of a population may remain stable for a number of generations before a superior chromosome appears.

generic optimization techniques lecture slides

More Related Content

Similar to generic optimization techniques lecture slides

Recently uploaded

generic optimization techniques lecture slides