Meta-heuristic(1)

NP-hard Problem

TSP
-하나의 도시에서부터 시작해서 모든 도시를 한 번씩만 방문하여 다시 시작점을 돌아오는 최단 거리를 구하기
-열거말고는 방법이 존재하지 않음(ex 70개 도시(70-1)!/2)
-고유한 구조 때문에 효율적인 알고리즘이 존재하지 않음
-이런 문제들 중 한 문제라도 효율적을 풀 수 있으면, 다른 모든 문제들도 풀 수 있음
-이런 문제들을 NP-hard문제라고 한다


serach algorithm
-Brute Force seach:어떤 주어진 문제를 해결하기 위해 정해진 규칙을 위반하지 않는 모든 규칙을 나열
-dynamic programming

np-hard problem
-어떤 문제가 주어지면 그 문제가 np-hard문제인지 판단이 필요
-맞다면 정확한 최적해를 구하는 알고리즘을 추구하는 것은 시간 낭비
-그렇다면 해를 얻는것은 불가능?->no->근사해
-데이터가 특별한 구조를 가지고 있어서 해법이 존재할 수도 있음
-최적해는 아니지만 근사해를 효율적으로 구하는 방법이 존재함


knapsack problem
-여행가가 가지고 가는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제->수리적 모형

T최소화
-spt/edd/slack 다 안되는 경우도 있다

->너무 어렵다 보니 메타휴리스틱 알고리즘이 나왔다
metaheuristic

정의
▪ 컴퓨터 과학 및 수학적 최적화에서 메타휴리스틱은 다음을 수행하도록 설계된 상위 수준 절차 또는 휴리스틱
문제에 대해 "충분"히 좋은 솔루션을 제공할 수 있는 "경험적 방법"(부분 검색 알고리즘)을 찾고 생성하거나 선택합니다.
특히 불완전하거나 "불완전한 정보" 또는 "제한된 계산 용량"으로 인해 최적화 문제가 발생합니다.
메타휴리스틱스는 너무 커서 완전히 샘플링할 수 없는 솔루션 세트를 샘플링합니다.

속성
▪ 최적화 알고리즘과 비교하여 메타휴리스틱은 전역적으로 최적의 솔루션을 보장하지 "않는다."
▪ 메타휴리스틱으로 찾은 솔루션은 생성된 "무작위 변수 세트에 따라 달라진다."
▪ 조합 최적화에서는 실현 가능한 솔루션의 큰 집합을 검색함으로써 메타휴리스틱이 종종 좋은 점을 찾을 수 있다.
최적화 알고리즘, 반복 방법 또는 간단한 경험적 방법보다 "계산 노력이 덜 드는 솔루션"




메타휴리스틱 예시들
-Genetic algorithm(popolation, evolutionary algorithm, naturally inspired)
-Tabu seach(trajectory, short time memory)
-cuckoo seach(popolation, evolutinonary algorithm, naturally inspired, levy flights)


진화 알고리즘
-생물의 진화과정을 문제 해결 과정에 적용한 알고리즘
-세대를 거듭할 수록 우수한 성능의 해는 살아남고, 열등한 성능의 해는 도태됨(하나의 해가 하나의 개체에 대응됨)
-해공간이 넓고 복잡한 문제에서 우수한 해를 탐색하기 위해 사용됨


GA
-근간이 되는 알고리즘
-집단 유전학의 개체 진화 원리를 이용하여 해 공간을 탐색하는 방법
-집단 유전학의 개체 진화 원리를 이용하는 solution sapce search 방법
-key features
적자생존/교차연산/돌연변이/집단(population)/대체/평가
-염색체:임의의 해를 GA가 이해할 수 있는 형태로 표현한 것/해/solution
-population(해집단):정해진 수로 운영되는 염색채들의 집단
-gene(유전자):염색체의 각 인자
-generation:GA의 하나의 루프


구조
(1)initalization
-n개의 초기 염색체 집단 랜덤으로 생성
-문제에 맞게 알고리즘들 이용
(2)evaluation and selection
-평가하고 부모 고르기
-각 해의 성능을 평가
-정의한 문제의 목적함수에 따른 성능을 계산
(3)crossover
-유전자 수는 같지만 적당한 부분만 교차로 받을 수 있다
-exploitation
-두해의 특징을 부분 결합하여 하나의 새로운 해를 만드는 연산
-두 부모해의 동일한 위치에 자름선을 정한 후, 각 부모해로부터 한 부분씩 가져와 합치면 새로운 해가 생성됨
(4)mutation
-랜덤으로 부모에게 없는 유전자를 수정해봄
-exploration
-해를 임의로 변형시키는 연산
-교차와 달리 부모해에 없는 속성을 도입하여 해의 다양성을 높이는 역할
-대부분 해의 품질이 낮아지는 결과로 이어짐
(5)replacement
-못하는 애들은 없애고 잘하는 대들을 복제
-해집단의 일부가 새로운 해로 대체됨(도태와 생존을 위해)
-교차와 돌연변이와 연관되어서 결정해야 함
-해를 대체하지 않고 특정 비율만큼만 생존시키는 방식도 존재


염색체 표현
-모든 해는 염색체로 표현되어야 함
-전형적인 유전 알고리즘은 해를 이진 스트링 모양의 염색체로 표현함(01010001)
-정수를 해로 삼을 때 이진수로 나타내면 자연스럽게 이진수로 표현 가능

스키마
-패턴
-임의의 염색체는 많은 부분적 패턴을 포함하고 있음
-1101은 16개의 패턴이 포함됨 1***/****/1*01
-유전 알고리즘은 작은 스키마들이 결합하여 점점 더 큰 스키마를 이루어가는 과정
초기 단계는 해의 품질은 좋지 않음
-그러나 이런 염색체들 속에 나중에 좋은 염색체를 구성할 부분 패턴(스키마)가 숨어있음
-작은 스키마에는 존재하지 않는 특성이 큰 스키마에서 창발하는 것이 유전 알고리즘의 중요한 특징