SelfCSHAGA: самоконфигурируемый генетический алгоритм оптимизации с адаптацией на основе истории успеха

Аннотация

Рассмотрена проблема повышения эффективности генетических алгоритмов оптимизации за счет применения методов самонастройки, которые изменяют параметры и поведение алгоритма в процессе поиска решения. Приведен обзор актуальных и наиболее эффективных методов самонастройки и адаптации, в рамках которого выделены их преимущества и недостатки. Предложен новый алгоритм, позволяющий объединить лучшие стороны отдельных методов. Он представляет собой расширенную версию SHAGA с усовершенствованной процедурой скрещивания, которая позволяет адаптировать его интенсивность, применять селективное давление на данном этапе и использовать многородительское скрещивание. Предложены различные варианты оператора скрещивания и метод самоконфигурирования генетических операторов на основе SelfCEA, который динамически корректирует вероятности их применения в зависимости от успешности. Предложенный алгоритм протестирован с применением статистических критериев для проверки значимости различий результатов и сравнения с другими подходами в задачах оптимизации с вещественными и булевыми переменными. В результате тестирования новый генетический алгоритм продемонстрировал более высокую эффективность и значительное улучшение надежности в большинстве тестовых задач

Работа выполнена при поддержке Минобрнауки России в рамках государственного задания в сфере науки (проект № FEFE-2023-0004)

Просьба ссылаться на эту статью следующим образом:

Шерстнев П.А., Семенкин Е.С. SelfCSHAGA: самоконфигурируемый генетический алгоритм оптимизации с адаптацией на основе истории успеха. Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение, 2025, № 2 (151), с. 122--139. EDN: TSKBOX

Литература

[1] Wang Z., Pei Y., Li J. A survey on search strategy of evolutionary multi-objective optimization algorithms. Appl. Sc., 2023, vol. 13, no. 7, art. 4643. DOI: https://doi.org/10.3390/app13074643

[2] Wolpert D.H., Macready W.G. No free lunch theorems for optimization. IEEE Trans. Evol. Comput., 1997, vol. 1, no. 1, pp. 67--82. DOI: https://doi.org/10.1109/4235.585893

[3] Kramer O. Evolutionary self-adaptation: a survey of operators and strategy parameters. Evol. Intel., 2010, vol. 3, no. 2, pp. 51--65. DOI: https://doi.org/10.1007/s12065-010-0035-y

[4] Meyer-Nieberg S., Beyer H.G. Self-adaptation in evolutionary algorithms. In: Parameter setting in evolutionary algorithms. Berlin, Heidelberg, Springer, 2007, pp. 47--75. DOI: https://doi.org/10.1007/978-3-540-69432-8_3

[5] Holland J.H. Genetic algorithms. Sc. Am., 1992, vol. 267, no. 1, pp. 66--72.

[6] Vie A., Kleinnijenhuis A.M., Farmer D.J. Qualities, challenges and future of genetic algorithms: a literature review. arXiv:2011.05277. DOI: https://doi.org/10.48550/arXiv.2011.05277

[7] Alam T., Qamar S., Dixit A., et al. Genetic algorithm: reviews, implementations, and applications. iJEP, 2020, vol. 10, no. 6, pp. 57--76. DOI: https://doi.org/10.36227/techrxiv.12657173

[8] Semenkin E.S., Semenkina M.E. Self-configuring genetic algorithm with modified uniform crossover operator. In: Lecture Notes in Computer Science, Cham, Springer Nature Switzerland, 2012, pp. 414--421. DOI: https://doi.org/10.1007/978-3-642-30976-2

[9] Semenkin E., Semenkina M. Self-configuring genetic programming algorithm with modified uniform crossover. IEEE CEC, 2012. DOI: https://doi.org/10.1109/CEC.2012.6256587

[10] Семенкина М.Е. Самоадаптивные эволюционные алгоритмы проектирования информационных технологий интеллектуального анализа данных. Искусственный интеллект и принятие решений, 2013, № 1, c. 13--24. EDN: QBWXYD

[11] Niehaus J., Banzhaf W. Adaption of operator probabilities in genetic programming. In: Genetic Programming. Berlin, Springer-Verlag, 2001, pp. 325--336. DOI: https://doi.org/10.1007/3-540-45355-5_26

[12] Липинский Л.В., Кушнарева Т.В. Исследование моделей и процедур самоконфигурации генетического программирования для формирования деревьев принятия решений в задачах интеллектуального анализа данных. Вестник СибГАУ им. академика М.Ф. Решетнева, 2016, т. 17, № 3, с. 579--586. EDN: WVPTZH

[13] Sopov A., Karaseva T. The comparison of different PDP-type self-adaptive schemes for the cooperation of GA, DE, and PSO algorithms. ITM Web Conf., 2024, vol. 59, art. 04013. DOI: https://doi.org/10.1051/itmconf/20245904013

[14] Tanabe R., Fukunaga A. Success-history based parameter adaptation for differential evolution. IEEE CEC, 2013, pp. 71--78. DOI: https://doi.org/10.1109/CEC.2013.6557555

[15] Rivera-Lopez R., Mezura-Montes E., Canul-Reich J., et al. An experimental comparison of self-adaptive differential evolution algorithms to induce oblique decision trees. Math. Comput. Appl., 2024, vol. 29, no. 6, p. 103. DOI: https://doi.org/10.3390/mca29060103

[16] Stanovov V., Akhmedova S., Semenkin E. Genetic algorithm with success history based parameter adaptation. IJCCI 2019, 2019, pp. 180--187. DOI: https://doi.org/10.5220/0008071201800187

[17] Yu E.L., Suganthan P.N. Ensemble of niching algorithms. Inform. Sc., 2010, vol. 180, no. 15, pp. 2815--2833. DOI: https://doi.org/10.1016/j.ins.2010.04.008

[18] Mann H.B., Whitney D.R. On a test of whether one of two random variables is stochastically larger than the other. Ann. Math. Statist., 1947, vol. 18, no. 1, pp. 50--60. DOI: https://doi.org/10.1214/aoms/1177730491

[19] Zhu X. Sample size calculation for Mann --- Whitney U test with five methods. Int. J. Clin. Trials, 2021, vol. 8, no. 3, pp. 184--190. DOI: https://doi.org/10.18203/2349-3259.ijct20212840

[20] Stanovov V., Semenkin E. Success rate-based adaptive differential evolution L-SRTDE for CEC 2024 Competition. IEEE CEC, 2024, pp. 1--8. DOI: https://doi.org/10.1109/CEC60901.2024.10611907 ]