Transcript 7주 강의
7주 강의 Machine Evolution Neural Networks • Some aspects of learning in biological systems • 차의영 교수님 강의에서 배울 것 Evolutions • Generations of descendants – Production of descendants changed from their parents – Selective survival • Search processes • Searching for high peaks in the hyperspace Applications • Function optimization – The maximum of a function ::: John Holland • Solving specific problems • Control reactive agents • Classifier systems • Genetic programming A program expressed as a tree + 3 / x 5 7 4 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 nw n ne w te xt e sw s se A wall following program IF AND east IF OR NOT AND n ne south e IF OR NOT AND e se west s OR s NOT sw north w 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 Randomly chosen crossover points NOT IF AND AND NOT OR AND se se n se NOT se IF s NOT e nw nouth OR Father program west w Mother program south IF NOT s west Child program AND se NOT nouth 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 350 300 Fitiness 250 200 150 100 50 0 0 1 2 3 4 5 6 7 Generation number 8 9 10 숙제 • Specify fitness functions for use in evolving agents that – Control an elevator – Control stop lights on a city main street • Determine what the words genotype and phenotype in evolutionary theory? • Why do you think mutation might or might no be helpful in evolutionary processes that use crossover?