Local Search and Optimization 2014.04.02 부산대학교 인공지능연구실 김민호

Slides:



Advertisements
Similar presentations
동의 / 반대 ? “Professional athletes such as football or basketball players do not deserve the high salaries that they are paid. (2010/07/10 한국 ) 이용 가능한 template.
Advertisements

인공지능 소개 부산대학교 인공지능연구실. 인공 + 지능 인공지능이란 ? 2.
실험 8. Cyclic Voltammetry - 7 조 : 한지영, 이호연, 최은진, 최효린 -
Ⅱ 세포의 주기와 생명의 연속성 Ⅱ 세포의 주기와 생명의 연속성 - 1. 세포주기와 세포분열.
김예슬 김원석 김세환. Info Northcutt Bikes Northcutt Bikes The Forecasting problem The Forecasting problem The solution 1~6 The.
15 장. 알고리즘의 설계 알고리즘 설계 학습목표 기본 패턴 패턴의 한계점 일곱 가지 패턴의 알고리즘 설계 기법을 이해한다.
Lecture 9 프로그램 실행의 비용 computation cost – 시간 time, 메모리 memory – tractable vs intractable problems.
Maximum Flow.
Fifth theme : Writing Class Superhero powers
Sources of the Magnetic Field
Multiple features Linear Regression with multiple variables (다변량 선형회귀)
Chapter 7 ARP and RARP.
10. Evolutionary programming
6.9 Redundant Structures and the Unit Load Method
Shortest Path Algorithm
TSP 알고리즘 구현 서왕덕.
어떤 과정으로 쓰면 될까.
Chapter 3 데이터와 신호 (Data and Signals).
4. Matlab-Simulink를 이용한 메카니즘 해석
LISTEN AND UNDERSTAND LISTEN AND SING
REINFORCEMENT LEARNING
제4장 자연언어처리, 인공지능, 기계학습.
7장 : 캐시와 메모리.
Discrete Math II Howon Kim
On the computation of multidimensional Aggregates
Christopher G. Langton (1989) 인지과학 협동과정 강 소 영
Fifth theme Superhero powers
Genetic Algorithm 신희성.
Dynamic Programming.
1 도시차원의 쇠퇴실태와 경향 Trends and Features of Urban Decline in Korea
Chapter 2. Finite Automata Exercises
Cluster Analysis (군집 분석)
숭실대학교 마이닝연구실 김완섭 2009년 2월 8일 아이디어  - 상관분석에 대한 연구
KMS 구현 및 활용사례 경쟁력 강화를 위한 2002년 5월 28일(화) 김 연 홍 상무 / 기술사
Chapter 31 Faraday’s Law.
PCA Lecture 9 주성분 분석 (PCA)
유전 알고리즘 - 기계 학습 발표 2008년 5월 15일 Computer Vision Lab. 이 득 용.
Genetic Programmed Soccer Softbot
2002년도 대한토목학회 학술발표회 Semi-active Fuzzy control for Seismic Response Reduction Using MR Damper K-M Choi1), H-J Jung1) J-H Lee2) and I-W Lee1) 1) Department.
Chip-based Computing + UMDA
Term Projects 다음에 주어진 2개중에서 한 개를 선택하여 문제를 해결하시오. 기한: 중간 보고서: 5/30 (5)
Dynamic Programming.
9. Do You Have a Scientific Mind?
컴퓨터 프로그래밍 기초 - 10th : 포인터 및 구조체 -
브레인스토밍이란? 공학입문 설계 네번째 시간 공학입문설계
Read and Think 영어 8-a단계 A Story of Two Seeds(3/8) [제작의도] [활용방법]
강변 교회 유초등부 설교. 강변 교회 유초등부 설교 강변 교회 유초등부 설교 이에 말씀하시되 내 마음이 매우 고민하여 죽게 되었으니 너희는 여기 머물러 나와 함께 깨어 있으라 하시고(마태복음 26:38) 이에 말씀하시되 내 마음이 매우 고민하여 죽게 되었으니.
CEO가 가져야 할 품질 혁신 마인드.
Discrete Math II Howon Kim
Machine Evolution.
이산수학(Discrete Mathematics)
탐색 (Lecture Note #3) 인공지능 이복주 단국대학교 컴퓨터공학과 Modified from the slides
제 4 장 유전자 알고리즘 (Genetic Algorithm)
7. Quicksort.
점화와 응용 (Recurrence and Its Applications)
광합성에 영향을 미치는 환경 요인 - 생각열기 – 지구 온난화 해결의 열쇠가 식물에 있다고 하는 이유는 무엇인가?
자동제어공학 4. 과도 응답 정 우 용.
탐색 (Search) 컴퓨터가 문제를 자율적으로 해결하기 위해 해 혹은 해에 이르기 위한 경로를 찾아가는 과정
The general form of 0-1 programming problem based on DNA computing
Numerical Analysis Programming using NRs
Additional fitness measures for Sequence Generation
CH557 진화연산 2003년도 제 2학기.
Hongik Univ. Software Engineering Laboratory Jin Hyub Lee
NACST progress report 신수용.
제10장. Other Models of TM’s 학습목표
[CPA340] Algorithms and Practice Youn-Hee Han
Chapter 4. Energy and Potential
Traditional Methods – Part 1
Chapter 7: Deadlocks.
Ⓒ Copyright CARROT Global. All Rights Reserved.
Presentation transcript:

Local Search and Optimization 부산대학교 인공지능연구실 김민호

Outline  Local search techniques and optimization –Hill-climbing –Simulated annealing –Genetic algorithms –Issues with local search

Local search and optimization  Previously: systematic exploration of search space. –Path to goal is solution to problem  YET, for some problems path is irrelevant. –E.g 8-queens  Different algorithms can be used –Local search

Local search and optimization  Local search –Keep track of single current state –Move only to neighboring states –Ignore paths  Advantages: –Use very little memory –Can often find reasonable solutions in large or infinite (continuous) state spaces.  “Pure optimization” problems –All states have an objective function –Goal is to find state with max (or min) objective value –Does not quite fit into path-cost/goal-state formulation –Local search can do quite well on these problems.

“Landscape” of search

Hill-climbing search function HILL-CLIMBING( problem) return a state that is a local maximum input: problem, a problem local variables: current, a node. neighbor, a node. current  MAKE-NODE(INITIAL-STATE[problem]) loop do neighbor  a highest valued successor of current if VALUE [neighbor] ≤ VALUE[current] then return STATE[current] current  neighbor

Hill-climbing search start goal -5 h = -3 h = -2 h = -1 h = 0 h = f (n) = -(number of tiles out of place)

Hill-climbing search  “a loop that continuously moves in the direction of increasing value” –terminates when a peak is reached –Aka greedy local search  Value can be either –Objective function value –Heuristic function value (minimized)  Hill climbing does not look ahead of the immediate neighbors of the current state.  Can randomly choose among the set of best successors, if multiple have the best value  Characterized as “trying to find the top of Mount Everest while in a thick fog”

Hill climbing and local maxima  When local maxima exist, hill climbing is suboptimal  Simple (often effective) solution –Multiple random restarts

Hill-climbing example  8-queens problem, complete-state formulation –All 8 queens on the board in some configuration  Successor function: –move a single queen to another square in the same column.  Example of a heuristic function h(n): –the number of pairs of queens that are attacking each other (directly or indirectly) –(so we want to minimize this)

Hill-climbing example Current state: h=17 Shown is the h-value for each possible successor in each column

A local minimum for 8-queens A local minimum in the 8-queens state space (h=1)

A local minimum for 8-puzzle f = -6 f = -7 f = 0 start goal move up move right f = -(manhattan distance)

Other drawbacks  Ridge = sequence of local maxima difficult for greedy algorithms to navigate  Plateau = an area of the state space where the evaluation function is flat.

Possible solution…sideways moves  If no downhill (uphill) moves, allow sideways moves in hope that algorithm can escape –Need to place a limit on the possible number of sideways moves to avoid infinite loops  For 8-queens –Now allow sideways moves with a limit of 100 –Raises percentage of problem instances solved from 14 to 94% –However…. 21 steps for every successful solution 64 for each failure

Hill-climbing variations  Stochastic hill-climbing –Random selection among the uphill moves. –The selection probability can vary with the steepness of the uphill move.  First-choice hill-climbing –stochastic hill climbing by generating successors randomly until a better one is found –Useful when there are a very large number of successors  Random-restart hill-climbing –Tries to avoid getting stuck in local maxima.

Hill-climbing with random restarts  Different variations –For each restart: run until termination v. run for a fixed time –Run a fixed number of restarts or run indefinitely  Analysis –Say each search has probability p of success E.g., for 8-queens, p = 0.14 with no sideways moves –Expected number of restarts? –Expected number of steps taken?

Search using Simulated Annealing  Simulated Annealing = hill-climbing with non-deterministic search  Basic ideas: –like hill-climbing identify the quality of the local improvements –instead of picking the best move, pick one randomly –say the change in objective function is  –if  is positive, then move to that state –otherwise: move to this state with probability proportional to  thus: worse moves (very large negative  ) are executed less often –however, there is always a chance of escaping from local maxima –over time, make it less likely to accept locally bad moves –(Can also make the size of the move random as well, i.e., allow “large” steps in state space)

Physical Interpretation of Simulated Annealing  A Physical Analogy: imagine letting a ball roll downhill on the function surface –this is like hill-climbing (for minimization) now imagine shaking the surface, while the ball rolls, gradually reducing the amount of shaking –this is like simulated annealing  Annealing = physical process of cooling a liquid or metal until particles achieve a certain frozen crystal state simulated annealing: – free variables are like particles – seek “low energy” (high quality) configuration –get this by slowly reducing temperature T, which particles move around randomly

Simulated annealing function SIMULATED-ANNEALING( problem, schedule) return a solution state input: problem, a problem schedule, a mapping from time to temperature local variables: current, a node. next, a node. T, a “temperature” controlling the probability of downward steps current  MAKE-NODE(INITIAL-STATE[problem]) for t  1 to ∞ do T  schedule[t] if T = 0 then return current next  a randomly selected successor of current ∆E  VALUE[next] - VALUE[current] if ∆E > 0 then current  next else current  next only with probability e ∆E /T

More Details on Simulated Annealing –Lets say there are 3 moves available, with changes in the objective function of d1 = -0.1, d2 = 0.5, d3 = -5. (Let T = 1). –pick a move randomly: if d2 is picked, move there. if d1 or d3 are picked, probability of move = exp(d/T) move 1: prob1 = exp(-0.1) = 0.9, –i.e., 90% of the time we will accept this move move 3: prob3 = exp(-5) = 0.05 –i.e., 5% of the time we will accept this move –T = “temperature” parameter high T => probability of “locally bad” move is higher low T => probability of “locally bad” move is lower typically, T is decreased as the algorithm runs longer –i.e., there is a “temperature schedule”

Simulated Annealing in Practice –method proposed in 1983 by IBM researchers for solving VLSI layout problems (Kirkpatrick et al, Science, 220: , 1983). theoretically will always find the global optimum (the best solution) –useful for some problems, but can be very slow –slowness comes about because T must be decreased very gradually to retain optimality In practice how do we decide the rate at which to decrease T? (this is a practical problem with this method)

다윈의 진화론  다산  생존경쟁  변이  자연선택  진화 e.g.) 똑똑한 토끼가 살아 남는다 ? 초기 토끼집단 진화된 토끼집단 느리고 영리하지 못한 토끼 빠르고 영리한 토끼

History of Genetic Algorithm (1/3)  1965 년 Rechenberg( 독일 ) – 진화전략 (Evolutionary Strategy) 발표 – 단 두개의 해로 이루어진 해 집단 사용 – 교차 연산자 사용 안함  1966 년 Fogel, Owens, Walsh – 진화 프로그램 제안 – 교차 연산이 없는 변이만을 사용

History of Genetic Algorithm (2/3)  Developed by John Holland in the early 70 ’ s – 유전 알고리즘의 대부 – 해 집단에 근거, 교차와 변이를 포함한 GA 의 골격 마련 –1975 년 역사적 저서 [Adaptation in Natural and Artificial Systems] 발표 –1984 년 산타페 연구소에 합류, 연구 방향을 [Complex System] 에서 [Adaptive Complex System] 으 로 선회

History of Genetic Algorithm (3/3)  1985 년 제 1 회 International Conference on Genetic Algorithms 개최  90 년대 많은 주목을 받은 Artificial Life 의 주된 도구로 활용됨  1997 년 IEEE Transactions on Evolutionary Computing 개설

유전자 알고리즘 (GA: Genetic Algorithm)  진화의 원리를 문제 풀이 또는 모의 실험에 이용하는 연구의 한 방법 –Solutions are encoded as chromosomes –Search proceeds through maintenance of a population of solutions –Reproduction favors “ better ” chromosomes –New chromosomes are generated during reproduction through processes of mutation and cross over, etc.

Genetic Algorithm  GA 가 필요 없는 문제 – 잘 정의된 Algorithm 이 존재하는 문제 – 최단 경로 탐색 문제, Sorting 등  GA 의 적용이 효과적인 문제 –Traveling salesman problem (TSP) – 함수 값을 최대화하는 변수 –NP Complete 문제

Basic Terminology in Biology  DNA, Chromosome : 염색체, 유전물질  유전자 (gene) : 염색체 상의 각 인자  유전자형 (genotype) : 유전자의 조합  표현형 (phenotype) : 관찰되는 형질  생물학적 진화 – 개체는 교차에 의해 염색체를 부분 결합과 돌연변이에 의해 새로운 염색체를 가진 새로운 개체 생성 – 환경에 적응하기 유리한 개체만이 선택적으로 번성

Basic Terminology in GA  염색체 (chromosome) : 임의의 solution  해집단 (population) : 정해진 개수의 염색체 집단  유전자 (gene) : 염색체의 인자 하나  유전자 형 : 염색체 자체  표현형 : 유전자형에 대응하는 해의 모양

유전자 알고리즘의 구조 selection mutation cross over population ABCDABCD Fitness evaluation Search space reproduction Substitution

유전자 알고리즘 function GENETIC-ALGORITHM(population, FITNESS-FN) returns an individual input: population, a set of individuals FITNESS-FN, a function that measures the fitness of an individual repeat parents  SELECTION(population,FITNESS-FN) population  REPRODUCTION(parents) until some individual is fit enough return the best individual in population, according to FITNESS-FN function GENETIC-ALGORITHM(population, FITNESS-FN) returns an individual input: population, a set of individuals FITNESS-FN, a function that measures the fitness of an individual repeat parents  SELECTION(population,FITNESS-FN) population  REPRODUCTION(parents) until some individual is fit enough return the best individual in population, according to FITNESS-FN % REPRODUCTION = cross-over + mutation

유전자 알고리즘의 구성요소  개체 표현 방법 (Encoding Scheme) – 문제의 해가 될 가능성이 있는 것의 유전자적 표현 방법  적합도 함수 (Fitness Function) – 유전자를 평가하는 함수 –Solution 에 가까운 유전자일 수록 높게 평가  유전 연산자 (Genetic Operators) – 자손의 합성을 변화시키는 유전 연산자들  알고리즘 제어 파라미터 (Parameter Setting) – 유전자 알고리즘이 사용하는 여러 가지 매개변수의 값 – 개체 집단의 크기, 유전 연산자를 적용시키는 확률 등

개체 표현 방법 (Encoding Scheme)  문제의 해가 될 가능성이 있는 것을 유전자로 표현하는 것  전형적인 표현 양식은 이진수 0 과 1 을 이용한 일차원적 표현  표현 양식이 결정된 후 이에 맞는 교차 연산자 및 변이 연산자 결정

스키마 (Schema)  염색체에 들어 있는 패턴 –1101 에는 1***, *1**, … 11**, 1*0*, …, 110*, *101,..., 1101, **** 의 16 개 스키마가 포함됨 –* : don ’ t care symbol –1 또는 0 : specific symbol – 유전 알고리즘이란 초기의 작은 스키마가 결합하여 점점 더 큰 스키마를 이루어가는 과정 – 마지막 return value 는 하나의 거대한 스키마

1. 이진수 표현, k 진수 표현  Binary Encoding, n-ary Encoding  vs  이진수 표현할 경우 교차시 자름 선 위치가 많아져 추가 변이 효과 발생 – 교차의 다양성 제공  k 진수의 경우 의미 있는 스키마 보존 가능성 높음 – 교차의 다양성은 시뮬레이션으로 가능

2. Gray Coding  0000, 0001, 0011, 0010, 0110, 0111, 0101, 0100, 1100, …  2 진수 표현의 한 변형  인접한 수는 단 한 비트만 차이가 나도록 하는 코드 체계  의미상으로 유사한 두 해가 문제 공간에서 가까이 위치하도록 만든 코드 체계

3. 순열 표현 (Permutation Encoding)  1234, 1243, 1324, 1342, 1423, 1432, 2134, 2143, 2314, …  순열을 유전자형으로 가짐  순서 기반형 표현  Traveling salesman problem (TSP)

4. 실수 표현 (Value Encoding)  독일의 진화 전략 그룹 – 교차 연산자를 사용 안 함 – 이진연산자 사용 불필요, 실수 사용  Bremermann 이 교차 연산에 실수를 처음 사용  실수 하나를 하나의 유전자로 사용  크기의 개념을 연산자에 적용 가능 – 부모의 값을 평균하여 자식의 값에 적용시키는 산술 교차를 사용할 수 있음  Finding weights for neural network

5. 가변 표현  대부분의 GA 는 수행이 완료될 때까지 표현 방식을 바꾸지 않음  표현상의 비효율로 인한 한계 극복 불가능  표현 방식을 미리 고정하지 않고 알고리즘 수행 중 표현 방식을 변화하는 방법 고안  역치, 메시 유전 알고리즘, 유전 프로그래밍  유전자 재배열

개체 표현 방법 정리  여러가지 표현형태들 –Binary Encoding –Permutation Encoding –Value Encoding  주로 0 과 1 의 Binary encoding 을 많이 사용 e.g.) ABDJEDIB e.g.)

적합도 함수 (Fitness Function)  염색체의 해 (solution) 로서의 적합도를 평가 염색체 적합도 e.g.)

유전 연산자 (Operators of GA)  선택 연산자 (Selection) – 교차를 위해 해집단 (population) 에서 2 개의 염색체를 선택 – 우수한 해에게 선택 가능성을 높게 해 준다  교차 연산자 (Crossover) – 선택된 두개의 parent 로부터 하나의 offspring 을 생성 –GA 의 대표적 연산자  변이 연산자 (Mutation) – 해를 임의로 변환  대치 연산자 (Substitution) – 부모의 염색체를 생성된 염색체로 대치 유전 연산자

선택 연산자 (1/2)  Roulette wheel selection – 각 염색체의 적합도에 비례하는 만큼 roulette 의 영역을 할당한 다음, roulette 을 돌려 화살표가 가리키는 영역의 염색체를 선택 – 적합도가 높은 것은 선택될 확률이 그만큼 많고 적합도가 낮을 것은 선택될 확률이 상대적으로 낮다  Elitist preserving selection 염색체적합도 % of total ABCDABCD Roulette Wheel e.g.)

선택 연산자 (2/2)  Expected-value selection : 적합도에 대한 각 개체의 확률적인 재생 개체수를 구하여 선택  Ranking selection : 적합도의 크기 순서에 따라 순위를 매기고 순위에 따라 확률을 결정 적합도 기대치 재생수 적합도 순위 재생수

교배 연산자 (1/4)  두 부모의 염색체를 부분적으로 바꾸어 자식의 염색체를 생성  Single point crossover  Two point crossover

교배 연산자 (2/4) Initialize threshold P 0 ; for each gene in chromosome { generate random number t ; if (t < P 0 ) copy the gene from S 1 ; else copy the gene from S 2 ; }  Uniform crossover ( 균등 교차 ) – 자름 선을 이용하지 않음 – 스키마의 결합 형태가 다양 – 스키마 내의 특정 기호의 위치가 거의 영향을 미치지 않음 – 교란의 정도가 크므로 수렴 시간이 오래 걸림

교배 연산자 (3/4) S 1 : a b c d e f g h i j S 2 : k l m n o p q r s t t : P 0 = 0.6 O : a l m d e f q h s t  균등 교차의 예 유전 연산자

교배 연산자 (4/4)  Arithmetic crossover ( 산술적 교차 ) – 실수 표현 (Value Encoding) 일 경우 사용 가능 – 염색체의 각 위치에 대해 두 부모 염색체의 유전자의 평균값을 내어 자식 유전자로 삼는다. – 매우 빠른 수렴을 보이므로, 변이 등을 적절히 조절하여 설익은 수렴 이 되지 않도록 주의하여야 한다. s1 : s2 : offspring :

변이 연산자 (1/2)  유전자를 일정한 확률로 변화시키는 조작  개체군의 다양성 유지 – 돌연변이가 없는 경우 초기 유전자 조합 이외의 공간을 탐색할 수 없 어 초기 조합에 적절한 해가 없을 경우 원하는 해를 구할 수 없다.  local optimum 방지 GA Search Method Hill-climbing Method cf

변이 연산자 (2/2)  부모 해에 없는 속성을 도입하여 탐색 공간을 넓힘  전형적 변이 – 난수를 발생시켜 변이  비균등 변이 – 초기에는 품질이 좋지 않은 해가 많으므로 변이의 강도를 높임 – 후반에는 변이가 강할 경우 품질 향상이 일어나지 않으므로 변이의 강도를 낮춤  변이의 확률이 높아지면 – 다양한 해 생성에 의해 GA 의 역동성이 높아짐 – 수렴성이 떨어져 수행 시간이 많이 걸림 – 개선의 속도가 느려짐

대치 연산자 (1/3)  대치가 GA 성능을 크게 좌우  Steady state GA : – 가장 성능이 낮은 해를 선택 대치하는 것이 가장 보편적 빠른 수렴 보장 설익은 수렴 가능성  Generational GA : – 가장 우수한 해만을 제외한 나머지 전부 대치 (Elitism)

대치 연산자 (2/3)  그 이외의 것들 – 두 부모 해 중 품질이 나쁜 해와 대치 (preselection) 해집단의 다양성 유지에 좋다 – 부모 해 중 하나보다 폼질이 좋을 경우 부모 해와 대치하고 그렇지 않을 경우 해집단에서 가장 나쁜 해와 대치 – 부모 해보다 품질이 좋을 경우 대치, 그렇지 않으면 대치 포기 수렴에 시간이 너무 오래 걸린다. – 해집단 전체를 비교하여 자신과 가장 가까운 해를 대치 – 해집단 중 일부를 임의로 선정, 이 중 가장 닮은 해를 대치 ( 군집 대치, crowding)

대치 연산자 (3/3)  대치 연산자의 선택 – 해집단의 다양성을 합리적으로 유지시킬 수 있는 연산자의 선택이 중요 – 교차, 변이 연산자와 연관하여 결정 –perturbation 이 강할 경우 교차, 변이 연산자 쌍이 부모 해를 많이 변형시킬 경우 수렴성이 강한 대치 연산자 사용 –perturbation 이 약할 경우 수렴성 보다는 해집단의 다양성을 유지시키도록 하는 대치 연산자를 선택

알고리즘 제어 파라미터  개체군의 크기 (Population size) –How many chromosomes are in population Too few chromosome  small part of search space Too many chromosome  GA slow down –Recommendation : 20-30,  교배 확률 (Probability of crossover) –How often will be crossover performed –Recommendation : 80% -95%  돌연변이 확률 (Probability of mutation) –How often will be parts of chromosome mutated –Recommendation : 0.5% - 1% 

Questions 1. 개체 표현 방식은 어떤 것이 좋은가 ? – 문제를 잘 고려 하여 선택한다. – 이것을 잘 선택하면 문제의 반은 푼 것이다. 2. 개체군의 크기는 어느 정도로 정할까 ? 3. 적합도 함수는 어떻게 정의할까 ? 4. 선택 연산자는 무엇을 사용할까 ? 5. 교배 확률을 어느 정도로 정할까 ? 6. 돌연변이 확률은 어느 정도로 정할까 ? 7. 대치 연산자는 어떻게 정할까 ? – 교배 연산자와 변이 연산자를 고려하여 선택

일차원 vs. 다차원  많은 경우 1 차원 표현 과정에서 정보의 손실이 일어남  1986, Cohoon 등이 VLSI 회로 최적 재배치 문제에서 2 차원 격자형 염색체 사용  2 차원 배열, Tree Encoding

위치기반 vs. 순서기반 (1/2)  위치 기반 – 유전자의 위치가 유전자의 속성을 결정 –n 번째 유전자는 n 번째 속성을 결정 – 한 해에 대해 유일한 염색체를 갖는 장점이 있으나 유전자의 배치로 인한 한계 극복에 어려움  순서 기반 – 유전자 값의 상대적 순서가 의미를 가짐 – 동일한 해에 대해 n 개의 표현이 존재 – 밀접한 관계를 갖는 염색체가 인접하여 교차시 생존 확률이 높음 개체 표현 방식

위치기반 vs. 순서기반 (2/2) 순서기반 … 위치기반 Traveling Salesman Problem 개체 표현 방식

예 2 : Traveling Salesman Problem 

유전자 알고리즘의 특성  어려운 비선형 문제에서 최적 해를 찾는데 적합하다. – 선로 라우팅, 적응제어, 게임놀이, 인지 모델링, 운송문제, 순회 판매원문제, 최적제어문제, …  Local optima 를 피해갈 능력이 있는 메커니즘을 가지고 있다.  해를 나타내는 파라미터를 염색체 형태로 코드화하여 이용한다.  점 (point) 이 아닌 다점 (multi points) 탐색 방법이다.  탐색에 적합도 함수 (fitness function) 을 이용하며 blind search 를 한다.  결정론적인 규칙이 없고 확률적 연산자를 사용하여 수행된다.

Genetic algorithms  Different approach to other search algorithms –A successor state is generated by combining two parent states  A state is represented as a string over a finite alphabet (e.g. binary) –8-queens State = position of 8 queens each in a column => 8 x log(8) bits = 24 bits (for binary representation)  Start with k randomly generated states (population)  Evaluation function (fitness function). –Higher values for better states. –Opposite to heuristic function, e.g., # non-attacking pairs in 8-queens  Produce the next generation of states by “simulated evolution” –Random selection –Crossover –Random mutation

Genetic algorithms  Fitness function: number of non-attacking pairs of queens (min = 0, max = 8 × 7/2 = 28)  24/( ) = 31%  23/( ) = 29% etc 4 states for 8-queens problem 2 pairs of 2 states randomly selected based on fitness. Random crossover points selected New states after crossover Random mutation applied

Genetic algorithms Has the effect of “jumping” to a completely different new part of the search space (quite non-local)

Genetic algorithm pseudocode function GENETIC_ALGORITHM( population, FITNESS-FN) return an individual input: population, a set of individuals FITNESS-FN, a function which determines the quality of the individual repeat new_population  empty set loop for i from 1 to SIZE(population) do x  RANDOM_SELECTION(population, FITNESS_FN)y  RANDOM_SELECTION(population, FITNESS_FN) child  REPRODUCE(x,y) if (small random probability) then child  MUTATE(child ) add child to new_population population  new_population until some individual is fit enough or enough time has elapsed return the best individual

Comments on genetic algorithms  Positive points –Random exploration can find solutions that local search can’t (via crossover primarily) –Appealing connection to human evolution E.g., see related area of genetic programming  Negative points –Large number of “tunable” parameters Difficult to replicate performance from one problem to another –Lack of good empirical studies comparing to simpler methods –Useful on some (small?) set of problems but no convincing evidence that GAs are better than hill- climbing w/random restarts in general