탄도미사일 방어무기체계 배치모형 연구 (Optimal Allocation Model for Ballistic Missile Defense System by Simulated Annealing Algorithm) 이 상 헌 국방대학교 운영분석학과 우 122-875 서울시 은평구 수색동 205번지 Abstract The set covering(sc) problem has many practical application of modeling not only real world problems in civilian but also in military. In this paper we study optimal allocation model for maximizing utility of consolidating old fashioned and new air defense weapon system like Patriot missile and develop the new computational algorithm for the SC problem by using simulated annealing(sa) algorithm. This study examines three different methods: 1) simulated annealing(sa); 2) accelerated simulated annealing(asa); and 3) selection by effectiveness degree(sed) with SA. The SED is adopted as an enhanced SA algorithm that the neighboring solutions could be generated only in possible optimal feasible region at the PERTURB function. Furthermore, we perform various experiments for both a reduced and an extended scale sized situations depending on the number of customers(protective objective), service(air defense), facilities(air defense artillery), threat, candidate locations, and azimuth angles of Patriot missile. Our experiment shows that the SED obtains the best results than others. 1. 서 론 설비배치와 입지선정문제를 기존의 정성적 접근방법에 서 벗어나 수학적 방법을 통해 해결하려는 시도가 여러 분야에서 이루어지고 있다. 지역담당(Set Covering) 모형은 이러한 연구 분야중 하나로 주어진 문제를 수학적으로 현 실과 유사하게 구현시킬 수 있고 모형에 대한 해법절차도 다양하기 때문에 여러 형태의 배치문제들에도 폭넓게 적 용되어 왔으며 최근 들어서는 군사설비분야에서 도 그 활 용도가 높아지고 있다. 현재 군에서 기존에 운용하던 무기체계들의 노후화 및 성능저하에 따라 이를 극복하기 위한 여러 형태의 무기체 계 도입사업이 진행되고 있다. 본 연구에서는 신규 무기체 계 설비 배치시 기존전력 기반위에 신구 전력의 전체능 력을 통합적으로 평가하여 최적의 설비배치를 결정할 수 있는 새로운 지역담당모형을 개발하였고 이 모형을 이용 하여 한국공군에서 추진 중인 SAM-X사업의 패트리어트 배치문제에 적용함으로써 그 활용방안을 제시하고자 한다. 본 연구에서는 새로운 지역담당모형의 개발과 더불어 SA(Simulated Annealing)알고리즘을 활용하여 대규모 설 비배치 문제에 대한 해 유도과정으로 구성하고 이 과정에 서 야기되는 부분적인 제한사항들을 보완하였으며 다양한 형태의 실험과 비교분석을 통해 메타 휴리스틱 기법이 지 역담당문제에 대한 일반 해법절차가 될 수 있음을 제안하 고자 한다. 2. 기존연구 고찰 지역담당문제는 주어진 지역 내 모든 고객을 담당할 수 있는 최소의 설비 수와 위치를 결정하기 위한 전체담당문 제와 가용한 예산한도 내에서 가능한 많은 수의 고객을 담당할 수 있는 설비배치를 결정하기 위한 부분담당문제 로 구분된다. 그리고 설비의 고객에 대한 담당여부에 확률 개념을 도입하고 중복담당효과를 고려할 수 있는 신뢰도 모형 등이 있다. 2.1 전체지역담당 (Total Set Covering) 모형 전체지역담당모형이란 모든 고객이 최소한 하나 이상의 설비로부터 담당되면서 설비배치에 드는 총비용을 최소화 하기 위한 것으로 식 (1) 과 같이 표현할 수 있다. (1) 위의 식 (1) 에서 는 설비를 후보지 에 1대 배치하는 비용이고 는 고객담당여부로 고객 가 후보지 에 배 치되는 설비로부터 담당될 수 있으면 1, 그렇지 않으면 0 이 되며, 의 관계에 따라 미리 결정되는 값이다. 는 결정변수로 설비가 후보지 에 배치되면 1, 그렇지 않으 면 0 으로 표현된다. 만약, 각 후보지별로 설비배치비용 ( ) 이 일정하다면 총 배치수량의 최소화문제 로 변형하여 적용할 수 있다. 전체담당문 제의 해를 구하는 방법으로는 정수계획법에 의한 평면절 단기법(Bellmore and Ratliff, 1971) 과 분지한계법(Lawer and Wood, 1996) 등이 있으며 이들 기법은 항상 최적해 를 구할 수는 있으나 문제의 규모가 조금만 커져도 해를 - 1020 -
찾기가 제한된다. 2.2 부분지역담당 (Partial Set Covering) 모형 부분지역담당모형은 가용예산 등의 제한사항으로 인해 주어진 자원( 비용, 설비 수 등) 한도 내에서 고객담당을 최대화시킬 수 있는 설비배치를 판단하기 위한 것으로 식 (2) 와 같이 표현할 수 있다. (2) 위의 식 (2)에서 목적함수내 는 고객담당규 모를 판단하기 위한 것으로 한 고객( ) 이 여러 설비들() 로부터 중복 담당되더라도 목적함수 값에는 오직 1만 증가 시킴을 의미하며 제약식 는 총 배치수량이 가 용량( ) 을 초과할 수 없다는 것이고 주어진 자원이 전체 예산( ) 이라면 로 변경하여 적용할 수 있 다. 부분지역담당문제의 해를 구하기 위한 방법으로는 분지 한계법(Lawer and Wood, 1996) 과 Ignizio(1971) 가 개발한 휴리스틱 기법 등이 있다. 2.3 신뢰도 (Reliability Set Covering) 모형 신뢰도모형은 부분담당문제를 보다 일반화시킨 형태 로 식 (3) 과 같이 표현할 수 있으며 주어진 자원한도를 초 과할 수 없다는 제약 하에 모든 설비들이 각 고객을 담당 할 수 있는 전체 확률을 최대화시키는 것을 목적으로 한 다. 위의 식 (3) (3) 에서 는 제한된 설비수이고 는 고객 가 설비 로부터 담당될 수 있는 확률이며 는 고객의 중요도를 구분하기 위한 가중치로 모든 고객의 여건이 동 일하다면 이 되어 수식에서 생략할 수 있다. 신뢰도모형에 대한 해법으로는 비선형의 수식을 단순한 선형문제로 재구성한 후 분지한계법을 적용한 김성인 (1987) 의 해법과 Yoshiaki(1975) 의 휴리스틱 기법을 변형 한 효과도법( 오제상, 1981) 등이 있다. 일반적으로 지역담당문제는 NP-Complete문제로 정수계 획법에 의한 해법들을 이용할 경우 정확한 해를 구할 수 있는 반면 문제의 크기가 커질수록 계산시간도 지수적으 로 증가하게 된다. 또한 최근의 지역담당모형에 대한 연구 들은 모형구조가 매우 복잡하고 문제의 규모 역시 방대하 게 모델링 되는 추세이다. 따라서 대규모 지역담당모형에 대한 해법으로는 합리적인 시간 내에 근사 최적해를 제공 할 수 있는 휴리스틱 접근방법이 효율적이라 판단된다. 지역담당문제에 대한 기존의 휴리스틱 해법으로는 Ignizio(1971) 알고리즘을 많이 활용하였고 신뢰도모형이 개발된 이후에는 비선형의 수식을 계산하기 위하여 Yoshiaki(1975) 알고리즘을 변형한 효과도법( 오제상, 1981) 이 주 해법으로 사용되어왔다. 이들 해법은 비교적 짧은 계산시간에 상대적으로 우수한 근사해를 구할 수 있는 반 면 그 기본구조가 그리디기법(greedy algorithm) 을 근간으 로 하기 때문에 지역최적해에 빠질 위험성을 많이 내재하 고 있다. 최근 들어서는 지역담당문제에 범용의 휴리스틱기법을 도입한 다양한 연구들이 발표되었다. Jacobs and Brusco(1994) 는 SA 에 기반을 둔 해를 제안하였고, Beasley and Chu(1996) 는 GA 에 기반을 둔 방법을, 이현 남 외(1999) 는 SA와 GA 두 방법을 결합한 알고리즘을 제 안한 바 있다. 이러한 연구들은 메타휴리스틱 기법을 이용 하여 기존의 그리디기법에서 갖는 국부탐색의 단점을 극 복하고 전역 최적해를 유도해냄으로써 이들 기법이 지역 담당문제에 대한 효율적인 해법절차가 될 수 있음을 제시 하였다. 그러나 연구에 적용된 배치문제 자체가 지역담당 모형에서 가장 단순한 형태의 전체담당문제 식 (1) 로 한정 되었고 부분담당문제 식(2) 나 수리모형 구조자체가 전혀 다른 신뢰도모형 식(3) 을 적용하여 그 효율성을 검토해본 사례는 매우 드물다. 신뢰도모형이 개발된 이후 군사설비 배치문제들은 배치 상황을 보다 현실적으로 구현하기 위해 복잡한 구조의 대 규모 비선형문제로 확대되고 있다. 하지만 모형의 해법에 관한 연구들(Jacobs and Brusco, 1994: Beasley and Chu, 1996)은 신뢰도모형에 비해 현실성이 떨어지고 활용도가 낮은 전체담당모형을 기반으로 연구되었기 때문에 부분담 당모형이나 신뢰도모형을 포함한 전반적인 배치문제들에 적용 가능한 해법으로 단정하기 어렵고 이를 위해서는 모 형의 개발추세에 상응하도록 보다 일반화된 신뢰도모형으 로 그 연구범위를 확대시켜야 할 것이다. 3. 최적배치모형 설계와 해 유도과정 3.1 최적배치모형 설계 본 연구에서는 기존전력의 운용환경에서 패트리어트와 같이 설치방향에 따라 서비스영역이 변경되는 설치특성을 지닌 신규전력 추가 배치시 신구 전력이 함께 발휘하게 될 통합방공능력을 최대화할 수 있는 지역담당문제를 구 상하였다. 앞에 서술한 상황을 종합하여 배치모형을 구상하면, 각 장비별 운용규모가 확정된 상태에서 주어진 고객들에게 제공할 전체서비스를 최대화시키는 배치방안을 연구하기 위해 부분담당모형을 근간으로 하며 신구 전력이 함께 발휘하게 될 전체능력을 비교하고 각 고객들이 여러 설비 들로부터 동시에 서비스되는 중복효과를 판단할 수 있도 록 병렬구조의 신뢰도모형을 적용하여 수리모형을 설계하 였다. 고객담당여부는 적 공중위협 에 대해 중요시설 가 후보지에 방향으로 설치된 유형 장비로부터 보호받을 수 있는 확률 로 구분하였을 때, 중요시설 가 위 협으로부터 모든 장비들에게 보호받을 수 있는 확률은 식 (4) 와 같은 병렬구조의 신뢰도 수식으로 표현할 수 있다. = (4) - 1021 -
위의 식 (4) 에서 은 장비유형별로 가용한 입 지후보지를 의미하고 은 설치방향에 영향을 받는 장비의 각 입지후보지별 가용한 설치방향을 나타낸 다. 본 연구에서는 기반전력 및 신규전력의 운용규모가 확 정된 상태의 배치문제를 고려해야 하기 때문에 제약조건 은 유형별 전력의 가용량( ) 이 되고 추가적으로 방호목 표들에 대한 균형적인 서비스제공과 설비자체의 생존성 보장도 함께 고려해야 한다. 본 배치모형은 이러한 제약 조건을 만족시키면서 배치될 전력들이 서비스 대상이 되 는 적 공중위협들로부터 방호목표들에게 제공할 수 있는 전체적인 서비스규모를 산출해낼 수 있어야 하며 이를 종 합하면 식 (5) 와 같은 수리모형으로 표현할 수 있다. 이 모형은 유형별 배치수량( ) 과 부지별 설치허용량을 초과 하지 않으면서 적 공중위협() 으로부터 지역 내 중요시설 ( ) 들을 최대로 보호할 수 있는 설비배치를 판단할 수 있 다. 여기서 결정변수( ) 는 각 후보지별 장비배치여부로 장비유형과 설치방향이 함께 산출된다. (5) 배치모형 식 (5) 는 신구 전력이 동일한 임무를 수행한 다는 전제하에 기존의 호크전력 기반에서 설치방향에 영 향을 받는 패트리어트 신규전력을 추가배치하기 위해 개 발된 것이지만 모형 내에 설비유형을 구분하고 각각의 장 비특성과 배치여건을 반영할 수 있도록 보다 일반화된 구 조를 이루고 있기 때문에 모형의 활용에 있어 신규설비의 초도배치문제뿐만 아니라 다양한 상황변화에 따라 탄력적 인 운용이 가능하다. 실제로 호크전력은 평시 현진지에서 임무를 수행하지만 긴급상황시 이동전개가 가능하도록 수 개씩의 예비진지를 보유하고 있다. 그리고 새로 도입될 패 트리어트 역시 전개능력을 보유한 무기체계로 당연히 공 군구성군사령부 예하 전시 이동전력으로 운용될 것이기 때문에 극단적인 경우에는 호크 및 패트리어트 전력전체 를 전면 재배치시켜야하는 상황도 발생할 수 있다. 따라서 본 연구는 평시 신규전력에 대한 초도배치문제 뿐만 아니라 전시나 긴급사태 등의 긴박한 환경에서 신속 한 의사결정을 필요로 하는 극단적인 배치문제들에 오히 려 그 활용도가 높을 것으로 판단된다. 합최적화문제에서 현재해 를 선택하고, 의 이웃해 를 얻어 이동하는 과정을 반복함으로써 전체 해 공간을 탐색하며, 이 탐색결과 근사최적해를 얻을 수 있게 된다. 이웃해로의 이동은 현재해보다 목적함수를 개선시킬 수 있는 경우에 허용되는데, 이 과정을 반복하다보면 지역최 적해에 빠지는 결과를 가져올 수기 있기 때문에 온도 에 대한 에너지변화에 따른 확률 (metropolis criterion)에 의해 목적함수 개선이 없는 이 웃해로의 이동도 허용함으로써 SA가 지역최적해에 빠졌 을 경우, hill climbing 방법을 통해 이를 탈피할 수 있도 록 하여준다. SA는 기본개념이 단순하여 쉽게 사용이 가능하고 전역 최적해(global optimal solution) 로의 수렴성이 이론적으로 증명된바 있으며 많은 실험결과들에서도 그 타당성이 확 인되었다. 하지만 이러한 적용결과들에서 거의 일치된 결 론으로 SA는 충분한 계산시간이 주어진다면 최적해로 수 렴할 수 있는 반면 규모가 큰 문제에서는 전체 해 공간을 탐색하는데 많은 시간이 걸린다는 단점이 있다 Algorithm SA begin; INITIALIZE(X, T, L); repeat; for i=1 to L do Y=PERTURB(X); if (C(Y) C(X)) or (exp((c(x)-c(y))/t)>random(0,1)) then X=Y; {accept the movement} endif; end for; UPDATE(T, L); until (Stop-criterion) end 그림 1. SA 알고리즘. 본 연구에서는 수렴시간 단축을 위해 ASA를 적용하고 해의 변동공간을 비가능해(infeasible solution) 영역까지 포함할 수 있도록 해 유도과정< 그림 2> 를 구성하였다. ASA는 SA의 기본구조를 변화시키지 않으면서 내부루프 에서 마코프 체인의 평형성을 더욱 강화시켰기 때문에 SA의 장점과 이론적 조건은 그대로 유지하면서도 수렴속 도가 매우 빨라질 수 있다( 윤복식조계연 1996). 비가능 해를 포함한 해공간의 탐색은 이웃해의 선별이 보다 빠르 고 간단하게 이루어질 수 있고 해가 국부최소점에서 빠져 나올 수 있는 가능성도 높여준다 3.2 Simulated Annealing 알고리즘을 이용한 해 유도과정 신뢰도모형이 개발된 이후 최근 군사설비 배치에 대한 연구는 대부분 병렬신뢰도구조를 적용하고 있기 때문에 단순한 조합최적화문제가 아닌 복잡한 구조의 비선형문제 로 변형되었고 모형 내에 설비유형을 구분하여 여러 설비 들을 동시에 구성한다면 문제의 규모 역시 설비종류에 비 례하여 증가하게 되고 또한 이 문제는 조합문제에서 순열 문제로 전환하게 된다. 일반적으로 사용되고 있는 SA알고리즘의 기본형태는 < 그림 1> 과 같고 목적함수를 최소화( 또는 최대화) 하는 조 - 1022 -
Algorithm ASA INITIALIZE(X, T, L); X_best=X;, Counter1=0;, Counter2=0; repeat; Costold=C(X);, Check=0; for i=1 to L do Y=PERTURB(X); if (C(Y) C(X)) or (exp((c(x)-c(y))/t)>random(0,1)) then X=Y; {accept the movement} if (C(X) C(X_best)) then X_best=X;, Counter2=0;, Check=1;, L=L+L; else Counter2=Counter2+1; end for; Costnew=C(X); UPDATE(T, Costnew, Costold, Check); if (Costnew=Costold) then Counter1=Counter1+1; else Counter1=0; until (Counter1>M or Counter2>N); UPDATE(T, Costnew, Costold, Check) if(check=1 or Costnew<Costold) then T=a T; C(X): C(X)+C Penalty; // C: the # of infeasible components 그림 2. ASA 를 이용한 해 유도과정. < 그림 2> 의 해 유도과정은 SA의 기본특성을 그대로 유지하면서 수렴속도를 개선시키기 위해 다음과 같은 사 항들을 보완하였다. (1) 초기 컨트롤 파라미터() 설정시 해를 받아들이는 비 율을 이용하여 결정함으로써 과도하게 높은 온도로 설정하는 것을 피하였다. 초기온도를 목적함수 값에 근거하여 적당히 낮은 수치로 지정하지 않는다면 지 나치게 많은 시간동안 hill climbing을 허용하게 되어 자칫 임의탐색과정으로 전락할 수 있다. (2) 내부루프() 를 최소값으로 지정하고 필요한 때만 수 행횟수를 늘려주는 방식을 취하였고 대신에 내부루프 동안 목적함수 값이 떨어지지 않는 경우 그 에서 안 정상태에 도달하지 못한 것으로 간주하여 일정한도의 내부루프를 증가시켜 주는 방식을 적용함으로써 불필 요한 내부루프들을 생략할 수 있다. (3) 냉각스케쥴은 기하형태를 적용하였고 현재까지의 가장 좋은 해를 계속 기억해 나가면서 그 값을 개선시킨 에서는 내부루프를 한번 더 돌리는 방식을 수용함 으로써 좋은 해를 찾을 가능성을 보다 높일 수 있다. (4) 종료조건은 정해진 외부루프동안 목적함수의 변화가 없거나 내부루프 안에서 최소점을 갱신하는 간격을 이용하여 두 조건중 하나가 먼저 만족되면 알고리즘 을 종료시킴으로써 해의 개선없는 낮은 에서 헛되 이 보내는 시간을 줄일 수 있다. 식 (6) 은 본 연구의 배치모형을 이용하여 호크와 패트리 어트의 배치상황을 구성한 예로 가용한 설치후보지에 각 장비들을 주어진 수량만큼 배치하고 추가적으로 패트리어 트는 후보지별 설치방향도 함께 판단해야 한다. 이웃해 생 성과정을 수리모형내 제약식의 구성요소와 연계하여 살펴 보면 일련의 이웃해들은 각 설비별 제한수량을 만족해야 하고 아울러 각 부지별 제약조건도 만족하면서 목적함수 를 개선시켜 나가야 한다. 호크 (6) 패트리어트 각 후보지 위의 예에서 알 수 있듯이 지역담당문제는 문제의 규모 가 커질수록 해공간도 확장되고 모형이 세밀하고 구체적 으로 구현될수록 제약조건 또한 증가하게 되어 보다 복잡 한 해의 구조를 형성하게 된다. 본 연구에서는 이웃해 생성을 비가능해 영역까지 확대 시켜주었기 때문에 전체 해공간이 매우 넓다. 그리고 배치 규모가 큰 문제에서는 그 규모에 비례하여 해공간도 확장 되므로 이웃해 생성과정이 최적해와는 거리가 먼 영역에 서 지나치게 많은 시간을 낭비하게 된다. 본 연구에서는 효율적인 이웃해 선별과정을 위해 비가 능해를 포함한 전 영역에서 이웃해를 생성하고 이 해가 최적해 영역으로 자연스럽게 전이될 수 있도록 새로운 절 차를 구상하였으며 이 절차를 ' 효과도에 의한 이웃해 선 별과정' 이라 명하고 이후부터는 약어로 ' 효과도선별' 이라 표기한다. 효과도선별이란 SA알고리즘을 지역담당문제에 효과적 으로 적용시키기 위해 고안한 방법으로 일련의 이웃해들 이 최적해 가능영역에서만 생성될 수 있도록 SA의 함수에 Yoshiaki(1975) 휴리스틱기법을 결합 하였고 이러한 일련의 전이과정들이 보다 신속하게 이루 어지도록 Dijkstra 알고리즘의 표지(label) 법을 이용하여 보완하였으며 먼저 함수에 의해 현재해 로 부터 이웃해 를 생성하고 함수를 통해 를 가능해 영역으로 전이시키며 전이된 해의 구성요소를 분 석하여 해에 추가 가능한 요소들을 표지(label) 하고 이 표 지된 요소들에 대해 현재의 목적함수 개선여부와 제약식 위반여부에 대조하여 의 구성요소에 포함시킨다. 4. 실험수행 및 결과분석 실험은 크게 축소실험과 확대실험으로 구분할 수 있다. 먼저 축소실험에서는 가상의 SAM-X 전력 배치상황을 설 정하고 본 연구의 수리모형과 해법을 적용하여 최적배치 방안을 유도함으로써 모형과 해법의 운용개념을 이해하고 연구의 활용방안을 제시하였다. 확대실험에서는 새 해법인 효과도선별이 대규모 설비배치문제에 대하여 폭넓게 활용 이 가능한 일반적인 해법절차가 될 수 있음을 증명하기 위해 현실적인 규모로 문제를 확대하고 기존해법들과의 비교실험을 통해 새 해법의 효율성 및 개선가능성을 판단 하였다. 4.1 축소실험 축소실험에서의 배치상황은 다음과 같다. (1) 주어진 지역내에 유도탄 전력이 보호해야 할 방호목표 ( 고객) 는 총 10 개소가 있다. (2) 유도탄 전력이 주어진 방호목표( 고객) 를 방어( 서비스) 해야 할 공중위협( 서비스 대상) 은 5 개가 된다. (3) 배치할 전력은 2개 유형으로 구분되고 배치규모는 호 - 1023 -
크 4 개 포대( 설비Ⅰ) 와 패트리어트 4 개 포대( 설비Ⅱ) 가 있다. (4) 유도탄 전력을 배치할 수 있는 후보지는 10개소이고 각 후보지별로 4 개씩 설치방위각이 가용하다. (5) 각 고객별, 위협별, 설비별, 후보지별, 방위각별 여건과 중요도는 모두 동일한 것으로 가정한다. (6) 이 배치문제에 있어 평가척도는 배치할 유도탄( 설비) 들이 적 공중위협( 서비스대상) 으로부터 주어진 방어목 표( 고객) 들을 전체적으로 얼마나 많이 보호( 서비스) 할 수 있느냐가 될 것이다. 이상의 배치상황을 종합한다면 다음과 같은 배치문제식 (7) 과 같이 구성할 수 있다. 호크 (7) 패트리어트 각 후보지 이 문제에서 고객담당확률( ) 은 중요시설(10 개), 적 공중위협(5 개), 설비유형(2 개 유형), 가용후보지(10 개) 와 각 후보지별 설치방향(4 개 방향) 을 고려한다면 10x5x10x2x4의 5차원배열로 구성되고 호크는 전 방향으 로 사격이 가능한 장비로 설치방향에 영향을 받지 않기 때문에 10 5 10 5처럼 4차원으로 변경이 가능하여 총 2,500개의 수치가 필요하고 실험의 객관성을 기하기 위해 균일(uniform) 분포에 의한 난수를 생성하여 구하였다. 4.2 확대실험 및 결과분석 본 절에서는 SA기법을 응용한 효과도선별기법이 단순 한 전체담당문제뿐만 아니라 신뢰도모형을 적용한 대규모 의 배치문제에 대해서도 우수한 해법이 될 수 있음을 입 증하기 위하여 본 연구에서 개발한 지역담당모형식 (5) 를 이용하여 현실적인 규모의 배치문제를 구성하고 이에 대 한 반복실험을 실시하여 기존 해법에 의한 결과들과 비교 분석하였다. 각 실험은 < 표 1> 과 같이 구성하였고 객관적인 비교분 석이 될 수 있도록 동일한 문제를 같은 조건에서 10번씩 수행하였으며 같은 방식으로 문제의 규모를 확대하였다. 표 1. 확대실험 구성 구분 문제 유형 ( ) 가용 설비수 설치방향 영향 실험 1 20 10 20 2 4 설비Ⅰ: 10, 설비Ⅱ: 8 설비Ⅱ 실험 2 20 10 25 2 4 설비Ⅰ : 15, 설비Ⅱ : 10 설비Ⅱ 실험 3 20 10 25 3 4 설비Ⅰ: 10, 설비Ⅱ : 7, 설비Ⅲ 설비 Ⅲ: 8 : 고객, : 공중위협, : 설치후보지 : 설비유형, : 후보지별 가용방위각 각 문제별로 초기온도, 냉각스케쥴, 내부루프에 따라 그 결과가 다양하게 바뀌었다. 본 실험에서는 일괄적으로 기 하형태의 냉각 스케쥴을 적용하였고 와 값은 문제의 규모별로 모의실험을 실시하여 가장 좋은 값을 추출하였 으며 초기온도() 는 모의실험결과에서 얻은 목적함수 값 에 근거하여 SA의 수렴성능이 보장될 수 있도록 적당한 수치를 지정해주었다. < 표 2> 는 각 실험에서 지정한 파라 미터들의 초기치와 사용한 난수들의 생성범위를 종합한 자료이다. 표 2. 파라미터 초기치 현황 실험 1 실험 2 실험 3 구 분 ( 회) ( ) SA 200 100 ASA 50 100 효과도선별 50 100 SA 200 100 ASA 50 100 효과도선별 50 50 SA 200 100 ASA 50 50 효과도선별 50 10 난 수 생성범위 0.95 0.1~1.0 0.95 0.2~1.0 0.95 0.3~1.0 < 표 3> 은 각 알고리즘별 최적해 비교를 위해 실험결과 들 중 가장 좋은 측정치를 기록한 것으로 효과도선별기법 이 전반적으로 가장 우수한 최적해를 계산해내었다. SA와 ASA는 문제의 규모가 커짐에 따라 최적해의 질이 떨어지 는 양상을 보였고 일부 실험에서는 주어진 시간동안 그리 디의 계산결과에도 도달하지 못하였다. 표 3. 최적해 비교 구분 SA 알고리즘 그리디 ASA+ 기법 SA ASA 효과도선별 실험 1 0.0019 0.0017 0.0011 0.0009 실험 2 0.00041 0.00027 0.0002 0.00015 실험 3 0.00236 0.00178 0.0016 18 배 확대실험 2와 3은 확대실험 1에 비해 약 10 16 ~10 정도 해공간이 더 넓어진 문제로 특히 실험3은 설비유형 이 하나 더 증가하였기 때문에 해의 구조가 훨씬 더 복잡 하다. < 표 4> 는 각 알고리즘별 수렴성능을 평가하기 위해 확대실험결과를 종합한 자료로 계산시간 비교에 추가하여 수렴성능의 효율성을 추가로 측정하였다. 이는 제한된 시 간 내에 주어진 해를 구하지 못한 경우 가중치를 부여하 기 위함이고 낮은 값일수록 좋은 결과가 되며 동일규모의 실험에서 각 알고리즘에 대한 비교척도로 한정되며 규모 가 다른 실험 간에 상호연관성은 없다. 표 4. 수렴성능 비교 (10 회 평균) 시간단위: 초 ASA+ SA ASA 효과도선별 구분 소요 수렴 소요 수렴 소요 수렴 시간 성능 시간 성능 시간 성능 실험 1 3,549 11.02 3,007 4.02 96 0.11 실험 2 3,565 1.606 3,362 0.866 155 0.028 실험 3 3,611 11.85 3,531 6.81 632 1.07 확대실험에서는 본 연구에서 제시한 해유도과정의 효율 성을 입증하기 위해 다양한 형태로 문제를 구분하여 반복 실험을 수행하였고 실험결과 < 표 3> 과 < 표 4> 에서 나타 났듯이 효과도선별기법이 최적해의 질과 수렴성능에 있어 가장 우수한 결과를 얻을 수 있었다. 본 절에서는 보다 객 관적인 비교분석을 위해 이들 결과에 대한 각각의 향상도 를 측정하였다. - 1024 -
새 해법들의 향상도를 측정한 결과 효과도선별기법이 모든 문제에 걸쳐 그리디기법보다 좋은 해를 구할 수 있 었고 최적해의 개선 정도도 가장 크게 나타났다. 5. 결 론 본 연구에서는 신규전력 배치시 기반전력과 연계하여 신구 전력이 발휘하게 될 전체능력을 통합적으로 평가 하여 설비배치를 결정할 수 있는 최적배치모형을 개발하 였고 이 모형과 같은 대규모 군사설비 배치문제를 효과적 으로 계산해내기 위해 SA를 응용한 새로운 해 유도과정 을 구성하였으며 이 연구를 이용하여 현재 한국공군에서 추진중인 SAM-X사업의 배치문제에 적용함으로써 새로 도입할 패트리어트 전력배치를 체계적으로 판단할 수 있 는 방법론을 제시하였다. 또한 추가적으로 지역담당 모형 의 개발과 효율적인 해법의 적용으로 양분화 되어있는 기 존 연구분야를 통합하여 연구분석함으로써 SA와 같은 범 용의 메타휴리스틱 기법이 신뢰도모형을 포함한 대규모 설비배치문제에 대한 일반적인 해법이 될 수 있음을 입증 하였다. 참고문헌 [1] 김성인(1987), 군사설비의 최적위치 결정을 위 한 지역담당(Set Covering) 모델 및 해법의 개발, 화랑대 심포지움 논문집. [2] 김여근, 윤복식, 이상복(2000), 메타휴리스틱, 영 지문화사. [3] 오제상(1981), 신뢰도를 최대화하는 지역담당 (Set Covering) 모델, 고려대학교 석사학위논문. [4] 윤복식, 조계연(1996), Simulated Annealing의 가 속화와 ATM 망에서의 가상경로 설정에의 적 용, 한 국경영과학회지, 21(2), 125-140. [5] 이현남, 한치근(1999), Set Covering 문제의 해 법 을 위한 개선된 Simulated Annealing 알고리 즘, 산 업공학, 12(1),.94-101. [6] Beasley, J. E. and Chu, P. C. (1996), Genetic Algorithm for the Set Covering Problem, European Journal of Operational Research, 94, 392-404. [7] Bellmore, M. and Ratliff, H.D.(1971), Set Covering and Involute Bases, Management Science, 18(3), 194-206. [8] Francis, R. L. and White, J. A(1974)., Facility Layout and Location, Prentice-Hall Inc., New Jersey. [9] Garfinkel, R.S., and Nemhauser, G.L. (1969), The Partitioning Problem: Set Covering with Equality Constraints, Operations Research, 17(5), 840-856. [10] George C. Moors and Charles Revelle(1982), The Hierarchical Service Location Problem, Management Science, 28(7), 775-780. [11] Jacobs, L. W. and Brusco, M. J.(1994), A Simulated Annealing-Based Heuristic for the Set Covering Problem, Preceding Decision Sciences Institute, 1994 Annual meeting, 12, 1189-1191. [12] Yoshiaki Toyoda(1975), A Simplified Algorithm for Obtaining Approximate Solutions to 0-1 Programming Problems, Management Science, 21(12), 1417-1427. - 1025 -