Bài giảng Tính toán tiến hóa - Chương 9: Particle Swarm Optimization

Particle Swarm Optimization (PSO) Tổng quan Particle Swarm Optimization: Đ ư ợc giới thiệu bởi Kennedy & Eberhart 1995 Lấy cảm hứng từ các hành vi xã hội của bầy chim và đàn cá Thuộc lớp các thuật toán tối ư u sử dụng Trí thông minh bầy đàn Thuật toán tối ư u dựa trên quần thể Các thành phần của thuật toán PSO Swarm (bầy) : Tập các cá thể (S) Particle (cá thể): ứng cử viên lời giải của bài toán Vị trí, Vận tốc , Vị trí tốt nhất đạt được của cá thể trong quá khứ : Cá thể tốt nhất trong bầy đàn: PSO Algorithm Các b ư ớc của thuật toán PSO: Khởi tạo một bầy gồm N cá thể Đánh giá độ thích nghi của mỗi cá thể trong bầy Cập nhật vị trí tốt nhất (kinh nghiệm) của mỗi cá thể . Cập nhật vị trí của cá thể tốt nhất của trong bầy đàn. Cập nhật vận tốc và vị trí của mỗi cá thể theo và Quay lại b ư ớc 2, và lặp cho đến khi thỏa mãn điều kiện dừng. PSO Algorithm (cont.) Biểu thức cập nhật vận tốc : Hệ số ngẫu nhiên : hệ số gia tốc Quán tính Thành phần nhận thức Thành phần xã hội PSO Algorithm (cont.) Biểu thức cập nhật vận tốc : Hệ số ngẫu nhiên : hệ số gia tốc Cập nhật vị trí: Quán tính Thành phận nhận thức Thành phần xã hội PSO Algorithm – Tham số Hệ số gia tốc Giá trị quá nhỏ làm hạn chế bước nhảy của các cá thể trong bầy đàn=> hội tụ chậm Giá trị quá lớn : không hội tụ Thông thường Giá trị vận tốc tối đa Giá trị vận tốc tối đa của một cá thể ở chiều thứ d trong không gian: Ví dụ thuật toán PSO (Bước 1 + 2 +3) Khởi tạo 1 bầy đàn với 4 cá thể (t=0) Đánh giá độ thích nghi, Đánh dấu gbest gbest Ví dụ thuật toán PSO (Bước 4) Cập nhât vận tốc của mỗi cá thể (t=1) gbest Ví dụ thuật toán PSO (B ư ớc 4 tiếp) Cập nhật vị trí của cá thể sau khi di chuyển (t=2) gbest Ví dụ thuật toán PSO (B ư ớc 2+3) Đánh giá độ thích nghi vàCập nhật vị trí tốt nhất của mỗi cá thể và vị trí tốt nhất toàn cục (t=2) gbest Ví dụ thuật toán PSO (B ư ớc 4) gbest Cập nhật vận tốc cho mỗi cá thể (t=2) Quán tính Nhận thức Xã hội Tổng hợp Quán tính Thành phần nhận thức Thành phần xã hội Thuật toán PSO rời rạc Binary PSO: Đ ư ợc giới thiệu bởi kennedy and Eberhart. Mỗi cá thể (particle) là một biểu diễn nhị phân 0-1. Biểu thức cập nhật vận tốc: Trạng thái tr ư ớc đó Vận tốc Vị trí tốt nhất tr ư ớc đó của cá thể đạt đ ư ợc Vị trí tốt nhất của cá thể tốt nhất trong cả bầy đàn Binary PSO (cont.) xác định một ng ư ỡng trong hàm xác xuất và nằm trong đoạn [0.0, 1.0]. Trạng thái của chiều thứ d trong biểu diễn của cá thể id ở thế hệ thứ t đ ư ợc xác định nh ư sau: Với là một số ngẫu nhiên với phân phối đều V id 1 Các biến thể PSO Hybrid PSO Incorporate the capabilities of other evolutionary computation techniques. Adaptive PSO Adaptation of PSO parameters for a better performance. PSO in complex environments Multiobjective or constrained optimization problems or tracking dynamic systems. Other variants variations to the original formulation to improve its performance. Hybrid PSO GA-PSO: combines the advantages of swarm intelligence and a natural selection mechanism. jump from one area to another by the selection mechanism  accelerating the convergence speed. capability of “breeding”. replacing agent positions with low fitness values, with those with high fitness, according to a selection rate Hybrid PSO EPSO: Evolutionary PSO Incorporates a selection procedure Self-adapting of parameters The particle movement is defined as: Hybrid PSO : EPSO Mutation of weights and global best: Learning parameters can be either fixed or dynamically changing as strategic parameters. Survival Selection: Stochastic tournament. Hybrid PSO : EPSO Hybrid PSO : DEPSO Hybrid of Differential Evolution and PSO. A DE operator applied to the particle’s best position to eliminate the particles falling into local minima. Alternation: Original PSO algorithm at the odd iterations. DE operator at the even iterations. Hybrid PSO : DEPSO DE mutation on particle’s best positions: where k is a random integer value within [1,n] which ensures the mutation in at least one dimension. Trial point: For each dth dimention: Hybrid PSO : DEPSO Applications Convenience of realization, properties of low constraint on the continuity of objective function and joint of search space, and ability of adapting to dynamic environment, make PSO be applied in more and more fields. Some PSO applications: Electronics and electromagnetic Signal, Image and video processing Neural networks Communication networks Thanks for your attention