Omarine Schoolsheet 2016 2.0 – Thuật giải di truyền(phần 2)

Posted by: Tuyen Pham Thanh 4 years, 2 months ago

(0 comments)

Xác suất đột biến heuristic thích nghi

Xác suất đột biến heuristic thích nghi là một phát triển lý thuyết của chương trình. Phương pháp này cũng dùng để tối ưu chiến lược tiến hóa nhưng dành cho ràng buộc thuộc loại khó.

Đối với bài toán có ràng buộc phức tạp chúng ta không thể loại bỏ các cá thể không thỏa mãn ràng buộc, thay vào đó là chỉ thưởng phạt các vi phạm. Điều này hoàn toàn khác với phương pháp thỏa mãn ràng buộc cổ điển(Constraint satisfaction method) và các chiến lược tiến hóa nghiêm khắc khác. Bài toán có ràng buộc trở thành bài toán không ràng buộc đa mục tiêu.

Xác suất động tính theo số thế hệ như trước là không đạt yêu cầu vì số thế hệ khác nhau xa đối với các bài toán khác nhau, cũng không thể dùng chung cho tất cả các cá thể. Hàm xác suất phải áp dụng cho từng cá thể và đối với từng ràng buộc và phụ thuộc vào số vi phạm ràng buộc hay độ thích nghi của cá thể.

Gọi s là số vi phạm cần xử lý của một ràng buộc trong một lần thi hành toán tử đột biến heuristic, t là số vi phạm của ràng buộc đó, a là tổng số vi phạm của tất cả các ràng buộc. Nếu ràng buộc đang xét bị vi phạm càng nhiều hơn các ràng buộc khác, nói cách khác tỉ số t/a càng lớn thì số vi phạm cần xử lý s càng lớn. Tương tự nếu số vi phạm ràng buộc t càng lớn thì số vi phạm cần xử lý s càng lớn. Như vậy s tỉ lệ với lũy thừa của t/a, và tỉ lệ với lũy thừa của t:

k là hệ số tỉ lệ, α và β là các hằng số

Xác suất đột biến

Mục đích của chúng ta là muốn tìm xác suất đột biến để thi hành. Xử lý s vi phạm trong số t vi phạm, vậy xác suất sẽ là

Từ (1) và (2) suy ra

Chương trình sử dụng α = 1 và β = 0.1, công thức (3) trở thành

Hệ số tỉ lệ k là tham số của hệ thống. Tham số này thay đổi được và đặc trưng cho tốc độ đột biến của hệ thống, viết gọn là tốc độ đột biến. Tốc độ đột biến được giữ trong một biến là speed. Công thức (4) viết theo ngôn ngữ C như sau:

p = speed * pow(t, 0.1) / a;

Tốc độ đột biến speed là tham số mà bạn nhìn thấy trên cửa sổ tiến độ của chương trình.

Đột biến tốc độ đột biến theo tính chất của không gian lồi

speed = αLEFT_s + (1 – α)RIGHT_s

LEFT_s và RIGHT_s là biên trái và biên phải của miền của tốc độ đột biến speed

α là một số ngẫu nhiên từ 0 đến 1

Xác suất đột biến ngẫu nhiên tương quan yếu

p = βLEFT_p + (1 – β)RIGHT_p

LEFT_p và RIGHT_p là biên trái và biên phải của miền của xác suất đột biến ngẫu nhiên p

β là một số ngẫu nhiên từ 0 đến 1

Khi tốc độ đột biến cần tăng lên nghĩa là hệ thống đang tĩnh, như vậy xác suất đột biến ngẫu nhiên cũng cần tăng theo, tương quan yếu với nó

P_n = p[αLEFT_r + (1 – α)RIGHT_r]

LEFT_r và RIGHT_r là biên trái và biên phải của miền tỉ lệ, p_n là xác suất mới

Ánh xạ co

Chương trình sử dụng tính chất của ánh xạ co để điều khiển hội tụ. Thuật giải sẽ hội tụ về tối ưu toàn cục nếu được cải thiện. Chương trình sử dụng khoảng cách thế hệ là 200. Nếu sau 200 thế hệ độ thích nghi trung bình của quần thể không tăng lên thì thế hệ sẽ được khởi tạo lại từ một quần thể được lưu giữ trước đó. Số thế hệ lùi về điểm xuất phát và biến đếm bước thất bại tăng lên 1. Biến đếm này là tham số nFailed mà bạn nhìn thấy trên cửa sổ tiến độ của chương trình. Các toán tử di truyền được thi hành lại. Bộ số ngẫu nhiên hoạt động sẽ làm cho kết quả lần sau khác với lần trước. Nếu ba lần thất bại liên tiếp thì tốc độ đột biến speed sẽ được điều chỉnh ngẫu nhiên trong một dải xác định như đã trình bày bên trên

Các quần thể con xử lý đa mục tiêu

Để tăng tính đa dạng quần thể được chia thành các quần thể con với kích thước theo tỉ lệ, mỗi quần thể con phụ trách một mục tiêu với một toán tử đột biến heuristic tương ứng. Riêng về lai tạo lại được thực hiện ngang qua biên giới của các quần thể con. Như vậy các quần thể con độc lập nhau nhưng vẫn trao đổi thông tin với nhau. Để điều hòa các quần thể con qua các thế hệ, chương trình chọn các cá thể vào các quần thể con một cách ngẫu nhiên.

Xử lý từng nhóm ràng buộc

Nếu xử lý cùng lúc tất cả các ràng buộc thì mỗi ràng buộc phải có một(hoặc một vài) hệ số. Nhưng việc xác định được bộ hệ số này lại phát sinh vấn đề của một bài toán tối ưu khác. Cách tốt hơn là chia thành các vòng xử lý.

Có 4 vòng xử lý được hiển thị trên cửa sổ tiến độ, mỗi vòng xử lý một nhóm ràng buộc. Việc phân chia các vòng xử lý có lợi lớn là các vòng xử lý trao đổi thông tin với nhau nhờ máy học.

• ← Chúng tôi chia ruộng hay ruộng chia chúng tôi?
• Omarine Schoolsheet 2016 2.0 – Thuật giải di truyền →