Example1.
A simple function optimization, f(x) = x2 on the integer interval [0,31]
encoding scheme → binary unsigned integer of length 5
fitness function → 목표함수 이용
selection scheme → roulette wehel selection 사용
crossover, mutation scheme → one point
parameter setting
M(population size) = 4 → coin을 20번 던져서 initialization한다.
Pc = 1
Pm = 0.001
Evolving process
01101 → 13 ( fitness는 13*13 = 169)
% of total → 169 / 1170 → 14.4
두 쌍이 필요하므로 selection을 4번한다.
0110|1 과 1100|0을 crossover 해서 New Population 01100과 11001이 생성된다.
New population들을 생성한 후, 또 계산한다.
Example 2
Traveling Salesman Problem
: 각 도시들은 한번만 방문할 수 있고, 총 이동거리는 최소가 되어야한다.
→ chromosome: 방문한 도시의 순서
→ 다른 문제들은 integer가 여러개 나타나도 되지만, 이 문제에서는 중복되어서는 안된다.
→ 순서가 존재하는 encoding : order exist
Representation은 ordered list of city
숫자들은 order-based GA이다.
도시의 개수 = gene의 개수
예시:
1)London 3) Dunedin 5) Beijing 7) Tokyo
2)Venice 4) Singapore 6) Phoenix 8) Victoria
City List 1
(3 5 7 2 1 6 4 8)
City List 2
(2 5 7 6 8 1 3 4)
order-based crossover
fop sop
Parent1 (3 5 | 7 2 1 6 | 4 8) → 4 8 3 5 7 2 1 6
Parent2 (2 5 | 7 6 8 1 | 3 4) → 3 4 2 5 7 6 8 1
Child (5 8 7 2 1 6 3 4)
4 8 3 5 7 2 1 6에서 7 6 8 1 제거 → 4 3 5 2
sop부터 4 3 5 2 쓰고 그 뒤에 7 6 8 1 입력
5 2 7 6 8 1 4 3 → O1
3 4 2 5 7 6 8 1에서 7 2 1 6 제거 → 3 4 5 8
sop부터 3 4 5 8 쓰고 그 뒤에 7 2 1 6 입력
5 8 7 2 1 6 3 4 → O2
order-based Mutation
Before: (5 8 7 2 1 6 3 4)
→ 세 번째 수와 다섯 번째 수를 바꾼다.
After: (5 8 6 2 1 7 3 4)
다른 기술들과의 비교
- 현재 문헌에는 주로 세 가지 종류의 검색 방법이 나타난다.
Calculus-based methods - hill climbing
Random methods - enumerative scheme
Stochastic methods - simulated annealing(SA), GA
optimization problems의 유형들
- The single peak function(unimodal problem)
- The multiple-peak function(Multimodal problem)
- Combinatorial problem
ECs는 robust search techniques이다.
Genetic algorithm이 다른 search method 보다 좋은 이유는?
- Ecs는 매개변수 집합의 코딩과 함께 작동하며, 매개변수 자체와는 직접 작용하지 않는다.
- ECs는 단일 지점이 아닌 여러 지점의 모집단에서 검색한다. → 빠르게 많은 공간을 찾을 수 있다. 병렬성이 높다.
- ECs는 경사 정보가 아닌 목적 함수 (적합도 함수) 정보를 사용한다.
- ECs은 결정론적 규칙이 아닌 확률적 전이 규칙을 사용한다.
단점: 조금 무겁다.
'Study > 인공지능' 카테고리의 다른 글
| [인공지능] 지식의 표현과 추론에 관하여 - 1 (2) | 2023.11.08 |
|---|---|
| [인공지능] Genetic Algorithm 요약 (1) | 2023.10.26 |
| [인공지능] Monte Carlo Tree Search 요약 (1) | 2023.10.26 |
| [인공지능] Min-Max Algorithm 요약 (0) | 2023.10.25 |
| [인공지능] 탐색(Search) 요약 (0) | 2023.10.25 |
