A comprehensively improved particle swarm optimization algotithm to guarantee particle activity.pdf Введение Алгоритм оптимизации множества частиц (PSO) [1] возник как результат моделирования группового кормового поведения птиц и был типичным параллельным алгоритмом глобальной оптимизации. Поскольку алгоритм PSO может быть использован для крупномасштабных, многопиковых, нелинейных и недифференцируемых сложных задач, а операция проста и легка в реализации, поэтому он широко применяется. Подобно генетическому алгоритм PSO в эволюционном процессе опирается, в основном, на две ключевые характеристики: множество и приспособленность. Каждая частица представляет собой одно возможное решение задачи, которое характеризуется параметрами положения и скорости, в то время как пригодность используется для измерения плюсов и минусов частиц. В отличие от генетического алгоритма, каждая эволюция оптимизации PSO не только зависит от ценности отдельных частиц, но и опирается на взаимосвязь и конкуренцию между множествами. Таким образом, хотя скорость сходимости велика и эффективность очень высока на ранней стадии эволюции множества частиц, но на поздней стадии скорость сходимости и точность алгоритма быстро падают и алгоритм легко попадает в локальный экстремум. Более того, при решении многомерных экстремальных задач точность сходимости алгоритма невелика. В этой связи в данной работе предложен алгоритм «динамической самоадаптирующейся и простой оптимизации множества частиц с возмущенным экстремумом и кроссовером» путем двух стратегий совершенствования: 1) упрощения уравнения скорости и динамической адаптивной регулировки инерционного веса множества частиц; 2) введения возмущенного экстремума и кроссовера, далее именуемого ecds-PSO. Базовый алгоритм множества частиц и его совершенствование Алгоритм процесса базового PSO (bPSO [2]) заключается в следующем: сначала инициализируется группа случайных частиц, затем в процессе итерационной эволюции частицы обновляют свою скорость и положение в соответствии с индивидуальным экстремумом и глобальным экстремумом, пока не находится оптимальное решение. Обновленные уравнения для положения и скорости можно записать как ; (1) , (2) где в итерации t положение частицы i обозначено как , скорость - , индивидуальное экстремальное положение частицы - , глобальное экстремальное положение - . На поздней стадии алгоритма частицы могут быть собраны в локальном экстремальном положении и не могут вырваться из него, что приводит к низкой скорости поиска или точности. Попытки решения этих проблем можно разделить на два подхода. Первый заключается в увеличении и регулировке глобального коэффициента для повышения скорости оптимизации и точности. Например, в [3] добавили инерционный вес к скорости в (1) с целью ускорить оптимизацию. Модифицированное уравнение выглядит так: . (3) В (2) добавили ограничивающий фактор к скорости [4] с целью предотвращения чрезмерной дивергенции частиц, а модифицированное уравнение выглядит как . (4) Было доказано, что большее отклоняет множество от первоначального направления, что приводит к дивергенции поиска, в то время как меньшее мало помогает для поиска скачка из локального экстремума. Фактор ограничения оказывает определенное влияние на оптимизацию, но в данном случае не подходит. В [5] добавили четыре вида новых частиц в алгоритм оптимизации PSO, скорректировали режим обновления и ввели динамическую регулировку инерционного веса изменения скорости фокусированного расстояния, чтобы преодолеть случайность алгоритма и решить проблемы слепого поиска на ранней стадии и медленной скорости поиска на поздней стадии алгоритма. В [6] предложили элитный алгоритм обратного обучения PSO, основанный на возмущении, и приняли метод нелинейного уменьшения для обновления весов, что значительно улучшило производительность алгоритма по скорости сходимости и точности. Усовершенствованный алгоритм оптимизации множества, основанный на генетическом кроссовере и стратегии мультихаоса, был предложен авторами работы [7]. Алгоритм значительно улучшил оптимизационные возможности за счет хаотической обработки инерционного веса, локального и глобального поиска. Согласно адаптивной оценке превосходного коэффициента и обновлению информации о положении глобальных оптимальных частиц, авторы [8] далее углубились в локальные решения с помощью стратегии 3-opt и применили улучшенный алгоритм оптимизации к дискретным задачам TSP. Приведенные исследования повысили скорость поиска и точность улучшенного алгоритма PSO, но идеи заключались лишь в оптимизации скоростных элементов bPSO. Такие стратегии значительно улучшили оптимальную скорость, но не решали проблему разнообразия частиц, поэтому на позднем этапе эволюции алгоритм легко попадал в локальную ловушку. Особенно в сложных задачах нелинейной оптимизации роль этих идей в повышении точности весьма ограничена [9]. Другой подход заключается в оптимизации положения частицы, а именно в динамической корректировке положения отдельных частиц. За счет увеличения разнообразия частиц повышаются их способность выскакивать из локального экстремума и точность. Например, получаем алгоритм оптимизации kPSO путем группировки и кластеризации частиц [10] и формирования на этой основе различных усовершенствованных алгоритмов. В [11] изучена топология пяти полей и обнаружено, что после введения кластеризации алгоритм может значительно повысить точность сходимости. С точки зрения топологии и адаптивного множества авторы [12] предложили адаптивный алгоритм оптимизации с гетерогенными характеристиками кластеризации и изучена способность обеспечения успеха кластеризации и чувствительности параметров. После вывода о том, что включение алгоритма в выборку признаков может повысить точность классификации [13], в [14] была использована стратегия классификации признаков с коэффициентом штрафа для управления процессом кластеризации. Было доказано, что этот метод оптимизации имеет лучший эффект кластеризации и глобальную сходимость, что очень подходит для задач уменьшения размерности для многомерных данных. Авторы [15] предложили многоцелевой алгоритм оптимизации, основанный на декомпозиции и дифференциальной эволюции, причем этот алгоритм генерировал набор однородных векторов направления через угол направления и обеспечивал равномерность распределения частиц. С помощью неявной политики удержания «элиты» и механизма коррекции дифференциальной эволюции исключалось попадание алгоритма в локальный экстремум, а с помощью стратегии сброса обеспечивалось разнообразие роев частиц. Большое количество исследований показало, что такого рода стратегии могут лучше решить проблему сходимости алгоритмов и разнообразия частиц, а также значительно улучшить оптимизационную способность. Однако достижение кластеризации, будучи очень сложным процессом, принесет много временных затрат и вычислительной сложности, поэтому при решении многомерных задач многоцелевой оптимизации возникают большие трудности. Динамическая самоадаптация и простая оптимизация множества частиц с возмущенным экстремумом и кроссовером Упрощение уравнения скорости и динамическая адаптация инерционного веса Предложена стратегия «упрощения уравнения скорости множества частиц и динамической регулировки адаптивного инерционного веса» с целью повышения скорости поиска и точности. Суть алгоритма заключается в процессе приближения к оптимальному значению через эволюционное положение частицы. В [9] было доказано, что скорость частиц не имеет ничего общего с оптимальным решением и был выдвинут упрощенный алгоритм PSO (sPSO) и упрощенное итерационное уравнение bPSO в виде . (5) Алгоритм sPSO устраняет концепцию скорости частицы, упрощает итерационное уравнение оптимизации множества (PSO), уменьшает влияние искусственного параметра или на процесс оптимизации и конечный результат, снижает затраты и сложность расчета для повышения точности и скорости. Но каждая частица по-прежнему использует одну и ту же итеративную формулу эволюции, что ограничивает возможности глобальной оптимизации. Однако на средне-поздней стадии алгоритма остается застойное множествование из-за концентрированного расположения частиц. Поэтому в данной работе на основе (5) вводится динамический адаптивный инерционный вес, а именно для плюсов и минусов каждого текущего местоположения частицы динамически придается разный инерционный вес с целью повышения способности и скорости частиц в глобальной оптимизации. Стратегия может быть описана следующим образом. По характеристикам частицы приходят к заключению о пространственном соотношении между оптимальным и текущим положениями. Для частиц, близких к оптимальному положению, уменьшается их инерционный вес, чтобы улучшить поисковую способность в пределах небольшой области вблизи оптимального положения. Для частиц, удаленных от оптимального положения, увеличивается инерционный вес, чтобы улучшить их способность приближаться к оптимальному положению. Вводится итерационное уравнение множества частиц динамического адаптивного инерционного веса в форме ; (6) (7) где - индивидуальное значение адаптационной способности; - среднее значение для множества. Если , то частица находится в хорошем положении, близком к оптимальному. В этом случае уменьшается инерционный вес в следующей итерации, пропускаются оптимальные решения из-за слишком быстрого обновления положения. Если , то частица находится в плохом положении, которое расположено далеко от оптимального. В этом случае увеличивается инерционный вес в следующей итерации и улучшается скорость оптимизации. Введение экстремального возмущения и кроссовера Предложенная стратегия «введения возмущенного экстремума и кроссовера» направлена на то, чтобы множество оставалось разнообразным и жизнеспособным на средней и поздней стадиях алгоритма, что играет важную роль в улучшении поисковой способности и предотвращении попадания алгоритма в ловушку локального экстремума. Рассматривая сходимость уравнения (6), предполагаем, что и равномерно распределены. На основе [16-19] можно вывести: (8) Выражение (8) показывает, что результаты оптимизации всех частиц после итерации будут получены совместно с ее экстремумом и экстремумом множества . То есть, если все частицы в процессе оптимизации не находят лучшего места, чем и , то частица не может отклоняться, поэтому поиск останавливается. Исходя из этого, предлагается: 1) наложить экстремальное возмущение на оптимальное положение ; 2) провести операцию кроссовера генетического алгоритма для всех частиц . А именно одновременно скорректировать положение отдельных частиц и положение экстремумов роев, заставить все частицы перемещаться в новое место, чтобы открыть новые пути поиска, а также избавиться от локального экстремума и найти лучшее решение. По сравнению со стратегией кластеризации kPSO при том же разнообразии частиц выдвинутая в данной работе стратегия о введении возмущенного экстремума и кроссовера имеет значительно меньшую вычислительную сложность и временные затраты. Это связано с тем, что на каждом шаге итерации отсутствуют сравнение, расчет и кластеризация положения частиц [20-24]. В соответствии с изложенным выражение (6) преобразуем к виду ; (9) (10) (11) (12) Здесь - элемент экстремального возмущения, а его роль состоит в том, чтобы нарушить глобальный экстремум множества. Выражения (10) и (11) указывают, что если глобальное оптимальное значение множества не обновляется более трех раз, то дается случайное возмущение его экстремуму. Выражение (12) используется для изменения положения каждой частицы, так что на каждом шаге итерационного процесса сначала выбирается множество в соответствии с определенной множественностью, а затем обменивается позициями между частицами по пересечению . Когда операция скрещивания завершается, сохраняются результаты и отбрасываются исходные значения для гарантии того, что рассматривается прежнее множество. Эксперименты и анализ результатов Для сравнения и анализа различных характеристик алгоритма ecds-PSO были разработаны три вида экспериментальных планов: Эксперимент 1. Анализ эффективности алгоритма по скорости сходимости и точности. Выбраны три типичные контрольные функции для фиксированного числа итераций с целью сравнения и оценки скорости сходимости и точности алгоритмов bPSO, sPSO, kPSO и ecds-PSO. Цель - проверить влияние стратегии улучшения на скорость сходимости и точность. Эксперимент 2. Анализ разнообразия множества. Выбрана многопиковая функция Швефеля. При условии одинакового начального значения сравнивается и оценивается состояние распределения множества алгоритмов bPSO, kPSO и ecds-PSO. Цель - проверить влияние стратегии улучшения на разнообразие частиц и способность избавиться от локального экстремума. Эксперимент 3. Статистический анализ производительности алгоритма. Выбраны три типичные бенчмарковые функции и проведен бенчмарковый тест на производительность алгоритмов bPSO, sPSO, kPSO и ecds-PSO. Цель - комплексная оценка различных статистических характеристик алгоритма ecds-PSO. В ходе эксперимента были выбраны три часто используемые тестовые функции бенчмарка и связанные с ними параметры (табл. 1). Таблица 1 Бенчмарковые функции, используемые для тестирования методов улучшения Код Характерис¬тика Формула Диапазон Цель Оптимум Инструкция Сфера Унимодальный [-100, 100]30 10-5 0 Обычные однопиковые функции, гладкая поверхность, используются для проверки регулярной работы алгоритма Розеброк Унимодальный [-100, 100]30 102 0 Однопиковые функции, небольшой наклон на полюсе, используются для проверки возможности выполнения алгоритма Растригин Мульти- модаль- ный [-100, 100]30 10-5 0 Многопиковые функции, многополюсные функции, используются для проверки глобальной поисковой и оптимизационной способности алгоритма Согласно [3, 4], размер множества алгоритма bPSO взят равным 30, . Величина принимает случайные значения в диапазоне , . На основании [9] размер множества sPSO составляет 15, . Согласно [12], размер множества kPSO принимается равным 30, , , , коэффициент кластеризации . Заданный размер множества алгоритма ecds-PSO равен 30, , , вероятность выбора генетического алгоритма принимает случайные значения в диапазоне [0.2, 0.4], а вероятность кроссовера - случайные значения в интервале [0.2, 0.8]. Скорость сходимости и точность Используя три эталонные функции таблицы, в случае фиксированной эволюционной алгебры сравнивались точность сходимости и скорость алгоритмов bPSO, sPSO, kPSO и ecds-PSO. Результаты показаны на рис. 1-3. Согласно кривым сходимости рис. 1, 2 и 3, алгоритмы sPSO и ecds-PSO по сравнению с bPSO и kPSO показали преимущества в скорости сходимости, что демонстрирует обоснованность и эффективность стратегии. Способность к сходимости ecds-PSO и kPSO по сравнению с bPSO и sPSO была значительно выше, т.е. стратегия имеет очень хорошие оптимизационные характеристики в способности избавляться от локального экстремума на средней-поздней стадии эволюции алгоритма, а также в точности сходимости. Рис. 1. Сфера Рис. 2. Розеброк Рис. 3. Растригин Разнообразие множеств частиц В этом эксперименте выбрана функция Швефеля для сравнения и оценки способности алгоритмов sPSO, kPSO и ecds-PSO поддерживать разнообразие частиц в процессе эволюции. Функция Швефеля - типичная «обманчивая» функция с одной глобальной и тремя локальными оптимальными точками. Четыре точки распределены по четырем углам 3D-графика на больших расстояниях. Застряв в локальном оптимуме, трудно выпрыгнуть и достичь точки глобального оптимального решения. Эта функция используется, в основном, для тестирования алгоритма глобальной оптимизации и разнообразия множества, а конкретные графики представлены на рис. 4. Для того чтобы показать пиковую производительность функции более наглядно, в данной работе была реализована небольшая деформация и формула после деформации . Результаты приведены на рис. 5-7. Рис. 4. Функция Швефеля Рис. 5. Итоговое итерационное состояние для трех алгоритмов Рис. 6. Распределение множества алгоритма PSO Рис. 7. Распределение множества алгоритма bPSO и kPSO На рис. 5 показан график наложения оптимальных результатов трех алгоритмов при одинаковых начальных значениях после десятикратного запуска алгоритмов bPSO, kPSO и ecds-PSO (задана одинаковая точность оптимизации, но нет ограничений на количество итераций). Из рис. 5 следует, что bPSO находил оптимальное решение 7 раз, kPSO - 8, ecds-PSO - 10 со скоростью успеха 100%. На рис. 6 показано распределение частиц (размер множества 50) после того, как ecds-PSO нашел оптимальное решение, на рис. 7 - bPSO и kPSO нашли оптимальное решение. При сравнении рис. 6 и 7 видно, что на средне-позднем этапе эволюции алгоритма ecds-PSO разнообразие частиц оставалось на значительном уровне. По сравнению с kPSO, который характеризовался сохранением разнообразия частиц, ecds-PSO был хорош, и, исходя из теоретического анализа, ecds-PSO должен быть более случайным, чем kPSO по распределению частиц. Статистический анализ производительности алгоритма С помощью трех эталонных функций (см. табл. 1), проведены анализ и сравнение различных статистических элементов алгоритмов bPSO, sPSO, kPSO и ecds-PSO. Каждый алгоритм проходил независимое выполнение в течение 20 раз, а фиксированная итерация выполнялась 500 раз для каждого. Статистические параметры включали в себя: наихудшее значение (худшее), оптимальное значение (лучшее), среднее оптимальное значение (среднее лучшее) и стандартное отклонение (SD). Результаты приведены в табл. 2. Из табл. 2 следует: 1) в функциональных тестах сферы из сравнений алгоритмов bPSO и sPSO, kPSO и ecds-PSO можно значительно улучшить точность алгоритма поиска; 2) в функциональных тестах Розеброка алгоритмы kPSO и sPSO имели одинаковый оптимизационный эффект, в то время как точность оптимизации ecds-PSO была на четыре-пять порядков выше; 3) в функциональных тестах Растригина, поскольку алгоритмы kPSO и ecds-PSO могли обеспечить более богатое разнообразие частиц и жизнеспособность, они имели значительно более высокую точность поиска, чем bPSO и sPSO; 4) благодаря производительности алгоритма ecds-PSO он значительно улучшил решающую способность по сравнению с bPSO, sPSO, kPSO, а также отразил большее преимущество в точности поиска. Таблица 2 Статистика производительности различных улучшенных алгоритмов PSO Функция Алгоритм Наихудший Лучший Средний лучший SD Сфера bPSO 7.6910-4 2.6710-7 2.0110-6 1.4210-6 kPSO 1.7910-18 0 3.6210-51 4.2510-50 sPSO 4.2610-15 0 5.3810-32 4.6810-32 ecds-PSO 8.9410-57 0 4.5510-57 2.8710-57 Розеброк bPSO 7.67105 1.07105 4.07105 2.77105 kPSO 1.49106 2.14102 8.48104 5.82104 sPSO 5.84105 8.03101 6.87103 3.47103 ecds-PSO 8.8710-1 6.6910-1 2.8910-1 1.7910-1 Растригин bPSO 3.1710-14 1.7410-15 9.1610-15 8.6210-15 kPSO 1.4210-18 0 5.5910-20 4.6210-20 sPSO 2.5610-14 3.8410-17 7.5310-16 2.6310-16 ecds-PSO 0 0 0 0 Заключение С учетом проблем скорости сходимости и точности алгоритма множества частиц принята стратегия улучшения, которая основывается на динамической адаптации инерционного веса и упрощении уравнения скорости. Применительно к задачам оптимизации множества частиц (алгоритм PSO), которые легко попадали в локальные экстремумы, одобрена стратегия возмущенного экстремума и кроссовера. На основе объединения двух этих стратегий предложена динамическая самоадаптация и простая оптимизация множества частиц с возмущенным экстремумом и кроссовером (ecds-PSO). Разработаны три набора оптимизационных вычислительных экспериментов, которые доказали, что алгоритм оптимизации ecds-PSO обладает более высокой точностью, более высокой скоростью сходимости и большей способностью избавляться от локального экстремума.

Скачать электронную версию публикации