Hitting times of local and global optima in genetic algorithms with very high selection pressure
DOI:
https://doi.org/10.2298/YJOR160318016EKeywords:
combinatorial optimization, evolutionary algorithms, runtime analysis, fitness level, local searchAbstract
The paper is devoted to upper bounds on the expected first hitting times of the sets of local or global optima for non-elitist genetic algorithms with very high selection pressure. The results of this paper extend the range of situations where the upper bounds on the expected runtime are known for genetic algorithms and apply, in particular, to the Canonical Genetic Algorithm. The obtained bounds do not require the probability of fitness-decreasing mutation to be bounded by a constant which is less than one.References
Aggarwal, C.C., Orlin, J.B. and Tai, R.P., ”An optimized crossover for maximum independent set”, Operations Research, 45 (1997) 225-234.
Ausiello, G., and Protasi, M., ”Local search, reducibility and approximability of NP-optimization problems”, Information Processing Letters, 54 (1995) 73-79.
Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., and Protasi, M., Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer-Verlag, Berlin, 1999.
Balas, E., ”A sharp bound on the ratio between optimal integer and fractional covers”, Mathematics of Operations Research, 9 (1) (1984) 1-5.
Balas, E., and Niehaus, W., ”Optimized crossover-based genetic algorithms for the maximum cardinality and maximum weight clique problems”, Journal of Heuristics, 4 (2) (1998) 107-122.
Barahona, F., ”On the computational complexity of Ising spin glass models”, Journal of Physics A, Mathematical and General, 15 (1982) 3241-3253.
Beasley, J.E., and Chu, P.C., ”A genetic algorithm for the set covering problem”, European Journal of Operational Research, 94 (2) (1996) 394-404.
Borisovsky, P., Eremeev, A., Grinkevich, E., Klokov, S., and Kosarev, N., ”Trading hubs construction in electricity markets using evolutionary algorithms”, Pattern Recognition and Image Analysis, 24 (2) (2014) 270-282.
Brimberg, J., Hansen, P., and Mladenovic, N., ”Attraction probabilities in variable neighborhood search”, 4OR, 8 (2) (2010) 181-194.
Corus, D., Dang, D.-C., Eremeev, A.V., and Lehre, P.K., ”Level-based analysis of genetic algorithms and other search processes”, Proceedings of Parallel Problem Solving from Nature (PPSN XIII), Springer, LNCS Vol. 8672, 2014, 912-921.
Dang, D.-C., and Lehre, P.K., ”Runtime analysis of non-elitist populations: From classical optimisation to partial information”, Algorithmica, 75 (3) (2016) 428-461.
Doerr, C., and Lengler, J., ”Elitist black-box models: analyzing the impact of elitist selection on the performance of evolutionary algorithms”, Proceedings of Genetic and Evolutionary Computation Conference (GECCO), ACM, New York, 2015, 839-846.
Eremeev, A.V., ”A genetic algorithm with tournament selection as a local search method”, Journal of Applied and Industrial Mathematics, 6 (3) (2012) 286-294.
Eremeev, A. V., ”Non-elitist genetic algorithm as a local search method”, Preprint (arXiv:1307.3463v2 [cs.NE]), Cornell: Cornell University (2013) 9 p. URL: http://arxiv.org/abs/1307.3463.
Eremeev, A.V., and Kovalenko, J.V., ”Optimal recombination in genetic algorithms for combinatorial optimization problems Part I”, Yugoslav Journal of Operations Research, 24 (1) (2014) 1-20.
Gnedenko, B.V., Theory of Probability, Gordon and Breach, Amsterdam, 1997.
Goldberg, D.E., Genetic Algorithms in Search, Optimization and Machine Learning, Reading, MA: Addison-Wesley, 1989.
Goldberg, D.E., ”A note on Boltzmann tournament selection for genetic algorithms and population-oriented simulated annealing”, Complex Systems, 4 (1990) 445-460.
He, J., and Yao, X., ”Drift analysis and average time complexity of evolutionary algorithms”, Artificial Intelligence, 127 (1) (2001) 57-85.
Jansen, T., and Wegener, I., ”On the analysis of evolutionary algorithms– a proof that crossover really can help”, Algorithmica, 34 (1) (2002) 47-66.
Kochetov, Yu.A., and Plyasunov, A. V., ”Genetic local search for the graph partitioning problem under cardinality constraints”, Computational Mathematics and Mathematical Physics, 52 (1) (2012) 157-167.
Kolokolov, A.A., ”Regular partitions and cuts in integer programming”, Discrete Analysis and Operations Research, Kluwer Academic Publishers (1996) 59-79.
Kötzing, T., Sudholt, D., and Theile, M., ”How crossover helps in pseudo-boolean optimization”, Proceedings of the 13th Conference on Genetic and Evolutionary Computation (GECCO), (2011) 989-996.
Lehre, P.K. ”Negative drift in populations”, Proceedings of the 11th International conference on Parallel Problem Solving from Nature (PPSN), (2010) 244–253.
Lehre, P.K., ”Fitness levels for non-elitist populations”, Proceedings of 13th Conf. on Genetic and Evolutionary Computation (GECCO), 2011, 2075-2082.
Lehre, P.K., and Yao, X., ”Crossover can be constructive when computing unique input-output sequences”, Soft Computing, 15 (9) (2011) 1675–1687.
Moraglio, A., and Sudholt, D., ”Principled design and runtime analysis of abstract convex evolutionary search”, Evolutionary Computation (2015) Posted Online. URL: http://dx.doi.org/10.1162/EVCO_a_00169
Oliveto, P.S., and Witt, C., ”On the runtime analysis of the simple genetic algorithm”, Theoretical Computer Science, 545 (2014) 2–19.
Rudolph, G., ”Convergence analysis of canonical genetic algorithms”, IEEE Transactions on Neural Networks, 5 (1) (1994) 96-101.
Sudholt, D., ”A new method for lower bounds on the running time of evolutionary algorithms”, IEEE Transactions on Evolutionary Computation, 17 (3) (2012) 418-435.
Sudholt, D., ”Crossover speeds up building-block assembly”, Proceedings of Genetic and Evolutionary Computation Conference (GECCO), 2012, 689-702.
Vitányi, P.M.B., ”A discipline of evolutionary programming”, Theoretical Computer Science, 241 (1-2) (2000) 3-23.
Vose, M.D., The Simple Genetic Algorithm: Foundations and Theory, MIT Press, Cambridge, MA, 1999.
Zaozerskaya, L.A., ”Investigation and solving of some classes of integer programming problems on the basis of the regular partitions”, PhD. thesis, Omsk Branch of Sobolev Institute of Mathematics, SB RAS, 1998.
Downloads
Published
Issue
Section
License
Copyright (c) 2017 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
