[인공지능] Genetic Algorithm Examples

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

Evolving process Table

01101 → 13 ( fitness는 13*13 = 169)

% of total → 169 / 1170 → 14.4

 

2nd generation

두 쌍이 필요하므로 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)

---

Overview of Performance

 

---

다른 기술들과의 비교

• 현재 문헌에는 주로 세 가지 종류의 검색 방법이 나타난다.

Calculus-based methods - hill climbing

Random methods - enumerative scheme

Stochastic methods - simulated annealing(SA), GA

 

 

optimization problems의 유형들

1. The single peak function(unimodal problem)
2. The multiple-peak function(Multimodal problem)
3. Combinatorial problem

 

ECs는 robust search techniques이다.

Efficiency: 정확도, 자원 사용 시간

 

 

Genetic algorithm이 다른 search method 보다 좋은 이유는?

• Ecs는 매개변수 집합의 코딩과 함께 작동하며, 매개변수 자체와는 직접 작용하지 않는다.
• ECs는 단일 지점이 아닌 여러 지점의 모집단에서 검색한다. → 빠르게 많은 공간을 찾을 수 있다. 병렬성이 높다.
• ECs는 경사 정보가 아닌 목적 함수 (적합도 함수) 정보를 사용한다.
• ECs은 결정론적 규칙이 아닌 확률적 전이 규칙을 사용한다.

단점: 조금 무겁다.