숫자 모으기 미로 게임을 위한 유전 알고리즘 = Genetic Algorithm for Number Collecting Maze Game

국문 초록 (Abstract)

본 숫자 모으기 미로 게임은 플레이어가 격자형 미로를 이동하며 특정 숫자를 수집하는 게임을 말한다. 숫자모으기 미로 게임은 수리 및 인지 능력 향상을 위한 교육 및 퍼즐 설계 분야에 적용되어 왔으며, 탐욕 알고리즘, 빔탐색, 초쿠다이 탐색 등의 알고리즘 성능 테스트를 위한 벤치마크 문제로서 다양한 연구에 활용되기도 하였다. 본 논문에서는 숫자 모으기 미로 게임에 유전 알고리즘을 적용하기 위한 설계 방법을 제안한다. 유전 알고리즘을 숫자 모으기미로 게임에 적용하기 위한 해 표현법을 제시하고, 교차 연산, 돌연변이 연산 및 선택 연산 등과 같은 유전 연산 설계방법을 제시한다. 간단한 유전 연산자를 적용한 유전 알고리즘은 탐욕 알고리즘 대비 우수한 결과를 보이나, 숫자 모으기 미로 게임에 특화된 빔 탐색 및 초쿠다이 탐색 알고리즘과 대비해서는 열등한 결과를 보인다. 이를 개선하기 위해, 탐욕적 개체를 혼합한 초기화, 엘리트 전략과 토너먼트 전략을 혼합한 선택 전략, 탐색 초기에는 높은 돌연변이 확률을가지고 탐색 말기에는 낮은 돌연변이 확률을 가지는 적응형 돌연변이 등의 유전 알고리즘 강화 기법을 설계한다. 숫자모으기 게임에 적용한 결과, 제안한 강화 유전 알고리즘이 빔 탐색 및 초쿠다이 탐색 알고리즘 대비 우수한 성능을 보여준다.

다국어 초록 (Multilingual Abstract)

The Number Collecting Maze game involves players navigating a grid-shaped maze to collect specific numbers. The Number Collecting Maze game has been applied in educational and puzzle design fields to enhance mathematical and cognitive abilities, and has also served as a benchmark problem for testing the performance of algorithms such as greedy algorithms, beam search, and Chokudai search.
This paper proposes a design method for applying genetic algorithms to the Number Collecting Maze game. We present a solution representation for applying genetic algorithms to the Number Collecting Maze game and present design methods for genetic operations such as crossover, mutation, and selection. The genetic algorithm, employing simple genetic operators, outperform the greedy algorithm but underperform the beam search and Chokudai search algorithms, which are specialized for the Number Collecting Maze game. To improve this, we design genetic algorithm enhancement techniques such as initialization mixed with greedy individuals, selection strategy mixed with elite strategy and tournament strategy, and adaptive mutation that has high mutation probability in the early stage of search and low mutation probability in the late stage of search. When applied to a number-collecting game, the proposed reinforced genetic algorithm shows superior performance compared to the beam search and Chokudai search algorithms.