Вивчайте Оптимізація Роїння Частинок

Визначення

Оптимізація роїння частинок (Particle Swarm Optimization, PSO) — це алгоритм, заснований на популяції, біоінспірований алгоритм, який черпає натхнення з колективної поведінки зграї птахів і косяків риб. У PSO використовується рой простих агентів, які називаються частинками. Кожна частинка представляє потенційне розв'язання задачі оптимізації та переміщується простором пошуку, оновлюючи свою позицію та швидкість.

Основні поняття

Рух кожної частинки визначається двома основними факторами:

Особистий найкращий: найкраща відома позиція, яку частинка знайшла до цього часу;
Глобальний найкращий: найкраща відома позиція, яку знайшов увесь рій на будь-якому етапі пошуку.

Ця динаміка дозволяє рою ефективно досліджувати простір рішень, балансуючи між дослідженням (пошук нових областей) та експлуатацією (уточнення відомих хороших областей), оскільки частинки спілкуються та навчаються одна в одної.

Ключові поняття в PSO:

Частинки: агенти, що представляють можливі рішення;
Позиція: поточне розташування частинки у просторі пошуку;
Швидкість: напрямок і швидкість руху частинки;
Особисто найкраща позиція: найкраща позиція, знайдена кожною частинкою;
Глобально найкраща позиція: найкраща позиція, знайдена будь-якою частинкою у рої.

Шляхом ітеративного оновлення позицій і швидкостей на основі цих принципів, PSO дозволяє розв'язувати складні задачі оптимізації гнучко та ефективно.

Приклад: базова реалізація PSO


              123456789101112131415161718192021222324252627282930313233343536373839404142434445
            
import numpy as np

# Objective function: simple 1D quadratic (minimum at x=3)
def objective(x):
    return (x - 3) ** 2 + 2

# PSO parameters
num_particles = 20
num_iterations = 50
w = 0.5  # Inertia coefficient
c1 = 1.5  # Cognitive (personal) coefficient
c2 = 1.5  # Social (global) coefficient

# Initialize particle positions and velocities
positions = np.random.uniform(-10, 10, num_particles)
velocities = np.zeros(num_particles)
personal_best_positions = positions.copy()
personal_best_scores = objective(positions)
global_best_idx = np.argmin(personal_best_scores)
global_best_position = personal_best_positions[global_best_idx]

# PSO loop
for iteration in range(num_iterations):
    # Evaluate current positions
    scores = objective(positions)
    # Update personal bests
    better_mask = scores < personal_best_scores
    personal_best_scores[better_mask] = scores[better_mask]
    personal_best_positions[better_mask] = positions[better_mask]
    # Update global best
    global_best_idx = np.argmin(personal_best_scores)
    global_best_position = personal_best_positions[global_best_idx]
    # Update velocities and positions
    r1 = np.random.rand(num_particles)
    r2 = np.random.rand(num_particles)
    velocities = (
        w * velocities
        + c1 * r1 * (personal_best_positions - positions)
        + c2 * r2 * (global_best_position - positions)
    )
    positions += velocities

print(f"Best position found: {global_best_position:.3f}")
print(f"Objective value: {objective(global_best_position):.3f}")

Покроково: Оновлення позиції та швидкості в PSO

Оцінка кожної частинки: Для кожної частинки обчислити значення цільової функції в її поточній позиції;
Оновлення особистого найкращого: Якщо поточна позиція дає кращий результат, ніж будь-яка попередня, зберегти її як новий особистий найкращий результат;
Оновлення глобального найкращого: Визначити найкращий результат серед усіх особистих найкращих і відповідно оновити глобальну найкращу позицію;
Оновлення швидкості: Для кожної частинки обчислити нову швидкість, використовуючи:
- Інерційний доданок (w * velocity), який спонукає частинку рухатися у поточному напрямку;
- Когнітивний доданок (c1 * r1 * (personal_best - position)), який тягне частинку до її власного найкращого досвіду;
- Соціальний доданок (c2 * r2 * (global_best - position)), який тягне частинку до найкращого результату, знайденого роєм;
Оновлення позиції: Додати нову швидкість до поточної позиції, щоб отримати нове розташування частинки у просторі пошуку.

Частинки повторюють ці кроки задану кількість ітерацій або до досягнення критеріїв збіжності.

Приклад: Візуалізація траєкторій частинок


              123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354
            
import numpy as np
import matplotlib.pyplot as plt

# Objective function: simple 1D quadratic (minimum at x=3)
def objective(x):
    return (x - 3) ** 2 + 2

# PSO parameters
num_particles = 20
num_iterations = 50
w = 0.5  # Inertia coefficient
c1 = 1.5  # Cognitive (personal) coefficient
c2 = 1.5  # Social (global) coefficient

# Re-run the PSO loop, recording particle trajectories
positions = np.random.uniform(-10, 10, num_particles)
velocities = np.zeros(num_particles)
personal_best_positions = positions.copy()
personal_best_scores = objective(positions)
global_best_idx = np.argmin(personal_best_scores)
global_best_position = personal_best_positions[global_best_idx]

trajectories = [positions.copy()]

for iteration in range(num_iterations):
    scores = objective(positions)
    better_mask = scores < personal_best_scores
    personal_best_scores[better_mask] = scores[better_mask]
    personal_best_positions[better_mask] = positions[better_mask]
    global_best_idx = np.argmin(personal_best_scores)
    global_best_position = personal_best_positions[global_best_idx]
    r1 = np.random.rand(num_particles)
    r2 = np.random.rand(num_particles)
    velocities = (
        w * velocities
        + c1 * r1 * (personal_best_positions - positions)
        + c2 * r2 * (global_best_position - positions)
    )
    positions += velocities
    trajectories.append(positions.copy())

trajectories = np.array(trajectories)

# Plot trajectories
plt.figure(figsize=(10, 6))
for i in range(num_particles):
    plt.plot(trajectories[:, i], label=f"Particle {i+1}", alpha=0.5)
plt.axhline(3, color='red', linestyle='--', label='Optimum (x=3)')
plt.title('Particle Trajectories in PSO')
plt.xlabel('Iteration')
plt.ylabel('Position')
plt.legend(bbox_to_anchor=(1.05, 1), loc='upper left', fontsize='small')
plt.tight_layout()
plt.show()

Аналіз параметрів

Вибір параметрів PSO суттєво впливає на поведінку та ефективність алгоритму:

Інерційний коефіцієнт (w): Контролює, яку частину попередньої швидкості зберігає частинка;
- Вищі значення сприяють дослідженню та допомагають частинкам уникати локальних мінімумів;
- Нижчі значення сприяють експлуатації та прискорюють збіжність.
Когнітивний коефіцієнт (c1): Визначає, наскільки сильно частинки тягнуться до власних найкращих позицій;
- Збільшення цього значення стимулює незалежне дослідження та підтримує різноманітність рою.
Соціальний коефіцієнт (c2): Відповідає за притягання до глобальної найкращої позиції;
- Збільшення цього значення прискорює збіжність завдяки колективному навчанню;
- Надто високі значення можуть призвести до передчасної стагнації.

Уважне налаштування цих коефіцієнтів є ключовим для досягнення надійної оптимізації в різних предметних областях. Підбирайте параметри так, щоб збалансувати дослідження та експлуатацію, забезпечуючи ефективний пошук без застрягання або надто швидкої збіжності.

Які твердження щодо оптимізації рою частинок (PSO) є правильними? Оберіть усі, що підходять.

Select the correct answer

Кожна частинка представляє потенційне рішення у просторі пошуку.

Дуже високий соціальний коефіцієнт завжди призводить до кращих результатів оптимізації.

Інерційний член у формулі оновлення швидкості спонукає частинки продовжувати рух у поточному напрямку.

Когнітивний член притягує кожну частинку до глобально найкращої позиції.

Все було зрозуміло?

Дякуємо за ваш відгук!

Секція 3. Розділ 2

Запитати АІ

Запитайте про що завгодно або спробуйте одне із запропонованих запитань, щоб почати наш чат

Suggested prompts:

Can you explain how to choose good values for the PSO parameters?

What happens if I set the inertia or cognitive/social coefficients too high or too low?

Can you give examples of how parameter changes affect the optimization process?

Awesome!

Completion rate improved to 6.25

Свайпніть щоб показати меню