확률적 알고리즘 과 유전 알고리즘

확률적 알고리즘

알고리즘의 근본적인 부분에서 확률이 관계하고 있는 것을 확률적 알고리즘이라 함. 하지만 주어진 문제를 해결하는 알고리즘은

결정론적 알고리즘으로 기술. 이는 항상 같은 결과를 출력하고 처리하기 때문이다.

- 확률적 알고리즘은 항상 같은 결과를 출력하지 않음. 경우에 따라서 틀린 결과를 출력하거나 최적해가 아닌 근사해를 출력함.

- 원하는 결과를 얻지 못할 확률이 매우 낮다는 조건하에서 주어진 문제를 해결하는데 활용함.

- 난수를 필요로 함. 암호학 분야에서 매우 중요. 몬테카를로 , 라스베이거스 알고리즘이 있음.

몬테카를로 알고리즘 

- 물리적, 수학적 시스템의 행동을 시뮬레이션하기 위한 계산 알고리즘이다.

- 통계학적이며 일반적으로 무작위의 숫자를 사용한 비결정적인 방법. 

- 스타니스와프 울람이 모나코의 유명한 도박의 도시 몬테카를로의 이름을 본떠 명명. 수소폭탄 개발에도 핵심역활.

- 근사해를 출력 혹은 틀린 해 혹은 정확한 해를 출력 하기도함

- 결정론적인 알고리즘을 찾지 못한 경우 효과적.

적분 등으로 계산하기 어려운 특정한 면적을 구할 때 사용하고 프로젝트 관리에도 사용된다.

몬테카를로 알고리즘

라스베이거스 알고리즘

- 언제나 정확한 결과를 출력한다. 난수 발생기에 의해 확률적으로 이루어지기 때문에 실행시간이 오래 걸릴수 있음.

- 오류가 발생하더라도 알고리즘이 빠르게 실행되기 위한 것 몬테카를로와 달리 올바른 해를 보다 빨리 출력하기 위해 확률적 

선택을 하게 됨.

- 항상 올바른 해를 출력하는 특징. 겨절론적 알고리즘으로 수행시간이 길어질수 있음. 평균적으로 O(logn)

유전 알고리즘

- 적자생존과 유전의 매커니즘을 바탕으로 하는 탐색 알고리즘으로, 자연세계의 진화과정을 추상화하여 컴퓨터상에서 시뮬레이션

함으로써 복잡한 실세계의 문제를 해결하고 하는 시스템에 적용하는 알고리즘.

- 유한한 해 공간에서 가능한 한 짧은 시간에 최적에 가까운 해를 구하는 알고리즘으로 미시간 대학의 홀란드가 체계화함.

- 임의 세대 t에 후보해의 집단 P(t)에 대하여 유전 연산을 통해 가상적인 진화를 진행시켜서 상대적으로 우수한 해는 다음 세대에

살아남고 그렇지 못한 해는 다음 세대에 사라지게 됨.

- 초기 후보해 집단을 생성해야 하고 초기 후보해는 먼저 주어진 문제의 조건을 만족하는 해를 가져야 함.

- 조합적 최적화 < 가장많은 결과를 낸 분야 , 대표적인 연구 분야는 비결정 난해 군에 속하는 문제들

 순회판매원 문제 , 이차원 배정문제 등 ..

진화 알고리즘

- 자연세계의 진화과정을 컴퓨터상에서 시뮬레이션을 함으로써 복잡한 실세계의 문제를 해결하고자 하는 계산모델.

진화 알고리즘은 구조가 간단하고 방법이 일반적이어서 응용범위가 넓고 적응적 탐색 및 최적화를 통한 공학적인

문제의 해결에 많이 이용. 신경망, 퍼지 로직과의 결합 등 그 응용범위는 늘어나고 있는 추세.

유전 알고리즘에서 개개의 후보해를 표현하는 것은 매우 중요, 원칙적으로 일정한 크기의 비트 스트링으로 표현. 유전 연산으로

교배와 돌연변이가 있음.

교배

개체의 진화는 확률적으로 적은데 돌연변이에 의해 발생할 수도 있지만 주로 개체들끼리의 교배를 통해 발생함.

교배는 개체들끼리 유전자 배열을 섞는 과정을 마함, 2개의 개체간의 염색체를 부분적으로 서로 바꿈으로써 새로운 개체를 생성.

돌연변이

교배는 개체군 내에서의 개체 진화에 한계가 존재함. 주어진 환경에서 어느 한계까지는 진화하여 적응할 수 있지만, 개체군 내의

개체의 유전자 스키마를 극복할수는 없음.  돌연변이는 유전자 배열 중의 유전자를 바꾸는 연산자이다.

외판원 순환문제(TSP)

N개의 도시가 주어지고 임의의 한 도시에서 출발하여 모든 도시를 한 번씩만 방문하고 출발했던 도시로 다시 돌아오는 방법

중에서 최적의 경로를 구하는 유명한 NP- 완전 문제임. TSP를 풀기 위해 여러가지 최적화를 시도하나 일반적으론

휴리스틱 알고리즘을 TSP 문제 해결에 사용.

TSP

유사 알고리즘

최적화 문제에서 최적해에 가까운 가능 해를 구하는 알고리즘으로 이건 가장 최적화하는 답을 구할 수는 없다. 하지만 빠른

시간에 계산이 가능하고 어느 정도 보장된 근사해를 계산할 수 있다. 근사 알고리즘은 NP- 완전 문제 등 현재 알려진 빠른 

최적화 알고리즘이 없을 때 주로 사용한다.

언덕 오르기

- 후보해의 적응도를 점진적으로 개선하는 과정을 더 이상 하지 않을 때까지 반복 시행.

- 1개의 임의의 출발 후보해에서 시작하여 현재의 후보해에 이웃한 후보해를 선택하고 이것의 적응도를 계산하여 현재

후보해의 적응도와 비교.

- 최적경로 탐색 보장하지 못함. 지역 최대치 문제가 있음.

최소 비용 탐색기법

- 언덕 오르기 탐색의 반대가 최소비용 탐색이다. 이 기법은 롤러스케이트를 신고 큰 언덕의 길중간에 서 있는 것과 비슷하다

생각할 떄, 위로 가는 것보다 아래로 내려가는 것이 훨씬 더 쉽다는 것을 알 수 있음.

- 최소의 노력이 드는 경로를 택하는 것을 말한다.

- 예로 비행기 예약 문제에 발견된 경로가 가장 짧은 연결 비행기를 택할 것을 의미함.

A* 알고리즘

- 언덕 오르기 방법이나 최적우선 방법에서는 어떠한 노드에서 목표 노드까지 도달하기 위한 비용을 평가함수로 사용함

- 이때 출발 노드에서 그 노드까지 도달하는 데 소비한 비용은 고려하지 않는다. 따라서 출발 노드에서 목표 노드까지

도달하는 최적의 경로의 탐색은 보장x

- a* 알고리즘은 출발 노드에서 목표 노드까지의 최적경로를 탐색하기 위한 것이며 이를 위해서는 각각의 노드에 대한

평가함수를 정의해야 함.

- 경험적 지식에 의거한 예측값을 h^(n)이라 하면 노드 n에 대한 평가함수f^(n)은 다음과 같음.

f(n)=g(n)+h(n) //g(n) : 출발노드에서노드n까지의 경로비용 //h(n): 노드 n에서 목표노드까지의 경로비용

정보사용 , 목적	임의의 경로	최적경로
맹목적 탐색	깊이 우선 탐색 넓이 우선 탐색	균일비용 탐색
경험적 탐색	언덕 오르기법 최적 우선 탐색	A* 알고리즘