배치 평가를 통한 자동 알고리즘 설계의 속도 향상: 개미집단 최적화를 위한 유전 프로그래밍 사례 연구
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배 더 빠릅니다.