Bài giảng Tính toán tiến hóa - Bài 8: Particle Swarm Optimization - Huỳnh Thị Thanh Bình
Tổng quan
2
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
3
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
4
Các bước của thuật toán PSO:
1. Khởi tạo một bầy gồm N cá thể
2. Đánh giá độ thích nghi của mỗi cá thể trong bầy
3. Cập nhật vị trí tốt nhất (kinh nghiệm) 푃 của mỗi cá thể .
푖
4. Cập nhật vị trí của cá thể tốt nhất 푃 của trong bầy đàn.
푔
5. Cập nhật vận tốc và vị trí của mỗi cá thể theo 푃 và 푃
푖
푔
6. 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.)
5
Biểu thức cập nhật vận tốc :
Thành phần nhận thức
Thành phần xã hội
Quán tính
Hệ số ngẫu nhiên
: hệ số gia tốc
PSO Algorithm (cont.)
6
Biểu thức cập nhật vận tốc :
Quán tính
Thành phận nhận thức
Thành phần xã hội
Hệ số ngẫu nhiên
: hệ số gia tốc
Cập nhật vị trí:
PSO Algorithm – Tham số
7
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)
8
• Khởi tạo 1 bầy đàn với 4 cá thể (t=0)
• Đánh giá độ thích nghi,
• Đánh dấu gbest
3
2.5
gbest
2
1.5
1
0.5
0
0
1
2
3
4
5
Ví dụ thuật toá n PSO (Bước 4)
9
Cập nhât vận tốc của mỗi cá thể (t=1)
3
2.5
gbest
2
1.5
1
0.5
0
0
1
2
3
4
5
Ví dụ thuật toá n PSO (Bước 4 tiếp)
10
Cập nhật vị trí của cá thể sau khi di chuyển (t=2)
3
2.5
gbest
2
1.5
1
0.5
0
0
1
2
3
4
5
Ví dụ thuật toá n PSO (Bước 2+3)
11
Đá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)
3
2.5
gbest
2
1.5
1
0.5
0
0
1
2
3
4
5
Ví dụ thuật toá n PSO (Bước 4)
12
Cập nhật vận tốc cho mỗi cá thể (t=2)
Thành phần nhận thức Thành phần xã hội
Quán tính
3
2.5
2
gbest
Quán tính
Nhận thức
Xã hội
1.5
1
Tổng hợp
0.5
0
0
1
2
3
4
5
Thuật toá n PSO rời rạc
13
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.
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
Vận tốc
Trạng thái trước đó
Biểu thức cập nhật vận tốc:
Binary PSO (cont.)
14
xác định một ngưỡng trong hàm xác xuất và nằm trong
đoạn [0.0, 1.0].
1
Vid
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
Cá c biến thể PSO
15
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
16
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
17
EPSO:
Evolutionary PSO
Incorporates a selection procedure
Self-adapting of parameters
The particle movement is defined as:
Hybrid PSO : EPSO
18
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
19
Hybrid PSO : DEPSO
20
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.
Tải về để xem bản đầy đủ
24 trang
23880
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Tính toán tiến hóa - Bài 8: Particle Swarm Optimization - Huỳnh Thị Thanh Bình", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_tinh_toan_tien_hoa_bai_8_particle_swarm_optimizati.ppt
8. PSO.pdf
