선택한 단어 수는 입니다.
최소 단어 이상 선택하여야 합니다.
최소 단어 이상 선택하여야 합니다.
선택한 단어 수는 30입니다.
최대 10 단어까지만 선택 가능합니다.
최대 10 단어까지만 선택 가능합니다.
문제 정의
- 즉, 기존 연구들에서는 ‘공격편대군-표적’, ‘표적-무장’의 조합을 결정 하였지만, 본 연구에서는 ‘공격편대군의 비행경로’가 추가적으로 고려된다. 따라서 본 연구에서는 WTA와 차량경로문제(VRP: Vehicle Routing Problem)가 통합된 유형의 문제가 제시되었다. 또한, WTA 문제와 VRP가 각각 NP-Complete, NP-hard [33] 인 조합 최적화 문제에 포함되므로 제안하는 문제는 NP-hard에 포함되며, 비선형 목적함수를 갖게 됨에 따라 이에 대한 해법으로 병렬 하이브리드 유전자 알고리즘(PHGA)을 제안하였다.
- 수리모형은 공격편대군의 비행경로가 생존확률에 영향을 미치기 때문에 차량경로문제(VRP)와 무기-표적 할당(WTA) 개념을 통합한 형태의 혼합정수계획모형(MIP)으로 제시되었다. 또한, 공군 작전계획 수립에 응용하는 수치실험을 통해 수리모형의 해가 제공하는 정보들의 효용성을 살펴보았다.
가설 설정
- 본 절에서는 ‘공격편대군별 표적’, ‘비행경로’, ‘표적별 무장’을 결정하기 위한 수리모형은 WTA와 VRP가 통합된 형태로 제시된다. 여기서, 운용하는 전투기의 기종과 무장의 종류가 제한적이고, 공격편대군 내에서 기종별 담당하는 임무와 Fig. 2와 같이 장착할 수 있는 무장의 조합이 사전에 결정되어 있으므로 공격편대군의 기종별 구성과 무장 장착에 대한 조합 또한 한정적이라는 가정을 둔다. 이는 수리모형의 해 탐색 공간을 축소하는 효과가 있다.
제안 방법
- 이러한 하이브리드 전략에는 전투기의 무장장착 능력의 제한으로 쏘티 당 공격할 수 있는 표적이 한정적임에 따라 공격편대군별 WTA 문제가 작은 사이즈로 구성되어 최적해 탐색에 많은 시간이 소요되지 않지만 공격효과에는 지대한 영향을 미친다는 현실적인 고려사항이 반영되었다. GA는 MATLAB, 최적해법은 ILOG CPLEX를 통해 구현하였으며, 두 가지 프로그램의 연동을 통해 HGA가 구현되었다.
- 즉, ‘공격편대군-표적’과 ‘비행경로(공격순서)’는 GA가 담당하고, 각 공격편대군의 비행경로 상의 표적들에 무장 할당(‘표적-무장’)은 최적해법을 적용하였다. GA는 MathWorks 사의 MATLAB, 최적해법은 IBM사의 ILOG CPLEX를통해 구현하였으며, 두 가지 프로그램의 연동을 통해 HGA가 구현되었다. 이러한 하이브리드 전략에는 실제 전투기의 무장장착 능력을 고려할 때, 쏘티 당 공격 가능한 표적 수의 제한으로 공격편대군별 WTA도작은 사이즈로 구성되어 최적해(Optimal solution) 탐색에 많은 시간이 소요되지 않지만 공격효과에는 지대한 영향을 미친다는 현실적인 고려사항이 반영되었다.
- al. [9] 의 모형을 기초로 해 탐색공간을 축소한 혼합정수계획(MIP: Mixed Integer Programming) 모형을 제안하였다.
- 본 연구의 목적함수 식 (2)는 비선형 함수이기 때문에 ILOG CPLEX에서 제공하는 최적해법을 적용할 수없다. 따라서 공격편대군별 WTA를 위해 변형된 목적함수를 적용하였다. 식 (20)에서 표적들의 전략적 가치와 생존확률만으로 구성된 항은 무장 할당과 무관한 상수항이므로, WTA의 목적함수는 식 (21)과 같이 변형될 수 있다.
- 4의 Targets)에서 동일 표적이 중복되지 않도록 하여야 한다. 따라서 본 연구에서는 잠재해를 두 부분으로 나누어 교차 연산을 수행하였다. 첫번째, 표적 공격순서와 공격편대군별 표적 개수에 대한 두 영역에 대해서는 Yuan et al.
- 따라서 본 연구에서는 WTA와 차량경로문제(VRP: Vehicle Routing Problem)가 통합된 유형의 문제가 제시되었다. 또한, WTA 문제와 VRP가 각각 NP-Complete, NP-hard [33] 인 조합 최적화 문제에 포함되므로 제안하는 문제는 NP-hard에 포함되며, 비선형 목적함수를 갖게 됨에 따라 이에 대한 해법으로 병렬 하이브리드 유전자 알고리즘(PHGA)을 제안하였다. 알고리즘의 병렬화(Parallelism)는 복수의 HGA가 해 탐색과정에서 상호간 협력하도록 설계되었음을 의미한다.
- 본 연구는 공군작전 최적화를 위한 기존 연구들의 공격편대군 생존확률 평가 방법과 임의 표적 공격에 혼합 무장 사용 등 현실적인 사항들을 개선한 새로운 수리모형을 제시하였으며, 합리적인 시간 내에 문제를 해결하기 위한 해법으로 메타 휴리스틱 기법과 최적 해법을 혼합하여 이용하는 병렬 하이브리드 유전자 알고리즘(PHGA)을 제안하였다. 수리모형은 공격편대군의 비행경로가 생존확률에 영향을 미치기 때문에 차량경로문제(VRP)와 무기-표적 할당(WTA) 개념을 통합한 형태의 혼합정수계획모형(MIP)으로 제시되었다.
- 본 연구는 제2장에서 제시된 비선형 혼합정수계획(MINLP) 모형의 해법으로써 하이브리드 병렬 유전자 알고리즘(PHGA)을 제안한다. 기존 연구들에서의 하이브리드 알고리즘들은 주로 전역탐색(Global search)과 지역탐색(Local search) 알고리즘들을 순차적으로 활용하는 전략을 사용하였다 [35-40] .
- 본 연구에서 유전자는 Fig. 4와 같이 무장장착 수량을 포함하고 있는 공격편대군 구성형태(Formation)의 번호, 공격할 표적의 개수와 순서를 표현하도록 구성하였다. 즉, 표적별 공격무장은 HGA의 잠재해(유전자) 에서 추천되지 않으며, 이는 최적해법(CPLEX)이 담당하도록 설계되었다.
- 본 연구에서는 기존 연구들을 바탕으로 ‘쏘티 당표적을 할당’하는 개념에서 새로운 최적화 수리모형 (Mathematical model)과 해법으로써 병렬 하이브리드 유전자 알고리즘(PHGA: Parallel Hybrid GA)을 제안하였다.
- 본 연구에서는 세대별 우수한 해의 생존성을 보장하되 적합도가 낮은 해에게도 확률적으로 생존 기회를 부여하는 룰렛 휠(Roulette wheel) 방법과 현 세대의 최선해를 다음 세대에 원형대로 상속하는 엘리티스트 보전 전략(Elitist preserving strategy)을 혼합한 ‘Elitist-roulette wheel’을 적용하였다.
- 본 연구의 2장에서는 기존 연구들이 고려하고 있는 생존확률에 대한 문제점을 분석하고, 개선된 생존확률 평가 방법을 기반으로 WTA 문제와 VRP가 통합된 유형의 수리모형을 제시한다. 3장에서는 본 연구에서 제시하는 문제의 특성을 고려하여 설계된 PHGA를 소개하고, 4장에서는 임의적으로 생성한 예제를 바탕으로 수행된 수치실험 결과와 수리모형의 해가 제공하는 정보의 효용성을 살펴본다.
- 본 절에서는 ‘공격편대군별 표적’, ‘비행경로’, ‘표적별 무장’을 결정하기 위한 수리모형은 WTA와 VRP가 통합된 형태로 제시된다.
- 유전자로부터 제공된 공격편대군별 구성형태, 무장보유량, 할당된 표적들의 공격순서 등에 대한 정보를 바탕으로, 목적함수 식 (22)와 제약식 식 (23)과 (24)를 갖는 WTA의 최적해를 탐색한다. 모든 공격편대군에 대해 이러한 과정을 수행한 후 원 목적함수 식 (2)를 계산한다.
- 즉, ‘공격편대군-표적’과 ‘비행경로(공격순서)’는 GA가 담당하고, 각 공격편대군의 비행경로 상의 표적들에 무장 할당(‘표적-무장’)은 최적해법을 적용하였다.
- 여기서, 표적 T8 공격시 무장 M4 2발과 M5 1발을 사용한다. 즉, 기존 연구들은 하나의 표적에 한 종류의 무장을 사용하도록 제한하나, 본 연구는 혼합 무장을 사용할 수 있도록 보다 현실화하였다.
- 하지만, 본 연구의 HGA는 탐색영역을 ‘공격편대군별 비행경로’와 ‘표적별 무장 할당’으로 구분하고 각각 GA와 최적해 법을 이용하도록 설계되었다.
대상 데이터
- 각 PHGA에 적용된 파라미터들은 Table 2와 같으며, PHGA를 통해 탐색된 최선해는 Table 3과 같다. 공격계획은 Type 2, Type 3 각 1개 편대와 Type 4 3개 편대로 구성하여 총 13개 표적을 공격하며, 예상되는 공격효과는 778.5612로 나타났다. 항공기들의 작전가능 쏘티, 무장 보유량의 제한으로 표적 T11, T14는 공격대상에서 제외되었다.
- 수치실험 예제는 항공기 4종, 무장 5종으로 편성되는 공격편대군 8종과 표적 15개로 구성하였으며, 실험에 사용한 데이터는 Table 1과 같다. 또한, 무장-표적간 파괴확률, 공격편대군의 표적 이동 간 생존확률에 대한 데이터는 부록(Appendix)에 제시하였다.
- 수치실험은 i5-3210M 2.5GHz CPU와 4GB RAM 노트북에서 수행되었으며, HPGA는 MATLAB으로 구현되었다. 각 PHGA에 적용된 파라미터들은 Table 2와 같으며, PHGA를 통해 탐색된 최선해는 Table 3과 같다.
- 이는, 모집단 기반 알고리즘의 특성상 적합도 함수에 대한 연산이 많음에 기인하며, 본 연구의 실험예제의 경우, 총 22,500회 (HGA 5개 × 50개체 × 총90세대)였다.
- 잠재해 해석에 대한 예시로, Fig. 4 에서 1번째 공격편대군은 Type 6로 구성되고 2개 표적(표적 15, 7)이 할당되었으며, 따라서 비행경로는 기지(Base)를 이륙하여 표적 15와 표적 7을 순차적으로 공격하고 기지로 귀환하는 “Base-T15-T7-Base”로 계획되었다.
이론/모형
- 첫번째, 표적 공격순서와 공격편대군별 표적 개수에 대한 두 영역에 대해서는 Yuan et al.[42] 이 제안한 TCX(Two-part chromosome crossover) 방법을 이용하였으며, TCX의 연산절차는 Fig. 6과 같다. 두 번째 부분으로, 공격편대군 구성형태 영역에 대해서는 Fig.
- 각 단위 HGA의 초기 모집단(Initial population)은 임의생성기법(Random generation method)에 의해 생성되었다. Fig.
- 6과 같다. 두 번째 부분으로, 공격편대군 구성형태 영역에 대해서는 Fig. 7과 같은 2점 교차(2-point crossover) 방법을 적용하였다.
- 이는 지역 최적 해를 탈출하여 다른 공간을 탐색할 수 있는 기회를 제공한다. 본 연구는 Fig. 4에서의 영역구분에 따라 Fig. 8과 같이 한 유전자에서 임의로 2개의 염색체를 선정하여 이들의 위치를 교체하는 2점 교환(Two-point exchange) 방법과 임의적으로 한 염색체를 수정하는 1점 돌연변이(1-point mutation) 방법을 적용하였다.
- 이주는 병렬 알고리즘의 핵심적인 단계로, 각 단위 HGA들이 지정된 세대수 동안 탐색한 우수해를 상호 교환하는 단계이다. 본 연구는 모든 단위 HGA들이 탐색한 우수해 정보를 활용하기 위해 Fig. 9와 같은 Fully-connected topology 방법을 이용하였다. 이주는 이주율(Migration rate)에 따라 각 단위 HGA의 우수해를 선별하여 우수해 집합을 구성하고, 각 HGA의 적합도가 저조한 열등해들을 우수해 집합으로 대체하는 절차로 수행된다.
- 벌금함수는 제약을 위반한 개체의 적합도가 저평가되도록 하여 실행불가능(Infeasible) 해보다 실행가능(Feasible) 해를 우선하도록 한다. 본 연구에서는 세대가 진화될수록 제약을 엄격하게 고려하는 식 (25)의 적응형(Adaptive) 벌금함수를 이용하였다. 이는, 진화 초기에는 제약을 위반하였으나 좋은 유전형질을 가진 개체를 보호하여 좋은 유전형질이 다음 세대에 상속되도록 하고, 진화세대 최종에는 실행가능한 최선해가 제공되도록 한다.
- 4와 같이 무장장착 수량을 포함하고 있는 공격편대군 구성형태(Formation)의 번호, 공격할 표적의 개수와 순서를 표현하도록 구성하였다. 즉, 표적별 공격무장은 HGA의 잠재해(유전자) 에서 추천되지 않으며, 이는 최적해법(CPLEX)이 담당하도록 설계되었다. 이에 대한 내용은 3.
성능/효과
- 즉, P01·P02 ≠ P02·P01이다. 결론적으로, 공격순서에 따라 생존확률이 변화됨을 직관적으로 알 수 있다. 식 (1)에서 Z0(y)는 기존 모형, Z1(y)은 본 연구의 생존확률 평가 방법을 기준으로 표적별 무장 할당에 대한 해(y)에 대한 공격효과를 나타낸다.
- 38초였다. 계산시간을 세부적으로 분석해 보면, MATLAB과 CPLEX 와 연동을 통한 표적별 무장 할당이 포함된 적합도 평가에 99.9 % 이상이 소요되었다. 이는, 모집단 기반 알고리즘의 특성상 적합도 함수에 대한 연산이 많음에 기인하며, 본 연구의 실험예제의 경우, 총 22,500회 (HGA 5개 × 50개체 × 총90세대)였다.
- 10은 PHGA의 해 탐색과정의 예시를 보여주고 있다. 첫 번째 이주단계에서는 5개의 HGA 중 1번째 HGA가 최선해를 제공하였으며, 이주를 통해 공유된 각 HGA의 우수해들을 바탕으로 30세대 간 새롭게 해를 탐색한 결과, 두 번째 이주단계에서는 2번째 HGA가 최선해를 제공하였으며, 이후 모든 HGA가 더 우수한 해를 탐색할 수 없어 수렴되었다. 결과적으로, 각단위 HGA는 이주를 통해 다른 HGA들의 좋은 해를 받아들임으로써 모집단의 다양성을 증대시키고, 지역 최적해로부터의 탈출할 수 있는 기회를 얻게 된다.
후속연구
- 향후 연구로는, 본 연구와 같이 최적해를 보장받을 수 없는 메타 휴리스틱을 이용하는 경우, 현실 작전에 서는 임의의 편대군에 인접한 표적들이 할당될 가능성이 높으므로 표적들에 대한 군집화(Clustering) 기법 등을 적용한다면 모집단의 크기 감소를 통해 계산시간 단축과 안정적이고 향상된 품질의 해를 도출할 수 있을 것으로 기대된다. 또한, 공격경로 상에서의 누적 생존확률 평가 등을 선형화한다면, 기존의 효율적인 최적 해법을 적용할 수 있어 계산시간이 상당히 단축되고 제공되는 정보의 가치가 높은 수리모형이 될 수 있을 것이다. 마지막으로, 최근 전쟁양상과 작전수행 형태를 고려할 때, 지대지, 공대지, 함대지 무기 등을 고려한 지‧해‧공군의 합동작전 환경에서의 표적 할당에 대한 연구가 필요하겠다.
- 또한, 공격경로 상에서의 누적 생존확률 평가 등을 선형화한다면, 기존의 효율적인 최적 해법을 적용할 수 있어 계산시간이 상당히 단축되고 제공되는 정보의 가치가 높은 수리모형이 될 수 있을 것이다. 마지막으로, 최근 전쟁양상과 작전수행 형태를 고려할 때, 지대지, 공대지, 함대지 무기 등을 고려한 지‧해‧공군의 합동작전 환경에서의 표적 할당에 대한 연구가 필요하겠다.
- 향후 연구로는, 본 연구와 같이 최적해를 보장받을 수 없는 메타 휴리스틱을 이용하는 경우, 현실 작전에 서는 임의의 편대군에 인접한 표적들이 할당될 가능성이 높으므로 표적들에 대한 군집화(Clustering) 기법 등을 적용한다면 모집단의 크기 감소를 통해 계산시간 단축과 안정적이고 향상된 품질의 해를 도출할 수 있을 것으로 기대된다. 또한, 공격경로 상에서의 누적 생존확률 평가 등을 선형화한다면, 기존의 효율적인 최적 해법을 적용할 수 있어 계산시간이 상당히 단축되고 제공되는 정보의 가치가 높은 수리모형이 될 수 있을 것이다.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.