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


УДК004.415.53:004.832.23

МЕТОД АДАПТИВНОГО ВЫБОРА ОПЕРАТОРОВ МУТАЦИИ ИСКУССТВЕННЫХ ИММУННЫХ СИСТЕМ И ЛОКАЛЬНОГО ПОИСКА

Буланова Н. С., Буздалова А. С., Шалыто А. А.


Язык статьи - русский

Ссылка для цитирования: Буланова Н.С., Буздалова А.С., Шалыто А.А. Метод адаптивного выбора операторов мутации искусственных иммунных систем и локального поиска // Научно-технический вестник информационных технологий, механики и оптики. 2017. Т. 17. № 6. С. 1100–1106. doi: 10.17586/2226-1494-2017-17-6-1100-1106

Аннотация
Предмет исследования. Рассмотреныэволюционные алгоритмы, использующие различные операторы мутации, которые могут быть эффективными на различных этапах оптимизации. Поставлена задача выбора наиболее подходящих операторов мутации в процессе оптимизации. Предложен адаптивный метод, выбирающий тот или иной оператор мутации с вероятностью, зависящей от значения функции приспособленности особи. Это свойство позволяет методу быть эффективным на каждом этапе оптимизации. Метод. В методе адаптивного выбора операторов мутации использованы алгоритмы искусственных иммунных систем, эффективные на начальном этапе оптимизации, и алгоритмы локального поиска, эффективные на заключительном этапе. Для анализа эффективности разработанного метода было проведено его сравнение с существующими методами на модельных задачах. Основные результаты. Разработан метод адаптивного выбора операторов мутации искусственных иммунных систем и локального поиска. Произведено экспериментальное сравнение эффективности предложенного метода с существующими аналогами. Исследование показывает, что разработанный метод эффективен при различных временных ограничениях и находит оптимальные решения задач в лучших, чем у аналогов, временных пределах. Практическая значимость. Предложенный метод позволяет разрабатывать алгоритмы, эффективные при решении динамических задач с оптимизируемой функцией, изменяющейся во времени. Примером такой задачи может служить задача о маршрутизации транспорта (англ. Pickup-and-Delivery Problem).

Ключевые слова: искусственные иммунные системы, локальный поиск, гибридизация, обучение с подкреплением, меметические алгоритмы

Список литературы
1.      Гладков Л.А., Курейчик В.В., Курейчик В.М.Генетические алгоритмы. М.: Физматлит, 2006. 320 с.
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. P. 202–212.
4.      Timmis J., Neal M.J. A resource limited artificial immune system for data analysis // Knowledge-Based Systems. 2001. V. 14. N 3-4. P. 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. P. 787–794.
7.      Smith J.E. Self-adaptative and coevolving memetic algorithms // Studies in Computational Intelligence.2012. V. 379. P. 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. P. 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. P. 1399–1406. doi: 10.1145/2739480.2754799
11.   Savelsbergh M.W.P., Sol M. The general pickup and delivery problem // Transportation Science. 1995. V. 29. N1. P. 17–29.
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. V. 4. N 3. P. 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. V. 6238. P. 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. V. 6. N 3. P. 239–251. doi: 10.1109/TEVC.2002.1011539
16.   Kelsey J., Timmis J. Immune inspired somatic contiguous hypermutation for function optimisation // Lecture Notes in Computer Science. V. 2723. P. 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. V. 6825. P. 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. V. 127. P. 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. V. 18. N 1. P. 50–60.
20.   Holm S. A simple sequentially rejective multiple test procedure // Scandinavian Journal of Statistics. 1979. V. 6. N 2. P. 65–70.
Информация 2001-2018 ©
Научно-технический вестник информационных технологий, механики и оптики.
Все права защищены.

Яндекс.Метрика