[논문]게임 환경에서의 유전 알고리즘과 인공신경망을 이용한 경로탐색에 관한 연구

오동화

[국내논문] 게임 환경에서의 유전 알고리즘과 인공신경망을 이용한 경로탐색에 관한 연구
A Study on Pathfinding in Game Environment Using Genetic Algorithm and Neural Network 원문보기

오동화 (고려대학교 컴퓨터정보통신대학원 디지털미디어공학과)

진화 알고리즘과 인공신경망은 생물학에서 비롯되어 컴퓨터과학 분야에서 응용되고 있는 문제해결 방법이다. 본 연구는 게임 환경에서 크기를 자율적으로 설정하여 생성할 수 있는 미로를 구성하고, 주어진 미로의 시작점으로부터 목적지까지 유전 알고리즘과 인공신경망을 이용하여 경로탐색을 하는 것에 대한 연구이다. 자동 생성된 미로가 특정 크기 이상으로 커지게 되면, 진화 알고리즘은 무작위적인 값에 의해서 결정되는 것으로 수렴한다는 결론을 얻었고, 인공신경망을 이용한 결과는 진화알고리즘 보다 미로의 경로탐색 문제해결에 적합한 결과를 보여주었다. 또한 어떤 방향이 최적경로인지 아닌지를 미리 알 수 있는 특수한 조건에서는 각 유전인자를 최적값인지 아닌지 표현하는 방법으로 효율적인 진화 알고리즘을 사용할 수 있다는 것을 제안하였다.

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

즉, 어떤한 알고리즘은 그 아이디어가 실제적인 각각의 문제해결에 있어서는 각기 다른 적용 방법이 필요하게 되는데, 특히 생물학적인 아이디어를 모델링 한 이 두 알고리즘은 파라미터나 주어진 과제에 대한 조건설정이 미치는 영향이 긴밀하다고 할 수 있다. 본 연구에서는 평면상 미로탐색의 문제에서의 진화 알고리즘과 인공신경망을 사용한 학습 기법을 적용해 보고, 이를 연구해 주어진 과제의 복잡성과 알고리즘의 성능 그리고 그 상관관계를 알아보고자 한다.

제안 방법

인공 신경망은 퍼셉트론을 기본으로, 환경정보가 받아들여지는 Input Layer 그리고 어떤 방향으로 이동하게 될 것인가를 결정하도록 결과값을 출력할 수 있는 Output Layer 그리고 두 층의 사이에 Hidden Layer를 각각 24개의 퍼셉트론으로 구성하여 미로에 대한 최적경로를 탐색하도록 하였고, 특히 환경정보는 5X5 크기만큼 받아들여 현재 위치를 중심으로 상하좌우 그리고 그 상하좌우의 상하좌우를 고려하여 어떤 방향으로 갈 것인지를 판단하도록 하였으며, 결과값과 기대되는 최적경로의 방향이 같은지 다른지를 역전파를 통해 가중치 조절을 하는 방식으로 설계하였고, 이 때 기대되는 최적경로는 상하좌우의 인접한 공간이 빈칸이고 그 칸의 상하좌우가 또다시 빈칸이면 높은 우선순위를, 그리고 여러개의 빈칸이 있을 때에는 방문하지 않은 빈칸에 우선순위를, 똑같은 방문 횟수라면 우측 하방에 위치한 목적지와 가까울수록 우선순위를 주는 방법을 사용했다.
진화 알고리즘으로 미로탐색을 하는 초기 조건은 미로 크기 15, population size 40, 교배는 랭킹선택의 방법으로, 그리고 교배확률을 75%, 돌연변이 확률은 2.5%로 설정하여 목적지에 도달하면 루프가 종료하도록 설정하였다.

성능/효과

조건을 달리하여 상위 유전자의 교배 가중치를 늘리고, population size는 80, 교배확률은 75%, 돌연변이는 3%, 그리고 해결하고자 하는 문제의 특성을 감안하여 최적경로를 상대적으로 많이 가지고 있는 최상위 랭크의 유전자를 8%의 확률로 중간급 랭커들과 교배하였다. 그 결과 탐색거리의 교착은 11~13칸에서 이루어졌고, 5~7크기의 정사각형 미로에서는 수백세대 내에 목적지에 도달하는 확률도 약 30~50%정도로 그 경우를 쉽게 볼 수 있었다.
실험결과 제안한 인공 신경망의 방법에서는 현재위치에서의 환경정보를 받아들인 후 적절한 가중치 조절을 한 후에는 주어진 정보 안에서 최적의 이동방향을 제시하였고, 진화 알고리즘에서 보여준 교착없이 목적지까지 도달하는 결과를 보여주었다.
실험조건 중 각 유전인자가 표현하는 것을 현재 위치에서의 이동방향으로부터, 최적경로인지 아닌지를 표현하는 정보로 바꾸어 4의 승수였던 유전자 표현 가능범위를 2의 승수로 현저하게 줄여보았다. 미로 크기 7~17사이에서 실험한 결과 수십세대 안에 목적지에 도착하는 모습을 보여 주었다.
조건을 달리하여 상위 유전자의 교배 가중치를 늘리고, population size는 80, 교배확률은 75%, 돌연변이는 3%, 그리고 해결하고자 하는 문제의 특성을 감안하여 최적경로를 상대적으로 많이 가지고 있는 최상위 랭크의 유전자를 8%의 확률로 중간급 랭커들과 교배하였다. 그 결과 탐색거리의 교착은 11~13칸에서 이루어졌고, 5~7크기의 정사각형 미로에서는 수백세대 내에 목적지에 도달하는 확률도 약 30~50%정도로 그 경우를 쉽게 볼 수 있었다.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증

[국내논문] 게임 환경에서의 유전 알고리즘과 인공신경망을 이용한 경로탐색에 관한 연구
A Study on Pathfinding in Game Environment Using Genetic Algorithm and Neural Network 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper

문제 정의

제안 방법

성능/효과

이 논문을 인용한 문헌

관련 콘텐츠

원문 보기

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

[국내논문] 게임 환경에서의 유전 알고리즘과 인공신경망을 이용한 경로탐색에 관한 연구 A Study on Pathfinding in Game Environment Using Genetic Algorithm and Neural Network 원문보기

초록 용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

제안 방법

성능/효과

이 논문을 인용한 문헌

관련 콘텐츠

원문 보기

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

[국내논문] 게임 환경에서의 유전 알고리즘과 인공신경망을 이용한 경로탐색에 관한 연구
A Study on Pathfinding in Game Environment Using Genetic Algorithm and Neural Network 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper