진화연산의 구체적인 예로 유전 알고리즘(GA; Genetic Algorithm), 유전 프로그래밍(GP; Genetic Programming) 등이 있습니다. 여기서는 유전 알고리즘에 관하여 공부합니다.
2. 유전 알고리즘(GA; Genetic Algorithm)
유전 알고리즘(GA; Genetic Algorithm)은 집단 기반의 최적화 기법인 진화 알고리즘의 한 종류로 집적 회로 설계, 리보핵산(RNA:RiboNucleicAcid) 구조 예측, 인공 신경망(ANN) 학습 등 매우 다양한 분야의 최적화 및 탐색(search) 문제에 적용되고 있습니다.
유전 알고리즘은 1931년 시월 라이트(Sewall Wright)가 제안한 적합도 경관(fitness landscape)의 개념에 영향을 받았고, 1965년 잉고 레켄베르크 (Ingo Rechenberg)가 비행기 익형(airfoil)의 최적화에 진화 전략을 적용하면서 유명해졌습니다.
2.1 염색체 표현 방법
먼저 염색체 표현 방법을 알아봅니다. 유전 알고리즘에서는 염색체로 0과 1 이 숫자를 나열한 표현을 이용합니다. 구체적인 표현 방법은 풀어야 할 문제에 따라 다를 수 있으며, 아래 (그림 1)처럼 유전자의 성분으로 이진수, 실수, 문자 모두 가능합니다.
2.2 유전 알고리즘의 처리 흐름
유전 알고리즘(GA; Genetic Algorithm)은 아래 (그림 2)에 표현된 것처럼 초기 집단 형성, 적합도(fitness) 계산, 교차(crossover), 돌연변이(mutation), 선택(selection), 유전자 교체 및 반복의 과정으로 이루어집니다.
선택(selection)은 현재 세대에서 다음 세대를 생성할 때 사용하는 해답들을 결정하는 연산으로 적합도(fitness)에 따라 확률적으로 결정됩니다. 교차(crossover)는 두 해답을 결합해 새로운 해답을 만드는 과정으로 생물의 염색체 교차를 모사한 것입니다. 서로 다른 두 해답의 좋은 점을 모두 취하는 새로운 해답을 만들 수 있습니다. 돌연변이는 해답의 일부분을 무작위로 변형하는 것으로, 지역 최적 해답(local optimal solution)에 빠질 가능성을 줄여 줍니다.
1) 유전자(염색체) 집단 초기화(집단 형성)
문제 해결을 위한 랜덤 한 여러 개의 유전자(이후 '유전자'로 표기합니다)를 형성합니다. 이때 유전자의 성분으로 이진수, 실수, 문자 모두 사용 가능합니다. Randon함수를 쓸 수도 있고 사용자가 직접 난수를 입력해도 됩니다. 이렇게 유전자집단을 초기화합니다. 이때 유전자 집단에 포함된 유전자의 개수가 너무 적으면 유전정보가 유지되지 못해서 진화를 진행할 수 없습니다. 반대로 너무 많으면 유전적인 조작에 필요한 계산량이 방대해져서 계산시간이나 필요한 기억용량이 지나치게 많아집니다. 최적 집단의 크기는 문제의 성질에 따라서도 다르기 때문에 이론적으로는 결정하기가 어렵고 문제마다 실험적으로 결정할 필요가 있습니다.
초기집단의 생성을 마치면 유전적인 조작을 가해 유전자 집단의 진화를 촉진합니다. 유전자 조작으로는 교차(crossover)나 돌연변이(mutation) 혹은 선택(selection)을 도입합니다.
2) 교차(crossover)
교차(crossover)는 부모 세대의 유전자에서 부모의 유전자를 골라내고 유전정보를 섞어 자식의 유전자를 생성합니다. 교차에는 일점 교차, 다점교차, 균등 교차, 임계 교차 등이 있습니다. 일점 교차(single point crossover)는 교차점이 한 개로 부모인 두 개의 유전자에 대해 교차점부터 앞뒤를 교환하는 방법으로 유전자를 물려줍니다. 다점 교차는 말 그대로 2 이상의 다점에서 교차합니다. 교차 과정은 일점 교차와 동일합니다. 그리고 균등 교차는 모든 유전자자리에서 확률적으로 유전자를 균등하게 나누어 교차하는 것입니다. 임계 교차는 임계점을 설정하고 그 임계점에 해당하는 유전자를 선택하여 교차하는 것입니다. 그림은 일점 교차와 다점 교차의 예시입니다.
여러 가지 교차(crossover) 방법 중 어떤 방법을 택할지는 문제의 성질이나 유전자 알고리즘 전체의 설계와도 관련이 있기 때문에 실험적으로 결정하여야 합니다. 또한 교차를 위해서는 부모가 되는 2개의 유전자를 선택해야 합니다.
(다음 편에 3) 돌연변이(mutation)가 이어집니다)
2023.05.26 - [인공지능(AI; Artificial Intelligence)] - 인공지능(AI): 진화연산(Evolutionary Computation) (1)
'인공지능(AI)이란? - 기초 개념 및 이론' 카테고리의 다른 글
| 떼지능(Swarm Intelligence) (1) | 2023.05.30 |
|---|---|
| 유전 알고리즘(GA; Genetic Algorithm) (2) (1) | 2023.05.29 |
| 진화연산(Evolutionary Computation) (1) (0) | 2023.05.26 |
| 딥러닝(Deep Learning) (3) - 생성적 대립 신경망(GAN; Generative Adversarial Network) (0) | 2023.05.25 |
| 딥러닝(Deep Learning) (2) - 자기부호화기(autoencoder) 및 LSTM(Long Short-Term Memory) (0) | 2023.05.24 |
댓글