Journal Search Engine

ISSN : 2005-0461(Print)
ISSN : 2287-7975(Online)

Journal of Society of Korea Industrial and Systems Engineering Vol.42 No.3 pp.1-7
DOI : https://doi.org/10.11627/jkise.2019.42.3.001

Improvement of Ant Colony Optimization Algorithm to Solve Traveling Salesman Problem

Juyoung Jang

, Minje Kim

, Jonghwan Lee†

Department of Industrial Engineering, Kumoh National Institute of Technology

Corresponding Author : shirjei@kumoh.ac.kr

Received 06/03/2019 Finally Revised 26/04/2019 Accepted 27/04/2019

Abstract

It is one of the known methods to obtain the optimal solution using the Ant Colony Optimization Algorithm for the Traveling Salesman Problem (TSP), which is a combination optimization problem. In this paper, we solve the TSP problem by proposing an improved new ant colony optimization algorithm that combines genetic algorithm mutations in existing ant colony optimization algorithms to solve TSP problems in many cities. The new ant colony optimization algorithm provides the opportunity to move easily fall on the issue of developing local optimum values of the existing ant colony optimization algorithm to global optimum value through a new path through mutation. The new path will update the pheromone through an ant colony optimization algorithm. The renewed new pheromone serves to derive the global optimal value from what could have fallen to the local optimal value. Experimental results show that the existing algorithms and the new algorithms are superior to those of existing algorithms in the search for optimum values of newly improved algorithms.

Key Words : Ant Colony Optimization Algorithm , Traveling Salesman Problem , Optimization

순회 판매원 문제 해결을 위한 개미집단 최적화 알고리즘 개선

장 주영, 김 민제, 이 종환†

금오공과대학교 산업공학부

초록

키워드 :

This article has been cited by 0 article in crossref

Cited-By

Funding:

Kumoh National Institute of Technology

1. 연구배경 및 방법

개미집단 최적화 알고리즘(Ant Colony Optimization Algorithm, ACO)[1, 2, 3, 4, 6, 10]은 복잡한 문제를 해결하기 위한 메타 휴리스틱 방법이다. 식량을 찾아 이동하는 개 미들의 행동을 기반으로 하여 만들어진 이 알고리즘은 개 미들이 이동을 하면서 페로몬(Pheromone)을 남기게 된다. 이동경로에 쌓여있는 페로몬의 정보를 이용해 다음 경로 를 선택하게 하는 원리를 휴리스틱 탐색기법에 적용시킨 방법이다. 개미는 갈림길에서 서로 다른 페로몬의 양을 기준으로 길을 선택하게 되고, 이러한 페로몬의 정보가 업데이트 되면서 문제를 해결하게 된다. 이러한 알고리즘은 여러 문제에서 사용되고 있다. 대표적으로 작업 상점 스케 줄링 문제(Job-shop Scheduling Problem, JSP), 차량 경로 문제(Vehicle Routing Problem, VRP), 순회 판매원 문제 (Traveling Salesman Problem, TSP)[3, 4, 6, 8, 9, 10] 등이 있다.

개미집단 최적화 알고리즘은 처음 고안된 것이 1992년 이며[9], 처음 고안된 시기에 비해 시간이 많이 지났다. TSP 문제는 시간이 지날수록 더욱 복잡해졌고, 도시의 수는 많이 증가하게 되었다. 본 논문에서는 기존의 개미 집단 최적화 알고리즘이 가지는 한계점을 설명하고 한계 점을 극복하여 개선한 것을 보여주고자 한다.

본 논문에서는 많은 도시 수의 TSP 문제를 해결하기 기존의 개미집단 최적화 알고리즘에서 유전 알고리즘(Genetic Algorithm, GA)[5, 8, 9]의 돌연변이를 더한 개선된 새로운 개미집단 최적화 알고리즘을 제시하여 문제를 해 결하는 방법을 제시한다. 이 새로운 개미집단 최적화 알 고리즘은 기존의 개미집단 최적화 알고리즘에서의 문제 점인 국부 최적 값에 쉽게 빠지는 현상을 돌연변이를 통 해 변경된 경로들을 통해서 전역 최적 값으로 넘어갈 수 있는 기회를 제공한다. 개선된 경로는 개미집단 최적화 알고리즘을 통해서 페로몬이 갱신되게 된다. 갱신된 새로 운 페로몬은 자칫 국부 최적 값에 빠질 수 있었던 것을 전역 최적 값으로 유도하는 역할을 하게 된다.

2. 순환 판매원 문제

순환 판매원 문제(Traveling Salesman Problem, TSP)[3, 8, 9, 10]는 조합 최적화 문제의 하나이다. 이 문제는 NPHard 문제에 속하는 문제이다. 순환 판매원 문제는 주어 진 여러 개의 도시가 있는 경우에 무작위로 선택된 한 도 시에서 출발하여 모든 주어진 도시들을 한번씩 방문하고 서 다시 선택된 도시로 되돌아오는 문제이다. 이 문제는 모든 도시들 간의 이동시간이나 비용 등이 존재하며, 모 든 도시들을 방문하고 돌아왔을 때의 최소 비용 혹은 최 소 시간 등을 구하는 문제이다. 순환 판매원 문제는 대칭 적인 거리를 가지는 문제와 비대칭적인 거리를 가지는 문 제로 나누어진다. 순환 판매원 문제가 NP-Hard 문제에 속 하는 문제라는 것은 이미 알려져 있는 사실이다. n개의 도시를 방문해야 하는 순환 판매원 문제를 풀기 위해서는 개의 경우의 수를 다 확인하여 비교해야 한다는 문제점이 있다. 이러한 문제점을 해결하기 위해서 여러 가지의 솔 루션들이 제시 되었다. 가장 대표적인 것으로는 시뮬레이티 드 어닐링(Simulated Annealing), 터부 검색(Tabu Search), 유전 알고리즘(Genetic Algorithm), 개미집단 최적화(Ant Colony Optimization) 등이 존재한다.

3. 메타 휴리스틱

3.1 메타 휴리스틱

휴리스틱(Heuristic)이라는 개념이 등장하면서 대다수 의 알고리즘은 다양한 최적화 문제를 해결하기 위해 개 발되고 발전되는 방향으로 나아가고 있다. 이러한 알고 리즘의 대부분은 기울기나 수식의 정보를 필요로 한다. 보통의 알고리즘은 시작점(Starting Point)에서 시작하여 시작점보다 개선된 해를 찾는 수학적 선형 혹은 비선형 수식을 구하여 그 수식을 해결하여 보다 나은 해를 선택 하는 방향으로 진행된다. 수학적 최적화 알고리즘은 해 결하고자 하는 모델이 단순하고 이상적일수록 전역 최적 값(Global Optimum)을 찾는데 유용하다. 그러나 많은 모 델들의 모형이 매우 복잡하고 이상적이지 않은 모델이 많아서 이러한 알고리즘을 이용하여 전역 최적 값을 구 하는 것은 매우 어려운 일이다. 또한 전역 최적 값을 구 한다고 하더라고 많은 시간이 소요되어서 하나의 문제를 푸는데 오랜 시간이 걸릴 수도 있다. 이러한 문제를 해결 하기 위해 국부 최적 값(Local Optimum)이라는 개념을 가지고 오게 된다. 이 국부 최적 값은 전역 최적 값이라 고 불리는 완벽한 답은 아니지만 전역 최적 값에 근접하 는 값을 찾고, 문제를 해결하는데 필요한 시간을 보다 줄 이게 된다. 그리하여 어떠한 문제에 하나 이상의 국부 최 적 값이 있다면 이 결과는 시작점의 선택에 의해 결정이 된다. 그러나 이렇게 구해진 최적의 값은 반드시 전역 최 적 값이라 할 수 없다.

<Figure 1>과 같은 모형일 경우에 국부 최적 값의 근처 에서 시작점이 생성된다면 수학적 알고리즘에 의해 최적 의 값은 국부 최적 값으로 수렴하게 될 것이다. 그러나 최 적의 값은 국부 최적 값이 아닌 전역 최적 값이다. 휴리스 틱 기법은 수학적 알고리즘에 의해서 값이 결정된다. 그 리고 휴리스틱 기법은 문제마다에 맞는 수학적 알고리즘 을 찾아야 한다. 문제에 마다 맞는 수학적 알고리즘을 찾 기 위해서는 그 문제에 맞는 경험이나 직관 등을 이용하 여 해결해야 한다. 이러한 문제를 해결하기 위해 메타 휴 리스틱(Meta Heuristic)이라는 개념이 등장하게 되었다. 메타 휴리스틱 기법에는 여러 가지의 방법이 존재한다. 가장 대표적인 것으로 유전 알고리즘(Genetic Algorithm : GA), 시뮬레이티드 어닐링(Simulated Annealing : SA), 터부 탐색(Tabu Search : TS) 등이 있다. 그리고 개미집단 최적화 (Ant Colony Optimization : ACO)가 있다.

3.2 개미집단 최적화

개미집단 최적화는 1992년 Marco Dorigo의 박사 학위 논문에서 가장 처음 등장하였다[3]. 이 당시의 개미집단 최적화 알고리즘은 집단과 각 식량이 존재하는 곳 사이의 경로를 탐색하는 개미들의 행동을 보고 그래프에서 최적 경로를 찾는 것을 목표를 두었다.

개미들은 이동하면서 페로몬을 뿌리고 다니게 된다. 이 페로몬은 개미들에게는 대화의 수단이 되고, 이동경 로가 된다. 페로몬을 통해서 먹이의 위치를 공유하고, 집 으로 가는 길을 공유하게 되면서 개미들은 이동하게 된 다. 또 다른 개미들이 이동하게 되면서 페로몬을 뿌리게 되고 페로몬은 중첩이 되어서 기존의 페로몬보다 보다 더 진한 페로몬이 된다. 뒤따라오는 개미들은 기존의 페 로몬보다 더 진하고 강한 페로몬에 이끌리게 되고 그렇 게 보다 강해진 페로몬으로 남게 되는 것이다. 진하고 강 한 페로몬이 끝에 있는 먹이를 개미들은 운반하게 된다. 그러나 먹이를 다 옮기게 되면 개미들은 더 이상 그 곳 으로 가지 않게 되면서 점차 페로몬의 길이 옅어지게 된 다. 그렇게 페로몬을 통해서 개미들은 먹이가 있는 가장 짧은 길을 자연적으로 찾게 되고, 그것을 공유하게 된다.

이러한 개미들의 특성을 활용해 빠르게 최적의 값을 찾을 수 있도록 만들어진 알고리즘이 개미집단 최적화 알고리즘이다. 개미집단 최적화 알고리즘은 순환 판매원 문제를 해결하는데 가장 최적화 되어있는 것으로 유명하 다. 그 이유는 우선 수많은 경우의 경로를 수학적 알고리 즘에 의해 여러 번 이동하면서 정해지는 수많은 경로들 중에 겹치게 되는 경로들이 존재할 것이다. 겹치게 되는 경로들은 그렇지 않은 경로들보다 페로몬이 쌓이게 되면 서 보다 강력한 페로몬으로 남게 된다. 겹치게 되는 경로 들을 개미집단 최적화 알고리즘으로 적용하여서 보다 나 은 경로를 찾게 되는 것이다.

4. 알고리즘 개발

4.1 기존의 알고리즘

기존의 개미집단 최적화 알고리즘에서 가장 중요한 요소는 개미이다. 개미들은 문제를 해결하기 위해서 스 스로 길을 찾아 움직이게 된다. 개미들이 움직이면서 이 동하는 경로를 따라서 페로몬을 남기면서 움직이게 된 다. 후발주자로 따라오게 되는 개미들은 페로몬을 따라 서 움직이게 된다. 따라오는 개미들 역시 페로몬을 남기 면서 움직이게 된다. 페로몬은 시간이 지남에 따라서 증 발을 하게 된다. 따라오는 개미들이 많은 길은 페로몬이 증발하는 것 보다 남는 것이 많아서 강력한 페로몬이 남 게 될 것이다. 이러한 것을 응용한 것이 바로 개미집단 최적화 알고리즘이다[1, 2, 3, 4, 6, 10].

개미집단 최적화 알고리즘에서 가장 큰 장점은 최적 의 값을 찾아가는 수렴속도가 매우 빠르다는 것과 전역 최적 값을 찾는 탐색능력이 우수하다는 것이다. 그러나 국부 최적 값에 수렴할 확률이 높다는 것이다. 국부 최적 값에 수렴했을 경우에 전역 최적 값으로 넘어갈 수 있는 어떠한 수식이나 조건이 필요한데 개미집단 최적화 알고 리즘에서는 그러한 능력이 부족하다. 개미집단 최적화 알고리즘에서는 많은 개미들이 한 번에 움직이기 때문에 메모리를 많이 차지한다는 단점이 존재한다.

이러한 한계점을 해결하기 위해서 기존의 개미집단 최적화 알고리즘에서 일정 수식을 더하여서 전역 최적 값으로 보다 쉽게 넘어갈 수 있는 방법을 생각해보았다. 가장 대표적으로 전역 최적 값으로 가장 많이 수렴할 수 있는 방법인 유전 알고리즘(GA)에서의 돌연변이, 화음 탐색 법(HS)에서의 새로운 하모니 생성 등 여러 가지의 방법들이 존재한다. 여기에서 유전자 알고리즘에서의 돌 연변이라는 과정은 기존의 국부 최적 값에 빠질 수도 있 는 알고리즘을 새로운 값으로 변경하여 문제를 해결함으 로써 국부 최적 값에 빠지지 않고 전역 최적 값으로 유 도하는 과정이다[5, 9]. 그리하여 개미집단 최적화 알고 리즘에서의 가장 큰 문제인 국부 최적 값에 쉽게 수렴할 수 있다는 문제점을 해결하기 위해서 돌연변이라는 개념 을 가져 새로운 개미집단 최적화 알고리즘을 만들어보고 자 한다.

4.2 새로운 알고리즘

기존의 개미집단 최적화 알고리즘에서는 국부 최적 값에 빠지기 쉽다는 단점을 가지고 있으나, 새롭게 개선 된 개미집단 최적화 알고리즘에서는 국부 최적 값 일수 도 있는 최적 값을 돌연변이라는 과정을 통해서 새롭게 개선된 알고리즘을 계획해보았다. 기존의 개미집단 최적 화 알고리즘에서 개선된 알고리즘의 문제점인 국부 최적 값에 빠지기 쉽다는 점을 개선하여 새로운 알고리즘을 도식화였다.

처음에는 기존의 개미집단 최적화와 같이 임의의 시 작점을 잡고 시작하게 된다. 임의의 시작점을 시작으로 하여 개미집단 최적화 알고리즘을 시작하게 되고 개미집 단 최적화 알고리즘은 최적의 값을 찾게 된다[3]. 최적의 값을 찾게 되었을 때 일정한 값으로 수렴하게 될 것이다. 이때 기존의 개미집단 최적화 알고리즘이라면 이때의 값 이 전역 최적 값인지 국부 최적 값인지 확인 할 수 있는 방법은 없다. 이때 일정확률을 통해서 돌연변이를 진행 해본다. 이때 돌연변이는 개미집단 최적화 알고리즘에서 나온 경로에서 한 숫자를 뽑아 변형을 주게 된다. 돌연 변이를 통해 생성된 경로를 다시 한 번 개미집단 최적화 알고리즘에 적용하여 기존의 경로와 돌연변이를 통해 생성된 경로를 비교하게 된다. 이때 돌연변이를 통해 나온 값은 전혀 새로운 경로를 제시하기 때문에 만약 국부 최적 값으로 수렴하고 있다면 이러한 돌연변이를 통해서 전역 최적 값으로 수렴할 수 있는 기회를 얻게 될 것이다. <Figure 2>

4.3 알고리즘에서 기호 및 변수 정의

ACO 알고리즘에서는 노드(r)에 있는 개미(k)가 노드(s) 로 이동할 때 식 (1)을 사용해 다음 노드로 이동을 하게 된다. 이것을 상태전이 규칙이라 부른다. 여기서 τ(r, u)는 노드(r)과 노드(u)사이의 페로몬의 양이다. 또한 η(r, u) = 1/δ(r, u)로서 δ(r, u)는 노드(r)과 노드(u)사이의 거리이며, J_k(r)은 노드(r)에 있는 개미(k)가 방문할 남아있는 노드들 의 집합이다[11].

s = {\begin{array}{l} \arg \max {{[τ (r, u)]}^{α} \cdot [η {(r, u)}^{β}]} & if q \leq q_{0} \\ S & o t h e r w i s e \end{array}

(1)

q는 [0, 1] 사이에 분포된 무작위 파라미터이며, q₀는 [0, 1] 사이의 값을 가진다. S는 식 (2)에서 주어진 함수 식에 따라 선택된 무작위의 파라미터이다. 페로몬과 간 선 사이의 길이에 의한 연산으로 선택된 것이 아니라 확 률분포를 이용하였다.

P_{k} (r, s) = {\begin{array}{l} \frac{[τ (r, u)] \cdot {[η (r, u)]}^{β}}{\sum_{e} [τ (r, u)] \cdot {[η (r, u)]}^{β}} & i f s \in J_{k} \\ 0 & o t h e r w i s e \end{array}

(2)

식 (3)은 지역 갱신을 하게 되는 규칙을 설명하고 있 다. 지역갱신은 개미들이 방문한 각 간선들을 아래의 지 역 갱신 규칙을 적용하여 페로몬의 양을 갱신시킨다.

γ (r, s) = (1 - ρ) \cdot τ (r, s) + ρ \cdot Δ γ (r, s)

(3)

식 (4)은 전역갱신을 하게 되는 규칙을 설명하고 있다. 여기서 은 nearest neighbor heuristic에 의해 생성된 경로 길이이고 n은 노드 수이다.

\begin{array}{l} γ (r, s) = (1 - α) \cdot τ (r, s) + α \cdot Δ γ (r, s) \\ w h e r e Δ τ (r, s) = {\begin{array}{l} {(L_{g b})}^{- 1} & if (r, s) \in g l o b a l - b e s t - t o u r \\ 0 & o t h e r w i s e \end{array} \end{array}

(4)

5. 연구방법

5.1 기존의 알고리즘

5.1절에서는 기존의 개미집단 최적화 알고리즘에서 개 선된 개미집단 최적화 알고리즘을 구현한다. 문제의 정의 를 위해 <Table 1>과 같은 파라미터를 설정하였다[3, 6].

개미집단 최적화 알고리즘에서 최대 반복횟수(Maximum Number of Iterations)은 1000이고 페로몬이 가지는 가중치(Pheromone Weight)는 1이다. 또한 휴리스틱이 가 지는 가중치(Heuristic Weight) 또한 1이다. 페로몬의 가중 치와 휴리스틱의 가중치는 기존의 값을 사용하였다. 페로 몬의 증발률(Evaporation Rate)은 0.05로 적용하였고, 개미 집단의 크기(Population of Ant)는 실험에 적용되는 도시 들의 수를 따라 적용되도록 하였다[3, 6].

5.2 돌연변이의 적용

유전 알고리즘에 차용한 돌연변이라는 개념을 이용하 여 기존의 개미집단 알고리즘에 쉽게 빠질 수 있는 국부 최적 값에서 벗어나 전역 최적 값으로 수렴할 수 있도록 한다. <Table 2>에서 돌연변이를 적용하기 위한 파라미 터를 설정하였다.

돌연변이를 할 수 있는 확률(MutateProb)은 0.15로 정 하였다. 이는 많은 유전자 알고리즘에서 사용하는 하는 값을 사용하였다[5, 8]. 만일 최적 값이 하나의 값으로 일 정하게 머무르게 된다면 기존의 경로에서 돌연변이를 할 수 있는 것을 찾아서 돌연변이를 진행한다. 돌연변이를 통해 순서를 변경된 경로는 새로운 경로가 되어서 개미 집단 최적화 알고리즘에 다시 적용되어서 기존의 값과 비교하여 진행을 하게 된다.

5.3 연구 프로세스

기존의 개미집단 최적화 알고리즘과 개미집단 최적화 알고리즘에 돌연변이를 적용한 코드를 제작하였다. 언어 는 Mathworks사의 MATLAB 언어를 사용하였다. 본 논 문에서는 TSP Library에서 가져온 대표적인 데이터를 사 용하여 분석을 진행했다. 또한 데이터 별로 다른 도시의 수 때문에 적정한 개미집단의 크기를 정하는 것이 중요 하다고 생각했다. 개미집단의 크기가 커지면 최적의 값 에 수렴하는 속도는 증가하지만 문제를 해결하는데 걸리 는 시간은 크게 증가하게 된다. 이러한 이유 때문에 적정 수의 개미집단의 크기가 중요하다. 또한, 반복 수 역시 커지게 되면 최적의 값에 수렴할 확률이 높아지지만 문 제를 해결하는데 걸리는 시간 역시 크게 증가하게 된다. 따라서 본 논문에서는 개미집단의 크기를 순환 판매원 문제에서 도시 수의 1/4로 설정하였다.

6. 실험 및 결과분석

본 연구에서는 개선된 개미집단 최적화 알고리즘을 이 용해서 도시의 수가 많은 대표적인 문제들을 풀어보았다. 위와 같은 알고리즘을 MATLAB을 통해 구현해보았다. 반 복횟수(Iteration)를 1000번으로 진행하였고, 같은 실험을 10회 반복하여 데이터를 구하였다. 각 도시 사이의 거리는 두 점 사이의 거리를 구하는 공식을 사용하여 거리를 구하 였다. 거리는 A도시에서 B도시를 가는 거리와 B도시에서 A도시를 가는 거리는 같다고 가정하였다. 기존의 개미집 단 최적화 알고리즘과 개선된 개미집단 최적화 알고리즘 과의 비교를 진행하면서 데이터를 모았다. <Table 3>에서 각 문제에서 설정된 도시의 수와 각 문제의 최적 값을 표 를 통해서 정리하였다.

그리고 <Table 4>, <Table 5>, <Table 6>에서는 기존의 알고리즘과 개선된 알고리즘 각각에서 나온 데이터들을 비교하였는데, 비교는 상대 오차율을 통해서 비교하였다.

상대 오차(%) = ((RL-OL)/OL)×100

(5)

식 (5)에서의 RL은 기존의 알고리즘 혹은 개선된 알고 리즘을 통해 나온 값이다. OL은 해당 문제에서의 최적 값을 나타낸다. 상대 오차율을 통해서 알고리즘을 통해 서 나온 두 가지의 값이 어떤 것이 더 오차율이 적다는 것을 확인할 수 있을 것이다.

7. 결론 및 향후 과제

7.1 결론

본 논문에서는 기존의 개미집단 최적화 알고리즘에서 국부 최적 값에서 벗어 날 수 있는 방법을 추가한 새로 운 알고리즘을 제안하였다. 이 방법은 유전 알고리즘에 서 돌연변이라는 방법을 추가하여서 국부 최적 값에서 벗어나 전역 최적 값으로 갈 수 있는 기회를 제공한다.

돌연변이라는 것을 이용하여 기존의 개미집단 최적화 알고리즘이 쉽게 빠질 수 있는 국부 최적 값에서 전역 최적 값으로 갈 수 있도록 하였다. 알고리즘에서 값에 영 향을 줄 수 있는 변수들은 일정한 값으로 고정하여 실험 을 진행하였다. 실험을 통해서 나온 결과 값을 정리하여 <Table 7>에 정리하였다.

<Table 7>을 통해서 확인 할 수 있듯이 기존의 알고리 즘에서의 최적 값에 대한 접근도 보다 개선된 알고리즘에 서 최적 값에 대한 접근도가 더 높다는 것을 확인 할 수 있다. 기존의 알고리즘에서 걸리는 시간과 개선된 알고리 즘의 시간은 비슷한 편이였다. 문제의 크기가 커지면 커질 수록 시간이 오래 걸리는 것을 확인할 수 있었는데 이것은 도시의 개수가 증가하면서 고려해야 하는 것과 비교해야 하는 것들이 기하급수 적으로 증가하게 되면서 시간이 증 가하는 것을 확인할 수 있었다. 도시의 수가 150개의 경우 에는 개선된 개미집단 알고리즘에서 최적 값에 가장 근접 하였고, 도시의 수가 225개의 경우에는 기존의 알고리즘에 서 보다 크게 최적 값에 가까워 진 것을 확인할 수 있었다.

또한, 이러한 실험 결과를 통해서 알 수 있었던 것은 결과 값에 대한 분산 값이 다르다는 것이었다. 도시의 수 가 100, 150, 225개로 늘어나게 되면서 오차율이 점차 증 가되는 것이 아니라, 들쭉날쭉 한 것을 확인할 수 있었 다. 이것은 완전한 정답을 찾는 것이 아니라 최적 값에 근접한 답을 찾는 것을 목표로 하는데, 개미집단 알고리 즘이 갱신하게 되는 페로몬에 따라서 값이 달라질 수 있 다는 것을 알 수 있다.

마지막으로 TSP 문제에서 도시의 수가 증가하는데 반해 최적의 값은 점차 줄어드는 것을 확인할 수 있는데, 이것 은 각 문제에서 각 도시들의 거리에 대한 값이므로 약간 의 차이가 있음을 확인할 수 있었다.

7.2 향후 과제

이번 연구에서 개선된 개미집단 최적화 알고리즘이 좋 은 값을 얻을 수 있었다. 순환 판매원 문제에서 도시의 수 가 급증하게 되면 기존의 개미집단 최적화 알고리즘에서 는 국부 최적 값에 쉽게 빠지게 된다. 이렇게 한번 빠지게 된 국부 최적 값에서 페로몬의 중첩으로 쉽게 빠져나올 수 없었다. 그러나 개선된 개미집단 최적화 알고리즘에서 는 돌연변이라는 것을 통해서 새로운 경로를 풀어보게 되 면서 국부 최적 값에서 벗어나 전역 최적 값으로 갈 수 있는 기회를 얻게 된 것이다. 이러한 것을 반복적으로 진 행하면서 보다 나은 값으로 데이터들이 이동을 할 수 있게 되었고 기존의 해 보다 더 나은 값을 찾을 수 있게 되었다.

알고리즘을 통해 같은 데이터로 문제를 해결하여도 반드시 최적 값에 수렴한다고 할 수는 없다. 물론 반복의 수를 증가시키고 여러 번 반복을 하게 된다면 전역 최적 값은 나오지 않더라도 전역 최적 값에 근접한 답을 얻을 수 있을 것이다. 본 연구에서는 시간적 제약으로 많은 반 복을 진행하지 못하였다. 연구결과는 많은 데이터가 있 게 되면 보다 많은 정보를 얻을 수 있기 때문에 보다 많 은 실험 결과를 통해서 데이터를 보완하는 점이 필요할 것이다. 또한 해결해본 3가지의 문제에서는 차이를 확인 할 수 있었지만, 도시의 수가 더 많아지게 된다면 반복의 수를 증가시켜서 보다 나은 값을 얻도록 해야 할 것이다.

Acknowledgement

This paper is the result of sabbatical year support from Kumoh National Institute of Technology.

Figure

<Figure 1>.

Global Optimum and Local Optimum

<Figure 2>.

New Algorithm Schematic

Table

<Table 1>.

Parameters for ant Colony Optimization Algorithm Implementation

<Table 2>.

Parameters for Applying Mutations

<Table 3>.

The Number of Cities and Optimal Values for Each Problem

<Table 4>.

kro100 Problem Data

<Table 5>.

ch150 Problem Data

<Table 6>.

tsp225 Problem Data

<Table 7>.

tsp225 Problem Data

Reference

Aziz, Z.A., Ant Colony Hyper-heuristics for Travelling Salesman Problem, Procedia Computer Science, Vol. 76, 2015, pp. 534-538.
Cho, S.Y., Chang, H.Y., and Choe, K.G., Ant colony Optimization Heuristic and Graph Optimization Algorithm of an Aisle-Based Order Picking System, Journal of the Korea Society of Supply Chain Management, Vol. 11, No. 2, 2011, pp. 13-19.
Colorni, A., Dorigo, M., and Maniezzo, V., Distributed Optimization by Ant Colonies, actes de la première conférence européenne sur la vie artificielle, Elsevier Publishing, 1992, pp. 134-142.
Hong, S.M., Lee, Y.A., and Chung, T.C., Efficient Path Method using Ant Colony System in Traveling Salesman Problem, Journal of KISS : Software and Application, Vol. 30, No. 9·10, 2003, pp. 862-866.
Kim, I.K. and Youn, M.Y., Improved Ant Colony System for the Traveling Salesman Problem, The KIPS transactions. Part B, Vol. 12, No. 7, 2005, pp. 823-828.
Kim, J.S., Jeong, J.Y., and Lee, J.H., Optimizing Work- In-Process Parameter using Genetic Algorithm, Journal of Society of Korea Industrial and Systems Engineering, 2017, Vol. 40, No. 1, pp. 79-86.
Kim, Y.J. and Cho S.B., An Improved Cultural Algorithm with Local Search for Traveling Salesman Problem, Korea Information Science Society, 2008, pp. 267-271.
Lee, K.K., Han, S.K., and Lee, S.W., A Genetic Algorithm for the Traveling Salesman Problem, Journal of The Korea Information Science Society, Vol. 22, No. 4, 1995, pp. 559-566.
Lee, K.M. and Lee K.M., A Genetic Algorithm for Traveling Salesman Problem with Precedence Constraints, Journal of KISS(A) : Computer System and Theory, Vol. 25, No. 4, 1998, pp. 362-368.
Lee, S.G. and Kang, M.J., Ant Colony System for solving the traveling Salesman Problem Considering the Overlapping Edge of Global Best Path, Journal of the Korea Society of Computer and Information, Vol. 16, No. 3, 2011, pp. 203-210.
Lee, S.U., Polynomial Time Algorithm of a Traveling Salesman Problem, Journal of the Korea Society of Computer and Information, Vol. 18, No. 12, 2013, pp. 75-82.
Yan, Y.Z. and Sohn H.S., German Reyes, A modified ant system to achieve better balance between intensification and diversification for the traveling salesman problem, Applied Soft Computing, Vol. 60, 2017, pp. 256-267.