[한국공공정책신문=최진실 기자]
◇ 유전 알고리즘의 개념
유전 알고리즘(Genetic Algorithm, GA)이란 생물의 진화 과정을 모델로 만들어진 진화적 알고리즘 중 하나이다. 확률적 탐색의 한 방법이며 1975년에 제안되었다. 유전자와 같은 모델을 사용하여 표현한 데이터군 중에서 평가함수에 대해 적응도가 높은 데이터군을 우선 선택하고 교차(재조합)나 돌연변이 등의 유전적 조작을 반복하면서 최적의 방법을 탐색한다.
◇ 데이터군의 선택 방법
데이터군을 무작위로 여러 개 작성하여 현재 세대로 한다. 현재 세대의 적응도를 계산하고 선택한 데이터군에 대해 교차, 돌연변이, 복제 중 하나를 수행한다. 그 선택의 방법은 ① 적응도 비례, ② 기댓값, ③ 랭킹, ④ 엘리트 보존 등의 지표를 이용한 전략이 있다. 교차는 2종류의 데이터군을 부분적으로 셔플하는 것으로, 단순 교차ㆍ동일 교차ㆍ부분 일치 교차 등이 있다. 돌연변이는 데이터군의 일부를 변경한다. 이렇게 작성된 새로운 데이터군을 차세대로 한다. 차세대 데이터군을 현재 세대와 동일하게 몇 개 작성한다. 이것들을 새로운 현재 세대로 하여 다시 조작을 최대 세대까지 반복한다. 이렇게 해서 현재 세대 중에서 가장 적응도가 높은 데이터군이 최적의 해답이 된다.
◇ 유전 알고리즘의 장단점
유전 알고리즘의 장점으로는 평가함수가 미분(微分)이 가능한지, 단봉성(unimodal)인지 여부 등이 확실하지 않은 경우에도 적용할 수 있다. 한편, 유전적 알고리즘의 문제점으로는 초기 파라미터의 설정에 따라 가장 바람직한 해법의 탐색이 잘되지 않는 경우를 들 수 있다.
예컨대, 첫 세대에서 적응도가 높은 데이터군이 생성됨으로써, 탐색이 비교적 초기에 수렴해 버리는 경우가 있다(과잉적합). 과잉적합은 선택 방법이나 돌연변이 조정에 의해 개선된다. 또, 적응도가 낮은 데이터가 적응도가 높은 데이터군에 뒤섞인 채 생존해 버리는 일이 있다(히치하이크). 히치하이크에 대해서는 1/2의 확률로 데이터를 교체하는 균등 교차가 유효하다.
*주) 히치하이크(Hitch hike)란 지나가는 자동차에 (무료로) 태워달라고 하는 것. 이 방법으로 여행하는 것을 히치하이킹(Hitch hiking), 여행자는 히치하이크(Hitch hike)라고 부른다.
현실 세계에는 해석의 평가는 가능해도 최적한 해법이 불분명한 문제(NP완전문제)는 다수 존재하고 있다. 그러한 해법이 비교적 확립되지 않은 문제에 대해 유전 알고리즘은 위력을 발휘한다. 순회 세일즈맨 문제 등의 조합 최적화 문제에 적용할 수 있다.
◇ 유전 알고리즘의 응용 분야
직관적인 알고리즘이면서 유전 알고리즘의 그 응용 분야는 폭넓다. ① 제어ㆍ설계 등의 공업 분야, ② 기계번역, ③ 인공생명, ④ 생물 정보학 등이 있다.
이규철 / 법학박사(상법)
∙ AI·GPT, SDGs&ESG 코치 및 강사
∙ 100세대학 크리에이터 및 칼럼니스트
∙ 생성AI와 챗GPT, SDGs·ESG경영전략,
글로벌 MBAtoCEO, 리더의 필승전략,
100세대학 행복디자인 매뉴얼 등 27권
∙ 일본(와세다대),중국(복단대·화동정법대)
){kind=small}
){kind=small}
){kind=small}
){kind=small}
