ADAPTIVE SELECTION OF AUXILIARY OBJECTIVES IN MULTIOBJECTIVE EVOLUTIONARY ALGORITHMS

Subject of Research.We propose to modify the EA+RL method, which increases efficiency of evolutionary algorithms by means of auxiliary objectives. The proposed modification is compared to the existing objective selection methods on the example of travelling salesman problem. Method. In the EA+RL method a reinforcement learning algorithm is used to select an objective – the target objective or one of the auxiliary objectives – at each iteration of the single-objective evolutionary algorithm.The proposed modification of the EA+RL method adopts this approach for the usage with a multiobjective evolutionary algorithm. As opposed to theEA+RL method, in this modification one of the auxiliary objectives is selected by reinforcement learning and optimized together with the target objective at each step of the multiobjective evolutionary algorithm. Main Results.The proposed modification of the EA+RL method was compared to the existing objective selection methods on the example of travelling salesman problem. In the EA+RL method and its proposed modification reinforcement learning algorithms for stationary and non-stationary environment were used. The proposed modification of the EA+RL method applied with reinforcement learning for non-stationary environment outperformed the considered objective selection algorithms on the most problem instances. Practical Significance. The proposed approach increases efficiency of evolutionary algorithms, which may be used for solving discrete NP-hard optimization problems. They are, in particular, combinatorial path search problems and scheduling problems.

1. Segura C., Coello C.A.C., Miranda G., Leon C. Using multi-objective evolutionary algorithms for single-objective optimization. 4OR, 2013, vol. 11, no. 3, pp. 201–228. doi: 10.1007/s10288-013-0248-x
2. Buzdalova A.S., Buzdalov M.V. Efficiency increasing method of the evolutionary algorithms by reinforcement learning. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2012, no. 5(91), pp. 115–119.
3. Buzdalova A., Buzdalov M. Increasing efficiency of evolutionary algorithms by choosing between auxiliary fitness functions with reinforcement learning. Proc. 11th Int. Conf. on Machine Learning and Applications. Boca Raton, USA, 2012, vol. 1, pp. 150–155. doi: 10.1109/ICMLA.2012.32
4. Buzdalov M., Buzdalova A., Shalyto A. A first step towards the runtime analysis of evolutionary algorithm adjusted with reinforcement learning. Proc. 12th Int. Conf. on Machine Learning and Applications. Miami, USA, 2013, vol. 1, pp. 203–208. doi: 10.1109/ICMLA.2013.42
5. Buzdalov M., Buzdalova A. Adaptive selection of helper-objectives for test case generation. Proc. IEEE Congress on Evolutionary Computation. Cancun, Mexico, 2013, vol. 1, pp. 2245–2250. doi: 10.1109/CEC.2013.6557836
6. Buzdalov M., Buzdalova A., Petrova I. Generation of tests for programming challenge tasks using multi-objective optimization. Proc. Genetic and Evolutionary Computation Conference Companion. Amsterdam, Netherlands, 2013, pp. 1655–1658. doi: 10.1145/2464576.2482746
7. Knowles J.D., Watson R.A., Corne D. Reducing local optima in single-objective problems by multi-objectivization. Lecture Notes in Computer Science, 2001, vol. 1993, pp. 269–283.
8. Petrova I., Buzdalova A., Buzdalov M. Improved selection of auxiliary objectives using reinforcement learning in non-stationary environment. Proc. 13th Int. Conf. on Machine Learning and Applications. Detroit, USA, 2014, pp. 580–583. doi: 10.1109/ICMLA.2014.99
9. Applegate D.L., Bixby R.E., Chvatal V., Cook W.J. The Traveling Salesman Problem: A Computational Study. Princeton University Press, 2007, 608 p.
10. Jensen M.T. Helper-objectives: using multi-objective evolutionary algorithms for single-objective optimisation: evolutionary computation combinatorial optimization. Journal of Mathematical Modelling and Algorithms, 2004, vol. 3, no. 4, pp. 323–347.
11. Jähne M., Li X., Branke J. Evolutionary algorithms and multi-objectivization for the travelling salesman problem. Proc. 11th Annual Genetic and Evolutionary Computation Conference. Montreal, Canada, 2009, pp. 595–602. doi: 10.1145/1569901.1569984
12. Skobtsov Yu.A., Fedorov E.E. Metaheuristics. Donetsk, Noulidzh Publ., 2013, 426 p.
13. Sutton R.S., Barto A.G. Reinforcement Learning: An Introduction. Cambridge, MIT Press, 1998, 322 p.
14. Afanasyeva A., Buzdalov M. Optimization with auxiliary criteria using evolutionary algorithms and reinforcement learning. Proc. 18th Int. Conf. on Soft Computing MENDEL. Brno, Czech Republic, 2012, pp. 58–63.
15. Derrac J., Garcia 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 and Evolutionary Computation, 2011, vol. 1, no. 1, pp. 3–18. doi: 10.1016/j.swevo.2011.02.002
 

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License