Machine Evolution
Evolutions Generations of descendants Search processes Production of descendants changed from their parents Selective survival Search processes Searching for high peaks in the hyperspace
Applications Function optimization Solving specific problems The maximum of a function John Holland Solving specific problems Control reactive agents Classifier systems Genetic programming
A program expressed as a tree
A robot to follow the wall around forever Primitive functions : AND, OR, NOT, IF Boolean functions AND(x,y) = 0 if x = 0; else y OR(x,y) = 1 if x = 1; else y NOT(x) = 0 if x = 1; else 1 IF(x,y,Z) = y if x = 1; else z Actions North, east, south, west
A robot to follow the wall around forever All of the action functions have their indicated effects unless the robot attempts to move into the wall Sensory inputs ::: n, ne, e, se, s , sw, w, nw 만약 함수의 수행결과가 값이 없으면 중지
A robot in a Grid World
A wall following program
The GP process Generation 0 (0세대): start with a population of random programs with functions, constants, and sensory inputs 5000 random programs Final : Generation 62 60 steps 동안 벽에 있는 방을 방문한 횟수로 평가 32 cells이면 perfects; 10곳에서 출발하여 fitness 측정
Generation of populations I (i+1)th generation 10%는 i-the generation에서 copy 5000 populations에서 무작위로 7개를 선택하여 가장 우수한 것을 선택 (tournament selection) 90%는 앞의 방법으로 두 프로그램(a mother, a father)을 선택하여, 무작위로 선정한 father의 subtree를 mother의 subtree에 넣는다 (crossover)
Crossover
Generation of populations II Mutation : 1%를 tournament로 선정 무작위로 선택한 subtree를 제거하고, 1세대에서 개체를 생성하는 방법으로 만들어서 끼워넣는다
Evolving a wall-following robot 개별 프로그램의 예 (AND (sw) (ne)) (with fitness 0) (OR (e) (west) (with fitness 5(?)) the best one ::: fitness = 92 (어떤 때)
The most fit individual in generation 0
The most fit individuals in generation 2
The most fit individuals in generation 6
The most fit individuals in generation 10
Fitness as a function of generation number