유전자 알고리즘을 이용한 지능 캐릭터의 경로 탐색에 관한 연구

국문 초록 (Abstract)

본 논문에서는 유전자 알고리즘을 이용하여 액션 게임에서 지능 캐릭터의 경로 탐색 방법을 제안하였다. 실험방법으로는 유전자 알고리즘의 특성을 살려 이동 캐릭터가 최단 경로를 선택 할 뿐만 아니라 최적경로 탐색이 가능하도록 하였다. 이 때 염색체의 코드화를 그대로 적용할 경우 많은 치사 유전자가 발생하는데 이 문제를 DNA의 행동 특성의 스플라이싱 방법을 이용하여 해결하였다. 탐색 과정에서 여러 개의 후보 해를 생성하는 유전자 알고리즘의 특징을 이용해서 최단 경로 이외에 최적 경로를 1회의 처리로서 지능 캐릭터가 경로를 탐색하였다.

다국어 초록 (Multilingual Abstract)

In this paper, I suggested a way for searching a path of the intelligent character in an action game by using a genetic algorithm. This realized the algorithm which enables not only to chose the nearest path but also to search the optimum path by using genetic algorithm. In this case, if the codes of chromosomes are applied as they are, a lot of lethal genes could occur. In order to solve such a problem, I used a splicing method, one of the DNA's behavior characteristics. The intelligent character searched out a optimum pass as well as a shortcut path with one treatment by using the characteristic of a genetic algorithm which generates multiple candidate solutions in the search process.

참고문헌 (Reference)

1 Grefenstette, J.J., Lawrence Erlbaum Associates 1985

2 조병헌, "지능형 게임 캐릭터를 위한 학습 및 적응 방법에 관한 연구" 국민대학교 2005

3 이면섭, "유전자 알고리즘을 이용한 대전형 액션게임의 지능캐릭터" 한국정보처리학회 12 (12): 329-336, 2005

4 이면섭, "대전형 액션 게임에서 에너지 점수를 도입한 지능 캐릭터" 한국정보처리학회 13 (13): 449-456, 2006

5 "http://en.wikipedia.org/wiki/Splicing_(genetics)"

6 Barbara Merry, "International Marine Publishing] The Splicing Handbook: Techniques for Modern and Traditional Ropes, Second Edition" International Marine Publishing 2000

7 Laura Barbulescu, "Dynamic Representations and Escaping Local Optima: Improving Genetic Algorithm and Local Search" 879-884, 2000

8 Darrell Whitley, "An Overview of Evolutionary Algorithms" 43 : 817-831, 2001

9 E. W. Dijkstra, "A note on two problems in connection with graphs" 1 : 269-271, 1959