선택한 단어 수는 입니다.
최소 단어 이상 선택하여야 합니다.
최소 단어 이상 선택하여야 합니다.
선택한 단어 수는 30입니다.
최대 10 단어까지만 선택 가능합니다.
최대 10 단어까지만 선택 가능합니다.
문제 정의
- 그러나 아크 중심의 문제인 URPP에서는 아크에서의 라우팅 방향이 결정되어 있지 않기 때문에 TSP과 같은 디코딩 방법을 사용할 수 없다. 따라서 본 논문에서는 그래프 변환에 의한 URPP의 염색체 디코딩 방법을 제안한다.
- 따라서 본 논문에서는 휴리스틱 알고리즘들 중 유전 알고리즘을 이용한 무향 그래프에서의 RPP 문제 해법을 제안한다. 노드 중심의 TSP 문제와는 달리 아크 중심의 RPP 문제에서는 아크의 라우팅 방향을 고려해야 하기 때문에 TSP에 적용되는 유전 알고리즘으로는 해를 구하기 힘들다.
- 또한, 실제 도로 및 통신 네트워크 상에서 다양한 제약 조건을 고려한 다중목적 최적화 문제에 본 논문에서 제안한 알고리즘을 적용하고 그 성능을 분석하고자 한다.
- 본 논문에서 그래프 변환에 의한 디코딩 알고리즘을 제안하였으며, 기존 연구의 문제점을 해결할 수 있었다. 실험은 기존 방법[7]에서 적용한 10개의 RPP 문제에 대해 본 논문에서 제안한 알고리즘을 적용하여 실시하였다.
- 따라서 무향 RPP 문제에서는 A'의 크기가 커짐에 따라 해 공간이 기하급수적으로 늘어나기 때문에 다항함수시간 (Polynomial Time) 내에 최적 해를 구하기 힘들다. 본 논문에서는 NP-Complete 문제에 많이 적용되는 휴리스틱 알고리즘 중 유전 알고리즘을 적용한 무향 RPP의 해법을 제안하였다. 특히, 아크 중심의 RPP 문제는 노드 중심의 TSP와는 달리 아크의 라우팅 방향에 대한 정보가 필요하므로 염색체 구성이나 디코딩 과정이 복잡하다.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.