지시 ch5) 유전 알고리즘

Symbolic AI

 

1. 탐색

  (1) 맹목적 탐색

  (2) 휴리스틱 탐색

  (3) 게임 트리 탐색

 

2. 전문가 시스템 

  (1) 지식베이스

  (2) 추론 엔진

 

3. 퍼지 이론 (일단 보류)

4. 유전 알고리즘

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

진화 알고리즘 ( = 유전 알고리즘)

1. 유전 알고리즘

2. 유전 프로그래밍

 ... 등을 포함

 

자연계에서의 진화 = 일종의 최적화 연산 (Optimization)

- 적자생존 : 환경에 대한 적합도가 높은 개체가 살아남음

- 자연선택(Selection) : 살아남은 개체의 특성이 후대에 유전

- 돌연변이(Mutation) : 돌연변이를 통해 새로운 특성이 추가

 

유전자 알고리즘

 

유전자 알고리즘 절차

1. 랜덤하게 초기 해답 생성

2. 해답에 대해 적합도 평가 : 적합성 (Fitness)

3. 적합도 기준으로 2개의 해답을 선택 : 선택 (Selection)

4. 선택한 해답 유전자를 교차시켜서 다음 세대를 생성 : 교차 (Crossover)

5. 돌연변이를 통해 새로운 해답 생성 : 돌연변이 (Mutation)

유전자 알고리즘의 절차

 

선택 연산자

- 룰렛을 돌려서 랜덤하게 2개를 선택

- 조각의 크기 ( 1번의 크기 / 전체 크기 )

 -> %를 활용함

 

선택 방법

 

교차 연산자

- 두 염색체를 선택 후 교차 위치를 임의로 선택하고 교차시킴

교차 방법

 

돌연변이 연산자

- 자손에 무작위로 유전자를 삽입하는 연산

돌연변이 방법

 

유전자 알고리즘 순서도

Modeling : 문제 공간의 지식을 염색체로 인코딩

 

유전자 알고리즘 코드

https://colab.research.google.com/drive/1rbRV-eC4lcoPFaVNvKHWdpCU1boYOoGK?usp=sharing

25_1-GA.ipynb

 

유전 알고리즘 예제

TSP (Traveling Salesman Problem)을 유전 알고리즘으로 접근

 

Fitness : 거리와 관련

 

Crossover의 문제점

     [1,2,3,4,5,6]

     [4,3,2,5,6,1]

              | 기준으로 crossover을 진행

=> [1,2,3,5,6,1]

     [4,3,2,4,5,6] 

 

방문한 노드를 또 방문하게 되는 문제 발생!!

 

Mutation의 문제점

[1,2,3,4,5,6] -> [1,2,2,4,5,6]

 

 

 

 

 

 

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

Few-shot Learning

 

1. Random 초기화 (대량의 training 데이터)

2. 사전 학습(언어) + Fine-tuning(Task) 

3. Few-shot Learning (5-10개 sample)

4. Instruction-Tuning

5. In-Context Learning