[논문]유전 이론을 이용한 위성 임무 스케줄링 알고리즘의 제어상수에 따른 적합도 변화 연구

조겸래; 백승우; 이대우

doi:10.5302/j.icros.2010.16.6.572

유전 이론을 이용한 위성 임무 스케줄링 알고리즘의 제어상수에 따른 적합도 변화 연구
Fitness Change of Mission Scheduling Algorithm Using Genetic Theory According to the Control Constants 원문보기

제어·로봇·시스템학회 논문지 = Journal of institute of control, robotics and systems, v.16 no.6, 2010년, pp.572 - 578

조겸래 (부산대학교 항공우주공학과) , 백승우 (부산대학교 항공우주공학과 대학원) , 이대우 (부산대학교 항공우주공학과)

Abstract ▼ AI-Helper

In this paper, the final fitness results of the satellite mission scheduling algorithm, which is designed by using the genetic algorithm, are simulated and compared with respect to the control constants. Heuristic algorithms, including the genetic algorithm, are good to find global optima, however, we have to find the optimal control constants before its application to a problem, because the algorithm is strongly effected by the control constants. In this research, the satellite mission scheduling algorithm is simulated with different crossover probability and mutation probability, which is major control constant of the genetic algorithm.

주제어

AI 본문요약
AI-Helper

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

문제 정의

본 연구에서는 유전 알고리즘을 이용한 위성 임무 스케줄링 알고리즘의 최적 제어상수와 그 경향을 알아보기 위하여 제어상수 값에 따른 적합도 결과를 비교하였다. 유전 알고리즘은 환경에 잘 적응한 개체가 좀 더 많은 자손을 남길 수 있다는 ‘자연선택 과정’과 유전시의 변화를 통해서 개체가 좋은 방향으로 발전해 나간다는 ‘자연진화 과정’을 모방한 최적화 알고리즘이다.

가설 설정

1) 모든 위성의 임무는 영상 촬영 임무이며, 각 임무 (mission) 당 하나의 작업(task)만이 존재한다.
2) 위성 임무는 하나씩 순차적으로 수행되며, 동시에 진행할 수 없다.
따라서 구름의 양에 따라 가중치를 차등 적용하며, 촬영 예상 지역의 구름의 양이 70%를 넘을 경우, 해당 미션을 수행하지 않도록 한다. 단, 구름의 양과 같은 날씨 변수는 예측할 수 있는 기간이 짧기 때문에 다른 고려변수와는 달리 스케줄링 시뮬레이션을 수행할 때, 정보를 받아온다고 가정하였다.
메모리 소모 또한 물리적 제한조건이며, 스케줄 수행 시, 사용된 메모리의 총합은 위성 보유 메모리 양을 넘지 않아야 한다. 실제 운용에서는 지상의 위성관제국과의 메모리 덤프를 통해 가용한 메모리양이 유동적이지만, 일반적으로 위성의 임무 스케줄 작성 시 사용가능한 메모리의 총 량은 한정되어 있다고 가정하여 스케줄을 작성하기 때문에 본 논문에서도 일정한 값을 가진다고 가정하였다.
따라서 에너지 소모는 매우 주의 깊게 고려되어야 하며, 하나의 물리적 제한조건이다. 실제 위성의 경우, 전력과 같이 소모되었다가 다시 충전되는 경우도 있으나, 본 연구에서는 시뮬레이션을 단순화하기 위하여 충전을 통하여 일정한 전력이 유지된다고 가정하였다.

제안 방법

일반적으로 알려진 교배확률 85%와 돌연변이확률 1%의 주변구간을 중심으로 시뮬레이션을 구성하였다. 교배확률은 75%에서 5%의 간격으로 95%까지 구간을 설정하였고, 돌연변이확률은 0%에서 0.5%의 간격으로 2.0%까지 구간을 설정하여 총 30가지 경우에 대해 시뮬레이션을 수행하였다.
보상은 해당 임무를 수행했을 때, 임무수행기관에 돌아오는 금전적 수입을 의미하며, 위성의 운영목적에 따라, 고려하지 않을 수도 있다. 대개, 보상이 큰 임무일수록 임무 수행 선호도가 높기 때문에, 보상 변수 값이 클수록 해당 임무의 선택 가능성을 높아지도록 하였다.
동일한 임무 시나리오와 시뮬레이션 환경을 유지한 채, 제어상수만을 변화시켜가며 시뮬레이션을 수행하였다. 교배확률과 돌연변이확률의 변화에 따른 30가지 경우를 시뮬레이션한 각각의 결과는 표 5~8과 그림 2~10과 같다.
본 논문에서 유전 알고리즘을 기반으로 디자인한 위성 임무 스케줄링 최적화 알고리즘의 적합도 변화를 알고리즘 제어상수를 달리하여 수행한 시뮬레이션을 통해 비교하였다.
고객 우선도는 스케줄링 매니저가 임무 요청자의 기관분류 및 위성 스케줄링 목적과의 관계를 고려하여 나누는 것으로, 등급 혹은 등급에 따른 임의의 점수로 표현할 수 있다. 본 논문에서는 3가지 등급으로 고객 우선도를 분류하고 각각 1, 3, 5점의 점수로 표현하였다.
그러나 아직 이들이 유전 알고리즘의 성능에 끼치는 영향을 명확하게 설명해줄 수 있는 이론이 부족하기 때문에, 특정 문제에 대해 경험과 실험에 의존해 제어상수를 결정하는 경우가 많다. 본 논문에서는 교배확률과 돌연변이 확률을 변화시켜가며 시뮬레이션을 수행하고 최종 적합도의 변화를 분석하였다.
촬영면적 변수는 촬영된 면적의 개념에 따라 다양하게 적용할 수 있다. 본 연구에서는 획득 영상 총 면적과 목표로 했던 부분의 면적의 비율, Rvalid을 채택하였다.
연산속도는 제어상수 변화에 크게 영향을 받지 않았으나, 대체적으로 교배확률 80%~85%사이에서 상대적으로 빠른 연산속도를 보여주었다. 시뮬레이션 결과는 대체적으로 기존에 수행된 연구[18,19]의 결과에 부합하며, 앞으로 수행될 유전 알고리즘을 이용한 위성 임무 스케줄링 최적화 알고리즘 연구에 있어, 적합한 제어상수를 선택할 수 있는 문헌적, 경험적 근거를 제시하였다.

대상 데이터

임의의 임무 200개로 구성된 임무 시나리오에 대하여, 유전 알고리즘 제어 상수만 변화시켜가며 시뮬레이션 결과를 비교분석하였다. 일반적으로 알려진 교배확률 85%와 돌연변이확률 1%의 주변구간을 중심으로 시뮬레이션을 구성하였다. 교배확률은 75%에서 5%의 간격으로 95%까지 구간을 설정하였고, 돌연변이확률은 0%에서 0.

데이터처리

임의의 임무 200개로 구성된 임무 시나리오에 대하여, 유전 알고리즘 제어 상수만 변화시켜가며 시뮬레이션 결과를 비교분석하였다. 일반적으로 알려진 교배확률 85%와 돌연변이확률 1%의 주변구간을 중심으로 시뮬레이션을 구성하였다.

이론/모형

즉, 문제를 풀기 위해 잠재적인 해들을 코딩된 개체로 변환하고, 여러 개의 해집합들을 모아 개체군을 형성한 뒤, 세대를 거듭하면서 이들의 유전 정보를 서로 교환하거나 새로운 유전 정보를 부여하면서 적자생존의 법칙에 따라 모의 진화를 시킴으로써, 주어진 문제에 대한 최적의 해를 찾는 계산 모델이다. 유전 알고리즘의 진행과정은 선택 연산자, 교배 연산자, 돌연변이 연산자와 적합도 함수(fitness function)를 이용한다.

성능/효과

3) 임무 시나리오의 임무들은 모두 수행 가능한 임무이며, 시간상 충돌이 없다.
시뮬레이션 결과, 교배는 선택과정의 영향을 받게 되지만 돌연변이는 이와 무관하게 유전자를 변경함으로써 전 탐색공간을 탐색한다는 특징을 가지기 때문에, 적합도 변화 결과는 적합도 값이 교배확률의 변화보다는 돌연변이확률의 변화에 영향을 많이 받는다는 것을 확인할 수 있었다. 돌연변이확률을 너무 낮게 설정하면 다른 탐색공간으로 옮겨 가기도 전에 유전 알고리즘이 지역해로 수렴하게 되고, 너무 높게 설정하면 탐색이 한 점에서 다른 점으로 불규칙적으로 점프하게 되어 불안정한 탐색 결과를 주게 된다.
그림 3에서 가장 위쪽에 위치하고 있는 돌연변이 확률 0%(점선) 그래프는 돌연변이가 일어나지 않기 때문에 적합도 값이 상대적으로 높게 나타난다. 확률적인 연산에 기반을 두고 있기 때문에 항상 경향이 일치하는 것은 아니나, 대체적으로 모든 교배확률 변화에 대해, 돌연변이확률 1%가 가장 좋은 적합도 값을 도출함을 확인하였다. 이후 수행한 시뮬레이션에서의 제어상수는 교배확률 85%, 돌연변이확률 1%로 설정하여 사용하였다.

질의응답

핵심어	질문	논문에서 추출한 답변
	휴리스틱 알고리즘의 장점은 무엇인가?	휴리스틱 알고리즘은 전역 최적해를 도출한다는 장점이 있으나, 그 성능은 다양한 알고리즘 제어상수와 밀접한 관계를 가지기 때문에 휴리스틱 알고리즘의 특성을 살려 시뮬레이션을 수행하기 위해서는 미지의 영역에 대한 탐색이 원활히 이루어질 수 있도록 적절한 제어상수를 선택해 사용하는 것이 중요하다.
	위성 임무 스케줄링에 사용되는 최적화 방법에는 무엇이 있는가?	위성 임무 스케줄링은 동시에 많은 변수를 고려해야 하기 때문에 연산양도 많은 편이며, 제한조건이 많고 최적화를 위한 동역학 모델 수립이 어렵기 때문에 전역해 탐색이 가능한 발견적 귀납법이 좋은 해법이 될 수 있다[5]. 이러한 최적화 방법으로는 타부탐색 알고리즘이나 유전알고리즘과 같은 휴리스틱 알고리즘이 많이 사용되고 있다[6-10].
	위성 임무 스케줄링이란 무엇인가?	위성 임무 스케줄링은 위성에게 요구된 작업들과 그에 따른 제한사항 및 다양한 변수들을 종합적으로 고려하여 상호간의 시간, 조건 등의 충돌을 회피함과 동시에 위성의 자원을 최대한 활용하여 운용할 수 있는 최적의 작업시간 표를 생성하는 것이다[2,3,4]. 위성 임무 스케줄링은 동시에 많은 변수를 고려해야 하기 때문에 연산양도 많은 편이며, 제한조건이 많고 최적화를 위한 동역학 모델 수립이 어렵기 때문에 전역해 탐색이 가능한 발견적 귀납법이 좋은 해법이 될 수 있다[5].

참고문헌 (19)

최수미, "우주분야 연구개발 및 산업동향," 한국항공우 주연구원, 항공우주산업기술동향 제6권 제1호, pp. 3-13, 2008.
김해동, 최해진, 김은규, "다목적 실용위성 1호의 임무 계획 및 운영," 한국항공우주학회지 제29권 제7호 pp. 118-126, 2001.

상세보기
김해동, 최해진, 김은규, "다목적 실용위성 1호의 임무 계획 및 자동 명령계획표 생성기 개발," 한국항공우주 학회지 제30권 제1호 pp. 139-146, 2002.

원문보기 상세보기
Daryl G. Boden and Wiley J. Larson, Cost-Effective Space Mission Operation, McGraw-Hill, Inc. 1996.
Kalyanmoy Deb, Multi-Objective Optimization using Evolutionary Algorithms, John&Sons, Ltd., 2001.
Glover, F., "Tabu Search-Part I," ORSA Journal on Computing 1, pp. 190-206, 1989.

상세보기
Glover, F. (1990), "Tabu Search- Part II," ORSA Journal on Computing 2, pp. 4-32, 1990.

상세보기
W.-C. Lin and D.-Y. Liao, "A tabu search algorithm for satellite imaging scheduling," Proc. of IEEE International Conference on Systems, Man and Cybernetics, pp. 1601-1606, 2004.
M. Vasquez and J.-K. Hao, "A "Logic-Constrained" Knapsack Formulation and a Tabu Algorithm for the Daily Photograph Scheduling of an Earth Observation Satellite," Computational Optimization and Applications, 2001.
S.-W. Baek, K.-R. Cho, D.-W. Lee, Peter M. Bainum and H.-D. Kim, "Development of scheduling algorithm and gui for the autonomous satellite mission operation," 60th International Astronautical Congress, Daejeon, Korea, Oct. 2009.
S.-W. Baek, K.-R. Cho, D.-W. Lee, Peter M. Bainum and H.-D. Kim, "Heuristic approach for satellite mission scheduling," Proc. of 19th AAS-AIAA Space Flgith Mechanics Meeting, Savannah, Georgia, U.S.A., Feb. 2009.
Oscar H. Ibarra and Chul E. Kim, "Fast approximation algorithms for the knapsack and sum of subset problems," Journal of the ACM (JACM), vol. 22, no. 4, 1975.
M. Hristakeva and D. Shrestha, "Different approaches to solve the 0/1 knapsack problem," Proc. of 38th Midwest Instruction and Computing Symposium, Apr. 2005.
M. Gendreau, "An introduction to tabu search," International Series in Operations Research and Management Science, vol. 57. Springer New York, 2003.
B.-S. Lee and J.-H. Kim, "Design and implementation of the mission planning functions for the KOMPSAT-2 mission control element," Journal of Astronomy and Space Science, vol. 20, no. 3, 2003, pp. 227-238.

원문보기 상세보기
D. E. Goldberg, Genetic Algorithms in search, Optimization and Machine Learning, 1st Ed., addison-wesley, MA, 1989.
D. Jong, "De Jong's sphere model test for a Social-Based Genetic Algorithm (SBGA)," IJCSNS, vol. 8, no. 3, pp. 179-185, 2008.
백승우, 한순미, 조겸래, 이대우, 김해동, "유전알고리즘을 이용한 전술위성 임무계획 스케줄링," 한국군사 과학기술학회, 종합학술대회 논문집, 2008.
한순미, 백승우, 조선영, 조겸래, 이대우, 김해동, "유전 알고리즘을 이용한 위성 임무 스케줄링 최적화," 한국항공우주학회지, 제36권 제12호, pp. 1163-1170, 2008.

원문보기 상세보기

저자의 다른 논문 :

LOADING...

표제어: 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

연합인증