부분집합 합 문제에서의 유전 알고리즘과 동적 계획법의 성능 비교
Performance Comparison between Genetic Algorithms and Dynamic Programming in the Subset-Sum Problem
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
부분집합 합 문제는 유한개의 정수로 이루어진 집합이 있을 때 이 집합의 부분집합 중에서 그 집합의 원소들의 합이 특정 값이 되는 경우가 있는지를 알아내는 문제로, 잘 알려진 다항식 시간 내에 풀기 어려운 NP-완비 문제이다. 유전 알고리즘은 선택과 교차, 돌연변이 등의 연산을 통해 주어진 문제의 최적해를 구하는 알고리즘이다. 동적 계획법은 주어진 문제를 풀기 위해서 문제를 하나 또는 여러 개의 하위 문제로 나누어 풀이하는 방법이다. 본 논문에서는 부분집합 합 문제를 풀이하는 유전 알고리즘을 설계 및 구현하고, 답을 찾는 데까지 걸리는 시간 성능을 동적 계획법의 경우와 실험적으로 비교하였다. 양의 정수인 원소 개를 가진 집합에서 ‘쉬움’과 ‘어려움’의 난이도를 고려하여 총 개의 문제를 선정하고, 이 문제들을 풀이하는 두 알고리즘의 성능을 비교하는 실험을 진행하였다. 개의 문제 중 개의 문제에서 본 논문에서 제시한 유전 알고리즘은 동적 계획법과 비교하여 약 가 우수한 시간 성능을 보였다.
Abstract
The subset-sum problem is to find out whether or not the element sum of a subset within a finite set of numbers is equal to a given value. The problem is a well-known NP-complete problem, which is difficult to solve within a polynomial time. Genetic algorithm is a method for finding the optimal solution of a given problem through operations such as selection, crossover, and mutation. Dynamic programming is a method of solving a given problem from one or several subproblems. In this paper, we design and implement a genetic algorithm that solves the subset-sum problem, and experimentally compared the time performance to find the answer with the case of dynamic programming method. We selected a total of test cases considering the difficulty in a set with elements of positive number, and compared the performance of the two algorithms. The presented genetic algorithms showed time performance improved by on of problems when compared with dynamic programming.
참고문헌 (10)
- Weisstein, Eric W., "Subset Sum Problen" (2000), Wolfram Research Inc.
- Garey, Michael R., "Computers and Intractability: A Guide to the Theory of NP-Completeness" (2002), W.H. Freeman
- Holland, John H., "Adaptation in Natural and Atificial Systems: an Introductory Analysis with Application to Biology, Control, and Artificial Intelligence" (1975), The University of Michigan Press
- Moon, Byung-Ro, "Easy-to-learn Genetic Algorithm: Evolutionary Approach" (2008), Hanbit Media Publisher
- Bellman, Richard, "Dynamic Programming" (2013), Courier Corporation
- De Jong, Kenneth A., "Using genetic algorithms to solve NP-complete problems", International Conference on Genetic Algorithms, pp.124~132 (1989)
- Hinkemeyer, Brenda, "A genetic algorithm for the longest common subsequence problem", Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation, pp.609~610 (2006)
- Jiménez, Mario J. Pérez, "Solving the subset-sum problem by P systems with active membranes", New Generation Computing, 23(4), pp.339~356 (2005)
- Cho, Hwi-Yeon, "Solving the subset-sum problem using a genetic algorithm", Convergence Research Letter, 3(4), pp.685~689 (2017)
- Martello, Silvano, "Knapsack problems: Algorithms and computer implementations" (1990), Wiley-Interscience