유전자 알고리즘을 이용한 경유횟수 제약이 있는 최단 경로 탐색
A Search of the Shortest Route with a Limit on a Number of Transfer using Genetic Algorithm
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
현재 인공지능 게임에서 지능 캐릭터의 주된 역할은 캐릭터의 행동을 보다 영리하고 흥미를 더해주는 기능 위주로 구현되고 있다. 또, 지능 캐릭터의 행동과 이동에 인공지능을 적용하려면 인공지능 처리에 시간을 단축하여야 한다. 이러한 이유는 인공지능 처리 외에 지능이 적용된 캐릭터를 시각화하여 출력하는데 시간이 소요되기 때문이다. 본 연구에서는 유전자 알고리즘을 이용하여 경유횟수 제약이 있는 최소비용 스패닝 트리를 탐색하는 방법을 제안하였다. 유전자 알고리즘에서 선택 방법은 룰렛 선택을 사용하였고, 교배는 균등교배를 적용하였다. 최적의 파라미터가 다음 세대에 유전되도록 엘리트 조존 전략을 적용하여 탐색시간을 단축하였다. 진화 알고리즘에서 트리를 인코딩하는데 효과적인 방법으로 널리 사용되고 있는 Dandelion Code를 사용하였다 실험 결과 정점수가 50, 60, 70, 80일 때 경유 횟수 제약을 3과 5로 하여 스패닝 트리의 비용과 시간을 비교하였다. 정점수가 80, 경유횟수가 5일 때 0.161초가 빠른 시간내에 경로를 탐색하였다.
Abstract
The major role of intelligent character in an artificial intelligence game is to be smarter and to add more interest on character behaviors. Moreover, to apply artificial intelligence on behaviors and movements of intelligent characters, the time to process artificial intelligence should be shortened because even without the process of artificial intelligence, it takes time to visualize and print out a character with intelligence. In this study, the method that searching a spanning tree with the lowest cost which is limited in a number of transfer by a using genetic algorithm is suggested. In genetic algorithm, a roulette selection was chosen to be the selection method, and hybridization method of uniform crossover was applied. The elite conservation strategy for throwing back the optimal parameter to the following generation was applied to shorten the searching time. The Dandelion Code, an effective method to encode a tree in the evolution algorithm, was used. As a result of experiment, when the definite number was 50, 60, 70, and 80, the number of transfer limitation was 3 and 5 to compare the cost and time of spanning tree. When the definite number was 80 and the number of transfer was 5, the route was searched 0.161 seconds earlier.
참고문헌 (15)
- B. Y. Wu, "Spanning trees and optimization problems" (2004), Chapman & Hall
- F. Rothlauf, "Pruefernumbers and genetic algorithms: A lesson how the low locality of an encoding can harm the performance of GAs", Lecture Notes in Computer Science, 1917, Proc. PPSN VI, pp.395~404 (2000)
- S. M. Elsayed, "A new genetic algorithm for solving optimization problems", Eng. Appl. Artif. Intell, 27, pp.57~69 (2014)
- M. Camilleri, "Parameter optimization in decision tree learning by using simple genetic algorithms", WSEAS Transactions on Computers, 13, pp.582~591 (2014)
- K. L. Sadowski, "On the usefulness of linkage processing for solving MAX-SAT", Proceedings of the 15th Annual Conference on Genetic and Evolutionary Computation, pp.853~860 (2013), ACM
- E. B. Thompson, "The application of evolutionary algorithms to spanning tree Problems", Ph.D., pp.2003
- D. Kniazew, "A competent genetic algorithm for solving permutation and scheduling problems" (2002), Kluwer Academic Publishers
- J. E. Laird, "Using a computer game to develop advanced AI", IEEE Computer (2001)
- S. Woodcock, "Game AI : The state of the industry", Gamasutra Magazine, 1 (2000)
- M. van Lent, "Developing an artificial intelligence engine", Proc. of the Game Developers Conference, pp.577~588 (1999)
- Learning models of opponent's strategy in game playing, "D. Carmel", CIS, ~, pp.CIS Report #9318 (1993)
- D. Whitley, "An overview of evolutionary algorithms", Journal of Information and Software Technology, 43, pp.817~831 (2001)
- E. Thompson, "From the dandelion code to the rainbow code; A class of bijective spanning tree representations with linear Complexity and bounded locality", IEEE Trans. on Evolutionary Computation, 10(2), pp.108~123 (2006)
- E. Thompson, "The dandelion code: a new coding of spanning trees for genetic algorithms", IEEE Trans. Vol. Comput., 11, pp.91~100 (2007)
- M. Imase, "Dynamic steiner tree problem", SIAM Journal of Discreate Mathematics, 4, pp.369~384 (1991)