선택한 단어 수는 입니다.
최소 단어 이상 선택하여야 합니다.
최소 단어 이상 선택하여야 합니다.
선택한 단어 수는 30입니다.
최대 10 단어까지만 선택 가능합니다.
최대 10 단어까지만 선택 가능합니다.
문제 정의
- index를 이용한 부분은 본 논문에서 적용한 유전자 알고리즘에서 적합도가 높은 개체일수록 다음세대를 생성할 수 있는 확률이 높기 때문이다. 따라서 개체가 도출된 것은 부모 개체가 우수한 개체이고 가장 적합한 개체가 선택된 것으로 본 논문에서는 정의하여 도출된 개체의 index를 이용하여 최적 경로를 탐색하였다. 그림 3은 단순 A*을 이용한 순차 방법과 제안된 방법, 랜덤 방법 간의 경로 탐색 결과이다.
- 따라서 본 논문에서는 A*와 유전자 알고리즘을 이용하여 모든 대상 노드를 탐색하여 최적의 경로를 탐색하는 방법을 제안한다. 최적의 경로 탐색 방법의 순서와 개요도는 그림 1과 같다.
- 본 논문에서는 출발지 노드부터 모든 노드들을 탐색하면서 최적 경로를 탐색하는 방법을 제안하였다. 본 논문에서는 최적의 경로를 탐색하기 위해서 최적화 방법중의 하나인 유전자 알고리즘을 적용하였다.
제안 방법
- 계산된 거리값을 이용하여 개체를 생성하였고 선택 연산과 교차 연산을 적용하여 우수한 개체를 생성하였고 적합도 평가함수를 적용하여 적합도를 계산하였다. 계산된 적합도가 조건에 만족되면 중간 경로의 노드를 도출하여 출력노드로 선택하고, 다음 출력 노드를 선택하기 위한 출발지점의 노드로 설정하였다. 이러한 과정들을 반복하여 최적화된 출력 노드를 도출하는 효율적인 경로 탐색 방법을 제안하였다.
- 교차 연산에서는 두 개의 개체를 교배하여 다음 세대의 개체를 생성한다. 그리고 새로운 개체는 각각의 부모 개체로부터 서로 중복되지 않는 위치의 유전자를 받아 새로운 유전자를 구성한다. 유전 알고리즘의 교차연산은 부모 해의 유전자들을 서로 교차시켜서 자식 해를 생성한다.
- 본 논문에서 제안한 방법은 출발지 노드 및 중간 노드의 거리 값을 A* 알고리즘을 적용하여 거리 값을 계산하였다. 그리고 유전자 알고리즘에 이용하여 최적의 경로를 탐색하였다. 제안된 방법은 A* 알고리즘으로 계산된 거리 값을 이용하여 개체를 생성한 후, 선택 연산을 적용하여 적합도를 구하고 교배 연산에 적용하여 새로운 개체를 생성하였다.
- 그 이유는 경험적인 특성에 따라서 최단 경로가 아닌 근사 경로를 탐색하거나 탐색되지 않았던 지점으로 다시 탐색을 반복하는 경우에는 탐색 시간이 많이 소요된다. 따라서 본 논문에서는 단순히 A* 알고리즘을 적용하여 순차적으로 경로를 탐색하였을 때와 제안된 경로 탐색 방법을 적용하여 최적의 경로를 탐색하였을 때를 비교한다. 제안된 경로 탐색 방법에는 최적화 방법 중의 하나인 유전자 알고리즘을 적용하여 모든 노드들을 최적으로 탐색하도록 한다.
- 그러나 모든 해에 대해 교차 연산을 수행하는 과정에서 우수한 해가 다른 해와의 교배를 통해서 우수성이 소멸되어 세대의 최적의 우수한 해를 구할 수 없는 경우가 발생할 수 있다. 따라서 제안된 방법에서는 모든 해에 대해 교차 연산을 수행하지 않고 개체의 2/3이후지점에 대해서만 교차 연산을 실행한다.
- 일반적으로는 가장 좋은 해의 순으로 선택될 확률을 높게 부여하는 방법이 널리 사용되고 있으며 추가적으로 유전 알고리즘의 성능을 향상시키는 방법으로 엘리트주의(elitism)가 있다. 따라서 제안된 방법에서는 적합도가 가장 좋은 염색체가 선택되도록 확률을 가장 높게 설정하고 확률적으로 염색체를 선택하는 방법을 이용한다. 그리고 적합도가 가장 높은 상위 2개의 염색체를 보존한다.
- 본 논문에서 제안한 방법은 출발지 노드 및 중간 노드의 거리 값을 A* 알고리즘을 적용하여 거리 값을 계산하였다. 그리고 유전자 알고리즘에 이용하여 최적의 경로를 탐색하였다.
- 본 논문에서는 Intel(R) Core(TM) i5 CPU @2.80GHz 와 8.00GB RAM이 장착된 PC상에서 VisualStudio 2013 C#으로 제안된 방법을 구현하여 실험하였다.
- 본 논문에서의 유전자 알고리즘은 선택, 교차, 변이연산으로 구성된다. 유전자 알고리즘의 순서도는 그림2와 같다.
- 제안된 방법은 A* 알고리즘으로 계산된 거리 값을 이용하여 개체를 생성한 후, 선택 연산을 적용하여 적합도를 구하고 교배 연산에 적용하여 새로운 개체를 생성하였다. 새로 생성된 개체들을 적합도 평가함수에 적용하여 적합도가 만족하면 최적의 경로를 도출하였다. 최적의 경로를 도출하는 과정에서 적합도 조건에 만족한 개체의 index를 이용하여 최적 경로 노드로 선택하였다.
- 출발지 노드에서 중간 노드들의 거리를 A* 알고리즘으로 계산한 후, 계산된 거리값을 이용하여 개체를 생성한다. 생성된 개체를 유전자 알고리즘의 선택 연산과 교차 연산을 이용하여 새로운 개체를 생성한다. 생성된 개체를 적합도 조건에 적용하여 최적의 경로를 탐색한다.
- 생성된 개체를 유전자 알고리즘의 선택 연산과 교차 연산을 이용하여 새로운 개체를 생성한다. 생성된 개체를 적합도 조건에 적용하여 최적의 경로를 탐색한다.
- 계산된 적합도가 조건에 만족되면 중간 경로의 노드를 도출하여 출력노드로 선택하고, 다음 출력 노드를 선택하기 위한 출발지점의 노드로 설정하였다. 이러한 과정들을 반복하여 최적화된 출력 노드를 도출하는 효율적인 경로 탐색 방법을 제안하였다. 실험에서 알 수 있듯이 제안된 방법이최적의 거리를 탐색하는데 있어서 효율적인 것을 확인하였다.
- 이러한 문제점을 개선하기 위해 본 논문에서는 α값을 0.1씩 감소시켜 적합도의 평가기준을 설정한다.
- 따라서 본 논문에서는 단순히 A* 알고리즘을 적용하여 순차적으로 경로를 탐색하였을 때와 제안된 경로 탐색 방법을 적용하여 최적의 경로를 탐색하였을 때를 비교한다. 제안된 경로 탐색 방법에는 최적화 방법 중의 하나인 유전자 알고리즘을 적용하여 모든 노드들을 최적으로 탐색하도록 한다. 출발지 노드에서 중간 노드들의 거리를 A* 알고리즘으로 계산한 후, 계산된 거리값을 이용하여 개체를 생성한다.
- 제안된 방법에서는 개체들의 값이 증가하여도 최적의 해를 구하도록 하기 식(3)을 개체들에 적용하여 적합도를 계산한다.
- 그리고 유전자 알고리즘에 이용하여 최적의 경로를 탐색하였다. 제안된 방법은 A* 알고리즘으로 계산된 거리 값을 이용하여 개체를 생성한 후, 선택 연산을 적용하여 적합도를 구하고 교배 연산에 적용하여 새로운 개체를 생성하였다. 새로 생성된 개체들을 적합도 평가함수에 적용하여 적합도가 만족하면 최적의 경로를 도출하였다.
- Step 3. 종료 조건을 검증한다.
- 새로 생성된 개체들을 적합도 평가함수에 적용하여 적합도가 만족하면 최적의 경로를 도출하였다. 최적의 경로를 도출하는 과정에서 적합도 조건에 만족한 개체의 index를 이용하여 최적 경로 노드로 선택하였다. index를 이용한 부분은 본 논문에서 적용한 유전자 알고리즘에서 적합도가 높은 개체일수록 다음세대를 생성할 수 있는 확률이 높기 때문이다.
- 최적의 경로를 탐색하기 위해 각 노드간의 거리를 가중치 값으로 계산하여 유전자 알고리즘의 개체를 생성한다. 개체의 생성은 식(1)을 이용하여 가중치 값에 해당하는 개체를 생성한다.
- 제안된 경로 탐색 방법에는 최적화 방법 중의 하나인 유전자 알고리즘을 적용하여 모든 노드들을 최적으로 탐색하도록 한다. 출발지 노드에서 중간 노드들의 거리를 A* 알고리즘으로 계산한 후, 계산된 거리값을 이용하여 개체를 생성한다. 생성된 개체를 유전자 알고리즘의 선택 연산과 교차 연산을 이용하여 새로운 개체를 생성한다.
데이터처리
- 제안된 방법은 최적의 경로를 탐색하기 위해서 가중치 값으로 A* 알고리즘을 이용하여 거리를 계산하였다. 계산된 거리값을 이용하여 개체를 생성하였고 선택 연산과 교차 연산을 적용하여 우수한 개체를 생성하였고 적합도 평가함수를 적용하여 적합도를 계산하였다. 계산된 적합도가 조건에 만족되면 중간 경로의 노드를 도출하여 출력노드로 선택하고, 다음 출력 노드를 선택하기 위한 출발지점의 노드로 설정하였다.
이론/모형
- 본 논문에서는 출발지 노드부터 모든 노드들을 탐색하면서 최적 경로를 탐색하는 방법을 제안하였다. 본 논문에서는 최적의 경로를 탐색하기 위해서 최적화 방법중의 하나인 유전자 알고리즘을 적용하였다. 제안된 방법은 최적의 경로를 탐색하기 위해서 가중치 값으로 A* 알고리즘을 이용하여 거리를 계산하였다.
- 유전자 알고리즘을 적용하기 위해 각 노드 간에 거리를 A* 알고리즘을 이용하여 계산한다. 이때 각 노드간거리를 계산할 때에는 식 (1)을 적용하여 거리값을 계산한다.
- 본 논문에서는 최적의 경로를 탐색하기 위해서 최적화 방법중의 하나인 유전자 알고리즘을 적용하였다. 제안된 방법은 최적의 경로를 탐색하기 위해서 가중치 값으로 A* 알고리즘을 이용하여 거리를 계산하였다. 계산된 거리값을 이용하여 개체를 생성하였고 선택 연산과 교차 연산을 적용하여 우수한 개체를 생성하였고 적합도 평가함수를 적용하여 적합도를 계산하였다.
성능/효과
- 이러한 과정들을 반복하여 최적화된 출력 노드를 도출하는 효율적인 경로 탐색 방법을 제안하였다. 실험에서 알 수 있듯이 제안된 방법이최적의 거리를 탐색하는데 있어서 효율적인 것을 확인하였다. 향후 연구 방향은 현재에 적용된 A* 알고리즘 대신에 Deep PCM 알고리즘과 유전자 알고리즘을 적용하여 현재의 탐색 성능을 더 개선하여 내비게이션에 적용할 수 있도록 할 것이다.
- 05 이하이다[6, 7]. 제안된 방법에서는 0.05%확률로 변이 연산을 수행하여 지역 최적해에 위치하는 경우를 방지한다.
- 표 3은 A* 방법을 적용한 순차방법과 랜덤방법 및 제안한 방법 간의 총 탐색 거리를 비교하여 나타내었다. 표 3에서와 같이 제안한 방법이 A* 알고리즘을 이용한 순차 방법과 랜덤 방법보다 총 탐색 거리 값이 적어서 최적 경로 탐색에 있어서 제안된 방법이 효율적인 것을 확인할 수 있다.
후속연구
- 실험에서 알 수 있듯이 제안된 방법이최적의 거리를 탐색하는데 있어서 효율적인 것을 확인하였다. 향후 연구 방향은 현재에 적용된 A* 알고리즘 대신에 Deep PCM 알고리즘과 유전자 알고리즘을 적용하여 현재의 탐색 성능을 더 개선하여 내비게이션에 적용할 수 있도록 할 것이다.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.