research-article

Few-Shots Parallel Algorithm Portfolio Construction via Co-Evolution

Authors:

Xin YaoAuthors Info & Claims

IEEE Transactions on Evolutionary Computation, Volume 25, Issue 3

Pages 595 - 607

https://doi.org/10.1109/TEVC.2021.3059661

Published: 01 June 2021 Publication History

Abstract

Generalization, i.e., the ability of solving problem instances that are not available during the system design and development phase, is a critical goal for intelligent systems. A typical way to achieve good generalization is to learn a model from vast data. In the context of heuristic search, such a paradigm could be implemented as configuring the parameters of a parallel algorithm portfolio (PAP) based on a set of “training” problem instances, which is often referred to as PAP construction. However, compared to the traditional machine learning, PAP construction often suffers from the lack of training instances, and the obtained PAPs may fail to generalize well. This article proposes a novel competitive co-evolution scheme, named co-evolution of parameterized search (CEPS), as a remedy to this challenge. By co-evolving a configuration population and an instance population, CEPS is capable of obtaining generalizable PAPs with few training instances. The advantage of CEPS in improving generalization is analytically shown in this article. Two concrete algorithms, namely, CEPS-TSP and CEPS-VRPSPDTW, are presented for the traveling salesman problem (TSP) and the vehicle routing problem with simultaneous pickup–delivery and time windows (VRPSPDTW), respectively. The experimental results show that CEPS has led to better generalization, and even managed to find new best-known solutions for some instances.

References

[1]

S. Lin and B. W. Kernighan, “An effective heuristic algorithm for the traveling-salesman Problem,” Oper. Res., vol. 21, no. 2, pp. 498–516, 1973.

Digital Library

[2]

A. E. Eiben and S. K. Smit, “Parameter tuning for configuring and analyzing evolutionary algorithms,” Swarm Evol. Comput., vol. 1, no. 1, pp. 19–31, 2011.

[3]

F. Hutter, H. H. Hoos, and K. Leyton-Brown, “Sequential model-based optimization for general algorithm configuration,” in Proc. 5th Int. Conf. Learn. Intell. Optim. (LION), Rome, Italy, Jan. 2011, pp. 507–523.

[4]

G. Karafotias, M. Hoogendoorn, and Á. E. Eiben, “Parameter control in evolutionary algorithms: Trends and challenges,” IEEE Trans. Evol. Comput., vol. 19, no. 2, pp. 167–187, Apr. 2015.

Digital Library

[5]

C. Huang, Y. Li, and X. Yao, “A survey of automatic parameter tuning methods for metaheuristics,” IEEE Trans. Evol. Comput., vol. 24, no. 2, pp. 201–216, Apr. 2020.

[6]

A. S. D. Dymond, A. P. Engelbrecht, S. Kok, and P. S. Heyns, “Tuning optimization algorithms under multiple objective function evaluation budgets,” IEEE Trans. Evol. Comput., vol. 19, no. 3, pp. 341–358, Jun. 2015.

Digital Library

[7]

F. Hutter, H. H. Hoos, K. Leyton-Brown, and T. Stützle, “ParamILS: An automatic algorithm configuration framework,” J. Artif. Intell. Res., vol. 36, no. 1, pp. 267–306, 2009.

[8]

C. Ansótegui, M. Sellmann, and K. Tierney, “A gender-based genetic algorithm for the automatic configuration of algorithms,” in Proc. 15th Int. Conf. Principles Pract. Constraint Program. (CP), Lisbon, Portugal, Sep. 2009, pp. 142–157.

[9]

C. Ansótegui, Y. Malitsky, H. Samulowitz, M. Sellmann, and K. Tierney, “Model-based genetic algorithms for algorithm configuration,” in Proc. 24th Int. Joint Conf. Artif. Intell. (IJCAI), Buenos Aires, Argentina, Jul. 2015, pp. 733–739.

[10]

M. López-Ibáñez, J. Dubois-Lacoste, L. Pérez Cáceres, T. Stützle, and M. Birattari, “The irace package: Iterated racing for automatic algorithm configuration,” Oper. Res. Perspect., vol. 3, pp. 43–58, Sep. 2016.

[11]

C. P. Gomes and B. Selman, “Algorithm portfolios,” Artif. Intell., vol. 126, nos. 1–2, pp. 43–62, 2001.

Digital Library

[12]

B. A. Huberman, R. M. Lukose, and T. Hogg, “An economics approach to hard computational problems,” Science, vol. 275, no. 5296, pp. 51–54, 1997.

[13]

S. Liu, K. Tang, and X. Yao, “Automatic construction of parallel portfolios via explicit instance grouping,” in Proc. 33rd AAAI Conf. Artif. Intell. (AAAI), Honolulu, HI, USA, Jan. 2019, pp. 1560–1567.

[14]

F. Peng, K. Tang, G. Chen, and X. Yao, “Population-based algorithm portfolios for numerical optimization,” IEEE Trans. Evol. Comput., vol. 14, no. 5, pp. 782–800, Oct. 2010.

Digital Library

[15]

S. Liu, K. Tang, and X. Yao, “Generative adversarial construction of parallel portfolios,” IEEE Trans. Cybern., early access, Apr. 29, 2020. 10.1109/TCYB.2020.2984546.

[16]

K. Asanovicet al., “A view of the parallel computing landscape,” Commun. ACM, vol. 52, no. 10, pp. 56–67, 2009.

Digital Library

[17]

G. Reinelt, “TSPLIB—A traveling salesman problem library,” INFORMS J. Comput., vol. 3, no. 4, pp. 376–384, 1991.

[18]

H.-F. Wang and Y.-Y. Chen, “A genetic algorithm for the simultaneous delivery and pickup problems with time window,” Comput. Ind. Eng., vol. 62, no. 1, pp. 84–95, 2012.

Digital Library

[19]

M. Nazari, A. Oroojlooy, L. V. Snyder, and M. Takác, “Reinforcement learning for solving the vehicle routing problem,” in Proc. 31st Annu. Conf. Neural Inf. Process. Syst. (NeurIPS), Dec. 2018, pp. 9861–9871.

[20]

X. Chen and Y. Tian, “Learning to perform local rewriting for combinatorial optimization,” in Proc. 32nd Annu. Conf. Neural Inf. Process. Syst. (NeurIPS), Dec. 2019, pp. 6278–6289.

[21]

W. Kool, H. van Hoof, and M. Welling, “Attention, learn to solve routing problems!”, 2018. [Online]. Available: http://www.arXiv:1803.08475

[22]

A. Blot, H. H. Hoos, L. Jourdan, M.-É. Kessaci-Marmion, and H. Trautmann, “MO-ParamILS: A multi-objective automatic algorithm configuration framework,” in Proc. 10th Int. Conf. Learn. Intell. Optim. (LION), Ischia, Italy, Jun. 2016, pp. 32–47.

[23]

M. Birattari, “On the estimation of the expected performance of a metaheuristic on a class of instances. How many instances, how many runs?” Dept. Comp. & Decis. Eng., Université Libre de Bruxelles, Brussels, Belgium, Rep. TR/IRIDIA/2004-01, 2004. [Online]. Available: https://code.ulb.ac.be/

[24]

S. Liu, K. Tang, Y. Lei, and X. Yao, “On performance estimation in automatic algorithm configuration,” in Proc. 34th AAAI Conf. Artif. Intell., Feb. 2020, pp. 2384–2391.

[25]

M. Lindauer, H. H. Hoos, K. Leyton-Brown, and T. Schaub, “Automatic construction of parallel portfolios via algorithm configuration,” Artif. Intell., vol. 244, pp. 272–290, Mar. 2017.

[26]

L. Xu, H. H. Hoos, and K. Leyton-Brown, “Hydra: Automatically configuring algorithms for portfolio-based selection,” in Proc. 24th AAAI Conf. Artif. Intell., Jul. 2010, pp. 210–216.

[27]

S. Kadioglu, Y. Malitsky, M. Sellmann, and K. Tierney, “ISAC—Instance-specific algorithm configuration,” in Proc. 19th Eur. Conf. Artif. Intell. (ECAI), Aug. 2010, pp. 751–756.

[28]

L. Xu, F. Hutter, H. H. Hoos, and K. Leyton-Brown, “SATzilla: Portfolio-based algorithm selection for SAT,” J. Artif. Intell. Res., vol. 32, pp. 565–606, Jun. 2008.

[29]

P. Kerschke, L. Kotthoff, J. Bossek, H. H. Hoos, and H. Trautmann, “Leveraging TSP solver complementarity through machine learning,” Evol. Comput., vol. 26, no. 4, pp. 597–620, 2018.

Digital Library

[30]

K. Zhao, S. Liu, Y. Rong, and J. X. Yu, “Leveraging TSP solver complementarity via deep learning,” 2020. [Online]. Available: http://www.arXiv:2006.00715

[31]

L. Kotthoff, “Algorithm selection for combinatorial search problems: A survey,” AI Mag., vol. 35, no. 3, pp. 48–60, 2014.

Digital Library

[32]

C. D. Rosin and R. K. Belew, “New methods for competitive coevolution,” Evol. Comput., vol. 5, no. 1, pp. 1–29, 1997.

Digital Library

[33]

J. I. van Hemert, “Evolving combinatorial problem instances that are difficult to solve,” Evol. Comput., vol. 14, no. 4, pp. 433–462, Dec. 2006.

Digital Library

[34]

K. Helsgaun, “General k-opt submoves for the Lin-Kernighan TSP heuristic,” Math. Program. Comput., vol. 1, nos. 2–3, pp. 119–163, 2009.

[35]

D. S. Johnson and L. A. McGeoch, “Experimental analysis of heuristics for the STSP,” in The Traveling Salesman Problem and Its Variations, G. Gutin and A. P. Punnen, Eds. Boston, MA, USA: Springer, 2007, pp. 369–443.

[36]

J. Bossek. (2015). netgen: Network Generator for Combinatorial Graph Problems. [Online]. Available: https://github.com/jakobbossek/netgen

[37]

J. Bossek, P. Kerschke, A. Neumann, M. Wagner, F. Neumann, and H. Trautmann, “Evolving diverse TSP instances by means of novel and creative mutation operators,” in Proc. 15th ACM/SIGEVO Conf. Found. Genet. Algorithms (FOGA), Aug. 2019, pp. 58–71.

[38]

Y. Nagata and S. Kobayashi, “A powerful genetic algorithm using edge assembly crossover for the traveling salesman problem,” INFORMS J. Comput., vol. 25, no. 2, pp. 346–363, 2013.

Digital Library

[39]

X.-F. Xie and J. Liu, “Multiagent optimization system for solving the traveling salesman problem (TSP),” IEEE Trans. Syst., Man, Cybern. B, Cybern., vol. 39, no. 2, pp. 489–502, Apr. 2009.

Digital Library

[40]

C. Wang, D. Mu, F. Zhao, and J. W. Sutherland, “A parallel simulated annealing method for the vehicle routing problem with simultaneous pickup–delivery and time windows,” Comput. Ind. Eng., vol. 83, pp. 111–122, May 2015.

Digital Library

[41]

W. Huang and T. Zhang, “Vehicle routing problem with simultaneous pick-up and delivery and time-windows based on improved global artificial fish swarm algorithm,” Comput. Eng. Appl., vol. 52, no. 21, pp. 21–29, 2016.

[42]

X. Pu and K. Wang, “An evolutionary ant colony algorithm for a vehicle routing problem with simultaneous pick-up and delivery and hard time windows,” in Proc. 30th Chin. Control Decis. Conf. (CCDC), Shenyang, China, Jun. 2018, pp. 6499–6503.

[43]

Y. Shi, T. Boudouh, and O. Grunder, “An efficient Tabu search based procedure for simultaneous delivery and pick-up problem with time window,” IFAC-PapersOnLine, vol. 51, no. 11, pp. 241–246, 2018.

[44]

V. Mnihet al., “Human-level control through deep reinforcement learning,” Nature, vol. 518, no. 7540, pp. 529–533, 2015.

[45]

T. D. Kulkarni, K. R. Narasimhan, A. Saeedi, and J. B. Tenenbaum, “Hierarchical deep reinforcement learning: integrating temporal abstraction and intrinsic motivation,” in Proc. 29th Annu. Conf. Neural Inf. Process. Syst. (NIPS), Dec. 2016, pp. 3675–3683.

Cited By

Liu SLu NHong WQian CTang K(2024)Effective and Imperceptible Adversarial Textual Attack Via Multi-objectivizationACM Transactions on Evolutionary Learning and Optimization10.1145/36511664:3(1-23)Online publication date: 23-Jul-2024
https://dl.acm.org/doi/10.1145/3651166
Liu SPeng FTang KWilliams BChen YNeville J(2023)Reliable robustness evaluation via automatically constructed attack ensemblesProceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v37i7.26064(8852-8860)Online publication date: 7-Feb-2023
https://dl.acm.org/doi/10.1609/aaai.v37i7.26064
He RDai ZHe STang KFrommholz IHopfgartner FLee MOakes MLalmas MZhang MSantos R(2023)Perturbation-Based Two-Stage Multi-Domain Active LearningProceedings of the 32nd ACM International Conference on Information and Knowledge Management10.1145/3583780.3615222(3933-3937)Online publication date: 21-Oct-2023
https://dl.acm.org/doi/10.1145/3583780.3615222
Show More Cited By

Index Terms

Few-Shots Parallel Algorithm Portfolio Construction via Co-Evolution
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
      1. Heuristic function construction
  2. Machine learning
2. Theory of computation
  1. Design and analysis of algorithms
    1. Algorithm design techniques

Index terms have been assigned to the content through auto-classification.

Recommendations

Population size reduction for the differential evolution algorithm

This paper studies the efficiency of a recently defined population-based direct global optimization method called Differential Evolution with self-adaptive control parameters. The original version uses fixed population size but a method for gradually ...
Multi-search differential evolution algorithm

The differential evolution algorithm (DE) has been shown to be a very simple and effective evolutionary algorithm. Recently, DE has been successfully used for the numerical optimization. In this paper, first, based on the fitness value of each ...
Research of multi population differential evolution algorithm
ICNC'09: Proceedings of the 5th international conference on Natural computation

The standard differential evolution is easy to fall into premature convergence; so for solving the problem, the paper presented a Multi Population Differential Evolution Algorithm (MPDE) which was based on simulating the developing history of human ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Evolutionary Computation

IEEE Transactions on Evolutionary Computation Volume 25, Issue 3

June 2021

203 pages

ISSN:1089-778X

Issue’s Table of Contents

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License. For more information, see https://creativecommons.org/licenses/by-nc-nd/4.0/.

Publisher

IEEE Press

Publication History

Published: 01 June 2021

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 17 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Liu SLu NHong WQian CTang K(2024)Effective and Imperceptible Adversarial Textual Attack Via Multi-objectivizationACM Transactions on Evolutionary Learning and Optimization10.1145/36511664:3(1-23)Online publication date: 23-Jul-2024
https://dl.acm.org/doi/10.1145/3651166
Liu SPeng FTang KWilliams BChen YNeville J(2023)Reliable robustness evaluation via automatically constructed attack ensemblesProceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v37i7.26064(8852-8860)Online publication date: 7-Feb-2023
https://dl.acm.org/doi/10.1609/aaai.v37i7.26064
He RDai ZHe STang KFrommholz IHopfgartner FLee MOakes MLalmas MZhang MSantos R(2023)Perturbation-Based Two-Stage Multi-Domain Active LearningProceedings of the 32nd ACM International Conference on Information and Knowledge Management10.1145/3583780.3615222(3933-3937)Online publication date: 21-Oct-2023
https://dl.acm.org/doi/10.1145/3583780.3615222
Yang MGao JZhou ALi CYao X(2023)Contribution-Based Cooperative Co-Evolution With Adaptive Population Diversity for Large-Scale Global Optimization [Research Frontier]IEEE Computational Intelligence Magazine10.1109/MCI.2023.327777218:3(56-68)Online publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1109/MCI.2023.3277772
Liu SZhang YTang KYao X(2023)How Good is Neural Combinatorial Optimization? A Systematic Evaluation on the Traveling Salesman ProblemIEEE Computational Intelligence Magazine10.1109/MCI.2023.327776818:3(14-28)Online publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1109/MCI.2023.3277768
Juillé HDumeur RShaw P(2023)Heuristics Selection with ML in CP OptimizerLearning and Intelligent Optimization10.1007/978-3-031-44505-7_15(208-222)Online publication date: 4-Jun-2023
https://dl.acm.org/doi/10.1007/978-3-031-44505-7_15
Peng FLiu SLu NTang K(2022)Training Quantized Deep Neural Networks via Cooperative CoevolutionAdvances in Swarm Intelligence10.1007/978-3-031-09726-3_8(81-93)Online publication date: 15-Jul-2022
https://dl.acm.org/doi/10.1007/978-3-031-09726-3_8
Parque VKrawiec K(2021)A differential particle scheme and its application to PID parameter tuning of an inverted pendulumProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3449726.3463225(1937-1943)Online publication date: 7-Jul-2021
https://dl.acm.org/doi/10.1145/3449726.3463225

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents