[ML][집단지성 프로그래밍] 5. 최적화

(1) 통계적 최적화(Stochastic optimization)
여러 변수들이 있고 다양한 해법이 있는 문제나 이 변수들의 조합에 따라 크게 변하는 산출물을 가진 문제에 사용됨
(2) 해답 표현하기
가능한 해답 표현 방식을 먼저 결정해야함
(3) 비용 함수
최적화를 사용해서 문제를 푸는 핵심 열쇠이며 동시에 선택하기 가장 어려운 존재
한 해답이 얼마나 나쁜지를 표현하는 값을 리턴해야 한다.
예) 몇가지 지표
가격, 여행 시간, 대기 시간, 출발 시간, 자동차 렌탈 기간
(4) 무작위 검색
좋은 최적화 기법은 아니지만 모든 알고리즘이 하려는 점을 정확히 이해하는 데 좋으며, 다른 알고리즘이 잘 동작하는지 볼 수 있는 기분선으로 공헌한다.
(5) 언덕 등반
무작위 해답으로 시작해서 더 좋은 해답을 찾아 이웃 해답들을 살펴보는 기법
전역최소점 : 어느 곳에서나 최고인 해답
무작위 재시작 언덕 등반 (random-restart hill climbing) : 무작위로 시작점을 몇 개 선택한 후 무작위로 선택한 시작점 중 하나가 전역 최소점에 근접할 것이란 희망을 가지고 언덕등반 알고리즘을 수차례 수행시킨다.
(6) 시뮬레이티드 어닐링(Simulated Annealing)
어닐링 : 합금을 가열한 후 천천히 냉각하는 과정. 원자는 주변을 뛰어다니다 점차 낮은 에너지 준위로 정착하기 때문에, 원자들은 가장 낮은 에너지 배치를 찾을 수 있다.
(7) 유전자 알고리즘(genetic algorithm)
개체군 : population이란 무작위 해답들을 생성하면서 시작된다.
최적화 단계마다 전체 개체군별 비용 함수가 계산되어 해답의 순위 목록을 만든다.
현재의 개체군에 대한 최상위 해답을 새로운 개체군에 추가한다(엘리트 선발(elitism)). 이 새로운 개체군의 나머지는 최고 해법을 수정하여 만든 완전히 새로운 해법을 구성한다.
해답을 변경하는 두가지 방법
A. 돌연변이(mutation) : 소량의 간단하고 무작위적인 변화를 기존 해답에 적용시키는 방법
B. 교배(crossover), 번식(breeding) : 최적 해답 두 개를 골라 어떤 방식으로 그 둘을 결합하는 것
(8) 비행편 검색 실제
KAYAK 카약 사이트의 API 이용
minidom 패키지
(9) 선호도 최적화 - 첫번째로 선택한 기숙사가 겹쳤을 때 누구를 선택하는가?
제한된 자원을 그에 대해 선호를 표현한 사람들에게 분배하여 가능한 모두 행복하게 하는 방법
- 학생 기숙사 최적화 : 학생들을 그들의 첫 번째와 두 번째 선택을 반영해서 기숙사에 배치하는 문제
모든 학생들이 적합하도록 해답을 표현하는 방법을 찾는 것
(10) 네트워크 시각화 ( 페이스북 앱에서 한번 해보고 싶음)
SNS사이트 내 각 멤버들은 연결된 친구들을 가지며 이를 모으면 사람 네트워크가 만들어진다. 이런 네트워크를 시작화하여 구조를 결정해서 이 네트워크에서 연결자 역할을 하는 사람을 찾는다.
(11) 다른 가능성들
사람의 기술 조합을 고려하여 그룹 프로젝트 안에 작업을 할당하는 방법
키워드로 태깅된 웹 사이트 목록에서 사용자가 제공한 키워드들을 가진 최적의 웹 사이트 그룹을 찾는 것