[논문]유전알고리즘을 이용하여 최적화된 방제 자원 배치안의 분포도 분석

김혜진; 김용혁

doi:10.15207/jkcs.2020.11.4.011

유전알고리즘을 이용하여 최적화된 방제 자원 배치안의 분포도 분석
Distribution Analysis of Optimal Equipment Assignment Using a Genetic Algorithm 원문보기

한국융합학회논문지 = Journal of the Korea Convergence Society, v.11 no.4, 2020년, pp.11 - 16

초록
AI-Helper

해양 오염사고를 대비한 계획으로, 최적화된 배치안들을 수집하여 분석하는 연구가 필수적이지만, 해양 오염사고 대응을 위한 최적을 배치안을 다양화하고 분석한 연구는 아직 선행되지 않았다. 이러한 필요성에 따라, 우리는 방제자원 배치 최적화를 위한 유전알고리즘을 고안하고 이를 통해 최적의 방제 자원 배치안을 10,000 개 도출하였다. k-평균 알고리즘으로 군집화한 결과, 예상 최대 유출지역인 여수, 대산, 울산에 대하여 두 개의 군집으로 확연히 구분되었다. 우리는 이러한 군집을 새몬 맵핑을 통해 이차원으로 사영하여 배치안의 분포도를 분석하였고, 군집에 포함되는 배치안들이 그렇지 않은 배치안보다 시뮬레이션의 결과가 우수함을 확인했다. 향후, 본 연구를 기반으로 성능이 우수한 근사모델을 구현하는 것이 가능할 것으로 보인다.

Abstract ▼ AI-Helper

As a plan for oil spill accidents, research to collect and analyze optimal equipment assignments is essential. However, studies that have diversified and analyzed the optimal equipment assignments for responding to oil spill accidents have not been preceded. In response to the need for analyzing optimal equipment assignments study, we devised a genetic algorithm for optimal equipment assignments. The designed genetic algorithm yielded 10,000 optimal equipment assignments. We clustered using the k-means algorithm. As a result, the two clusters of Yeosu, Daesan, and Ulsan, which are expected to be the largest spills, were clearly identified. We also projected 16-dimensional data in two dimensions via Sammon's mapping. The projected data were analyzed for distribution. We confirmed that results of the simulation were better than those of optimal equipment assignments included in the cluster.In the future, it will be possible to implement an approximate model with excellent performance based on this study.

주제어

표/그림 (6)

표 Table 1. Maximum oil spill accident scenario
그림 Fig. 1. Flowchart of our genetic algorithm for resource allocation optimization
그림 Fig. 2. Clustering results when oil spill accident
표 Table 2. Parameters information of our genetic algorithm
그림 Fig. 3. Projection results by Sammon’s mapping
표 Table 3. Distribution analysis of optimal resource allocations

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

해당 보고서에서 방제자원배치는 해양 오염 발생에 대응하기 위해, 유출된 기름을 회수하는 장비인 유회 수기를 적절히 한국의 16 개 지역으로 분산 배치 최적화한다. 또한, 유출된 기름의 1/3을 유회수기를 이용하여 해상 회수하기 위한 최적의 배치를 찾는 것이 목표이다. 방제자원배치는 대표적인 실세계의 자원 배치 문제이기 때문에, 많은 제약조건이 존재한다.
방제자원배치는 대표적인 실세계의 자원 배치 문제이기 때문에, 많은 제약조건이 존재한다. 본 논문에서는 기름 유출 시나리오를 우리나라의 각 지역에서 최대로 유출될 수 있는 기름의 양으로 한다(Table 1 참고).
또한, 해당 패턴들에 속하는 배치안들이 좋은 시뮬레이션 결과를 보였다. 본 연구에서 진행한 최적화된 배치안을 다양화하여 분석한 결과들을 바탕으로. 시뮬레이션을 대체할 수 있는 근사모델[14, 15, 16]을 통해 속도적 이점이 있는 유전알고리즘을 설계할 수 있을 것이다.
그러나 뚜렷한 평가방법이 없는 실세계의 문제에 대하여 해를 도출하고 평가하며 최적화하는 것은 매우 어려운 일이다. 본 연구에서는 해당 문제에 대한 평가를 위해, 실제 기름 유출사고 상황과 유사한 시뮬레이션을 고안하였다. 최대유출량의 목표량을 회수하는 시간을 최소화하기 위한 시뮬레이션을 수식화하면 다음과 같다.

제안 방법

나누어진 군집들을 이용한 분포도 분석을 위해, 각 군 집에서 1,000 개의 데이터를 샘플링하여 새몬맵핑[13]을 적용하였다. 새몬맵핑은 고차원 데이터의 인스턴스간 거리를 바탕으로 저차원으로 사영하는 기법이며, 식 7처럼 나타낼 수 있다.
우리는 메타 휴리스틱의 대표적인 기법인 유전알고리즘을 사용하여 자원 배치를 최적화하는 방법을 제안하고, 10,000 개의 최적화된 배치안을 수집하여 k-평균 알고리즘과 새몬맵핑을 이용하여 분포도를 분석하였다. 최적화된 배치안을 다양화 하고 분포도를 분석한 결과, 최대 유출지역인 대산, 여수, 울산의 배치량에 따라 2 가지의 패턴으로 나누어진다는 것을 알 수 있었다.

대상 데이터

군집 분석을 위해 장비 동원 속도를 10 knot로 고정 한 후, 오염사고 발생 시각에 따라 유전알고리즘으로 최적화된 데이터를 10,000 개씩 수집하였다. 우리는 별도의 실험을 통해 k가 2일 때, 클러스터가 가장 뚜렷하게 보임을 확인했다.
우리는 유클리드 거리를 기반으로 새몬맵핑을 적용하여 16 차원의 배치안 데이터를 2 차원으로 사영하였다. 또한 밀집도를 기반으로 Fig.

이론/모형

최적화 현실의 제약조건과 지역별 적정한 소요량을 모두 반영하는 실험을 구성하기 위해 Yoon 등[8]이 작성한 국가 방제능력 산정방안 연구의 최종보고서를 기반으로 진행하였다. 해당 보고서에서 방제자원배치는 해양 오염 발생에 대응하기 위해, 유출된 기름을 회수하는 장비인 유회 수기를 적절히 한국의 16 개 지역으로 분산 배치 최적화한다.

성능/효과

최적화된 배치안을 다양화 하고 분포도를 분석한 결과, 최대 유출지역인 대산, 여수, 울산의 배치량에 따라 2 가지의 패턴으로 나누어진다는 것을 알 수 있었다. 또한, 해당 패턴들에 속하는 배치안들이 좋은 시뮬레이션 결과를 보였다. 본 연구에서 진행한 최적화된 배치안을 다양화하여 분석한 결과들을 바탕으로.
배치안을 시뮬레이션하여 얻은 평균 작업시간을 평가했을 때, 작업에 소요되는 시간이 적을수록 우수한 배치안이라 볼 수 있다. 시뮬레이션 결과, 군집에 속하지 않는 주변값들 보다 군집에 속하는 배치안들의 시뮬레이션 결과가 더 좋은 것을 확인하였다.
군집 분석을 위해 장비 동원 속도를 10 knot로 고정 한 후, 오염사고 발생 시각에 따라 유전알고리즘으로 최적화된 데이터를 10,000 개씩 수집하였다. 우리는 별도의 실험을 통해 k가 2일 때, 클러스터가 가장 뚜렷하게 보임을 확인했다. 예상 최대유출량이 가장 많은 지역인 대산, 여수, 울산을 기준으로 할당된 배치량의 범주에 따라 군집화하면 Fig.
해당 연구에서는 클라우드 클러스터, 컨 테이너, 마이크로 서비스를 포함한 네 가지의 최적화 목표로 알고리즘이 동작한다. 유전알고리즘으로 최적화된 자원을 기반으로 시스템 프로비저닝, 시스템 성능, 시스템 장애 및 네트워크 오버헤드를 향상시켰으며, 쿠버네티스(Kubernetes)에서 구현된 컨테이너 관리 정책보다 컨테이너 할당 및 탄력성 문제를 해결하기에 적합함을 보였다.
Dai와 Wang[5]은 그리드 서비스 신뢰도를 기준으로 평가하는 그리드 서비스 할당문제에 대한 최적화 모델을 제시했다. 이를 유전알고리즘을 통해 해결하였으며, 상관 장애가 없을 경우 거의 최적의 해를 찾을 수 있었다. Lavric 등[6]은 오염물질과 저수준의 자원을 갖춘 수자원 시스템을 최적화하기 위해 유전알고리즘으로 접근하였다.
입력과 출력 장치의 제약 조건과 함께 오염정도에 따라 평가되며, 수학적으로 프로그래밍한 기법과 비교하여 유전알고리즘을 이용한 기법의 우수함을 확인했다.
우리는 메타 휴리스틱의 대표적인 기법인 유전알고리즘을 사용하여 자원 배치를 최적화하는 방법을 제안하고, 10,000 개의 최적화된 배치안을 수집하여 k-평균 알고리즘과 새몬맵핑을 이용하여 분포도를 분석하였다. 최적화된 배치안을 다양화 하고 분포도를 분석한 결과, 최대 유출지역인 대산, 여수, 울산의 배치량에 따라 2 가지의 패턴으로 나누어진다는 것을 알 수 있었다. 또한, 해당 패턴들에 속하는 배치안들이 좋은 시뮬레이션 결과를 보였다.
최적화 현실의 제약조건과 지역별 적정한 소요량을 모두 반영하는 실험을 구성하기 위해 Yoon 등[8]이 작성한 국가 방제능력 산정방안 연구의 최종보고서를 기반으로 진행하였다. 해당 보고서에서 방제자원배치는 해양 오염 발생에 대응하기 위해, 유출된 기름을 회수하는 장비인 유회 수기를 적절히 한국의 16 개 지역으로 분산 배치 최적화한다. 또한, 유출된 기름의 1/3을 유회수기를 이용하여 해상 회수하기 위한 최적의 배치를 찾는 것이 목표이다.

후속연구

본 연구에서 진행한 최적화된 배치안을 다양화하여 분석한 결과들을 바탕으로. 시뮬레이션을 대체할 수 있는 근사모델[14, 15, 16]을 통해 속도적 이점이 있는 유전알고리즘을 설계할 수 있을 것이다.

질의응답

핵심어	질문	논문에서 추출한 답변
	복잡한 실세계의 자원배치 문제를 해결하기 위해 유전알고리즘을 통해 접근한 연구들 중 Dai와 Wang이 제시한 모델은 무엇인가?	이처럼 복잡한 실세계의 자원배치 문제를 해결하기 위해, 대표적인 메타 휴리스틱 기법인 유전알고리즘을 통해 접근한 연구들이 있다. Dai와 Wang[5]은 그리드 서비스 신뢰도를 기준으로 평가하는 그리드 서비스 할당문제에 대한 최적화 모델을 제시했다. 이를 유전알고리즘을 통해 해결하였으며, 상관 장애가 없을 경우 거의 최적의 해를 찾을 수 있었다.
	k-평균 알고리즘이란 무엇인가?	k-평균 알고리즘[11]은 군집분석[12]을 위해 대표적 으로 사용되는 기법으로, 각 군집의 중심(μ)까지 유클리드 거리 차이의 분산(V)을 최소화하며, 데이터를 k 개의 군집(S)으로 나눈다. 해당 알고리즘을 수식으로 나타내 면 식 6과 같다.
	자원배치 최적화를 해결하기 위해 사용하는 방법은?	그러나 자원배치 최적화문제는 높은 차원의 조합최적화 문제들이 대부분이며, 이를 해결하기 위해 해공간을 모두 탐색하여 글로 최적해를 찾는 것은 현실적으로 불가능하다. 이러한 이유로 자원배치 최적화를 해결하기 위해 적합도에 기반한 휴리스틱(heuristic) 탐색[3]을 통해 최적해를 찾는다. 자원배치 최적화 문제에는 다양한 상황과 제약을 갖는 문제들이 속하므로, 휴리스틱 탐색보다 유연하게 해를 찾아내는 메타 휴리스틱(meta heuristic)[4]을 사용하는 것이 적절하다.

참고문헌 (16)

G. Tyagi, R. Singh & A. Hussain. (2019, Apr). Applications of genetic algorithm in water resources management and optimization. International Conference on Advanced Computing and Software Engineering, (pp. 137-143).
L. Wang, S. Guo, X. Li, B. Du & W. Xu. (2018). Distributed manufacturing resource selection strategy in cloud manufacturing. The International Journal of Advanced Manufacturing Technology, 94(9-12), 3375-3388. DOI: 10.1007/s00170-016-9866-8

상세보기
J. Pearl. (1984). Heuristics: Intelligent Search Strategies for Computer Problem Solving : United States : Addison-Wesley Longman Publishing Co.
C. Blum & A. Roli. (2003). Metaheuristics in combinatorial optimization: overview and conceptual comparison. Association for Computing Machinery Computing Surveys, 35(3), 268-308. DOI : 10.1145/937503.937505
Z. S. Dai & X. L. Wang. (2006). Optimal resource allocation on grid systems for maximizing service reliability using a genetic algorithm. Reliability Engineering & System Safety, 91(9), 1071-1082. DOI : 10.1016/j.ress.2005.11.0008

상세보기
V. Lavric, P. lancu & V. Plesu. (2004). Optimal water system topology through genetic algorithm under multiple contaminated-water sources constraint. Computer Aided Chemical Engineering, 18, 433-438. DOI: 10.1016/S1570-7946(04)80138-X
C. Guerrero, I. Lera & C. Juiz. (2018). Genetic Algorithm for Multi-Objective Optimization of Container Allocation in Cloud Architecture. Journal of Grid Computing, 16(1), 113-135. DOI : 10.1007/S10723-017-9419-X

상세보기
J. H. Yun et al. (2009). A Study on Practical Strategies for Estimating the National Control Ability of Oil Spill Control. South Korea: Korea Coast Guard.
H. J. Kim, J. Lee, J. H. Yun & Y. H. Kim. (2019, July). Optimal equipment assignment for oil spill response using a genetic algorithm. Genetic and Evolutionary Computation Conference Companion. (375-376).
H. J. Kim & Y. H. Kim. (2019). Optimization of weapon target assignment using a genetic algorithm. Journal of Korean Institute of Intelligent Systems, 29(3), 176-181. DOI : 10.5391/JKIIS.2019.29.3.176

상세보기
K. W. C. Cardie & S. R. S. Schroedl. (2001). Constrained k -means clustering with background knowledge. International Conference on Machine Learning. ( 577-584).
H. J. Kim & Y. H. Kim. (2019, Dec). Distribution analysis of optimal resource allocation for oil spill response. Korean Institute of Intelligent Systems Conference. (193-194).
J. W. Sammon. (1969). A nonlinear mapping for data structure analysis. Institute of Electrical and Electronics Engineers Transactions on Computers, 18(5), 401-209. DOI : 10.1109/T-C.1969.222678

상세보기
Y. Jin. (2011). Surrogate-assisted evolutionary computation: recent advances and future challenges. Swarm and Evolutionary Computation, 1(2), 61-70. DOI : 10.1016/j.swevo.2011.05.001

상세보기
D. P. Yu & Y. H. Kim. (2019, July). Predictability on performance of surrogate-assisted evolutionary algorithm according to problem dimension. Genetic and Evolutionary Computation Conference Companion. (91-92).
H. J. Kim & Y. H. Kim (2020), Optimal resource allocation using a genetic algorithm: application to weapon-target assignment and equipment assignment for oil spill response. Doctoral dissertation. Kwangwoon University, Seoul.

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, 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

연합인증