[방송대 알고리즘]해 탐사 알고리즘

해 탐사 알고리즘

되추적 알고리즘

• DFS로 해를 찾아다니다가 앞쪽에 더 이상 해가 없으면 왔던 길을 되돌아가서 다른 길을 찾아보는 방법

상태 공간 트리

• 주어진 입력으로 만들어 낼 수 있는 모든 후보해를 리프 노드로 갖는 트리
• 내부 노드는 각 후보해를 만들어 가는 부분 후보해를 나타냄

특징

• 다항 시간 알고리즘이 없지만 정확한 해를 구해야 하는 경우에 적용
• 저울 문제, 0-1 배낭 문제 → O(2^n)
• 시간 복잡도 분석과는 별개로 실제 동작 시 빠른 수행 결과를 보이는 경우가 많음

분기한정 알고리즘

최적화 문제에 대한 상태 공간 트리를 각 노드의 한정값을 이용하여 탐색 하는 방법

• 한정값: 현재 노드로 만들 수 있는 해의 상항이나 하한, 혹은 둘 다
• 한정값이 그 순간의 최적해보다 좋은 경우에만 탐색 후보로 보관
• 다음 탐색 대상은 탐색 후보 중 한정값이 가장 좋은 노드로 선택
• 더 좋은 해가 등장하면 최적해를 업데이트

특징

• 다항 시간 알고리즘이 없지만 근사해가 아닌 최적해를 구해야 하는 경우에 적용
• 0-1 배낭 문제, 외판원 문제 → O(2^n)
• 시간 복잡도 분석과는 별개로 실제 동작 시 빠른 수행 결과를 보이는 경우가 많음

유전 알고리즘

자연계의 진화를 통해 관찰된 메커니즘을 모방하여 최적화 문제를 해결하기 위한 탐색 방법

• 개체군 내의 각 개체에 대해서 적합도 점수 기반의 선택, 교차, 변이 연산을 차례로 적용하여 자손 개체를 만들어 새로운 개체군을 형성하는 과정을 종료 조건이 만족할 때까지 반복
• 적자생존을 모방하여 세대를 거치면서 점진적으로 해를 향상시킴

염색체의 인코딩

• 표현하려는 해에 대한 정보를 염색체의 형태로 표현하는 것
• 이진 인코딩, 순열 인코딩, 값 인코딩, 트리 인코딩 등

선택

• 개체군으로부터 부모 염색체가 되어 교차를 수행할 염색체를 선정하는 연산
• 룰렛 힐 선택, 순위 선택, 토너먼트 선택, 엘리티즘 등

교차

• 두 염색체의 특징을 부분 결합하여 하나의 새로운 특징을 가진 염색체를 만들어 내는 연산
• 단일점 교차, 두 점 교차, 균등 교차, 산술 교차 등

변이

• 교차 연산을 통해 생성된 새로운 개체의 이룹분의 유전자를 임의적으로 변경함으로써 부모 염색체에 없는 속성을 갖도록 하는 연산

주요 매개변수

• 교차 확률, 변이 확률, 개체군의 크기