전반적 유전 알고리즘 설명.
유전 알고리즘은 초기 무작위 해 집합인 모집단(population)으로 시작합니다.
모집단의 각 개체는 문제의 해를 나타내는 염색체(chromosome)라고 부릅니다.
염색체는 연속된 세대(generation)를 통해 진화합니다.
각 세대에서는 염색체의 적합도(fitness)를 측정합니다.
다음 세대를 생성하기 위해, 교차(crossover) 연산자를 사용하여 현재 세대에서 두 염색체를 합치거나 돌연변이(mutation) 연산자를 사용하여 염색체를 수정하여 새로운 염색체, 즉 자손(offspring)을 만듭니다.
다음 세대는 (a) 부모와 자손 중 적합도 값에 따라 일부를 선택하고(b) 다른 개체는 제거하여 모집단의 크기를 일정하게 유지합니다.
적합도가 높은 염색체는 선택될 확률이 높습니다.
여러 세대를 거쳐, 알고리즘은 최적 또는 부분 최적해를 나타내는 최상의 염색체로 수렴합니다
빨간색 자르는 부분은 랜덤이다.
임시값 윗줄 : 10110110
임시값 아랫줄 : 01001001
<자손1 구하기>
부모1(P1) x 임시값 윗줄 + 임시값 아랫줄 x 부모2(P2)
자식1의 첫번째 칸 : 0x1 + 0x1 = 0 (연두색 표시부분)
자식2의 두번째 칸 : 1x0 + 1x1 = 1 -> 자손1 색칠
… 자식 끝번까지 반복
<자손2 구하기>
위와 동일 식 사용. 부모1(P1) x 임시값 윗줄 + 임시값 아랫줄 x 부모2(P2)
단, 임시값 수를 서로 바꿈.
V표시가 임시 값 0을 의미, x표시가 임시 값 1로 값을 의미하게됨.
자식2의 첫번째 칸 : 0x0 + 1x1 = 1 => 자손2 색칠
자식2의 두번째 칸 : 1x1 + 0x1 = 1 => 자손2 색칠
정리해보자면,
알파는 임시 값 1 혹은 0
X11 => 부모1의 첫째칸
Y21 => 자식2의 첫째칸
<돌연변이 과정>
본래 유전자 조합(cross over)이 있고. 이진수로 정렬되있다고 가정.
저 유전자 조합 중 랜덤으로 선택된 유전자의 index를 j라 한다.
저 j라는 인덱스가 아닐 때는 값을 그대로.
저 j라는 인덱스 차례가 왔을 때, 1 값이면 0, 0값이면 1로 무조건 다른 값을 바꿔준다.
이렇게 유전자를 계속 바꿔간다.
그리고 각 세대마다 적합도를 검사하고서
높은 적합도를 지닌 모집단만 계속 살린다.
강의 출처
https://www.youtube.com/watch?v=Fdk7ZKJHFcI&list=PLgH3sgdvgO4TQagjfi1FmPcdBjIlmk5s9
'📈알고리즘 > 알고리즘' 카테고리의 다른 글
| 근사 알고리즘(1)[여행자 문제, 정점 커버 문제, 통 채우기 문제] (0) | 2023.05.22 |
|---|---|
| 휴리스틱 flow shop 사례로 이해해보기 (0) | 2023.05.22 |
| 쉘 정렬 , 힙 정렬, 정렬 문제의 하한 (0) | 2023.05.08 |
| 버블정렬, 선택정렬, 삽입정렬 (0) | 2023.05.04 |
| 배낭문제 Knapsack (0) | 2023.04.24 |