Towards a complexity theory of randomized search heuristics: ranking-based black-box complexity. (English) Zbl 1330.68110
Kulikov, Alexander (ed.) et al., Computer science – theory and applications. 6th international computer science symposium in Russia, CSR 2011, St. Petersburg, Russia, June 14–18, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-20711-2/pbk). Lecture Notes in Computer Science 6651, 15-28 (2011).
Summary: Randomized search heuristics are a broadly used class of general-purpose algorithms. Analyzing them via classical methods of theoretical computer science is a growing field. A big step forward would be a useful complexity theory for such algorithms. We enrich the two existing black-box complexity notions due to Wegener and other authors by the restrictions that not actual objective values, but only the relative quality of the previously evaluated solutions may be taken into account by the algorithm. Many randomized search heuristics belong to this class of algorithms. We show that the new ranking-based model gives more realistic complexity estimates for some problems, while for others the low complexities of the previous models still hold.
For the entire collection see [Zbl 1215.68017].
For the entire collection see [Zbl 1215.68017].
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |
| 68W20 | Randomized algorithms |
| 90C59 | Approximation methods and heuristics in mathematical programming |
References:
| [1] | Aldous, D.: Minimization algorithms and random walk on the d-cube. Annals of Probability 11, 403–413 (1983) · Zbl 0513.60068 · doi:10.1214/aop/1176993605 |
| [2] | Anil, G., Paul Wiegand, R.: Black-box search by elimination of fitness functions. In: Proc. of Foundations of Genetic Algorithms (FOGA 2009), pp. 67–78. ACM, New York (2009) · Zbl 1369.68291 |
| [3] | Doerr, B., Johannsen, D., Kötzing, T., Lehre, P.K., Wagner, M., Winzen, C.: Faster black-box algorithms through higher arity operators, ArXiv e-prints 1012.0952 (2010); Foundations of Genetic Algorithms XI FOGA (2011, to appear) · Zbl 1369.68238 |
| [4] | Droste, S., Jansen, T., Tinnefeld, K., Wegener, I.: A new framework for the valuation of algorithms for black-box optimization. In: Proc. of Foundations of Genetic Algorithms (FOGA 2003), pp. 253–270 (2003) |
| [5] | Droste, S., Jansen, T., Wegener, I.: Upper and lower bounds for randomized search heuristics in black-box optimization. Theory of Computing Systems 39, 525–544 (2006) · Zbl 1103.68115 · doi:10.1007/s00224-004-1177-z |
| [6] | Doerr, B., Winzen, C.: Towards a Complexity Theory of Randomized Search Heuristics: Ranking-Based Black-Box Complexity, ArXiv e-prints 1102.1140 (2011) · Zbl 1330.68110 |
| [7] | Garey, M.R., Johnson, D.S.: Computers and intractability; a guide to the theory of np-completeness. W. H. Freeman & Co., New York (1990) · Zbl 0411.68039 |
| [8] | Hansen, N.: Private communication (2010) |
| [9] | Horn, J., Goldberg, D., Deb, K.: Long path problems. In: Davidor, Y., Männer, R., Schwefel, H.-P. (eds.) PPSN 1994. LNCS, vol. 866, pp. 149–158. Springer, Heidelberg (1994) · doi:10.1007/3-540-58484-6_259 |
| [10] | Hausmann, D., Korte, B.: Lower bounds on the worst-case complexity of some oracle algorithms. Discrete Math. 24, 261–276 (1978) · Zbl 0392.68036 · doi:10.1016/0012-365X(78)90097-3 |
| [11] | Hromkovič, J.: Algorithmics for hard problems: introduction to combinatorial optimization, randomization, approximation, and heuristics, 2nd edn. Springer, New York (2003) |
| [12] | Llewellyn, D.C., Tovey, C., Trick, M.: Local optimization on graphs. Discrete Appl. Math. 23, 157–178 (1989) Erratum: 46, 93–94 (1993) · Zbl 0675.90085 · doi:10.1016/0166-218X(89)90025-5 |
| [13] | Lehre, P.K., Witt, C.: Black-box search by unbiased variation. In: Proc. of Genetic and Evolutionary Computation Conference (GECCO 2010), pp. 1441–1448. ACM, New York (2010) · Zbl 1264.68221 |
| [14] | Motwani, R., Raghavan, P.: Randomized algorithms. Cambridge University Press, Cambridge (1995) · Zbl 0849.68039 · doi:10.1017/CBO9780511814075 |
| [15] | Yao, A.C.-C.: Probabilistic computations: Toward a unified measure of complexity. In: Proc. of 18th Annual Symposium on Foundations of Computer Science (FOCS 1977), pp. 222–227 (1977) · doi:10.1109/SFCS.1977.24 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
