입자 군집 최적화 알고리즘 기본 원리

알고리즘 개요

입자 군집 최적화(Particle Swarm Optimization, PSO)는 새떼의 먹이 탐색 행동을 모방하여 개발된 군집 기반의 탐색 알고리즘입니다. 이 알고리즘은 다차원 공간에서 최적해를 찾기 위해 개별 입자들이 서로 정보를 공유하며 협력하는 방식으로 작동합니다.

알고리즘 전략

입자 군집 알고리즘의 목표는 다차원 공간에서 최적해를 찾는 것입니다. 먼저 모든 입자에 초기 무작위 위치와 초기 무작위 속도를 할당합니다. 그런 다음 각 입자의 속도, 알려진 공간의 최적 전역 위치, 그리고 입자의 최적 위치에 따라 각 입자의 위치를 순차적으로 업데이트합니다. 계산이 진행됨에 따라 반복하면서, 탐색 공간에서 알려진 유리한 위치를 탐색하고 활용함으로써 입자들은 하나 또는 여러 개의 최적점 주변으로 모이게 됩니다.

핵심 공식

입자의 d번째 단계 속도 = 이전 단계 속도의 관성 + 자기 인지 부분 + 사회 인지 부분

v_i^d = w·v_i^d-1 + c₁·r₁·(pbest_i^d - x_i^d) + c₂·r₂·(gbest^d - x_i^d)

입자의 d+1번째 단계 위치 = d번째 단계 위치 + d번째 단계 속도 × 시간

x_i^d+1 = x_i^d + v_i^d

매개변수 분석

• 학습 인자: c₁과 c₂는 각 입자가 p_i와 p_g로 향하는 통계적 가중치를 나타냅니다. 낮은 값은 입자가 목표 영역을 벗어나 탐색할 수 있게 하고, 높은 값은 입자가 갑자기 목표 영역으로 돌진하거나 넘어가게 합니다. 초기 연구에서는 c₁과 c₂를 2로 설정하는 것이 적합하다고 제안했습니다.
• 관성 가중치: 관성 가중치 w는 입자가 이전 속도를 유지하는 능력을 나타냅니다. 큰 관성 가중치는 전역 탐색에 유리하고, 작은 가중치는 지역 탐색에 유리합니다. 일반적으로 w는 0.9~1.2 사이의 값이 적합합니다.

Python 구현

함수 y = 7·cos(5·x) + 4·sin(x)의 [-5, 5] 구간에서 최대값 찾기

import numpy as np
import matplotlib.pyplot as plt

def objective_function(x):
    """목적 함수 정의"""
    return 7 * np.cos(5 * x) + 4 * np.sin(x)

def pso_optimization():
    """입자 군집 최적화 알고리즘 구현"""
    # 알고리즘 매개변수 설정
    num_particles = 15  # 입자 수
    dimensions = 1      # 변수 차원
    max_iter = 50       # 최대 반복 횟수
    c1 = 2.0            # 개별 학습 인자
    c2 = 2.0            # 사회 학습 인자
    w = 0.9             # 관성 가중치
    v_max = 1.2         # 최대 속도
    x_lower = -3        # 변수 하한
    x_upper = 3        # 변수 상한
    
    # 입자 위치와 속도 초기화
    positions = np.random.uniform(x_lower, x_upper, (num_particles, dimensions))
    velocities = np.random.uniform(-v_max, v_max, (num_particles, dimensions))
    
    # 개별 최적 위치와 전역 최적 위치 초기화
    personal_best = positions.copy()
    fitness_values = np.array([objective_function(p) for p in positions])
    global_best_idx = np.argmax(fitness_values)
    global_best = positions[global_best_idx].copy()
    
    # 함수 그래프 그리기
    x_range = np.linspace(-5, 5, 1000)
    y_range = objective_function(x_range)
    plt.figure(figsize=(10, 6))
    plt.plot(x_range, y_range, 'b-', label='목적 함수')
    plt.scatter(positions, fitness_values, color='red', marker='*', s=100, label='입자')
    plt.title('y = 7·cos(5·x) + 4·sin(x)')
    plt.legend()
    
    # 최적화 과정
    best_fitness_history = []
    for iteration in range(max_iter):
        for i in range(num_particles):
            # 속도 업데이트
            r1, r2 = np.random.random(2)
            velocities[i] = (w * velocities[i] + 
                           c1 * r1 * (personal_best[i] - positions[i]) + 
                           c2 * r2 * (global_best - positions[i]))
            
            # 속도 제한 적용
            velocities[i] = np.clip(velocities[i], -v_max, v_max)
            
            # 위치 업데이트
            positions[i] += velocities[i]
            
            # 위치 제한 적용
            positions[i] = np.clip(positions[i], x_lower, x_upper)
            
            # 적합도 계산
            current_fitness = objective_function(positions[i])
            
            # 개별 최적 위치 업데이트
            if current_fitness > fitness_values[i]:
                personal_best[i] = positions[i].copy()
                fitness_values[i] = current_fitness
                
            # 전역 최적 위치 업데이트
            if current_fitness > objective_function(global_best):
                global_best = positions[i].copy()
        
        # 그래프 업데이트
        plt.scatter(positions, fitness_values, color='red', marker='*', s=100)
        best_fitness_history.append(objective_function(global_best))
        plt.pause(0.1)
    
    # 결과 시각화
    plt.figure(figsize=(10, 6))
    plt.plot(best_fitness_history)
    plt.xlabel('반복 횟수')
    plt.ylabel('최적 적합도')
    plt.title('최적화 과정')
    
    print(f"최적 위치: {global_best[0]:.4f}")
    print(f"최적 값: {objective_function(global_best):.4f}")
    
    return global_best, objective_function(global_best)

# 알고리즘 실행
if __name__ == "__main__":
    pso_optimization()
    plt.show()

입자 군집 알고리즘 개선: 선형 감소 관성 가중치

선형 감소 관성 가중치(LDIW)

탐색 초기에는 전역 탐색 능력을 강화하여 해 공간을 넓게 탐색하고 지역 최적해에 갇히는 것을 방지해야 합니다. 탐색 후기에는 지역 탐색 능력을 강화하여 최적해를 정확하게 찾아야 합니다. 이러한 균형을 맞추기 위해 Shi, Y는 선형 감소 관성 가중치를 제안했습니다.

w^d = w_start - (w_start - w_end) × (d/K)

여기서 d는 현재 반복 횟수, K는 총 반복 횟수입니다. 일반적으로 w_start는 0.9, w_end는 0.4로 설정합니다.

개선된 Python 코드

def pso_with_linear_decreasing_weight():
    """선형 감소 관성 가중치를 사용한 PSO 구현"""
    # 알고리즘 매개변수 설정
    num_particles = 15
    dimensions = 1
    max_iter = 50
    c1 = 2.0
    c2 = 2.0
    w_start = 0.9
    w_end = 0.4
    v_max = 1.2
    x_lower = -3
    x_upper = 3
    
    # 입자 위치와 속도 초기화
    positions = np.random.uniform(x_lower, x_upper, (num_particles, dimensions))
    velocities = np.random.uniform(-v_max, v_max, (num_particles, dimensions))
    
    # 개별 최적 위치와 전역 최적 위치 초기화
    personal_best = positions.copy()
    fitness_values = np.array([objective_function(p) for p in positions])
    global_best_idx = np.argmax(fitness_values)
    global_best = positions[global_best_idx].copy()
    
    # 함수 그래프 그리기
    x_range = np.linspace(-5, 5, 1000)
    y_range = objective_function(x_range)
    plt.figure(figsize=(10, 6))
    plt.plot(x_range, y_range, 'b-', label='목적 함수')
    plt.scatter(positions, fitness_values, color='red', marker='*', s=100, label='입자')
    plt.title('선형 감소 관성 가중치를 사용한 PSO')
    plt.legend()
    
    # 최적화 과정
    best_fitness_history = []
    for iteration in range(max_iter):
        # 관성 가중치 동적 업데이트
        w = w_start - (w_start - w_end) * iteration / max_iter
        
        for i in range(num_particles):
            # 속도 업데이트
            r1, r2 = np.random.random(2)
            velocities[i] = (w * velocities[i] + 
                           c1 * r1 * (personal_best[i] - positions[i]) + 
                           c2 * r2 * (global_best - positions[i]))
            
            # 속도 제한 적용
            velocities[i] = np.clip(velocities[i], -v_max, v_max)
            
            # 위치 업데이트
            positions[i] += velocities[i]
            
            # 위치 제한 적용
            positions[i] = np.clip(positions[i], x_lower, x_upper)
            
            # 적합도 계산
            current_fitness = objective_function(positions[i])
            
            # 개별 최적 위치 업데이트
            if current_fitness > fitness_values[i]:
                personal_best[i] = positions[i].copy()
                fitness_values[i] = current_fitness
                
            # 전역 최적 위치 업데이트
            if current_fitness > objective_function(global_best):
                global_best = positions[i].copy()
        
        # 그래프 업데이트
        plt.scatter(positions, fitness_values, color='red', marker='*', s=100)
        best_fitness_history.append(objective_function(global_best))
        plt.pause(0.1)
    
    # 결과 시각화
    plt.figure(figsize=(10, 6))
    plt.plot(best_fitness_history)
    plt.xlabel('반복 횟수')
    plt.ylabel('최적 적합도')
    plt.title('선형 감소 관성 가중치 최적화 과정')
    
    print(f"최적 위치: {global_best[0]:.4f}")
    print(f"최적 값: {objective_function(global_best):.4f}")
    
    return global_best, objective_function(global_best)

# 알고리즘 실행
if __name__ == "__main__":
    pso_with_linear_decreasing_weight()
    plt.show()

입자 군집 알고리즘 개선: 적응형 관성 가중치

적응형 관성 가중치

적응형 관성 가중치는 반복 횟수와 각 입자의 적합도에 따라 동적으로 가중치를 조절합니다. 이 방법은 전역 탐색과 지역 탐색 간의 균형을 더 잘 맞출 수 있습니다.

최대값 문제의 경우:

w = w_min + (w_max - w_min) × (f_max - f_i) / (f_max - f_avg)

개선된 Python 코드

def pso_with_adaptive_weight():
    """적응형 관성 가중치를 사용한 PSO 구현"""
    # 알고리즘 매개변수 설정
    num_particles = 15
    dimensions = 1
    max_iter = 50
    c1 = 2.0
    c2 = 2.0
    w_max = 0.9
    w_min = 0.4
    v_max = 1.2
    x_lower = -3
    x_upper = 3
    
    # 입자 위치와 속도 초기화
    positions = np.random.uniform(x_lower, x_upper, (num_particles, dimensions))
    velocities = np.random.uniform(-v_max, v_max, (num_particles, dimensions))
    
    # 개별 최적 위치와 전역 최적 위치 초기화
    personal_best = positions.copy()
    fitness_values = np.array([objective_function(p) for p in positions])
    global_best_idx = np.argmax(fitness_values)
    global_best = positions[global_best_idx].copy()
    
    # 함수 그래프 그리기
    x_range = np.linspace(-5, 5, 1000)
    y_range = objective_function(x_range)
    plt.figure(figsize=(10, 6))
    plt.plot(x_range, y_range, 'b-', label='목적 함수')
    plt.scatter(positions, fitness_values, color='red', marker='*', s=100, label='입자')
    plt.title('적응형 관성 가중치를 사용한 PSO')
    plt.legend()
    
    # 최적화 과정
    best_fitness_history = []
    for iteration in range(max_iter):
        # 적응형 관성 가중치 계산
        f_avg = np.mean(fitness_values)
        f_max = np.max(fitness_values)
        
        for i in range(num_particles):
            f_i = fitness_values[i]
            if f_max != f_avg:
                w = w_min + (w_max - w_min) * (f_max - f_i) / (f_max - f_avg)
            else:
                w = w_max
            
            # 속도 업데이트
            r1, r2 = np.random.random(2)
            velocities[i] = (w * velocities[i] + 
                           c1 * r1 * (personal_best[i] - positions[i]) + 
                           c2 * r2 * (global_best - positions[i]))
            
            # 속도 제한 적용
            velocities[i] = np.clip(velocities[i], -v_max, v_max)
            
            # 위치 업데이트
            positions[i] += velocities[i]
            
            # 위치 제한 적용
            positions[i] = np.clip(positions[i], x_lower, x_upper)
            
            # 적합도 계산
            current_fitness = objective_function(positions[i])
            
            # 개별 최적 위치 업데이트
            if current_fitness > fitness_values[i]:
                personal_best[i] = positions[i].copy()
                fitness_values[i] = current_fitness
                
            # 전역 최적 위치 업데이트
            if current_fitness > objective_function(global_best):
                global_best = positions[i].copy()
        
        # 그래프 업데이트
        plt.scatter(positions, fitness_values, color='red', marker='*', s=100)
        best_fitness_history.append(objective_function(global_best))
        plt.pause(0.1)
    
    # 결과 시각화
    plt.figure(figsize=(10, 6))
    plt.plot(best_fitness_history)
    plt.xlabel('반복 횟수')
    plt.ylabel('최적 적합도')
    plt.title('적응형 관성 가중치 최적화 과정')
    
    print(f"최적 위치: {global_best[0]:.4f}")
    print(f"최적 값: {objective_function(global_best):.4f}")
    
    return global_best, objective_function(global_best)

# 알고리즘 실행
if __name__ == "__main__":
    pso_with_adaptive_weight()
    plt.show()

입자 군집 알고리즘 개선: 압축 인자법

압축 인자(Constriction Factor)

압축 인자법은 속도 업데이트 공식에 압축 인자를 도입하여 알고리즘의 수렴성을 보장하고 속도 제한을 제거할 수 있습니다.

χ = 2 / |2 - φ - √(φ² - 4φ)|

여기서 φ = c₁ + c₂이고, 일반적으로 c₁ = c₂ = 2.05로 설정합니다.

개선된 Python 코드

def pso_with_constriction_factor():
    """압축 인자를 사용한 PSO 구현"""
    # 알고리즘 매개변수 설정
    num_particles = 15
    dimensions = 1
    max_iter = 50
    c1 = 2.05
    c2 = 2.05
    w = 0.9
    v_max = 1.2
    x_lower = -3
    x_upper = 3
    
    # 압축 인자 계산
    phi = c1 + c2
    chi = 2.0 / abs(2.0 - phi - np.sqrt(phi**2 - 4.0*phi))
    
    # 입자 위치와 속도 초기화
    positions = np.random.uniform(x_lower, x_upper, (num_particles, dimensions))
    velocities = np.random.uniform(-v_max, v_max, (num_particles, dimensions))
    
    # 개별 최적 위치와 전역 최적 위치 초기화
    personal_best = positions.copy()
    fitness_values = np.array([objective_function(p) for p in positions])
    global_best_idx = np.argmax(fitness_values)
    global_best = positions[global_best_idx].copy()
    
    # 함수 그래프 그리기
    x_range = np.linspace(-5, 5, 1000)
    y_range = objective_function(x_range)
    plt.figure(figsize=(10, 6))
    plt.plot(x_range, y_range, 'b-', label='목적 함수')
    plt.scatter(positions, fitness_values, color='red', marker='*', s=100, label='입자')
    plt.title('압축 인자를 사용한 PSO')
    plt.legend()
    
    # 최적화 과정
    best_fitness_history = []
    for iteration in range(max_iter):
        for i in range(num_particles):
            # 속도 업데이트 (압축 인자 적용)
            r1, r2 = np.random.random(2)
            velocities[i] = chi * (w * velocities[i] + 
                                c1 * r1 * (personal_best[i] - positions[i]) + 
                                c2 * r2 * (global_best - positions[i]))
            
            # 위치 업데이트
            positions[i] += velocities[i]
            
            # 위치 제한 적용
            positions[i] = np.clip(positions[i], x_lower, x_upper)
            
            # 적합도 계산
            current_fitness = objective_function(positions[i])
            
            # 개별 최적 위치 업데이트
            if current_fitness > fitness_values[i]:
                personal_best[i] = positions[i].copy()
                fitness_values[i] = current_fitness
                
            # 전역 최적 위치 업데이트
            if current_fitness > objective_function(global_best):
                global_best = positions[i].copy()
        
        # 그래프 업데이트
        plt.scatter(positions, fitness_values, color='red', marker='*', s=100)
        best_fitness_history.append(objective_function(global_best))
        plt.pause(0.1)
    
    # 결과 시각화
    plt.figure(figsize=(10, 6))
    plt.plot(best_fitness_history)
    plt.xlabel('반복 횟수')
    plt.ylabel('최적 적합도')
    plt.title('압축 인자 최적화 과정')
    
    print(f"최적 위치: {global_best[0]:.4f}")
    print(f"최적 값: {objective_function(global_best):.4f}")
    
    return global_best, objective_function(global_best)

# 알고리즘 실행
if __name__ == "__main__":
    pso_with_constriction_factor()
    plt.show()

입자 군집 알고리즘 개선: 자동 반복 종료

자동 반복 종료 전략

입자가 최적 위치를 찾은 후에도 반복을 계속하면 계산 시간만 낭비됩니다. 따라서 적합도 변화량을 기준으로 자동으로 반복을 종료하는 전략을 도입할 수 있습니다.

개선된 Python 코드

def pso_with_early_stopping():
    """자동 반복 종료를 포함한 PSO 구현"""
    # 알고리즘 매개변수 설정
    num_particles = 15
    dimensions = 1
    max_iter = 100
    c1 = 2.0
    c2 = 2.0
    w = 0.9
    v_max = 1.2
    x_lower = -3
    x_upper = 3
    tolerance = 1e-2  # 적합도 변화량 허용치
    max_no_improvement = 30  # 개선 없을 시 최대 반복 횟수
    
    # 입자 위치와 속도 초기화
    positions = np.random.uniform(x_lower, x_upper, (num_particles, dimensions))
    velocities = np.random.uniform(-v_max, v_max, (num_particles, dimensions))
    
    # 개별 최적 위치와 전역 최적 위치 초기화
    personal_best = positions.copy()
    fitness_values = np.array([objective_function(p) for p in positions])
    global_best_idx = np.argmax(fitness_values)
    global_best = positions[global_best_idx].copy()
    
    # 함수 그래프 그리기
    x_range = np.linspace(-5, 5, 1000)
    y_range = objective_function(x_range)
    plt.figure(figsize=(10, 6))
    plt.plot(x_range, y_range, 'b-', label='목적 함수')
    plt.scatter(positions, fitness_values, color='red', marker='*', s=100, label='입자')
    plt.title('자동 반복 종료를 포함한 PSO')
    plt.legend()
    
    # 최적화 과정
    best_fitness_history = []
    no_improvement_count = 0
    previous_best_fitness = -np.inf
    
    for iteration in range(max_iter):
        current_best_fitness = -np.inf
        
        for i in range(num_particles):
            # 속도 업데이트
            r1, r2 = np.random.random(2)
            velocities[i] = (w * velocities[i] + 
                           c1 * r1 * (personal_best[i] - positions[i]) + 
                           c2 * r2 * (global_best - positions[i]))
            
            # 속도 제한 적용
            velocities[i] = np.clip(velocities[i], -v_max, v_max)
            
            # 위치 업데이트
            positions[i] += velocities[i]
            
            # 위치 제한 적용
            positions[i] = np.clip(positions[i], x_lower, x_upper)
            
            # 적합도 계산
            current_fitness = objective_function(positions[i])
            current_best_fitness = max(current_best_fitness, current_fitness)
            
            # 개별 최적 위치 업데이트
            if current_fitness > fitness_values[i]:
                personal_best[i] = positions[i].copy()
                fitness_values[i] = current_fitness
                
            # 전역 최적 위치 업데이트
            if current_fitness > objective_function(global_best):
                global_best = positions[i].copy()
        
        # 최적 적합도 기록
        best_fitness_history.append(objective_function(global_best))
        
        # 개선 여부 확인
        if abs(current_best_fitness - previous_best_fitness) < tolerance:
            no_improvement_count += 1
        else:
            no_improvement_count = 0
        
        # 조기 종료 조건 확인
        if no_improvement_count >= max_no_improvement:
            print(f"조기 종료: {iteration+1}번째 반복에서 개선 없음")
            break
        
        previous_best_fitness = current_best_fitness
        
        # 그래프 업데이트
        plt.scatter(positions, fitness_values, color='red', marker='*', s=100)
        plt.pause(0.1)
    
    # 결과 시각화
    plt.figure(figsize=(10, 6))
    plt.plot(best_fitness_history)
    plt.xlabel('반복 횟수')
    plt.ylabel('최적 적합도')
    plt.title('자동 반복 종료 최적화 과정')
    
    print(f"최적 위치: {global_best[0]:.4f}")
    print(f"최적 값: {objective_function(global_best):.4f}")
    
    return global_best, objective_function(global_best)

# 알고리즘 실행
if __name__ == "__main__":
    pso_with_early_stopping()
    plt.show()