[인공지능] Genetic Algorithm 요약

조합 최적화 (Combinatorial Optimization, CO)

VLSI 디자인에서의 배치 및 라우팅 문제:

• VLSI 셀들의 집합이 주어지며, 이들은 경계에 포트를 가지고 있다. 또한 포트를 연결해야 하는 네트워크의 모음도 주어진다.
• 전체 배치 및 배선 거리를 최소화하고 각 선이 특정한 상수 이하인 방법을 찾아야 한다.

외판원 문제 (The Traveling Salesman Problem):

• 외판원은 최소 비용으로 각 도시를 한 번만 방문하는 경로를 찾고자 합니다.
• 실행 가능한 해는 1부터 n까지의 숫자의 순열로 나타낼 수 있습니다.
• 따라서 해 공간의 크기는 (n-1)!이다

Local Search

• 부분 탐색 알고리즘
• 이전 값에 가까운 값으로 할당 공간 내에서 값을 수정
• 모든 제약 조건이 만족될 때까지 변수의 할당을 반복적으로 개선
• 제약 조건 충족 문제의 해결을 위한 불완전한 방법
• 기본 아이디어: 현재 솔루션을 개선하기
• 어떤 솔루션으로 시작합니다.
• 현재 솔루션과 "가까운" 일련의 솔루션을 찾습니다 - 이를 이웃 탐색이라고 한다.
• 이 중 하나의 이웃이 현재 솔루션보다 더 나을 경우 그 솔루션으로 이동한다.
• 개선할 수 없을 때까지 반복한다.

Variations

• First Improvement (select the first improving neighbor)

• Best Improvement (always select the best neighbor)

• Random Walk (move to neighbors at random)

• Problem: Gets stuck in a local optimum

• (except Random Walk, which isn’t a good method anyway)

 

Metaheuristics

• 주요 목표
• 지역 최적해에 갇히지 않기
• 탐색 공간의 더 큰 부분을 탐구하기
• 지역 최적해뿐만 아니라 전역 최적해를 찾으려고 시도하기
• 정확한 방법의 합리적인 대안 제공 (특히 크거나 어려운 문제 인스턴스 및 솔루션 시간이 중요한 경우)
• 지역 최적해를 피하기 위한 다양한 방법들은 매우 다른 기술을 사용한다.

 

Local search metaheuristics(로컬 탐색 메타휴리스틱)

• 모의 담금질 (Simulated Annealing, SA) (Kirkpatrick et al., 1983; Metropolis et al., 1953)
• 반복 지역 탐색 (Iterated Local Search, ILS), 다중 시작 로컬 탐색 (Multi-Start Local Search, MLS) (Lourenco et al., 2003)
• 타부 탐색 (Tabu Search, TS) (Glover, 1989, 1990, 1996)

 

Population based metaheuristics(집단 기반 메타휴리스틱)

• 유전 알고리즘 (Genetic Algorithm, GA) (Goldberg et al., 1989; Holland, 1975)
• 스캐터 서치 (Scatter Search) (Glover et al., 2000, 2003)
• 메멧틱 알고리즘 (Memetic Algorithm) (Moscato, 1989): 하이브리드 메타휴리스틱
• 입자 무리 최적화 (Particle Swarm Optimization, PSO) (Kennedy et al., 1995)

-------------------------------------------------------------------------------------------------------------

 

Random Walk

• 일정 수준의 무작위성을 포함
• 때로는 탐욕 알고리즘과 유사한 방식으로 움직이지만 때로는 무작위로 움직임
• 매개 변수 p에 의존 (0에서 1 사이의 실수)
• 매 이동에서 확률 p로 비용을 최대한 감소시키려고 시도하지만 확률 1-p로 솔루션을 다른 방식으로 변경함

Simulated annealing

• 온도 (Temperature)에 따라 무작위 이동의 확률을 변경
• T는 점차 감소하며 알고리즘이 진행됨
• 큰 탐색 공간에서 전역 최적화를 근사하는 메타휴리스틱 방법

Tabu Search

• 타부 탐색은 유연한 메모리 구조에 의존하여 검색 공간의 다양한 영역으로 안내할 정보를 충분히 기록한다. (예: 빈도 기반 다양성).
• 때로는 적응형 메모리 프로그래밍 알고리즘으로도 불린다.
• SA와 유사한 하향 이동 가능
• "금지된" 할당 목록인 타부 목록을 유지한다.

 

Genetic Algorithm

유전을 기반으로 하는 알고리즘

• 돌연변이 (Mutation)
• 부모의 염색체를 결합

복잡한 객체의 표현을 간단한 구성 요소의 벡터로 • 염색체 • 선택적 번식 • 다윈주의적 진화 • 고전적 유전 알고리즘: 이진 부호화

 

Terminology

GA Terminology

• 각 염색체는 종종 0과 1의 문자열을 사용하여 솔루션을 나타낸다.
• 일반적으로 각 비트는 유전자에 해당합니다. 이를 이진 부호화라고 한다.
• 특정한 유전자에 대한 값은 염색체의 알려로이(alleles)이다.

Block diagram (Goldberg, 1989)

t ← 0;

Initialize Population P(t) (initialization);

while ( not termination condition ) do

     evaluate P(t);

     Select individual for mating (Selection);

     Mate indivduals and produce children (Crossover);

     Mutate children (Mutation)

     Insert children into population (Insertion)

     t ← t+1;

end

 

GA 생성하기

1. 표현 방식 정의 (인코딩 - 디코딩 기술)
2. "적합도" 함수 정의
   • 실행 가능성(제약)과 목표를 통합
3. 유전 연산자 정의
   • 초기화, 선택, 교차, 돌연변이, 삽입
4. 초기 알고리즘 실행 수행
   • 평균 모집단 적합도 모니터링
   • 최적 개체 식별
5. 알고리즘 조정 (매개 변수 설정)
   • 선택, 삽입 전략, 돌연변이 비율 조정

 

Decoding-Encoding

Decoding-Encoding

Decoding

Decoding 예시

 

모든 유전 알고리즘 염색체가 이진 문자열이 아닐 수 있다.

• GA 코딩에 다른 알파벳을 사용할 수 있다.

• 가장 흔한 것은 이진 알파벳 {0, 1} 이다.

 

GA에서 selection이 제일 중요하다.

• 일반적으로 선택은 유전 알고리즘의 가장 중요하고 계산적으로 가장 비용이 많이 드는 단계
• 올바른 적합도 함수를 선택하는 것은 매우 중요하지만 매우 어려운 작업이다.
• 적합도 함수
  • 문제에 대한 해결 방법의 우수성을 나타낸다.
  • 최적화 문제의 목적 함수 또는 주관적 평가 함수가 될 수 있다.
  • 양의 값으로 정규화되어야 한다.

f’ = af + b

 

Selection

• 부모 염색체를 유전 연산을 위한 잠정적인 새 모집단으로 복사하는 과정 • 순위 선택 (Ranking selection)
• 모든 가설을 적합도에 따라 정렬한다.
• 선택 확률은 순위에 비례합니다.
• 예: 모집단에서 가장 적합한 k번째 멤버를 선택한다.
• 비례 선택 (Roulette wheel selection)
• 적합도에 비례하여 hi를 선택합니다

Roulette wheel selection

Roulette wheel selection

 

토너먼트 선택 (Tournament selection)

• 균일한 확률로 h1, h2를 무작위로 선택한다.
• 확률 p로 더 적합한 것을 선택한다

Tournament Selection

 

Crossover

• 무작위로 선택된 부모 염색체 간에 정보를 교환하는 연산자
• 그 목적은 부모 염색체의 중요한 정보를 손실하지 않는 것.

crossover

 

Mutation

An operator to randomly alter each gene

11101001000 → 11101011000

Its aim is to introduce genetic diversity into the population

 

Insertion 전략

• 한 번에 모든 모집단을 교체할 수 있다 (생존자 없이 k 세대에서 k+1 세대로 넘어갈 수 있음)
  • N/2 개의 부모 쌍 (N은 모집단의 회원 수)을 선택한다.
  • N 개의 자식을 생성하고 모든 부모를 대체한다.
  • 일반적으로 다수 결혼이 허용됩니다.
• 두 부모를 한 번에 선택할 수 있다.
  • 자식을 생성합니다.
  • 모집단의 일부를 제거한다 (가장 약한 것일까?).
• 엘리트 전략
  • 가장 맞는 몇몇 개체만 변경없이 생존한다.
• 명예의 전당
  • 최고의 과거 개체를 기억하지만 후손에 사용하지 않는다.

 

Initialization

어떻게든 GA를 시작하기 위한 초기 해결책 모집단을 생성해야 한다.

일반적인 목표: 품질과 다양성 모두를 갖춘 초기 모집단을 선택

어떻게 해야 할까?

• 무작위 초기 모집단, 여러 옵션 중 하나
• 초기 모집단을 생성하기 위해 난수 발생기를 사용한다 (씨드(seed)에 주의!).
• 일반적으로 균일 확률 밀도 함수(pdf)를 사용한다.

 

GA Convergence

모집단의 개체들의 평균 성능이 향상될 것으로 기대되며, 우수한 개체는 보전되고 번식하고 적합하지 않은 개체는 사라진다.

 

GA Control Parameter

• Population size (M)
• Mutation rate (Pm)
• Crossover rate (Pc)
• Tuning is practice and art

Basic Components Recap

A problem to solve, and ...

• Encoding technique (gene, chromosome)
• Initialization procedure (creation)
• Evaluation function (environment)
• Selection of parents (reproduction)
• Genetic operators (mutation,recombination)
• Parameter settings (practice and art)