DOI: 10.17586/2226-1494-2017-17-6-1100-1106


N. S. Bulanova, A. S. Buzdalova, A. A. Shalyto

Read the full article 
Article in русский

For citation: Bulanova N.S., Buzdalova A.S., Shalyto A.A. Adaptive selection of artificial immune systems and local search mutation operators. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2017, vol. 17, no. 6, pp. 1100–1106 (in Russian). doi: 10.17586/2226-1494-2017-17-6-1100-1106

Subject of Research.Evolutionary algorithms use various mutation operations, which can be optimal at different stages of optimization. We formulate the task of choosing the most suitable mutation operator while optimizing. We propose a method for adaptive selection of mutation operators with probability depending on the current fitness. This property makes this method efficient on every stage of optimization. Method. We use two classes of algorithms: artificial immune systems, which are efficient at the initial stage of optimization, and randomized local search, which is efficient towards the end. The new method and the existing algorithms are compared experimentally on two benchmark problems. Main Results. The method for adaptive selection between artificial immune systems and local search mutation operators is developed. An experimental comparison of the proposed method with existing ones was performed. It showed that the proposed method is efficient under various computational budgets and finds optimal problem solutions faster than the other methods. Practical Relevance. The proposed modification improves the performance of algorithms when solving dynamic optimization problems with fitness functions changing in time, such as Pickup-and-Delivery Problem.

Keywords: artificial immune systems, local search, hybridisation, reinforcement learning, memetic algorithms

1.      Gladkov L.A., Kureichik V.V., Kureichik V.M. Genetic Algorithms.Moscow, Fizmatlit Publ., 2006, 320 p. (In Russian)
2.      Mitchell M. An Introduction to Genetic Algorithms. Cambridge, MIT Press, 1996, 221 p.
3.      Forrest S., Allen L., Perelson A.S., Cherukuri R. Self-nonself discrimination in a computer. Proc. IEEE Symposium on Research in Security and Privacy. Oakland, USA, 1994, pp. 202–212.
4.      Timmis J., Neal M.J. A resource limited artificial immune system for data analysis. Knowledge-Based Systems, 2001, vol. 14, no. 3-4, pp. 121–130. doi: 10.1016/S0950-7051(01)00088-0
5.      Neri F., Cotta C., Moscato P. Handbook of Memetic Algorithms. Springer, 2012, 370 p. doi: 10.1007/978-3-642-23247-3
6.      Sudholt D. Memetic algorithms with variable-depth search to overcome local optima. Proc. 10th Genetic and Evolutionary Computation Conference. Atlanta, USA, 2008, pp. 787–794.
7.      Smith J.E. Self-adaptative and coevolving memetic algorithms. Studies in Computational Intelligence,2012, vol. 379, pp. 167–188. doi: 10.1007/978-3-642-23247-3_11
8.      Sutton R.S., Barto A.G. Reinforcement Learning: An Introduction. Cambridge, MIT Press, 1998, 344 p.
9.      Buzdalova A., Kononov V., Buzdalov M. Selecting evolutionary operators using reinforcement learning: Initial explorations. Proc. 16th Genetic and Evolutionary Computation Conference. Vancouver, Canada, 2014, pp. 1033–1036. doi: 10.1145/2598394.2605681
10.   Corus D. On easiest functions for somatic contiguous hypermutations and standard bit mutations. Proc. 17th Genetic and Evolutionary Computation Conference. Madrid, Spain, 2015, pp. 1399–1406. doi: 10.1145/2739480.2754799
11.   Savelsbergh M.W.P., Sol M. The general pickup and delivery problem. Transportation Science, 1995, vol. 29, no.1, pp.
12.   Zarges C. Theoretical Foundations of Artificial Immune Systems. PhD Thesis. Universitat Dortmund, 2011.
13.   Oliveto P.S., He J., Yao X. Time complexity of evolutionary algorithms for combinatorial optimization: a decade of results. International Journal of Automation and Computing, 2007, vol. 4, no. 3, pp. 281–293. doi: 10.1007/s11633-007-0281-3
14.   Bottcher S., Doerr B., Neumann F. Optimal fixed and adaptive mutation rates for the LeadingOnes problem. Lecture Notes in Computer Science, 2010, vol. 6238, pp. 1–10. doi: 10.1007/978-3-642-15844-5_1
15.   de Castro L.N., von Zuben F.J. Learning and optimization using the clonal selection principle. IEEE Transactions on Evolutionary Computation, 2002, vol. 6, no. 3, pp. 239–251. doi: 10.1109/TEVC.2002.1011539
16.   Kelsey J., Timmis J. Immune inspired somatic contiguous hypermutation for function optimization. Lecture Notes in Computer Science, vol. 2723, pp. 207–218.
17.   Jansen T., Oliveto P.S., Zarges C. On the analysis of the immune-inspired B-cell algorithm for the vertex cover problem. Lecture Notes in Computer Science, 2011, vol. 6825, pp. 117–131. doi: 10.1007/978-3-642-22371-6_13
18.   He J., Yao X. Drift analysis and average time complexity of evolutionary algorithms. Artificial Intelligence, 2001, vol. 127, pp. 57–85. doi: 10.1016/S0004-3702(01)00058-3
19.   Mann H.B., Whitney D.R. On a test of whether one of two random variables is stochastically larger than the other. Annals of Mathematical Statistics, 1947, vol. 18, no. 1, pp. 50–60.
20.   Holm S. A simple sequentially rejective multiple test procedure. Scandinavian Journal of Statistics, 1979, vol. 6, no. 2, pp. 65–70.

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License
Copyright 2001-2019 ©
Scientific and Technical Journal
of Information Technologies, Mechanics and Optics.
All rights reserved.