CHƯƠNG 3: THUẬT TOÁN DIFFERENTIAL EVOLUTION
3.3 Quá trình tối ưu hóa của DE
Bước đầu tiên trong quá trình tối ưu hóa của DE là tạo ra một quần thể ban đầu bằng cách chỉ định các giá trị ngẫu nhiên cho từng tham số của mỗi cá thể trong quần thể. Các giá trị này phải nằm trong miền khả thi được chỉ định và có thể được tạo theo công thức:
X (0) =min + n j ( X max − X min ) ,i 1,..., N P ; j 1,..., D
(3.2)
X min và X max phải thấp hơn và cao hơn tương ứng với miền tham số thứ j và nj là số ngẫu nhiên được sắp xếp tương đồng trong khoảng [0 , 1] được tái lập lại ứng với mỗi giá trị của j.
Sau khi quần thể được khởi tạo, nó tiến triển qua tiến trình đột biến, lai ghép và chọn lọc. Tiến trình đột biến đảm nhận việc giới thiệu các tham số mới vô trong quần thể. Để làm được như vậy, tiến trình đột biến tạo ra các vector bằng
j jX j j j( = == ( j,i ( = p ,i 1,..., N(G ) = X P1 N(G,..., P)
cách xáo trộn vector được lựa chọn ngẫu nhiên (Xa) với một vector sai phân từ 2 vector khác được lựa chọn ngẫu nhiên (Xb và Xc). Tất cả các vector này phải khác nhau, để thỏa mãn điều kiện này, yêu cầu quần thể cần có ít nhất 4 cá thể. Để điều khiển việc xáo trộn và cải thiện độ hội tụ, người sử dụng đặt cho vector sai phân một tỷ lệ xác định không đổi nằm trong khoảng [0 , 1.2]. Hằng số này thông thường được gọi là hằng số tỷ lệ (F).
X '(G ) = (G ) + F(X (G ) − X (G ) ),i 1,..., N P
(3.3)
Xa, Xb, Xc được chọn ngẫu nhiên ∈{1,…,NP} và a ≠ b ≠ c ≠ i. Xa, Xb và Xc
được tái lập lại từ mỗi vector cha, F là hằng số tỷ lệ.
Hình 3.1 Tiến trình Đột Biến (Mutation Operator)
Tiến trình đột biến tạo ra các vector thử nghiệm để sử dụng trong tiến trình chọn lọc. Vector thử nghiệm được kết hợp thành từ vector đột biến và vector cha (vector mục tiêu). Ứng với mỗi tham số, giá trị ngẫu nhiên dựa trên sự phân loại nhị thức được tạo ra trong miền [0 , 1] và được đối chiếu với hằng số xác định bởi người sử dụng được xem như hằng số lai ghép. Nếu giá trị của số ngẫu nhiên ít hơn hoặc bằng giá trị hằng số lai ghép thì tham số sẽ lấy từ vector đột biến hoặc ngược lại sẽ lấy từ vector cha.
Hình 3.2 Tiến trình Lai Ghép (Crossover Operator)
Tiến trình lai ghép duy trì tính đa dạng trong quần thể, ngăn ngừa hội tụ tối thiểu cục bộ. Hằng số lai ghép CR phải được đặt trong miền [0 , 1]. Hằng số lai ghép bằng 1 có nghĩa là vector thử nghiệm sẽ bao gồm toàn bộ các tham số của vector đột biến. Hằng số lai ghép gần bằng 0 dẫn tới kết quả nhiều khả năng sẽ có thêm các tham số từ vector mục tiêu trong vector thử nghiệm. Tham số được chọn ngẫu nhiên từ vector đột biến phải luôn được chọn để đảm bảo vector thử nghiệm có ít nhất một tham số từ vector đột biến thậm chí nếu hằng số lai ghép được đặt bằng 0.
"(G )j,i j,i
(3.4)
q là thông số được chọn ngẫu nhiên ∈{1,…,D} để đảm bảo vector thử nghiệm có ít nhất một tham số từ vector đột biến, n’j là số ngẫu nhiên được phân phối đồng đều trong [0 , 1) được tái lập lại ứng với mỗi giá trị của j. X Gj,i là vector cha, X 'Gj,i là vector đột biến và X ''G là vector thử nghiệm.
Tiến trình chọn lọc lựa chọn các vector sẽ bao gồm trong quần thể ở thế hệ kế tiếp. Tiến trình này đối chiếu tính tương thích của vector thử nghiệm với vector mục tiêu tương ứng và lựa chọn ra một vector biểu hiện tốt hơn. Tiến trình chọn
X '(G ) ⇔ n 'j < CR hay j =
lọc được lặp lại ứng với mỗi cặp vector mục tiêu/ vector thử nghiệm cho đến khi quần thể ứng với thế hệ kế được hình thành.
i
i i
(3.5)
Một số phương thức có thể được sử dụng trong DE để tạo ra các vector tham số mới. Các phương thức này khác ở cách thực hiện việc xáo trộn, có thể được biểu thị bằng DE/x/y/z, x chỉ định dạng xáo trộn, y biểu thị số cặp vector được sử dụng trong quá trình xáo trộn và z là lược đồ lai ghép được sử dụng trong quá trình lai ghép lại. Dạng xáo trộn x có thể được lựa chọn để tạo ra các quần thể mới bằng cách xáo trộn vector được chọn lựa ngẫu nhiên từ quần thể. Việc xáo trộn này có cả một hoặc hai cặp vector (y) trong khi việc lai ghép (z) có thể được sử dụng dựa trên sự phân phối nhị thức hoặc số mũ.
Qua thử nghiệm, giải pháp DE tốt nhất cho tối ưu hóa toàn diện là
DE/best/2/bin. Phương thức này làm xáo trộn giải pháp tốt nhất tìm được với hai vector sai phân dựa trên lưu đồ lai ghép phân phối nhị thức. Giải pháp cơ bản là DE/rand/1/bin vẫn tốt cho việc tìm kiếm tối ưu toàn diện, trừ việc biểu hiện tỷ lệ hội tụ thấp.
' G )
G ) G G G G )
) , i = 1,..., N P (3.6) Xa, Xb, Xc và Xd là các vector được lựa chọn ngẫu nhiên ∈{1,…,NP} và a ≠ b ≠ c ≠ i. Xa, Xb, Xc và Xd được tái lập lại ứng với mỗi vector cha. Xbest là giải pháp tối ưu nhất tìm được.