KAIST, 진화프로그래밍을 이용한 최적화기법 도입 눈길

"남북한 50개 주요도시를 승용차와 항공기를 이용, 최적 경로로 여행할 경우얼마의 시간이 소요될까" 한국과학기술원(KAIST) 김종환교수팀(전기.전자공학과)은 최근 전세계적으로 활발하게 연구되고 있는 "진화프로그래밍(EP)을 이용한 최적화 기법"을 응용 해 이같은 의문을 풀어주었다.

김교수팀이밝힌 한반도 통일시 백두산에서 한라산까지 주요도시를 순회하면 서 가장 빠르게 국토순례를 하는데 걸리는 시간은 "63시간".

"진화프로그래밍을이용한 최적화기법을 국내에 널리 소개 하고 남북 통일시 국민들에게 최적의 여행경로를 제공하기 위해 이 연구에 착수했다"는 김교수 는 최적의 여행경로를 컴퓨터로 찾아내는데 채 5분이상이 소요되지 않았다.

진화프로그래밍기법을적용했기 때문에 이같이 짧은 시간안에 여행경로를 계산할 수 있었다는 것이다.

이문제를 풀기위해 김교수팀은 우선 우리나라 주요 50개도시를 선정, 좌표 상으로 그 위치를 정확하게 계산.입력한뒤 승용차로 갈 경우 각 도시간의 도로상태를 감안, 구간사이의 시속을 입력했다.

이어항공기로 가는 구간(서울~제주.부산~제주.대구~제주.진주~제주.여수~제 주, 항공기 시속은 8백km로 입력)을 설정했는데, 이때 50개 도시를 순회하는 총가짓수는 3×1천62개다.

3×1천62가짓수를 일일이 계산해서 최소시간을 가지는 경로를 찾아낼 수도있지만 이렇게 계산할 경우 3×1천50년의 시간이 소요되기 때문에 이를 통한 최적경로 산출은 사실상 불가능하다고 할 수 있다.

그러나 김교수팀이 이 문제에 적용한 진화프로그래밍 기법을 이용하게 되면단지 4×1백5개의 도시순회가짓수만으로 최소시간을 산출해낼 수 있다.

진화프로그래밍기법은 다윈의 "돌연변이법"을 통해 새로운 자손세대를 만들어내고 이를 확률적으로 선택, 점차 최적의 개체를 찾아가는 방법이다.

이를여행경로 최적화에 적용 하면 50개 도시에 일련번호를 부여하고 50개도 시를 임의의 순서로 나열한 첫 부모 세대인 1백가지의 순회경로들을 먼저 만들어낸다. 이어 진화과정을 통해 1백개의 자손을 만든후에 전체 2백가지 순회경로중 시간이 적게 걸리는 1백가지를 선택하고 , 다시 진화과정을 통해 1백가지를 생성하는 과정을 컴퓨터로 반복, 2천여 세대를 거치면 최소시간을 갖는 최적의 순회경로를 구할 수 있게 된다는 것이다.

진화프로그래밍기법은 이같은 방법으로 최적 여행경로 산출문제 뿐 아니라조립공정에서의 최적조립순서를 찾는 문제, 항공기의 최적항공 결정, 프린트 기판에서의 최적회로설계, 지능제어에의 적용 등 다양한 최적화 문제에 적용 될 수 있는 장점을 갖고 있다.

김교수는"국내의 진화프로그래밍 지식과 기술은 태동단계에 불과한 실정"이 라며 "이를 보다 효율적이고도 체계적으로 연구하기 위해 현재 국내 산. 학.

연관계자들을중심으로 산업기술진흥협회내에 "진화연산연구회"의 설립을 추진중에 있다"고 말했다.