Бинарный генетический алгоритм с декомпозицией на основе оценки распределения для задач глобальной оптимизации высокой размерности

В последние годы существенно увеличилась размерность многих практических задач оптимизации. Подобные задачи глобальной оптимизации высокой размерности (large-scale global optimization, LSGO) имеют несколько сотен или тысяч переменных и являются несепарабельными. Более того, практические задачи оптимизации часто сложны для детального анализа и рассматриваются как модели типа «черный ящик», следовательно, при решении этих задач применимы только методы прямого («слепого») поиска. Наиболее эффективные подходы используют популяционные методы случайного поиска и основаны на идеях кооперативной коэволюции с декомпозицией задачи по переменным. Подобные алгоритмы в основном ориентированы на задачи с вещественными переменными и не могут быть применены к задачам с дискретными и смешанными переменными. Предложен новый подход, основанный на применении сочетания бинарного генетического алгоритма и алгоритма оценки распределения (Еstimation of distribution algorithm, EDA). Бинарный генетический алгоритм решает основную задачу оптимизации, алгоритм EDA используется для оценки статистики, накопленной по результатам прошлых этапов поиска генетическим алгоритмом, и дальнейшей декомпозиции задачи путем фиксации перспективных значений генов в хромосоме. Предложенная декомпозиция задачи на основе EDA-алгоритма обладает свойствами основных методов решения задач оптимизации высокой размерности: метода случайной группировки генов и метода анализа динамики генов. Обсуждаются обычная версия предложенного подхода и островная модель, позволяющая реализовать алгоритм на параллельных компьютерах. Представлены результаты численных экспериментов на множестве тестовых задач, используемых в соревнованиях по глобальной оптимизации высокой размерности в рамках конференций IEEE CEC. Результаты демонстрируют, что предложенный подход обладает эффективностью, сравнимой с другими известными эффективными подходами (победителями и участниками соревнований), и в то же время может применяться к задачам оптимизации с любыми переменными, так как используется бинарное представление решений.