algoritma genetika

Genetic Algorithms

BA Stuttgart – Guest Lecture @ VEDC Malang 2005 Prof. Dr. Dirk Reichardt1

Basics

EVOLUTIONARY COMPUTING

GENETIC ALGORITHMS

Modern Methods of Information Technology

Guest lectureProf. Dr. Dirk Reichardt

February 2005

Genetic Algorithms


Basics

Overview

Introduction & Motivation

Application of GAs

What is this lecture all about? What‘s the story behind theMystic name „genetic algorithms“? How could they be usedand why are they better than „normal“ algorithms?

Explanation of the way genetic algorithms are used to solvecomputer science problems.

Genetic Algorithms Motivation and short introduction to the basic computationprinciples of genetic algorithms.

Practice / Implementation Using genetic algoritms in practical experiments.Programming excercises in C.

Extension: advanced GA Advanced algorithm variations for modeling problems withthe genetic algorithm paradigm.

Genetic Algorithms


Basics

Genetic Algorithms – Theory of Evolution

Nature as role model

Bildquelle: www.aboutdarwin.com

Principle of natural selection

Every small change will be kept by nature if it isbeneficial for survival.

The ability of an organism to survive depends onits ability to adapt to changes in its environment.

Idea: Take this principle to computer science

Charles Darwin1809-1882

Genetic Algorithms


Basics

A2A3

Nature as role model - Generations of Algorithms

A2A1

A1A1

A1

A1

A2A3A3

A3A3

Algorithm pool„Today“

A3A1A1

A1A1

A3A3

A3A3

Algorithm pool„Tomorrow“

Applicationto Problem

X

Applicationto Problem

X

?? A2

A3A3

A3Goodsolution

Badsolution


Genetic Algorithms


Basics

Nature as role model - Generations of Algorithms

Observation: In the new generation there are no newalgorithms but just a new selection of algorithmswhich already existed before !

How is this in nature?

Individuals show small changes in their appearanceand features as compared to their parent generation.

that means: features of the parents are mixedand modified!


Genetic Algorithms


Basics

Nature als role model - Biology

Image source: www.biologie.uni-hamburg.de

dominant-rezessive inheritance

Mendel‘s Rules

Figure:

If there are many featureswe get a lot of combinationsfor the child-generation


Genetic Algorithms


Basics

Nature as role model - How do we get an algorithm from that?

Algorithm descriptions need to be made of componentswhich can be recombined.Algorithm descriptions need to be made of componentswhich can be recombined.

We need a rating for the currently existing algorithm in order to tell good ones from bad ones. The good onesshall be selected and recombined to build the nextgeneration.

We need a rating for the currently existing algorithm in order to tell good ones from bad ones. The good onesshall be selected and recombined to build the nextgeneration.

Every successor generationshould now be better than itsparents!

Why would we write algorithms in that way?

The domain of application for genetic algorithms isa set of complex problems for which there are no efficientalgorithmic solutions available.


Genetic Algorithms


Basics


Application of genetic algorithms

Source:

Spiegel Onlinewww.spiegel.devom 22.6.2004

An example:

Formula 1 – race cars

Genetic Algorithms


Basics

The chromosome theory

Based upon a theory of Boveri und Sutton (early 20th Century)

Chromosome Carrier of the genetic information

Build the core of a cell of an organism

Diploid

Chromosomes occur as pairs (diploid)

Number and length are variing

Number of chromosomesis characteristic for thebreed

Human : 46Carp : 48Potatoe: 104

Human : 46Carp : 48Potatoe: 104

Each chromosome consists of a number of genes


Genetic Algorithms


Basics

Die chromosome theory

InheritanceA B

1 2 1 2

split split

A1B1 A1B2 A2B1 A2B2

P-Generation

F1-Generation

Recombination by

chromosomes

Recombination by

chromosomes


Genetic Algorithms


Basics


Gene-Maps Genes are associated to aChromosome in a fixed manner

Gene A

Gene B

Gene C

Gene D

The coded informationis not changed byinheritance …

... or is it?

CROSSOVERsplitting chromosomesand recombining them


Genetic Algorithms


Basics


Mutations Random changes in genetic information codes

Gene mutation

Chromosome mutation

Genome mutation

Change rate of a gene in a generationIs between 1:10.000 and 1:1.000.000.000

Structural changes in order etc.

Also the number of chromosomes can change


Genetic Algorithms


Basics

Overview


Application of GAs






Genetic Algorithms


Basics

The Basic Algorithm

Generate random populationGenerate random population

Rating of the individualsRating of the individuals

select best individualsfor a "mating-pool"

select best individualsfor a "mating-pool"

Recombination by CrossoverRecombination by Crossover

MutationsMutations

Population

Pi

Population

Pi

Good enough?Good enough? Solutionfound

A brief outline

Constraints

- Constant population size

- Stop if individuals are all identical

- Stop if solution quality is good

Genetic Algorithms


Basics

Representation of individuals

- the „genome" should represent a solution to a problem

- every individual is rated regarding a specific overall goal

Example: The function f(x) : 2552-(x - 10)2 for x ∈ [0,255]

shall be maximized

possible solutions x = 73 x = 128 x = 10

binary coded: 01001001 10000000 00001010

optimal solutionbad solutions

every digit is a geneevery digit is a gene

The Basic Algorithm

Genetic Algorithms


Basics

Fitness of a solution

- The solution (the genome / the individual) must be rated

- A simple way is to measure the distance to the optimum

Example:

possible solutions x = 73 x = 128 x = 10

binary coded: 01001001 10000000 00001010Let‘s take the functionItself!

Fitness: 61056 51101 65025

The Basic Algorithm

The function f(x) : 2552-(x - 10)2 for x ∈ [0,255]

shall be maximized

Genetic Algorithms


Basics

Selection of the parent individuals

- the best of a generation should sprawn - „build pairs"

- The selection is made due to probabilities using the fitness function

The higher the fitness value the higher the probability to get in The so called Mating-Pool.

PopulationPopulation

Mating-PoolMating-Pool

Good individuals may get there several times

Population and Mating-Poolhave the same size

The Basic Algorithm

Genetic Algorithms


Basics

copy the individualsto the successor generation

copy the individualsto the successor generation

Randomly determine aCrossover-Site

and recombine theindividuals accordingly

Randomly determine aCrossover-Site

and recombine theindividuals accordingly

Recombination - "Crossover"

- step by step two individuals are taken from the mating pool

- a random variable decides wheter to perform a crossover or not

CROSSOVER?CROSSOVER?

0 1 1

1 1 0

0 1 0

1 1 1

10 10

11 11

Crossover Site

crossing

The Basic Algorithm

Genetic Algorithms


Basics

Mutation

- After some iterations the population may converge (all individuals are equal)without arriving at an optimum solution!

- How do we get out of this? A solution is “mutation”

1 1 011 111

random selection

1 0 011 111

the probability for mutations has to be set to a very lowvalue

The Basic Algorithm

Genetic Algorithms


Basics

An example

Definition of a starting population

No. Ai fi pi n·pi1 101 52 001 13 010 24 110 6

fi = (simplified!) a binary coded number

0.3570.0710.1430.429

1.4290.2860.5711.714

total 14 1.000 4.000avg 3.5 0.250 1.000max 6 0.429 1.714

individuals are defined by 3 genes which can thake either the value 1 or 0 (binary).

initialpopulation

rating of the solutins (individual)by the fitness function

probability for the selectiondepends on fitness value

fitness value of theoverall populationsource: [Muna 1998]

The Basic Algorithm

Genetic Algorithms


Basics

An example (cont’d)

Selection : Forming the mating pool

No. Ai fi pi n·pi1 101 52 001 13 010 24 110 6

0.3570.0710.1430.429

1.4290.2860.5711.714

total 14 1.000 4.000avg 3.5 0.250 1.000max 6 0.429 1.714

randomize

000-356357-427428-570571-999

select 4individuals

1012

mating pool

101010110110

”throw the dicefour times"

the worst resultis omitted!

the best one is included twice!

The Basic Algorithm

Genetic Algorithms


Basics


Recombination : pairwise crossover

Mating pool:

No A(i) partner crossing site new population fitness1 010 4 1 010 22 101 3 2 100 43 110 2 2 111 74 110 1 1 110 6

0 1 0

1 1 0

0 1 0

1 1 0

No 1 und 4

1 0 1

1 1 0

1 0 0

1 1 1

No 2 und 3010110100111

new population

The Basic Algorithm

Genetic Algorithms


Basics


Comparison of populations

010110100111

010001101110

Population i Population i+1

2156

2647

14 19

The successorgeneration is

better!

The successorgeneration is

better!

The optimumhas already been

found!

The optimumhas already been

found!

The Basic Algorithm

Genetic Algorithms


Basics

Evolution over generations Example A

250 individuals100 generations250 individuals100 generations

The Basic Algorithm

Genetic Algorithms


Basics

Verlauf der Evolution Beispiel

The number of different individuals

decreases

The number of different individuals

decreases

The Basic Algorithm

Genetic Algorithms


Basics

Genetic Algorithms – Advanced Techniques

Variations

Mating poolselection

Population

Binary Integer Floating Point PermutationRepresentation

FPS Rankselektion SUS Tournament

Selection ofsuccessor generation no survivor age selection fitness selektion

Generation model Steady State Modell

Successor population

Terminating thealgorithm All individuals are equal

(or "> x % equal")Quality level is reached

Genetic Algorithms


Basics

Exercise

The genetic algorithm should operate with the following fitness function:

f(x) =

4 x3(6-x) 2(x-6) (12-x) 0

x ≤ 44 < x ≤ 66 < x ≤ 88 < x ≤ 12otherwise

The population is coded by a 4 bit word

Start with the following population and determine the following two generations

0 1 1 0

1 1 0 1

1 1 0 0

0 1 1 1

population i population i+1 population i+2

use the presented scheme of the basic algorithm withoutmutation

Genetic Algorithms


Basics

Overview


Application of GAs






Genetic Algorithms


Basics

Application Types

Application types of "Evolutionary Computing"

Optimizing

System identification

Simulation

Model and solution are known – optimal input is searched for.

Typical problem type: The Traveling Salesman Problem

Input and output of a system can be observed but wecannot look inside

Socio-economic simulation

XXININ OUTOUT?

XXININ OUTOUT?

XXININ OUTOUT?

Genetic Algorithms


Basics

What is meant by "System identification"?


You can observe the reactions of a system to an input butthe goal is to determine the general principle of behavior -The so called internal Model of the system.

applyacceleratorpedal

accelerationbehavior?

Genetic Algorithms


Basics

Problem schematic using a binary example

x1 x2 x3 y

0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1

01100010

Defining a function by a table:

w1x1 + w2x2 + w3x3 < 0

y =

0

1 otherwise

wi ∈ {-1,0,1}

A more compact way …:

Especially interesing whenusing large tables!

Especially interesing whenusing large tables!


Genetic Algorithms


Basics

Similar to „machine learning“ techniques

No. wi fi1 1 0-1 22 0 0 1 23 0-1 0 14 -1 1 0 3

total 8avg 2max 3

Large Tables:Testing input/outputpairs (by random)

Beispiel:

0 0 1 10 1 0 11 0 0 01 1 1 0

0 0 1 1 1 ok0 1 0 1 0 no1 0 0 0 1 no1 1 1 0 1 no

fitness: 1

„Teacher"


Genetic Algorithms


Basics

Idea: stock market „forecast“

Observation Forecast

Genome = development of values

Fitness function = comparison to real world

Witchcraft?Witchcraft?


Genetic Algorithms


Basics

Solving NP-complete problems

Traveling Salesman Problem (TSP)

Given a set of locations, ways and distances.We are looking for a cost-optimal round trip.

Optimizing

22

77

66

55

11

44

33

99

88

254

115

210

95

104

45

23

232

92

45

133

18719

27

304

129

49 153

Genetic Algorithms


Basics

Solving NP-complete problems

time table problem

Given a set of classes (courses) , lectures and lecturers.We are looking for a time table with low gaps and good distribution of lectures.

Optimizing

Genetic Algorithms


Basics

The Job Shop Scheduling - Problem

M1M1 M2M2 M3M3

O1 O7 O3 O4

O4 O2 O5 O7

O3 O7 O4 O5

J1

J2

J3

1,2,3 4,5,6 7,8,9

A set of jobs JA set of machines MA set of operations O

capability: fMO : O → M (Maschine can perform operation)sequence: PS : O x O (which operation bevor which other?)duration : fd : M x O → R (Operation O lasts x minutes on machine M ...)

Simplification:Operation can be doneby several machines-

Simplification:Operation can be doneby several machines-

JSSP: all jobs must be carried out, all conditions / constraints must be fulfilled… and all this must be done very fast !

Quelle: [ES 2003]

Optimizing

Genetic Algorithms


Basics

The Job Shop Scheduling - Problem

Problem encoding Permutation : every gene is an operation of a jobThe permutation determines the order of processing theoperations. These are given to a „schedule builder“ whichassigns them to the machines.

1 / duration of completing all jobsFitness funktion

PMX or Index methodCrossover

Swap / Insert / Scramble / InversionMutation

The schedule builder guarantees the order constraints ofthe jobs an determines the earliest starting point.

Given timing constraint is reached (or: equal solutions...)Termination

Optimizing

Genetic Algorithms


Basics

Overview


Application of GAs






Genetic Algorithms


Basics

How does the main algorithm look like?

Implementing Genetic Algorithms

int main(void){int generations = 0;population pop;population temp;

myrandomize(); // initializes random number generator

initPopulation(&pop,8,100,binary);

for(generations=1; generations < 200; generations++){

selectMatingPool(&pop,&temp);recombine(&temp,&pop);mutation(&pop,binary);

}}

Genetic Algorithms


Basics

How do you represent individuals?


/* genome structure ------------------------------------------ */

/* a single individuum in the population is represented as one *//* genome as defined in the following structure. */

typedef struct{int gene[MAX_NUMBER_OF_GENES];int numberOfGenes; // actually used number of genesint mutated; // 1: mutated in last cycle, 0: not mutatedint fitness; // current fitness of the genomegenetype type; // binary, digit, number

} genome;

Genetic Algorithms


Basics

How do you represent a population?


/* population ------------------------------------------------ */

/* a structure containing the set of solutions which represents *//* the current population. */

typedef struct{genome solution[MAX_NUMBER_OF_SOLUTIONS];int numberOfSolutions; // actual population size

} population;

Genetic Algorithms


Basics

The fitness function


/* Test Fitness Function ------------------------------------- */

int fitness(genome g){int r;

/* simple 8-bit code to test a genetic algorithm principle */

r = g.gene[0]*8+g.gene[2]*-4+g.gene[1]*10+g.gene[3]*2+g.gene[4]*-6+(g.gene[5]*2+g.gene[6]*5)+g.gene[7]*-5+ 15;

return r;}

Genetic Algorithms


Basics

The crossover function


/* 1-point-crossover ---------------------------------------- */

void crossover (genome p1, genome p2, genome *np1, genome *np2, int site){int i;

for (i=0;i<site;i++){

np1->gene[i] = p1.gene[i];np2->gene[i] = p2.gene[i];

}for (i=site;i<p1.numberOfGenes;i++){

np1->gene[i] = p2.gene[i];np2->gene[i] = p1.gene[i];

}}

Genetic Algorithms


Basics

Literature

[ES 2003]

A.E.Eiben, J.E.Smith"Introduction to EvolutionaryComputing"

Springer, 2003

[TM 1998]

T.Munakata"Fundamentals of the

New Artificial Intelligence"Springer, 1998

algoritma genetika

Engineering