Сибирский федеральный университет

Перевод названия: BINARY GENETIC ALGORITHM USING EDA-BASED PROBLEM DECOMPOSITION FOR LARGE-SCALE GLOBAL OPTIMIZATION

Тип публикации: статья из журнала

Год издания: 2016

Ключевые слова: LSGO, GA-EDA, Binary genetic algorithm, Estimation of Distribution Algorithm, problem decomposition, large-scale global optimization, бинарный генетический алгоритм, алгоритм оценки распределения, декомпозиция задачи оптимизации, глобальная оптимизация высокой размерности

Аннотация: В последние годы существенно увеличилась размерность многих практических задач оптимизации. Подобные задачи глобальной оптимизации высокой размерности (large-scale global optimization, LSGO) имеют несколько сотен или тысяч переменных и являются несепарабельными. Более того, практические задачи оптимизации часто сложны для детального анализа и рассматриваются как модели типа «черный ящик», следовательно, при решении этих задач применимы только методы прямого («слепого») поиска. Наиболее эффективные подходы используют популяционные методы случайного поиска и основаны на идеях кооперативной коэволюции с декомпозицией задачи по переменным. Подобные алгоритмы в основном ориентированы на задачи с вещественными переменными и не могут быть применены к задачам с дискретными и смешанными переменными. Предложен новый подход, основанный на применении сочетания бинарного генетического алгоритма и алгоритма оценки распределения (Еstimation of distribution algorithm, EDA). Бинарный генетический алгоритм решает основную задачу оптимизации, алгоритм EDA используется для оценки статистики, накопленной по результатам прошлых этапов поиска генетическим алгоритмом, и дальнейшей декомпозиции задачи путем фиксации перспективных значений генов в хромосоме. Предложенная декомпозиция задачи на основе EDA-алгоритма обладает свойствами основных методов решения задач оптимизации высокой размерности: метода случайной группировки генов и метода анализа динамики генов. Обсуждаются обычная версия предложенного подхода и островная модель, позволяющая реализовать алгоритм на параллельных компьютерах. Представлены результаты численных экспериментов на множестве тестовых задач, используемых в соревнованиях по глобальной оптимизации высокой размерности в рамках конференций IEEE CEC. Результаты демонстрируют, что предложенный подход обладает эффективностью, сравнимой с другими известными эффективными подходами (победителями и участниками соревнований), и в то же время может применяться к задачам оптимизации с любыми переменными, так как используется бинарное представление решений. In recent years many real-world optimization problems have had to deal with growing dimensionality. Such optimization problems, that are called large-scale global optimization (LSGO) problems, contain many hundreds or thousands of variables and are not separable. Moreover, many real-world problems are usually complex for detailed analysis, thus they are viewed as the black-box optimization problems. Thus, we can use the “blind” search techniques only. The most advanced techniques for LSGO are population-based stochastic search algorithms and are based on cooperative coevolution schemes using the problem decomposition via variables. These algorithms are mainly proposed for the real-valued search space and cannot be applied for problems with discrete or mixed variables. In this paper a novel technique is proposed, that uses a combination of a binary genetic algorithm (GA) and an estimation of distribution algorithm (EDA). The GA is used for solving the main optimization problem, and the EDA is used for collecting statistical data based on the past search experience to provide the problem decomposition by fixing perspective genes in chromosomes. The proposed EDA-based decomposition technique has the benefits of two general LSGO concepts: the random grouping methods and the dynamic learning methods. A standard implementation of the EDA-based decomposition GA and an implementation using the island model for parallel computing are discussed. The results of numerical experiments for benchmark problems from the IEEE CEC competition on the LSGO are presented. The experiments show that the approach demonstrates efficiency comparable to other advanced techniques. At the same time, the proposed approach can be applied for LSGO problems with arbitrary variables as it uses the binary representation of solutions.

Журнал: Вестник Сибирского государственного аэрокосмического университета им. академика М.Ф. Решетнева

Выпуск журнала: Т. 17, № 4

Номера страниц: 899-906

ISSN журнала: 18169724

Место издания: Красноярск

Издатель: Сибирский государственный аэрокосмический университет имени академика М.Ф. Решетнева

• Сопов Е.А. (Сибирский государственный аэрокосмический университет имени академика М. Ф. Решетнева)

• РИНЦ (eLIBRARY.RU)