Industrial Applications


정적 채널 할당 문제


최근에 이르러 많은 무선 통신의 수요가 증가하면서 mobile telecommunication의 요구가 급속하게 증가하고 있다. Mobile환경에서 어떻게 채널(주파수)을 효율적으로 할당할 것 인가하는 문제를channel assignment problem이라 한다. 채널 할당 문제는 물리적인 지역을 나타내는 cell에서 채널에 대한 요청이 발생할 때, 이러한 요청에 대해 채널의 재사용성을 높이면서 어떻게 최적으로 할당 할 것인가 하는 NP-Complete문제이다. 정적 채널 할당문제는 주파수 할당 문제라고도 하며, 문제공간과 제약조건이 주어진 상태에서 채널을 각 cell에 채널을 고정적으로 할당하는 방법이다. 채널을 할당함에 있어서는 electromagnetic compatibility(EMC) constraint가 만족되어야 한다. EMC constraint의 세 가지 타입은 다음과 같다.

    - cochannel constraint(CCC): 같은 채널이 특정 cell들에 동시에 assign될 수 없는 조건 이다.
    - adjacent channel constraint(ACC): 인접한 cell간에 인접한 채널이 동시에 할당 될 수 없다는 조건이다.
    - cosite constraint(CSC)로써 같은 cell안에 채널이 할당될 때 할당되는 채널 사이에 최 소한의 간격차가 있어야 한다는 조건이다.

이와 같은 조건이 만족되지 않을 경우 할당된 채널간에는 간섭현상이 발생하게 된다. 각 cell에서의 주파수 요청 수와 EMC constraint를 나타내는 matrix C가 주어질 때, 최적의 채널 할당을 찾아가는 연구 주제는 크게 두 개로 나뉜다. 하나는 모든 제약 조건을 만족시켰을 때 얼마나 적은 수의 채널을 사용했는가 하는 minimum span을 구하는 주제이고, 또 하나는 사용가능 한 채널의 수를 이미 지정해 놓은 상태에서 한정된 채널에서 어떻게 할당하는 것이 가장 최적인가를 연구하는 것이다. 최근엔 무선통신의 수요가 늘어나고 사용가능 한 채널의 수가 한정되었으므로 두 번째 주제에 대한 연구가 더 활발히 진행되고 있다. 본 연구실에서는 Hybrid GA를 이용하여 주어진 문제공간에서 한정된 채널을 이용하여 최적의 할당의 방법을 연구하고 있다.


함수 최적화


1. Function approximation

    Input data로부터 output data를 설명하는 함수를 근사 추정하는 작업을 함수 최적화라고 한다. 함수 최적화를 위해 필요한 기법으로는 F code와 같은 regression anlaysis 엔진, genetic algorithm, coevolution, space smoothing 등이 고려될 수 있다.

2. Project

    핵발전소에서 원자로의 임계열수력상관식을 최적화하기 위한 프로젝트를 수행하였다. 15개 의 독립 변수들과 1개의 종속 변수로 약 2000개의 sample case가 주어졌다. 우리는 비선형 Levenberg-Marquardt 알고리즘과 유전 알고리즘을 결합하여 이용하여 최적식을 찾았으며 그 식은 기존의 알려진 식보다 7% 향상된 결과를 보여 주었다.


Vehicle Routing Problem


Vehicle Routing Problem은 자동차가 각지에 흩어져 있는 고객에게 물건을 전달하거나 가져오기 위해서 고객들을 방문할 때, 여러 가지 지정된 제약을 깨뜨리지 않고, 가장 최소의 비용으로 갈 수 있는 경로를 찾는 문제이다. 일반적으로 복수의 자동차를 가질 수 있고, 자동차에는 용량이 있어서 그 이상의 물건을 실을 수 없다. 시간에 대한 제약도 있을 수 있는 데, 각 고객마다 자신이 서비스 받을 시간대를 정해 놓고, 자동차가 그 시간대전이나 내에 도착해서 서비스를 해야 한다. 이 문제는 유명한 NP-Hard 문제인 순회 판매원 문제의 일반형이다. 즉, 순회 판매원 문제보다 풀기가 어렵기 때문에, 당연히 이 문제도 NP-Hard 문제군에 속한다. 우리 연구실에서는 순회 판매원 문제에 대한 유전 알고리즘을 성공적으로 개발하여 왔다. 그 경험을 바탕으로 Vehicle Routing Problem에 도전하고 있다.