arXiv:2405.15569

Randomized heuristic repair for large-scale multidimensional knapsack problem

Jean P. Martins

제출 2024-05-24

원문 초록

The multidimensional knapsack problem (MKP) is an NP-hard combinatorial optimization problem whose solution is determining a subset of maximum total profit items that do not violate capacity constraints. Due to its hardness, large-scale MKP instances are usually a target for metaheuristics, a context in which effective feasibility maintenance strategies are crucial. In 1998, Chu and Beasley proposed an effective heuristic repair that is still relevant for recent metaheuristics. However, due to its deterministic nature, the diversity of solutions such heuristic provides is insufficient for long runs. As a result, the search for new solutions ceases after a while. This paper proposes an efficiency-based randomization strategy for the heuristic repair that increases the variability of the repaired solutions without deteriorating quality and improves the overall results.

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2609.24104v1cs.NE공통 태그 Diversity, Combinatorial Optimization

차량 경로 문제에서 유도 국소 탐색 학습을 위한 행동 기반 니칭 유전 프로그래밍

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 보정 후에도 유의하게 남는다. 이 결과는 평가된 설정 내에서 유용한 해 품질과 프로그램 크기 간의 트레이드오프를 밝히며, 크기 감소를 행동 표현만으로 귀인하지는 않는다.

arXiv:2607.22314v1cs.LG공통 태그 Diversity, Combinatorial Optimization

팩터 그래프를 통한 서브샘플링을 위한 진화 인식 MSA 추론

Evolution-Aware MSA Reasoning for Subsampling via Factor Graphs

다중 서열 정렬(MSA)은 단백질 언어 모델에 명시적인 진화적 맥락을 제공하지만, 깊이가 크기 때문에 제한된 토큰 예산 하에서는 서브샘플링이 불가피하다. 무작위 선택, 동일성(identity) 기반 필터링, 다양성 중심 샘플링 등 기존 전략은 효과적인 휴리스틱이지만, 부분집합에 보존되는 진화적 신호에 대한 제어가 제한적이다. 본 연구에서는 MSA 서브샘플링을 명시적 최적화 문제로 재구성하며, 쿼리 동일성과 다양성을 포함한 핵심 진화 지표를 제어 가능한 목표로 취급한다. 이 관점을 바탕으로 친화력 전파(Affinity Propagation) 기반 팩터 그래프 접근법인 AP-REASONER를 제안한다. 진화 인식 단항(unary) 팩터, exemplar 일관성 팩터, 두 개의 제어 노브를 갖춘 AP-REASONER는 메시지 전달(message passing)을 통한 팩터 그래프 추론으로 고정 예산 MSA 부분집합을 추론한다. 장거리 접촉 예측 및 conformational 앙상블 예측 실험에서 AP-REASONER는 구조 민감 하위 작업에서 기준선 서브샘플러보다 우수한 성능을 보이며, 대안적 단백질 conformation의 제어 가능한 복원을 가능하게 한다. 이러한 결과는 MSA 서브샘플링을 제어 가능한 최적화 문제로 모델링할 때의 가치를 부각하며, 팩터 그래프 추론이 휴리스틱 선택에 대한 효과적인 대안임을 보여준다.

arXiv:2607.14027v1cs.NE공통 태그 Diversity, Combinatorial Optimization

SPECS: 종 분화 진화적 회로 합성

SPECS: Speciated Evolutionary Circuit Synthesis

우리는 토폴로지와 사이징 최적화를 동시에 수행하는 자동 아날로그 회로 합성을 위한 유전 알고리즘인 SPECS를 제안한다. SPECS는 신경망 합성을 위해 처음 개발된 진화 알고리즘인 NEAT(NeuroEvolution of Augmenting Topologies)에서 영감을 받았다. 게놈 표현을 재정식화하고 유전 연산자를 아날로그 회로 영역에 맞게 조정함으로써, NEAT의 핵심 원리를 아날로그 회로 합성으로 성공적으로 이식하였다. 회로 특화 배선 제약을 통합하여 진화 과정 전반에 걸쳐 유효하고 물리적으로 의미 있는 설계가 되도록 보장하며, 종 분화(speciation)를 사용하여 집단 다양성을 유지하면서 혁신을 보존한다. 제안 방법을 제곱, 세제곱, 제곱근, 세제곱근 함수로 구성된 일련의 계산 회로 합성 과제에 대해 평가하였다. 실험 결과, SPECS가 모든 과제에서 해 품질과 신뢰성 모두에서 벤치마크 방법들을 능가함을 보여준다. 합성된 회로와 해당 회로도는 보충 자료 저장소에서 제공된다.

arXiv:2607.11916v1cs.NE공통 태그 Diversity, Combinatorial Optimization

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 지표 모두에서 최신 방법들을 크게 능가한다. 본 프레임워크는 고성능이면서 동시에 계산적으로 효율적이고 의미적으로 다양한 휴리스틱의 발견을 가능하게 하며, 복잡한 최적화 문제에 대해 실무자에게 풍부한 해 포트폴리오를 제공한다.

arXiv:2607.11684v1stat.ML공통 태그 Diversity, Combinatorial Optimization

다양화 다항 로짓 맥락 밴딧

Diversified Multinomial Logit Contextual Bandits

기존의 맥락적 다항 로짓(MNL) 밴딧은 관련성 기반 선택을 모델링하지만 품목 구성 내 다양성의 잠재적 이점을 무시하는 반면, 서브모듈러/조합적 밴딧은 보상에 다양성을 인코딩하지만 구조화된 선택 확률이 부재하다. 우리는 $\textit{다양화 다항 로짓}$(DMNL) 맥락 밴딧으로 이 간극을 해소한다. 이 모델은 MNL 선택 확률에 일반적 서브모듈러 다양성 함수를 결합하여 단일 모델 내에서 관련성-다양성 트레이드오프를 공식화한다. 다양성을 통합하면 정확한 MNL 품목 구성 최적화가 난해해진다. 우리는 낙관적 한계 이득을 최대화하여 항목별로 품목 구성을 구성하고 블랙박스 최적화 오라클을 회피하는 $\textit{화이트박스}$ UCB 기반 알고리즘 $\texttt{OFU-DMNL}$을 제안한다. $\texttt{OFU-DMNL}$이 적어도 $(1-\frac{1}{e+1})$-$\textit{근사}$ 후회 경계 $\tilde{O}\left(d \sqrt{T/K}\right)$를 달성함을 보이는데, 여기서 $d$는 맥락 차원, $K$는 최대 품목 구성 크기, $T$는 기간이며, 표준 서브모듈러 기준선 대비 향상된 근사 인수를 달성한다. 실험에서는 일관된 성능 향상을 보였으며, 전수 열거 대비 유사한 후회 수준을 유지하면서도 실행 시간을 크게 단축하였다. 전반적으로, DMNL 밴딧은 불확실성 하에서 다양성을 고려한 품목 구성 최적화를 위한 실용적 기반을 제공하며, $\texttt{OFU-DMNL}$은 통계적·계산적으로 효율적인 해법을 제시한다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.