Journal Search Engine

ISSN : 2005-0461(Print)
ISSN : 2287-7975(Online)

Journal of Society of Korea Industrial and Systems Engineering Vol.39 No.2 pp.88-102
DOI : https://doi.org/10.11627/jkise.2016.39.2.088

An Efficient Genetic Algorithm for the Allocation and Engagement Scheduling of Interceptor Missiles

Dae Ryeock Lee^*

, Jaehwan Yang^**†

^*Department of Business Administration, University of Seoul/ Korea Institute of Marine Science and Technology Promotion
^**Department of Business Administration, University of Seoul

Corresponding Author : jyang@uos.ac.kr

Received March 30, 2016 Finally Revised June 7, 2016 Accepted June 9, 2016

Abstract

This paper considers the allocation and engagement scheduling problem of interceptor missiles, and the problem was formulated by using MIP (mixed integer programming) in the previous research. The objective of the model is the maximization of total intercept altitude instead of the more conventional objective such as the minimization of surviving target value. The concept of the time window was used to model the engagement situation and a continuous time is assumed for flying times of the both missiles. The MIP formulation of the problem is very complex due to the complexity of the real problem itself. Hence, the finding of an efficient optimal solution procedure seems to be difficult. In this paper, an efficient genetic algorithm is developed by improving a general genetic algorithm. The improvement is achieved by carefully analyzing the structure of the formulation. Specifically, the new algorithm includes an enhanced repair process and a crossover operation which utilizes the idea of the PSO (particle swarm optimization). Then, the algorithm is throughly tested on 50 randomly generated engagement scenarios, and its performance is compared with that of a commercial package and a more general genetic algorithm, respectively. The results indicate that the new algorithm consistently performs better than a general genetic algorithm. Also, the new algorithm generates much better results than those by the commercial package on several test cases when the execution time of the commercial package is limited to 8,000 seconds, which is about two hours and 13 minutes. Moreover, it obtains a solution within 0.13~33.34 seconds depending on the size of scenarios.

Key Words : Genetic Algorithm , Weapon Target Allocation Problem , Mixed Integer Programming , Optimization , Interceptor Missile

효율적인 유전 알고리즘을 활용한 요격미사일 할당 및 교전 일정계획의 최적화

이 대력^*, 양 재환^**†

^*서울시립대학교 경영학과/한국해양과학기술진흥원
^**서울시립대학교 경영학부

초록

키워드 :

This article has been cited by 0 article in crossref

Cited-By

Funding:

University of Seoul

1서 론

우리나라에서 구축 중인 한국형 미사일 방어체계(KAMD, Korea Air and Missile Defense)는 조기경보체계, 지휘통 제체계, 요격체계로 구성되는데, 이 중에서 지휘통제체계 역할을 수행하는 곳을 작전통제소라고 한다[24]. 작전통 제소는 각종 탐지장치로부터 탐지된 적 탄도미사일의 정 보를 수집 및 분석하고, 전국에 배치되어 있는 요격포대 의 위치와 상태를 파악해서 어느 포대에서 몇 발의 요격 미사일을 발사할 것인지 요격명령을 내리게 된다. 이때 탐지된 탄도미사일이 단․중거리 탄도미사일이라면 짧은 비행시간으로 인해 탐지부터 요격의 결정을 수십 초 또는 수 분 내에 하여야 한다[13, 16].

이러한 작전통제소의 임무는 오래 전부터 연구되어 온 WTA(Weapon Target Assignment) 문제 중 미사일 할 당 문제와 같으며, 그 중에서도 요격 가능 시간이 제한되 는 시간 윈도우(window) 개념을 적용한 동적(dynamic) WTA 문제로 볼 수 있다.

시간 윈도우 개념을 적용한 동적 WTA 연구로는 Khosla [15], Karasakal[14], Gülez[8], Lee[20], Jang et al.[11], Lee and Yang[18] 등이 있는데, 그 중에서 작전통제소의 임 무와 같이 적 탄도미사일을 방어하기 위해 요격미사일을 할당하는 연구로는 Jang et al.[11]과 Lee and Yang[18]이 있다. 하지만 Jang et al.[11]과 Lee and Yang[18]은 미사 일 할당을 위한 수학적 모형만을 제시하여 신속하게 최 적해에 접근할 수 있는 효율적인 알고리즘에 대한 연구 가 추가적으로 필요하다.

이에 본 연구에서는 탄도미사일 방어 임무에 적용하 기 위해 많은 제약조건이 반영된 Lee and Yang[18]의 미 사일 할당 모형을 대상으로 하여 최적해 또는 이에 근접 한 우수한 해를 신속하게 찾을 수 있는 휴리스틱 알고리 즘을 개발하고자 한다. 그리고 본 연구의 결과는 현실적 으로는 작전통제소의 효과적인 임무 수행을 지원하는 방 안을 제시하고, 이론적으로는 시간 윈도우 개념을 적용 한 동적 WTA 연구의 확장에 기여할 것으로 판단된다.

2선행 연구 분석

WTA 문제에 대한 알고리즘 개발 연구는 주로 유전 알고리즘, 개미 집단 최적화(ACO : Ant Colony Optimization) 알고리즘, 개체 군집 최적화(PSO : Particle Swarm Optimization) 알고리즘 등과 같은 메타 휴리스틱 알고리 즘을 문제의 특성에 맞게 개선하거나 문제 특성에 최적 화된 새로운 휴리스틱 알고리즘을 개발한다.

유전 알고리즘을 적용한 연구로는 Khosla[15], Chen et al. [4], Julstrom[12], Song et al.[27], Hong et al.[9], You[32], Woo[29] 등이 있다. Khosla[15]는 유전 알고리즘과 모의 담금질(simulated annealing) 형태의 휴리스틱 기법이 적 용된 혼합형 유전 알고리즘을 연구하였고, 모의 담금질 형태의 휴리스틱 기법은 유전 알고리즘의 적합도 평가 과정에 포함되어 찾아낸 해가 제약조건을 만족하도록 조 정하는 역할을 수행한다. Chen et al.[4]은 동적 WTA 문제 에 유전 알고리즘과 지역 최적화 알고리즘인 2-opt 알고리 즘이 적용된 혼합형 유전 알고리즘을 연구하였고, Julstrom [12], Song et al.[27], Hong et al.[9], You[32]는 정적(static) WTA 문제에 MMR(Maximum Marginal Return)과 같은 탐욕(greedy) 알고리즘으로 최적해와 가까운 해를 찾아서 유전 알고리즘의 초기 해집단에 포함시키는 GA-S(Genetic Algorithm-Seed) 기법을 적용하여 보다 신속하게 최적해 를 찾을 수 있도록 하였다. Liu et al.[22]은 동적 WTA 문제에 대해 모의 담금질을 지역 최적화 알고리즘으로 적용한 혼합형 유전 알고리즘을 연구하였다.

ACO 알고리즘을 적용한 연구로는 Lee et al.[21], Fu et al.[6], Zhang et al.[33] 등이 있다. Lee et al.[21]은 동적 WTA 문제에 대해서 ACO 알고리즘이 찾아낸 해를 더욱 향상시키기 위해 지역 최적화 알고리즘으로 면역 알고리 즘(immune system algorithm)을 추가한 혼합형 알고리즘 을 연구하였다. Fu et al.[6]은 정적 WTA 문제에 대해 유 전 알고리즘으로 찾아낸 해로 페로몬을 초기화하고, ACO 알고리즘으로 최적해를 찾는 순서로 2개의 메타 휴리스 틱 알고리즘이 연속으로 사용되는 알고리즘을 연구하였다. Zhang et al.[33]도 정적 WTA 문제에 대해서 특정 시점 이후 비효율적인 반복 계산을 많이 하는 유전 알고리즘의 단점과 지역 최적해로 수렴하는 ACO 알고리즘의 단점을 보완하기 위해 유전 알고리즘으로 페로몬을 초기화하고, ACO 알고리즘으로 찾아낸 해에 대해 교차 연산과 변이 연산을 실시하는 알고리즘을 연구하였다.

PSO 알고리즘을 적용한 연구로는 Teng et al.[28], Chen et al.[4], Zhu et al.[34], Liu et al.[23], Geetha et al.[7] 등 이 있다. Teng et al.[28]은 공대공 요격미사일 할당문제 에 대해서 지역 최적해로 수렴하는 것을 방지하고, 탐색 속도를 향상시키기 위해 특정 조건에서 개체의 관성 가 중치(inertia weight)와 속도 및 위치 업데이트 방법을 수 정하는 PSO 알고리즘을 연구하였다. Chen et al.[3]은 정 적인 센서-무장-표적 할당문제에 대해 지역 최적해로 수 렴하는 것을 방지하고, 탐색 속도를 향상시키기 위해 각 개체의 속도와 위치를 업데이트하는 과정에서 유전 알고 리즘의 교차 및 돌연변이 연산을 PSO 알고리즘에 적용 하였으며, 새로운 업데이트 방법에 따라 다음 세대에서 각 개체의 위치는 현 시점에서의 개체가 Global best 개체 (현재까지 가장 좋은 해를 가진 개체), Personal best 개체 (해당 개체가 현재까지 가장 좋은 해를 가졌을 때), 돌연 변이를 통해 임의로 만들어진 개체와 교차 연산을 하여 결정된다. Zhu et al.[34]은 공대공 요격미사일 할당문제 에 대해서 탐색 속도 향상을 위해 한 세대가 지날 때마 다 관성 가중치의 크기가 줄어들고, 지역 최적해에 빠지지 않도록 유전 알고리즘의 돌연변이 연산을 적용한 PSO 알고리즘을 연구하였다. Liu et al.[23]은 공대공 요격미 사일 할당문제에 대해서 유전 알고리즘과 PSO 알고리즘이 혼합된 Chen et al.[4]의 알고리즘을 적용하였다. Geetha et al.[7]은 차량경로문제(VRPㆍVehicle Routing Problem)에 대해 더 좋은 탐색 능력을 위해 PSO 알고리즘과 유전 알고리즘을 순차적으로 실행하는 알고리즘을 연구하였다.

새로운 휴리스틱 알고리즘은 대개 문제의 특성을 고려 하여 탐욕 알고리즘 방법으로 해를 찾아내는 구성적 휴리 스틱(construction heuristic)과 찾아낸 해를 더 좋은 해로 바꾸기 위한 향상적 휴리스틱(improvement heuristic)으로 구성되는데, 이런 연구로는 Karasakal[14], Ahuja et al.[2], Lee[22] 등이 있다. Karasakal[14]은 함정의 대공 방어 모형 의 최적해를 찾기 위해 구성적 휴리스틱으로 BEC(Best Engagement Construction) 알고리즘과 QUC(Quasi-Uniform Construction) 알고리즘을 개발하고, 향상적 휴리스틱으로 OC(Opt-Change) 알고리즘과 2OX(2-Opt Exchange) 알고 리즘을 연구하였다. Ahuja et al.[2]은 정적 WTA 문제를 최소비용흐름 문제 형태로 접근하여 구성적 휴리스틱으 로 초기 해를 찾아내고, 이웃해 탐색(neighborhood search) 기법으로 향상된 해를 찾아내는 VLSN(Very Large-Scale Neighborhood search) 알고리즘을 연구하였다. Lee[22]는 Ahuja et al.[2]의 연구모형에 표적당 할당되는 요격미사 일 수의 상한값과 하한값을 제약조건으로 추가하고, 해당 제약조건이 고려된 VLSN 알고리즘을 연구하였다.

Xin et al.[31]은 동적 WTA 문제에 대해서 VQP값(표적 의 위협 수준과 각 시간 단계에서 무장이 표적을 파괴할 확률의 곱)을 기준으로 한 구성적 휴리스틱 기법을 적용하 고, MCM(Monte Carlo Method) 방법과 비교하여 제안한 알고리즘의 우수함을 보였다. Xin et al.[30]은 Xin et al. [31]과 같은 동적 WTA 문제에 대해서 최적해를 찾기 위해 탐색점 분포 학습 알고리즘(EDA : Estimation of Distribution Algorithm)을 적용하였으며, 모형의 제약조건을 만족 시키는 방법으로 CRI(Constructive Repair/Improvement) 연산 자를 추가하였다. 그리고 CRI 연산자의 성능을 평가하기 위해 벌칙 함수(penalty function)를 적용한 EDA 알고리즘 과 CRI 연산자를 포함한 EDA 알고리즘을 비교하였는데, 벌칙 함수를 적용한 EDA 알고리즘은 몇몇 실험 문제에서 실행 가능한 최적해를 찾아내지 못하였고, 실행 불가능한 해에 대해서 많은 시간을 소비한다고 하였다. 그에 비해 CRI 연산자를 포함한 EDA 알고리즘은 실행 가능한 해만을 생산한다고 하였다. 이 외에도 동적 WTA 문제에 대해서 Hosein[10], Murphey[26], Krokhmal et al.[17], Ahner et al.[1] 등은 동적계획법(dynamic programming) 형태로 모형 을 구성하고, MMR과 같은 탐욕 알고리즘을 적용하였다.

WTA 모형과 휴리스틱 알고리즘이 실제 작전 현장에 적용되기 위해서는 무장의 성능 및 운영 환경, 표적과의 교전 상황 등으로부터 발생될 수 있는 많은 제약조건들이 반드시 고려되어야 하지만 앞에서 언급된 대부분의 연구 는 <Table 1>에서 보는 것과 같이 제약조건의 수가 적은 단순화된 모형을 중심으로 휴리스틱 알고리즘을 개발하였 고, 반면 많은 제약조건을 가진 Jang et al.[11]과 Lee and Yang[18]의 연구는 해를 신속하게 찾기 위한 알고리즘을 제시하지 않아 많은 제약조건을 가진 모형에 대한 휴리스 틱 알고리즘 개발 연구는 부족하다고 할 수 있다. 또한, Xin et al.[30]의 연구 결과를 고려하면 제약조건이 많은 문제일수록 실행가능한 해를 구하고, 실행 시간을 단축하 는 것이 더욱 어려워져 많은 제약조건을 가진 모형에 대해 신속하게 해를 찾을 수 있는 휴리스틱 알고리즘 개발 연구 는 중요하다. 특히, 탄도미사일 방어와 같이 시간 윈도우 개념이 모형에 적용되면 시간변수가 무장과 표적의 조합 을 결정하는 변수에 영향을 줄 수 있고, 탄도미사일과 요 격미사일의 제한된 교전 시간에 의해 실시간에 가까운 실 행 시간이 요구되어 문제는 더욱 어려워진다.

본 연구에서는 시간 윈도우 개념을 적용한 연구 중에 서 현실성 강화를 위해 9개의 제약조건을 포함한 Lee and Yang[18]의 모형을 대상으로 최적해를 신속하게 찾기 위한 휴리스틱 알고리즘을 개발하고, 알고리즘 내에 9개의 제 약조건을 만족시키기 위한 방법을 함께 제시하고자 한다.

3미사일 할당 모형

본 장에서는 개발하는 휴리스틱 알고리즘에 대한 이 해를 돕기 위해 제 2장에서 언급한 것과 같이 탄도미사 일 공격에 대해 요격미사일의 할당과 교전 일정계획을 모형화한 Lee and Yang[18]의 모형에 대해 설명한다. 이 모형은 본 연구에서 새롭게 개발된 것이 아니고 선행연 구인 Lee and Yang[18]의 모형을 제시한 것이다.

3.1모형의 가정

모형에 대한 주요 가정사항은 다음과 같다.

1) 최초 탐지 후, 추가로 탐지 및 확인되는 탄도미사일 은 고려하지 않는다.
2) 작전통제소는 두 종류의 무장을 이용한 협동교전을 실시할 수 있다.
3) 작전통제소는 교전 상황에 따라 적합한 사격 전술 을 결정한다.
4) 단거리 요격시스템(M-SAM)은 하나의 특정 시설만 을 장거리 요격시스템(L-SAM)은 사거리 내의 지역 을 방어한다.
5) L-SAM과 M-SAM은 각각 상층과 하층 방어를 담 당하여 다층 방어를 구성한다.
6) 탄도미사일을 탐지한 시간을 교전의 시작 시간(0초) 으로 한다.

3.2기호 및 변수 정의

모형에 사용된 기호 및 변수는 다음과 같다.

인덱스

i :

발사대, i = 1, 2, ⋯, I

k :

탄도미사일, k = 1, 2, ⋯, K

J_i :

발사대 i가 보유한 요격미사일의 수

j :

발사대의 j번째 요격미사일, j = 1, 2, ⋯, J_i

b :

포대, b = 1, 2, ⋯, B (포대는 발사대로 구성)

I_b :

b포대에 속한 발사대의 집합

p :

반응시간부터 마지막 탄도미사일의 탄착까지 일 정 간격의 시간(초)

데이터 및 교전 상황에 따라 계산 가능한 값

VI_i :

발사대 i의 요격미사일 속도

D_k :

탄도미사일 k에 할당되어야 하는 요격미사일의 수

FFT_ik :

발사대 i의 요격미사일이 탄도미사일 k를 요격 하기 위해 발사 가능한 최초 시간

LFT_ik :

발사대 i의 요격미사일이 탄도미사일 k를 요격 하기 위해 발사 가능한 최후 시간

MFT_ik :

발사대 i의 요격미사일이 탄도미사일 k를 요격 하기 위한 발사 가능 시간의 중간지점

FFZ_ik :

발사대 i의 요격미사일과 탄도미사일 k의 최 초 교전점 고도

RF_k :

탄도미사일 k의 낙하율

W_k :

방어자산까지의 탄착 시간이 가장 짧은 탄도 미사일을 우선 요격하기 위한 탄도미사일별 가 중치

FT_ijk :

발사대 i에서 발사되는 j번째 요격미사일이 탄 도미사일 k의 요격 지점까지 도달하는데 걸리 는 비행시간

U_i :

발사버튼을 누르고 나서 요격미사일이 실제 발 사될 때까지 지연된 시간

LT :

교전결과 확인에 소요되는 시간

RT_i :

발사대 i의 반응 시간

FFTR_ik :

발사대 i에서 탄도미사일 k에 대한 최초 교전 점까지 거리

MFTR_ik :

발사대 i에서 탄도미사일 k에 대한 중간 교전 점까지 거리

SFT_i :

발사대 i가 요격미사일을 연속 발사할 경우 최 소 시간 간격

α_ik :

발사대 i와 탄도미사일 k의 최초 교전점과 중 간 교전점 사이에서 요격미사일의 비행거리가 줄어드는 정도

β_ik :

발사대 i와 탄도미사일 k의 중간 교전점과 최 후 교전점 사이에서 요격미사일의 비행거리가 줄어드는 정도

SE_b :

b포대의 레이더가 동시에 유도할 수 있는 요격 미사일의 수

M :

큰 수

결정변수

X_ijk :

발사대 i에서 발사되는 j번째 요격미사일이 탄 도미사일 k에 할당되면 “1” 그렇지 않으면 “0” 의 값을 가지는 이진변수

T_ij :

발사대 i의 j번째 요격미사일 발사 시간

q_ij :

α_ik가 선택되면 “1” 그렇지 않으면 “0”의 값을 가지는 이진변수

r_ij :

β_ik가 선택되면 “1” 그렇지 않으면 “0”의 값을 가지는 이진변수

G_ijp :

발사대 i의 j번째 요격미사일이 p초에 비행중 이면 “1” 그렇지 않으면 “0”의 값을 가지는 이 진변수

3.3목적함수 및 제약조건

모형의 목적함수와 제약조건은 다음과 같으며, 모형에 대한 보다 자세한 설명은 Lee and Yang[18]을 참고하면 된다.

목적함수

M a x \sum_{k = 1}^{K} \sum_{i = 1}^{I} \sum_{j = 1}^{J_{i}} {F F Z_{i k} - (T_{i j} - F F T_{i k}) R F_{k}} W_{k} \cdot X_{i j k}

(1)

제약조건

\begin{array}{l} \sum_{k = 1}^{K} X_{i j k} \leq 1 & \forall i, j \end{array}

(2)

\begin{array}{l} \sum_{k = 1}^{K} X_{i j k} \geq \sum_{k = 1}^{K} X_{i, j + 1, k} & \forall i, j = 1, 2, \dots, J_{i - 1} \end{array}

(3)

\begin{array}{l} T_{i j} + S F T_{i} \leq M (1 - \sum_{k = 1}^{K} X_{i, j + 1, k}) + T_{i, j + 1} \\ \forall 1, 2, \dots, J_{i} - 1 \end{array}

(4)

\begin{array}{l} \sum_{i = 1}^{I} \sum_{j = 1}^{J_{i}} X_{i j k} \leq D_{k} & \forall k \end{array}

(5)

\begin{array}{l} \sum_{i \in L S A M} \sum_{j = 1}^{J_{i}} X_{i j k} \leq \sum_{i \in M S A M} \sum_{j = 1}^{J_{i}} X_{i j k} & \forall k \end{array}

(6)

\begin{array}{l} \sum_{k = 1}^{K} X_{i j k} \cdot F F T_{i k} \leq T_{i j} \leq \sum_{k = 1}^{K} X_{i j k} \cdot L F T_{i k} & \forall i, j \end{array}

(7)

\begin{array}{l} X_{m n k} \cdot T_{m n} + M (1 - X_{m n k}) \\ \geq X_{i j k} (T_{i j} + U_{i} + F T_{i j k} + L T) \\ \forall i \in L S A M, m \in M S A M, j \in J_{i}, n \in J_{m}, k \end{array}

(8)

\begin{matrix} F T_{i j k} = \frac{{F F T R_{i k} - α_{i k} (T_{i j} - F F T_{i k})} q_{i j}}{V I_{i}} \\ + \frac{{M F T R_{i k} - β_{i k} (T_{i j} - M F T_{i k})} r_{i j}}{V I_{i}} \end{matrix}

(9)

\begin{array}{l} q_{i j} + r_{i j} = 1 & \forall i, j \end{array}

(10)

\begin{array}{l} (\sum_{k = 1}^{K} X_{i 1 k}) \cdot R T_{i} \leq T_{i 1} & \forall i \end{array}

(11)

\begin{array}{l} \sum_{i \in I_{b}} \sum_{j = 1}^{J_{i}} G_{i j p} \leq S E_{b} & \forall b, p \end{array}

(12)

\begin{array}{l} X_{i j k} \in {0, 1}, q_{i j} \in {0, 1}, r_{i j} \in {0, 1}, \\ G_{i j p} \in {0, 1}, T_{i j} \geq 0 \end{array}

(13)

목적함수 (1)은 탄도미사일이 요격되는 고도를 최대화 하는 것을 의미한다. 제약조건 (2)는 요격미사일은 하나 의 탄도미사일만 공격할 수 있도록 제한한다. 제약조건 (3)은 요격미사일이 순차적으로 발사되도록 제한한다. 제 약조건 (4)는 요격미사일을 연속으로 발사할 경우 최소 발사 간격을 제한한다. 제약조건 (5)는 탄도미사일에 할 당되는 요격미사일의 수를 제한한다. 제약조건 (6)은 하 나의 탄도미사일에 L-SAM과 M-SAM이 함께 할당되면 M-SAM의 수가 더 많도록 제한한다. 제약조건 (7)은 요 격미사일의 발사 시간이 발사 가능한 최초 시간과 최후 시간 내에 있도록 제한한다. 제약조건 (8)은 Shoot-Look- Shoot 사격 전술을 위해 탄도미사일에 L-SAM이 발사되 었을 경우, L-SAM의 교전 결과를 확인하기 전에 M-SAM 이 발사되지 않도록 제한한다. 제약조건 (9)와 (10)은 시 간이 지남에 따라 요격미사일과 탄도미사일 사이의 거리 가 비선형으로 줄어들기 때문에 발사가능 시간 내에서 2 개 구간으로 구분하여 제약조건 (8)의 비행시간(FT_ijk)을 선형화하는 조건이다. 제약조건 (11)은 작전통제소로부터 요격명령을 받은 발사대가 첫 번째 요격미사일을 발사하 기 전까지 소요되는 준비 시간을 제한한다. 제약조건 (12)는 포대 레이더가 동시에 유도할 수 있는 요격미사 일의 수를 제한한다. 제약조건 (13)은 결정변수에 대하여 비음조건 및 이진수 조건을 부여한다.

4제안하는 유전 알고리즘

본 연구에서 제안하는 알고리즘은 WTA 연구에서 많이 적용되는 메타 휴리스틱 알고리즘 중 유전 알고리즘을 기 반으로 하여 수선(repair) 연산 부분을 강화하고, 교차 연산 에 PSO 알고리즘의 개체의 속도 및 위치 업데이트 개념을 이용하여 보다 향상된 유전 알고리즘이다. 알고리즘의 흐 름도는 <Figure 1>과 같으며, 다음과 같이 실행된다.

STEP 1 : 초기 해집단을 임의로 생성한다.
STEP 2 : (생성된 해집단의) 각 염색체는 실행불가능한 해일 수 있으므로 수선 연산을 통해 실행 가 능한 해가 되도록 한다.
STEP 3 : 각 염색체의 적합도를 계산하여 염색체 자신 이 가장 좋은 적합도를 가졌을 때의 유전자 정보(이하 Pbest 염색체)와 전 세대에서 가장 좋은 적합도를 가진 염색체(이하 Gbest 염색 체)를 업데이트 한다.
STEP 4 : 종료 조건을 확인하여 해당될 경우 종료하고, 그렇지 않으면 STEP 5로 이동한다.
STEP 5 : 각 염색체는 Pbest 염색체, Gbest 염색체와의 교차 연산을 통해 자식 염색체를 생성한다.
STEP 6 : 자식 염색체는 돌연변이 연산을 실시한 후 STEP 2로 이동하고, 종료 조건이 만족될 때까지 STEP 2~STEP 6까지의 절차를 반복한다.

4.1염색체 표현 및 초기 해집단 생성

염색체는 <Table 2>와 같이 어느 포대의 어떤 발사대 의 몇 번째 요격미사일이 어떤 표적에 할당되었는지를 이진수로 표현하는 형태이며, 할당이 되면 숫자 “1”로 표기한다. 예를 들면, <Table 2>의 가운데 부분에서 괄호 안에 있는 “1”은 A포대 1번 발사대의 세 번째 요격미사 일이 표적 3에 할당이 되었고, 이 요격미사일은 최초 표 적을 탐지한 시간으로부터 49.6초 후에 발사된다는 것을 의미한다.

염색체를 이진수로 표현한 것은 수선 연산에서 이진 수가 십진수보다 편리하기 때문이다.

초기 해집단은 염색체의 각 유전자 단위에서 0 또는 1 의 값을 임의로 부여하는 방법을 사용하였다. 단, 요격미 사일이 요격할 수 없는 표적에는 0의 값을 부여한다. 그 리고 이 단계에서는 발사 시간을 부여하지 않는다. 어떤 발사대의 몇 번째 요격미사일이 어떤 표적에 할당되는지 에 따라 발사 시간은 큰 영향을 받기 때문에 수선 연산 단계에서 제약조건을 만족하면서 가장 빠른 시간을 부여 하도록 한다.

4.2수선 연산

수선 연산은 <Figure 1>에서 보는 것과 같이 2개의 단 계로 구분되는데, 1단계에서는 제약조건 (2)~제약조건 (11) 을 만족시키도록 수선 연산을 하고, 2단계에서는 제약조 건 (12)를 만족시키도록 수선 연산을 한다. 2개의 단계로 구분한 것은 포대 레이더의 동시 유도 능력이 제한됨에 따라 염색체 일부 유전자의 값이 한 번 더 바뀌게 되며, 당초 Lee and Yang[18]의 모형이 기본 모형과 확장 모형으 로 구분되기 때문에 이해를 돕고자 임의로 구분하였다.

1단계 수선 연산은 다음과 같은 절차로 실행된다. STEP 1~STEP 6은 염색체의 L-SAM 부분 유전자 값이 제약조건 (2)~제약조건 (7), 제약조건 (11)을 만족하도록 유전자 값을 수정하고, 표적이 할당된 요격미사일에는 발사 순서대로 가장 빠른 발사 시간을 부여한다. STEP 7~STEP 10은 염색체의 M-SAM 부분 유전자 값이 제 약조건 (2)~제약조건 (11)을 만족하도록 유전자 값을 수정하고, 표적이 할당된 요격미사일에는 발사 순서대 로 가장 빠른 발사 시간을 부여한다.

STEP 1 : 표적별로 할당된 L-SAM의 수를 확인하고, 표적 에 할당된 L-SAM의 수가 D_k의 1/2을 초과한다 면 해당 표적에 할당할 L-SAM의 수를 D_k의 1/2 범위 내에서 임의로 다시 선택한다.
STEP 2 : 해당 표적에 할당된 L-SAM의 수가 D_k의 1/2을 초과하여 임의로 다시 선택한 경우, 현재 1의 값 을 가진 유전자 중에 해당 값만큼을 임의로 선 택하여 1의 값을 유지하도록 하고, 나머지는 모 두 0으로 바꾼다.
STEP 3 : 발사대별로 각 요격미사일이 몇 개의 표적에 할 당되었는지를 확인하고, j번째 요격미사일에 2 개 이상의 표적에 할당되었다면 그 중 임의로 선택된 1개 표적을 제외한 나머지 표적에 할당 된 유전자 값 1은 바로 아래로 내린다. 바로 아 래의 유전자가 1의 값을 가지고 있다면 그 아래 로 내린다.
STEP 4 : j번째 요격미사일에 표적이 할당되지 않았는데, j + 1번째 요격미사일에 표적이 할당되었다면 j + 1번째 요격미사일에 할당된 표적 중 가장 좌 측에 있는 표적의 유전자 값을 위로 올린다.
STEP 5 : L-SAM 각 발사대의 첫 번째 요격미사일의 발사 가능한 최초 시간(FFT_ik)과 반응 시간(RT_i )을 비교하여 늦은 시간을 발사 시간으로 하고, 발사 시간을 기준으로 요격미사일의 교전 결과 확인 시간을 포함한 비행종료 시간을 산출한다.
STEP 6 : L-SAM 각 발사대의 두 번째 요격미사일부터는 바로 앞 요격미사일의 발사 시간에 연속 발사 간격(SFT_i )을 더한 시간(이하 PLT)과 FFT_ik를 비교한다. PLT가 FFT_ik보다 늦고, LFT_ik보다 빠르면 PLT가 발사 시간이 된다. 만약 PLT가 LFT_ik보다 늦으면 해당 요격미사일의 유전자 값은 모두 0으로 바꾸고, 후속 요격미사일의 유 전자 값을 하나씩 위로 올린다. PLT가 FFT_ik보 다 빠르면 FFT_ik가 발사 시간이 된다. 발사 시 간을 기준으로 요격미사일의 교전 결과 확인 시 간을 포함한 비행종료 시간을 산출한다.
STEP 7 : 표적별로 할당된 L-SAM의 수를 확인하고, 표적 별로 L-SAM의 가장 늦은 비행종료 시간을 확인 한다.
STEP 8 : 표적별로 할당된 M-SAM의 수를 확인하고, 표적 에 할당된 M-SAM의 수가 D_k에서 할당된 LSAM의 수를 뺀 값을 초과한다면 해당 표적에 할당할 M-SAM의 수를 허용 범위 내에서 임의 로 다시 선택한다.
STEP 9 : M-SAM 부분에 대하여 STEP 2~STEP 4까지의 절차를 반복한다.
STEP 10 : M-SAM의 발사 시간은 STEP 5~STEP 6까지의 절차를 반복하는데, 표적별로 L-SAM의 늦은 비행종료 시간을 추가로 비교하여 결정한다.

1단계 수선 연산 과정 중 몇 발의 요격미사일을 할당 할 것인지 어떤 요격미사일의 유전자 값을 유지할 것인 지에 대해 임의로 정하는 부분이 있다. 이는 Coello[5]의 주장과 같이 수선 연산이 편향된 결과를 유도할 수 있어 실행 시간이 더 소요될 수 있더라도 임의로 정하는 방법 을 적용하였다.

2단계 수선 연산은 제약조건 (12)를 만족시키기 위해 다 음과 같은 절차로 실행된다. STEP 1~STEP 2는 L-SAM 포 대의 동시 유도 능력을 초과한 요격미사일을 삭제하고, STEP 3~STEP 4는 요격미사일의 삭제에 따라 바뀐 LSAM의 비행종료 시간에 맞추어 M-SAM의 발사 시간을 수정한다. STEP 5~STEP 7은 M-SAM 포대의 동시 유도 능 력에 맞추어 요격미사일의 할당 및 발사 시간을 재산출하고, STEP 8~STEP 10은 앞의 수선 과정에서 제약조건을 위배 한 부분을 찾아 다시 제약조건을 만족하도록 수정한다.

STEP 1 : L-SAM 각 포대에서 발사될 요격미사일의 수를 확인하고, 동시에 유도할 수 있는 요격미사일의 수(SE_b)를 초과한 포대에 대해서는 발사될 요격 미사일을 발사 시간이 빠른 순으로 확인한다.
STEP 2 : 발사 시간이 가장 늦은 요격미사일부터 SE_b를 만족시킬 때까지 발사하지 않는 것으로 바꾼다 (유전자 값과 발사 시간을 0으로 수정).
STEP 3 : 표적별로 L-SAM의 가장 늦은 비행종료 시간을 확인한다.
STEP 4 : 표적별로 L-SAM의 가장 늦은 비행종료 시간이 바뀔 수 있으므로 1단계 수선 연산의 STEP 10 절차를 실시하여 M-SAM의 발사 시간을 수정 한다.
STEP 5 : M-SAM 각 포대에서 발사될 요격미사일의 수를 확인하고, 동시에 유도할 수 있는 요격미사일의 수(SE_b)를 초과한 포대에 대해서는 발사될 요격 미사일을 발사 시간이 빠른 순으로 확인한다.
STEP 6 : 발사 시간이 가장 빠른 요격미사일부터 SE_b 내 에 들어온 요격미사일들(A 그룹)의 비행종료(교 전 결과 확인 시간 제외) 시간을 산출하고, 비행 종료 시간이 가장 빠른 순으로 요격미사일을 확 인한다.
STEP 7 : A 그룹에 속한 요격미사일 중 비행종료 시간이 가장 빠른 시간부터 A 그룹에 속하지 못한 요격 미사일 중 가장 빠른 발사 시간을 가진 요격미 사일 순으로 발사 시간을 비교하여 비행종료 시 간보다 발사 시간이 늦다면 해당 요격미사일은 현재의 유전자 값을 유지한다. 만약 발사 시간 이 비행종료 시간보다 빠르고, 비행종료 시간이 LFT_ik보다 빠르면 해당 요격미사일의 발사 시 간을 비행종료 시간으로 수정한다. 비행종료 시 간이 LFT_ik보다 늦다면 해당 요격미사일은 발 사하지 않는 것으로 바꾼다(유전자 값과 발사 시간을 0으로 수정).
STEP 8 : STEP 1~STEP 7을 실행하는 동안 포대 레이더 의 동시 유도 능력 조건에 따라 발사하지 않는 것으로 유전자 값이 변경된 요격미사일 때문에 제약조건 (6)을 만족시키지 못하는 경우가 발생 할 수 있으며, 해당사항이 발생되었다면 L-SAM 각 포대 단위에서 초과한 만큼 요격미사일을 발 사하지 않는 것으로 바꾼다(유전자 값과 발사 시간을 0으로 수정).
STEP 9 : STEP 1~STEP 8을 실행하는 동안 포대 레이더 의 동시 유도 능력 조건에 따라 발사하지 않는 것으로 유전자 값이 변경된 요격미사일 때문에 제약조건 (3)을 만족시키지 못하는 경우가 발생 할 수 있어 발사대 단위에서 해당사항이 발생되었 다면 아래 요격미사일을 위로 끌어 올린다.
STEP 10 : STEP 1~STEP 9을 실행하는 동안 발사 시간이 변경되어 제약조건 (4)를 만족시키지 못하는 경우가 발생할 수 있어 발사대 단위에서 해당 사항이 발생된다면 SFT_i 와 LFT_ik을 비교하여 발사 시간을 조정한다. 만약 제약조건을 만족 시킬 수 없다면 해당 요격미사일은 발사하지 않는 것으로 바꾼다(유전자 값과 발사 시간을 0으로 수정).

이렇게 해서 2단계의 수선 연산이 완료된 염색체는 모 든 제약 조건을 만족하게 된다.

4.3교차 연산

PSO 알고리즘에서 개체의 다음 위치( $X_{i, (t + 1)}$ )는 식 (14) 와 같이 속도( $V_{i, (t + 1)}$ )를 통해 결정되고, 그 속도는 식 (15) 와 같이 관성 가중치(W : inertia weight)와 상수(C) 및 확 률변수(R : random variable), Gbest 개체의 정보, Pbest 개체의 정보에 따라 결정된다. 이렇게 우수한 개체(Pbest/ Gbest 개체)의 정보를 이용하여 자신의 위치를 계속 수 정하면서 최적해를 찾아가는 PSO 알고리즘에서는 좋은 개체를 찾기 위한 선택 절차가 별도로 필요하지 않는다. 그래서 본 연구에서는 PSO 알고리즘의 이런 프로세스를 참고하여 개체의 위치와 속도 업데이트 방법을 새로운 유전 알고리즘의 교차 연산에 이용하고, 유전 알고리즘 의 주요 절차인 선택 연산을 제외하였다. 이런 방법을 적 용함에 따라 선택 연산에 소요되는 시간은 줄어들고, 우 수 염색체와 지속적인 교차 연산을 통해 최적해를 보다 신속하게 찾을 수 있을 것으로 예상된다. 반면 비슷한 염 색체와 계속된 교차 연산으로 인해 지역 최적해에 빠지 는 것이 우려될 수도 있지만 돌연변이 연산과 돌연변이 연산과 비슷한 효과를 보이는 수선 연산이 지역 최적해 에 빠지는 것을 방지할 것으로 예상된다.

X_{i, (t + 1)} = X_{i, t} + V_{i, (t + 1)} i : 개체 t : 세대

(14)

\begin{matrix} V_{i, (t + 1)} = W \cdot V_{i, t} + C 1 \cdot R 1 (P b e s t_{i} - X_{i, t}) \\ + C 2 \cdot R 2 (G b e s t - X_{i, t}) \end{matrix}

(15)

<Table 2>에서 보는 것과 같이 염색체가 2차원의 형태 를 갖기 때문에 다차원 교차 연산 중 블록 균등 교차 방 법을 적용하며, <Figure 2>와 같이 각 표적마다 0과 1사 이의 난수를 발생시켜 난수의 크기에 따라 자식 염색체 에 자신의 유전자, Pbest 염색체의 유전자, Gbest 염색체 의 유전자 중 어떤 유전자를 남길 것인지 결정하는 방법 이다. 예를 들면, 난수 값이 0~0.4이면 자신의 유전자, 0.4~ 0.7이면 Pbest 염색체의 유전자, 0.7~1이면 Gbest의 염색 체의 유전자를 남긴다. 염색체에서 발사 시간 부분은 교 차 연산을 하지 않고, 수선 연산에서 결정한다.

4.4돌연변이 연산

돌연변이는 <Figure 3>과 같이 각 염색체의 유전자 단 위에서 난수를 발생시키고, 난수와 돌연변이율을 비교하 여 난수가 돌연변이율보다 작을 경우 해당 유전자의 값 을 변경한다. 해당 유전자가 1의 값을 가졌다면 0으로 변경하고, 0의 값을 가졌다면 1로 변경한다. 단, 돌연변 이 연산도 교차 연산과 마찬가지로 염색체의 발사 시간 부분에 대해서는 적용하지 않는다.

4.5적합도 평가

적합도는 대부분의 WTA 연구와 같이 식 (1)의 목적함 수를 이용한다. 적합도 평가 절차에서는 Pbest 염색체와 Gbest 염색체를 선정하며, 세대가 종료될 때마다 업데이 트를 한다. Pbest 염색체는 현재의 자신 염색체와 적합도 를 비교하여 높은 값을 가진 염색체를 Pbest 염색체로 선 정하고, Gbest 염색체는 현재 세대의 모든 염색체 중 가 장 높은 적합도를 가진 염색체와 비교하여 높은 값을 가 진 염색체를 Gbest 염색체로 선정한다.

5실험 결과

5.1실험 설계

제안하는 유전 알고리즘의 성능은 수선 연산을 추가한 일반적인 유전 알고리즘과 연구모형에 대하여 ILOG CPLEX 12.6을 사용하여 구한 결과 값을 비교하여 검증한다. 일반 적인 유전 알고리즘에 본 연구에서 개발하는 수선 연산을 추가한 것은 Colleo[5]의 연구에서와 같이 진화 알고리즘 에서 제약조건을 만족시키기 위해 많이 사용되는 벌칙 함 수 기법을 검토하였으나 벌칙 함수 기법으로는 실행가능한 해를 찾기 어려웠기 때문이다. 각 유전 알고리즘은 Microsoft Visual Studio 2010 C++로 구현하였으며, 실험은 Core (TM) i7-2670QM 2.20GHz CPU와 8GB RAM의 성능을 가 진 PC로 실행하였다.

일반적인 유전 알고리즘은 <Figure 4>와 같이 수선 연 산, 선택 연산, 교차 연산, 돌연변이 연산으로 구성되며, 다음과 같이 실행된다.

STEP 1 : 초기 해집단을 임의로 생성한다.
STEP 2 : (생성된 해집단의) 각 염색체는 실행불가능한 해일 수 있으므로 수선 연산을 통해 실행 가능 한 해가 되도록 한다.
STEP 3 : 각 염색체의 적합도를 계산하여 전 세대에서 가 장 좋은 적합도를 가진 염색체(Gbest 염색체)를 업데이트 한다.
STEP 4 : 종료 조건을 확인하여 해당될 경우 종료하고, 그렇지 않으면 STEP 5로 이동한다.
STEP 5 : 교차 연산에 사용될 부모 염색체를 고르기 위 해 선택 연산을 실시한다.
STEP 6 : 선택된 부모 염색체는 교차 연산을 통해 자식 염색체를 생성한다.
STEP 7 : 자식 염색체는 돌연변이 연산을 실시한 후 STEP 2로 이동하고, 종료 조건이 만족될 때까지 STEP 2~STEP 7까지의 절차를 반복한다.

일반적인 유전 알고리즘에서 선택 연산은 해의 다양성 을 보장하기 위해 가장 좋은 해의 적합도가 가장 나쁜 해 의 적합도의 3~4배가 되도록 조절하는 품질비례 룰렛 휠 방식을 적용하였다[25]. 교차 연산은 <Figure 5>와 같이 각 표적마다 0과 1사이의 난수를 발생시키고, 난수가 0.5 보다 크면 자식 염색체는 1번 부모 염색체의 유전자를 0.5보다 작으면 2번 부모 염색체의 유전자를 물려받는 방 식의 블록 균등 교차 연산을 적용하였다. 돌연변이 연산 은 제안하는 유전 알고리즘과 동일하다. 교차 연산과 돌연 변이 연산의 교차율과 돌연변이율은 각각 0.8, 0.015이다.

제안하는 유전 알고리즘은 제 4.3절에서와 같이 교차 연 산에서는 난수 값이 0~0.4이면 자신의 유전자, 0.4~0.7이면 Pbest 염색체의 유전자, 0.7~1이면 Gbest 염색체의 유전자를 남기도록 하고, 돌연변이 연산의 돌연변이율은 0.015이다. 두 알고리즘 모두 해집단의 크기는 100개로 하고, 80세대 가 지나면 한 세대가 지날 때만다 돌연변이율이 0.0002씩 감소하도록 한다. 그리고 유전 알고리즘은 초기 해집단의 생성 결과에 따라 실행 시간이나 해의 값에서 차이가 있으므 로 각 시나리오마다 10번씩 반복 실행하여 찾아낸 적합도 의 평균값을 비교한다. 종료 기준은 최대 1,000세대까지이며, 해집단의 70% 이상이 동일한 적합도를 같거나 100세대 동 안 적합도의 개선이 없을 경우에도 종료하는 것으로 한다.

ILOG CPLEX 12.6으로 구하는 방법은 Lee and Yang [18]의 연구에서 사용한 것과 같이 비선형인 목적함수와 제약조건을 선형화 한 이후 목적함수 값을 구한다. 선형화 방법에 대한 자세한 설명은 Lee and Yang[21]을 참고하면 된다. 그리고 포대 레이더의 동시 유도 능력을 제한할 때 적용되는 확인 시간의 간격은 3초로 동일하게 설정하고, 8,000초(약 2시간 13분)가 지나도 계속 실행된다면 8,000초까 지 구한 해의 적합도를 비교한다. 16번 시나리오부터 CPLEX 로 8,000초 내에 목적함수 값을 구하는 것이 어려워지는데, 16~18번 시나리오를 12시간 이상 실행하여 구한 값과 3,600 초(1시간)에 구한 값의 차이가 0.5% 이하여서 2시간보다 조금 큰 8,000초로 실행 시간을 임의로 제한하였다.

실험은 <부록 A>와 같이 시나리오의 크기와 형태를 바꾸어가면서 총 50개의 시나리오를 대상으로 실시한다.

5.2제안하는 유전 알고리즘의 성능

먼저 <부록 A>의 실험 시나리오들에 대하여 제안하는 유전 알고리즘의 실험 결과는 <Table 3>과 같다.

<Table 3>에서 정확수준은 [1-{(CPLEX의 목적함수 값 -유전 알고리즘의 평균 적합도)/CPLEX의 목적함수 값}]× 100으로 구했고, 표준편차수준은(표준편차/유전 알고리즘 의 평균 적합도)×100으로 구했다. <Table 3>에서 보는 것 과 같이 모든 시나리오에서 제안하는 유전 알고리즘은 일 반적인 유전 알고리즘보다 정확수준이 높고, 실행 시간 도 전반적으로 짧은 것을 알 수 있다. 그리고 본 실험에서 4, 16, 17, 18번 시나리오, 20번 이후 시나리오는 CPLEX가 8,000초 내에 최적해를 찾지 못했다.

실험결과에서 제안하는 유전 알고리즘의 정확수준이 100%를 초과하는 것을 관찰할 수 있는데, 이 경우들은 CPLEX가 8,000초 동안 계산한 해보다 제안하는 유전 알 고리즘이 더 좋은 해를 도출한 것을 의미한다. 상당히 많 은 시나리오에서 즉, 총 50개 중 20개의 시나리오에서 제 안하는 유전 알고리즘이 8,000초로 제한된 CPLEX보다 더 나은 해를 도출했음을 알 수 있다. 결과를 좀 더 자세히 살펴보면 다음과 같다.

먼저 CPLEX가 8,000초 내에 최적해를 찾은 15개의 시 나리오에서 제안하는 유전 알고리즘의 정확수준은 거의 100%이다. 즉 13개의 시나리오에서 100%로 최적해를 제시하였으며, 나머지 2개의 시나리오에서 각각 99.99%, 99.98%의 정확도를 나타냈다. 나머지 35개 시나리오의 경 우 최적해를 구했다고는 판단할 수 없지만 CPLEX가 8,000 초 동안 실행되면서 구한 목적함수 값과 비교했을 때 더 우수한 해를 제시한 경우가 20회이고, 가장 낮은 정확수 준은 96.56%이다. 제안하는 유전 알고리즘의 우수성은 가장 긴 실행 시간이 33.34초임을 감안하면 더욱 의미가 있다고 할 수 있다.

추가로 제안하는 유전 알고리즘이 최적해를 찾아가는 과정에서 어떻게 수렴하는지를 확인하기 위해 크기가 다 른 6개의 시나리오를 대상으로 종료 기준에 도달할 때까 지 각 세대의 최고 적합도 값이 어떻게 변화하는지를 일 반적인 유전 알고리즘과 함께 비교하였고, 그 결과는 <부 록 B>에 제시되어 있다. <부록 B>에서 보는 것과 같이 제안하는 유전 알고리즘은 문제 크기가 커질수록 함께 비 교한 일반적인 유전 알고리즘보다 빠르게 더 좋은 적합도 를 찾아 수렴하는 것이 확인되었다. 이는 일반적인 유전 알고리즘 대비 더 우수한 성능을 보인 것이라 할 수 있다.

6결 론

본 연구에서는 적 탄도미사일을 방어하기 위해 요격미 사일을 할당하고, 교전 일정을 계획하는 모형에 대하여 최적해를 신속하게 찾을 수 있는 향상된 유전 알고리즘 을 개발하였다. 제안하는 유전 알고리즘에는 9개의 복잡 한 제약조건을 만족시키기 위한 수선 연산이 포함되었는 데, 본 모형과 같이 실수인 요격미사일의 발사 시간이 요 격미사일과 탄도미사일의 조합 및 요격미사일의 발사 순 서에 연동되는 특성을 가지는 등 제약조건이 복잡한 경 우에는 수선 연산을 적용하는 것이 적절하다는 것을 확 인할 수 있었다. 또한 제안하는 유전 알고리즘은 실행 시 간을 단축하기 위해 PSO 알고리즘에서 사용되는 개체의 위치 및 속도 업데이트 개념을 교차 연산에 이용하고, 선 택 연산을 제외하였는데, 그 결과 기존의 일반적인 유전 알고리즘보다 우수한 해를 빠르게 찾을 수 있었다. 이는 그 성능을 직접 비교할 수는 없지만 우수한 해를 찾기 위 해 메타 휴리스틱 알고리즘을 복합적으로 사용하거나 별 도의 절차를 추가하는 기존 알고리즘에 비해 실행 절차 를 단순화하면서도 좋은 결과를 얻었다고 볼 수 있다.

제안하는 유전 알고리즘의 성능을 검증하기 위해 50개 의 실험 시나리오에 대하여 CPLEX 12.6에서 8,000초 동안 찾은 적합도 값을 비교한 결과 정확수준이 최소 96.5%를 상회하였으며, 20개의 시나리오의 경우 CPLEX의 해보다 우수한 해를 제시하였다. 또한 실행 속도도 상당히 우수 한 것으로 나타나 빠른 계산이 요구되는 현실적인 상황 에서도 의미가 있다고 판단된다. 이러한 결과를 종합해 보면 본 연구에서 개발된 향상된 유전 알고리즘은 적절한 현실적인 가정 보완을 통해서 작전통제소의 효과적 임무 수행을 지원하는데 기여할 수도 있을 것으로 기대된다.

그러나 본 알고리즘이 현장에서 보다 효과적으로 적용 되기 위해서는 보완해야할 사항이 있다. 첫째, 실제 교전 환경에서는 모든 적 탄도미사일이 동시에 탐지되지 않고, 지속적으로 탐지되어 그 수가 증가할 것이다. 그러므로 더 빠른 실행 시간을 가질 수 있도록 개선되어야 한다. 둘째, 유전 알고리즘의 특성 상 초기 해집단의 생성 결과에 따라 실행 시간과 해의 값에 차이가 발생하는데, 문제의 크기가 커질수록 이 차이는 증가한다. 따라서 알고리즘의 신뢰성 향상을 위해 여러 번 계산하더라도 동일 수준의 최적해를 산출할 수 있도록 개선되어야 한다. 셋째, 지역 최적화 알고 리즘과 같이 해의 값을 향상시키기 위한 알고리즘이 보완 된다면 더욱 우수한 최적해를 구할 수 있을 것이다.

마지막으로 향후 연구로서 본 연구에서 제안한 알고 리즘과 기존의 알고리즘들을 비교하는 연구를 고려할 수 있다. 특히 유전 알고리즘과 PSO를 결합한 기존 연구들 의 알고리즘과 장단점을 비교하는 것은 의미가 있을 것 으로 판단된다.

Acknowledgement

Mr. Lee, Dae Reock, who is the first author of this paper, is currently a Ph.D. student at the graduate school of the University of Seoul.

Figure

<Figure 1> .

The Flowchart of the New Genetic Algorithm

<Figure 2> .

Crossover Operation

<Figure 3> .

Mutation Operation

<Figure 4> .

The Flowchart of a General Genetic Algorithm

<Figure 5> .

The Block Uniform Crossover Operation of a General Genetic Algorithm

<Figure A>.

Changes of the Best Fitness Function Values

Table

<Table 1>.

The Number of Constraints in WTA Literature

# of Constraints	Related Research
1	Ahuja et al.[2], Hong et al.[9], You[32], Lee et al.[21], Liu et al.[23]
2	Ahner et al.[1], Fu et al.[6], Krokhmal et al.[17], Liu et al.[22], Murphey[26], Song et al.[27], Teng et al.[28], Zhang et al.[33], Zhu et al.[34]
3	Chen et al.[3], Lee[22]
4	Chen et al.[4], Xin et al.[31], Xin et al.[30], Geetha[7]
5	Karasakal[14], Khosla[15]
8	Jang et al.[11]
9	Lee and Yang[18]

<Table 2>.

Representation of Chromosome

*B : Battery, L : Launcher, M : Interceptor Missile.

B	L	M	T1	T3	T4	Launch time
A	1	1	1	0	0	45.6
2	1	0	0	46.6
3	0	0	(1)	49.6
2	1	0	0	1	44.2
2	0	1	0	48.6
3	0	1	0	49.6

<Table 3>.

Results

P#	A General GA	The NEW GA	CPLEX
1	99.99	0.30	100	0.13	0.00	5.87
2	99.91	0.36	100	0.18	0.00	30.70
3	99.84	0.43	100	0.23	0.00	114.99
4	99.47	0.48	99.99	0.28	0.00	8,000
5	100	0.20	100	0.13	0.00	6.88
6	99.92	0.37	100	0.18	0.00	44.69
7	99.90	0.58	100	0.22	0.00	208.46
8	99.68	0.69	100	0.27	0.00	1,113.33
9	100	0.44	100	0.22	0.00	13.85
10	99.93	0.56	100	0.28	0.00	45.01
11	99.79	0.67	100	0.35	0.00	313.56
12	99.66	1.04	99.99	0.45	0.01	4,664.87
13	99.99	0.58	100	0.29	0.00	21.65
14	99.97	0.74	100	0.39	0.00	105.71
15	99.85	0.95	100	0.49	0.00	688.03
16	99.68	1.24	99.99	0.65	0.01	8,000
17	99.60	1.85	99.95	1.02	0.04	8,000
18	99.67	2.45	99.94	1.38	0.04	8,000
19	99.56	1.90	99.98	1.03	0.01	4,144.2
20	99.59	2.88	99.98	1.61	0.02	8,000
21	99.68	3.79	99.98	2.27	0.02	8,000
22	98.97	4.05	100.05	1.72	0.08	8,000
23	99.26	5.98	100.05	3.03	0.03	8,000
24	98.78	6.18	99.66	3.86	0.05	8,000
25	98.95	3.46	99.88	2.14	0.05	8,000
26	99.26	5.27	100.03	3.41	0.06	8,000
27	99.22	10.10	99.81	4.69	0.06	8,000
28	111.34	9.98	114.62	4.86	1.81	8,000
29	107.59	15.11	110.03	7.74	1.54	8,000
30	129.32	19.71	130.53	13.40	0.14	8,000
31	102.05	9.11	105.01	5.62	2.94	8,000
32	101.44	13.87	102.11	7.44	0.17	8,000
33	101.01	19.38	102.47	12.62	3.10	8,000
34	93.63	11.57	106.08	13.98	3.99	8,000
35	204.07	22.67	220.74	23.57	3.82	8,000
36	212.92	29.74	231.90	28.95	3.34	8,000
37	101.42	16.34	103.31	8.35	0.26	8,000
38	108.02	26.08	109.86	16.29	1.26	8,000
39	102.71	34.11	104.23	25.72	0.19	8,000
40	96.81	11.64	100.78	8.49	1.59	8,000
41	101.35	14.22	103.95	12.76	0.70	8,000
42	104.02	19.65	105.79	11.63	2.18	8,000
43	87.31	9.65	96.56	10.48	2.10	8,000
44	90.93	16.47	98.94	15.05	2.63	8,000
45	92.26	23.75	97.22	26.99	0.71	8,000
46	85.28	10.90	99.33	14.45	1.26	8,000
47	97.61	23.34	107.23	19.23	1.21	8,000
48	94.20	27.85	102.92	33.34	2.30	8,000
49	82.86	16.90	97.13	16.66	1.83	8,000
50	87.90	24.74	98.30	26.53	1.28	8,000

<Table A>.

Engagement Scenarios

P#	Scenario	P#	Scenario
1	T-3, A-1, B-2, L-4, M-4, G-9	26	T-12, A-3, B-4, L-6, M-8, G-9
2	T-4, A-1, B-2, L-4, M-4, G-9	27	T-12, A-3, B-4, L-8, M-8, G-9
3	T-5, A-1, B-2, L-4, M-4, G-9	28	T-18, A-3, B-4, L-4, M-8, G-9
4	T-6, A-1, B-2, L-4, M-4, G-9	29	T-18, A-3, B-4, L-6, M-8, G-9
5	T-3, A-1, B-2, L-2, M-8, G-9	30	T-18, A-3, B-4, L-8, M-8, G-9
6	T-4, A-1, B-2, L-2, M-8, G-9	31	T-16, A-4, B-5, L-4, M-8, G-9
7	T-5, A-1, B-2, L-2, M-8, G-9	32	T-16, A-4, B-5, L-6, M-8, G-9
8	T-6, A-1, B-2, L-2, M-8, G-9	33	T-16, A-4, B-5, L-8, M-8, G-9
9	T-3, A-1, B-2, L-3, M-8, G-9	34	T-24, A-4, B-5, L-4, M-8, G-9
10	T-4, A-1, B-2, L-3, M-8, G-9	35	T-24, A-4, B-5, L-6, M-8, G-9
11	T-5, A-1, B-2, L-3, M-8, G-9	36	T-24, A-4, B-5, L-8, M-8, G-9
12	T-6, A-1, B-2, L-3, M-8, G-9	37	T-20, A-5, B-6, L-4, M-8, G-9
13	T-3, A-1, B-2, L-4, M-8, G-9	38	T-20, A-5, B-6, L-6, M-8, G-9
14	T-4, A-1, B-2, L-4, M-8, G-9	39	T-20, A-5, B-6, L-8, M-8, G-9
15	T-5, A-1, B-2, L-4, M-8, G-9	40	T-25, A-5, B-6, L-4, M-4, G-9
16	T-6, A-1, B-2, L-4, M-8, G-9	41	T-25, A-5, B-6, L-6, M-4, G-9
17	T-6, A-1, B-2, L-6, M-8, G-9	42	T-25, A-5, B-6, L-8, M-4, G-9
18	T-6, A-1, B-2, L-8, M-8, G-9	43	T-30, A-5, B-6, L-4, M-4, G-9
19	T-8, A-2, B-3, L-4, M-8, G-9	44	T-30, A-5, B-6, L-6, M-4, G-9
20	T-8, A-2, B-3, L-6, M-8, G-9	45	T-30, A-5, B-6, L-8, M-4, G-9
21	T-8, A-2, B-3, L-8, M-8, G-9	46	T-36, A-6, B-7, L-4, M-4, G-9
22	T-12, A-2, B-3, L-4, M-8, G-9	47	T-36, A-6, B-7, L-6, M-4, G-9
23	T-12, A-2, B-3, L-6, M-8, G-9	48	T-36, A-6, B-7, L-8, M-4, G-9
24	T-12, A-2, B-3, L-8, M-8, G-9	49	T-40, A-6, B-7, L-4, M-4, G-9
25	T-12, A-3, B-4, L-4, M-8, G-9	50	T-40, A-6, B-7, L-6, M-4, G-9

Reference

Ahner DK , Parson CR (2015) Optimal multi-stage allocation of weapons to targets using adaptive dynamic programming , Optimization Letters, Vol.9 (8) ; pp.1689-1701
Ahuja RK , Kumar A , Jha KC , Orlin JB (2007) Exact and heuristic algorithms for the weapon-target assignment problem , Operations Research, Vol.55 (6) ; pp.1136-1146
Chen H , Liu Z , Sun Y , Li Y (2012) Particle swarm optimization based on genetic operators for sensor-weapon-target assignment , 2012 Fifth International Symposium on Computational Intelligence and Design, ; pp.170-173
Chen J , Xin B , Peng ZH , Dou LH , Zhang J (2009) Evolutionary decision-makings for the dynamic weapontarget assignment problem , Science in China Series F : Information Sciences, Vol.52 (11) ; pp.2006-2018
Coello CA (2002) Theoretical and numerical constraint- handling techniques used with evolutionary algorithms : a survey of the state of the art , Computer Methods in Applied Mechanics and Engineering, Vol.191 ; pp.1245-1287
Fu T , Liu Y , Chen J (2006) Improved genetic and ant colony optimization algorithm for regional air defense WTA problem , Proceedings of the First International Conference on Innovative Computing, Information and Control, ; pp.226-229
Geetha S (2010) A hybrid particle swarm optimization with genetic operators for vehicle routing problem , Journal of Advances in Information Technology, Vol.1 (4) ; pp.181-188
Gulez T (2007) Weapon-target allocation and scheduling for air defense with time varying hit probabilities [master’s thesis], Middle East Technical University,
Hong SS , Han MM , Choi HJ , Mun CM (2012) A study of population initialization method to improve a genetic algorithm on the weapon target allocation problem , Journal of Korean Institute of Intelligent Systems, Vol.22 (5) ; pp.540-548
Hosein P (1989) A class of dynamic nonlinear resource allocation problems [dissertation], Massachusetts Institute of Technology,
Jang JG , Kim K , Choi BW , Suh JJ (2015) A linear approximation model for an asset-based weapon target assignment problem , Journal of Society of Korea Industrial and Systems Engineering, Vol.38 (5) ; pp.108-116
Julstrom BA (2009) String-and permutation-coded genetic algorithms for the static weapon-target assignment problem , Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference, ; pp.2553-2558
Jung HS (2013) Ballistic Missile Defense , Journal of the Defense Science and Technology Information, Vol.40 ; pp.169
Karasakal O (2004) Optimal air defense strategies for a naval task group [dissertation], Middle East Technical University,
Khosla D (2001) Hybrid genetic approach for the dynamic weapon-target allocation problem , Proceedings of SPIE, Vol.4396 ; pp.244-259
Kim MS (2013) The missiles that occupy news, KAMD and Kill Chain , Geunduun, Vol.59 ; pp.14-17
Krokhmal P , Murphey R , Pardalos P , Uryasev S Butenko S (2004) Use of conditional value-at-risk in stochastic programs with poorly defined distributions , Recent Developments in Cooperative Control and Optimization, Kluwer Academic Publishers, ; pp.225-243
Lee DR , Yang J (2015) A study on the allocation and engagement scheduling of air defense missiles by using mixed integer programming , Korean Management Science Review, Vol.32 (4) ; pp.109-133
Lee JB (2009) A study on real time dynamic multi-weapon multi-target assignment algorithm [dissertation], Korea Advanced Institute Science and Technology,
Lee MZ (2010) Constrained weapon-target assignment : enhanced very large scale neighborhood search algorithm , IEEE Transactions on Systems Man and Cybernetics-Part A Systems and Humans, Vol.40 (1) ; pp.198-204
Lee ZJ , Lee CY , Suc SF (2002) An immunity-based ant colony optimization algorithm for solving weapon- target assignment problem , Applied Soft Computing, Vol.2 (1) ; pp.39-47
Liu C , Wang H , Qiu Z (2010) An adaptive memetic algorithm solving dynamic weapon target assignment problem , IEEE International Conference on Information Engineering and Computer Science, ; pp.1-4
Liu P , Xiong J , Zhang W (2014) WTA model study of air defense missile system based on particle algorithm , Proceedings of IEEE Chinese Guidance Navigation and Control Conference Yantai China, ; pp.1534-1538
Ministry of National Defense(Republic of Korea) (2014) Defense White Paper, ; pp.58-59
Moon BR (2008) Easy Learning Genetic Algorithms, Hanbit Media Inc, ; pp.59-61
Murphey RA (1999) in Approximation and Complexity in Numerical Optimization : Continuous and Discrete Problems, Kluwer Academic Publishers, ; pp.1-16
Song Z , Zhu F , Zhang D (2009) A heuristic genetic algorithm for solving constrained weapon-target assignment problem , IEEE International Conference on Intelligent Computing and Intelligent Systems, ; pp.336-341
Teng P , Lv H , Huang J , Sun L (2008) Improved particle swarm optimization algorithm and its application in coordinated air combat missile-target assignment , Proceedings of the 7th World Congress on Intelligent Control and Automation, ; pp.2833-2837
Woo B-H (2012) Reinforced Genetic Algorithm for Solving Reliability Optimization Design Problem , Journal of the Korean Institute of Plant Engineering, Vol.17 (4) ; pp.17-33
Xin B , Chen J (2012) An Estimation of Distribution Algorithm with Efficient Constructive Repair/Improvement Operator for the Dynamic Weapon-Target Assignment , Proceedings of the 31st Chinese Control Conference, ; pp.2346-2351
Xin B , Chen J , Peng Z , Dou L , Zhang J (2011) An efficient rule-based constructive heuristic to solve dynamic weapon-target assignment problem , IEEE Transactions on Systems, Man, and Cybernetics-Part A : Systems and Humans, Vol.41 (3) ; pp.598-606
You H-S (2014) A performance improvement study on weapon assignment of fire control system [master's thesis], Hanyang University,
Zhang J , Xu C , Wang X , Yuan D (2012) ACGA algorithm of solving weapon-target assignment problem , Open Journal of Applied Sciences, Vol.2 (4) ; pp.74-77
Zhu B , Zou F , Wei J (2011) A novel approach to solving weapon-target assignment problem based on hybrid particle swarm optimization algorithm , International Conference on Electronic and Mechanical Engineering and Information Technology, ; pp.1385-1387

P#	A General GA		The NEW GA			CPLEX
P#	Accuracy (%)	Run Time (Seconds)	Accuracy (%)	Run Time (Seconds)	Standard Deviation(%)	Run Time (Seconds)
1	99.99	0.30	100	0.13	0.00	5.87
2	99.91	0.36	100	0.18	0.00	30.70
3	99.84	0.43	100	0.23	0.00	114.99
4	99.47	0.48	99.99	0.28	0.00	8,000
5	100	0.20	100	0.13	0.00	6.88
6	99.92	0.37	100	0.18	0.00	44.69
7	99.90	0.58	100	0.22	0.00	208.46
8	99.68	0.69	100	0.27	0.00	1,113.33
9	100	0.44	100	0.22	0.00	13.85
10	99.93	0.56	100	0.28	0.00	45.01
11	99.79	0.67	100	0.35	0.00	313.56
12	99.66	1.04	99.99	0.45	0.01	4,664.87
13	99.99	0.58	100	0.29	0.00	21.65
14	99.97	0.74	100	0.39	0.00	105.71
15	99.85	0.95	100	0.49	0.00	688.03
16	99.68	1.24	99.99	0.65	0.01	8,000
17	99.60	1.85	99.95	1.02	0.04	8,000
18	99.67	2.45	99.94	1.38	0.04	8,000
19	99.56	1.90	99.98	1.03	0.01	4,144.2
20	99.59	2.88	99.98	1.61	0.02	8,000
21	99.68	3.79	99.98	2.27	0.02	8,000
22	98.97	4.05	100.05	1.72	0.08	8,000
23	99.26	5.98	100.05	3.03	0.03	8,000
24	98.78	6.18	99.66	3.86	0.05	8,000
25	98.95	3.46	99.88	2.14	0.05	8,000
26	99.26	5.27	100.03	3.41	0.06	8,000
27	99.22	10.10	99.81	4.69	0.06	8,000
28	111.34	9.98	114.62	4.86	1.81	8,000
29	107.59	15.11	110.03	7.74	1.54	8,000
30	129.32	19.71	130.53	13.40	0.14	8,000
31	102.05	9.11	105.01	5.62	2.94	8,000
32	101.44	13.87	102.11	7.44	0.17	8,000
33	101.01	19.38	102.47	12.62	3.10	8,000
34	93.63	11.57	106.08	13.98	3.99	8,000
35	204.07	22.67	220.74	23.57	3.82	8,000
36	212.92	29.74	231.90	28.95	3.34	8,000
37	101.42	16.34	103.31	8.35	0.26	8,000
38	108.02	26.08	109.86	16.29	1.26	8,000
39	102.71	34.11	104.23	25.72	0.19	8,000
40	96.81	11.64	100.78	8.49	1.59	8,000
41	101.35	14.22	103.95	12.76	0.70	8,000
42	104.02	19.65	105.79	11.63	2.18	8,000
43	87.31	9.65	96.56	10.48	2.10	8,000
44	90.93	16.47	98.94	15.05	2.63	8,000
45	92.26	23.75	97.22	26.99	0.71	8,000
46	85.28	10.90	99.33	14.45	1.26	8,000
47	97.61	23.34	107.23	19.23	1.21	8,000
48	94.20	27.85	102.92	33.34	2.30	8,000
49	82.86	16.90	97.13	16.66	1.83	8,000
50	87.90	24.74	98.30	26.53	1.28	8,000