본문으로 건너뛰기
AI NEWS JOURNAL
arXiv cs.DCAI NEWS / JOURNAL

배치 평가를 통한 자동 알고리즘 설계의 속도 향상: 개미집단 최적화를 위한 유전 프로그래밍 사례 연구

arXiv:2611.19751v1 발표 유형: 교차 요약: 평가는 자동 알고리즘 설계의 병목이 되고 있으며, 특히 개미집단최적화(ACO)와 같은 반복 알고리즘의 경우 여러 인스턴스에서 완전히 실행되어야 합니다. 유전프로그래밍으로 설계된 전이 규칙은 각 개미의 구성 상태를 읽으며 매 단계마다 평가되어야 합니다. 그러나 기존 ACO용 GPU 방법들은 고정된 규칙을 사전 계산하고 한 번의 실행에 속한 개미들을 병렬화합니다. 이 문제를 해결하기 위해 우리는 GPU 및 CPU 백엔드를 갖춘 배치 평가 프레임워크인 BlockEval을 제안합니다. GPU 백엔드는 여러 실행을 동시에 처리하며, 각 실행을 하나의 스레드 블록으로 통째로 수행하고 세대별로 하나의 모듈을 컴파일합니다. 개미가 모든 후보 도시를 방문하면, 워프 협력형 대체 경로는 가능한 경우 해당 개미의 워프만 정지시킵니다. 50~1000개의 도시를 가진 여행판매원 문제에서 GPU 백엔드는 32코어 기준 CPU 백엔드보다 4.1~16.5배 더 빠르며, EvoGP+TensorACO-CL보다 11.2~17.8배 더 빠릅니다.

이 언어의 번역이 아직 없어 원문을 표시합니다.

초록: 평가는 자동 알고리즘 설계의 병목으로 떠오르고 있으며, 특히 개미집단최적화(ACO)와 같이 여러 인스턴스에서 완전히 실행되어야 하는 반복 알고리즘의 경우 더욱 그렇습니다. 유전프로그래밍으로 설계된 전이 규칙은 각 개미의 구성 상태를 읽으며 매 단계마다 평가되어야 합니다. 그러나 기존 ACO용 GPU 방법들은 고정된 규칙을 사전 계산하고 한 번의 실행에 대한 개미들을 병렬화합니다. 이 문제를 해결하기 위해 우리는 GPU 및 CPU 백엔드를 갖춘 배치 평가 프레임워크인 BlockEval을 제안합니다. GPU 백엔드는 여러 실행을 동시에 처리하며, 각 실행을 하나의 스레드 블록으로 묶어 전체적으로 실행하고 세대별로 하나의 모듈을 컴파일합니다. 개미가 모든 후보 도시를 방문하면, 워프 협력형 대체 경로는 가능한 경우 해당 개미의 워프만 정지시킵니다. 50~1000개의 도시를 가진 여행판매원 문제에서 GPU 백엔드는 32코어 기준 CPU 백엔드보다 4.1~16.5배 빠르며, EvoGP+TensorACO-CL보다 11.2~17.8배 빠릅니다. 제출 내역 논문 열람: PDF 보기 HTML (실험적) TeX 소스 추가 기능 음성 요약 현재 탐색 컨텍스트: 참고 문헌 및 인용 Google 학술검색 Semantic Scholar 북마크 기관 arXivLabs는 공동 작업자가 당사 웹사이트에서 새로운 arXiv 기능을 직접 개발하고 공유할 수 있도록 하는 프레임워크입니다. arXivLabs를 활용하는 개인과 조직 모두 개방성, 커뮤니티, 우수성, 사용자 데이터 개인정보 보호라는 당사의 가치를 수용하고 동의했습니다. arXiv은 이러한 가치에 헌신하며 이를 준수하는 파트너들과만 협력합니다. arXiv 커뮤니티에 가치를 더할 프로젝트 아이디어가 있으신가요? arXivLabs에 대해 자세히 알아보세요.

자료 출처

원문 읽기 ↗

관련 주제

← 전체 소식 이어 읽기