DMS-PSO с локальным поиском

PSO с размерностью кластера 5 и более достигает хороших результатов на простых задачах, было проведено множество исследований на эту тему, если же размерность кластера не большая, то PSO работает лучше на комплексных задачах. PSO использует информацию предыдущей итерации, что в совокупности с небольшим размером кластера дает быструю сходимость к локальному оптимуму. Чтобы этого избежать, необходимо дать возможность частицам в разных кластерах обмениваться информацией между собой. Причем информация должна быть как положительной (информация о более «хорошем» решении), так и отрицательной, чтобы более разнообразить популяцию. Поэтому вводится случайная регруппировка элементов кластеров, благодаря чему PSO имеет динамическую структуру соседства частиц. Каждые итераций работы алгоритма кластеры обмениваются некоторыми частицами и поиск оптимума продолжается с уже новой конфигурацией соседства частиц. называется периодом регруппировки. Таким образом, происходит обмен информацией между кластерами и повышается разнообразие популяции.

Для примера, возьмём 9 частиц, топология соседства — кластер размерности 3. Кластеры формируются случайным образом. Через некоторый период частицы (кластеры) могут сгруппироваться вокруг локальных оптимумов. Затем применятся операция регруппировки и продолжается поиск оптимума. Этот процесс повторяется, пока не будет выполнен критерий останова алгоритма. Изменение структуры соседства даёт возможность небольшим группам частиц охватывать большие области поиска. Операция регруппировки представлена на рис. 2.

Рис. 2. Работа оператора регруппировки

При достижении болшего разнообразия популяции, уменьшается скорость сходимости и благодаря стахостическому поведению алгоритма нет вообще гарантии, что найденное алгоритмом PSO решение будет хотябы локально-оптимальным. По этой причине, в DMS-PSO добавлен локальный поиск: каждые L итераий популяция сортируется согласно пригодсности, выбирает 25% лучших индивидов и эти индивиды улучшаются, использую локальный поиск. L называется периодом локализации. Улучшенные индивиды возвращаются в популяцию, структура топологии при этом переинициализируется.