Daily Arxiv

전 세계에서 발간되는 인공지능 관련 논문을 정리하는 페이지 입니다.
본 페이지는 Google Gemini를 활용해 요약 정리하며, 비영리로 운영 됩니다.
논문에 대한 저작권은 저자 및 해당 기관에 있으며, 공유 시 출처만 명기하면 됩니다.

A Preprocessing Framework for Efficient Approximate Bi-Objective Shortest-Path Computation in the Presence of Correlated Objectives

Created by
  • Haebom

저자

Yaron Halle, Ariel Felner, Sven Koenig, Oren Salzman

개요

본 논문은 상관관계가 있는 두 개의 상충되는 목적 함수를 최적화하는 이중 목적 최단 경로(BOSP) 문제를 다룬다. 실제 도로 네트워크에서 여행 시간과 연료 소비량처럼 양의 상관관계를 갖는 두 목적 함수를 최적화하는 경우가 흔하다. 기존의 BOSP 솔버는 계산 복잡도가 높기 때문에, Apex 와 같은 근사 알고리즘이 사용된다. 본 논문에서는 목적 함수 간의 상관관계가 높을수록 Pareto 최적 해 집합이 하나의 해로 수렴하는 점에 착안하여, 상관관계를 활용한 효율적인 알고리즘을 제안한다. 그래프 클러스터링 알고리즘에서 영감을 얻어, 전처리 단계에서 상관된 클러스터를 식별하고 새로운 그래프 표현을 생성하여 Apex 알고리즘을 일반화함으로써 DIMACS 데이터셋에서 최대 5배 빠른 성능을 달성하였다. 이는 이중 목적 탐색에서 상관관계를 효율적이고 효과적으로 활용하면서 해의 질에 대한 이론적 보장을 제공하는 최초의 알고리즘이다.

시사점, 한계점

•
시사점:
◦
상관관계가 있는 목적 함수를 갖는 BOSP 문제에 대한 효율적인 알고리즘을 제시한다.
◦
그래프 클러스터링 기법을 활용하여 기존 알고리즘(A*pex)의 성능을 향상시킨다.
◦
DIMACS 데이터셋을 이용한 실험 결과를 통해 알고리즘의 효율성을 검증한다.
◦
해의 질에 대한 이론적 보장을 제공한다.
•
한계점:
◦
제안된 알고리즘의 성능 향상은 상관관계가 높은 경우에 국한될 수 있다.
◦
DIMACS 데이터셋 외 다른 데이터셋에 대한 실험 결과가 제시되지 않았다.
◦
다중 목적 함수(bi-objective 이상) 문제에 대한 일반화 가능성이 명확하지 않다.
👍
Made with Slashpage