Анализ метода оптимизации на основе моделирования перемещения бактерий Костин Антон, 4 курс ФУПМ МФТИ

Цели и задачи работы Изучить работу алгоритмов, имеющихся в научной литературе Исследовать корректность и выявить недостатки Предложить пути устранения этих недостатков Реализовать и протестировать алгоритм на ряде тестовых функций различной сложности Сделать выводы о пути развития алгоритма и целесообразности его использования

Возникновение идеи алгоритма Колония бактерии E.Coli (кишечной палочки) Использование моделирования колонии E.Coli для оптимизации функции Растригина

Эволюция колонии бактерии в питательной среде Распределение бактерий повторяет распределение питательности в среде

Математическая модель Хемотаксис – это двигательная реакция бактерии в ответ на появление в среде аттрактанта или репеллента Репродукция - размножение бактерий Рассеивание бактерий

Математическая модель 1. Бактерии точечные 2. Количество бактерий в колонии постоянно 3. Смерть происходит у группы бактерий одновременно 4. Вместо умерших рядом с оставшимися возникают новые 5. С некоторой вероятностью колония почти целиком умирает, после чего происходит разброс новых агентов колонии 6. Бактерия перемещается, если чувствует следующее положение более благоприятным 7. Направление последующего движения случайно или псевдослучайно 8. Бактерии способны мутировать (изменение начальных параметров системы)

Хемотакси с Хемотаксис помогает бактерии находить оптимум в локальной области

Классический алгоритм 1. Инициализация стартовых переменных 2. Для каждой бактерии моделируются хемотаксис: кувыркание, перемещение и скольжение Моделируется кувыркание за счёт генерации вектора случайных чисел Рассчитывается новое положение бактерии и значение целевого функционала в нём Выполняется движение бактерией вдоль выбранного направления, если будущее положение лучше предыдущего 3.Воспроизведение: все агенты сортируются в соответствии с полученными значениями целевой функции, после чего худшая половина отбрасывается, а лучшая – дублируется. 4. Исключение и рассеивание: В соответствии с данным подходом каждая бактерия с наперёд заданной вероятностью размещается в случайно выбранной точке пространства поиска. 5. Алгоритм выдаёт положение самой молодой бактерии

Недостатки классического алгоритма Слепой переход бактерии

Недостатки классического алгоритма Верояность пропуска тяготеющего минимума

Недостатки классического алгоритма Высокая вероятность стагнации на объёмном семействе локальных минимумов

Недостатки классического алгоритма Потеря точности на проскакивании

Недостатки классического алгоритма Риск потерять зону тяготения, из-за несовершенства системы отбора

Предложенные модификации Переход только после определения определения целесообразности перехода Усовершенствовать шаг репродукции Добавление PSO-оператора, отклоняющий в сторону глобального минимума Заменить понятие возраста бактерий на более подходящее - величину функционала Добавить уменьшение шага бактерии и критерий уменьшения

Модифицированный алгоритм 1. Инициализация всех переменных и констант. К списку из прошлого алгоритма добавится коэффициент для подсчёта доли 2. Устранение и рассеяние. На первый раз оно должно происходить наверняка. На последующих итерациях с некоторой вероятностью для каждой бактерии. 3. В общем цикле сначала выполняем хемотаксис по там же правилам, потом шаги для репродукции колонии. Здесь же работает счётчик для подсчёта доли хороших шагов. 4. Репродукция происходит с ранжированием по величине целевого функционала в точках с бактериями. Используем случайное направление и долю от диаметра колонии для отпрыгивания новых агентов от оставшихся. 5. Сокращение шага, если доля шагов хороших шагов меньше порогового значения. 6. Возвращаем координаты первой (после ранжирования бактерии)

Параметры полученного алгоритма Время алгоритма составляет, где N - размерность поиска, S - количество бактерий Точность результата составляет порядка, что составляет примерно 1e-11 для N=4 и 1e-60 для N=10 Повышена стабильность работы при запусках на сложных тестовых функциях (примерно в 1,5 раза)

Cферическая функция

Ступенчатая функция

Функция Экли

Функция Розенброка

Функция Растригина

Функция Швефеля

Функция Гривонка

Выводы Модифицированный метод показал высокую стабильность работы на каждом из тестов Полученный прошёл тесты на всех, даже довольно сложных функциях Не все предложенные модификации были внедрены, что оставляет платформу для исследования и совершенствования алгоритма

Спасибо за внимание!