차량 경로 문제에서 유도 국소 탐색 학습을 위한 행동 기반 니칭 유전 프로그래밍
Genetic Programming with Behaviour-based Niching for Learning Guided Local Search in Vehicle Routing Problems
한국어 초록
유전 프로그래밍 유도 국소 탐색(GPGLS)은 차량 경로를 위한 국소 탐색을 유도하는 효용 함수를 학습한다. 진화하는 프로그램은 서로 다른 탐색 행동을 유발하면서 유사한 적합도를 가질 수 있어, 적합도만으로는 개체군 다양성 관리의 불완전한 기준이 된다. 우리는 국소 탐색 중 수집된 여섯 가지 연산자 수준 기술자로 프로그램을 특성화하는 행동 기반 니칭 GPGLS(BN-GPGLS)를 제안한다. 현 세대 아카이브는 행동 점수의 층에서 적합도 경쟁력이 있고 compact한 대표를 선정한다. 고정 정책은 아카이브 부모를 지속적으로 사용하는 반면, 적응형 정책은 학습 적합도와 표준화된 행동 분산 신호를 사용하여(선택적으로 트리 크기 조건과 함께) 이를 활성화한다. 우리는 생성된 200-고객 인스턴스에서 30회 시드 매칭 실행에 걸쳐 아카이브 없는 GPGLS 대조군 및 적합도 기반 니칭과 네 가지 행동 기반 변형을 비교한다. BN-Adaptive는 별도의 90-인스턴스 모니터링 세트에서 최고의 평균 순위를 달성한다; 집계된 경로 비용 차이는 작다. 다섯 가지 아카이브 정책 모두 GPGLS 대조군보다 낮은 최종 개체군 중앙값 트리 크기를 산출하며, 쌍체 Wilcoxon 비교는 Holm 보정 후에도 유의하게 남는다. 이 결과는 평가된 설정 내에서 유용한 해 품질과 프로그램 크기 간의 트레이드오프를 밝히며, 크기 감소를 행동 표현만으로 귀인하지는 않는다.
원문 초록
Genetic Programming Guided Local Search (GPGLS) learns utility functions that guide local search for vehicle routing. Its evolving programs can have similar fitness while inducing different search behaviour, making fitness alone an incomplete basis for population diversity management. We propose GPGLS with Behaviour-based Niching (BN-GPGLS), which characterises programs through six operator-level descriptors collected during local search. A current-generation archive selects fitness-competitive, compact representatives from strata of a behaviour score. Fixed policies use archive parents continuously, whereas adaptive policies activate them using training-fitness and standardised behaviour-dispersion signals, optionally with a tree-size condition. We compare four behaviour-based variants with a no-archive GPGLS control and fitness-based niching over 30 seed-matched runs on generated 200-customer instances. BN-Adaptive achieves the best descriptive average rank on a separate 90-instance monitoring set; aggregate routing-cost differences are small. All five archive policies produce lower final-population median tree sizes than the GPGLS control, with paired Wilcoxon comparisons remaining significant after Holm adjustment. These results identify useful solution-quality and program-size trade-offs within the evaluated setting, without attributing the size reductions to behaviour representation alone.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2609.24104v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
DCL-GPGLS: 대규모 차량 경로 문제를 위한 유전 프로그래밍 유도 국소 탐색 기반 동적 커리큘럼 학습
DCL-GPGLS: Dynamic Curriculum Learning for Genetic Programming Guided Local Search in Large-Scale Vehicle Routing
유전 프로그래밍 유도 국소 탐색(GPGLS)은 대규모 차량 경로 문제(LSVRP)의 유도 국소 탐색에 사용할 효용 함수(utility function)를 진화시키기 위해 유전 프로그래밍을 활용합니다. 매 세대마다 모든 학습(training) 인스턴스에 걸쳐 모든 GP 개체를 평가(evaluation)하는 것은 비용이 많이 들기 때문에, GPGLS는 통상적으로 작은 인스턴스 배치(batch)로 학습됩니다. 기존의 커리큘럼 기반 GPGLS는 주로 인스턴스 크기에 따라 이러한 배치의 순서를 정합니다. 적응형 커리큘럼 학습 GPGLS(ACL-GPGLS)는 고정된 커리큘럼 단계 간 이동 시점을 조정하여 학습 효율을 개선하지만, 인스턴스 난이도 순서는 여전히 사전에 정의된 상태로 유지됩니다. 본 논문에서는 현재 모집단(population)의 해 품질을 바탕으로 각 학습 인스턴스의 난이도를 추정하고 진화 과정 동안 이를 업데이트하는 DCL-GPGLS를 제안합니다. 이후 각 세대는 계획된 난이도 수준에 근접한 배치를 전달받으며, 동일 인스턴스의 반복 선택을 제한하는 보정이 함께 적용됩니다. CVRPLIB X 세트의 고정된 학습-테스트 분할에 대한 실험 결과, DCL-GPGLS는 6가지 학습 정책 중 가장 우수한 평균 순위와 평균 테스트 비용을 달성함을 보여줍니다. 또한 65개의 미확인(unseen) 테스트 인스턴스 중 36개에서 가장 낮은 평균 비용을 기록했으며, 총 평가자 호출 횟수가 동일한 정적 피드백 기반 커리큘럼과 비교했을 때 6개 인스턴스에서 유의미하게 우수했고 나머지 59개 인스턴스에서는 유의미한 차이가 없었습니다.
SPECS: 종 분화 진화적 회로 합성
SPECS: Speciated Evolutionary Circuit Synthesis
우리는 토폴로지와 사이징 최적화를 동시에 수행하는 자동 아날로그 회로 합성을 위한 유전 알고리즘인 SPECS를 제안한다. SPECS는 신경망 합성을 위해 처음 개발된 진화 알고리즘인 NEAT(NeuroEvolution of Augmenting Topologies)에서 영감을 받았다. 게놈 표현을 재정식화하고 유전 연산자를 아날로그 회로 영역에 맞게 조정함으로써, NEAT의 핵심 원리를 아날로그 회로 합성으로 성공적으로 이식하였다. 회로 특화 배선 제약을 통합하여 진화 과정 전반에 걸쳐 유효하고 물리적으로 의미 있는 설계가 되도록 보장하며, 종 분화(speciation)를 사용하여 집단 다양성을 유지하면서 혁신을 보존한다. 제안 방법을 제곱, 세제곱, 제곱근, 세제곱근 함수로 구성된 일련의 계산 회로 합성 과제에 대해 평가하였다. 실험 결과, SPECS가 모든 과제에서 해 품질과 신뢰성 모두에서 벤치마크 방법들을 능가함을 보여준다. 합성된 회로와 해당 회로도는 보충 자료 저장소에서 제공된다.
QDEvo: 자동 휴리스틱 설계를 위한 다목표 품질-다양성 프레임워크
QDEvo: A Multi-Objective Quality-Diversity Framework for Automated Heuristic Design
대규모 언어 모델(LLM)과 진화 연산(evolutionary computation)의 통합은 조합 최적화(combinatorial optimization)에서 자동 휴리스틱 설계를 위한 강력한 패러다임으로 부상했다. 그러나 기존 접근법은 모드 붕괴(mode collapse)에 시달리며, 의미적 다양성이 부족한 동질적 개체군으로 수렴하고 전체 알고리즘 공간을 탐색하지 못한다. 우리는 품질-다양성(Quality-Diversity) 최적화와 LLM 기반 휴리스틱 탐색을 통합하는 다목표 프레임워크인 Quality-Diversity Evolution(QDEvo)을 제안한다. 사전학습된 코드 임베딩을 사용해 의미적으로 다양한 알고리즘의 무한 아카이브를 유지하고, 계층적 자기 성찰(hierarchical self-reflection)을 도입해 진화 과정을 안내한다. 표준 벤치마크와 실제 산업 응용에 걸친 광범위한 실험 결과, QDEvo는 Hypervolume 및 Inverted Generational Distance 지표 모두에서 최신 방법들을 크게 능가한다. 본 프레임워크는 고성능이면서 동시에 계산적으로 효율적이고 의미적으로 다양한 휴리스틱의 발견을 가능하게 하며, 복잡한 최적화 문제에 대해 실무자에게 풍부한 해 포트폴리오를 제공한다.
학생 학습 자원 배분을 위한 유전 알고리즘
A genetic algorithm for student academic resource allocation
개별 학생에게 학습 자원을 최적으로 배분하는 것은 학습자 다양성을 다루고 공평한 교육 성과를 촉진하는 데 필수적이다. Erasmus+ KA220-SCH 프로젝트의 틀 안에서, 본 논문은 고등학교 수학 학생을 위한 교육 자료 선택을 엄격한 학습 시간 제약을 따르는 0-1 이진 조합 최적화(optimization) 문제로 모델링한다. 이 공식화의 NP-hard 복잡도를 고려할 때, 자원 카탈로그가 확대될수록 정확한 해법은 계산적으로 다루기 어려워진다. 이 과제를 해결하기 위해, 우리는 이진 결정 공간을 효과적으로 탐색하기 위해 특화된 제약 복구 메커니즘과 통합된 유전 알고리즘(Genetic Algorithm)을 제안한다. 10회의 독립 실행에 걸친 실험적 평가는 빠른 수렴, 높은 해 품질, 그리고 서로 다른 기본 시드에 걸친 강한 알고리즘적 안정성을 보여준다. 이 결과는 중등 교육에서 실시간 의사결정 지원 시스템을 위한 메타휴리스틱(metaheuristic) 접근법의 실용적 유용성을 확인한다.
LLM을 활용한 제로샷 교차 문제 일반화를 위한 다중 작업 진화
Multi-Task Evolution for Zero-Shot Cross-Problem Generalization using LLMs
다양한 조합 최적화(combinatorial optimization) 문제를 위한 효과적인 휴리스틱(heuristic)을 설계하는 것은 상당한 전문성과 반복적인 탐색을 필요로 합니다. 대규모 언어 모델(LLM)은 휴리스틱 생성과 개선을 자동화하지만, 휴리스틱 탐색은 일반적으로 최적화 대상 문제의 평가 피드백에 의존합니다. 따라서 소스 작업 피드백만을 사용하여 새로운 문제 정의로 일반화하는 것은 여전히 핵심적인 과제로 남아 있습니다. 본 논문에서는 제로샷(zero-shot) 교차 문제 일반화를 위한 LLM 기반 다중 작업 진화 프레임워크인 MECo를 소개합니다. MECo는 작업 조건부 휴리스틱 개체군을 유지하며, 교차 작업 개체군 성능에 기반한 전이 격차(transfer gap)를 활용해 이들의 상호작용을 유도합니다. 이러한 상호작용은 휴리스틱의 전이와 재조합을 가능하게 합니다. 그런 다음 상호보완적 선택 기준을 통해 각 개체가 소스 조합에 대해 제공하는 추가적인 커버리지를 보상함으로써 간결한 휴리스틱 세트를 구성합니다. 선택된 세트는 추가적인 탐색이나 적응 과정 없이 타깃 문제에 바로 적용됩니다. 차량 경로 문제(VRP) 및 유연한 잡숍 스케줄링(FJSP) 전반에 걸친 32가지 변형 문제를 대상으로 한 실험에서, MECo는 동일한 예산 하에 8개의 자동화된 휴리스틱 설계(AHD) 기준선과 비교해 가장 낮은 평균 비용을 달성함을 보여줍니다. 도메인 외(OOD) 문제에서도 각 제품군에서 가장 강력한 기준선을 능가합니다. 나아가 MECo 프레임워크를 서로 다른 AHD 방법들과 통합했을 때 두 제품군 모두에서 ID 및 OOD 성능이 향상되어, 여러 방법 전반에 걸친 유효성을 뒷받침합니다.
목표 수가 변하는 동적 다목적 최적화를 위한 비유계 아카이브 기반 전이 전략
An Unbounded Archive-based Transfer Strategy for Dynamic Multi-Objective Optimization with a Changing Number of Objectives
목표 수가 가변적인 동적 다목적 최적화는 목표 차원의 변화가 파레토 전선을 크게 바꿀 수 있고 알고리즘의 적응성을 저하시킬 수 있어 어렵다. 본 논문은 각 환경 단계에서 자손 해의 비유계 아카이브를 유지하고, 목표 변화가 발생할 때 실행 가능한 비支配 해를 전이 가능한 정예(elite)로 추출하는 비유계 아카이브 기반 전이 전략(UATS)을 제안한다. UATS를 SPEA2SDE에 내장해 UATS-SPEA2SDE를 구성함으로써, 알고리즘이 shift-based density estimation(SDE)의 수렴과 다양성 이점을 유지하면서 과거 진화 정보를 재사용할 수 있게 한다. 세 가지 목표 변화 설정 하에서 네 개의 벤치마크 문제에 대해 실험을 수행하였으며, UATS-SPEA2SDE를 재시작 기반 SPEA2SDE 기준선 및 네 가지 대표 동적 다목적 최적화 알고리즘과 비교하였다. 결과는 아카이브 안내 전이가 환경 변화 이후 회복을 개선하고 목표 수 변화에 대한 적응성을 향상시킴을 보여준다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.