컴퓨터는 문제 해결을 위하여 사용되는 도구이고, 이 도구를 유용하게 활용하여 입력되는 데이터를 이용 가능한 새로운 형태로 변환하는 일이 데이터의 처리이다.

따라서 데이터를 하나의 형태로서 다른 형태로 바꾸는 데이터 변환(data transformation)이 능률적으로 이루어지기 위해서는 데이터의 구조, 데이터의 변환 과정, 그리고 데이터의 변환을 효과적으로 실행하기 위한 기술 등이 따라야 한다.

데이터의 변환 과정에서는 수학적이나 통계적인 연산, 즉 평균을 계산하거나 시간당 임율과 작업 시간수를 가지고 임금을 계산하는 연산들이 포함될 수 있다. 또, 워드 프로세서(word processor)를 이용한 문서 편집이나 문서 조작, 그리고 방대한 자료로부터 특정의 정보를 발췌해 내는 정보 검색(information retrieval) 등도 포함된다.

이러한 데이터 변환을 위해서 적용되는 잘 정의된 방법(well-defined method)이 알고리즘(algorithm)인데, 알고리즘은 결국 문제를 풀기 위한 절차를 정해둔 것이라고 할 수 있다.

알고리즘이란 특정 작업을 수행하기 위한 유한 개의 명령어의 집합으로써 다음과 같은 5가지의 조건을 만족하여야 한다.

• 입력(input) : 데이터의 변환 대상이 되는 입력이 있어야 한다. 그러나 경우에 따라서는 데이터가 외부에서 투입되지 않고 내부에서 생성될 수도 있다.

• 출력(output) : 데이터 변환 과정을 거쳐 적어도 한 가지 이상의 결과가 출력되어야 한다.

• 명확성(definiteness) : 알고리즘을 구성하는 각 명령어들은 그 의미가 명백하고 모호하지 않아야 한다.

• 유한성(infiniteness) : 알고리즘의 명령대로 순차적인 실행을 하면 언젠가는 반드시 실행이 종료되어야 한다.

• 유효성(effectiveness) : 원칙적으로 모든 명령들은 오류가 없이 실행 가능해야 한다.

이상과 같이 알고리즘은 입력, 출력, 명확성, 유한성, 유효성이 만족되어야 하는데, 프로그램(program)은 유한성이 만족되지 않아도 된다는 측면에서 알고리즘과 프로그램이 구별된다.

 

< 수업 교재 >

http://ant.blackun.com/ch02
전북대학교 알고리즘 개미 - 2조


Divide and Conquer

분할 정복법은 하향식(Top-Down) 접근 방법이다.

즉, 문제의 맨 상위 사례의 해답은 아래로 내려가서 작은 사례에 대한 해답을 구함으로써 구한다.

Divide-and-conquer란 여러 개의 부프로그램으로 나누는 전략을 말한다. 다시 말하면, n개의 입력을 처리하는 함수는 divide-and-conquer를 통해 k개(1 < k <= n)의 부프로그램으로 나뉘어 각각 처리하게 된다. n개의 입력은 k개의 부분집합으로 나뉘어 각각의 부분프로그램에서 처리되어 진 후, 이 결과값들을 합치어, 원하던 값을 얻게 된다.

만약, 나누어진 부프로그램이 여전히 처리하기에 크다면, 이 부프로그램은 다시 divide-and-conquer를 사용하여 더 작은 부프로그램으로 나뉘게 된다. 결국 프로그램은 더 이상 쪼갤 필요가 없을 때까지, 즉 처리하기에 충분히 작은 크기가 될 때까지 트리와 같은 형태로 부프로그램으로 나뉘어지게 된다.

흔히, Divide-and-conquer로 생긴 자식 프로그램은 원래의 부모 프로그램과 같은 타입을 가지는 경우가 많다. 다시 말해서, 자식 프로그램을 처리하는 것이 부모 프로그램을 처리하는 것과 입력의 크기만 다를 뿐, 과정이 모두 똑같다는 말이다

이런 경우, divide-and-conquer를 자식프로그램에서 적용하고자 한다면, 재귀함수를 사용하는 것이 자연스럽다. 사실, divide-and-conquer를 사용했다고 하면, 재귀함수를 이용했다고 보아도 무방할 것이다.

더 정확한 설명을 위해, divide-and-conquer 방법을 보여주는 프로그래밍 코드를 살펴보도록 하겠다.

< Program. Divide-and-conquer >

먼저, DAndC(P)가 호출될 것이다. 여기서 DAndC는 divide-and-conquer를 의미하며 P(problem)는 해결해야 할 문제이다. DAndC 내부에서는 제일 먼저 Small(P)가 호출되어진다.

Small 함수는 불리안(Boolean) 값을 반환하는 함수로, 입력 크기가 더 이상 쪼개질 필요없이 충분히 작을 경우 참을 반환한다. 반환값이 참인 경우, S(P)를 호출한다. S(solve)는 P를 풀어서 적당한 값을 반환하게 될 것이다.

다시 Small 함수로 돌아가자.

여기서 Small(P)의 값이 거짓이라면, 즉 P가 여전히 크다면, P는 k개의 부프로그램으로 나누어 질 것이다. 이 프로그램은 나누어진 부프로그램 P1, P2, .. 등이 P와 같은 타입을 가지는 경우이므로, 재귀함수를 이용하여 똑같은 과정을 적용하게 된다. Combine 함수는 k개의 부프로그램으로부터 얻은 결과들을 합쳐서 P의 솔루션을 얻어내게 된다.

위 알고리즘에서 살펴보았듯이, divide-and-conquer를 기반으로 하는 알고리즘은 부모 프로그램과 자식 프로그램(또는 부프로그램)이 형태가 같은 경우가 많으므로, 재귀함수를 사용하는 것이 자연스럽다.

분할정복의 사용의 예...

① 이분검색(Binary Search)

② 합병정렬(Merge Sort)

③ 빠른 정렬(Quick Sort)

④ 행렬의 곱셈

⑤ 큰 정수의 계산

http://ant.blackun.com/ant


Ant Colony Algorithm(ACO)

개미 알고리즘(Ant algorithm)은 실제 개미들이 먹이까지 가장 짧은 경로를 찾는 것을 모방한 알고리즘입니다. 이 알고리은 1992년

Dorigo에 의해 처음 제안되었습니다. 개미들은 어떻게 가장 짧은 경로를 찾게 되는 것일까요? 다음과 같은 예제를 통해 살펴보겠습니다.

어떤 개미가 (a) 라는 길을 열심히 돌아다니다가 음식 (F)를 찾게 됩니다. 그 후 <그림1>과 같이 둥지로 돌아오는 경로 (b)에다가 페로몬

으로 흔적을 남기면서 돌아옵니다.

이 어떤 개미는 한 마리가 아니었고 4마리 정도가 동시에 둥지에 도착해서 <그림2> 번과 같이 여러 개의 길을 찾게 되었습니다. 이중에는

먹이까지 긴 길도 있고 짧은 길도 있게 됩니다.. 그러나 페로몬의 특성상 길에 남겨진 페로몬은 시간이 지날수록 그 향이 희미해진다.

경로가 길게 되면 개미들이 흔적을 남기는 시간도 길어지게 되며 자연적으로 긴 경로에는 상대적으로 페로몬 향이 옅어 지게 됩니다.

개미들은 여러 경로 중 페로몬 향이 강한 길을 선택해서 움직입니다.

짧은 길일 수록 개미들의 왕래가 잦아지면서 페로몬 향기는 짙어집니다.

결국 <그림3>과 같이 개미들은 가장 짧은 경로로 먹이를 운반하게 됩니다.

Ant 알고리즘은 최적의 경로를 선택합니다. 우리는 이 경로를 Edge 로 정의하고 Edge 끝은 Node 로 정의 합니다. 정리하면 다음과

같습니다.

Ant 알고리즘은 페로몬의 향기 정도를 다음과 같은 확률계산식으로 계산합니다.

이 식에서 τi,j 는 edgei,j 의 페로몬의 양을 나타냅니다. α는 τi,j 의 값을 컨트롤 하는 파라미터 값입니다.

ηi,j 는 edgei,j 에 대한 가중치를 나타내며 보통 노드 사이의 거리에 반비례하는 값입니다.

β는 ηi,j 의 값을 컨트롤 하는 파라미터 값입니다.

Ant 알고리즘에서 개미는 이 확률 값을 통해 경로를 선택하게 됩니다.

다음은 페로몬 업데이트 공식을 살펴 보겠습니다.

τi,j = (1 − ρ)τi,j + Δτi,j

ρ 값은 페로몬의 증발 비율을 나타냅니다. Δτi,j 는 새로이 추가되는 양을 나타내며 다음과 같이 정의됩니다.

Lk 는 노드 사이의 거리로 볼 수 있습니다.

Ant 알고리즘은 TSP 문제에 적용시킬 때 좋은 예가 됩니다.

TSP는 판매원이 집에서 출발하여 모든 고개들의 도시에 방문하고 다시 집에 돌아오는 최단 경로를 찾는 문제 입니다.

이 문제에는 다음과 같은 전제 조건이 있다.

매판원의 집도 도시로 취급한다.

모든 도시들은 서로 연결되어 있다.

모든 도시들은 한번씩만 거쳐야 한다.

모든 도시들을 거친뒤 다시 매판원의 집으로 돌아와야 한다.

이 전제 조건을 고려하여 TSP를 구하는 Pseudocode 를 작성하면 다음과 같습니다.

-----------------------------------------------------------------------------------------------------

Start Node : Each ant is initially put on a ramdomly chosen start city

While(all ants don’t pass by every nodes)

while(an ant don’t pass by every nodes)

ant←getNextMovableNode()

ant←chooseNextNode()

end-while

Arc←updatePheromone(ant’s path)

End-while

-----------------------------------------------------------------------------------------------------

 개미는 처음에 랜덤하게 시작 노드를 정해 위치시킵니다.

페로몬을 업데이트 할 때는 짧은 경로일수록 가중치를 주기 위해서 경로의 길이가 짧을수록 페로몬이 증발량을 작게 합니다.

모든 개미가 모든 노드를 거치게 되면 프로그램이 종료하게 됩니다.

TSP의 결과는 프로그램이 종료된 후 그래프의 각 arc(경로)에 남아있는 페로몬의 수치가 높은 순으로 선택하면 앞의 그림처럼 하나의

루프가 형성된다.

이것은 곧 TSP의 최적의 해가 됩니다.

이러한 NP 문제를 해결하는 이외에도 ACO 알고리즘은 네트워크 분야, 유전학 분야, 검색 분야 등 다양한 곳에 적용 될 수 있습니다.