[논문]기계학습을 이용한 파레토 프런티어의 생성

윤예분; 정나영; 윤민

doi:10.7465/jkdi.2013.24.3.495

기계학습을 이용한 파레토 프런티어의 생성
Generating of Pareto frontiers using machine learning 원문보기

Journal of the Korean Data & Information Science Society = 한국데이터정보과학회지, v.24 no.3, 2013년, pp.495 - 504

윤예분 (간사이대학교 환경 도시공학부) , 정나영 (부경대학교 통계학과) , 윤민 (부경대학교 통계학과)

초록
AI-Helper

진화 알고리즘 계산 지능을 이용한 예측 방법이 다목적 최적화 문제에서 많이 이용되고 있고, 이러한 방법들은 많은 근사 파레토 최적해들을 좀 더 정확하게 생성하기 위해서 개선되고 있다. 본 논문은 다목적 최적화 문제에서 서포트 벡터기계를 이용하여 근사 파레토 프런티어를 찾는 방법을 제안한다. 또한 제안된 방법과 진화 알고리즘을 결합한 것이 파레토 프런티어를 더 잘 근사시킨다는 것과 두 개혹은 세 개의 목적함수를 가진 의사결정은 제안된 방법으로 파레토 프런티어를 시각화한 것에 근거하여 더 쉽게 수행된다는 것을 보인다. 마지막으로 몇 개의 수치예제를 통해 제안된 방법의 효율성에 대해 보일 것이다.

Abstract ▼ AI-Helper

Evolutionary algorithms have been applied to multi-objective optimization problems by approximation methods using computational intelligence. Those methods have been improved gradually in order to generate more exactly many approximate Pareto optimal solutions. The paper introduces a new method using support vector machine to find an approximate Pareto frontier in multi-objective optimization problems. Moreover, this paper applies an evolutionary algorithm to the proposed method in order to generate more exactly approximate Pareto frontiers. Then a decision making with two or three objective functions can be easily performed on the basis of visualized Pareto frontiers by the proposed method. Finally, a few examples will be demonstrated for the effectiveness of the proposed method.

주제어

AI 본문요약
AI-Helper

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

문제 정의

하지만 많은 실제 공학 문제에 있어서, 블랙박스 목적함수의 형태들은 설계변수에 의해 정확하게 알 수 없으나, 이러한 함수값들은 표본의 실제적으로나 계산실험을 통하여 얻어진 값들로써 얻어지게 된다. 구조분석, 유체역학 그리고 열역학 등과 같은 여러 분야에서 목적함수들을 평가하기 위해 이용되었다. 일반적으로 이러한 분석은 비용이 많이들고 아주 긴 실행시간이 소요된다.

가설 설정

3. 검정용 문제 1과 2에 대하여, 파레토 최적해들은 실행 가능한 영역의 경계에 있다.
4. 검정용 문제 2와 4에서 실행가능한 영역은 설계공간에서 볼록하지 않다.
5. 검정용 문제 1의 파레토 프런티어는 볼록하지도 오목하지도 않다.

제안 방법

본 논문은 MOP들에서 서포트 벡터기계 (Hwang과 Shim, 2012; Sch¨olkopf 등, 2001; Steinwart와 Christmann, 2008)를 이용하여 근사 파레토 프런티어를 찾아내는 방법을 제안한다.
본 논문은 MOP에서 근사 파레토 프런티어를 얻기 위하여 서포트 벡터기계를 이용한 방법을 제안하였고 더 정확하게 근사된 파레토 프런티어를 생성하기 위해 제안된 방법에 진화 알고리즘을 적용했다. 또한, 몇 가지 검정용 문제들 및 실제 문제에 제안된 방법을 적용하고, 시뮬레이션 결과를 통하여 제안된 방법의 효율성을 보였다.
본 논문은 다음과 같이 구성되었다. 서포트 벡터기계와 MOP에 대해 간단히 설명하고 서포트 벡터기계를 이용한 다목적 최적화 방법을 제안한 후 제안된 방법을 인공적, 실제 예제에 적용시키고 마지막으로 결론을 내린다.
이 방법들은 다음의 두 단계를 반복적으로 수행함으로써 의사결정해들을 찾는다. 의사결정자의 목표수준 (aspiration level)에 가장 근접한 파레토 최적해를 얻기 위한 보조 최적화 문제를 해결하고, 트레이드-오프 (trade-off)분석으로 의사결정자의 목표수준을 수정한다.
이제, MOP에서 SVM을 적용하여 파레토 프런티어 생성하고, 잘 근사된 파레토 프런티어를 생성하기 위해 SVM과 진화 알고리즘 (Yun 등, 2001)을 결합하고자 한다. 특히, 제안된 알고리즘은 다음과 같이 요약된다 :
다음은, 몇 개의 검정용 예제들을 통하여 제안된 방법의 효율성을 보인다. 일반적으로 계산지능을 이용한 다목적 최적화 방법들의 대부분의 연구는 둘 혹은 세 개의 목적함수들을 가지는 문제에서 시행되고 있고, 본 연구에서는 두 개의 목적함수를 가지는 검정용 문제들을 다룬다.
진화 알고리즘을 사용하여 가능한 많은 실행가능한 자료점들을 만들고 실행 시간에 따라 자료점들은 실제 파레토 프런티어로 다가간다. 제안된 알고리즘을 적용한 SVM은 원래 입력 공간에 자료점들을 모두 포락 (envelopment)하는 영역을 제공한다. 각각 알고리즘의 최적을 활용하는 것은 효율적으로 수렴하고 빠르게 실제 파레토 프런티어에 다가간다.

성능/효과

2. 검정용 문제 3은 복잡한 제약식들을 가지지는 않지만 파레토 프런티어는 볼록하지 않고 연결되어 있지 않다.
본 논문은 MOP들에서 서포트 벡터기계 (Hwang과 Shim, 2012; Sch¨olkopf 등, 2001; Steinwart와 Christmann, 2008)를 이용하여 근사 파레토 프런티어를 찾아내는 방법을 제안한다. 나아가 제안된 방법과 진화 알고리즘을 결합한 것이 파레토 프런티어를 더 잘 근사시킨다는 사실과 두 개 또는 세 개의 목적함수를 가지는 의사결정의 문제에서 제안된 방법을 이용하는 것이 더 쉽게 수행된다는 것을 파레토 프런티어를 시각화한 것에 근거하여 보인다. 마지막으로 수치예제를 통해 제안된 방법의 효율성에 대해 보인다.
또한, 몇 가지 검정용 문제들 및 실제 문제에 제안된 방법을 적용하고, 시뮬레이션 결과를 통하여 제안된 방법의 효율성을 보였다. 따라서, 제안된 방법이 기존의 알고리즘들에서 필요한 실험횟수의 1/10에서 1/2로 줄일 것으로 예상한다. 실제 공학 설계문제들에서 가능하면 실험의 수는 1000 번(가능하다면 100 번) 이하가 바람직하다.
본 논문은 MOP에서 근사 파레토 프런티어를 얻기 위하여 서포트 벡터기계를 이용한 방법을 제안하였고 더 정확하게 근사된 파레토 프런티어를 생성하기 위해 제안된 방법에 진화 알고리즘을 적용했다. 또한, 몇 가지 검정용 문제들 및 실제 문제에 제안된 방법을 적용하고, 시뮬레이션 결과를 통하여 제안된 방법의 효율성을 보였다. 따라서, 제안된 방법이 기존의 알고리즘들에서 필요한 실험횟수의 1/10에서 1/2로 줄일 것으로 예상한다.
이런 관점에서 제안된 알고리즘은 기존의 방법보다 더 우수할 수 있다. 마지막으로 서포트 벡터기계와 진화 알고리즘을 결합한 제안된 방법이 좀 더 복잡한 형태의 목적함수들과 제약식들을 갖는 문제에서 잘 근사된 파레토 프런티어를 생성할 수 있다.
이러한 관점에서 제안된 방법은 이러한 어려움을 극복 할 수 있으며, 또한 100(자료) × 5(반복)의 작은표본실험 횟수 내에서 실제 파레토 프런티어와 거의 유사한 파레토 프런티어를 얻을 수 있으나 진화 알고리즘의 경우는 80(자료) × 30(반복)을 통해서 유사한 결과를 얻을 수 있었다.

후속연구

이번 절에서 제안된 방법의 효율성을 보이기 위해 실제 공학 설계문제에서 실험할 것이다. 많은 실제 적인 공학 문제에서 종종 설계변수들에 의해 정확하게 알려져 있지 않은 블랙박스 목적함수를 가지고 있다.

질의응답

핵심어	질문	논문에서 추출한 답변
	대다수의 의사결정 문제는 무엇으로 공식화 할 수 있는가?	많은 의사결정 문제는 다목적 최적화 문제 (multi-objective optimization problem; MOP)로 공식화 할 수 있다. 모든 목적함수를 동시에 최적화 시키는 해가 반드시 존재하는 것은 아니다.
	모든 목적함수를 동시에 최적화 시키는 해가 반드시 존재하지 않는 이유는?	모든 목적함수를 동시에 최적화 시키는 해가 반드시 존재하는 것은 아니다. 왜냐하면 다양한 목적이 서로 모순될 수 있기 때문이다. 그래서 파레토 최적해의 개념이 소개되었다.
	패턴인식 문제에서 자료가 선형분리가 되지 않는 경우 서포트 벡터 기계는 분류를 위해 무엇을 하는가?	반응변수가 두 개의 범주를 갖는 패턴인식 문제에서 자료가 선형분리가 되지 않는 경우, 서포트 벡터 기계는 원 자료를 어떤 비선형 사상에 의해 고차원의 특징공간 (feature space)으로 변환한다. 특징공간으로 사상된 자료는 선형 분리 가능하고 서포트 벡터기계는 입력 공간에서는 비선형 결정 경계를 가지는 자료를 최대 마진을 가지고 선형으로 분리하는 초평면을 찾는다.

참고문헌 (18)

Binh, T. T. and Korn, U. (1997). MOBES: A multiobjective evolution strategy for constrained optimization problems. Proceedings of the 3rd International Conference on Genetic Algorithms, 176-182.
Coello Coello, C. A., Van Veldhuizen, D. A. and Lamont, G. B. (2002). Evolutionary algorithms for solving multi-objective problems, Kluwer Academic Publishers, New York.
Deb, K. (2001). Multi-objective optimization using evolutionary algorithms, John & Wiley Sons, New York.
Deb, K., Ptratap, A. and Moitra, S. (2000). Mechanical component design for multiple objectives using elitist non-dominated sorting GA. Proceedings of the Parallel Problem Solving from Nature VI (PPSN-VI), 859-868.
Goldberg, D. E. (1989). Genetic algorithms in search, optimization and machine learning, Addison-Wesley, Boston.
Holland, J. H. (1975). Adaptation in natural and artificial systems, University of Michigan Press, Ann Arbor.
Hwang, C. and Shim, J. (2012). Mixed effects least squares support vector machine for survival data analysis. Journal of the Korean Data & Information Science Society, 23, 739-748.

원문보기 상세보기
Nakayama, H., Yun, Y. B. and Yoon, M. (2009). Sequential approximate multiobjective optimization using computational intelligence, Springer Verlag, Berlin Heidelberg.
Palli, N., Azram, S., McCluskey, P. and Sundararajan, R. (1998). An interactive multistage ${\epsilon}$ -inequality constraint method for multiple objectives decision making. ASME Journal of Mechanical Design, 120, 678-686.

상세보기
Park, D. J., Yun, Y. B. and Yoon, M. (2012). Prediction of bankruptcy data using machine learning techniques. Journal of the Korean Data & Information Science Society, 23, 569-577.

원문보기 상세보기
Poles, S. (2003). MOGA-II An improved multi-objective genetic algorithm, Esteco Achieving Perfection Technical Report 2003-006, 1-14.
Sawaragi, Y., Nakayama, H. and Tanino, T. (1985). Theory of multiobjective optimization, Academic Press Inc., Boston.
Scholkopf, B., Platt, J. C., Shawe-Taylor, J., Smola, A. J. and Williamson, R. (2001). Estimating the support of a high-dimensional distribution. Neural Computation, 13, 1443-1471.

상세보기
Scholkopf, B. and Smola, A. J. (2002). Learning with kernels, MIT Press, New York.
Seok, K. H. (2010). Semi-supervised classification with LS-SVM formulation. Journal of the Korean Data & Information Science Society, 21, 461-470.
Steinwart, I. and Christmann, A. (2008). Support vector machines, Springer, New York.
Vapnik, V. N. (1995). The nature of statistical learning theory, Springer Verlag, New York.
Yun, Y. B., Nakayama, H., Tanino, T. and Arakawa, M. (2001). Generation of efficient frontiers in multi-objective optimization problems by generalized data envelopment analysis. European Journal of Operational Research, 129, 586-595.

상세보기

저자의 다른 논문 :

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

연합인증