카테고리 없음2010. 7. 30. 13:11

어.. 갑자기 이노래가 땡긴다. 새기타도 하나 샀는데 이거 한번 연습해서 연주를 때려야 겠다. 

하우젠 버블 광고 나올 때는 몰랐는데.. 이게 윈터플레이가 연주한 곡이었군.
Posted by 태씽
CSE(컴퓨터 공학)2010. 7. 26. 18:23
nadir (어떤 순간에서) 최악의 상황, 바닥
nadir point


1. Introduction
 

Multi-objective optimization 과정에서 nadir objective vector라는 것을 추정하는 것이 중요한 task중에 하나 이다. nadir objective vector는 전체 Pareto-optimal set에 상응하는 각 objective value의 가장 나쁜값을 나타낸다. 때때로, 이 point가 전체 search space에서 가장 나쁜 objective value값을 나타내는 point와 혼동이 될 수 있다. 이런점이 때로는 nadir objective vector에 over-estimation이 될 수 있는것이다. 이상적인(혹은 알맞은) objective vector와 함께 (point는 각 objective의 가장 좋은 값에 의해 구성된다), nadir objective vector는 normalize objective function으로 이용이된다. 문제(matter)는 때때로 multiobjective optimization algorithm의 충분한(적절한) functioning을 이상적이게 여기게 된다. 이들 두가지의 extreme value와 함께 objective function은 크기를 변화할 수 있고 그러므로 각 scaled objective는 같은 범위내에서 값을 좀더 또는 덜 가질 수 있다. 이들 scaled value는 weighted-sum approach나 Tchebycheff metric method와 같이 다른 알고리즘과 함께 optimization을 할때 이용할 수 있다. 이런 scaling procedure는 문제를 해결하는 속도를 증가시켜서 computational cost를 줄일 수 있다.  objective function vlaue들을 normalize하는것 말고도, nadir objective vector는 또한 guess method 와 다른것들 같이 서로다른 interactive 알고리즘을 이용해서 Pareto-optimal solution들을 찾는데 이용할 수 있다. 이들 방법의 일반적인 아이디어는 nadir objective vector로 부터 minimum weighted deviation을 최대화하는 것이다. 더욱이 nadir의 knowledge와 이상적인 objective value는 decision maker에 게있어서 각 objective의 범위를 알게 함으로서 실제 level에 대한 그들의 예상(기대)을 조절할 수 있게 도와주고 그러면 실제 이상적인 지역으로 집중하게 할 수 있다. 더욱이 Pareto-optimal solution들을 시각화 하는데에 있어서 nadir objective vector에 대한 지식은 필수적이다. 이상적인 point와 함께, nadir point는 각 objective의 범위를 제공해주고 value path나 bar chart, petal diagram같은 것으로 시각화 할 수 있다. 

nadir point를 추정하는것이 Pareto optimal frontier 전체에 대한 정보를 필요로 하기 때문에 이 point를 추정하는 어떤 procedure이든지 Pareto-optimal solution들을 찾을 수 있는 과정이 필요로 하다. 이것은 ideal point를 찾는것과 비교해서 task를 더 어렵게 만든다. ideal point란 전체 search space를 통틀어서 가장 좋은 objective value들을 이야기하는 것이다. evolutionary multi-objective optimization (EMO) 알고리즘이 Pareto optimal frontier 전체를 찾으려고 시도를 하기 때문에 EMO 는 이런 작업(nadir point를 추정하는 작업)을 하는데 가능한 후보가 될 수 있다. 하지만 nadir objective vector의 추정에는 중간의 Pareto-optimal solution을 찾는 과정을 포함할 필요는 없다. 오직 extreme solution이 필요할 뿐이다. 이 논문에서는 extreme Pareto-optimal solution을 강조하기 위해서  2가지 존재하는 EMO(elist non-dominated sorting GA or NSGA-II)의 수정방안을 제안할 것이다. 그렇게 함으로써 nadir point를 추정할 것이다. 시뮬레이션 결과는 20개의 objective(EMO에서는 거의 시도하지 않는) optimization problem에서 두가지 approach중 하나-the extremized crowded NSGA-II-가 원래 NSGA-II보다 빠르고 신뢰성이 있게 nadir point를 찾을 수 있게 하는것을 입증할것이다. 


2. NADIR OBJECTIVE VECTOR

Multi-objective optimization problem들은 여러가지 서로 대립하는 objective들을 수반하고 있고 이론적으로 Pareto-optimal solution들의 set이 생기게 한다. 이것은 objective간 trade-off를 제공한다. 2개의 objective의 minimization problem를 고려해보자. Figure1에 나타나 있다.
nadir objective vector를 계산하기 위해서 f1, f2 들이 개별적으로 최대화되었을때, 각자 A와 B라는 포인트가 나올 수 있다. 이들 두가지 point가 extreme point zw라는것을 만든다. (그림에서는 Worst objective vector라고 나와 있다.) 이것은 실제 nadir point가 아니다. nadir point라는것은 모든 Pareto-optimal solution들 사이에서 가장나쁜 objective value들을 이용해서 만들어지는것이지, 전체 search space상에서 가장 나쁜 objective value들로 만들어 지는것이 아니다. 그러므로 nadir point를 찾기 위해서는, nadir point를 찾기위한 solution들의 Pareto-optimality를 알 수 있어야 한다. 이것이 nadir point를 찾는것을 보다 어렵게 만든다.

3. Existing Methods
이런 어려움을 극복하기 위해서, 여러가지 method들이 제안되었다. Benayoun et al. [1]-Linear programming with multiple objective functions: Step method (STEM). Mathematical Programming, -은 처음으로 interactive multi-objective optimization method를 소개했다. (저자가 nadir 이라는 용어를 쓰지는 않았지만) 이것은 nadir point를 추정하기 위해서 payoff table이라는 method를 이용을 했다. 이 method에서는 어떤 table이 구성이 된다. 그 테이블은 i번째 objective가 최소인 point에서 다른 모든 objective function의 값이 계산된 값이 table의 i번째 행으로 구성이 된다. 그런 다음에 i번째 열의 최대값은 i번째 objective의 upper bound의 추정값으로 할 수 있고 이들 최대값들은 함께 nadir vector를 구성하는데에 이용이 된다. 이런 접근방식에서 주로 문제가 되는것은 어떤 objective의 minimum solution에 상응하는것이 다른 objective에 서로 다른 값에 따라 하나 이상은 존재하게 되는 것이다. 특히 문제가 2개이상의 objective를 가질때 이야기이다. Figure2에 있는 전형적인 3개의 objective에 대한 Pareto-optimal front를 한번 살펴보자.
첫번째 objective function의 minimum value는 f1 = 0 일 때이다.  그림에서 봐서 알 수 있듯이 f1=0일 떄 f2와 f3이 각각 서로 다른 값을가지게 되는 수많은 solution들이 존재를 한다. (선 BC라인에 있는 모든 솔루션들이 그러하다.) payoff table method에 의해서, 다음의 세가지 solution이 나타날 수 있다. f(1) = (0, 0, 1)T => point C, f(2) = (1, 0, 0)T => Point A, f(3) = (0, 1, 0)T(point B), 즉 nadir point, znad = (1, 1, 1)T로 나타낼 수 있다. 하지만 solutions이  f(1) = (0, 0.2, 0.8)T, f(2) = (0.5, 0, 0.5)T 그리고 f(3) = (0.7, 0.3. 0)T (이것은 그림에서 하얀 동그라미로 표시가 되어있다) 와 같이 f1, f2, f3가 각각 minimization 되는 해를 찾았다면 이것의 nadir point는 z' = (0.7, 0.3, 0.8)T로 나타낼 수 있을것이다. 이 그림에서 잘못된 nadir point는 오직 Pareto-optimal front의 부분에서만 나타난다는것을 보여주고 있다. 

후에 Iserman 과 Steuer [9] - Computational experience concerning payoff tables and minimum criterion values over the efficient set - 에서는 linear problem 조차도 nadir point를 찾는데 어려움이 있다는 것을 증명했고 payoff table 보다 더 나은 method를 이용해야 한다고 강조를 했다. Dessouky et al. [7] - Estimates of the minimum nondominated criterion values in multiple-criteria decision-making.- 에서는 3가지의 heuristic method를 제안했고 Korhene et al. [10] - A heuristic for estimating nadir criterion values in multiple objective linear programming.- 에서는 nadir point를 찾기 위해서 또다른 method를 제안했다. 중요한 것은 이들 method 모두가 모든 objective들과 constraint들이 linear function인 multi-objective linear problem들을 위해서 제안 되었다는 것이다.

Ehrgott 와 Tenfelde-Podehl [8] - Computation of ideal and nadir values and implications for their use in MCDM
methods.
 - 에서는 subproblem에 기반을 둔 알고리즘을 제안했다. 즉, M-objective problem에서 nadir point를 찾기 위해서더 낮은 dimensional problem의 Pareto-optimal solution들을 이용했다. 이런 요구사항이 알고리즘을 objective가 3개 이상일 때는  계산적으로 실현 불가능하게 할수 도 있다. 더욱이 저자는 nonlinear problem에 대해서 확장할 수 있는 알고리즘을제안하지않았다. 비록 nadir point를 찾는것이 Pareto-optimal solution들의 set에서 가장 나쁜  objective value를 찾는 것이고, 이것이 linear problem에 적용하는 것이라 할 지라도 이것은 반드시 다루어져야 하는 내용이다. 이것은 또 한 매우 어려운 task이다. 

4. Evolutionary Approach
nadir point를 결정하는 것은 Pareto-optimal solution들과 관련이 있다 그 때문에 Pareto-optimal set의 결정에 대한 힌트를 주는것은 nadir point를 추정하는 것을 가능하게 한다. 과거 십수년전에는 EMO 알고리즘은 그들의 multiple, wide spread 한 Pareto-optimal solution들을 한번의 simulation run동안에 동시에 찾을 수 있는 기능에 인기를 얻었다. 그들 알고리즘이 Pareto-optimal solution들의 set을 찾는것이기 때문에, EMO procedure는 nadir objective vector를 찾기 위한 이상적인 방법이라고 할 수 있다. 하지만 먼저 Pareto-optimal set을 찾고 다음에 set에서 nadir objective vector를 찾는  naive procedure는 딜레마를 야기시키는 듯 하다. 자 여기서 nadir objective vector의 목적에 대해서 상기시켜 보자. 그것은 objective들을 normalize해서 interactive multi-objective optimization algorithm을 이용해서 이상적인 Pareto-optimal solution을 찾는것이다. 하지만 EMO가 대표적인 Pareto-optimal set을 찾는데 사용이 된다면 nadir point를 찾을 이유가 더 이상 없다는 것이다. 상호적인 의미에서는 EMO procedure의 application은  Pareto-optimal set의 본질에 대한 idea를 제공해줄 수 있고 차후에 이상적인 Pareto-optimal 지역을 위한 EMO procedure가 nadir point 기반을 한 interactive method들과 같다고 정할 수 있을것이다. 

하지만 EMO procedure들은 그들의 작업 원칙에서 Pareto-dominace의 concept를 이용하고 많은 수의 objective들(5개 이상)을 다루는데 있어서는 그것의 비효율성으로 많은 비판을 받아왔다. high-dimensional Pareto-optimal front를 나타내기 위해서는 exoponential 한 큰 수가의 point가 필요하다. 이것이 EMO procedure가 first place에서 완벽한 Pareto-optimal front를 찾을 수 없게 한다. 그러므로, 많은 수의 objective에서 Pareto-optimal front를 찾고 이상적인 지역을 강조하기 위해서 두개의 갈라진(pronged) EMO procedure를 이용하는것은 별로 장점이 없다. 대신에 EMO procedure가 하나의 application에서 이 두가지 작업을 동시에 수행하도록 이용할 수 있을 것이고 이 과정에서 main focus는 Pareto-optima set의 지역으로 population을 퍼트리는것이다. 그리고 이 Pareto-optima set은 nadir point를 올바르게 구축할 것이다. 그림 2에서 3개의 objective의 minimization problem에서 제안한 EMO procedure는 그것의 population member들을 전체의 Pareto-optimal set 대신에  A,B,C 지역 근처에 퍼트려야 한다. 그렇게 해서 nadir point가 빠르게 발견될 수 있다. 다음 section에서는 우리는 이를 위한 2가지 EMO procedure에 대해서 알아볼 것이다.

5. Elitist Non-dominated Sorting Genetic Algorithm (NSGA-II)
제안방안 두가지 다 NSGA-II를 이용할 것이다. 이 알고리즘은 최근에 매우 각광을 받고 있는데, 그 이유는 그것의 간단하고 계산적으로도 매우 빠르며 source code의 이용가능성에 있다고 할 수 있다. 

5.1 NSGA-II Crowding Distance Calculation
multi-objective optimization problem의 주된 목적 중 하나는 front에 따라 diversity를 유지하는 것이다. diversity를 보존하기 위해서 non-dominated front에서 solution의 density(밀도) 측정할 수 있어야 한다. 가장 간단한 방법으로는 solution 간의 Euclidean distance를 계산해서 clustering 하는것이다. 하지만 계산량이 엄청나게 많아진다. 그래서 NSGA-II에서는 매우 빠른 계산 방법을 이용한다. Crowding distance는 어떤 솔루션 i의 두개의 이웃 solution 사이의 objective-wise normalize distance를 구한다. extreme solution들의 경우에는 임의로 엄청나게 큰 수를 할당해준다. 그리고 나서 솔루션들은  crowding distance 높은 순으로 정렬을 정렬된 순서되로 필요한 수만큼 선택이 되는 구조이다. 

6. Modifications To NSGA-II
NSGA-II가 non-dominated front의 extreme solution들에 대한 중요성을 제공하기는 하지만 주로 강조하는것은 전체 front에서 솔루션들의 diversity를 좋게 유지하는것이다. 하지만 위에서 이야기 했었듯이 nadir point를 찾기위해서는 nondominated-fornt에서의 extreme solution들 사이에서 NSGA-II population member을 퍼뜨려야 한다. 그러므로 계산적으로 효율적으로 nadir point를 찾기위해서 기존 NSGA-II 보다 더  extreme non-dominated solution들 근처를 강조하는 효율적인 방법을 이용해야 한다. 이런 concept를 구현하기 위해서 crowding distance calculation이 수정되어야 한다. 

6.1 Worst Crowded NSGA-II 
Pareto-optimal solution들에 대한 가장 나쁜 objective value들이 nadir point를 구성하므로 우리는 front-wise에 가장 나쁜 objective value를 강조한다. 특정 front에 있는 solution은 먼저 각 objective에 기반으로 minimum으로 부터 maximum까지로 정렬이 되고(minimization problem일때) 정렬된 리스트 내에서 솔루션의 위치가 rank(순위)가 된다. 그런 다음에 가장 큰 랭크가 솔루션에 assign된다. 이것은 crowding distance measure에 로 모든  objective가 선언되었기 때문이다. 이런 방식으로 어떤 objective의 가장 큰 objective value가 가장 큰 crowded distance를 가지게 된다. NSGA-II procedure가 non-dominated solution들을 강조하고 crowding distance value가 더 큰 솔루션들을 선호하기 때문에, 모든 fornt에서 모든 가장 나쁜 objective value들은 강조되어야 한다. 그렇게 함으로써 nadir point를 구하는 것에 도움이 될 수 있다. 

6.2 Extremized Crowded NSGA-II
하지만, 이런 가장 나쁜 objective solutions front-wise에 대해서만 강조를 하는것은 적어도 두가지 어려움이 생기게 된다 
(i) 각각의 가장 나쁜 objective vector 근처의 subpopulation 에서 diversity를 유지하기 어렵고(이로 인해 sub-optimal solution으로의 이른 수렴이 발생 할 수도 있다.) (ii) 가장 나쁜 objective vector들의 individual에 해당하는 솔루션 단독으로 는 많은 수의 non-Pareto-optimal solution을 dominate 할 수 없을 것이다. 그것 때문에 원하지 않은 솔루션과 함께 non dominated front를 찾을 수 있다. 이와같은 front는 nadir point를 잘못 추측하게 만들 수 있다. 이런 두가지 가능성을 피하기 위해서 다른 crowding distance measure를 제안한다. 특정 front의 solution들은 각 objective에 대해서 최대부터 최소의 순으로 정렬을 한다. 솔루션이 각 extreme objective vector에 가까워 질 수록(minimum or maximum objective values) 중간에 있는 솔루션들 보다 좋은 높은 랭크를 받을 것이다. 그러므로 모든 objective에 대한 2개의 extreme solution들은 N'(front에서 솔루션의 수)라는 rank를 부여 받을 것이다. extreme solution들 다음에 있는 솔루션은 N'-1의 랭크를 받게 되는것이다. 그림 3은 이 rank assignment procedure를 보여줘고 있다. 
각 objective 에 대한 솔루션에 랭크가 부여가 되면 할당된 rank의 최대값은 crowding distance로서 선언 crowding distance value들은 그림에서 괄호 내의 값으로 보여 지고 있다. 이 procedure는 각 objective에 대해서 extreme solution들을 강조(minimum과 maximum) extreme solution들에 대해서 가까운 솔루션을 강조할 수 있는 계층구조를 만들어 낸다. 

one-dimensional Pareto-optimal front를 가지는 2개의 objective 문제와 그 이상의 objective 문제에 대해서(즉, M-2 redundant objective들을 가지는 M-objective 문제), 이 crowding distance assignment는 worst crowding distance assignment scheme과 유사할 것이다. (하나의 objective의 minimum rank solution이 다른 하나의 objective의 maximum rank solution이 되는) 하지만 large-dimensional Pareto-optimal hyper-surface, 를 가지는 문제에 대해서는 extremized crowding 은 worst crowding scheme과 다르다. 그림 2에서의 3개의 objective에 대한 문제에서 extremized crowding scheme은 오로지 A, B, C만 강조하지 않고 선, AB, BC, CA와 그들 근처에 있는 솔루션들을 강조할 것이다. 이렇게 되면 두가지의 장점이 생긴다 : (i) solution들의 좋은 diversity가 유지가 될 것이고 그것 때문에 좀 더 좋은 솔루션을 찾기 위한 genetic operator들이 가능해질 것이다.(crossover, mutation같은) 그리고 너무 이른 수렴이 발생하지 않을것이고 이들 솔루션들의 존재는 겉으로만 그럴싸한 non-Pareto-optimal 솔루션들을 가질 기회도 없어진다는 이야기가 된다. 더욱이 Pareto-optimal 지역에서 중간 지역의 대해서 강조가 되지 않기 때문에 실제 original NSGA-II 알고리즘에 보다 extreme solution들을 빠르게 찾을 수 있다. 특히 많은 objective들을 가지는 문제에서 말이다. 

6.3 VEGA Based Approach
신중하게 생각하보면 위에서 봤던 worst crowding distance calculation method는 다른 multi-objective GA와 유사하다, 잘알려진 VEGA(vector evaluated GA)이다. 이 approach에서, GA population은 각 세대에서 objective function의 수와 같은 더 작은 그룹으로 세분화 된다. 첫번째 그룹에 있는 individual들은 first objective를 기반으로 reproduce되고 두번째 그룹은 두번째 objective를 기반으로, 이런 식으로 재생산을 한다. VEGA의 selection operator는 각 group에 대해서 제한적이지만 crossover 라든지 mutation operator같은 경우는 전체 space에서 적용 가능하다. selective search가 subpopulation대해서 각 objective에 독립적이기 때문에 각 objective에 대해서 더 좋은 값을 가지는 individual들이 강조가 된다. VEGA가 Pareto-optimal front에서 extreme solution 으로 수렴하는 성향을 가지고 있지만 domination check 나 explicit diversity-preserving mechanism(NSGA-II 처럼)이 없다. 이 연구에서 우리는 nadir point를 추정하기 위해서 VEGA approach를 evaluate해볼 것이고 original NSGA-II와 두가지의 제안된 NSGA-II의 수정방안을 비교해 볼 것이다.


'CSE(컴퓨터 공학)' 카테고리의 다른 글

[HCI] Evaluation techniques  (0) 2010.04.14
Posted by 태씽
잡담2010. 7. 26. 17:57
모토로이를 질렀다... 난 원래 기기를 성격상 가지고 있으면 써야 되기 때문에 3개나 가지고 있는다는건 상당히 부담이 되는 상황이었다. 물론 금전적인 측면도 무시못하지만.. 어찌되었든 그래서 엑페를 과감하게 초기화하고 팔려고 마음을 먹고 오늘 해지를 하러갔는데, 결론은 "기존회선 묶이셨네요. 고객님.^^;;" 이란다ㅜ 으억.. 9월 28일까지 해지도 못하고 그 많이 깔아놨던 어플들은 또 어쩌냐... 사실 엑페가 할 수 있었던거는 모토로이가 다 할 수 있다. 쿼티 빼고. 그러므로 결론은 그냥 서랍행 or 실험용... 뭔가 잼나는게 나오면 그걸로 실험이나 좀 해야겠다. 지금은 모토로이 샀으니까 모토로이에 집중해줘야지. 데이터요금제까지 신청해서 사용할것인디 말이여.. 생각해보면 이제 오즈라는것이 많이 실용성이 떨어지는듯.. 이번달까지만 편의점 캐쉬 다 쓰고 이제 오즈는 해지 하고 SKT데이터 요금으로 가자. 아레나는 단순 전화 문자용, 모토로이는 SNS, 인터넷, 게임용.  이런 체제로 한동안 가야지.

2010/7/27(화)
내가 마이너스의 손이란 말인가???ㅡ.ㅡ;;; 내가 사자말자 24/7이 뜨네.ㄷㄷㄷ 으어 해지도 못하고 이게 뭐야!!! 버럭버럭!!!!!!!!뭐 질렀으니 어쩔 수 없고.. 엑페 관련으로 좀 기발한게 생각이 나서 이야기를 해보면 .. 일단은 엑페를 동생걸로 유심기변을 하자. 그러면 내가 현재 가지고 있는 엑스페리아는 팔 수 있다. 이렇게 해서 그냥 2개월 있다가 파는거지.. 집에 너무 기기가 많으면 대략 좋지 않으니 그렇게 하도록하자. 일단 세미나가 중요하니 세미나 부터 해결을 좀 할 수 있도록 하고.

Posted by 태씽