Skip to main content
main-content
Top

Hint

Swipe to navigate through the articles of this issue

Published in: Natural Computing 3/2021

16-02-2021

Evolutionary algorithms and submodular functions: benefits of heavy-tailed mutations

Authors: Francesco Quinzan, Andreas Göbel, Markus Wagner, Tobias Friedrich

Published in: Natural Computing | Issue 3/2021

Login to get access
share
SHARE

Abstract

A core operator of evolutionary algorithms (EAs) is the mutation. Recently, much attention has been devoted to the study of mutation operators with dynamic and non-uniform mutation rates. Following up on this area of work, we propose a new mutation operator and analyze its performance on the \((1+1)\) Evolutionary Algorithm (EA). Our analyses show that this mutation operator competes with pre-existing ones, when used by the \((1+1)\) EA on classes of problems for which results on the other mutation operators are available. We show that the \((1+1)\) EA using our mutation operator finds a (1/3)-approximation ratio on any non-negative submodular function in polynomial time. We also consider the problem of maximizing a symmetric submodular function under a single matroid constraint and show that the \((1+1)\) EA using our operator finds a (1/3)-approximation within polynomial time. This performance matches that of combinatorial local search algorithms specifically designed to solve these problems and outperforms them with constant probability. Finally, we evaluate the performance of the \((1+1)\) EA using our operator experimentally by considering two applications: (a) the maximum directed cut problem on real-world graphs of different origins, with up to 6.6 million vertices and 56 million edges and (b) the symmetric mutual information problem using a four month period air pollution data set. In comparison with uniform mutation and a recently proposed dynamic scheme, our operator comes out on top on these instances.

To get access to this content you need the following product:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 69.000 Bücher
  • über 500 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Testen Sie jetzt 15 Tage kostenlos.

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 50.000 Bücher
  • über 380 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




Testen Sie jetzt 15 Tage kostenlos.

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 58.000 Bücher
  • über 300 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Testen Sie jetzt 15 Tage kostenlos.

Footnotes
1
In contrast to our earlier work (Friedrich, Göbel, et al., 2018), we are comparing against \(\mathsf {unif}_{1}\), which performs at least one flip, thus making it a fairer comparison.
 
2
Source categories of the 67 instances: 2x bio-*, 6x ca-*, 5x ia-*, 2x inf-*, 1x soc-*, 40x socfb-*, 4x tech-*, 7x web-*. The largest graph is socfb-Texas84 with 36 364 vertices and 1 590 651 edges.
 
3
This dataset is publicly available at www.​berkleyearth.​org.
 
Literature
go back to reference Ageev AA, Sviridenko M (1999) An 0.828-approximation algorithm for the uncapacitated facility location problem an 0.828-approximation algorithm for the uncapacitated facility location problem. Discrete Appl Math 93(2–3):149–156 Ageev AA, Sviridenko M (1999) An 0.828-approximation algorithm for the uncapacitated facility location problem an 0.828-approximation algorithm for the uncapacitated facility location problem. Discrete Appl Math 93(2–3):149–156
go back to reference Caselton WF, Zidek J (1984) Optimal monitoring network designs optimal monitoring network designs. Stat Probab Lett 2(4):223–227 CrossRef Caselton WF, Zidek J (1984) Optimal monitoring network designs optimal monitoring network designs. Stat Probab Lett 2(4):223–227 CrossRef
go back to reference Dasgupta D, Michalewicz Z (2013) Evolutionary algorithms in engineering applications. Springer, Berlin MATH Dasgupta D, Michalewicz Z (2013) Evolutionary algorithms in engineering applications. Springer, Berlin MATH
go back to reference Doerr B, Jansen T, Sudholt D, Winzen C, Zarges C (2013) Mutation rate matters even when optimizing monotonic functions mutation rate matters even when optimizing monotonic functions. Evol Comput 21(1):1–27 CrossRef Doerr B, Jansen T, Sudholt D, Winzen C, Zarges C (2013) Mutation rate matters even when optimizing monotonic functions mutation rate matters even when optimizing monotonic functions. Evol Comput 21(1):1–27 CrossRef
go back to reference Doerr B, Le HP, Makhmara R, Nguyen TD (2017) Fast genetic algorithms. In: Proceedings of GECCO, pp 777–784 Doerr B, Le HP, Makhmara R, Nguyen TD (2017) Fast genetic algorithms. In: Proceedings of GECCO, pp 777–784
go back to reference Doerr C, Wagner M (2018a) Sensitivity of parameter control mechanisms with respect to their initialization. In: Proceedings of of PPSN, pp 360–372 Doerr C, Wagner M (2018a) Sensitivity of parameter control mechanisms with respect to their initialization. In: Proceedings of of PPSN, pp 360–372
go back to reference Doerr C, Wagner M (2018b) Simple on-the-fly parameter selection mechanisms for two classical discrete black-box optimization benchmark problems. In: Proceedings of GECCO, pp 943–950 Doerr C, Wagner M (2018b) Simple on-the-fly parameter selection mechanisms for two classical discrete black-box optimization benchmark problems. In: Proceedings of GECCO, pp 943–950
go back to reference Droste S, Jansen T, Wegener I (2002) On the analysis of the (1+1) evolutionary algorithm. Theor Comput Sci 276(1–2):51–81 MathSciNetCrossRef Droste S, Jansen T, Wegener I (2002) On the analysis of the (1+1) evolutionary algorithm. Theor Comput Sci 276(1–2):51–81 MathSciNetCrossRef
go back to reference Eiben AE, Hinterding R, Michalewicz Z (1999) Parameter control in evolutionary algorithms. IEEE Trans Evol Comput 3(2):124–141 CrossRef Eiben AE, Hinterding R, Michalewicz Z (1999) Parameter control in evolutionary algorithms. IEEE Trans Evol Comput 3(2):124–141 CrossRef
go back to reference Eiben AE, Smith JE (2003) Introduction to evolutionary computation. Springer, Berlin CrossRef Eiben AE, Smith JE (2003) Introduction to evolutionary computation. Springer, Berlin CrossRef
go back to reference Feige U, Mirrokni VS, Vondrák J (2011) Maximizing non-monotone submodular functions. SIAM J Comput 40(4):1133–1153 MathSciNetCrossRef Feige U, Mirrokni VS, Vondrák J (2011) Maximizing non-monotone submodular functions. SIAM J Comput 40(4):1133–1153 MathSciNetCrossRef
go back to reference Friedrich T, Göbel A, Quinzan F, Wagner M (2018a) Heavy-tailed mutation operators in single-objective combinatorial optimization. In: Proceedings of PPSN, pp 134–145 Friedrich T, Göbel A, Quinzan F, Wagner M (2018a) Heavy-tailed mutation operators in single-objective combinatorial optimization. In: Proceedings of PPSN, pp 134–145
go back to reference Friedrich T, He J, Hebbinghaus N, Neumann F, Witt C (2010) Approximating covering problems by randomized search heuristics using multi-objective models. Evol Comput 18(4):617–633 CrossRef Friedrich T, He J, Hebbinghaus N, Neumann F, Witt C (2010) Approximating covering problems by randomized search heuristics using multi-objective models. Evol Comput 18(4):617–633 CrossRef
go back to reference Friedrich T, Neumann F (2015) Maximizing submodular functions under matroid constraints by evolutionary algorithms. Evol Comput 23(4):543–558 CrossRef Friedrich T, Neumann F (2015) Maximizing submodular functions under matroid constraints by evolutionary algorithms. Evol Comput 23(4):543–558 CrossRef
go back to reference Friedrich T, Quinzan F, Wagner M (2018b) Escaping large deceptive basins of attraction with heavy-tailed mutation operators. In Proceedings of GECCO, pp 293–300 Friedrich T, Quinzan F, Wagner M (2018b) Escaping large deceptive basins of attraction with heavy-tailed mutation operators. In Proceedings of GECCO, pp 293–300
go back to reference Goemans MX, Williamson DP (1995) Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J ACM 42(6):1115–1145 MathSciNetCrossRef Goemans MX, Williamson DP (1995) Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J ACM 42(6):1115–1145 MathSciNetCrossRef
go back to reference Håstad J (2001) Some optimal inapproximability results. J ACM 48(4):798–859 Håstad J (2001) Some optimal inapproximability results. J ACM 48(4):798–859
go back to reference Jansen T, Wegener I (2006) On the analysis of a dynamic evolutionary algorithm. J Discrete Algorithms 4(1):181–199 MathSciNetCrossRef Jansen T, Wegener I (2006) On the analysis of a dynamic evolutionary algorithm. J Discrete Algorithms 4(1):181–199 MathSciNetCrossRef
go back to reference Karp RM (1972) Reducibility among combinatorial problems. Complexity of computer computations. Springer, US, Boston, pp 85–103 MATH Karp RM (1972) Reducibility among combinatorial problems. Complexity of computer computations. Springer, US, Boston, pp 85–103 MATH
go back to reference Krause A, Guestrin C (2007) Near-optimal observation selection using submodular functions. In Proceedings of AAAI, pp 1650–1654 Krause A, Guestrin C (2007) Near-optimal observation selection using submodular functions. In Proceedings of AAAI, pp 1650–1654
go back to reference Krause A, Singh AP, Guestrin C (2008) Near-optimal sensor placements in gaussian processes: theory, efficient algorithms and empirical studies. J Mach Learn Res 9:235–284 MATH Krause A, Singh AP, Guestrin C (2008) Near-optimal sensor placements in gaussian processes: theory, efficient algorithms and empirical studies. J Mach Learn Res 9:235–284 MATH
go back to reference Lee J, Mirrokni VS, Nagarajan V, Sviridenko M (2009) Non-monotone submodular maximization under matroid and knapsack constraints. In: Proceedings of STOC, pp 323–332 Lee J, Mirrokni VS, Nagarajan V, Sviridenko M (2009) Non-monotone submodular maximization under matroid and knapsack constraints. In: Proceedings of STOC, pp 323–332
go back to reference Lehmann B, Lehmann DJ, Nisan N (2006) Combinatorial auctions with decreasing marginal utilities. Games Econ Behav 55(2):270–296 MathSciNetCrossRef Lehmann B, Lehmann DJ, Nisan N (2006) Combinatorial auctions with decreasing marginal utilities. Games Econ Behav 55(2):270–296 MathSciNetCrossRef
go back to reference Mitzenmacher M, Upfal E (2017) Probability and computing: randomization and probabilistic techniques in algorithms and data analysis. Cambridge University Press, Cambridge MATH Mitzenmacher M, Upfal E (2017) Probability and computing: randomization and probabilistic techniques in algorithms and data analysis. Cambridge University Press, Cambridge MATH
go back to reference Mühlenbein H (1992) How genetic algorithms really work: mutation and hillclimbing. In: Proceedings of PPSN, pp 15–26 Mühlenbein H (1992) How genetic algorithms really work: mutation and hillclimbing. In: Proceedings of PPSN, pp 15–26
go back to reference Nemhauser GL, Wolsey LA (1978) Best algorithms for approximating the maximum of a submodular set function. Math Oper Res 3(3):177–188 MathSciNetCrossRef Nemhauser GL, Wolsey LA (1978) Best algorithms for approximating the maximum of a submodular set function. Math Oper Res 3(3):177–188 MathSciNetCrossRef
go back to reference Oliveto PS, He J, Yao X (2009) Analysis of the (1+1)-EA for finding approximate solutions to vertex cover problems. IEEE Trans Evol Comput 13(5):1006–1029 CrossRef Oliveto PS, He J, Yao X (2009) Analysis of the (1+1)-EA for finding approximate solutions to vertex cover problems. IEEE Trans Evol Comput 13(5):1006–1029 CrossRef
go back to reference Qian C, Shi J, Tang K, Zhou Z (2018) Constrained monotone k-submodular function maximization using multiobjective evolutionary algorithms with theoretical guarantee. IEEE Trans Evol Comput 22(4):595–608 CrossRef Qian C, Shi J, Tang K, Zhou Z (2018) Constrained monotone k-submodular function maximization using multiobjective evolutionary algorithms with theoretical guarantee. IEEE Trans Evol Comput 22(4):595–608 CrossRef
go back to reference Qian C, Yu Y, Tang K, Yao X, Zhou Z (2017) Maximizing non-monotone/non-submodular functions by multi-objective evolutionary algorithms. CoRRabs/1711.07214 Qian C, Yu Y, Tang K, Yao X, Zhou Z (2017) Maximizing non-monotone/non-submodular functions by multi-objective evolutionary algorithms. CoRRabs/1711.07214
go back to reference Rhode RA, Muller RA (2015) Air pollution in China: mapping of concentrations and sources. PLoS One 10(8):e0135749 CrossRef Rhode RA, Muller RA (2015) Air pollution in China: mapping of concentrations and sources. PLoS One 10(8):e0135749 CrossRef
go back to reference Singh A, Krause A, Guestrin C, Kaiser WJ (2009) Efficient informative sensing using multiple robots. J Artif Intell Res 34:707–755 MathSciNetCrossRef Singh A, Krause A, Guestrin C, Kaiser WJ (2009) Efficient informative sensing using multiple robots. J Artif Intell Res 34:707–755 MathSciNetCrossRef
go back to reference Wagner M, Friedrich T, Lindauer M (2017) Improving local search in a minimum vertex cover solver for classes of networks. In: Proceedings of CEC, pp 1704–1711 Wagner M, Friedrich T, Lindauer M (2017) Improving local search in a minimum vertex cover solver for classes of networks. In: Proceedings of CEC, pp 1704–1711
go back to reference Wegener I (2001) Theoretical aspects of evolutionary algorithms. In: Proceedings of ICALP, pp 64–78 Wegener I (2001) Theoretical aspects of evolutionary algorithms. In: Proceedings of ICALP, pp 64–78
go back to reference Welsh DJ (2010) Matroid theory. Courier Corporation Welsh DJ (2010) Matroid theory. Courier Corporation
go back to reference Witt C (2005) Worst-case and average-case approximations by simple randomized search heuristics. In: Proceedings of STACS, pp 44–56 Witt C (2005) Worst-case and average-case approximations by simple randomized search heuristics. In: Proceedings of STACS, pp 44–56
go back to reference Zhu Z, Stein ML (2006) Spatial sampling design for prediction with estimated parameters. J Agric Biol Environ Stat 11(1):24–44 CrossRef Zhu Z, Stein ML (2006) Spatial sampling design for prediction with estimated parameters. J Agric Biol Environ Stat 11(1):24–44 CrossRef
go back to reference Zimmerman DL (2006) Optimal network design for spatial prediction, covariance parameter estimation, and empirical prediction. Environmetrics 17(6):635–652 MathSciNetCrossRef Zimmerman DL (2006) Optimal network design for spatial prediction, covariance parameter estimation, and empirical prediction. Environmetrics 17(6):635–652 MathSciNetCrossRef
Metadata
Title
Evolutionary algorithms and submodular functions: benefits of heavy-tailed mutations
Authors
Francesco Quinzan
Andreas Göbel
Markus Wagner
Tobias Friedrich
Publication date
16-02-2021
Publisher
Springer Netherlands
Published in
Natural Computing / Issue 3/2021
Print ISSN: 1567-7818
Electronic ISSN: 1572-9796
DOI
https://doi.org/10.1007/s11047-021-09841-7

Other articles of this Issue 3/2021

Natural Computing 3/2021 Go to the issue

Premium Partner