The General Combinatorial Optimization Problem: Towards Automated Algorithm Design

Qu, Rong; Kendall, Graham; Pillay, Nelishia

Abstract

This paper defines a new combinatorial optimisation problem, namely General Combinatorial Optimisation Problem (GCOP), whose decision variables are a set of parametric algorithmic components, i.e. algorithm design decisions. The solutions of GCOP, i.e. compositions of algorithmic components, thus represent different generic search algorithms. The objective of GCOP is to find the optimal algorithmic compositions for solving the given optimisation problems. Solving the GCOP is thus equivalent to automatically designing the best algorithms for optimisation problems. Despite recent advances, the evolutionary computation and optimisation research communities are yet to embrace formal standards that underpin automated algorithm design. In this position paper, we establish GCOP as a new standard to define different search algorithms within one unified model. We demonstrate the new GCOP model to standardise various search algorithms as well as selection hyper-heuristics. A taxonomy is defined to distinguish several widely used terminologies in automated algorithm design, namely automated algorithm composition, configuration and selection. We would like to encourage a new line of exciting research directions addressing several challenging research issues including algorithm generality, algorithm reusability, and automated algorithm design.

Citation

Qu, R., Kendall, G., & Pillay, N. (2020). The General Combinatorial Optimization Problem: Towards Automated Algorithm Design. IEEE Computational Intelligence Magazine, 15(2), 14-23. https://doi.org/10.1109/mci.2020.2976182

• Journal Article Type: Article
• Acceptance Date: Jan 9, 2020
• Online Publication Date: Apr 13, 2020
• Publication Date: 2020-05
• Deposit Date: Feb 25, 2020
• Publicly Available Date: Apr 13, 2020
• Journal: IEEE Computational Intelligence Magazine
• Print ISSN: 1556-603X
• Electronic ISSN: 1556-6048
• Publisher: Institute of Electrical and Electronics Engineers
• Peer Reviewed: Peer Reviewed
• Volume: 15
• Issue: 2
• Pages: 14-23
• DOI: https://doi.org/10.1109/mci.2020.2976182
• Keywords: Theoretical Computer Science; Artificial Intelligence
• Public URL: https://nottingham-repository.worktribe.com/output/4033779
• Publisher URL: https://ieeexplore.ieee.org/abstract/document/9064746
• Additional Information: © 2020 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works