Роевый интеллект

ГА

ГА берет множество параметров оптимизационной проблемы и кодирует их последовательностями конечной длины в некотором конечном алфавите (в простейшем случае двоичный алфавит «0» и «1»). Предварительно простой ГА случайным образом генерирует начальную популяцию стрингов (хромосом). Затем алгоритм генерирует следующее поколение (популяцию), с помощью трех основных генетических операторов:

1) Оператор репродукции, котоый отбирает лучших особей для дальнейшей эволюции;

2) Оператор скрещивания (кроссинговера), производящий обмен фрагментов особей – потенциальных решений проблемы;

3) Оператор мутации, позволяющий с малой вероятностью случайно вносить изменния в особи, что дает возможность им приобрести новые свойства.

Рис.3. Простой генетический алгоритм

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

Роевый интеллект. В последнее десятилетие при решении задач оптимизации все шире используются новые методы, которые фактически примыкают к эволюционным вычислениям по своей идеологии и основаны на моделировании социального поведения живых организмов. К ним относятся, прежде всего, роевые алгоритмы (РА, PSO -particle swarm optimization[1]), которые, в основном, используются в численной оптимизации; и муравьиные алгоритмы (МА, ACO – ant colony optimization [1]), применяемые, как правило, при решении задач комбинаторной оптимизации (прежде всего на графах).

РА также как и эволюционные используют популяцию особей – потенциальных решений проблемы и метод стохастической оптимизации, который навеян (моделирует) социальным поведением птиц или рыб в стае или насекомых в рое (рис.5). Аналогично эволюционным алгоритмам здесь также начальная популяция потенциальных решений генерируется случайным образом и далее ищет (суб)оптимальное решение проблемы в процессе своего развития. Первоначально в РА предпринята попытка моделировать поведение стаи птиц, которая обладает способностью порой внезапно и синхронно перегруппироваться и изменять направление полета при выполнении некоторой задачи. В отличие от ЭА здесь не используются генетические операторы, в РА особи (называемые частицами- particle) летают в процессе поиска в гиперпространстве поиска решений и учитывают успехи своих соседей. Если одна частица видит хороший (перспективный) путь (в поисках пищи или защиты от хищников), то остальные частицы способны быстро последовать за ней, даже если они находились в другом конце роя. С другой стороны в рое, для сохранения достаточно большого пространства поиска должны быть частицы с долей «сумасшествия» или случайности в своем поведении (движении)

Рис. 5. Стаи птиц, рыб и рой насекомых.

Муравьиные алгоритмы (МА), как и большинство ранее рассмотренных видов эволюционных алгоритмов основаны на использовании популяции потенциальных решений и разработаны для решения задач комбинаторной оптимизации, прежде всего, поиска различных путей на графах[1]. Кооперация между особями – потенциальніми решениями (искусственными муравьями) здесь релизуется на основе моделирования «stigmergy». При этом каждый агент, называемый искусственным муравьем, ищет решение поставленной задачи. Искусственные муравьи последовательно строят решение задачи, передвигаясь по графу, откладывают феромон и при выборе дальнейшего участка пути учитывают концентрацию этого фермента. Чем больше концетрация феромона в последующем участке, тем больше вероятность его выбора.

Дата добавления: 2014-01-05