Constructing Generalizable Parallel Algorithm Portfolios for Multi-Objective Binary Optimization via General-Purpose Instance Generation
Zhiyuan Wang, Shengcai Liu, Shaofeng Zhang, Ke Tang
原文摘要
Despite progress in constructing generalizable parallel algorithm portfolios~(PAPs), no general-purpose method is yet available for multi-objective binary optimization problems~(MOBOPs) without problem-specific customization. To fill this gap, this work proposes domain-agnostic co-evolution of parameterized search for multi-objective binary optimization~(DACMO), the first general-purpose method for automatic PAP construction on MOBOPs. Its core, Unified Instance Representation~(UIR), represents and generates MOBOP instances with varying dimensions without knowledge of problem-specific instance structures. UIR separates common features of the target class from instance-specific features, preserving the common features learned from real instances during generation. DACMO co-evolves the training instances and PAP by alternating UIR-based instance augmentation with PAP updates. Experiments cover four structurally different MOBOP classes, including two black-box classes from real-world applications. Starting from five real training instances per class, DACMO constructs high-performance PAPs without problem-specific customization. On unseen instances from all four classes, these PAPs outperform portfolios of tuned classical multi-objective evolutionary algorithms and those constructed by the recent automatic PAP construction method EoH-S. DACMO also achieves overall performance comparable to the strong CEPS baseline and significantly outperforms it on two classes, without the substantial expert effort CEPS requires for problem-specific instance generator design.
cs.NE