Роевые и муравьиные алгоритмы (стр. 5 )

Случайное регулирование, где различные веса инерции случайно генерируются на каждой итерации. В некоторых случаях используется Гауссово распределение, где и достаточно мало, чтобы не превышало 1. Иногда полагают без случайного изменения вклада когнитивной и социальной компонент [3]. Линейное уменьшение веса инерции, например в соответствии с

где - максимальное число итераций выполнения алгоритма, – начальный вес, – конечный вес, – текущий вес на итерации . Заметим, что .

Нелинейное уменьшение веса инерции, которое часто позволяет сократить этап исследования пространства поиска и может быть выполнено по-разному:

и другими методами [3].

Нечеткие (fuzzy) веса инерции на основе нечетких множеств и правил регулирования [3].

Использование коэффициента сжатия (constriction coefficient) является модификацией РА, которая похожа на использование коэффициента инерции. Здесь уравнение изменения скорости частицы выполняется следующим образом:

Этот подход является альтернативой методу ограничения скорости и при гарантирована сходимость роя [3].

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

11.6. Сравнение роевых и генетических алгоритмов

Сила генетических алгоритмов, прежде всего, в параллельной природе поиска решений. В ГА реализована псевдослучайная форма поиска решения, которая сохраняет кратные решения, уничтожает неперспективные и дает приемлемые решения. Генетические операторы позволяют даже слабым решениям оставаться в числе потенциальных решений и генерировать из них приемлемые. Использование генетических операторов обеспечивает успех поиска хорошего решения. Все ГА используют некоторую форму рекомбинации, позволяющую порождать новые решения, которые сохраняют хорошие качества родителей и с большой вероятностью показывают хорошие характеристики. Кроссинговер является основным оператором ГА, в то время как мутация используется намного реже.

Большинство эволюционных методов используют следующую схему:

Случайная генерация начальной популяции. Вычисление значения фитнесс-функции для каждой особи, определяющего ее близость к оптимуму. Репродукция популяции на основе полученных значений фитнесс-функции. Конец при выполнении условий останова. В противном случае переход на 2.

Из этой схемы видно, что РА имеет много общего с ГА. Оба алгоритма стартуют из случайно генерированной популяции и используют оценку значений фитнесс-функции. В обоих алгоритмах эволюция популяции и соответственно поиск решения основаны на случайных методах. Оба не гарантируют успех в поиске решения. Однако РА не имеет генетических операторов, подобных кроссинговеру и мутации. Здесь потенциальные решения-частицы взаимодействуют и изменяют свои скорости. Частицы имеют память, что очень важно для алгоритма. Механизмы передачи информации в РА и ГА совершенно различны. В ГА хромосомы обмениваются информацией друг с другом. Поэтому вся популяция движется как единая группа в область оптимума. В РА только глобальная (локальная) лучшая позиция передается другим частицам. Это единственный механизм передачи информации. В процессе эволюции ведется поиск лучшего решения. По сравнению с ГА все частицы в большинстве случаев стремятся к лучшему решению быстрее. РА имеет много общего с эволюционными вычислениями в общем и с ГА в частности. Все три метода стартуют из случайно генерированной начальной популяции и используют оценку значений фитнесс-функции. Преимущество РА также в том, что они, как правило, проще в реализации и имеют меньше параметров управления.

В настоящее время РА применяются при решении задач численной и комбинаторной оптимизации (существует дискретный вариант РА), обучении искусственных нейронных сетей, построении нечетких контроллеров и т. д. в различных областях науки техники:

управление энергетическими системами; решение NP-трудных комбинаторных проблем; задачи календарного планирования; оптимизация в мобильной связи; оптимизация процессов пакетной обработки; оптимизация многокритериальных задач; обработка изображений; распознавание образов; кластеризация данных; биоинформатика; проектирование сложных технических систем и т. д.

Контрольные вопросы

Как представляется потенциальное решение в РА? Как производится коррекция скорости частицы? Что такое когнитивная составляющая? Что такое социальная составляющая? Опишите глобальный РА. Чем отличаются глобальный и локальный РА? Какие используются социальные структуры? Опишите локальный РА. Определите персональную лучшую позицию. Определите глобальную лучшую позицию. Приведите основные аспекты РА. Приведите основные условия останова РА. Как выполняется инициализация в РА? Приведите основные параметры РА. Какие существуют модификации РА? В чем суть метода ограничения скорости в РА? Что дает введение веса инерции в РА? Какиеспособы существуют для динамического изменения веса инерции? Что общего между РА, ЭВ и ГА? Какие различия имеют место между РА, ГА и ЭВ?

Краткие итоги:

изложены основы роевого интеллекта, который основан на моделировании поведения простейших социальных структур; описана основная модель, где множество потенциальных решений представляется в виде роя взаимодействующих частиц; представлен глобальный роевой алгоритм с основными формулами взаимодействия частиц; изложен способ коррекции положения и скоростей частиц (потенциальных решений) в зависимости от достигнутых ими лучших глобальных и персональных позиций; изложен локальный роевой алгоритм, где для данной частицы коррекция скорости и положения выполняется с учетом только ее локального окружения; описаны различные топологии социальных структур для локальных роевых алгоритмов; приведены основные параметры и аспекты роевых алгоритмов, которые влияют на их эффективность; изложены различные модификации роевых алгоритмов; выполнено сравнение генетических и роевых алгоритмов.