Journal Search Engine

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

Journal of Society of Korea Industrial and Systems Engineering Vol.40 No.4 pp.260-267
DOI : https://doi.org/10.11627/jkise.2017.40.4.260

An Application of Quantum-inspired Genetic Algorithm for Weapon Target Assignment Problem

Jung Hun Kim^*†

, Kyeongtaek Kim^*

, Bong-Wan Choi^*

, Jae Joon Suh^**

^*Department of Industrial and Management Engineering, Hannam University
^**Department of Industrial and Management Engineering, Hanbat National University

Corresponding Author : afphantom@naver.com

Received November 3, 2017 Finally Revised December 21, 2017 Accepted December 22, 2017

Abstract

Quantum-inspired Genetic Algorithm (QGA) is a probabilistic search optimization method combined quantum computation and genetic algorithm. In QGA, the chromosomes are encoded by qubits and are updated by quantum rotation gates, which can achieve a genetic search. Asset-based weapon target assignment (WTA) problem can be described as an optimization problem in which the defenders assign the weapons to hostile targets in order to maximize the value of a group of surviving assets threatened by the targets. It has already been proven that the WTA problem is NP-complete. In this study, we propose a QGA and a hybrid-QGA to solve an asset-based WTA problem. In the proposed QGA, a set of probabilistic superposition of qubits are coded and collapsed into a target number. Q-gate updating strategy is also used for search guidance. The hybrid-QGA is generated by incorporating both the random search capability of QGA and the evolution capability of genetic algorithm (GA). To observe the performance of each algorithm, we construct three synthetic WTA problems and check how each algorithm works on them. Simulation results show that all of the algorithm have good quality of solutions. Since the difference among mean resulting value is within 2%, we run the nonparametric pairwise Wilcoxon rank sum test for testing the equality of the means among the results. The Wilcoxon test reveals that GA has better quality than the others. In contrast, the simulation results indicate that hybrid-QGA and QGA is much faster than GA for the production of the same number of generations.

Key Words : Weapon Target Assignment , Genetic Algorithm , Quantum-inspired Genetic Algorithm

양자화 유전자알고리즘을 이용한 무기할당

김 정훈^*†, 김 경택^*, 최 봉완^*, 서 재준^**

^*한남대학교 산업경영공학과
^**국립한밭대학교 산업경영공학과

초록

키워드 :

This article has been cited by 0 article in crossref

Cited-By

Funding:

1. 서 론

무기할당(Weapon Target Assignment: WTA) 문제는 아군지역을 공격하는 적의 표적에 대하여 아군의 방어무 기를 적절히 할당함으로써 아군의 자산을 방어하기 위한 문제이다. 과학기술의 발전으로 무기체계는 더욱 빠르고 정밀해짐에 따라 대응할 수 있는 교전시간이 짧아졌으며 컴퓨터를 이용하여 무기할당문제의 해를 구하고 빠른 의 사결정을 하는 것은 필수적이다. 실제로, 적의 탄도미사 일에 대하여 방어 체계 구축 시 지휘 및 통제(Command and Control; C2)체계 및 WTA의 자동화는 매우 중요한 이슈중의 하나이다[18].

무기할당 문제는 NP-Complete 문제로 일반적으로 확률 적 특성을 가지고 있는 비선형으로 모델링되며, 비선형모 델의 해를 구하기 위해 많은 시간이 소요되기 때문에 근사 최적해를 구하는 휴리스틱 알고리즘이 사용된다[13]. 이 중 한 가지 방법인 유전자알고리즘(Genetic Algorithm)은 복잡 한 비선형문제에 대한 탐색능력이 뛰어나고 구현이 용이하 여 무기할당 문제 분야에서 많은 연구가 이루어지고 있다. 그러나 유전자알고리즘도 제약조건이 많은 문제일수록 해 를 구하는 시간이 많이 소요되거나 지역화되는 문제가 발 생되기 때문에 많은 제약조건을 가진 모형에 대하여 신속 하게 해를 구할 수 있는 알고리즘 개발연구는 중요하다.

본 연구에서는 무기할당 문제의해를 구하기 위하여 탄도미사일 방어를 위한 자산기반 무기할당 문제의 모형 을 기반으로 양자화유전자알고리즘 및 혼합 양자화유전 자알고리즘을 적용하여 그 결과를 도출하고, 기존의 일 반적인 유전자알고리즘과 결과를 비교 및 분석하였다.

본 연구는 양자화유전자알고리즘을 무기할당 문제에 적용함으로써 무기할당 문제 해결을 위한 방법론 측면에 서 연구의 폭을 확장하였다.

2. 무기할당(WTA) 모형

무기할당모형은 크게 정적 무기할당(Static WTA) 및 동적 무기할당(Dynamic WTA)로 분류된다[6, 7]. 정적 무 기할당은 한 단계로 필요한 모든 정보를 한 번만 고려하 여 자원을 배정하는 접근방법이며, 동적 무기할당은 다단 계접근방법으로, 각 단계의 결과가평가되고, 매 단계마다 의 정보를고려하여 자원을 배정하는 접근방법이다.

무기할당모형을 분류하는 또 다른 방법으로, 목적함수 가 표적의 위협가치의 최소화인지, 방어 자산의 생존율 의 최대화인지에 따라서 표적기반 무기할당(Target-based WTA)과 자산기반 무기할당(Asset-based WTA)으로 나누 어진다[9].

대부분의 연구는 표적기반 무기할당에 집중되어왔다. 표적기반 무기할당에서는, 방어자산의 가치를 직접 표현 하지는 않고, 각 표적에 대한 위협(threat)의 정도에 따른 위협가치를 부여하고, 전체 위협가치를 최소화하는 목적 함수를 갖는다.

무기할당 문제의 해를 구하기 위한 알고리즘 연구는 주로 유전자알고리즘[14], 개미 군집 최적화(Ant Colony Optimization) 알고리즘[12], 개체 군집 최적화(Particle Swarm Optimization) 알고리즘[21] 등과 같은 휴리스틱 알고리즘 을 문제의 특성에 맞게 개선하거나 문제 특성에 최적화된 새로운 휴리스틱 알고리즘을 개발[11] 또는 두 가지 이상의 방법을 혼합하여 사용한 경우도 있었다[1, 2].

본 연구에서의 무기할당 모형은 장준건[8]의 탄도미사 일 방어를 위한 자산기반 무기할당 문제의 선형근사모형 을 기반으로 양자화 유전자알고리즘을 위해 변형시킨 모 형을 사용하였으며, 모형에 사용되는 가정사항, 기호 및 변수, 목적함수 및 제약식은 다음과 같다.

2.1. 가정사항

첫째, 각 무기가 표적에 발사한 탄약수의 합은 탄약의 재고를 초과하지 않음
둘째, 각 표적에 대한 r번째 발사가 이루어져야 r+1번 째 발사가 이루어짐
셋째, 각 무기가 s번째 발사가 이루어져야 s+1번째 발 사가 이루어짐
넷째, 표적에 대한 r번째 발사가 이루어진 후 도착시간 이후에 r+1번째 발사가 이루어짐
다섯째, 표적에 대한 무기발사는 교전시간의 범위 내에 서 이루어짐
여섯째, 각 무기는 발사 후 다음 발사까지 일정시간이 경과되어야 함

2.2. 기호 및 변수의 정의

$T = {T_{1}, \dots, T_{| T |}}$ ≜ 탐지된 표적들의 집합
$A = {A_{1}, \dots, A_{| A |}}$ ≜ 방어 자산들의 집합
$W = {W_{1}, \dots, W_{| W |}}$ ≜ 아군 방어포대들의 집합
w_k ≜ 자산 A_k의 가치
d_j ≜ 방어포대 W_j 가 가진 방어 미사일 수
p_ij ≜ 방어포대 W_j 가 한 기의 방어미사일로 표적 T_i 를 격추할 확률
q_ik ≜ 표적 T_i 가 자산 A_k를 파괴할 확률
Δ_j ≜ 방어포대 W_j 의 셋업시간

[ $Q_{i j}, R_{i j}$ ]≜방어 미사일의 유효사거리로 인한 방어포대 W_j 표적 T_i 에 대한 교전 가능 시간으로, 교전은 Q_ij 이전 에 시작할 수 없으며, R_ij까지 끝나야 한다.

$B ≜ big number$

결정변수는 다음과 같다.

x_ijrs = 1, 방어포대 W_j 의 s번째 방어미사일이 표적 T_i 에 대한 r번째 사격으로 할당

0, 그 외의 경우
t_ir≜ SLS 전략에 따라 표적 T_i 에 대한 r번째 발사 명 령이 내려진 시간
h_ijr≜ 표적 T_i 에 대한 r번째 사격으로 할당된 방어포대 W_j 에 발사명령이 내려진 순간부터 표적까지 다다 르는데 소요된 시간

2.3. 목적함수 및 제약식(11)(12)

\max \sum_{k = 1}^{| A |} w_{k} \prod_{i = 1}^{| T |} (1 - q_{i k} [\prod_{j = 1}^{| W |} \prod_{r = 1}^{m_{i}} \prod_{s = 1}^{n_{j}} {(1 - p_{i j})}^{x_{i j r s}}])

(1)

\begin{array}{l} s.t. \\ \begin{array}{l} \sum_{i = 1}^{| T |} \sum_{r = 1}^{m_{i}} \sum_{s = 1}^{n_{j}} x_{i j r s} \leq d_{j} & \forall j \end{array} \end{array}

(2)

\begin{array}{l} \sum_{j = 1}^{| W |} \sum_{s = 1}^{n_{j}} x_{i j 1 s} \leq 1 & \forall i \end{array}

(3)

\begin{array}{l} \sum_{j = 1}^{| W |} \sum_{s = 1}^{n_{j}} x_{i j, r + 1, s} \leq \sum_{j = 1}^{| W |} \sum_{s = 1}^{n_{j}} x_{i j r s} & \forall i, r = 1, \dots, m_{i} - 1 \end{array}

(4)

\begin{array}{l} \sum_{i = 1}^{| T |} \sum_{r = 1}^{m_{i}} x_{i j r 1} \leq 1 & \forall j \end{array}

(5)

\begin{array}{l} \sum_{i = 1}^{| T |} \sum_{r = 1}^{m_{i}} x_{i j r, s} \leq 1 \sum_{i = 1}^{| T |} \sum_{r = 1}^{m_{i}} x_{i j r s} & \forall i, s = 1, \dots, n_{j} - 1 \end{array}

(6)

\begin{array}{l} B (1 - \sum_{j = 1}^{| W |} \sum_{s = 1}^{n_{j}} x_{i j, r + 1, s}) + t_{i, r + 1} \geq t_{i r} + \sum_{j = 1}^{| W |} \sum_{s = 1}^{n_{j}} h_{i j r} x_{i j r s} \\ \forall i, r = 1, \dots, m_{i} - 1 \end{array}

(7)

\begin{array}{l} \sum_{j = 1}^{| W |} \sum_{s = 1}^{n_{j}} x_{i j r s} Q_{i j} \leq t_{i r} & \forall i, \forall r \end{array}

(8)

t_{i r} \leq \begin{array}{l} \sum_{j = 1}^{| W |} \sum_{s = 1}^{n_{j}} (R_{i j} - h_{i j r s}) & \forall i, \forall r \end{array}

(9)

\begin{array}{l} B (1 - x_{i j r, s + 1} \cdot x_{i^{*} j r^{*} s}) + t_{i r} \geq t_{i^{*} r^{*}} + Δ_{j} \\ \forall i, \forall j, \forall r, s = 1, \dots, d_{j} - 1, \forall i^{*}, \forall r^{*} \end{array}

(10)

x_{i j r s} b i n a r y \forall i, \forall j, \forall r, \forall s

(11)

t_{i r} \geq 0 \forall i, \forall r

(12)

식 (1)은 방어된 자산의 총 가치를 최대화하는 목적함 수이다. 식 (2)는 각 방어포대에서 표적에 발사된 방어 미사일의 수의 합이 미사일 재고를 초과할 수 없음을 나 타낸다. 식 (3)과 식 (4)는 표적에 대한 r+1번째 발사가 이루어지려면, 그 이전 r번째까지의 발사가 있어야 함을 나타낸다. 식 (5)와 식 (6)은 방어포대에서 s+1번째 방어 미사일을 발사를 하려면, 그 이전 s번째까지 발사를 해야 함을 나타낸다. $\sum_{j = 1}^{| W |} \mp \sum_{s = 1}^{n_{j}} x_{i j, r + 1, s}$ 의 값은 0 또는 1이므 로, $\sum_{j = 1}^{| W |} \mp \sum_{s = 1}^{n_{j}} x_{i j, r + 1, s}$ = 1이면, 식 (7)은 표적에 대한 r 번째 발사가 이루어 진후, r+1번째 발사는, SLS 전략에 따라 r번째 발사의 결과를 본 후에 이루어져야 함을 나 타낸다. $\sum_{j = 1}^{| W |} \mp \sum_{s = 1}^{n_{j}} x_{i j, r + 1, s}$ = 0이면, 식 (7)은 항상 성립 하여, 제한식의 역할을 하지 못한다. 식 (8)과 식 (9)는 표적에 대한 무기의 발사는 교전 시간의 창 내에서 이루 어져야 함을 나타낸다. $x_{i j r, s + 1} \cdot x_{i^{*} j r^{*} s}$ 의 값은 0 또는 1 이므로, $x_{i j r, s + 1} \cdot x_{i^{*} j r^{*} s}$ = 1이면, 식 (10)은 각 무기는 발 사 후 다음 발사까지 일정시간 경과 되어야 함을 나타낸 다. $x_{i j r, s + 1} \cdot x_{i^{*} j r^{*} s}$ = 0이면, 식 (10)은 항상 성립하여, 제 한식의 역할을 하지 못한다.

3. 일반 유전자알고리즘

유전자 알고리즘은 기본적으로 생물학적 진화원리를 기 반으로 한 탐색 및 최적화 알고리즘으로 문제의 해들을 각각의 개체인 염색체(Chromosome)로 표현하여, 목적함수 를 통해서 우수한 개체를 선택(Selection)하고, 선별된 우수 한 개체들을 교배(Crossover) 및 돌연변이(Mutation) 등의 유전자연산(Genetic Operation) 과정을 통하여 최적에 가까 운 근사 해를 구할 수 있도록 여러 세대를 거쳐 진화시키는 알고리즘이다. 이때 해들은 염색체 또는 개체(individual)라 고 표현하며, 개체들의 집합을 개체군(individuals) 또는 인 구(Population)라고 한다. 일반적인 유전자알고리즘의 구조 는 <Figure 1>과 같은 순서에 따른다.

초기 개체군을 생성하고, 개체군을 개체단위로 비용함 수를 이용하여 평가한 후 우수개체들을 선택하고, 선택 된 우수개체들을 이용하여 교배 및 돌연변이 연산 과정 을 거쳐 다음 세대로 전달하는 과정을 반복하여 최적의 해를 찾는다.

최근 유전자알고리즘을 이용한 무기할당문제에 관한 연구들은 선택, 교차, 돌연변이 등의 유전자연산자들을 개선하는 형태나 각 유전자연산자들의 매개변수에 관한 연구 또는 다른 휴리스틱 방법들과 연계하여 성능을 개 선시키는 연구들이 진행되고 있다[5].

4. 양자화 유전자알고리즘(QGA)

양자화 유전자알고리즘은 양자정보의 최소 단위인 큐 비트(Q-bit) 및 중첩상태(superposition state)와 같은 양자 계산의 개념과 원리에 기반하고 있으나, 양자컴퓨터에서 실행되는 양자컴퓨팅알고리즘이 아닌 기존의 컴퓨터에 서 실행되는 새로운 형태의 유전자알고리즘이다[3].

양자화 유전자알고리즘은 모든 개체를 0과 1의 이진 비트 로 표현하는 유전자알고리즘과는 달리 0과 1로 결정될 확률 값을 가진 양자 상태의 데이터로 정의하기 때문에 확정된 값을 갖는 다른 유전자 알고리즘에 비해 개체의 다양성이 유지되어 우수한 수렴도를 나타내며, 단일 개체에서도 지역 탐색과 전역 탐색을 동시에 수행함으로써 일반적인 유전자 알고리즘에 비하여 빠른 처리속도를 보여준다[17].

<Figure 2>에서 Q(t)는 확률 상태의 개체군인 양자개 체군 이며,Q(t)의 해당 비트 주소의 확률에 의해 0과 1의 비트 상태가 결정된 개체군 P(t)가 생성된다. 개체군 P(t) 를 비용함수에 대입하여 최우수 개체를 선별한 후 나머 지 개체들을 최우수 개체와 비교하여 다음 세대에 나머 지 개체들이 최우수 개체와 같은 값이 나오는 방향으로 확률을 조정한다[4].

4.1. 양자정보(Quantum Information)

양자화 유전자알고리즘은 모든 개체를 0과 1의 이진 비트로 표현하는 유전자알고리즘과는 달리 0과 1로 결정 될 확률 값을 가진 Q-bit로 정의한다.

Ψ > = α | 0 > + β | 1 >

(13)

{| α |}^{2} + {| β |}^{2} = 1

(14)

Q_{(t)} = {q_{1}^{t}, q_{2}^{t}, q_{3}^{t}, \dots, q_{n}^{t}}

(15)

β_{j}^{t} = [θ_{1}, θ_{2}, θ_{3}]

(16)

P (t) = {β_{1}^{t}, β_{2}^{t}, β_{3}^{t}, \dots, β_{n}^{t}}

(17)

식 (15)는 확률로 이루어진 양자개체들의 집합인 양자 개체군을 나타내며, 식 (16)은 확률에 의해 결정된 값 즉 0과 1의 값을 갖는 개체를 보여준다. 식 (17)은 결정된 개체로 이루어진 개체군을 나타낸다.

4.2. 양자유전자연산(Quantum Genetic Operation)

Q(t)는 양자게이트(Quantum Gate 또는 Q-gates)라고 하 며 양자유전자연산자(또는 변형연산자)로서 정의된다.

<Figure 2>에서 Q(t)의 갱신은 양자화 유전자알고리즘 의 Q-gates에 의해 이루어지는데,

이 연산에 의해 갱신된 Q-bit의 값 α′와 β′는 |α′|²+ |β′|² = 1을 만족한다.

U (Δ θ_{i}) = (\begin{array}{l} cos (Δ θ_{i}) & - sin (Δ θ_{i}) \\ sin (Δ θ_{i}) & cos (Δ θ_{i}) \end{array})

(18)

식 (18)의 Rotation gates는 QGA에서 기본적인 Q-gates 로서 $Δ θ_{i}$ 는 각 Q-bit가 0 또는 1상태로 향하기 위한 회 전각을 의미한다.<Figure 3>

4.3. 양자개체군 초기화

양자개체군을 초기화하는 가장 일반적인 방법은 식 (19) 와 같이 확률진폭 α와 β가 모든 Q-bit의 개체들이 같은 확률을 갖는 양자중첩 상태로 놓는 것이다.

(\begin{matrix} α_{j} \\ β_{j} \end{matrix}) = (\begin{array}{l} cos (Δ θ_{i}) & - sin (Δ θ_{i}) \\ sin (Δ θ_{i}) & cos (Δ θ_{i}) \end{array}) \frac{1}{\sqrt{2}} (\begin{matrix} 1 \\ 1 \end{matrix})

(19)

4.4. 양자개체군 갱신

양자개체군 갱신은 식 (20)과 같이 양자게이트 Q(t)와 회전연산자 U(t)의 곱으로 현재의 개체군을 최우수 개체 방향으로 이동시키면서 이루어진다.

Q (t+1) =U (t) \cdot Q (t)

(20)

4.5. 적합도 평가

적합도 평가는 위해서 식 (1)의 목적함수의 값이 종료 조건을 만족 할 때까지 우수 염색체(해)를 선정하고 업 데이트 하여 세대가 종료될 때 마다 반복하는 것을 의미 한다.

5. 제안하는 양자화 유전자알고리즘(QGA)

제안하는 양자화 유전자알고리즘은 일반 유전자알고 리즘에서 사용되는 선택, 교배, 돌연변이 연산을 하지 않 았으며, 일반 유전자알고리즘에 적용한 교배 및 돌연변 이 비율만 양자화 유전자연산을 위한 기준으로 사용하였 다. <Figure 4>에서와 같이 개체를 이루고 있는 모든 요 격미사일에 대하여 양자유전자연산을 통하여 목적함수 의 값이 최대화 되는 방향으로 개체를 이동시키는 양자 개체군 갱신 작업을 하였다.

자산기반 무기할당 문제에 대하여, 제안하는 양자화 유전자알고리즘은 다음과 같은 처리과정을 따른다.

단계 1 : 초기해 집단을 임의로 선정
단계 2 : 제약조건(미사일 발사 순서, 시기 및 발수 등) 충족 여부 판단
단계 3 : 양자연산을 통해 양자개체군 갱신
단계 4 : 적합도 평가 및 우수해 선별/비교
단계 5 : 종료조건 확인

5.1. 염색체 표현

포대(Battery) 별로 사용 가능한 요격미사일(Interceptor Missile)이 <Table 1>과 같이 주어진다. 아울러 적의 표 적미사일(Target Missile)이 몇 기 인지도 주어진다.

<Table 1>로부터 추출된 포대-요격미사일 쌍을 임의의 순서대로 나열한다. <Table 2>의 제 1열은 임의의 순서 대로 나열 된 포대-요격미사일 쌍을 보여준다.

5.2. 초기해 선택(Selection) 및 제약조건 판단

각 포대-요격미사일 쌍에 표적을 나타내는 임의의 Qbits를 배정하여 초기화 한다. 그 다음 Q-bits를 측정하면 붕괴(collapse)가 일어나 이진수로 전환되며, 이를 이용하 여 표적을 할당한다. 이와 같이 임의로 생성된 무기할당 에 대하여, 자산기반 무기할당모형 제약조건들의 충족 여부를 판단한다. 무기할당 염색체는 <Table 2>와 같이 어느 포대의 몇 번째 요격미사일이 어떤 표적 미사일에 할당되었는지를 이진수로 표현하는 형태이며, 할당이 되 면 숫자 “1”로 표현한다.

5.3. 양자연산(Quantum Operation)

양자연산은 양자유전자연산자인 Q-gate를 통하여 하며 이를 위해 <Table 3>와 같은 Lookup table을 사용하였다. Lookup table의 값은 양자화 유전자알고리즘의 성능에 큰 영향을 미치며, <Table 3>에서 δ의 값은 수렴속도와 밀접한 관계가 있다. 일반적으로, δ값은 0.1π에서 0.005π 까지의 값을 갖는다[15]. Q-bit의 값을 다음 Lookup table 에 의거하여 갱신하였다.

5.4. 적합도 평가

각 염색체가 나타내는 무기할당 결과에 대한 식 (1)의 목적함수 값을 적합도 값으로 기록한다. 개체군의 각 세 대 별로 최우수 적합도를 갖는 염색체(해)를 선정하여 세대가 종료될 때 마다 업데이트 하였다.

5.5. 혼합 양자화 유전자알고리즘(HQGA)

혼합 양자화 유전자알고리즘은 양자화 유전자알고리 즘의 근사 해의 정확도를 높이기 위하여 돌연변이 연산 을 추가한 알고리즘이다. 결과적으로 양자화 유전자알고 리즘과 일반 유전자 알고리즘을 혼합한 형태의 알고리 즘이다.

6. 모형적용 및 실험 결과

본 연구에서는 자산기반 무기할당 모형을 탄도 미사 일 방어문제에 적용하여 표적에 대한 무기할당 뿐만 아 니라, 무기 발사 시간, 표적 탄도 미사일의 수, 아군 방공 포대 수, 방어 미사일의 속도, 미사일 발사명령과 실제 발사 사이의 소요시간 등 을 입력변수로 하여 일반 유전 자알고리즘(GA), 양자화 유전자알고리즘(QGA), 혼합 양 자화 유전자알고리즘(Hybrid QGA)을 각각 적용하여 비 교실험 하였다.

6.1. 실험환경

실험환경은 컴퓨터 CPU i5-6200U2.3GHz, RAM 8G, 운영체제 WINDOW 10 PRO(64Bit), 프로그램언어 Python 2.7 하에서 실시하였다.

6.2. 실험 데이터

실험은 3가지 시나리오로 실험하였으며, 아군 포대 및 요격미사일과 적의 표적미사일에 대한 세부적인 내용은 각각 <Table 4>, <Table 5>와 같다.

6.3. 비교실험 결과

실험조건은 HQGA, QGA, GA 알고리즘에 대하여 위와 동일한 실험데이터 및 인구수 50, 교배확률 0.9%, 돌연변 이 확률 0.01%, 세대 수 100을 동일하게 적용하였다.

GA, QGA, HQGA 알고리즘을 3가지 시나리오 별로 100세대에 걸쳐 반복한 비교실험 결과 값은 <Table 6>과 같다. 100세대에 대한 100회 반복 실험시 연산 처리시간 은 QGA > HQGA > GA순으로 확연한 차이를 보였다. 그 러나, 목적 함수의 평균 값에는 세 알고리즘 사이에 근소 한 차이만 보여, 이 값들의 차이 여부를 확인할 필요가 있 다. 이를 위하여 매 실험 마다 Scenario 1의 목적 함수의 값들을 기록하여 각 알고리즘 마다 100개의 데이터를 얻은 후에 Pairwise Wilcox Rank Sum Test를 한 결과 <Table 7>과 같은 p-value를 얻었다. 따라서, 각 알고리즘 간에 Mean output에 차이가 있는 것으로 확인되었다.

7. 결 론

본 연구에서는 탄도미사일방어와 같이 짧은 시간 내 에 최적의 요격포대를 선정하고 미사일을 할당하는 무기 할당문제에 대하여 양자화 유전자알고리즘을 적용 및 실 험하였다. 이를 위해 자산기반 무기할당 모형에 일반 유 전자알고리즘, 양자화 유전자알고리즘, 혼합 양자화 유 전자알고리즘을 각각 적용하여 실험 결과를 비교하였다. 비교 결과 일반 유전자알고리즘이 양자화 유전자알고리 즘 및 혼합 양자화 유전자알고리즘보다 미세하게 우수한 결과를 가져왔으나, 양자화 유전자알고리즘의 처리속도 가 현저하게 빠른 것으로 나타났다. 본 연구는 무기할당 문제에 대하여 양자화 유전자알고리즘을 최초로 적용하 여 무기할당 문제관련 연구의 폭을 확장하였으며, 현실 세계의 제약조건을 충분히 반영한 자산기반 무기할당 모 형을 기반으로 비교실험을 하였기 때문에 향후 추가적인 연구를 통해 미사일 방어체계 구축 시 최적의 요격포대 선정 및 미사일할당 문제에 사용될 수 있을 것으로 판단 되며, 미사일 방어 작전계획 수립 시 무기체계 배치 우선 순위 결정 등에도 적용 할 수 있을 것으로 기대된다.

8. 향후 연구

향후 연구 과제로 무기할당 문제에 최적화된 양자화 유전자알고리즘 모형을 구하기 위해 다양한 시나리오에 대한 실험과 검증이 필요하며, 무기할당 문제 관련 양자 화 유전자연산자(Q-gate, Look-up table 등)의 매개변수에 관한 연구도 필요한 것으로 판단된다.

Figure

<Figure 1>.General Genetic Algorithm Flowchart

<Figure 2>.QGA Flowchart

<Figure 3>.Rotation Gate for Q-bit Individuals

<Figure 4>.Proposed QGA Flowchart

Table

<Table 1>.

Weapon Chromosome Representation

<i>B<sub>i</sub></i>: i-th Battery, Wj : i-th Interceptor Missile equipped in the battery.

	Interceptor Missile
Battery	B1	1	0	0	…	0
B2	1	1	1	…	0
B3	1	1	0	…	0
…	…	…	…	…	…
Bm	1	1	1	1	1

<Table 2>.

Weapon-Target Chromosome Representation

<i>B<sub>i</sub></i>: i-th Battery, <i>T<sub>k</sub></i>: k-th Target.

	Target
Battery	B1	1	0	1	ㆍ	0
B2	0	1	0	ㆍ	0
B3	1	1	0	ㆍ	0
…	ㆍ	ㆍ	ㆍ	ㆍ	ㆍ
Bm	0	0	0	0	0

<Table 3>.

Lookup Table of ∆θ_i

F( )is fitness, and <i>b<sub>i</sub></i>and <i>x<sub>i</sub></i>are the ith bits of the best solution b and binary solution x. δ is angle step.

xi	bi	F (xi)< F (bi)	∆θi
0	0	True	0
0	0	False	0
0	1	True	∆
0	1	False	∆
1	0	True	∆
1	0	False	∆
1	1	True	0
1	1	false	0

<Table 4>.

Battery and Interceptor Missile Data

<i>p<sub>k</sub></i>: the probability that interceptor missile kills a target.

Numberof Battery	Setup time (sec)	InterceptorMissile
2~5	1~6	2,000	3	0.5~0.6	0.1~29.9

<Table 5>.

Target Missile Data.

<i>p<sub>d</sub></i>: the probability that a target missile destroys an asset.

Target Missile
3~5	1,200~2,000	60,000	0~1

<Table 6>.

Experimental Results(run 100 times)

Scenario	Results	HQGA	QGA	GA
1	Target :5Asset :3Battery :5	Mean Output	2.498	2.502	2.519
Time(sec)	204.1	186.3	311.2
2	Target :3Asset :3Battery :5	Mean Output	2.843	2.828	2.845
Time(sec)	130.8	127.4	288.6
3	Target :3Asset :2Battery :2	MeanOutput	1.529	1.529	1.529
Time(sec)	30.2	25.8	246.9

<Table 7>.

p-value from Pairwise Wilcox Rank Sum Test

Algorithm	Sample Size	GA	QGA
GA	100	-	-
QGA	100	0.000000069	-
HQGA	100	0.0021	0.0021

Reference

S. Bisht (2004) Hybrid Genetic-Simulated Annealing Algorithm for Optimal Weapon Allocation in Multilayer Defense Scenario., Def. Sci. J., Vol.54 (3) ; pp.395-405
T. Fu , Y. Liu , J. Chen (2006) Improved Genetic & Ant Colony Optimization for Regional Air Defense WTA Problem, Proceedings of the 1st International Conference on Innovative Computers, Information, Control, ; pp.226-229
K.H. Han , J.H. Kim On Setting the Parameters Of Quantum-inspired Evolutionary Algorithm for Practical Applications, http://koasas.kaist.ac.kr/handle/10203/11267
K.H. Han , J.H. Kim (2002) Quantum-Inspired Evolutionary Algorithm for Class of Combinatorial Optimization., IEEE Trans. Evol. Comput., Vol.6 (6) ; pp.580-593
S.S. Hong , M.M. Han (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
P.A. Hosein , M. Athans (1990) Some Analytical Results for the Dynamic Weapon-Target Allocation problem, MIT Technology Report LIDSP-1944, Cambridge,
P.A. Hosein , M. Athans (1990) Preferential Defense Strategies, Part I : The Static Case, MIT Technology Report LIPS-P-2002, Cambridge,
J.G. Jang , K.T. Kim , B.W. Choi , J.J. Suh (2015) A Linear Approximation Model for an Asset-based Weapon Target Assignment Problem., Journal of Korean Institute of Intelligent Systems, Vol.38 (3) ; pp.108-116
F. Johansson (2010) Evaluating the Performance of TEWA System, Ph.D. Dissertation, Orebro University,
O. Karasakal (2008) Air Defense Missile-Target Allocation for a Naval Task Group., Comput. Oper. Res., Vol.35 ; pp.1759-1770
D.R. Lee , J.W. Yang (2016) An Efficient Genetic Algorithm for the Allocation and Engagement Scheduling of Interceptor Missile., Journal of Society of Korea Industrial and Systems Engineering, Vol.39 (2) ; pp.88-102
Z.J. Lee , C.Y. Lee , S.F. Su (2002) An Immunity based Ant Colony Optimization Algorithm for Solving Weapon- Target Assignment Problem., Appl. Soft Comput., Vol.2 (1) ; pp.39-47
S.P. Lloyd , H.S. Witsenhausen (1986) Weapon Allocation is NP-Complete, Proceedings of the IEEE Summer Computer Simulation Conference, ; pp.1054-1058
H. Lu , H. Zhang , X. Zhang , R. Han (2006) An Improved Genetic Algorithm for Target Assignment Optimization of Naval Fleet Air Defense, Proceedings of the 6^th World Congress on Intelligent Control & Automation, ; pp.3401-3405
W.A. Metler , F.L. Preston (1989) Solutions to a Probabilistic Resource Allocation Problem, Proceedings of the 28th IEEE Conference on Decision and Control, Vol.Vol. 2 ; pp.1606-1611
R.A. Murphey (2000) Target-based Weapon Target Assignment Problems, Nonlinear assignment Problems : Algorithms and Applications., Kluwer Academic Publishers, ; pp.39-53
L.B. Rafael (2016) Quantum Genetic Algorithm for Computer Scientists Computers, http://www.mdpi.com/journal/computer
J.N. Roux , J.H. van Vuuren (2007) Threat Evaluation and Weapon Assignment Decision Support : A Review of the State-of-the-Art, ORiON., Journal of ORSSA, Vol.23 (2) ; pp.151-187
E. Wacholder (1989) A Neural Network-based Optimization Algorithm for the Static Weapon-Target Assignment Problem., ORSA J. Comput., Vol.1 (4) ; pp.232-246
D-S. Yim , B.W. Choi (2010) Performance Comparison of Heuristics for Weapon-Target Assignment Problem with Transitivity Rules in Weapon ?(tm)s Kill Probability., MORSK, Vol.36 (3) ; pp.29-42
X. Zeng , Y. Zhu , L. Nan , K. Hu , B. Niu , X. He (2006) Solving Weapon Target Assignment Problem using Discrete Particle Swarm Optimization, Proceedings of the 6th World Congress on Intelligent Control and Automation, ; pp.562-3565

Numberof Battery	Setup time (sec)	InterceptorMissile
Numberof Battery	Setup time (sec)	Speed (m/sec)	Number (eachBatt’)	pk	EngageStart/ Termination (sec)
2~5	1~6	2,000	3	0.5~0.6	0.1~29.9

Target Missile
Number	Speed (m/sec)	Target-Interceptor Distance (meter)	pd
3~5	1,200~2,000	60,000	0~1