Гибридный эволюционный алгоритм для решения задач глобальной оптимизации сверхбольшой размерности

Аннотация

При решении прикладных задач различных сфер человеческой деятельности возникает необходимость в поиске наилучшего набора параметров по заданному критерию. Обычно такую задачу формулируют в виде задачи параметрической оптимизации. Рассмотрены задачи оптимизации, представленные моделью типа черного ящика. С ростом размерности таких задач для многих традиционных подходов оптимизации сложно найти удовлетворительное решение даже при значительном увеличении числа вычислений целевой функции. Предложен новый гибридный эволюционный метод координации самонастраивающихся алгоритмов кооперативной коэволюции с локальным поиском COSACC-LS1 для решения задач глобальной вещественной оптимизации сверхбольшой размерности. В основе COSACC-LS1 лежит идея автоматического распределения вычислительных ресурсов между группой самонастраивающихся алгоритмов дифференциальной эволюции, основанных на кооперативной коэволюции, и алгоритмом локального поиска. Оценка эффективности предложенного алгоритма выполнена на 15 эталонных тестовых задачах из набора LSGO CEC 2013. Результаты работы алгоритма на основе COSACC-LS1 сравнивали с современными метаэвристическими алгоритмами, которые разработаны специально для решения задач оптимизации сверхбольшой размерности и являются победителями и призерами соревнований по оптимизации в рамках конференций IEEE CEC. С помощью численных экспериментов продемонстрировано, что по критерию средней точности найденного решения предложенный алгоритм лучше большинства других популярных алгоритмов

Работа выполнена при поддержке Минобрнауки России (грант № 075-15-2022-1121)

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

Вахнин А.В., Сопов Е.А., Рурич М.А. Гибридный эволюционный алгоритм для решения задач глобальной оптимизации сверхбольшой размерности. Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение, 2023, № 2 (143), с. 51--73. DOI: https://doi.org/10.18698/0236-3933-2023-2-51-73

Литература

[1] Карпенко А.П. Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохновленные природой. М., Изд-во МГТУ им. Н.Э. Баумана, 2021.

[2] Del Ser J., Osaba E., Molina D., et al. Bio-inspired computation: where we stand and what’s next. Swarm Evol. Comput., 2019, vol. 48, pp. 220--250. DOI: https://doi.org/10.1016/j.swevo.2019.04.008

[3] Tang K. Summary of results on CEC’08 competition on large-scale global optimization. China, USTC, 2008.

[4] Tang K., Yao X., Suganthan P.N., et al. Benchmark functions for the CEC’2008 special session and competition on large-scale global optimization. China, USTC, 2007.

[5] Tang K., Li X., Suganthan P.N., et al. Benchmark functions for the CEC’2010 special session and competition on large-scale global optimization China, USTC, 2008.

[6] Li X., Tang K., Omidvar M.N., et al. Benchmark functions for the CEC’2013 special session and competition on large-scale global optimization. Australia, RMIT University, 2013.

[7] Molina D., La Torre A. Toolkit for the automatic comparison of optimizers: comparing large-scale global optimizers made easy. Proc. IEEE CEC, 2018. DOI: https://doi.org/10.1109/CEC.2018.8477924

[8] Mahdavi S., Shiri M.E., Rahnamayan S. Metaheuristics in large-scale global continues optimization: a survey. Inf. Sc., 2015, vol. 295, pp. 407--428. DOI: https://doi.org/10.1016/j.ins.2014.10.042

[9] Singh A., Dulal N. A survey on metaheuristics for solving large-scale optimization problems. Int. J. Comput. Appl., 2017, vol. 170, no. 5, pp. 1--7. DOI: https://doi.org/10.5120/ijca2017914839

[10] Omidvar M.N., Li X., Yao X. A review of population-based metaheuristics for large-scale black-box global optimization. Part I. IEEE Trans. Evol. Comput., 2022, vol. 26, no. 5, pp. 802--822. DOI: https://doi.org/10.1109/TEVC.2021.3130838

[11] Omidvar M.N., Li X., Yao X. A review of population-based metaheuristics fo large-scale black-box global optimization. Part II. IEEE Trans. Evol. Comput., 2022, vol. 26, no. 5, pp. 823--843. DOI: https://doi.org/10.1109/TEVC.2021.3130835

[12] Molina D., La Torre A., Herrera F. SHADE with iterative local search for large-scale global optimization. Proc. IEEE CEC, 2018. DOI: https://doi.org/10.1109/CEC.2018.8477755

[13] La Torre A., Muelas S., Pena J.-M. Multiple offspring sampling in large-scale global optimization. Proc. IEEE CEC, 2012. DOI: https://doi.org/10.1109/CEC.2012.6256611

[14] Zhao S.Z., Liang J.J., Suganthan P.N., et al. Dynamic multi-swarm particle swarm optimizer with local search for large-scale global optimization. Proc. IEEE CEC, 2008, pp. 3845--3852. DOI: https://doi.org/10.1109/CEC.2008.4631320

[15] Marcelino C., Almeida P., Pedreira C., et al. Applying C-DEEPSO to solve large-scale global optimization problems. Proc. IEEE CEC, 2018. DOI: https://doi.org/10.1109/CEC.2018.8477854

[16] Lopez E., Puris A., Bello R. VMODE: a hybrid metaheuristic for the solution of large-scale optimization problems. Investig. Operacional, 2015, vol. 36, no. 3, pp. 232--239.

[17] Tseng L.-Y., Chen C. Multiple trajectory search for large-scale global optimization. Proc. IEEE CEC, 2018, pp. 3052--3059. DOI: https://doi.org/10.1109/CEC.2008.4631210

[18] Molina D., Herrera F. Iterative hybridization of DE with local search for the CEC’2015 special session on large-scale global optimization. Proc. IEEE CEC, 2015, pp. 1974--1978. DOI: https://doi.org/10.1109/CEC.2015.7257127

[19] Qin A.K., Huang V.L., Suganthan P.N. Differential evolution algorithm with strategy adaptation for global numerical optimization. IEEE Trans. Evol. Comput., 2009, vol. 13, no. 2, pp. 398--417. DOI: https://doi.org/10.1109/TEVC.2008.927706

[20] Morales J., Nocedal J. Remark on "Algorithm 778: L-BFGS-B: Fortran subroutines for large-scale bound constrained optimization". ACM Trans. Math. Softw., 2011, vol. 38, no. 1, pp. 1--4. DOI: https://doi.org/10.1145/2049662.2049669

[21] La Torre A., Muelas S., Pena J.-M. Large-scale global optimization: experimental results with MOS-based hybrid algorithms. Proc. IEEE CEC, 2013, pp. 2742--2749. DOI: https://doi.org/10.1109/CEC.2013.6557901

[22] Tanabe R., Fukunaga A. Evaluating the performance of SHADE on CEC’2013 benchmark problems. Proc. IEEE CEC, 2013, pp. 1952--1959. DOI: https://doi.org/10.1109/CEC.2013.6557798

[23] Bolufe-Rohler A., Fiol-Gonzalez S., Chen S. A minimum population search hybrid for large-scale global optimization. Proc. IEEE CEC, 2015, pp. 1958--1965. DOI: https://doi.org/10.1109/CEC.2015.7257125

[24] Potter M., De Jong K. A cooperative coevolutionary approach to function optimization. PPSN 1994. Berlin, Springer Verlag, 1994, pp. 245--257. DOI: https://doi.org/10.1007/3-540-58484-6_269

[25] Yang Z., Tang K., Yao X. Large-scale evolutionary optimization using cooperative coevolution. Inf. Sc., 2008, vol. 178, no. 15, pp. 2985--2999. DOI: https://doi.org/10.1016/j.ins.2008.02.017

[26] Yang Z., Tang K., Yao X. Self-adaptive differential evolution with neighborhood search. Proc. IEEE CEC, 2008, pp. 1110--1116. DOI: https://doi.org/10.1109/CEC.2008.4630935

[27] Hadi A., Wagdy A., Jambi K. LSHADE-SPA memetic framework for solving large-scale optimization problems. Complex Intell. Syst., 2019, vol. 5, no. 1, pp. 25--40. DOI: https://doi.org/10.1007/s40747-018-0086-8

[28] Omidvar M.N., Li X., Yao X. Cooperative сoevolution with delta grouping for large-scale non-separable function optimization. Proc. IEEE CEC, 2010, pp. 1--8. DOI: https://doi.org/10.1109/CEC.2010.5585979

[29] Omidvar M.N., Li X., Mei Y., et al. Cooperative coevolution with differential grouping for large-scale optimization. IEEE Trans. Evol. Comput., 2014, vol. 18, no. 3, pp. 378--393. DOI: https://doi.org/10.1109/TEVC.2013.2281543

[30] Omidvar M.N., Yang M., Mei Y., et al. DG2: a faster and more accurate differential grouping for large-scale black-box optimization. IEEE Trans. Evol. Comput., 2017, vol. 21, no. 6, pp. 929--942. DOI: https://doi.org/10.1109/TEVC.2017.2694221

[31] Li L., Fang W., Wang Q., et al. Differential grouping with spectral clustering for large-scale global optimization. IEEE Trans. Evol. Comput., 2019, pp. 334--341. DOI: https://doi.org/10.1109/CEC.2019.8790056

[32] Liu J., Tang K. Scaling up covariance matrix adaptation evolution strategy using cooperative coevolution. IDEAL 2013. Berlin, Springer Verlag, 2013, pp. 350--357. DOI: https://doi.org/10.1007/978-3-642-41278-3_43

[33] Mahdavi S., Rahnamayan S., Shiri M. Cooperative coevolution with sensitivity analysis-based budget assignment strategy for large-scale global optimization. Appl. Intell., 2017, vol. 47, no. 3, pp. 888--913. DOI: https://doi.org/10.1007/s10489-017-0926-z

[34] Ge H., Zhao M., Hou Y., et al. Bi-space interactive cooperative coevolutionary algorithm for large-scale black-box optimization. Appl. Soft Comput., 2020, vol. 97-A,art. 106798. DOI: https://doi.org/10.1016/j.asoc.2020.106798

[35] Liu W., Zhou Y., Li B., et al. Cooperative coevolution with soft grouping for large-scale global optimization. Proc. IEEE CEC, 2019, pp. 318--325. DOI: https://doi.org/10.1109/CEC.2019.8790053

[36] Sun Y., Kirley M., Halgamuge S. A recursive decomposition method for large-scale continuous optimization. IEEE Trans. Evol. Comput., 2018, vol. 22, no. 5, pp. 647--661. DOI: https://doi.org/10.1109/TEVC.2017.2778089

[37] Sun Y., Li X., Ernst A., et al. Decomposition for large-scale optimization problems with overlapping components. Proc. IEEE CEC, 2019, pp. 326--333. DOI: https://doi.org/10.1109/CEC.2019.8790204

[38] Vakhnin A., Sopov E. Investigation of the iCC framework performance for solving constrained LSGO problems. Algorithms, 2020, vol. 13, no. 5, art. 108. DOI: https://doi.org/10.3390/a13050108

[39] Vakhnin A., Sopov E. Investigation of improved cooperative coevolution for large-scale global optimization problems. Algorithms, 2021, vol. 14, no. 5, art. 146. DOI: https://doi.org/10.3390/a14050146

[40] Polakova R., Bujok P. Adaptation of population size in differential evolution algorithm: an experimental comparison. Proc. IWSSIP, 2018. DOI: https://doi.org/10.1109/IWSSIP.2018.8439374