Speaker
Dr
Nikolay Ershov
(Moscow State University)
Description
Клеточные генетические алгоритмы обладают рядом преимуществ по сравнению с обычными генетическими алгоритмами. Во-первых, за счет локальности взаимодействия между особями популяции удается более долгое время поддерживать разнообразие в популяции, что потенциально ведет к получению более качественного решения. Во-вторых, благодаря регулярности расположения особей в клеточном пространстве и отсутствию глобальных операций клеточные генетические алгоритмы хорошо и масштабируемо распараллеливаются. Однако, как и в обычных генетических алгоритмах, в клеточном варианте остается актуальной проблема попадания алгоритма в локальные экстремумы. В настоящей работе предлагается подход к решению этой проблемы, основанный на введении зависимости работы операторов генетического алгоритма (прежде всего, мутации) от положения особи в клеточном пространстве.
В работе рассматривается решение различных оптимизационных задач с помощью клеточных генетических алгоритмов на двумерной прямоугольной решетке. В алгоритме применяется турнирная схема отбора, равномерное скрещивание и оператор миграции. Идея, лежащая в основе неоднородных клеточных генетических алго¬ритмов, заключается в том, что параметры алгоритма (например, вероятности выполнения операторов отбора, скрещивания, мутации и отбора) делаются зависимыми от положения той или иной особи в клеточном пространстве алгоритма. В работе, в частности, исследуется введение неоднородности в величину мутации (максимальное изменение значения одного гена) и в вероятность отбора, что позволяет поддерживать на высоком уровне разнообразие популяции в течение всего времени работы алгоритма, а не только на начальном его этапе. Рассматривается несколько типов зависимости величины мутации от положения особи (горизонтальный градиент, центральный градиент и т.п.).
В работе рассматривается крупнозернистая параллельная реализация неоднородных клеточных алгоритмов с использованием технологии MPI. Приводятся результаты численного сравнения со стандартным генетическим алгоритмом и со стандартным клеточным генетическим алгоритмом при решении ряда тестовых задач. Показывается, что за счет более медленной сходимости неоднородным клеточным генетическим алгоритмам удается достигать намного более качественных решений. Полученные результаты показывают перспективность предложенного подхода при решении сложных мультимодальных задач оптимизации.
Работа выполнена при финансовой поддержке РФФИ (грант №14-07-00628 А).
Primary author
Dr
Nikolay Ershov
(Moscow State University)
