Роевые и муравьиные алгоритмы

11. Роевые алгоритмы

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

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

(рис 11.1) Стаи птиц, рыб и рой насекомых.

11.1. Основной роевой алгоритм

Итак, РА использует рой частиц, где каждая частица представляет потенциальное решение проблемы. Поведение частицы в гиперпространстве поиска решения все время подстраивается в соответствии со своим опытом и опытом своих соседей. Кроме этого, каждая частица помнит свою лучшую позицию с достигнутым локальным лучшим значением целевой (фитнесс-) функции и знает наилучшую позицию частиц - своих соседей, где достигнут глобальный на текущий момент оптимум. В процессе поиска частицы роя обмениваются информацией о достигнутых лучших результатах и изменяют свои позиции и скорости по определенным правилам на основе имеющейся на текущий момент информации о локальных и глобальных достижениях. При этом глобальный лучший результат известен всем частицам и немедленно корректируется в том случае, когда некоторая частица роя находит лучшую позицию с результатом, превосходящим текущий глобальный оптимум. Каждая частица сохраняет значения координат своей траектории с соответствующими лучшими значениями целевой функции, которые обозначим $$y_i$$, которая отражает когнитивную компоненту. Аналогично значение глобального оптимума, достигнутого частицами роя, будем обозначать $$\hat y_i$$, которое отражает социальную компоненту. Таким образом, каждая частица роя подчиняется достаточно простым правилам поведения (изложенным ниже формально), которые учитывают локальный успех каждой особи и глобальный оптимум всех особей (или некоторого множества соседей) роя.

Каждая $$i$$-я частица характеризуется в момент времени $$t$$ своей позицией $$x_i(t)$$ в гиперпространстве и скоростью движения $$v_i(t)$$. Позиция частицы изменяется в соответствии со следующей формулой:

$$x_i(t+1)=x_i(t)+v_i(t+1),\mbox{где }x_i(0)\sim(x_{\min},x_{\max})$$

Вектор скорости $$v_i(t+1)$$ управляет процессом поиска решения и его компоненты определяются с учетом когнитивной и социальной составляющей следующим образом:

$$v_{ij}(t+1)=v_{ij}(t)+c_1r_{1j}(t)[y_{ij}(t)-x_{ij}(t)]+c_2r_{2j}(t)[\hat y_{j}(t)-x_{ij}(t)]$$

Здесь $$v_{ij)(t)$$- $$j$$-ая компонента скорости $$(j=1,\dots,n_x)$$ $$i$$-ой частицы в момент времени $$t$$, $$x_{ij}(t)$$- $$j$$-я координата позиции $$i$$-й частицы, $$c_1$$ и $$c_2$$ – положительные коэффициенты ускорения (часто полагаемые 2), регулирующие вклад когнитивной и социальной компонент, $$r_{1j}(t),r_{2j}(t)\sim(0,1)$$- случайные числа из диапазона [0,1], которые генерируются в соответствии с нормальным распределением и вносят элемент случайности в процесс поиска. Кроме этого $$y_{ij}(t)$$- персональная лучшая позиция по $$j$$-й координате $$i$$-ой частицы, а $$\hat y_{j}(t)$$–лучшая глобальная позиция роя, где целевая функция имеет экстремальное значение.

При решении задач минимизации персональная лучшая позиция в следующий момент времени $$(t+1)$$ определяется следующим образом:

$$y_i(t+1)=\begin{cases}y_i(t)if\ f(x_i(t+1))\ge f(y_i(t))\\x_i(t+1)if\ f(x_i(t+1))< f(y_i(t))\end{cases}$$

где $$f:R^{n_{\infty}}\to R$$- фитнесс-функция. Как и в эволюционных алгоритмах фитнесс-функция измеряет близость текущего решения к оптимуму.

Глобальная лучшая позиция $$\hat y_j(t)$$ в момент $$t$$ определяется в соответствии с

$$\hat y_j(t)\in\{y_0(t),\dots,y_{n_s}(t)\}|f(\hat y_j(t))=\min\{f(y_0(t)),\dots,f(y_{n_s}(t))\},$$

где $$n_s$$ – общее число частиц в рое.

В процессе поиска решения описанные действия выполняются для каждой частицы роя. Укрупненный основной роевой алгоритм представлен ниже.

Рассмотрим влияние различных составляющих при вычислении скорости частицы в соответствии с (11.2). Первое слагаемое в (11.2) $$v_i(t)$$ сохраняет предыдущее направление скорости $$i$$-й частицы и может рассматриваться как момент, который препятствует резкому изменению направления скорости и выступает в роли инерционной компоненты. Когнитивная компонента $$c_1r_1(y_i-x_i)$$ определяет характеристики частицы относительно ее предистории, которая хранит лучшую позицию данной частицы. Эффект этого слагаемого в том, что оно пытается вернуть частицу назад в лучшую достигнутую позицию. Третье слагаемое $$c_2r_2(\hat y-x_i)$$ определяет социальную компоненту, которая характеризует частицу относительно своих соседей. Эффект социальной компоненты в том, что она пытается направить каждую частицу в сторону достигнутого роем (или его некоторым ближайшим окружением) глобального оптимума.

Графически это наглядно иллюстрируется для двумерного случая, как это показано на рис.11.2.

(рис 11.2) Геометрическая иллюстрация изменения позиции и скорости частицы.

Представленный основной роевой алгоритм часто называют глобальным РА (Global Best PSO), поскольку здесь при коррекции скорости частицы используется информация о положении достигнутого глобального оптимума, которая определяется на основании информации, передаваемой всеми частицами роя. В противоположность этому подходу иногда используется локальный РА, где при коррекции скорости частицы используется информация, передаваемая только в каком-то смысле ближайшими соседними частицами роя.

11.2.Локальный роевой алгоритм

Локальный РА (Local Best PSO) использует для коррекции вектора скорости частицы только локальный оптимум, который определяется на множестве соседних (ближайших в некотором смысле) частиц. То есть считается, что данной частице может передавать полезную информацию только ее ближайшее окружение. При этом отношение соседства задается некоторой "социальной" сетевой структурой, которая образует перекрывающееся множества соседних частиц, которые могут влиять друг на друга. Соседние частицы обмениваются между собой информацией о достигнутых лучших результатах и поэтому стремятся двигаться в сторону локального в данной окрестности оптимума. Характеристики роевого локального алгоритма сильно зависят от структуры используемой "социальной сети". Поток информации через "социальную сеть" зависит от: 1) степени связности узлов сети, 2) числа кластеров, 3) среднего расстояния между узлами сети. В сильно связной социальной сети большинство частиц могут сообщаться друг с другом, что способствует быстрому распространению информации о достигнутых оптимумах и вследствие этого высокой скорости сходимости процесса поиска решения в отличие от мало связных сетей. Однако это часто достигается ценой преждевременной сходимости к локальным экстремумам. С другой стороны, для мало связных сетей с большим числом кластеров возможна ситуация, когда пространство поиска покрывается неудовлетворительно, вследствие чего трудно получить глобальное оптимальное решение. Каждый кластер содержит сильно связанные особи и покрывает только часть пространства поиска. Сетевая структура обычно содержит несколько кластеров, которые слабо связаны между собой. Следовательно, исследуется информация только в ограниченной части пространства поиска. В РА используются различные социальные структуры, типовые сетевые структуры которых представлены на рис.11.3.

На рис.11.3a) представлена структура "звезда", где все частицы связаны друг с другом (образуют полный граф) и могут соответственно обмениваться информацией. В этом случае каждая частица стремится сместиться в сторону глобальной лучшей позиции, которую нашел рой. Очевидно, что основной РА, рассмотренный в предыдущем разделе, использует по умолчанию фактически структуру "звезда" на всем рое.

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

(рис 11.3) Типовые социальные сетевые структуры.

На следующем рис.11.3 б) приведена сетевая структура "кольцо", где каждая частица общается со своими $$n_N$$ ближайшими соседями. При $$n_N=2$$ каждая частица связана только с двумя ближайшими соседями по кольцу, как это показано на рисунке. В этом случае каждая частица пытается сместиться в сторону лучшего соседа. Следует отметить, что множества соседних окружений перекрываются и вследствие этого возможен обмен информацией не только между ближайшими соседями. Поэтому данная структура позволяет находить и глобальный экстремум, но с меньшей скоростью. Данная структура лучше зарекомендовала себя при решении мульти-модальных задач (со многими экстремумами).

В сетевой структуре "колесо", показанной на рис.11.3 в), особи фактически изолированы друг от друга. Только одна частица выступает в качестве "фокальной точки", через которую идет обмен информации. В этом случае "фокальная частица" сравнивает характеристики всех соседних частиц и стремится в сторону лучшего соседа. Если новая позиция "фокальной частицы" имеет лучшие характеристики, то она сообщает это всем своим соседям. Данная сетевая структура замедляет распространение хороших решений через рой.

Социальная структура "пирамида" образует трехмерный каркас, как это показано на рис. 11.3 г).

Далее на рис.11.3 д) представлена четырех-кластерная социальная структура, в которой четыре кластера (клики) связаны друг с другом двумя соединениями.

Наконец, на рис.11.3 е) приведена социальная структура, где частицы объединены в решетку, которая часто называется социальной сетевой структурой фон Неймана. Данный тип согласно проведенным экспериментальным исследованиям показывает лучшие результаты при решении многих задач.

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

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

$$v_{ij}(t+1)=v_{ij}(t)+c_1r_{1j}(t)[y_{ij}(t)-x_{ij}(t)]+c_2r_{2j}(t)[\hat y_{j}(t)-x_{ij}(t)]$$

где $$\hat y_{ij}$$- лучшая позиция, которая найдена по координате $$j$$ соседями частицы $$i$$. При этом локальная лучшая позиция $$\hat y_{ij}$$ определяется как лучшая позиция в окружении $$N_i$$ в соответствии с выражением

$$\hat y_i(t+1)\in\{N_i|f(\hat y_i(t+1))=\min\{f(x)\},\forall x\in N_i\}$$

где

$$N_i=\{y_{i-nN_i}(t),y_{i-nN_i+1}(t),\dots,y_{i-1}(t),y_{i}(t),y_{i+1}(t),\dots,y_{i+nN_i}(t)\}$$

при числе соседей $$nN_j$$. Здесь локальная лучшая позиция относится к лучшей позиции соседнего окружения.

Следует отметить, что, в основном, РА частицы в окружении не связаны друг с другом. Выбор соседей выполняется на основе индексов частицы[2].Однако, кроме этого, разработаны методы, где соседнее окружение формируется на основе пространственной близости.

Существуют, по крайней мере, две причины, по которым отношение соседства по индексам предпочтительнее:

экономия в вычислительных ресурсах, так как не требуется пространственное упорядочение частиц, где необходимы вычисления евклидовых расстояний между частицами со сложностью $$O(n_s^2)$$;

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

Ниже представлен псевдокод локального РА.

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

Но существуют, по крайней мере, два основных различия между этими двумя подходами относительно их характеристик (свойств) сходимости:

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

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

11.3. Основные аспекты роевых алгоритмов

Далее рассмотрим некоторые аспекты представленных выше роевых алгоритмов А11.1 и А11.2, к которым относятся вопросы инициализации, условий останова, вычисления фитнесс-функций и т.п. Как было показано ранее, процесс поиска решения в РА согласно А 11.1 и А 11.2 является итеративным, который продолжается пока не выполнено условие останова. Одна итерация содержит все шаги основного цикла repeat …until, включая определение персональных и глобальных лучших позиций и коррекцию скорости каждой частицы. В каждой итерации производится оценка значений фитнесс-функций частиц. Оценка качества потенциального решения выполняется на основе вычисления значения фитнесс-функции, которая характеризует данную задачу оптимизации. В основном РА выполняется $$n_s$$ вычислений фитнесс-функции за итерацию, где $$n_s$$- число частиц в рое.

На первом этапе РА производится инициализация роя и управляющих параметров алгоритма. При этом определяются начальные значения скоростей, позиций и персональных лучших позиций частиц, коэффициенты ускорения $$c_1$$, $$c_2$$ и т.п. Для локальных РА необходимо также определить отношение соседства и размер окрестности ближайших соседей.

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

Предположим, что оптимум расположен внутри области, определяемой двумя векторами $$x_{\min}$$, $$x_{\max}$$, которые представляют минимальные и максимальные значения по каждой координате. Тогда эффективным методом инициализации начальной позиции частиц является:

$$x(0)=x_{\min,j}+r_j(x_{\max,j}-x_{\min,j}),\forall j=1,\dots,n_x,\ \forall i=1,\dots,n_x$$

где $$r_j\sim U(0,1)$$.

Начальные скорости частиц при этом можно положить нулевыми $$v_i(0)=0$$. В другом варианте начальные скорости можно инициализировать случайными значениями из некоторого диапазона, но делать это необходимо осторожно. Случайная инициализация позиций частиц уже определяет начальное движение в случайных направлениях. Если, однако, выполняется случайная инициализация скоростей, то их значения не должны быть слишком большими, чтобы частицы не вышли из "зоны интереса", что может существенно ухудшить сходимость.

Персональная лучшая позиция для каждой частицы определяется позицией частицы в момент $$t=0$$, то есть $$y_i(0)=x_i(0)$$. Различные схемы инициализации позиций частиц исследованы для покрытия пространства поиска [3]: на основе последовательностей Соболя, Faure, нелинейного симплекс-метода и т.д. При решении реальных задач важно, прежде всего, чтобы частицы равномерно покрывали пространство поиска.

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

критерий не должен вызывать преждевременной сходимости РА в локальных оптимумах;

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

В настоящее время предложен ряд критериев останова, основными из которых являются следующие.

Останов по максимальному числу итераций (при превышении заданного порога). Очевидно, что в случае малого порога числа итераций процесс может остановиться до того, как будет найдено хорошее решение. Это критерий обычно используется совместно с критерием сходимости. Данный критерий полезен, когда необходимо за ограниченное заданное время найти лучшее решение.

Останов по найденному приемлемому решению. Предположим, что $$x^*$$ представляет оптимум для целевой функции $$f$$. Тогда критерий окончания можно сформулировать в терминах близости найденного лучшего решения $$x$$ к оптимуму $$f(x_i)\le|f(x^*)-\varepsilon|$$, то есть при достижении достаточно малой ошибки $$\varepsilon$$. Значение порога ошибки $$\varepsilon$$ необходимо выбирать осторожно. Если значение $$\varepsilon$$ слишком велико, то очевидно процесс поиска может остановиться, если найдено не очень хорошее решение. С другой стороны, если значение слишком мало, то процесс может вовсе не сойтись. Это особенно характерно для основного (глобального) РА. Кроме этого,данный критерий предполагает априорное знание оптимального значения, которое не всегда известно, кроме случаев минимизации ошибки (например, в процессе обучения).

Останов по отсутствию улучшения решения за заданное число итераций. Есть различные способы измерения улучшения получаемых решений. Например, среднее изменение позиции частиц мало, то можно предположить, что процесс поиска сошелся. С другой стороны, если среднее значение скорости частицы за некоторое число итераций примерно равно нулю, то возможны только незначительные изменения позиции частиц и процесс поиска можно остановить. К сожалению, данный критерий требует ввода двух параметров: 1) диапазона изменения итераций, 2) пороговое значение наблюдаемых величин.

Останов при стремлении нормализованного радиуса роя к нулю. Определим нормализованный радиус роя следующим образом:

$$R_{norm}=\frac{R_{\max}}{diameter(s)},$$

где diameter(S) - диаметр начального роя и максимальный радиус $$R_{\max}$$ определяется следующим образом

$$R_{\max}=\|x_m-\hat y\|,\quad m=1,\dots,n_s\ \mbox{c}\\\|x_m-\hat y\|\ge\|x_i-\hat y\|,\quad\forall i=1,\dots,n_s.$$

Можно считать, что алгоритм сошелся, если $$R_{norm}<\varepsilon$$. Если $$\varepsilon$$ слишком велико, то процесс поиска может закончиться раньше, чем будет найдено хорошее решение. С другой стороны при малом значении $$\varepsilon$$ может потребоваться слишком большое число итераций для формирования компактного роя.

Останов по малому значению наклона (крутизны) целевой функции.Рассмотренные критерии учитывают только относительное расположение частиц в пространстве поиска и не принимают во внимание информацию о крутизне целевой функции. Для учета изменений целевой функции часто используют следующее отношение:

$$f'(t)=\frac{f(\hat y(t))-f(\hat y(t-1))}{f(\hat y(t))}.$$

Если $$f'(t)<\varepsilon$$ для определенного числа последовательных итераций, то можно считать, что рой сошелся. Этот критерий сходимости, по мнению многих специалистов, превосходит приведенные ранее, так как он учитывает динамические характеристики роя. Однако использование крутизны целевой функции в качестве критерия останова может привести к преждевременной сходимости в локальном экстремуме. Поэтому целесообразно использовать данный критерий в сочетании с приведенным ранее критерием нормализованного радиуса роя.

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

11.4. Основные параметры роевых алгоритмов

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

Размер роя, число частиц $$n_s$$, играет большую роль: чем больше частиц, тем больше разнообразие потенциальных решений (при хорошей схеме инициализации, обеспечивающей однородное распределение частиц). Большое число частиц позволяет покрыть большую часть пространства поиска за итерацию. С другой стороны большое число частиц повышает вычислительную сложность итерации и при этом РА может выродиться в случайный параллельный поиск. Хотя бывают случаи, что большее число частиц ведет к уменьшению числа итераций при поиске хороших решений. Экспериментально показано, что РА способны находить оптимальное решение с малым размером роя от 10 до 30 частиц [3]. В общем случае оптимальный размер роя зависит от решаемой задачи и определяется экспериментально.

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

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

Коэффициенты ускорения $$c_1$$ и $$c_2$$ вместе со случайными векторами $$r_1$$ и $$r_2$$ определяют вклад когнитивной и социальной компонент в результирующую скорость частицы. При $$c_1=c_2=0$$ частицы летают с прежней скоростью пока не достигнут (по инерции) границы пространства поиска. Если $$c_1>0$$ и $$c_2=0$$, частица не зависит от остальных особей. Каждая частица находит свою лучшую позицию в своем окружении путем замены лучшей позиции в том случае, если текущая позиция лучше. В случае $$c_2>0$$ и $$c_1=;0$$, весь рой стремится к одной точке $$\hat y$$. Эксперименты показывают, что эффективность поиска увеличивается при балансе этих коэффициентов, т.е. при $$c_1\approx c_2$$. Если $$c_1=c_2$$, то частицы стремятся к средней точке между $$y_i$$ и $$\hat y$$. Часто при решении задач полагают $$c_1=c_2$$, но в общем случае отношение этих коэффициентов зависит от решаемой задачи. При $$c_1\gg c_2$$ каждая частица больше стремится к своей лучшей позиции, что в результате ведет к чрезмерному блужданию частиц. Наоборот $$c_2\gg c_1$$ определяет большее стремление частиц к глобальному экстремуму. Обычно значения $$c_1,c_2$$ в процессе поиска постоянны, но иногда используются адаптивные схемы, когда величины $$c_1,c_2$$ изменяются [3].

11.5. Основные модификации РА

В настоящее время РА применяется при решении многих проблем, включая стандартные задачи численной и комбинаторной оптимизации, обучение нейронных сетей и т.д. и показал неплохие результаты. Но в некоторых случаях изложенная базовая версия РА имеет тенденцию к преждевременной сходимости и не находит оптимальные решения. Поэтому разработан ряд модификаций РА, основные из которых включают введение веса инерции, ограничение и сужение диапазона скорости частиц, различные способы определения персональных и глобальных позиций и различные модели скорости, которые будут рассмотрены ниже. При этом важнейшим аспектом, который определяет эффективность и точность алгоритма оптимизации является соотношение (exploration-exploitation) исследование-локализация пространства поиска. Исследование (exploration) характеризует способность алгоритма исследовать различные области пространства поиска (расширять его) для того, чтобы локализовать хорошее решение. С другой стороны локализация (exploitation – разработка, эксплуатация) определяет способность алгоритма концентрировать поиск в перспективной области для того, чтобы улучшить решение. Хороший алгоритм оптимизации должен поддерживать баланс между этими двумя противоположными свойствами.

Ограничение скорости является одним из основных методов повышения эффективности РА, где свойства исследования-локализации пространства поиска определяются уравнением изменения скорости (11.2) (или 11.5), которое содержит три слагаемых, регулирующих величину и направление изменения скорости частицы. Уже в ранних работах было обнаружено, что часто скорость частиц резко увеличивается, особенно это характерно для частиц, далеких от лучших локальных и глобальных позиций. В результате частицы получают большие положительные приращения и покидают границы "зоны интереса" в пространстве поиска (частицы расходятся). Поэтому желательно ограничить изменение скоростей частиц в некотором диапазоне. Если скорость частицы превышает некоторый порог, то она искусственно устанавливается в некоторое максимально допустимое значение. Пусть $$V_{\max,j}$$ обозначает максимально допустимую скорость в $$j$$-й компоненте. Тогда скорость частицы регулируется (перед изменением позиции согласно уравнению (11.1)) следующим образом

$$v_{ij}(t+1)=\begin{cases}v'_{ij}(t+1)\mbox{если $v'_{ij}(t+1)<$}V_{\max,j}\\V_{\max,j}\mbox{если $v'_{ij}(t+1)\ge$}V_{\max,j}\end{cases},$$

где $$V'_{i,j}$$ вычисляется в соответствии с (11.2) (или (11.5)). При этом значение $$V_{\max,j}$$ имеет большое значение, поскольку оно определяет уровень разбиения пространства поиска путем ограничения увеличения скорости. Большое значение $$V_{\max,j}$$ способствует глобальному исследованию пространства поиска, в то время как малое – локализации хорошего решения. Кроме этого, малые значения увеличивают число итераций при поиске решения. Более того, при этом рой может попасть в ловушку локального экстремума. С другой стороны большие значения $$V_{\max,j}$$ увеличивают риск пропуска перспективной области. Частицы могут "перепрыгнуть" через хорошие решения и продолжать поиск в неперспективной области пространства поиска. Часто $$V_{\max,j}$$ полагают

$$V_{\max,j}=\delta(x_{\max,j}-x_{\min,j}),$$

где $$x_{\max,j}$$ и $$x_{\min,j}$$ соответственно максимальное и минимальное значение $$j$$-ой компоненты, а $$\delta\in(0,1]$$. Значение коэффициента $$\delta$$ зависит от проблемной области и определяется экспериментально. Следует отметить следующие важные аспекты данной модификации РА:

Удерживание скорости в некотором диапазоне не ограничивает явно позицию частицы и непосредственно влияет только на размер шага перемещения, который определяется скоростью.

Максимальное значение скорости ассоциируется с каждой компонентой $$j$$ и пропорционально ее области определения. Для упрощения предположим, что по компонентам (измерениям) значения скорости ограничены одной константой $$V_{\max}$$. Тогда, в случае $$x_{\max,j}-x_{\min,j}\ll V_{\max}$$ в измерении $$j$$-ой частицы могут значительно отклониться от оптимума в компоненте $$j$$.

Данный подход имеет преимущество в том, что сдерживает резкое увеличение скорости, но пользователь должен следить за этим. Во-первых, ограничение скорости изменяет не только шаг изменения, но и направление движения частицы. Этот эффект показан на рис.11.4 для двумерного случая.

(рис 11.4) Эффект ограничения скорости

На этом рисунке $$x_i(t+1)$$ обозначает позицию $$i$$-ой частицы без ограничения скорости, а $$x'_i(t+1)$$– ее позицию в результате ограничения скорости по второй компоненте $$x_2$$. Заметим, что при этом направление поиска и величина шага изменились.

Кроме этого, существует другая проблема в случае равенства всех скоростей максимальных значений по всем компонентам. Если не предусмотрены измерения для предотвращения такой ситуации, то частицы остаются на границе гиперкуба, определяемого как $$[x_i(t)-V_{\max},x_i(t)+V_{\max}]$$. Возможно, что частицы могут задержаться в оптимуме, но в общем случае рою трудно искать решение в этой локальной области. Эта проблема может быть решена по-разному - например, путем ввода веса инерции или временным уменьшением значения $$V_{\max,j}$$[3].

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

$$v_{ij}(t+1)=wv_{ij}(t)+c_1r_{1j}(t)|y_{ij}(t)-x_{ij}(t)|+c_2r_{2j}(t)|\hat y_{j}(t)-x_{ij}(t)|$$

для глобального РА. Аналогично это делается и для локального РА.

Значение коэффициента $$w$$ играет большую роль и определяет компромисс между исследованием и локализацией в пространстве поиска. При $$w\ge 1$$ скорость частицы увеличивается (с учетом ранее рассмотренного ограничения) и рой "расходится". Частицам тяжело изменить направление движения для того, чтобы вернуться к перспективной области поиска решения. При $$w< 1$$ частицы замедляются до тех пор, пока их скорость не станет равной нулю. Таким образом, большие значения $$w$$ способствуют исследованию пространства поиска, а малые - локализации решения. Однако слишком малые значения $$w$$ лишают рой способности исследовать пространство поиска. Чем меньше $$w$$, тем больше влияние когнитивной и социальной компоненты. Как и остальные параметры, оптимальное значение $$w$$ проблемно-ориентировано (зависит от задачи). В первых реализациях этого подхода использовались постоянные значения $$w$$. Далее стали использовать динамические $$w$$, где старт производится с большим значением $$w$$, которое далее постепенно уменьшается. Выбор значения $$w$$ можно совместить с определением значений коэффициентов $$c_1$$ и $$c_2$$. Например, показано [3], что $$w>\frac{1}{2}(c_1+c_2)-1$$ гарантирует сходимость траектории частицы. Если это условие не выполняется, то возможно расхождение или зацикливание движения частиц.

При динамическом изменении веса инерции обычно применяются следующие методы:

Случайное регулирование, где различные веса инерции случайно генерируются на каждой итерации. В некоторых случаях используется Гауссово распределение, где $$w\sim N(0.72,\sigma)$$ и $$\sigma$$ достаточно мало, чтобы $$w$$ не превышало 1. Иногда полагают $$w=(c_1r_1+c_2r_2)$$ без случайного изменения вклада когнитивной и социальной компонент [3].

Линейное уменьшение веса инерции, например в соответствии с

$$w(t)=(w(0)-w(n_t))\frac{(n_t-1}{n_t}+w(n_t),$$

где $$n_t$$- максимальное число итераций выполнения алгоритма, $$w(0)$$ – начальный вес, $$w(n_t)$$ – конечный вес, $$w(t)$$ – текущий вес на итерации $$t$$. Заметим, что $$w(0)>w(n_t)$$.

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

$$w(t+1)=\frac{(w(t)-0.4)(n_t-t)}{n_t+0.4}\quad\mbox{с } w(0)=0.9;\\w(t+1)=\alpha w(t')\quad\mbox{с } w(0)=0.975$$

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

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

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

$$v_{ij}=(t+1)=\chi[v_{ij}(t)+\phi_1(y_{ij}(t)-x_{ij}(t))+\phi_2(\hat y_j(t)-x_{ij}(t))],\\\mbox{где}\ \chi=\frac{2k}{|2-\phi-\sqrt{\phi(\phi-4)}|}\ \mbox{c }\phi=\phi_1+\phi_2,\phi_1=c_1r_1\ and\ \phi_2=c_2r_2.$$

Этот подход является альтернативой методу ограничения скорости и при $$\phi\ge 4\ and\ k\in[0,1]$$ гарантирована сходимость роя [3].

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

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

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

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

Случайная генерация начальной популяции.

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

Репродукция популяции на основе полученных значений фитнесс-функции.

Конец при выполнении условий останова. В противном случае переход на 2.

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

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

управление энергетическими системами;

решение NP-трудных комбинаторных проблем;

задачи календарного планирования;

оптимизация в мобильной связи;

оптимизация процессов пакетной обработки;

оптимизация многокритериальных задач;

обработка изображений;

распознавание образов;

кластеризация данных;

биоинформатика;

проектирование сложных технических систем и т.д.

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

Как представляется потенциальное решение в РА?

Как производится коррекция скорости частицы?

Что такое когнитивная составляющая?

Что такое социальная составляющая?

Опишите глобальный РА.

Чем отличаются глобальный и локальный РА?

Какие используются социальные структуры?

Опишите локальный РА.

Определите персональную лучшую позицию.

Определите глобальную лучшую позицию.

Приведите основные аспекты РА.

Приведите основные условия останова РА.

Как выполняется инициализация в РА?

Приведите основные параметры РА.

Какие существуют модификации РА?

В чем суть метода ограничения скорости в РА?

Что дает введение веса инерции в РА?

Какиеспособы существуют для динамического изменения веса инерции?

Что общего между РА, ЭВ и ГА?

Какие различия имеют место между РА,ГА и ЭВ?

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

изложены основы роевого интеллекта, который основан на моделировании поведения простейших социальных структур;

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

представлен глобальный роевой алгоритм с основными формулами взаимодействия частиц;

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

изложен локальный роевой алгоритм, где для данной частицы коррекция скорости и положения выполняется с учетом только ее локального окружения;

описаны различные топологии социальных структур для локальных роевых алгоритмов;

приведены основные параметры и аспекты роевых алгоритмов, которые влияют на их эффективность;

изложены различные модификации роевых алгоритмов;

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