В моей предыдущей статье описывался алгоритм поведения роя пчёл и применение его для решения задач оптимизации и синтеза. Вооружившись С++ и OpenGL я написал программу, реализующую этот самы алгоритм в двухмерном пространстве, и отображающую роение «пчёл».
В качестве испытательной функции была выбрана следующая функция:
Целевая функция имеет чётко выраженый минимум, куда добрая половина пчёлок слетается уже на третьем шаге.
Немножко видео самого процесса для различных настроек:
притяжение к ПНП(персональная наилучшая позиция) — 0.5. Притяжение к ГНП(глобальная наилучшая позиция) — 0.5. Инерционный вес — 0.5. Пчёл в рое — 60. Для наглядности я поставил задержку в 500мс перед каждым шагом.
Притяжение к ПНП — 0.1. Притяжение к ГНП — 0.7. Инерционный вес — 0.3. Пчёл в рое — 60.
Теперь задача посложнее.
Функция сильно осциллирует.
Притяжение к ПНП — 0.3. Притяжение к ГНП — 0.3. Инерционный вес — 0.3. Пчёл в рое — 60.
И ещё сложнее задача.
Границы расширены.
Притяжение к ПНП — 0.3. Притяжение к ГНП — 0.3. Инерционный вес — 0.3. Пчёл в рое — 60.
Критерий остановки хоть и более явный, если сравнивать с генетическим алгоритмом, но здесь также есть подводные камни. Например в случае со второй функцией, имеющей много локальных минимумов, которые довольно близки по значению к глобальному. На 7секунде видно, что ГНП находилась не в глобальном минимуме и переходит в него только на 12 секунде.
Особым пунктом здесь стоит построение целевой функции. Мы должны грамотно оценить качество объекта оптимизации по заданным критериям. Можно создавать произведения искусства, если задать закон, который бы оценивал красоту.
Вместо расчёта целевой функции также возможен опыт. Например. Нам нужно установить вайфай точку в комнате так, чтобы на диване и на кухне сигнал был максимальным. Мы задаём границы комнаты. После чего алгоритм нам говорит в каких точка нужно поставить и проверить сигнал. Замеряем сигнал на кухне и на диване и на основани этих данных присваиваем каждому положению значение целевой функции. Туда же можно включить и удалённость от стен (ведь не подвесишь же её под люстрой), а ещё удалённость от свича и розетки, фен-шуй,… И через пару часов беготни с ноутбуком и точкой мы будем знать куда стоит её крепить, а куда не нужно.
Пример, конечно, дикий, но зато относится к реальной жизни. Подчеркиваю, что метод оптимизации на выбор целевой функции никак не влияет.
P.S. Производительность метода будет рассмотрена в следующий раз, а также в следующий раз
МРП будет сравнён с методом градиентного спуска. А если есть желающие помочь, то милости прошу, выставляйте своих кандидатов и мы проверим, какой алгоритм лучше и в каком случае.
P.P.S Код программы без комментариев можно посмотреть здесь.
В качестве испытательной функции была выбрана следующая функция:
Целевая функция имеет чётко выраженый минимум, куда добрая половина пчёлок слетается уже на третьем шаге.
Немножко видео самого процесса для различных настроек:
притяжение к ПНП(персональная наилучшая позиция) — 0.5. Притяжение к ГНП(глобальная наилучшая позиция) — 0.5. Инерционный вес — 0.5. Пчёл в рое — 60. Для наглядности я поставил задержку в 500мс перед каждым шагом.
Притяжение к ПНП — 0.1. Притяжение к ГНП — 0.7. Инерционный вес — 0.3. Пчёл в рое — 60.
Теперь задача посложнее.
Функция сильно осциллирует.
Притяжение к ПНП — 0.3. Притяжение к ГНП — 0.3. Инерционный вес — 0.3. Пчёл в рое — 60.
И ещё сложнее задача.
Границы расширены.
Притяжение к ПНП — 0.3. Притяжение к ГНП — 0.3. Инерционный вес — 0.3. Пчёл в рое — 60.
Критерий остановки
Критерий остановки хоть и более явный, если сравнивать с генетическим алгоритмом, но здесь также есть подводные камни. Например в случае со второй функцией, имеющей много локальных минимумов, которые довольно близки по значению к глобальному. На 7секунде видно, что ГНП находилась не в глобальном минимуме и переходит в него только на 12 секунде.
И в заключение о задаче оптимизации
Особым пунктом здесь стоит построение целевой функции. Мы должны грамотно оценить качество объекта оптимизации по заданным критериям. Можно создавать произведения искусства, если задать закон, который бы оценивал красоту.
Вместо расчёта целевой функции также возможен опыт. Например. Нам нужно установить вайфай точку в комнате так, чтобы на диване и на кухне сигнал был максимальным. Мы задаём границы комнаты. После чего алгоритм нам говорит в каких точка нужно поставить и проверить сигнал. Замеряем сигнал на кухне и на диване и на основани этих данных присваиваем каждому положению значение целевой функции. Туда же можно включить и удалённость от стен (ведь не подвесишь же её под люстрой), а ещё удалённость от свича и розетки, фен-шуй,… И через пару часов беготни с ноутбуком и точкой мы будем знать куда стоит её крепить, а куда не нужно.
Пример, конечно, дикий, но зато относится к реальной жизни. Подчеркиваю, что метод оптимизации на выбор целевой функции никак не влияет.
P.S. Производительность метода будет рассмотрена в следующий раз, а также в следующий раз
МРП будет сравнён с методом градиентного спуска. А если есть желающие помочь, то милости прошу, выставляйте своих кандидатов и мы проверим, какой алгоритм лучше и в каком случае.
P.P.S Код программы без комментариев можно посмотреть здесь.
