Theory/Algorithms (35) 썸네일형 리스트형 Multi-Objective 최적화 (3) - NSGA-3 Multi-Objective 최적화 (1) - 파레토 (pareto) 최적 Multi-Objective 최적화 (2) - NSGA-2 NSGA (Non-dominated Sorting Genetic Algorithm)의 종류는 여러 가지가 있으나 각 샘플 별 $n_p, S_p$를 계산하여 파레토 front level 순으로 정렬하는 Non-dominated Sorting은 동일합니다. NSGA-3 알고리즘은 NSGA-2의 같은 front level에 속한 샘플들을 가려내던 crowding distance를 reference direction으로 바꾼 알고리즘입니다. Reference direction Reference direction은 $M$개의 목적함수에 대해 다음 조건을 만족하는 $w_i$의 집합입.. Multi-Objective 최적화 (2) - NSGA-2 Multi-Objective 최적화 (1) - 파레토 (pareto) 최적 Multi-Objective 최적화는 결국 전체 solution 중에 파레토 최적인 solution 집합을 찾는 문제입니다. 먼저 문제를 단순화하여 여러 개의 목적을 하나의 목적으로 단순화하는 방법은 없을까요? 지난 포스트에서 봤던 일반적인 최적화 수식을 생각해 본다면 다음처럼 1) 특정한 목적 함수만 남기고 나머지 목적 함수를 constaint 조건으로 보내거나 ($\epsilon$ constrained), 2) 여러 목적 함수의 가중치 합으로 하나의 목적 함수로 표현하는 것이 가능하겠죠. (weighted sum) 하지만 이 방법들의 문제점은 각 목적 함수 별로의 가중치 $w_m$나 제한 조건 $\epsilon$을 정하기 쉽지.. Multi-Objective 최적화 (1) - 파레토 (pareto) 최적 최적화란 기본적으로 주어진 목적함수를 최소화 혹은 최대화시키는 입력을 찾는 과정입니다. 한정된 자원에서의 최대 효율을 달성해야 하는 상황은 공학, 자연과학 분야뿐 아니라 실생활에서도 광범위하게 존재하기에 유관한 대부분의 학과에서 접하게 됩니다. 대표적으로 유전 알고리즘 (Genetic Algorithm), Particla Swarm Optimization, Simulated Annealing, Differential Evolution 등 다양한 meta-heuristic 알고리즘들이 있죠. 주어진 목적이 하나라면 다른 것을 희생시킬 필요가 없기에 간단하지만 한정된 자원에서 두 가지 이상 목적을 충족하려면 어떻게 해야 할까요? 수학적으로 표현하면 다음 $M$개의 목적을 동시에 만족시키고 싶은 겁니다. 파레.. 자료구조 - 해시 함수와 엔트로피 해시 함수 파이썬의 객체는 이미 __hash__, __cmp__ 함수를 구현하므로 일반적으로 해시가 가능합니다. int나 float 같은 산술 타입은 수의 bit를 기반으로 해시값을 구하고 튜플과 문자열은 내용을 기반으로 해시값을 구합니다. 다만, 리스트는 값과 크기가 변경될 수 있으므로 해시를 지원하지 않습니다. (리스트의 값이 변경되면 리스트를 나타내는 해시값이 엉뚱한 색인을 참조할 수 있기에 사전의 키로 사용할 수 없습니다) 사용자 정의 클래스에서는 어떨까요? 기본 __hash__ 함수는 내장 함수인 id 함수를 이용해서 객체의 메모리 함수를 반환하고 __cmp__ 함수는 객체의 메모리 위치를 산술 비교합니다. 일반적으로 어떤 클래스의 두 인스턴스는 서로 다르고 해시 테이블 내에서 충돌이 발생하지 .. 자료구조 - 사전과 셋 (Dictionary, Set) 개요 셋과 사전은 삽입 순서를 제외하면 미리 정해진 순서로 정해지지는 않으나 (파이썬 3.7 부터 딕셔너리에 값을 추가한 순서가 보존됩니다) 특정 데이터를 고유하게 참조할 수 있는 별도 객체가 있을 때 매우 적합한 자료구조 입니다. 알다시피 참조 객체를 "키", 특정 데이터를 "값" 이라고 칭하며, 키는 해시가 가능하다면 (hashable) 어떤 타입이도 상관 없습니다. 사전과 셋은 거의 같지만 셋에는 값이 없고 유일한 키를 저장하는 자료구조입니다. 해쉬가 가능한 타입이란 ? 해쉬가 가능한 타입은 __hash__ 매직 함수, 그리고 키 값 비교를 위한 __eq__ 혹은 __cmp__ 매직 함수를 구현한 타입입니다. 파이썬의 내장 타입 (dict, set 등)은 모두 이를 구현하였기에 사용자가 사용할 때는.. 자료구조 - 리스트와 튜플 (List, Tuple) 리스트와 튜플은 파이썬의 배열 자료구조로서 리스트는 아마 파이썬에서 가장 많이 사용되는 자료구조일 겁니다. 배열에서는 항목의 내용 자체만큼이나 항목이 배치된 순서가 굉장히 중요한데, 리스트는 저장하는 데이터나 배열 크기를 변경할 수 있는 동적 배열이고 튜플은 내용과 순서가 고정된 변경 불가능한 정적 배열입니다. 파이썬은 배열을 생성하기 위해 연속된 시스템 메모리 블록을 할당하고 각 메모리에는 실제 데이터를 가리키는 정수 타입 크기의 포인터가 담겨 모든 타입의 데이터를 저장할 수 있습니다. (이는 numpy array 와 다른 점인데, numpy 배열은 정적으로 타입이 정해져있어 다른 타입의 값을 저장할 수 없습니다) 따라서 연속적인 메모리에 정렬되어 저장된 데이터는 배열의 크기와 상관없이 배열이 시작되는.. 방정식 해 찾기 - 고정점 반복법 하나의 변수 $x$를 가진 방정식의 해를 구하고 싶습니다. ($f(x) = 0$) 방정식의 해를 구하는 방법은 여러 가지가 있습니다만 이번 포스트에서 알아볼 방법은 고정점 반복법이라는 알고리즘입니다. 고정점 반복법의 시작은 $f(x) = 0$을 $g(x)=x$의 형태로 두고 $y=x$와 $y=g(x)$의 연립방정식을 반복을 통해 푸는 방법으로 특정 조건 하에서 사용할 수 있습니다. 그렇다면 $f(x) = 0$으로부터 $g(x) = x$ 형태로 둔다는 것은 무엇일까요? 예를 들어 $f(x)=x-cos(x)$일 경우, $g(x)$는 $x=g(x)=cos(x)$로 둠으로써 $y=x$와 $y=cos(x)$의 교차점을 찾으면 $f(x)=x-cos(x)=0$의 해를 구할 수 있겠죠. 만약 $f(x)=x^3+cos(.. 메트로폴리스 (Metropolis) 지난 몬테카를로 시뮬레이션 관련 포스트들은 모두 독립 확률 변수에 기초한 것입니다. 독립 확률 변수란 확률 변수들 사이에 상관관계가 없어 각 확률 변수를 독립적으로 만들 수 있다는 말이죠. 수식으로는 두 확률 변수 $X, Y$에 대해 $p(X,Y)=p(X)*p(Y)$와 같이 표현할 수 있을 겁니다. 하지만 확률 변수들을 독립적이지 않을 때는 어떨까요? 다시 말해서 $n$개의 확률 변수 $x_1, ..., x_n$에 대해서 다음 수식처럼 확률 변수를 독립적으로 분해할 수 없다는 것이죠. 이럴 때에는 메트로폴리스 (metropolis) 알고리즘을 사용할 수 있습니다. $p(x_1, ..., x_n) !=p(x_1)...p(x_n)$ 메트로폴리스 알고리즘은 다음과 같이 동작합니다. 정의역에 있는 독립 난수의 .. 이전 1 2 3 4 5 다음
