[Optimization] 조합 최적화

이번 포스팅에서는 최적화에서 사용되는 목적 함수의 개념과 조합 최적화, 그 중 유전 알고리즘에 대해 자세히 알아보겠습니다.

개요

최적화

최적화란 여러 가지 허용되는 값들 중 주어진 기준을 가장 잘 만족하는 것을 선택하는 것을 말합니다.

즉, 자신의 목적에 가장 적합한 해를 찾는 것이죠.

목적 함수

최적화 문제에서는 목적 함수가 사용됩니다.

이 목적 함수가 최적화 문제에서 사용되는 기준이 되며, 이 목적 함수를 최대화 또는 최소화하는 해를 찾는 것입니다.

조합 최적화

조합 최적화란 순회 판매자 문제(TSP)같이 주어진 항목들의 조합으로 해가 표현되는 최적화 문제입니다.

순회 판매자 문제의 경우 목적 함수는 경로의 길이가 되고, 이 경로의 길이를 최소화하는 최적 해를 찾습니다.

메타 휴리스틱

본격적으로 유전 알고리즘에 대해 알아보기 전에 메타 휴리스틱이라는 용어에 대해 짚고 넘어가겠습니다.

메타 휴리스틱이란 최적해는 아니지만 우수한 해를 빠르게 찾기 위한 휴리스틱적인 문제헤결 전략을 말합니다.

그 예로 아래와 같은 조합 최적화 기법들이 있습니다.

• 유전 알고리즘
• 모방 알고리즘
• 입자 군집 최적화
• 개미 집단 알고리즘
• 타부 탐색
• 담금질 기법

이 중 우리는 유전 알고리즘이 무엇인지 자세히 알아보도록 하겠습니다.

유전 알고리즘

유전 알고리즘이란 생물의 진화를 모방한 집단 기반의 확률적 탐색 기법으로, 대표적인 진화 연산중 하나에 해당합니다.

대표적인 진화 연산에는 유전 알고리즘, 유전자 프로그래밍, 진화 전략 등이 있습니다.

생물의 진화

우선 유전 알고리즘이 모방한 생물의 진화의 특징으로는 무엇이 있을까요?

1. 염색체의 유전자들이 개체 정보 코딩

하나의 개체에 해당하는 특징들은 그 개체를 이루고 있는 염색체의 유전자들에 의해 결정됩니다.

2. 적자생존/자연선택

생물은 환경에 적합도가 높은 개체의 생존 및 후손 번성 가능성이 높습니다.

이것은 곧 우수 개체들은 높은 자식 증식의 기회를, 열등 개체들은 낮은 자식 증식의 기회를 부여받게 된다는 것이죠.

3. 집단의 진화

하나의 집단으로부터 자식들이 태어나며 자연스러운 세대 교차가 일어납니다. 이를 세대 집단의 변화라고 합니다.

4. 형질 유전과 변이

후손이 생겨나는 방식으로는 크게 두 가지를 들 수 있습니다.

하나는 부모 유전자들의 교차 상속이고, 다른 하나는 돌연변이에 의한 변이입니다.

생물 진화와 문제 해결

유전 알고리즘은 위에서 살펴본 생물 진화의 특징을 최적화 문제 해결을 위한 방법에 반영하였습니다.

• 개체 ➡ 후보 해
• 환경 ➡ 문제
• 적합도 ➡ 해의 품질

후보 해의 표현

유전 알고리즘에서는 후보 해의 표현을 위해서 대표적으로 염색체 표현을 사용합니다.

모집단

동시에 존재하는 염색체들의 집합을 말합니다.

적합도 함수

후보해가 문제의 해로서 적합한 정도를 평가하는 함수입니다.

부모 개체 선택

유전 알고리즘에서는 생물의 진화와 마찬가지로 높은 적합도를 보이는 후보 해가 새로운 후보 해를 생성할 확률이 높도록 합니다.

즉, 적합도에 비례하는 선택 확률을 부여합니다.

예를 들어 개체 1의 적합도가 10, 개체 2의 적합도가 5, 개체 3의 적합도가 15라면 개체 1~3의 선택 확률은 2:1:3이 됩니다.

유전 연산자

새로운 후보 해를 생성할 후보 해를 선택했다면, 이 후보 해를 이용해 새로운 후보 해를 어떻게 만들어낼까요?

여기서도 역시 생물의 진화 방법을 모방합니다.

대표적으로, 교차 연산자와 돌연변이 연산자를 사용합니다.

1. 교차 연산자

2. 돌연변이 연산자

세대 교체

하나의 모집단에서 후보 해들을 생성하고 나면, 그 모집단은 세대 교체를 겪게 됩니다.

이렇게 우수한 개체를 다음 세대에 유지하는 것을 엘리트 주의라고 합니다.

정리

이상으로 최적화 기법 중 조합 최적화, 그 중 유전 알고리즘에 대해 알아보았습니다.

조합 최적화는 주어진 후보들의 조합으로 해가 표현되는 최적화 기법을 말하고, 이 중 유전 알고리즘은 생물의 진화를 모방하여 최적화를 수행합니다.

유전 알고리즘에서 사용되는 진화의 개념으로는 개체의 표현, 개체의 번식 확률, 자손이 생겨나는 방법, 세대의 교체 등이 있었습니다.