그래프 분할

그래프 분할 문제는 여러 개의 노드들과 그 노드들 사이를 연결하는 링크로 구성된 그래프에서 노드들을 몇 개의 그룹들로 분할하고 그 그룹들 사이에 걸쳐진 링크의 수가 최소가 되는 분할을 찾는 문제이다. 분할되는 그룹이 두 개인 경우를 특히 이분할이라고 하고, 두 개보다 많은 그룹으로 분할시 다중분할이라고 한다. 이러한 그래프 분할 문제는 반도체 레이아웃과 네크워크 배치, 행렬 계산 시간 단축, 프로세서들의 스케줄링 등의 응용분야에서 핵심적인 역할을 하는 부분이다. 전산과학 분야의 대표적 어려운 문제인 NP-hard 문제군에 속한다. 현재까지 그래프 이분할 문제에 유전자 알고리즘을 결합하여 푸는 방법과 기존의 다중 분할의 문제점을 개선하여 좀 더 효율적인 다중 분할 알고리즘을 개발하는 일들이 진행되었다.

그래프 다중 분할은 그래프 이분할에 비해서 더 자연적이고 직접적인 모델을 제공하기 때문에 그래프 이분할의 중요한 확장이다. 그래프 다중 분할을 위한 대부분의 방법은 그래프 이분할을 여러 번 적용함으로써 원하는 수 만큼 분할을 얻는 것이다. 이러한 접근 방법은 전체를 보지 않고 부분만 보게 된다는 단점을 갖고 있다. 본 연구에서는 그래프 이분할에 기초하지 않고 모든 분할에 직접 관계를 하는 방법을 이용한다. 그렇게 함으로써 기존 방법이 부분만 본는 단점을 해결할 수 있었다. 이러한 방법으로 이분할에 기초한 Pairwise나 Recursive 방법보다 향상된 결과를 얻을 수 있다.

존슨 벤치마크를 통한 그래프 이등분할 문제에서 현재까지 알려진 가장 좋은 결과를 낸 바 있으며 [IEEE Transactions on Computers, 45(7), 1996], 이 기록은 본 연구실의 소스를 가져가서 비교를 행한 Battiti & Bertossi에 의해 경신되었다 [Battiti & Bertossi, 1999]. 본 연구실 내부적으로 Battiti & Bertossi의 기록을 다시 경신한 상태이다. 유전 알고리즘에 강력한 지역 최적화 알고리즘을 결합한 혼합형 방식으로 현재의 기록을 내었다 [Kim & Moon, 2000]. 본 연구실에서는 또한 ACM/SIGDA 벤치마크를 이용한 VLSI 회로의 비율 분할 문제에 있어서도 현재까지의 최고 기록을 보유하고 있다 [IEEE Transactions on CAD, 17(3), 1998; Journal of Intelligent Manufacturing, 9(5), 1998].

지수귀문도

지수귀문도는 조선시대의 수학자 최석정(1646-1715)이 고안한 육각진의 하나이다. 이 문제는 거북이의 등 모양과 같이 겹쳐지는 육각형이 여러 개 배열되어 있는 꼭지점에 숫자를 지정하여 모든 육각형의 합이 같도록 만드는 것이다. 특수한 형태의 지수귀문도에 대한 몇 가지 특수한 방법의 해들이 알려져 있지만 일반적인 해법은 아직 없다.

본 연구실의 연구 결과에 의하면 16꼭지 문제는 6억 개 정도의 다양한 정답이 존재하고, 24꼭지 문제에 대해서는 대략 40조 개 정도의 정답이 존재하는 것으로 추정된다. 본 연구실에서는 지수귀문도에 혼합형 유전알고리즘을 적용하여 198꼭지 지수귀문도를 풀어내었고 현재도 이 알고리즘을 개선하는 중이다.

순회 판매원 문제

순회 판매원 문제는 N 개의 도시가 주어질 때 한 도시로부터 출발하여 모든 도시를 한 번씩 방문한 다음 출발했던 도시로 돌아오는 가장 짧은 경로를 찾는 문제이다. 아래 그림은 1000개의 도시에 대한 가장 짧은 여행 경로를 그린 것이다. 순회 판매원 문제는 유명한 NP-Hard 문제로서 약어로 TSP (Traveling Salesman Problem)라 불린다. INSPEC 데이터베이스를 검색해 보면 최근 5년간 관련 단어로 검색되는 논문이 1,500여 편이 될 정도이다. 이 문제는 그 유명도와 고 난이도로 인해 어떤 새로운 공간 탐색 기법이 고안되면 문제에 대한 실험이 이루어지지 않고는 제대로 평가받을 수 없을 정도로 큰 영향력을 가진 문제이다.

많은 연구자들이 몇 십 개에서 많게는 수백만 개의 도시를 가진 순회 판매원 문제들을 다양한 방법으로 근사 최적해를 찾으려고 노력하고 있다. 당연히 유전 알고리즘에서도 수많은 아이디어들이 쏟아져 나왔다. 순회 판매원 문제는 물류, 택배, 스쿨버스 등의 다양한 차량 라우팅 문제들의 원형이고 VLSI 칩의 공정, 컴퓨터 보드의 생산공정 등에서도 작업의 효율을 결정하는 데 중요한 역할을 한다. 또한 X선 결정학 문제 등 다양한 분야에서 순회 판매원 문제와 연관되어 있다.

본 연구실은 94년 유전 알고리즘 분야에서는 최초로 318 도시 TSP의 최적해를 찾아내었다 [IEEE Conference on Evolutionary Conference, 1994]. 이 기록은 이후 Nagata & Kobayashi(1997)와 Merz & Freisleben(1997)에 의해 경신되었다. 본 연구실은 이 기록들을 다시 경신한 상태이다 [ Genetic and Evolutionary Computation Conference 2000 ]. 현재 보로노이 양자화를 응용한 보로노이 양자화 교차 (VQX; Voronoi Quantized Crossover)를 개발하고 이를 응용하여 10000개 도시 이상의 문제들에 대해서 최적해를 찾는데 도전하고 있다.

핵심 보유 기술은 유전 알고리즘의 새로운 인코딩 변환 기법, 교차 기법, 국소 최적화 알고리즘의 스피드업, 문제 공간 분석 등이다.

정렬망 (Sorting Networks)

정렬망(sorting networks)은 데이터의 비교와 교환이 미리 정해진 순서로 이루어지는 정렬 하드웨어이다. 정렬망은 일련의 동종 비교자(comparator)들로 구성된다.

정렬망은 최근 들어 반도체 연산 및 필터의 핵심으로 자리잡으면서 그 연구가 활발히 이루어지고 있다. 본 연구실에서는 정렬망을 구성하는 비교자의 개수를 최소화하는 최적 정렬망 (optimal sorting networks) 문제를 중심으로 정렬망에 대한 연구가 이루어지고 있다. 최적 정렬망 문제는 그 문제 공간의 복잡성으로 인해 지금까지는 주로 슈퍼 컴퓨터(supercomputer)급의 대형 컴퓨터들을 이용하여 연구가 이루어져 왔다. 본 연구실은 일반 PC만을 이용하였음에도 불구하고 기존의 연구 결과를 뛰어넘는 경쟁력 있는 연구 성과를 기록하였다.