Выпускная квалификационная работа: Реализация алгоритма бактериального поиска в среде моделирования NetLogo

1. Государственное бюджетное образовательное учреждение высшего образования Московской области «Университет «Дубна»

Выпускная квалификационная работа
Реализация алгоритма бактериального поиска
в среде моделирования NetLogo
Студент: Костин А.О.
Группа: 4253
Направление: программная инженерия
Руководитель: доц., к.ф.-м.н. Ершов Н.М.
10 июня 2019
Дубна

2. Актуальность и цели работы

Актуальность темы дипломного проекта связана c решением сложных
оптимизационных
задач
с
помощью
децентрализованных
самоорганизующихся систем.
Цель дипломной работы – реализовать двумерную модель
бактериального поиска на основе роевого поведение бактерий и
хемотаксиса.
Для решения поставленной задачи нам потребуется:
• Изучить инструмент NetLogo
• Изучить алгоритм бактериального поиска
• Построить и исследовать модель
2

3.

Постановка задачи
• Выполнить обзор тематики роевого интеллекта и методов роевой
оптимизации
• Формализовать модельную задачу поисковой оптимизации
• Адаптировать алгоритм бактериального поиска к решению
модельной задачи
• Выполнить программную модель задачи и алгоритма ее решения
в среде NetLogo
• Провести численное исследование влияния параметров
алгоритма на эффективность его работы
3

4.

Алгоритм бактериального поиска
Хемотаксис бактерий
Размножение
и отбор
бактерий
Хемотаксис
бактерий
Рассеяние
Алгоритм
бактериального
поиска
Хемотаксисом называют
способ движений бактерий
в микробиологии: если
клетка движется в сторону
(от) питательных веществ,
то её количество обращений
сокращается
(увеличивается).
4

5.

Алгоритм бактериального поиска
Размножение и отбор
Размножение
и отбор
бактерий
Хемотаксис
бактерий
Рассеяние
Алгоритм
бактериального
поиска
Удаляются (отбираются) из
популяции бактерии,
которые имеют низкое
значение функции качества;
заполняются
освободившиеся свободные
места своими копиями
(размножение)
5

6.

Алгоритм бактериального поиска
Рассеяние
Размножение
и отбор
бактерий
Хемотаксис
бактерий
Рассеяние
Алгоритм
бактериального
поиска
В силу малой скорости
движения бактерий (что
не позволяет
передвигаться на большие
расстояния), они
переносятся на большие
расстояния с помощью
животных или воды
6

7.

Поисковая задача
• Необходимо реализовать двумерную модель бактериального
поиска на основе роевого поведение бактерий и хемотаксиса.
• Требуется найти сигнал, который монотонно убывает с
увеличением расстояния до источника сигнала.
• Рассмотреть в модели наличие 4х карт препятствий.
7

8.

Создание карт модели
В реализованной модели было создано 4 карты препятствий:
free
blackhole
bricks
room
8

9.

Настройка цели для бактерий
free
blackhole
bricks
room
9

10.

Реализация бактериального
алгоритма
10

11.

Роевое движение бактерий
11

12.

Численные исследования
Исследования рассеяния
12

13.

Численные исследования
Исследования шума в источнике сигнала
13

14.

Заключение
• Построена двумерная модель в среде моделирования
NetLogo
• Реализован алгоритм бактериального поиска.
• Реализован режим роения бактерий.
• Произведены численные исследования.
Спасибо за внимание!
14