인공지능 최적화

인공지능

코코팡 2021. 10. 11. 19:55

우선 최적화는 여러 가지 허용되는 값들 사이에서 주어진 기준을 가장 잘 만족하는 것을 선택하는 것이며

여기서 쓰이는 함수는 목적함수가 있으며 이 목적함수는 최소 또는 최대가 되도록 만들려는 함수이다.

조합 최적화

순회 판매자 문제와 같이 주어진 항목들을 조합하여 해가 표현되는 최적화 문제이다.

순회 판매자 문제의 목적함수: 경로의 길이

이런 식으로 주어진 항목들을 조합하여 최적의 경로의 길이를 구하는 방식을 조합 최적화라 한다.

유전 알고리즘은 생물의 진화를 모방한 집단 기반의 확률적 탐색 기법이며 대표적인 진화 연산의 하나이다.

생물의 진화에 과정을 보게 된다면

염색체의 유전들이 개체 정보를 코딩을 하고 적자생존과 자연선택으로 특정 환경에 적합도가 높은 개체의 높은 생존 및 후손 번성 가능성을 보며 우수 개체들의 높은 자손 증식 기회가 있지만 열등 개체들도 적은 확률이지만 증식의 기회가 있다.

그리고 이러한 과정들을 통해 개체들이 집단을 생성하며 진화하는 과정을 거치면서 점점 좋은 개체들을 배출을 해낼 수 있다.

그 과정에서 자연스럽게 부모 유전자들이 자식에게 교차로 상속이 되지만 부모 두 개체를 필요하지 않고 하나의 개체가 변화가 일어나 자식에게 물려줘 새로운 개체를 생성해 가는 방식이 있다.

그렇다면 이 생물의 진화 과정을 알고리즘 형태로 타나 내주면 어떻게 해주면 될까? 먼저 생물 진화와 문제 해결을 하기 위해 진화 과정의 개체는 후보 해가 되며 환경은 문제가 되며 적합도는 그 문제에서 개체가 잘 적응을 할 수 있냐의 해의 품질이 된다.

이를 순서도로 나타내 준다면

처음 초기 모집단 처음 세대의 해당하는 개체들을 생성하고 이 개체들은 우수한 열등한 개체들이 섞여 있으며 그것들을 적합도 함수를 이용하여 적합도 평가하고 특정 조건을 만족하면 종료 조건에서 최적 개체로 인식하여 순서도를 멈추고 아니라면 부모 개체를 선택한다.

그렇게 조건을 만족하지 못하면 다시 부모 개체들을 선택하여 유전 연산을 통해 자식 개체를 생성하여 이번엔 새로운 세대인 개체들을 구성하여 다시 적합도를 평가하는 과정을 최적 개체가 나올 때까지 반복한다.

그렇다면 이제 자세하게 이 순서도를 이용하려면 어떤 식으로 표현해야 할지에 대해 알아보자.

1. 후보해 표현에는 대표적으로 그림의 밑에서부터 배열의 형태, 벡터의 형태, 조합의 형태로 나타낼 수 있다.

2. 모집단: 동시에 존재하는 염색체들의 집합

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

4. 부모 개체 선택: 높은 적합도의 개체가 새로운 개체를 생성할 확률이 높도록 하고 적합도에 비례하는 선태 확률로 개체를 선택한다. 하지만 이 적합도가 무조건 높다고 선택이 되는 것이 말 그대로 확률이 상대적으로 높은 거지 적합도가 낮아도 선택될 확률이 있다.

실제로 부모 개체를 선택하였을 때 이 부모개체를 통해 자식 개체 즉 새로운 개체를 생성하는데 생성하는 과정에서 교차 연산자와 돌연변이 연산자를 써서 개체를 생성한다.

교차 연산자: 화살표를 기준에 부와 모의 개체가 있다 했을 때 이 둘의 정보를 믹스하여 오른쪽처럼 새로운 개체 2개를 생성할 수 있다.

돌연변이 연산자: 부나 모 둘 중 하나의 개체만을 가지고 새로운 개체를 만들 수 있다.

현재 세대를 거쳐 부모 개체 선택을 하여 더 우수한 개체를 다음 세대에 전달해주는 과정 즉 교차방식 또는 돌연변이 방식으로 전 세대의 부모 개체들이 더 우수한 개체를 생성을 하도록 하여 다음 세대로 전달되게 한다.

이 과정에서 이미 우수한 개체들은 그대로 전달이 되기도 한다.

함수 최적화는 어떤 목적함수가 있을 때 이 목적함수를 최대로 하거나 최소로 하는 변수의 값을 찾는 최적화 문제를 말한다.

예를 들어

그림의 예시처럼 x1과 x2의 해를 구하는 과정이 목적함수이고 이 함수의 최소로 하는 변수의 값을 구하기 위해 각각 변수의 대한 편미분을 통해 구하였다.

제약조건 최적화는 함수 최적화 문제에서 제약조건을 덧붙여 목적함수를 최적화시켜주는 변숫값들을 찾는 문제이다. 그림에서는 subject에 만족하는 x1, x2를 찾는 문제이며 주어진 제약 조건을 만족시키면서 최적화가 되는 변숫값을 찾는 최적화 방식의 문제이다.

회귀 문제에 대한 최적 함수 문제는 는 주어진 데이터가 있다면 그 데이터에 가장 근사한 값을 찾는 함수를 찾는 문제이다.

근사한 값을 찾는 방법에는 최소 평균 제곱 법이라는 방식으로 찾는다.

이 방식은 오차 함수 또는 에너지 함수를 최소로 함는 함수들을 찾는 방식으로 근사한 값이 음수가 나오면 안 되기에 제곱을 해주는 것도 있다.

먼저 위의 그림처럼 E의 식은 그래프를 기준으로 현재 1차 방정식으로 어떠한 최소로 하는 함수를 찾는 과정을 그린 것이며(1차가 아니어도 된다.) 파란색 점들을 근사한 값이 될 수 있는 후보들이다.

y의 좌표와 x의 좌표를 대입하였을 때 나오는 함숫값을 이용하여 오차값을 구하는 데 여기서 최소 평균 제곱 법을 이용하여 값을 구하고 주어진 점들의 개수만큼 N에 대입하여 E를 구하는 문제이다.

경사 하강법은 어떠한 함수의 최솟값을 구한다 했을 때 그 최솟값의 위치를 찾는 과정에서 오차 함수의 그레디언트를 계산하고 반대 방향으로 조금씩 움직이면서 최적의 파라미터를 찾고자 하는 방법이다.

예를 들어

이러한 그래프가 있다고 했을 때 처음에는 어떠한 값이 최솟값인지 모르기에 일단 a, b를 아무렇게나 정해놓고 우리는 최솟값을 찾기에 그레디언트 한 값을 구한 것에 반대방향으로 계속 조금씩 가다 보면 최적의 파라미터를 찾을 수 있다.