IE Interfaces Vol. 19, No. 4, pp. 300-305, December 2006. 유전자알고리즘을 적용한 위성고객할당 최적 설계 김성수 1 김중현 2 김기동 1 이선엽 3 1 강원대학교 산업공학과 / 2 아인솔루션(주) 솔루션사업부 3 한림대춘천성심병원 방사선과 Optimal Design of Satellite Customer Assignment using Genetic Algorithm Sung-Soo Kim 1 Choong-Hyun Kim 2 Ki-Dong Kim 1 Sun-Yeob Lee 3 1 Department of Industrial Engineering, Kangwon National University, Chuncheon, Korea, 200-701 2 Byuk-San Digital valley 809, Ainsolution Co., Kuro-Gu, Kuro-Dong 212-6, Seoul, Korea 3 Department of Radiology, Hallym University Chuncheon Sacred Heart Hospital,Chunchon, Korea, 200-704 The problem of assigning customers to satellite channels is considered in this paper. Finding an optimal allocation of customers to satellite channels is a difficult combinatorial optimization problem and is shown to be NP-complete in an earlier study. We propose a genetic algorithm (GA) approach to search for the best/optimal assignment of customers to satellite channels. Various issues related to genetic algorithms such as solution representation, selection methods, genetic operators and repair of invalid solutions are presented. A comparison of GA with CPLEX8.1 is presented to show the advantages of this approach in terms of computation time and solution quality. 1) Keyword: Satellite Customer Assignment (SCA), Genetic Algorithm (GA) 1. 위성고객할당문제의 정의 및 모델링 위성통신분야에서 자원의 효율성 관련 연구들 중에서 Rote and Vogel(1993), Dell Amico and Martello (1996)은 위성자원의 효율 적인 사용을 위해 위성통신 스케줄링(scheduling)에 대하여 연 구하였다. 또한, Prins(1994)는 위성통신 스케줄링 문제에 대하 여 전반적으로 정리 분류하였다. Lee et al.(2003)는 위성통신에 서 최적의 라우팅(routing) 방법에 대하여 연구하였다. 이와 같이 기존 위성통신관련 연구에서는 주파수와 파워의 효율적 사용에 대한 연구가 주 관심 사항은 아니었으나, Scott et al.(2000)은 고객이 요구하는 각 시그널에 따라 서로 다른 주파 수와 파워수준을 갖는다고 서술하고, 최선의 자원 할당을 위 해서는 고객이 요구하는 가장 적절한 주파수를 할당해야 한다 고 설명하였다. 또한, 그들은 위성고객할당(satellite customer assignment, SCA) 문제를 I명의 고객들에게 J개의 채널 중에서 적 어도 1개를 할당하고자 하는 수리적 모델을 제시하고 정수계 획 방법으로 풀기 위해 비선형문제를 선형계획문제로 변환하 여 풀고자 시도하였다. 이외에도 무선채널할당 문제를 다룬 논문들로는 Lai and Coghill(1996), Beckmann and Killat(1999), Ghosh and Sinha(2003) 등이 있는데 기존 논문들에서는 실제 상 황에서 몇 초안에 어느 정도의 성능지표를 갖는 해로 의사결 정을 해야 한다는 데이터를 제시 못하고 논문에서 사용한 테 스트 문제의 난이도와 컴퓨터 성능에 따라 다양한 결과를 제 시하였다. 실제 문제에 따라 시스템 운용자 및 사용자가 요구 본 논문은 2006년 강원대학교 정보통신연구소의 일부 지원에 의하여 연구되었음. 연락저자 : 김성수 교수, 200-701 춘천시 효자 2동 192-1 강원대학교 산업공학과, Fax : 033-255-6281, E-mail : kimss@kangwon.ac.kr 2006년 06월 접수, 2회 수정 후 2006년 10월 게재확정.
유전자알고리즘을 적용한 위성고객할당 최적 설계 301 하는 해결 시간과 성능지표에 맞추어 의사 결정을 해야 한다. 본 논문에서 해결하고자 하는 SCA 문제는 위성의 주파수대 역과 파워의 용량제약을 만족해야만 하고 각각의 고객은 위성 채널 하나에만 할당되어야 한다. 이러한 제약 조건을 만족하 면서 위성의 주파수 대역의 이용률과 위성의 파워 이용률의 총 차이를 최소화하기 위하여 어떻게 고객을 위성 채널에 할 당할 것인가를 찾아내는 것이다. 다시 말해서, 주파수 대역의 사용과 채널에 대한 파워의 균형을 잡기 위한 것이다. SCA 문제의 수리적인 모델의 평가식은 모든 채널에 대해서 고객의 주파수대역과 파워의 이용률의 편차의 합의 최소화를 나타내고 가장 이상적인 해는 이 편차의 합이 0인 경우이다. SCA 문제의 평가를 위한 식 (1)에서 의사결정변수 는 고객 i 가 채널 j에 할당되었다면 1, 그렇지 않으면 0이 된다. SBWj 는 위성채널 j에 대한 가용 주파수 대역을 나타내고 SPj는 위성채 널 j에 대한 가용 파워를 나타낸다. CBWi 는 고객 i의 주파수 대역 요구량을 나타내고 CPi 는 고객 i의 파워 요구량을 나타낸 다. 는 채널 j를 이용하는 모든 고객의 주 파수대역상의 이용효율을 나타낸다. 또한, 는 채널 j를 이용하는 모든 고객의 가용파워의 이용효율을 나 타낸다. 식 (1)은 위성통신의 자원인 채널 사용의 효율성을 높 이기 위해 모든 채널 j에 대하여 고객 i의 주파수대역 이용률과 고객 i의 파워 이용률의 편차의 합을 최소화하는 것을 목표로 한다. 즉, 각 채널에 대한 주파수와 파워이용의 트랜스폰더의 균형을 맞추기 위한 것이다. Minimize (1) SCA문제의 제약식들은 식 (2), 식 (3), 식 (4)와 같다. 식 (2)와 식 (3)은 각각 위성의 주파수대역과 파워의 용량제약을 나타낸 다. 또한, 식 (4) 는 각각의 고객은 위성채널 하나에만 할당되어 야 한다는 것을 나타낸다. (2) (3) (4) 그런데, SCA문제는 일반적인 할당문제의 유형과 매우 흡사 하다. Cattrysse and Wassenhove(1992)는 이와 같은 할당문제는 NP-complete 조합 문제라 하였다. 일반적으로 할당 문제는 정 확한 해를 찾는 알고리즘해법으로 적용할 경우 문제의 난이도 가 증가할수록 최적해를 탐색하는 계산시간이 지수적으로 급 격하게 증가하게 된다. SCA 문제는 짧은 시간 내에 최적해 또는 근접 해를 찾아 사 용 해야 하기 때문에 기존 해법을 적용하기 부적절하다. 따라 서, 본 논문에서는 SCA문제에 대하여 시스템 사용자가 요구하 는 제한된 시간 내에 최적해 또는 최적해에 근접한 가장 좋은 해를 탐색할 수 있는 유전자알고리즘(genetic algorithm, GA)을 개발 하여 제안하고자 한다. 특히, 본 논문에서 유전자알고리 즘을 사용한 이유는 Ghosh et al.(2003)와 Ngo et al.(1998)가 언급 한 것처럼 Neural network은 태생적으로 local optima를 찾는 것 에 문제가 있고 simulated annealing은 수렴율에 문제가 있는데, GA는 수렴율이 다른 휴리스틱 알고리즘에 비하여 상대적으로 좋기 때문이다. 본 논문에서 제안하는 GA방법과 기존 방법과의 차별성은 고객의 수만큼의 크기 염색체로 표현하고 각 유전인자를 할당 채널로 표시하여 교배 및 돌연변이가 효율적으로 수행되도록 하였다. 특히, 돌연변이 과정을 2단계로 나누어 고객을 중심으 로 채널을 돌연변이 시키고 같은 채널을 갖는 고객들에게 다 른 임의의 채널로 돌연변이 시킴으로 하여 다양한 탐색을 유 도하였다. 또한, 최적화 방법 적용과정에서 발생되는 불가능 해를 효과적으로 교정하는 방법도 제시하였다. 2절에서는 SCA문제에 적용할 수 있는 GA를 제시하였는데, 해의 표현과 평가 방법, SCA문제에 적합한 교배와 돌연변이 방 법, 교배, 돌연변이 등을 통하여 생성될 수 있는 불가능 해들의 교정 방법을 제시하였다. 3절에서는 SCA 문제 식 (1)~식 (4)에 대하여 제안하는 GA를 적용한 결과와 식 (1)의 절대값에 의한 비선형 문제를 선형문제로 변환하여 CPLEX 8.1(2003)로 구한 최적해와의 비교 분석한 결과를 제시 하였다. 2. 유전자알고리즘을 적용한 최적설계방법 유전자알고리즘은 한 세대에서 염색체들을 평가하고 이들의 평가값을 기반으로 확률에 의해 재생산하고 교배 및 돌연변이 를 거침으로써 다음세대의 염색체들은 더 우수한 평가값을 유 지하게 된다(Holland, 1975; Goldberg, 1989; Michalewicz, 1996). 위성고객할당(SCA)문제에 GA를 적용할 때 주요 핵심사항은 다음과 같다. 첫째, 각각의 고객에 어떤 고유번호의 채널을 할 당할지를 나타내는 것이다. 즉, 채널을 할당한 해를 어떻게 염 색체로 표현할 것인가? 둘째, 각 채널할당 해를 평가할 수 있는 정확한 평가함수는 무엇인가? 셋째, 제약조건을 만족하면서 어떻게 효율적으로 염색체 선택 및 재생성방법, 교배와 돌연 변이를 할 것인가? 이 밖에도 염색체집단의 크기, 교배율과 돌 연변이율, 종료조건 등 GA의 파라미터를 정해야 한다. 위성고객할당을 위한 유전자알고리즘의 적용 전체 메카니 즘은 <Figure1>과 같이 나타낼 수 있다. 유전자를 채널 번호로
302 김성수 김중현 김기동 이선엽 나타내고 고객의 수만큼의 유전자들로 구성하여 표현된 염색 체들을 개체 수만큼 2.1절에 설명한 것과 같이 생성한다. 각각 의 염색체들을 평가하고 가능한 해가 아닐 경우 2.3절과 같이 가능하지 않은 해는 가능해로 교정한다. 개체수 중에서 룰렛 휠선택(roulette wheel selection, 평가값에 기초한 확률분포에 의 한 새로운 개체집단의 선택) 방법을 사용하여 평가값에 따라 2 개체를 선택하여 2.2절과 같이 교배율에 따라 유니폼교배를 실 행하고 교배가 이루어지지 않으면 선택된 개체 중 더 좋은 평가 값을 갖는 개체를 선택하여 새로운 개체군에 추가한다. 새로운 개체군이 재생성 되면 고객에 대한 1단계 돌연변이와 채널에 대한 2단계 돌연변이를 실행하게 된다. 이와 같이 교배와 돌연 변이 후에 생성된 불가능한 해에 대한 교정과 평가를 다시 하게 된다. 이와 같은 유전자알고리즘 적용 메커니즘을 반복 수행하 여 종료조건을 만족하게 되면 프로그램을 종료하게 된다. 게 채널 1, 고객 6에게 채널 1, 고객 7에게 채널 2를 할당하는 것 을 뜻한다. 초기해군의 생성은 다양한 가능해 탐색을 위하여 임의로 선택된 각각의 고객에 대하여 임의로 선택된 채널을 할당한다. 2.2 교배와 돌연변이 <Figure 2>에 나타난 것과 같이 임의로 0과 1로 구성되는 염 색체 길이와 같은 이진행렬을 생성한 후 자식 1에 대해 이진행 렬의 값이 0인 부모 1의 값을 복사하고, 이진행렬의 값이 1인 부분에는 부모 2의 값을 복사한다. 그리고 자식 2에 대해서는 그 반대로 적용하는 이진행렬에 따른 교배방법을 적용하였다. Parent 1 2 1 3 3 1 1 2 Start Generation of initial population Reparir & evaluation of solution Parent 2 Binary matrix Child 1 Child 2 3 2 2 3 1 2 3 0 1 0 0 1 1 1 2 2 3 3 1 2 3 3 1 2 3 1 1 2 Figure 2. An example of uniform crossover Two chromosomes selected using roulette wheel Select better one from two chromosomes no Pc > random # yes Uniform crossover New population generated? no yes Step 1 Mutation for customer Step 2 Mutation for channel no 2.1 해의 표현과 생성 Update optimal solution after repair & evaluation of solution Stopping condition? Termination yes Figure 1. GA mechanism for SCA GA와 같은 휴리스틱 알고리즘을 적용할 때에는 해의 표현 을 어떻게 하느냐 하는 것은 최적해 탐색을 위한 계산시간 등 에 큰 영향을 준다. 따라서, 본 논문에서는 GA의 해의 표현을 다음과 같이 사용함으로써 효율성을 최대화 하였다(Chu et al., 1997, Etiler et al., 2004). I명의 고객에 각각 J 개의 채널 중에서 1 개의 채널을 할당한다고 한다면, 가능해의 수는 J I이다. 즉, 만 약 I = 7 (1~7), J = 3 (1~3)이라면 총 가능해의 수는 37=243이 다. 예를 들어, 가능해 [2 1 3 3 1 1 2] 는 고객 1에게 채널 2, 고객 2에게 채널 1, 고객 3에게 채널 3, 고객 4에게 채널 3, 고객 5에 Figure 3. An example of mutation 문제의 특성상 염색체 하나의 유전인자에 의해 평가값에 큰 변화가 있을 수 있고 또한 하나의 채널에 할당된 고객 그룹 입 장에서 보면 고객그룹을 어떤 채널에 배속 시키느냐에 따라 전혀 다른 결과를 얻을 수도 있다. 그러므로, 돌연변이는 여러 가지 방법을 실험 적용 후 해의 다양한 탐색을 위해 2단계로 적 용 하였다. 2단계로 이루어진 돌연변이는 단계별로 돌연변이 율에 따라 각 단계를 수행 또는 수행하지 않을 수 있다. 1단계 에서 각 세대의 모든 염색체들을 대상으로 돌연변이율에 따라 하나의 유전자를 임의로 선택하고, 그 고객에 대한 유전인자 (채널)를 임의로 선택된 다른 채널로 바꿔준다. 1단계를 거친 염색체중 일부는 돌연변이 연산을 종료하고 일부는 2단계에 서 임의의 특정 채널을 가지고 있는 모든 고객의 채널을 임의 로 선택된 다른 채널로 교환해준다. <Figure 3>(1)은 임의로 선 택된 염색체가 1단계에서 임의로 선택된 5번째 고객에 할당된 채널4를 임의로 선택된 채널 1로 돌연변이 시키는 것을 설명하 고 있다. <Figure 3>(2)는 돌연변이율에 따라 1단계를 거치지
유전자알고리즘을 적용한 위성고객할당 최적 설계 303 않았을 경우 (3)과 같이 2단계에서 임의로 선택된 3번 채널에 할당된 모든 고객을 임의로 선택된 1번 채널로 돌연변이 시키 는 경우를 나타낸다. <Figure 3>(4)는 1단계 5번째 고객에 대한 돌연변이를 거친 염색체를 (5)와 같이 2단계에서 임의로 선택 된 2번 채널에 할당된 모든 고객을 임의로 선택된 4번 채널로 돌연변이 시키는 것을 나타낸 것이다. 2.3 해의 평가 및 교정 모든 해(염색체)에 대한 평가는 식 (1)에 의해 간단히 할 수 있으나 모든 염색체에 대한 초기 염색체 생성 후 또는 교배나 돌연변이후에 식 (2)와 식 (3)의 제약에 의해 불가능한 해가 발 생될 수 있다. 불가능해의 확인은 바로 알 수 없고 평가한 이후 에 알 수 있기 때문에 해의 평가 수행 시 교정을 수행한다. 교정 방법은 다음과 같이 3단계로 수행된다. 1 단계는 불가 능한 해를 야기하는 채널의 고객집합 G를 구한다. 2단계는 G 에서 임의의 고객 x를 선택해서 임의의 다른 채널을 할당한다. 3 단계는 모든 채널에서 불가능해가 없으면 종료하고 만약 불 가능해가 존재하면 1단계를 다시 수행한다. 예를 들어 고객의 수가 5, 채널의 수가 3인 경우, 고객 i의 주파수 대역 요구량이 CBW1=5, CBW2=4, CBW3=6, CBW4=7, CBW5=3과 같고 고 객 i의 파워요구량이 CP1=7, CP2=9, CP3=8, CP4=6, CP5=5라 하자. 위성채널 j에 대한 가용 주파수 대역은 SBW1=10, SBW2 =16, SBW3=이고 위성채널 j에 대한 가용 파워가 SP1=15, SP2=31, SP3= 라고 하자. <Figure 4>에서는 1번 채널의 파 워효율이 (9+8)/15로 제한식 식 (2)에 위배되기 때문에 불가능 해를 야기하므로 1번 채널을 가지고 있는 2, 3번 고객 중에서 임의로 선택된 3번 고객에게 임의로 선택된 다른 채널 2를 할 당함으로써 해를 교정하는 예를 보이고 있다. 새로 생성된 염 색체의 파워 효율과 주파수 대역 효율은 제한식 (2)와 식 (3)을 모두 만족하는 가능해가 된다. 3 Restriction for channel #1 1 1 3 2 Repair 3 1 2 3 2 3. 실험 및 분석 Fraction of bandwidth utilized for each channel 9+8 15 9 15 5 31 5+8 31 7+6 7+6 Fraction of power utilized for each channel 4+6 10 4 10 Figure 4. The repair of infeasible solution 3절에서는 1절에서 공식화한 SCA문제에 2절에서 제안한 유전 자알고리즘을 적용 실험하였다. SCA문제 최적화 시뮬레이션 은 펜티엄Ⅳ 2.0MHz, 256Mbytes RAM환경에서 JAVA로 구현하 였다. 3 16 3+6 16 5+7 5+7 3.1 SCA 적용문제 본 논문에서 제안한 유전자알고리즘의 성능 측정을 위해 테 스트 문제들을 문제크기에 따라 두 가지 종류로 나누었다. 하 나는 고객의 수가 5이고 채널수가 3일 경우 고객의 대역폭 요 구량이 CBW1=5, CBW2=4, CBW3=6, CBW4=7, CBW5=3이 고 고객의 파워 요구량이 CP1=7, CP2=9, CP3=8, CP4=6, CP5=5로 각 문제에 대한 위성의 대역폭과 파워는 <Table 1> 과 같다. Table 1. Satellite bandwidth & power available in channels Prob SBW 1 SBW 2 SBW 3 SP 1 SP 2 SP 3 1 30 35 40 40 45 50 2 9 11 9 21 17 11 3 18 11 19 21 21 21 아래 문제 4는 고객의 수가 20이고 채널수가 10일 경우로 고 객의 대역폭 요구량과 파워 요구량은 <Table 2>에서 위성의 대역폭과 파워의 용량은 <Table 3>에 각각 주어졌다. Table 2. Bandwidth & power required by customer i Customer CBW CP 1 5 5 2 5 8 3 5 9 4 5 5 5 4 7 6 4 6 7 3 8 8 7 6 9 6 7 10 5 8 11 6 6 12 3 7 13 6 9 7 9 15 4 7 16 3 7 17 6 5 18 6 7 19 4 5 20 4 9 Table 3. Bandwidth & power available in channels for problem 4 1 2 3 4 5 6 7 8 9 10 SBWj 22 13 15 20 15 15 15 22 19 13 SPj 31 19 24 26 25 24 18 28 23 29
304 김성수 김중현 김기동 이선엽 3.2 유전자알고리즘의 적용과 결과 분석 유전자알고리즘의 기본적인 파라미터로는 염색체수, 교배 율, 돌연변이율 등이 있다. 실험은 1개의 염색체가 1세대를 진 화하는 것을 1 사이클로 정의했을 때 40000사이클을 기준으로 염색체수와 세대 수를 정하고 다른 조합의 교배율과 돌연변이 율로 실험하였다. <Table 4>는 교배율과 돌연변이율을 각각 0.5, 0.5로 두고 염색체수와 세대수에 따라 100회 수행 후 구한 평가값의 평균을 나타낸 것이다. 복잡도가 낮은 문제인 문제 1, 2, 3은 상대적으로 어렵지 않기 때문에 비교적 간단히 최적해 를 모두 찾을 수 있었다. 상대적으로 복잡도가 높은 문제4는 한 세대의 염색체수가 20일 때 가장 결과가 좋았기 때문에 염색체 수를 20으로 하여 실험하였다. Table 4. Results with different pop-size & number of generations Prob Population size Number of generation 20 2000 40 1000 100 400 160 250 200 200 1 0.041666 0.041666 0.041666 0.041666 0.041666 2 0.046108 0.046108 0.046108 0.046108 0.046108 3 0.030303 0.030303 0.030303 0.030303 0.030303 4 0.023675 0.026913 0.025926 0.023474 0.026503 <Table 5>는 한 세대의 염색체수를 20으로 할 때 복잡도가 높은 문제 4에 대하여 다양한 교배율과 돌연변이율의 조합에 따라 100회 수행 후 구한 평가값의 평균을 나타낸 것이다. 교배 율 0.9, 돌연변이율 0.5일 때 평가값 0.017471이 가장 결과가 좋 았다. Table 5. Results with different crossover & mutation rates Mutation Crossover 0.1 0.3 0.5 0.7 0.9 0.1 0.043290 0.035326 0.028765 0.028991 0.070460 0.3 0.039763 0.029910 0.024195 0.030738 0.078483 0.5 0.037505 0.031629 0.023675 0.036847 0.080700 0.7 0.036536 0.027439 0.022356 0.051130 0.093367 0.9 0.040278 0.029090 0.017471 0.058418 0.103351 <Figure 5>는 문제 4에 대해 본 논문에서 제안한 유전자알 고리즘을 1회 적용했을 때 평가값이 수렴하는 패턴을 나타낸 다. 위에서 설명했듯이 한 세대의 개체수는 20개, 교배율 0.9, 돌연변이율 0.5를 적용하였다. 두 문제에 대한 수렴 경향이 뚜 렷하며 300세대 전후에서 안정된 최소값을 찾을 수 있었다. 지금까지 설명한 유전자알고리즘(GA) 결과와 CPLEX8.1을 사용한 최적해와 비교분석 하여 SCA문제에 대한 GA의 성능 을 검증하고자 한다. GA를 적용한 실험의 종료조건은 SCA문 제의 이상적인 해인 0을 찾거나 해의 개선이 더 이상 없이 정 체가 1000 사이클 동안 지속되면 종료하도록 한다. 단, 평가 값 의 정체 없이 해의 변동이 계속될 경우 3000세대를 종료조건 으로 하였다. <Table 6>은 염색체 20개로 개체군을 형성하고 교배율 0.9, 돌연변이율 0.5로하여 200회 실험했을 때 GA방법 의 결과에 대한 평균, 최소값, 최대값 편차를 나타낸 것이다. 식 (1)~식 (4)로 공식화된 SCA문제를 정수계획법으로 풀기 위 해 식 (1)의 절대값에 의한 비선형 문제를 선형문제로 변환하 여 CPLEX8.1을 사용하여 최적해 0을 찾았다. GA가 최적해 0 을 탐색하는 평균계산시간 298.56초와 같이 상대적으로 계산 소요시간이 많이 소요된다. 그러나, GA 방법은 아주 짧은 평 균계산시간 0.72초에 최적해 0에 근접한 해를 찾을 수 있었다. <Figure 6>은 문제 4에 대해 GA를 200회 수행했을 때 각각의 평가값을 나타낸 것이다. 분석결과와 같이 실제 위성고객할 당문제에 실시간 또는 거의 실시간에 의사 결정을 하기 위해 서는 본 논문에서 제안하는 GA방법이 매우 효율적으로 사용 될 수 있을 것으로 분석되었다. 실제 문제에 따라 시스템 운용 자 및 사용자가 요구하는 해결 시간과 성능지표에 맞추어 의 사 결정을 할 수 있다. 즉, 본 논문에서 사용한 유전자 알고리 즘 등 휴리스틱 알고리즘 등은 최적해를 보장하지 못하지만, 시스템에서 요구하는 시간 내에 가장 좋은 해를 탐색하여 제 시할 수 있다. Table 6. Results comparison between GA & CPLEX8.1 Aver Min Max Deviation Time(sec) GA 0.020331 0.002653 0.038433 0.008375 0.72 CPLEX - 0.0 - - 298.56 Cost 0.6 0.5 0.4 0.3 0.2 0.1 0 1 37 73 109 5 181 217 253 289 325 361 397 433 469 505 541 577 613 649 685 721 757 793 829 865 Generation Figure 5. The trend of evaluation value for problem 4 Cost 0.05 0.045 0.04 0.035 0.03 0.025 0.02 0.015 0.01 0.005 0 0 20 40 60 80 100 120 0 160 180 200 Iterations Figure 6. Distribution of results using GA for problem 4
유전자알고리즘을 적용한 위성고객할당 최적 설계 305 4. 결 론 본 논문의 중요한 의미는 NP-complete 조합문제인 위성고객할 당(SCA)문제를 계산소요시간과 해의 정확도 측면에서 효율적 으로 탐색할 수 있는 유전자알고리즘(genetic algorithm, GA)을 개발 제안한 것이다. 본 논문에서 제시하는 GA는 SCA문제에 가장 적합한 교배와 돌연변이, 해의 교정 방법을 제시하였다. SCA문제에 맞게 최적 설계한 GA 방법은 CPLEX8.1로 찾은 최 적해와 비교분석 했을 때 매우 짧은 계산 시간 내에 최적해에 근접한 좋은 해를 효과적으로 탐색해 낼 수 있음을 검증하였 다. 따라서, 위성고객할당(SCA) 최적해를 본 논문에서 제시한 GA를 적용하여 위성정보기술시스템의 효율성을 더욱 증대시 킬 수 있다. 참고 문헌 Beckmann, D. and Killat, U.(1999), A new strategy for the application of genetic algorithms to the channel-assignment problem, IEEE Transactions on Vehicular Technology, 48(4), 1261-1269. Cattrysse, D. and Wassenhove, L. N. Van(1992), A survey of algorithms for the generalized assignment problem, European Journal of Operational Research, 60, 260-272. CPLEX 8.1(2003), CPLEX Optimization Inc. Chu, P. C. and Beasley, J. E.(1997), A genetic algorithm for the generalized assignment problem, Computers and Operations Research, 24, 17-23. Dell Amico, M. and Martello, S.(1996), Open shop satellite communication and a theorem by Egervary, Operations Research Letters, 18. 209-211. Etiler, O., Toklu, B., Atak, M., and Wilson, J.(2004), A genetic algorithm for flow shop scheduling problems, Journal of the Operational Research Society, 55, 830-835. Ghosh, S. C. and Sinha, B. P.(2003), Channel Assignment using Genetic Algorithm based on Geometric Symmetry, IEEE Transactions on Vehicular Technology, 52(4), 860-875. Goldberg, D. E.(1989), Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley publishing company, Inc. Holland, J. H.(1975), Adaptation in Natural and Artificial Systems, The University of Michigan Press, Michigan. Lai, W. K. and Coghill, G. G.(1996), Channel Assignment through Evolutionary Optimization, IEEE Transactions on Vehicular Technology, 45(1), 91-96. Lee, H., Ahn, D. H., and Kim, S.(2003), Optimal routing in non-geostationary satellite ATM networks with intersatellite link capacity constraints, Journal of Operational Research Society, 54, 401-409. Michalewicz, Z.(1996), Genetic Algorithms+Data Structures = Evolution Programs, Springer. Ngo, C. Y. and Li, V.(1998), Fixed Channel Assignment in Cellular Radio Networks using a Modified Genetic Algorithm, IEEE Transactions on Vehicular Technology, 47(1), 163-172. Prins, C.(1994), An overview of scheduling problems arising in satellite communications, Journal of the Operational Research Society, 45, 611-623. Rote, G. and Vogel, A.(1993), A Heuristic for Decomposing Traffic Matrices in TDMA Satellite Communication, ZOR, 38, 281-307. Scott, C. H., Skelton, O. G., and Rolland, E.(2000), Tactical and strategic models for satellite customer assignment, Journal of the Operational Research Society, 51, 61-71. 김 성 수 한양대학교 산업공학과 학사 일리노이대, 위스콘신대 산업공학과 석사 아리조나주립대 산업공학 박사 현재: 강원대학교 산업공학과 부교수 관심분야: 정보기술 최적화 설계, 네트워크 시스템, 물류정보시스템 김 기 동 서울대학교 산업공학과 학사 서울대학교 산업공학과 석사 서울대학교 산업공학과 박사 현재: 강원대학교 산업공학과 부교수 관심분야: ERP, MES, SCM, 일정계획 김 중 현 강원대학교 산업공학과 학사 강원대학교 산업공학과 석사 현재: 아인솔루션(주) 사원 관심분야: 정보기술 최적화 설계, 네트워크 시스템, ERP, SCM, MES 이 선 엽 신구대학 방사선학과 학사 연세대학교 보건관리학과 석사 강원대학교 산업공학과 박사과정 현재: 한림대학교병원 MRI팀장 관심분야: Medical Export System, Artificial Intelligence, CAD