Главная В помощь малому бизнесу

Применение метод роя частиц c исходники. Алгоритм роя частиц

17.07.2019

Алгоритм

Пусть f : ℝ n → ℝ - целевая функция, которую требуется минимизировать, S - количество частиц в рое, каждой из которых сопоставлена координата x i ∈ ℝ n в пространстве решений и скорость v i ∈ ℝ n . Пусть также p i - лучшее из известных положений частицы i , а g - наилучшее известное состояние роя в целом. Тогда общий вид метода роя частиц таков.

  • Для каждой частицы i = 1, …, S сделать:
    • Сгенерировать начальное положение частицы с помощью случайного вектора x i ~ U (b lo , b up ), имеющего многомерное равномерное распределение . b lo и b up - нижняя и верхняя границы пространства решений соответственно.
    • Присвоить лучшему известному положению частицы его начальное значение: p i ← x i .
    • Если (f (p i) < f (g )), то обновить наилучшее известное состояние роя: g ← p i .
    • Присвоить значение скорости частицы: v i ~ U (-(b up -b lo ), (b up -b lo )).
  • Пока не выполнен критерий остановки (например, достижение заданного числа итераций или необходимого значения целевой функции), повторять:
    • Для каждой частицы i = 1, …, S сделать:
      • Сгенерировать случайные векторы r p , r g ~ U (0,1).
      • Обновить скорость частицы: v i ← ω v i + φ p r p × (p i -x i) + φ g r g × (g -x i), где операция × означает покомпонентное умножение.
      • Обновить положение частицы переносом x i на вектор скорости: x i ← x i + v i . Заметим, что этот шаг выполняется вне зависимости от улучшения значения целевой функции.
      • Если (f (x i) < f (p i)), то делать:
        • Обновить лучшее известное положение частицы: p i ← x i .
        • Если (f (p i) < f (g )), то обновить лучшее известное состояние роя в целом: g ← p i .
  • Теперь g содержит лучшее из найденных решений.

Параметры ω, φ p , и φ g выбираются вычислителем и определяют поведение и эффективность метода в целом. Эти параметры составляют предмет многих исследований (см. ниже) .

Подбор параметров

Выбор оптимальных параметров метода роя частиц - тема значительного количества исследовательских работ, см., например, работы Ши и Эберхарта , Карлисла и Дозера , ван ден Берга , Клерка и Кеннеди , Трелеа , Браттона и Блеквэлла , а также Эверса .

Простой и эффективный путь подбора параметров метода предложен Педерсеном и другими авторами. Они же провели численные эксперименты с различными оптимизациоными проблемами и параметрами. Техника выбора этих параметров называется мета-оптимизацией, так как другой оптимизационный алгоритм используется для «настройки» параметров МРЧ. Входные параметры МРЧ с наилучшей производительностью оказались противоречащими основным принципам, описанным в литературе, и часто дают удовлетворительные результаты оптимизации для простых случаев МРЧ. Реализацию их можно найти в открытой библиотеке SwarmOps.

Варианты алгоритма

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

См. также

  • Пчелиный алгоритм
  • Gravitational Search Algorithm

Примечания

  1. (1995) "Particle Swarm Optimization". Proceedings of IEEE International Conference on Neural Networks IV : 1942-1948.
  2. (1998) "A modified particle swarm optimizer". Proceedings of IEEE International Conference on Evolutionary Computation : 69-73.
  3. Swarm Intelligence. - Morgan Kaufmann, 2001.
  4. Poli, R. (2007). «An analysis of publications on particle swarm optimisation applications ». Technical Report CSM-469 (Department of Computer Science, University of Essex, UK).
  5. Poli, R. (2008). «Analysis of the publications on the applications of particle swarm optimisation ». : 1-10. DOI :10.1155/2008/685175 .
  6. (1998) "Parameter selection in particle swarm optimization". Proceedings of Evolutionary Programming VII (EP98) : 591-600.
  7. (2000) "Comparing inertia weights and constriction factors in particle swarm optimization". Proceedings of the Congress on Evolutionary Computation 1 : 84-88.
  8. (2001) "An Off-The-Shelf PSO". Proceedings of the Particle Swarm Optimization Workshop : 1-6.
  9. van den Bergh F. An Analysis of Particle Swarm Optimizers. - University of Pretoria, Faculty of Natural and Agricultural Science, 2001.
  10. (2002) «The particle swarm - explosion, stability, and convergence in a multidimensional complex space». IEEE Transactions on Evolutionary Computation 6 (1): 58-73.
  11. Trelea, I.C. (2003). «The Particle Swarm Optimization Algorithm: convergence analysis and parameter selection». Information Processing Letters 85 : 317-325.
  12. (2008) «A Simplified Recombinant PSO». Journal of Artificial Evolution and Applications .
  13. Evers G. An Automatic Regrouping Mechanism to Deal with Stagnation in Particle Swarm Optimization . - The University of Texas - Pan American, Department of Electrical Engineering, 2009.
  14. Pedersen M.E.H. Tuning & Simplifying Heuristical Optimization . - University of Southampton, School of Engineering Sciences, Computational Engineering and Design Group, 2010.
  15. Pedersen, M.E.H.; Chipperfield, A.J. (2010). «Simplifying particle swarm optimization ». Applied Soft Computing 10 : 618-628.
  16. (2002) "The LifeCycle Model: combining particle swarm optimisation, genetic algorithms and hillclimbers". Proceedings of Parallel Problem Solving from Nature VII (PPSN) : 621-630.
  17. (2010) «An efficient hybrid approach based on PSO, ACO and k-means for cluster analysis». Applied Soft Computing 10 (1): 183-197.
  18. (2002) "Extending Particle Swarm Optimisers with Self-Organized Criticality". Proceedings of the Fourth Congress on Evolutionary Computation (CEC) 2 : 1588-1593.
  19. Xinchao, Z. (2010). «A perturbed particle swarm algorithm for numerical optimization». Applied Soft Computing 10 (1): 119-124.
  20. (2009) «Adaptive Particle Swarm Optimization». IEEE Transactions on Systems, Man, and Cybernetics 39 (6): 1362-1381.

Ссылки

  • Particle Swarm Central . Новости, люди, места, программы, статьи и др. В частности, см. текущий стандарт МРЧ. (англ.)
  • SwarmOps . Подбор параметров / калибровка МРЧ и другие мета-оптимизационные методы. Программная библиотека на языках C и C#.
  • EvA2 - комплексный инструмент эволюционных методов оптимизации и МРЧ с открытым исходным кодом, написанный на Java.
  • ParadisEO мощный C++ фреймворк, предназначенный для создания различных метаэвристик, включая алгоритмы МРЧ . Готовые к использованию алгоритмы, множество учебников, помогающих быстро создать собственный вариант МРЧ.
  • Код МРЧ на FORTRAN Измерение производительности на тестовых функциях.
  • - GPLed computational intelligence simulation and research environment written in Java, includes various PSO implementations
  • Использование реализации МРЧ на Python для решения головоломки о пересечении лестниц.
  • ECF - Evolutionary Computation Framework различные алгоритмы, генотипы, распараллеливание, учебники.
Методы оптимизации
Одномерные
Стая птиц представляет собой прекрасный пример коллективного поведения животных. Летая большими группами, они почти никогда не сталкиваются в воздухе. Стая двигается плавно и скоординировано, словно ей кто-то управляет. А любой, кто вешал в своем дворе кормушку, знает, что спустя несколько часов его найдут все птицы в округе.


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

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

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

Boids

Наблюдение за птицами вдохновило Крейга Рейнольдса (Craig Reynolds) на создание в 1986 году компьютерной модели, которую он назвал Boids. Для имитации поведения стаи птиц, Рейнольдс запрограммировал поведение каждой из них в отдельности, а также их взаимодействие. При этом он использовал три простых принципа. Во-первых, каждая птица в его модели стремилась избежать столкновений с другими птицами. Во-вторых, каждая птица двигалась в том же направлении, что и находящиеся неподалеку птицы. В-третьих, птицы стремились двигаться на одинаковом расстоянии друг от друга.

Результаты первых же симуляций удивили самого создателя: несмотря на простоту лежащих в основе программы алгоритмов, стая на экране выглядела крайне правдоподобно. Птицы сбивались в группы, уходили от столкновений и даже хаотично метались точь-в-точь как настоящие.
Как специалист в области компьютерной графики, Крейг Рейнольдс был в первую очередь заинтересован визуальной стороной результатов созданной им имитации. Однако, в посвященной Boids статье он также отметил, что разработанная им поведенческая модель может быть расширена введением дополнительных факторов – таких, как поиск пищи или боязнь хищников .

Классический алгоритм роя частиц

В 1995 году Джеймс Кеннеди (James Kennedy) и Рассел Эберхарт (Russel Eberhart) предложили метод для оптимизации непрерывных нелинейных функций, названный ими алгоритмом роя частиц . Вдохновением для них послужила имитационная модель Рейнольдса, а также работа Хеппнера (Heppner) и Гренадера (Grenader) на схожую тему . Кеннеди и Эберхарт отметили, что обе модели основаны на управлении дистанциями между птицами – а, следовательно, синхронность стаи является в них функцией от усилий, которые птицы прилагают для сохранения оптимальной дистанции.

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

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

На каждой итерации алгоритма направление и длина вектора скорости каждой из частиц изменяются в соответствие со сведениями о найденных оптимумах:

Где – вектор скорости частицы ( – его i-ая компонента), , – постоянные ускорения, – лучшая найденная частицей точка, – лучшая точка из пройденных всеми частицами системы, – текущее положение частицы, а функция возвращает случайное число от 0 до 1 включительно.

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

Модификации классического алгоритма

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

LBEST

Позже в том же 1995 году была опубликована статья Кеннеди и Эберхарта, в которой они назвали оригинальный алгоритм “GBEST”, поскольку он использует глобальное лучшее решение (global best) для формирования векторов скоростей, а также предложили его модификацию, названную ими “LBEST”. При обновлении направления и скорости движения частицы в LBEST используют информацию о решениях соседних с ними частиц:

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

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

Inertia Weighted PSO

В 1998 году Юхи Ши (Yuhui Shi) и Рассел Эберхарт предложили модификацию, на первый взгляд совсем незначительно отличающуюся от классического алгоритма . В своей статье Ши и Эберхарт заметили, что одной из главных проблем при решении задач оптимизации является баланс между тщательностью исследованием пространства поиска и скоростью сходимости алгоритма. В зависимости от задачи и характеристик поискового пространства в ней, этот баланс должен быть различным.
С учетом этого, Ши и Эберхарт предложили изменить правило обновления векторов скоростей частиц:

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

Time-Varying Inertia Weighted PSO

В своей работе 1998 года, Ши и Эберхарт отметили, что инерция не обязательно должна быть положительной константой: она может изменяться во время работы алгоритма по линейному и даже нелинейному закону . В статье 1999 года и более поздних работах они наиболее часто использовали линейный закон убывания, как достаточно эффективный и вместе с тем простой . Тем не менее, разрабатывались и успешно применялись и другие законы изменения инерции.

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

Canonical PSO

В 2002 году Марис Клер (Maurice Clerc) и Джеймс Кеннеди предложили свою модификацию алгоритма роя частиц, которая стала настолько популярной, что теперь ее принято называть каноническим алгоритмом роя частиц . Он позволяет избавиться от необходимости «угадывать» подходящие значения регулируемых параметров алгоритма, контролируя сходимость частиц.

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

Где , а коэффициент сжатия равен:

Такой подход гарантирует сходимость алгоритма без необходимости явно контролировать скорость частиц.

Fully Informed Particle Swarm

В своей работе 2004 года Руи Мендес (Rui Mendes), Джеймс Кеннеди и Жозе Невес (José Neves) заметили, что принятое в каноническом алгоритм роя частиц допущение о том, что на каждую из частиц влияет только наиболее успешная, не соответствует лежащим в его основе природным механизмам и, возможно, ведет к снижению эффективности алгоритма . Они предположили, что из-за чрезмерного внимания алгоритма к единственному решению может быть потеряна важная информация о структуре пространства поиска.

Исходя из этого, они решили сделать все частицы «полностью информированными», то есть получающими информацию от всех соседних частиц. Для этого они изменили в каноническом алгоритме закон изменения скорости:

Где – множество соседей частицы, – лучшая из пройденных k-ым соседом точек. – весовая функция, которая может отражать любую характеристику k-ой частицы, которая считается важной: значение целевой функции в точке, в которой она находится, дистанцию от нее до данной частицы и так далее.

Заключение

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

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

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

Литература

Craig Reynolds, “Flocks, Herds, and Schools: A Distributed Behavioral Model” // Computer Graphics, 21(4), стр. 25–34, 1987 г.
J. Kennedy, R. C. Eberhart, “Particle swarm optimization” // In Proceedings of IEEE International Conference on Neural Networks, стр. 1942–1948, 1995 г.
R. C. Eberhart, J. Kennedy, “A new optimizer using particle swarm theory” // Proceedings of the Sixth International Symposium on Micro Machine and Human Science MHS’95, стр. 39–43, 1995 г.
F. Heppner, U. Grenander, “A stochastic nonlinear model for coordinated bird flocks” // The Ubiquity of Chaos, стр. 233–238, 1990 г.
Y. Shi, R. Eberhart, “A modified particle swarm optimizer” // The 1998 IEEE International Conference on Evolutionary Computation Proceedings, стр. 69–73, 1998 г.
Y. Shi, R. Eberhart, “Empirical study of particle swarm optimization” // Proceedings of the 1999 IEEE Congress on Evolutionary Computation, стр. 1945–1950, 1999 г.
M. Clerc, J. Kennedy, “The particle swarm – explosion, stability, and convergence in a multidimensional complex space” // IEEE Transactions on Evolutionary Computation, №6 (1), стр. 58–73, 2002 г.
R. Mendes, J. Kennedy, J. Neves, “The fully informed particle swarm: Simpler, maybe better” // IEEE Transactions on Evolutionary Computation, №8 (3), стр. 204–210, 2004 г.

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

Алгоритм

Пусть f : ℝ n → ℝ - целевая функция, которую требуется минимизировать, S - количество частиц в рое, каждой из которых сопоставлена координата x i ∈ ℝ n в пространстве решений и скорость v i ∈ ℝ n . Пусть также p i - лучшее из известных положений частицы i , а g - наилучшее известное состояние роя в целом. Тогда общий вид метода роя частиц таков.

  • Для каждой частицы i = 1, …, S сделать:
    • Сгенерировать начальное положение частицы с помощью случайного вектора x i ~ U (b lo , b up ), имеющего многомерное равномерное распределение . b lo и b up - нижняя и верхняя границы пространства решений соответственно.
    • Присвоить лучшему известному положению частицы его начальное значение: p i ← x i .
    • Если (f (p i) < f (g )), то обновить наилучшее известное состояние роя: g ← p i .
    • Присвоить значение скорости частицы: v i ~ U (-(b up -b lo ), (b up -b lo )).
  • Пока не выполнен критерий остановки (например, достижение заданного числа итераций или необходимого значения целевой функции), повторять:
    • Для каждой частицы i = 1, …, S сделать:
      • Сгенерировать случайные векторы r p , r g ~ U (0,1).
      • Обновить скорость частицы: v i ← ω v i + φ p r p × (p i -x i) + φ g r g × (g -x i), где операция × означает покомпонентное умножение.
      • Обновить положение частицы переносом x i на вектор скорости: x i ← x i + v i . Заметим, что этот шаг выполняется вне зависимости от улучшения значения целевой функции.
      • Если (f (x i) < f (p i)), то делать:
        • Обновить лучшее известное положение частицы: p i ← x i .
        • Если (f (p i) < f (g )), то обновить лучшее известное состояние роя в целом: g ← p i .
  • Теперь g содержит лучшее из найденных решений.

Параметры ω, φ p , и φ g выбираются вычислителем и определяют поведение и эффективность метода в целом. Эти параметры составляют предмет многих исследований (см. ниже) .

Подбор параметров

Выбор оптимальных параметров метода роя частиц - тема значительного количества исследовательских работ, см., например, работы Ши и Эберхарта , Карлисла и Дозера , ван ден Берга , Клерка и Кеннеди , Трелеа , Браттона и Блеквэлла , а также Эверса .

Простой и эффективный путь подбора параметров метода предложен Педерсеном и другими авторами. Они же провели численные эксперименты с различными оптимизациоными проблемами и параметрами. Техника выбора этих параметров называется мета-оптимизацией , так как другой оптимизационный алгоритм используется для «настройки» параметров МРЧ. Входные параметры МРЧ с наилучшей производительностью оказались противоречащими основным принципам, описанным в литературе, и часто дают удовлетворительные результаты оптимизации для простых случаев МРЧ. Реализацию их можно найти в открытой библиотеке SwarmOps.

Варианты алгоритма

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

Напишите отзыв о статье "Метод роя частиц"

Примечания

  1. (1995) "Particle Swarm Optimization". Proceedings of IEEE International Conference on Neural Networks IV : 1942-1948.
  2. (1998) "A modified particle swarm optimizer". Proceedings of IEEE International Conference on Evolutionary Computation : 69-73.
  3. Swarm Intelligence. - Morgan Kaufmann, 2001.
  4. Poli, R. (2007). «». Technical Report CSM-469 (Department of Computer Science, University of Essex, UK).
  5. Poli, R. (2008). «». : 1-10. DOI :10.1155/2008/685175 .
  6. (1998) "Parameter selection in particle swarm optimization". Proceedings of Evolutionary Programming VII (EP98) : 591-600.
  7. (2000) "Comparing inertia weights and constriction factors in particle swarm optimization". Proceedings of the Congress on Evolutionary Computation 1 : 84-88.
  8. (2001) "An Off-The-Shelf PSO". Proceedings of the Particle Swarm Optimization Workshop : 1-6.
  9. van den Bergh F. An Analysis of Particle Swarm Optimizers. - University of Pretoria, Faculty of Natural and Agricultural Science, 2001.
  10. (2002) «The particle swarm - explosion, stability, and convergence in a multidimensional complex space». IEEE Transactions on Evolutionary Computation 6 (1): 58-73.
  11. Trelea, I.C. (2003). «The Particle Swarm Optimization Algorithm: convergence analysis and parameter selection». Information Processing Letters 85 : 317-325.
  12. (2008) «A Simplified Recombinant PSO». Journal of Artificial Evolution and Applications .
  13. Evers G. . - The University of Texas - Pan American, Department of Electrical Engineering, 2009.
  14. Pedersen M.E.H. . - University of Southampton, School of Engineering Sciences, Computational Engineering and Design Group, 2010.
  15. Pedersen, M.E.H.; Chipperfield, A.J. (2010). «». Applied Soft Computing 10 : 618-628.
  16. (2002) "The LifeCycle Model: combining particle swarm optimisation, genetic algorithms and hillclimbers". Proceedings of Parallel Problem Solving from Nature VII (PPSN) : 621-630.
  17. (2010) «An efficient hybrid approach based on PSO, ACO and k-means for cluster analysis». Applied Soft Computing 10 (1): 183-197.
  18. (2002) "Extending Particle Swarm Optimisers with Self-Organized Criticality". Proceedings of the Fourth Congress on Evolutionary Computation (CEC) 2 : 1588-1593.
  19. Xinchao, Z. (2010). «A perturbed particle swarm algorithm for numerical optimization». Applied Soft Computing 10 (1): 119-124.
  20. (2009) «Adaptive Particle Swarm Optimization». IEEE Transactions on Systems, Man, and Cybernetics 39 (6): 1362-1381.

Ссылки

  • . Новости, люди, места, программы, статьи и др. В частности, см. текущий стандарт МРЧ. (англ.)
Одномерные
Прямые методы
Первого порядка
Второго порядка
Стохастические
Методы линейного
программирования
Методы нелинейного
программирования

Отрывок, характеризующий Метод роя частиц

– Да, – сказал Ростов, как будто выговорить это слово стоило большого труда, и сел за соседний стол.
Оба молчали; в комнате сидели два немца и один русский офицер. Все молчали, и слышались звуки ножей о тарелки и чавканье поручика. Когда Телянин кончил завтрак, он вынул из кармана двойной кошелек, изогнутыми кверху маленькими белыми пальцами раздвинул кольца, достал золотой и, приподняв брови, отдал деньги слуге.
– Пожалуйста, поскорее, – сказал он.
Золотой был новый. Ростов встал и подошел к Телянину.
– Позвольте посмотреть мне кошелек, – сказал он тихим, чуть слышным голосом.
С бегающими глазами, но всё поднятыми бровями Телянин подал кошелек.
– Да, хорошенький кошелек… Да… да… – сказал он и вдруг побледнел. – Посмотрите, юноша, – прибавил он.
Ростов взял в руки кошелек и посмотрел и на него, и на деньги, которые были в нем, и на Телянина. Поручик оглядывался кругом, по своей привычке и, казалось, вдруг стал очень весел.
– Коли будем в Вене, всё там оставлю, а теперь и девать некуда в этих дрянных городишках, – сказал он. – Ну, давайте, юноша, я пойду.
Ростов молчал.
– А вы что ж? тоже позавтракать? Порядочно кормят, – продолжал Телянин. – Давайте же.
Он протянул руку и взялся за кошелек. Ростов выпустил его. Телянин взял кошелек и стал опускать его в карман рейтуз, и брови его небрежно поднялись, а рот слегка раскрылся, как будто он говорил: «да, да, кладу в карман свой кошелек, и это очень просто, и никому до этого дела нет».
– Ну, что, юноша? – сказал он, вздохнув и из под приподнятых бровей взглянув в глаза Ростова. Какой то свет глаз с быстротою электрической искры перебежал из глаз Телянина в глаза Ростова и обратно, обратно и обратно, всё в одно мгновение.
– Подите сюда, – проговорил Ростов, хватая Телянина за руку. Он почти притащил его к окну. – Это деньги Денисова, вы их взяли… – прошептал он ему над ухом.
– Что?… Что?… Как вы смеете? Что?… – проговорил Телянин.
Но эти слова звучали жалобным, отчаянным криком и мольбой о прощении. Как только Ростов услыхал этот звук голоса, с души его свалился огромный камень сомнения. Он почувствовал радость и в то же мгновение ему стало жалко несчастного, стоявшего перед ним человека; но надо было до конца довести начатое дело.
– Здесь люди Бог знает что могут подумать, – бормотал Телянин, схватывая фуражку и направляясь в небольшую пустую комнату, – надо объясниться…
– Я это знаю, и я это докажу, – сказал Ростов.
– Я…
Испуганное, бледное лицо Телянина начало дрожать всеми мускулами; глаза всё так же бегали, но где то внизу, не поднимаясь до лица Ростова, и послышались всхлипыванья.
– Граф!… не губите молодого человека… вот эти несчастные деньги, возьмите их… – Он бросил их на стол. – У меня отец старик, мать!…
Ростов взял деньги, избегая взгляда Телянина, и, не говоря ни слова, пошел из комнаты. Но у двери он остановился и вернулся назад. – Боже мой, – сказал он со слезами на глазах, – как вы могли это сделать?
– Граф, – сказал Телянин, приближаясь к юнкеру.
– Не трогайте меня, – проговорил Ростов, отстраняясь. – Ежели вам нужда, возьмите эти деньги. – Он швырнул ему кошелек и выбежал из трактира.

Вечером того же дня на квартире Денисова шел оживленный разговор офицеров эскадрона.
– А я говорю вам, Ростов, что вам надо извиниться перед полковым командиром, – говорил, обращаясь к пунцово красному, взволнованному Ростову, высокий штаб ротмистр, с седеющими волосами, огромными усами и крупными чертами морщинистого лица.
Штаб ротмистр Кирстен был два раза разжалован в солдаты зa дела чести и два раза выслуживался.
– Я никому не позволю себе говорить, что я лгу! – вскрикнул Ростов. – Он сказал мне, что я лгу, а я сказал ему, что он лжет. Так с тем и останется. На дежурство может меня назначать хоть каждый день и под арест сажать, а извиняться меня никто не заставит, потому что ежели он, как полковой командир, считает недостойным себя дать мне удовлетворение, так…
– Да вы постойте, батюшка; вы послушайте меня, – перебил штаб ротмистр своим басистым голосом, спокойно разглаживая свои длинные усы. – Вы при других офицерах говорите полковому командиру, что офицер украл…
– Я не виноват, что разговор зашел при других офицерах. Может быть, не надо было говорить при них, да я не дипломат. Я затем в гусары и пошел, думал, что здесь не нужно тонкостей, а он мне говорит, что я лгу… так пусть даст мне удовлетворение…
– Это всё хорошо, никто не думает, что вы трус, да не в том дело. Спросите у Денисова, похоже это на что нибудь, чтобы юнкер требовал удовлетворения у полкового командира?
Денисов, закусив ус, с мрачным видом слушал разговор, видимо не желая вступаться в него. На вопрос штаб ротмистра он отрицательно покачал головой.
– Вы при офицерах говорите полковому командиру про эту пакость, – продолжал штаб ротмистр. – Богданыч (Богданычем называли полкового командира) вас осадил.
– Не осадил, а сказал, что я неправду говорю.
– Ну да, и вы наговорили ему глупостей, и надо извиниться.
– Ни за что! – крикнул Ростов.
– Не думал я этого от вас, – серьезно и строго сказал штаб ротмистр. – Вы не хотите извиниться, а вы, батюшка, не только перед ним, а перед всем полком, перед всеми нами, вы кругом виноваты. А вот как: кабы вы подумали да посоветовались, как обойтись с этим делом, а то вы прямо, да при офицерах, и бухнули. Что теперь делать полковому командиру? Надо отдать под суд офицера и замарать весь полк? Из за одного негодяя весь полк осрамить? Так, что ли, по вашему? А по нашему, не так. И Богданыч молодец, он вам сказал, что вы неправду говорите. Неприятно, да что делать, батюшка, сами наскочили. А теперь, как дело хотят замять, так вы из за фанаберии какой то не хотите извиниться, а хотите всё рассказать. Вам обидно, что вы подежурите, да что вам извиниться перед старым и честным офицером! Какой бы там ни был Богданыч, а всё честный и храбрый, старый полковник, так вам обидно; а замарать полк вам ничего? – Голос штаб ротмистра начинал дрожать. – Вы, батюшка, в полку без году неделя; нынче здесь, завтра перешли куда в адъютантики; вам наплевать, что говорить будут: «между павлоградскими офицерами воры!» А нам не всё равно. Так, что ли, Денисов? Не всё равно?
Денисов всё молчал и не шевелился, изредка взглядывая своими блестящими, черными глазами на Ростова.
– Вам своя фанаберия дорога, извиниться не хочется, – продолжал штаб ротмистр, – а нам, старикам, как мы выросли, да и умереть, Бог даст, приведется в полку, так нам честь полка дорога, и Богданыч это знает. Ох, как дорога, батюшка! А это нехорошо, нехорошо! Там обижайтесь или нет, а я всегда правду матку скажу. Нехорошо!
И штаб ротмистр встал и отвернулся от Ростова.
– Пг"авда, чог"т возьми! – закричал, вскакивая, Денисов. – Ну, Г"остов! Ну!
Ростов, краснея и бледнея, смотрел то на одного, то на другого офицера.
– Нет, господа, нет… вы не думайте… я очень понимаю, вы напрасно обо мне думаете так… я… для меня… я за честь полка.да что? это на деле я покажу, и для меня честь знамени…ну, всё равно, правда, я виноват!.. – Слезы стояли у него в глазах. – Я виноват, кругом виноват!… Ну, что вам еще?…
– Вот это так, граф, – поворачиваясь, крикнул штаб ротмистр, ударяя его большою рукою по плечу.
– Я тебе говог"ю, – закричал Денисов, – он малый славный.
– Так то лучше, граф, – повторил штаб ротмистр, как будто за его признание начиная величать его титулом. – Подите и извинитесь, ваше сиятельство, да с.
– Господа, всё сделаю, никто от меня слова не услышит, – умоляющим голосом проговорил Ростов, – но извиняться не могу, ей Богу, не могу, как хотите! Как я буду извиняться, точно маленький, прощенья просить?
Денисов засмеялся.
– Вам же хуже. Богданыч злопамятен, поплатитесь за упрямство, – сказал Кирстен.
– Ей Богу, не упрямство! Я не могу вам описать, какое чувство, не могу…

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

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

Введение

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

Копируя действия природы, человек создает всё более и более совершенные алгоритмы оптимизации. Для их создание чаще всего служат примеры из природы, например: генетический код или поведение птиц, моделирование миграций рыб или охлождение металла и т.д.

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

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

Для данной работы был выбран метод оптимизации «рой частиц». Алгоритм метода благодаря своей простоте и скорости считается очень перспективным для задач планирования.

1 . Постановка задачи

1.1 Математическая модель

Метод «рой частиц» - наиболее простой метод эволюционного программирования, появившийся в середине 90-х годов, основанный на идеи о возможности решения задач оптимизации с помощью моделирования поведения групп животных. В основу метода положен тот факт, что при формировании стаи птицы стремятся к некоторому центру «притяжения», постепенно замедляя скорость полёта.

Когда стая ищет еду, её представители будут проверять прилегающую область и двигаться вокруг стаи независимо друг от друга. Каждый представитель имеет степень свободы или хаотичности в движении, которая даёт ему возможность найти скопление пищи. Так, рано или поздно, один из них найдет, что-то съедобное, и, будучи частью стаи, сообщит остальным. Остальные также могут тогда приблизиться к источнику пищи, и уже каждый представитель, благодаря степени свободы и хаотичности своего движения может найти новое скопление пищи.

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

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

2 . Реализация алгоритма

2.1Схема работы алгоритма

Схема работы алгоритма выглядит следующим образом:

1. Создаётся исходная «случайная» популяция частиц.

2. Для каждой частицы рассчитывается целевая функция.

3. Лучшая частица с точки зрения целевой функции объявляется «центром притяжения».

4. Векторы скоростей всех частиц устремляются к этому «центру», при этом чем дальше частица находится от него, тем большим ускорением она обладает.

5. Осуществляется расчёт новых координат частиц в пространстве решений.

6. Шаги 2-5 повторяются заданное число раз или пока не выполнится условие остановки.

7. Последний «центр тяжести» объявляется найденным оптимальным решением.

2. 2 Код программы

#include

#include

#include

#include

const int n=200;

const int m=200;

int i, j, k, t=200;

double F (double x)

return pow (pow(x, 3) - 125,2);

{double V[n] [m];

double lower_limit=1, upper_limit=300;

double best_pos[n] [m];

double cel[n] [m]; // массив генотипа

double best_cel=1000; // лучшее глобальное значение

const double C1=0.7, C2=1.2, w=0.93;

double **X=new double*[n];

for (i=0; i

X[i]=new double[m];

srand (time(NULL));

// инициализация положения и скоростей частиц

for (i=0; i

for (j=0; j

X[i] [j]=lower_limit + (upper_limit - lower_limit)*rand()/RAND_MAX;

// Инициалиция генотипом частиц самым худшем

best_pos[i] [j]=1000;

for (k=0; k

// заполнение массива генотипов

for (i=0; i

for (j=0; j

// определение текущего генотипа

cel[i] [j]=F (X[i] [j]);

// сохранение значения лучшего генотипа для каждой частицы

if (cel[i] [j]

best_pos[i] [j]=cel[i] [j];

if (best_pos[i] [j]

best_cel=best_pos[i] [j];

printf («%f\n», x);

// Обновление скоростей частиц и их позиций

for (i=0; i

for (j=0; j

R1 = 1.*rand()/RAND_MAX;

R2 = 1.*rand()/RAND_MAX;

V[i] [j] = w*V[i] [j] + C1*R1*(best_cel - X[i] [j]) + C2*R2*(best_pos[i] [j] - X[i] [j]);

X[i] [j] = X[i] [j] + V[i] [j];

2.3 Блок схема алгоритма

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

3 . Теоретическая оценка трудоемкости алгоритма оптимизации

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

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

1) операцию присваивания ab;

2) операцию индексации массива a[i];

3) арифметические операции *,/,-,+;

4) операции сравнения a < b;

5) логические операции or, and, not.

Цикл for не является элементарной операцией, т.к. может быть представлен в виде;

Таким образом конструкция цикла требует 2*N элементарных операций:

F «цикл» = 2* N + N * f «тело цикла».

Таким образом, для нашей программы получим:

F=9+ // константы

2*200+200*(2*200+(8+6)*200)+ // инициализация положения и скоростей

2*200+200*(2*200+200*(2*200+200*(6+20))+ // заполнение массива генотипа и лучших значений

2*200+200*(2*200+200*(4+4+10+2+16)) // обновление скоростей и позиций

В результате теоретического вычисления трудоемкость данной программы составила F= 528800809 элементарных операций.

Заключение

программа алгоритм моделирование

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

Дальнейшее развитие подобных алгоритмов является ключём к новым технологиям оптимизации и развития в целом.

Список использованных источников

1. Ульянов М.В., Шептунов М.В. Математическая логика и теория алгоритмов, часть 2: Теория алгоритмов. - М.: МГАПИ, 2003. - 80 с.

2. Конспект лекций по дисциплине «Математическая логика и теория алгоритмов».

3. Global Optimization Algorithms - Theory and Application.

4. http://ru.wikipedia.org

Размещено на Allbest.ru

Подобные документы

    Особенности задач линейного программирования. Симплексный метод решения задач линейного программирования. Обоснование выбора языка, инструментария программирования, перечень идентификаторов и блок-схема алгоритма. Логическая схема работы программы.

    дипломная работа , добавлен 13.08.2011

    Рзработка библиотеки, которая позволит моделировать динамику частиц в трехмерной графики. Выбор средств и методов разработки. Варианты моделирования систем частиц. Моделирование на вершинном шейдере. Диаграммы класса Particle System и PSBehavior.

    курсовая работа , добавлен 07.02.2016

    Основные аналитические соотношения. Блок схемы и алгоритм решения задачи. Проверка работоспособности алгоритма вручную. Таблица идентификации переменных. Формы входной и выходной печати. Разработка и отладка программы. Инструкция для работы с программой.

    курсовая работа , добавлен 13.02.2012

    Понятие линейного программирования и оптимизации. Основы работы в системе MathCAD. Интерфейс пользователя, входной язык и тип данных. Этапы компьютерного математического моделирования. Пример решения оптимизационной задачи средствами программы MathCAD.

    курсовая работа , добавлен 16.10.2011

    Создание программы в среде программирования MatLab для решения задачи одномерной оптимизации (нахождение минимума и максимума заданных функций) методом золотого сечения, построение блок-схемы алгоритма и графическое изображение исследованных функций.

    реферат , добавлен 14.06.2010

    Система программирования Delphi, ее характеристика. Основные требования к обучающей программе. Составление блок-схемы алгоритма программы "Математика. 1 класс". Виды задач для решения в обучающей программе. Описание работы системы, инструкция к ней.

    курсовая работа , добавлен 17.06.2015

    Оптимизация решения задачи с помощью алгоритма отжига. Анализ теории оптимизации как целевой функции. Метод градиентного спуска. Переменные и описание алгоритма отжига. Представление задачи коммивояжера через граф. Сведение задачи к переменным и решение.

    курсовая работа , добавлен 21.05.2015

    Построение математической модели движения заряженных частиц, реализация на алгоритмическом языке с помощью ЭВМ. Описание предметной области. Имитация взаимодействия двух разноименно заряженных частиц. Результаты работы программы, руководство пользователя.

    курсовая работа , добавлен 26.02.2015

    Преобразование матрицы системы линейных алгебраических уравнений (СЛАУ) с помощью алгоритма Гаусса. Решение задачи методом простой итерации. Создание блок-схемы и текста программы для решения СЛАУ, реализованной на языке программирования Turbo Pascal.

    курсовая работа , добавлен 15.06.2013

    Паскаль как язык профессионального программирования, который назван в честь французского математика и философа Блеза Паскаля, история его разработки и функциональные особенности. Задача с использованием двумерного массива, составление блок-схемы решения.