Sorting-based Techniques for Pareto-dominance based Multi-objective Optimization = 파레토 지배순위 기반 다목적 함수 최적화에 대한 정렬 기반 기법
저자
발행사항
대구 : Kyungpook National university, School of Electronics Engineering, The Graduate School, 2017
학위논문사항
학위논문(석사)-- Kyungpook National university, School of Electronics Engineering, The Graduate School : 전자공학부 2017. 8
발행연도
2017
작성언어
영어
주제어
발행국(도시)
대구
형태사항
iii, 53 p. ; 26 cm
일반주기명
지도교수: 말리페디람모한
소장기관
실세계 최적화 문제의 대부분은 다목적 함수 최적화 문제 (Multi-Objective optimization problems, MOPs)라고 불리는 수많은 모순된 목표와 관련이 있다. 목적 함수의 상충되는 특성으로 인해, 모든 목표에서 가장 좋은 단일 최적 솔루션을 얻는 것이 MOPs에서는 불가능하다. MOPs에서의 목적은 파레토-최적 해법 (Pareto-optimal solutions)으로 불리는 비지배적인 해의 집합을 얻는 것이다. 파레토-최적 해법들을 포함하는 표면을 파레토 전면(Pareto front)이라 부른다.
문헌에서 MOPs를 해결하기 위해 다양한 알고리즘이 제안되었다. 제안된 여러 가지 알고리즘들 중에서, 진화 알고리즘은 파레토 최적 솔루션 집합을 찾는 MOPs에서 가장 널리 사용되고 있다. 즉, NSGA, NSGA-II, SPEA2, MOEA / D, PESA-II 등 다양한 다목적 함수 진화 알고리즘 (MOEAs)이 제안되었다.
모든 MOEAs의 두 가지 주요 목표는 다음과 같다. a) 융합 (실제 파레토 최적의 전면에 도달), b) 다양성 (파레토 최적의 전면에 속하는 솔루션 간분리를 최대화). 여러 가지 MOEAs 중 파레토-지배 순위(Pareto-dominance rank)를 기반으로 하는 솔루션의 품질을 비교할 때, 파레토 지배 기반 접근 방식이 가장 널리 사용된다.
파레토 우세 기반 MOEAs의 주요 쟁점은 다음과 같다 : a) 비 지배 정렬의 계산 복잡성; b) 목적 함수가 4보다 크거나 같은 문제에서 융합도가 낮아지는 경우 (많은 목적 함수 최적화 문제라고 함).
비지배적 정렬(Non-dominated sorting, NDS)은 솔루션이 지배력 관계에 따라 다른 전면에 할당되는 절차로 정의된다. 일반적으로, NDS는 계산 비용이 많기 때문에, 효율적인 여러 방법들이 제안되었다. 본 논문은 기존의 정렬 알고리즘을 사용하여 NDS의 계산 복잡도를 최소화하는 방법을 제시한다.
목표가 증가함에 따라 많은 목표 최적화 문제 (Many Objective Optimization Problems, MaOPs)에서솔루션 간 파레토 우위 관계가 점차 사라지고, 선택 압력이 진정한 파레토 전면 방향으로 감소합니다. 이러한 우려를 극복하기 위해 문헌에서 사용된 보편적 인 방법들은 a) 기존의 파레토 지배 관계를 수정하거나, b) 보조 선택 기준으로 추가 선택 기준을 채택하였으며, c) 일부 성과 지표에 기반한 새로운 선택 기준을 개발하기도 하였다.
이 논문에서 우리는 MaOPs에서 MOEAs의 수렴을 개선하기위해 새로운 추가 선택 기준을 제안한다. 제안된 2차 선택 기준은 각 솔루션의 평균 순위에 기반한 방법이다. 2차 기준에 따라, 동일한 파레토 프론트에 속한 솔루션 집합을 솔루션들의 평균 순위와 다양성에 기반하여 각기 다른 그룹으로 분리할 수 있다.
Most of the real-world optimization problems are associated with numerous contradictory objectives, termed as the Multi-Objective optimization problems (MOPs). Due to the conflicting nature of the objectives, obtaining a single optimal solution that is best in all the objectives is not possible in (MOPs). In other words, in MOPs the aim is obtain a set of solutions which are nondominated with each other referred to as Pareto-optimal solutions. The surface that contains the Pareto-optimal solutions is termed as the Pareto front.
In literature, various algorithms have been proposed to solve MOPs. Among the different methods proposed evolutionary algorithms are most popular in multi-objective optimization as they find the set of Pareto-optimal solutions in a single run. In literature, various Multi-objective Evolutionary Algorithms (MOEAs) such as NSGA, NSGA-II, SPEA2, MOEA/D, PESA-II etc. haven been proposed in the past few decades.
When solving MOPs, the two main goals of any MOEAs are: a) Convergence (to reach the true Pareto-optimal front); and b) Diversity (to maximize the separation between solutions over the Pareto-optimal front). Among the different MOEAs, Pareto-dominance based approaches are most popular as they compare the quality of the solutions based on their Pareto-dominance rank.
The main issues in Pareto-dominance based MOEAs are: a) computational complexity of non-domination sorting; and b) poor convergence in problems where the number of objectives are greater than or equal to four (referred to as Many Objective optimization problems).
Non-dominated sorting (NDS) can be defined as the procedure in which the solutions are assigned to different fronts depending on their dominance relations. In general, NDS is computational expensive and various computationally efficient methods have been proposed. In this thesis, we present a method to minimize the computational complexity of NDS by using conventional sorting algorithms.
In Many Objective Optimization Problems (MaOPs) as the objectives increases, the Pareto-dominance relationship between the solutions vanishes gradually and decreases the selection pressure towards true Pareto Front. To overcome these concerns, most popular techniques employed in the literature are: a) to modify the existing the Pareto-dominance relation, b) to adopt an additional selection metrics as secondary selection criteria, c) to develop a new selection criteria based on the some performance indicators.
In this thesis, we propose an additional selection metric to improve the convergence of MOEAs on MaOPs. The proposed secondary selection criterion is based on the average rank of each solution. Based on the secondary criteria, set of solutions that belong to the same Pareto-front can be segregated into different groups where is each group is assigned a priority based on their average rank and diversity.
서지정보 내보내기(Export)
닫기소장기관 정보
닫기권호소장정보
닫기오류접수
닫기오류 접수 확인
닫기음성서비스 신청
닫기음성서비스 신청 확인
닫기이용약관
닫기학술연구정보서비스 이용약관 (2017년 1월 1일 ~ 현재 적용)
학술연구정보서비스(이하 RISS)는 정보주체의 자유와 권리 보호를 위해 「개인정보 보호법」 및 관계 법령이 정한 바를 준수하여, 적법하게 개인정보를 처리하고 안전하게 관리하고 있습니다. 이에 「개인정보 보호법」 제30조에 따라 정보주체에게 개인정보 처리에 관한 절차 및 기준을 안내하고, 이와 관련한 고충을 신속하고 원활하게 처리할 수 있도록 하기 위하여 다음과 같이 개인정보 처리방침을 수립·공개합니다.
주요 개인정보 처리 표시(라벨링)
목 차
3년
또는 회원탈퇴시까지5년
(「전자상거래 등에서의 소비자보호에 관한3년
(「전자상거래 등에서의 소비자보호에 관한2년
이상(개인정보보호위원회 : 개인정보의 안전성 확보조치 기준)개인정보파일의 명칭 | 운영근거 / 처리목적 | 개인정보파일에 기록되는 개인정보의 항목 | 보유기간 | |
---|---|---|---|---|
학술연구정보서비스 이용자 가입정보 파일 | 한국교육학술정보원법 | 필수 | ID, 비밀번호, 성명, 생년월일, 신분(직업구분), 이메일, 소속분야, 웹진메일 수신동의 여부 | 3년 또는 탈퇴시 |
선택 | 소속기관명, 소속도서관명, 학과/부서명, 학번/직원번호, 휴대전화, 주소 |
구분 | 담당자 | 연락처 |
---|---|---|
KERIS 개인정보 보호책임자 | 정보보호본부 김태우 | - 이메일 : lsy@keris.or.kr - 전화번호 : 053-714-0439 - 팩스번호 : 053-714-0195 |
KERIS 개인정보 보호담당자 | 개인정보보호부 이상엽 | |
RISS 개인정보 보호책임자 | 대학학술본부 장금연 | - 이메일 : giltizen@keris.or.kr - 전화번호 : 053-714-0149 - 팩스번호 : 053-714-0194 |
RISS 개인정보 보호담당자 | 학술진흥부 길원진 |
자동로그아웃 안내
닫기인증오류 안내
닫기귀하께서는 휴면계정 전환 후 1년동안 회원정보 수집 및 이용에 대한
재동의를 하지 않으신 관계로 개인정보가 삭제되었습니다.
(참조 : RISS 이용약관 및 개인정보처리방침)
신규회원으로 가입하여 이용 부탁 드리며, 추가 문의는 고객센터로 연락 바랍니다.
- 기존 아이디 재사용 불가
휴면계정 안내
RISS는 [표준개인정보 보호지침]에 따라 2년을 주기로 개인정보 수집·이용에 관하여 (재)동의를 받고 있으며, (재)동의를 하지 않을 경우, 휴면계정으로 전환됩니다.
(※ 휴면계정은 원문이용 및 복사/대출 서비스를 이용할 수 없습니다.)
휴면계정으로 전환된 후 1년간 회원정보 수집·이용에 대한 재동의를 하지 않을 경우, RISS에서 자동탈퇴 및 개인정보가 삭제처리 됩니다.
고객센터 1599-3122
ARS번호+1번(회원가입 및 정보수정)