A framework for co-optimization algorithm performance and its application to worst-case optimization.

*(English)*Zbl 1314.68295Summary: Traditional black-box optimization searches a set of potential solutions for those optimizing the value of a function whose analytical or algebraic form is unknown or inexistent, but whose value can be queried for any input. Co-optimization is a generalization of this setting, in which fully evaluating a potential solution may require querying some function more than once, typically a very large number of times. When that’s the case, co-optimization poses unique difficulties to designing and assessing algorithms. A generally-applicable approach is to judge co-optimization algorithm performance via an aggregate over all possible functions in the problem domain. We establish formal definitions of such aggregate performance and then investigate the following questions concerning algorithm design: 1) are some algorithms strictly better than others? i.e. is there “free lunch”? 2) do optimal algorithms exist? and 3) if so, are they practical? We formally define free lunch and aggregate optimality of co-optimization algorithms and derive generic conditions for their existence. We review and explain prior (no) free lunch results from the perspective of these conditions; we also show how this framework can be used to bridge several fields of research, by allowing formalization of their various problems and views on performance. We then apply and extend the generic results in a context involving a particular type of co-optimization called worst-case optimization. In this context we show that there exist algorithms that are aggregately-optimal for any budget (allowed number of function calls) and any starting point (set of previously uncovered function call outcomes), and also non-trivially strictly optimal for many budgets and starting points; moreover, we formalize the operation of such optimal algorithms and show that for certain domains, budgets and starting points this operation is equivalent to a simple procedure with tractable implementation – a first-of-its-kind result for co-optimization.

##### MSC:

68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |

90C59 | Approximation methods and heuristics in mathematical programming |

##### Keywords:

co-optimization; solution concepts; performance; optimality; free lunch; worst-case optimization; best worst-case; minimax; maximin; coevolution
PDF
BibTeX
XML
Cite

\textit{E. Popovici} and \textit{E. Winston}, Theor. Comput. Sci. 567, 46--73 (2015; Zbl 1314.68295)

Full Text:
DOI

##### References:

[1] | Wolpert, D.; Macready, W., Coevolutionary free lunches, IEEE Trans. Evol. Comput., 9, 721-735, (2005) |

[2] | Ficici, S. G., Solutions concepts in coevolutionary algorithms, (2004), Brandeis University Department of Computer Science USA, Ph.D. thesis |

[3] | Wolpert, D.; Macready, W., No free lunch theorems for optimization, IEEE Trans. Evol. Comput., 1, 67-82, (1997) |

[4] | Droste, S.; Jansen, T.; Wegener, I., Perhaps not a free lunch but at least a free appetizer, (Banzhaf, W.; Daida, J. M.; Eiben, A. E.; Garzon, M. H.; Honavar, V.; Jakiela, M. J.; Smith, R. E., GECCO, (1999), Morgan Kaufmann), 833-839 |

[5] | Droste, S.; Jansen, T.; Wegener, I., Optimization with randomized search heuristics - the (a)nfl theorem, realistic scenarios, and difficult functions, Theoret. Comput. Sci., 287, 131-144, (2002) · Zbl 1061.68145 |

[6] | Schumacher, C.; Vose, M. D.; Whitley, L. D., The no free lunch and problem description length, (Proceedings of the Genetic and Evolutionary Computation Conference, GECCO-2001, (2001), Morgan Kaufmann), 565-570 |

[7] | Corne, D. W.; Knowles, J. D., No free lunch and free leftovers theorems for multiobjective optimisation problems, (Evolutionary Multi-criterion Optimization (EMO 2003) Second International Conference, LNCS, (2003), Springer), 327-341 · Zbl 1036.90523 |

[8] | Igel, C.; Toussaint, M., A no-free-lunch theorem for non-uniform distributions of target functions, J. Math. Model. Algorithms, 3, 313-322, (2004) · Zbl 1079.90111 |

[9] | Streeter, M. J., Two broad classes of functions for which a no free lunch result does not hold, (Proceedings of the Genetic and Evolutionary Computation Conference, GECCO-2003, (2003), Morgan Kaufmann), 1418-1430 · Zbl 1038.68880 |

[10] | Igel, C.; Toussaint, M., On classes of functions for which no free lunch results hold, Inf. Process. Lett., 86, 317-321, (2003) · Zbl 1162.68816 |

[11] | Everitt, T., Universal induction and optimisation: no free lunch?, (2013), Stockholm University Department of Mathematics Sweden, Master’s thesis |

[12] | Auger, A.; Teytaud, O., Continuous lunches are free plus the design of optimal optimization algorithms, Algorithmica, 57, 121-146, (2010) · Zbl 1206.90133 |

[13] | Service, T. C.; Tauritz, D. R., A no-free-lunch framework for coevolution, (Proceedings of the Genetic and Evolutionary Computation Conference, (2008), ACM), 371-378 |

[14] | Service, T. C., Unbiased coevolutionary solution concepts, (Foundations of Genetic Algorithms, (2009), ACM Press), 121-130 · Zbl 1369.68330 |

[15] | Service, T. C., Free lunches in Pareto coevolution, (Proceedings of the Genetic and Evolutionary Computation Conference, (2009), ACM Press), 1721-1728 |

[16] | Halck, O. M.; Dahl, F. A., Asymmetric co-evolution for imperfect-information zero-sum games, (European Conference on Machine Learning, (2000), Springer), 171-182 |

[17] | Barbosa, H. J.C., A genetic algorithm for MIN-MAX problems, (Proceedings of the International Conference on Evolutionary Computation and Its Applications, (1996), Presidium of the Russian Academy of Sciences), 99-109 |

[18] | Dem’yanov, V. F.; Malozemov, V. N., Introduction to minimax, (1974), John Wiley & Sons · Zbl 0277.52007 |

[19] | Barbosa, H. J.C., A coevolutionary genetic algorithm for constrained optimization, (Proceedings of the Congress on Evolutionary Computation, (1999), IEEE Press), 1605-1611 |

[20] | Kouvelis, P.; Yu, G., Robust discrete optimization and its applications, (1997), Kluwer · Zbl 0873.90071 |

[21] | Barbosa, H. J.C., A coevolutionary genetic algorithm for a game approach to structural optimization, (Proceedings of the International Conference on Genetic Algorithms, (1997), Morgan Kaufmann), 545-552 |

[22] | Popovici, E.; Bandte, O.; Gaudiano, P., New approaches for the automated performance evaluation and design of control systems: a firemain example, (Proceedings of the Automation and Controls Symposium, (2007), American Society of Naval Engineers) |

[23] | Herrmann, J. W., A genetic algorithm for minimax optimization problems, (Proceedings of the Congress on Evolutionary Computation, (1999), IEEE Press), 1099-1103 |

[24] | Jensen, M. T., Finding worst-case flexible schedules using coevolution, (Proceedings of the Genetic and Evolutionary Computation Conference, (2001), Morgan Kaufmann), 1144-1151 |

[25] | Jensen, M. T., Robust and flexible scheduling with evolutionary computation, (2001), Department of Computer Science, University of Aarhus Denmark, Ph.D. thesis |

[26] | Popovici, E.; De Jong, K. A., Monotonicity versus performance in co-optimization, (Foundations of Genetic Algorithms, (2009), ACM Press), 151-170 · Zbl 1369.68327 |

[27] | Popovici, E.; Winston, E.; Bucci, A., On the practicality of optimal output mechanisms for co-optimization algorithms, (Foundations of Genetic Algorithms, (2011), ACM Press), 43-60 · Zbl 1369.68328 |

[28] | Popovici, E., An analysis of two-population coevolutionary computation, (2006), George Mason University USA, Ph.D. thesis |

[29] | Popovici, E.; Bucci, A.; Wiegand, R. P.; De Jong, E. D., Coevolutionary principles, (Rozenberg, G.; Back, T.; Kok, J. N., Handbook of Natural Computing, Theoret. Comput. Sci., (2010), Springer-Verlag Berlin), 987-1033 |

[30] | Jansen, T., Black-box complexity for bounding the performance of randomized search heuristics, (Borenstein, Y.; Moraglio, A., Theory and Principled Methods for the Design of Metaheuristics, Natural Computing Series, (2014), Springer Berlin/Heidelberg), 85-110 · Zbl 1328.68197 |

[31] | Sutton, R. S.; Barto, A. G., Introduction to reinforcement learning, (1998), MIT Press Cambridge, MA, USA |

[32] | Service, T. C.; Tauritz, D. R., Co-optimization algorithms, (Proceedings of the Genetic and Evolutionary Computation Conference, (2008), ACM), 387-388 |

[33] | Tesauro, G., Temporal difference learning and TD-gammon, Commun. ACM, 38, 58-68, (1995) |

[34] | Anil, G.; Wiegand, R. P., Black-box search by elimination of fitness functions, (Proceedings of the Tenth ACM SIGEVO Workshop on Foundations of Genetic Algorithms, FOGA ’09, (2009), ACM New York, NY, USA), 67-78 · Zbl 1369.68291 |

[35] | Jansen, T.; Zarges, C., Fixed budget computations: a different perspective on run time analysis, (Proceedings of the 14th Annual Conference on Genetic and Evolutionary Computation, GECCO ’12, (2012), ACM New York, NY, USA), 1325-1332 |

[36] | Jansen, T.; Zarges, C., Performance analysis of randomised search heuristics operating with a fixed budget, Theoret. Comput. Sci., 545, 39-58, (2014) · Zbl 1360.68781 |

[37] | Nallaperuma, S.; Neumann, F.; Sudholt, D., A fixed budget analysis of randomized search heuristics for the traveling salesperson problem, (Arnold, D. V., GECCO, (2014), ACM), 807-814 |

[38] | Doerr, B.; Jansen, T.; Witt, C.; Zarges, C., A method to derive fixed budget results from expected optimisation times, (Proceedings of the 15th Annual Conference on Genetic and Evolutionary Computation, GECCO ’13, (2013), ACM New York, NY, USA), 1581-1588 |

[39] | Doerr, B.; Winzen C, C., Playing mastermind with constant-size memory, (Proc. of the Symposium on Theoretical Aspects of Computer Science, STACS’12, (2012), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik), 441-452 · Zbl 1245.68144 |

[40] | Whitley, D.; Rowe, J., A “no free lunch” tutorial: sharpened and focused no free lunch, (Auger, A.; Doerr, B., Theory of Randomized Search Heuristics. Foundations and Recent Developments, Series on Theoretical Computer Science, vol. 1, (2011), World Scientific Singapore), 255-287 · Zbl 1235.90190 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.