[논문]유전 알고리즘을 이용한 최적 경로 탐색

김경남; 조민석; 이현경

유전 알고리즘을 이용한 최적 경로 탐색
Searching optimal path using genetic algorithm 원문보기

김경남 (한국과학기술원 해양시스템공학과) , 조민석 (한국과학기술원 기계공학과) , 이현경 (한국기술교육대학교 메카트로닉스 공학부)

In case of the big city, choosing the adequate root of which we can reach the destination can affect the driver's condition and driving time. so it is quite important to find the optimal routes for arriving the destination as considering the factors, such as driving conditions or travel time and so on. In this paper, we develop route choice model with considering driving conditions and travel time, and it can search the optimal path which make drivers reduce their fatigues using genetic algorithm.

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

문제 정의

본 논문에서는 16개의 블록이 4x4형태로 배치되어 있고, 이 블록들을 연결하는 40개의 도로들의 통행 시간과 도로 상태 및 도로 특성을 고려하여 경로선택모형을 만들었고, 이를 기반으로 유전 알고리즘을 이용하여 운전자의 부담을 최소화할 수 있는 최적경로를 탐색한다.
본 논문에서는 통행에 영향을 주는 도로의 속성을 고려하여 만든 경로 탐색 모델에서, genetic algorithm을 이용하여 최적 경로를 탐색하였다. 2.

가설 설정

그리고 Road12, Road19를 통행 시 자동으로 Road20, Road 27을 각각 통행하는 것으로 가정하였다. 또한 Road35를 ↑방향으로 통행하거나 Road 36을 →방향으로 통행 시, 각각 Road 38과 Road39를 자동으로 통행하도록 가정하였다.
또한 Road35를 ↑방향으로 통행하거나 Road 36을 →방향으로 통행 시, 각각 Road 38과 Road39를 자동으로 통행하도록 가정하였다.
여기서 Road0, Road2, Road6, Road12, Road27, Road33, Road37, Road39는 ↑방향으로만 통행하고, Road1, Road5, Road11, Road19, Road20, Road28, Road34, Road38은 →방향으로만 통행하는 것으로 가정하였다.

제안 방법

Table 1은 genetic algorithm의 chromosome이 의미하는 방향을 보여주고 있다. 교차점에서 다음 도로로 진입하는 경우의 수는 최대 4가지이므로 이를 나타내기 위해 최소 2개의 chromosome이 하나의 방향을 의미하는 것으로 정하였다. 그리고 어느 한 도로를 통행한 후 도로와 도로의 교차지점에 도달하였을 때, 다음 도로로 진행할 수 있는 방향의 경우의 수는 어떤 교차점에 도착하였느냐에 따라 다르게 된다.
이전에 서술한 것처럼, 각 도로의 특성을 나타내는 요소들인 통행 시간과 도로 상태는 따로 자료를 수집하기 어렵거나 많은 시간이 요구되므로 임의로 그 값을 정하였다. 그리고 이 두 요소의 관계를 고려하였을 때, 통행시간에 따른 통행자의 피로도는 도로의 상태의 좋고 나쁜 정도에 비례하여 선형적으로 증가한다고 가정하였으므로, 도로의 특성을 통행 시간과 도로 상태를 곱으로 정하였다.
왜냐하면 도로의 개수가 40개 이므로 최적 경로를 찾는다는 가정 아래에서는 통행자가 40개 이상의 도로를 통과하지 않는다. 따라서 chromosome의 크기는 통행자가 모든 도로를 통행한다는 최악의 경우까지 고려하여 80개로 정하였다. 그리고 mutation과 crossover에 대해서 이들 값들의 설정에 대한 명확한 기준은 찾을 수 없었고, mutation은 0.
그리고 어느 한 도로를 통행한 후 도로와 도로의 교차지점에 도달하였을 때, 다음 도로로 진행할 수 있는 방향의 경우의 수는 어떤 교차점에 도착하였느냐에 따라 다르게 된다. 따라서 교차점들을 4가지 경우로 나누어 각 경우에 따라 chromosome이 의미하는 방향을 각기 다르게 적용시켰다. Figure 1에서 Case 1에 해당하는 교차점은 별 모양에 해당하는 9개의 교차점, Case 2에 해당하는 교차점은 세모 모양에 해당하는 6개의 교차점, Case 3에 해당하는 교차점은 네모 모양에 해당하는 3개의 교차점, Case 4에 해당하는 교차점은 X모양에 해당하는 3개의 교차점이다.
8로 설정하였다. 또한 population size와 generation number는 본 논문에서 수행하고자 하는 genetic algorithm이 많은 시간이 요구하는 복잡한 것이 아니므로, 여러 번 실행시켜 일정한 결과가 나오도록 설정하였다. Genetic algorithm의 objective function은 아래와 같이 나타내었다.
result값은 초기에 0으로 설정되어 있다. 본 논문에서 사용한 Genetic algorithm은 최대값을 찾도록 되어 있기 때문에, 찾아야 하는 최적경로는 가장 작은 피로도를 가지고 있어야 하므로 objective function 값이 음수를 가지도록 하였다. 만약 도로들을 통과한 횟수가 40번을 초과하였을 때는 result값을 -9999로 리턴하도록 설정하여 다음 세대로 해당 population이 전달되지 못하도록 하였다.
따라서 이러한 애로사항이 있는 요소들을 통합하여 하나의 요소로 단순하게 나타내기로 하였다. 본 논문에서는 경로 선택에 영향을 미치는 요소를 통행 시간과 도로 상태 두 가지로 선정하였다.
이전에 서술한 것처럼, 각 도로의 특성을 나타내는 요소들인 통행 시간과 도로 상태는 따로 자료를 수집하기 어렵거나 많은 시간이 요구되므로 임의로 그 값을 정하였다. 그리고 이 두 요소의 관계를 고려하였을 때, 통행시간에 따른 통행자의 피로도는 도로의 상태의 좋고 나쁜 정도에 비례하여 선형적으로 증가한다고 가정하였으므로, 도로의 특성을 통행 시간과 도로 상태를 곱으로 정하였다.

대상 데이터

본 논문의 경로 탐색 모형은 16개의 블록이 4x4 형태로 배치되어 있고, 이 블록들을 연결하는 40개의 도로로 구성되어 있다.

이론/모형

최적 경로 탐색을 위해 Binary Coded Genetic Algorithm을 사용하였다.

성능/효과

본 논문에서는 통행에 영향을 주는 도로의 속성을 고려하여 만든 경로 탐색 모델에서, genetic algorithm을 이용하여 최적 경로를 탐색하였다. 2.3의 두 가지 예제에서도 확인할 수 있듯이, 주로 통행시간과 도로상태를 의미하는 두 속성의 곱이 작은 도로들로 구성된 경로를 최적 경로로 선택하며 성공적으로 최적 경로를 찾아낼 수 있었다.
Genetic algorithm으로 최적 경로 탐색 알고리즘을 만들면서, 이전에는 어렴풋하게만 알며 사용했던 genetic algorithm의 개념을 책을 빌려 공부하면서 더 확실하게 이해할 수 있었다. 그리고 무엇보다 genetic algorithm의 open source중에 하나인 Galib을 기반으로 하여 코드를 만들었기 때문에, C 및 C++을 더 자유롭게 다룰 수 있게 된 계기가 되었다.

후속연구

하지만 최적경로탐색을 위한 알고리즘에는 genetic algorithm보다 더 빠르고 뛰어난 알고리즘이 존재하기 때문에, 경로 탐색 모델을 이보다 더 복잡하게 확장할 경우 보완이 필요할 것으로 판단된다.

핵심어

질문

논문에서 추출한 답변

최적 경로는 무엇인가?

최적 경로는 정해진 기점과 종점을 연결하는 다수의 경로들 중 통행자의 목적을 최적으로 하는 경로이다. 일반적으로 최적경로를 탐색하는 기준에는 통행시간, 통행비용 등 하나의 속성만을 고려하며, 통행자는 자신의 목적에 맞는 경로를 최적경로로 선택하여 이동한다.

통행 시간과 도로 상태는 각각 무엇을 의미하는가?

통행시간은 통행자가 특정 도로를 통과할 때 걸리는 시간을 의미하고, 도로 상태는 통행자가 특정 도로를 통과함으로 인해 받게 되는 피로도의 정도를 나타낸다. 도로 상태에 영향을 주는 것으로는 도로 불량, 도로에서의 차량 사고 여부 등이라고 할 수 있다.

일반적으로 최적경로를 탐색하는 기준에는 무엇이 있는가?

최적 경로는 정해진 기점과 종점을 연결하는 다수의 경로들 중 통행자의 목적을 최적으로 하는 경로이다. 일반적으로 최적경로를 탐색하는 기준에는 통행시간, 통행비용 등 하나의 속성만을 고려하며, 통행자는 자신의 목적에 맞는 경로를 최적경로로 선택하여 이동한다. 그러나 실제로 통행자가 단일 속성만을 고려하여 경로를 선택하는 경우, 통행자의 인식범위를 넘어선 도로불량, 차량사고 등과 같은 요인들이 통행시간 및 운전자의 피로도에 영향을 미치게 된다.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, 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

연합인증

유전 알고리즘을 이용한 최적 경로 탐색
Searching optimal path using genetic algorithm 원문보기

Abstract ▼ AI-Helper

AI 본문요약
AI-Helper

문제 정의

가설 설정

제안 방법

대상 데이터

이론/모형

성능/효과

후속연구

질의응답

이 논문을 인용한 문헌

관련 콘텐츠

원문 보기

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

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

선택된 텍스트

연합인증

유전 알고리즘을 이용한 최적 경로 탐색 Searching optimal path using genetic algorithm 원문보기

Abstract ▼ AI-Helper

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

문제 정의

가설 설정

제안 방법

대상 데이터

이론/모형

성능/효과

후속연구

질의응답

이 논문을 인용한 문헌

관련 콘텐츠

원문 보기

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

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

선택된 텍스트

유전 알고리즘을 이용한 최적 경로 탐색
Searching optimal path using genetic algorithm 원문보기

AI 본문요약
AI-Helper