[논문]포병부대 사격순서결정을 위한 분지한계 알고리즘 연구

윤상흠; 황원식; 전재호; 이익선

문제 정의

따라서, 본 연구에서는 포병부대의 사격 순서 결정 문제를 고려하고 있으며 이에 대한 효과적인 해법을 제시하는 것을 목적으로 하고 있다. 사격순서결정문제는 복수의 표적을 복수의 무기체계를 통해 타격을 가할 경우 전체 발사임무를 모두 완료하기 위한 총 소요시간을 최소화하기 위한 사격순서를 결정하는 의사결정모형으로 정의될 수 있다.
[9]에 의해 증명됨)로써, 표적수와 부대 수의증가에 따라 문제의 복잡도가 급격히 증가하게 된다. 따라서 본 연구에서는 작은 사이즈의 문제에 대한 최적해를 효율적으로 도출할 수 있는 분지한계 법 (branch- and-bound)과 큰 사이즈의 문제에 대해서는 빠른 시간 안에 효과적인 해를 제공하는 휴리스틱을 함께 제시한다
본 수치실험은 표적의 수(#)를 9종류(6, 8, 10, 12, 14, 16, 18, 20, 22), 부대의 수#를 3종류(2, 3, 4)를 대상으로 하고, p값으로 4종류를 고려하여 총 108가지의 문제 조합에 대해 각각 20문제씩, 총 2, 160문제를 임의로 생성하였다. 실제 군사문제에서는 부대의 수는 4개를 이제는 3.3점에서 제시된 노드제거규칙들이 분지 한계 알고리즘의 성능에 얼마나 큰 도움을 주었는지 평가하기 위한 실험을 실시하였다.<표 6>는 노드 제거규칙들을 적용하지 않았을 경우의 분지한계 알고리즘의 성능평가 결과를 보여주고 있다.

가설 설정

(1) 한 부대는 동일시점에 하나의 표적에 대해서만 사격이 가능하다.
(1) 각 표적에 대한 사격은 동시에 시작된다. 즉, 표적 7에 대한 사격수행시간이 # >0 인 모든 부대들은 해당 표적 에 대한 사격 을 동시에 시 작한다.
부속성질 2 : 모든 표적이 #표적인 경우에는 모든 사격 순서 의 사격 완료시 간은 동일하다.
본 연구가 제시하는 두 번째 그리디 휴리스틱은 H1 휴리스틱과 유사하지만, Tz 값을 계산하는 방식에서 차 이점을 가진다. H1 휴리스틱은 표적들의 최종완료시간 을 최소화시키는 것이 주관심사이지만, H2는 표적들을 처리해나가는 과정에서 발생하는 유휴시간(idle time)을 줄이는 것이 주관심사이다. 따라서, 어떤 표적을 할당 할 때, 부대별로 사격완료의 최대시간값과 최소시간값 의 차이를 최소화되는 표적들을 우선적으로 처리하도 록 한다.

제안 방법

[7, 8]은 사격모형에 대한 기존연구들을상세히 기술하고 있으며 각 문제에 대한 효과적인 수리계획(mathematical formulation)들을 제안하였다. 또한, 표적 할당에 대한 라그랑지안 접근법과 사격순서결정을 위한 휴리스틱(heuristic algorithm)을 최초로 제안하였다. 김태헌과 이영훈[1]은 사격순서결정을 위한 페어 알고리즘이란 이름의 새로운 휴리스틱을 제안하였으며, Kwon[6]은 유전알고리즘을 통한 해법을 제안한 바 있다.
본 연구에서 제안하는 분지한계법의 각 노드는 전체 사격순서중에 부분순열(partial sequence)에 대응된다. 분 지단계에서는 분지할 하나의 노드(부분순열)를 선택하 고 이 부분순열에 포함되지 않은 표적들 중 한 개를 부 분순열의 뒤에 붙임으로써 새로운 노드(확장된 부분순 열)가 생성된다.
한계규칙 (bounding rule)은 각 노드의 상한과 하한을 이용하여 현재 탐색중인 노드의 제거 여부를 결정하고, 해의 수렴을 촉진시킨다. 본 연구에서는 초기 상한값으 로 제 3.4절에서 제시될 두 가지 휴리스틱들의 목적함 수 값을 구하고 그 중에서 해가 더 우수한 것을 사용한 다 즉, h1와 h2를 각각 휴리스틱 h1과 H2를 활용 하여 얻은 목적함수값이라고 할 때, 초기노드의 상한값 UB는 다음과 같다.
본 연구의 분지한계법에서는 분지한계 트리의 각 노드에서 도출된 두 가지 하한 LB1 LB2, 를 계산하여 보다 우수한 것을 각 노드별 최종 하한으로 사용한다. 즉각 노드에서의 최종 하한값은 다음과 같다.
'본 절에서는 , 그리디(Greedy) 타입의 두 가지 휴리스틱 Hl, H₂를 제안한다. 첫 번째 휴리스틱은 할당되지 않은 표적들 중에서 사격완료시간의 증가분을 최소화시켜주는 표적들을 우선적으로 할당해나가는 방식의 알고리즘이 다.
본 장에서는 제 2장에서 소개된 성질들과, 제 3장에서 제안된 분지한계 알고리즘, 제 4장에서 소개된 휴리스틱들의 성능을 평가하고 분석한다. 먼저 각 목표에 대한 사격시간(#,#) 으로부터 발생시 킨다.
본 수치실험은 표적의 수(#)를 9종류(6, 8, 10, 12, 14, 16, 18, 20, 22), 부대의 수#를 3종류(2, 3, 4)를 대상으로 하고, p값으로 4종류를 고려하여 총 108가지의 문제 조합에 대해 각각 20문제씩, 총 2, 160문제를 임의로 생성하였다. 실제 군사문제에서는 부대의 수는 4개를 이제는 3.3점에서 제시된 노드제거규칙들이 분지 한계 알고리즘의 성능에 얼마나 큰 도움을 주었는지 평가하기 위한 실험을 실시하였다.<표 6>는 노드 제거규칙들을 적용하지 않았을 경우의 분지한계 알고리즘의 성능평가 결과를 보여주고 있다.
다음으로 제 3.4절에서 제안된 휴리스틱들의 성능평 가를 위한 수치실험을 수행하였다. 결과는〈표 7＞에 요 약되어 있다.

대상 데이터

9의 네 가지 값을 고려하고 있다. 본 수치실험은 표적의 수(#)를 9종류(6, 8, 10, 12, 14, 16, 18, 20, 22), 부대의 수#를 3종류(2, 3, 4)를 대상으로 하고, p값으로 4종류를 고려하여 총 108가지의 문제 조합에 대해 각각 20문제씩, 총 2, 160문제를 임의로 생성하였다. 실제 군사문제에서는 부대의 수는 4개를 이제는 3.

성능/효과

(2) 일단 사격이 시작되면 사격임무가 완료될 때 까지 중간에 중단될 수 없다.
(3) 동일 표적에 대해 여러 부대에 사격임무가 주어진 경우 해당 표적에 대한 사격들의 시작 시점은 동일하다. 그러나, 각 부대의 사격임무가 다르기 때문에 종료되는 시점은 다를 수 있다.
성질 1 : 임의의 사격순서 S에서 S에 속한 런간에순서를 바꾸는 것은 총 사격완료시간에 변화를 주지 않는다.
〈표 2>〜〈표 5>까지의 분지한계 알고리즘의 성능 테 스트 결과를 보면, p값이 0.6이고 부대수가 2인 경우에 는 20개까지 타겟들의 경우에 모두 최적해를 찾음을 알 수 있었다. 부대의 수가 4개로 증가되면 알고리즘의 성 능은 떨어져서, 14개 정도까지 최적해를 찾을 수 있었 다 또한 실험결과표를 보면, P의 값이 작을수록 알고리 즘의 성능은 좋아짐을 알 수 있다.
6이고 부대수가 2인 경우에 는 20개까지 타겟들의 경우에 모두 최적해를 찾음을 알 수 있었다. 부대의 수가 4개로 증가되면 알고리즘의 성 능은 떨어져서, 14개 정도까지 최적해를 찾을 수 있었 다 또한 실험결과표를 보면, P의 값이 작을수록 알고리 즘의 성능은 좋아짐을 알 수 있다. 또한, 부대의 수가 작을수록 성능이 더 좋아짐을 알 수 있다.
부대의 수가 4개로 증가되면 알고리즘의 성 능은 떨어져서, 14개 정도까지 최적해를 찾을 수 있었 다 또한 실험결과표를 보면, P의 값이 작을수록 알고리 즘의 성능은 좋아짐을 알 수 있다. 또한, 부대의 수가 작을수록 성능이 더 좋아짐을 알 수 있다.
성능분석결과 휴리스틱 H2가 보다 우수한 성능을 보 임을 알 수 있었다. 또한 p값이 증가할수록 휴리스틱 알고리즘의 성능은 저하되는 것을 확인할 수 있었다.
성능분석결과 휴리스틱 H2가 보다 우수한 성능을 보 임을 알 수 있었다. 또한 p값이 증가할수록 휴리스틱 알고리즘의 성능은 저하되는 것을 확인할 수 있었다. 휴리스틱 H2는 평균적으로 5% 안팍의 오차를 가지는 것으로 보이는데, 이는 매우 우수한 성능을 가지는 것 으로 결론 내려질 수 있다.
또한 p값이 증가할수록 휴리스틱 알고리즘의 성능은 저하되는 것을 확인할 수 있었다. 휴리스틱 H2는 평균적으로 5% 안팍의 오차를 가지는 것으로 보이는데, 이는 매우 우수한 성능을 가지는 것 으로 결론 내려질 수 있다.

후속연구

사격순서결정문제에 대한 최적화 기법을 활용한 연구는 단순히 수리계획의 제안[1, 8, 9]）과 ILOG Cplex와 같은 상용패키지를 통한 접근[1,3]에 국한되어 있었다. 따라서, 본 연구에서 제시한 분지한계법을 활용하면 보 다 큰 사이즈（부대수-표적수）의 문제에 대한 최적화된 해를 찾게 될 뿐 아니라 향후에도 진행될 다양한 발견 적 해법에 대한 성능비교의 도구로도 활용될 수 있을 것이다.
또한, 본 연구결과는 동시사격상황을 확장한 개별사 격이나 혼합사격과 같은 보다 현실적인 복잡성을 가미 한 다양한 사격모형에 대한 연구에도 도움이 될 것으로 사료된다.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증

[국내논문] 포병부대 사격순서결정을 위한 분지한계 알고리즘 연구
A Branch-and-Bound Algorithm on the Fire Sequencing for Planned Artillery Operations 원문보기

Abstract ▼ AI-Helper

Keyword

AI 본문요약
AI-Helper

문제 정의

가설 설정

제안 방법

대상 데이터

성능/효과

후속연구

참고문헌 (9)

이 논문을 인용한 문헌

저자의 다른 논문 :

활용도 분석정보

활용도 Top5 논문

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

[국내논문] 포병부대 사격순서결정을 위한 분지한계 알고리즘 연구 A Branch-and-Bound Algorithm on the Fire Sequencing for Planned Artillery Operations 원문보기

Abstract ▼ AI-Helper

Keyword

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

가설 설정

제안 방법

대상 데이터

성능/효과

후속연구

참고문헌 (9)

이 논문을 인용한 문헌

저자의 다른 논문 :

윤상흠 (15) 전재호 (8) 이익선 (15)

활용도 분석정보

활용도 Top5 논문 더보기

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

[국내논문] 포병부대 사격순서결정을 위한 분지한계 알고리즘 연구
A Branch-and-Bound Algorithm on the Fire Sequencing for Planned Artillery Operations 원문보기

AI 본문요약
AI-Helper

활용도 Top5 논문