У 1995 році Джеймс Кеннеді (James Kennedy) і Рассел Еберхарт (Russel Eberhart) запропонували метод для оптимізації безперервних нелінійних функцій, який назвали алгоритмом рою частинок. Натхненням для них послужила імітаційна модель Рейнольдса, а також робота Хеппнера (Heppner) і Гренадера (Grenader) на схожу тему. Кеннеді і Еберхарт відзначили, що обидві моделі засновані на управлінні дистанціями між птахами - а, отже, синхронність зграї в них є функцією від зусиль, які птиці докладають для збереження оптимальної дистанції.
Розроблений ними алгоритм досить простий і може бути реалізований буквально в декількох десятках рядків коду на будь-якій високорівневій мові програмування. Він моделює багатоагентну систему, де агенти-частинки рухаються до оптимальних рішень, обмінюючись при цьому інформацією з сусідами.
Поточний стан частинки характеризується координатами в просторі рішень (тобто, власне, пов'язаним з ними рішенням), а також вектором швидкості переміщення. Обидва цих параметра вибираються випадковим чином на етапі ініціалізації. Крім того, кожна частка зберігає координати одного з найкращих знайдених їй рішень, а також найкраще з знайдених усіма частинками рішень - цим імітується миттєвий обмін інформацією між птахами.
На кожній ітерації алгоритму напрямок і довжина вектора швидкості кожної з частинок змінюються відповідно до відомостей про знайдених оптимумах:
де v - вектор швидкості частинки (vi- його i-а компонента), a1, a2 - постійні прискорення, pbest - найкраща знайдена часткою точка, gbest - найкраща точка з пройдених усіма частинками системи, x - поточний стан частинки, а функція rnd()t повертає випадкове число від 0 до 1 включно.
Після обчислення напрямку вектора, частка переміщається в точку. У разі необхідності, оновлюються значення кращих точок для кожної частки і для всіх частинок в цілому. Після цього цикл повторюється.
Перейти до розв'язання задачі: