Abstract
In order to increase the performance of an evolutionary algorithm, additional auxiliary optimization objectives may be added. It is hard to predict which auxiliary objectives will be the most efficient at different stages of optimization. Thus, the problem of dynamic selection between auxiliary objectives appears. This paper proposes a new method for efficient selection of auxiliary objectives, which uses fitness landscape information and problem meta-features. An offline learned meta-classifier is used to dynamically predict the most efficient auxiliary objective during the main optimization run performed by an evolutionary algorithm. An empirical evaluation on two benchmark combinatorial optimization problems (Traveling Salesman and Job Shop Scheduling problems) shows that the proposed approach outperforms similar known methods of auxiliary objective selection.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
References
Pitzer, E., Affenzeller, M.: A comprehensive survey on fitness landscape analysis. In: Fodor, J., Klempous, R., Araujo, C.P.S. (eds.) Recent Adv. Intell. Eng. Syst., pp. 161–191. Springer, Heidelberg (2012)
Picek, S., Jakobovic, D.: From fitness landscape to crossover operator choice. In: Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation, pp. 815–822. ACM (2014)
Ceberio, J., Calvo, B., Mendiburu, A., Lozano, J.A.: Multi-objectivising the quadratic assignment problem by means of an elementary landscape decomposition. In: Puerta, J.M., Gámez, J.A., Dorronsoro, B., Barrenechea, E., Troncoso, A., Baruque, B., Galar, M. (eds.) CAEPIA 2015. LNCS (LNAI), vol. 9422, pp. 289–300. Springer, Heidelberg (2015). doi:10.1007/978-3-319-24598-0_26
Jensen, T.: Helper-objectives: using multi-objective evolutionary algorithms for single-objective optimisation. J. Math. Model. Algorithms 3(4), 323–347 (2005)
Buzdalova, A., Buzdalov, M.: Increasing efficiency of evolutionary algorithms by choosing between auxiliary fitness functions with reinforcement learning. In: 2012 11th International Conference on Machine Learning and Applications (ICMLA), vol. 1, pp. 150–155. IEEE (2012)
Knowles, J.D., Watson, R.A., Corne, D.W.: Reducing local optima in single-objective problems by multi-objectivization. In: Zitzler, E., Thiele, L., Deb, K., Coello Coello, C.A., Corne, D. (eds.) EMO 2001. LNCS, vol. 1993, pp. 269–283. Springer, Heidelberg (2001). doi:10.1007/3-540-44719-9_19
Petrova, I., Buzdalova, A., Buzdalov, M.: Improved selection of auxiliary objectives using reinforcement learning in non-stationary environment. In: 2014 13th International Conference on Machine Learning and Applications (ICMLA), pp. 580–583. IEEE (2014)
Applegate, D.L., Bixby, R.E., Chvatal, V., Cook, W.J.: The Traveling Salesman Problem: A Computational Study. Princeton University Press, Princeton (2011)
Kanda, J., Carvalho, A., Hruschka, E., Soares, C.: Using meta-learning to classify traveling salesman problems. In: 2010 Eleventh Brazilian Symposium on Neural Networks, pp. 73–78. IEEE (2010)
Kanda, J.Y., de Carvalho, A.C., Hruschka, E.R., Soares, C.: Using meta-learning to recommend meta-heuristics for the traveling salesman problem. In: 2011 10th International Conference on Machine Learning and Applications and Workshops (ICMLA), pp. 346–351. IEEE (2011)
Cover, T., Hart, P.: Nearest neighbor pattern classification. IEEE Trans. Inf. Theory 13(1), 21–27 (1967)
Jähne, M., Li, X., Branke, J.: Evolutionary algorithms and multi-objectivization for the travelling salesman problem. In: Proceedings of the 11th Annual conference on Genetic and evolutionary computation, pp. 595–602. ACM (2009)
Johnson, D.S., McGeoch, L.A.: The traveling salesman problem: a case in study local optimization. Local Search Comb. Optim. 1, 215–310 (1997)
Deb, K., Pratap, A., Agarwal, S., Meyarivan, T.: A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. Evol. Comput. 6(2), 182–197 (2002)
Derrac, J., García, S., Molina, D., Herrera, F.: A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms. Swarm Evol. Comput. 1(1), 3–18 (2011)
Lochtefeld, D.F., Ciarallo, F.W.: Deterministic helper-objective sequences applied to job-shop scheduling. In: Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation, pp. 431–438. ACM (2010)
Lochtefeld, D.F., Ciarallo, W.: Helper-objective optimization strategies for the job-shop scheduling problem. Appl. Soft Comput. 11(6), 4161–4174 (2011)
Petrova, I., Buzdalova, A., Buzdalov, M.: Improved helper-objective optimization strategy for job-shop scheduling problem. In: 2013 12th International Conference on Machine Learning and Applications (ICMLA), pp. 374–377, vol 2. IEEE (2013)
Bierwirth, C.: A generalized permutation approach to job shop scheduling with genetic algorithms. Oper. -Res. -Spektrum 17(2–3), 87–92 (1995)
Giffler, B., Thompson, G.L.: Algorithms for solving production-scheduling problems. Oper. Res. 8(4), 487–503 (1960)
López-Ibáñez, M., Dubois-Lacoste, J., Stützle, T., Birattari, M.: The irace package, iterated race for automatic algorithm configuration. Technical report TR/IRIDIA/2011-004, IRIDIA, Université Libre de Bruxelles, Belgium (2011)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
A Appendix: TSP and JSSP Instances Lists
A Appendix: TSP and JSSP Instances Lists
TSP Train: att532, bays29, brazil58, ch130, d198, d493, eil101, gil262, gr120, gr202, gr24, gr431, hk48, kroA150, kroB200, kroE100, p654, pa561, pr136, pr264, rat575, rat99, si175, st70, ts225, u574, ulysses22. TSP Cross-validate: a280, att48, bayg29, bays29, berlin52, bier127, brazil58, brg180, burma14, ch130, ch150, d198, d493, dantzig42, eil101, eil51, eil76, fl417, fri26, gil262, gr17, gr21, gr24, gr48, gr96, gr120, gr137, gr202, gr229, gr431, hk48, kroA100, kroA150, kroA200, kroB100, kroB150, kroB200, kroC100, kroD100, kroE100, lin105, lin318, pcb442, pr76, pr107, pr124, pr136, pr144, pr152, pr226, pr264, pr299, pr439, rat195, rat99, rd100, rd400, si175, st70, swiss42, ts225, tsp225, u159, ulysses16, ulysses22.
JSSP Train and Cross-validate: abz5, abz8, ft10, la02, la04, la07, la13, la15, la18, la19, la23, la24, la27, la28, la32, la33, la34, la37, la39, orb01, orb04, orb05, orb08, swv02, swv05, swv06, swv10, swv13, swv18, swv19, yn2, yn3.
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Bassin, A., Buzdalova, A. (2017). Selection of Auxiliary Objectives Using Landscape Features and Offline Learned Classifier. In: Hu, B., López-Ibáñez, M. (eds) Evolutionary Computation in Combinatorial Optimization. EvoCOP 2017. Lecture Notes in Computer Science(), vol 10197. Springer, Cham. https://doi.org/10.1007/978-3-319-55453-2_12
Download citation
DOI: https://doi.org/10.1007/978-3-319-55453-2_12
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-55452-5
Online ISBN: 978-3-319-55453-2
eBook Packages: Computer ScienceComputer Science (R0)