tailieunhanh - Bài giảng Tính toán tiến hóa: Bài 6 - TS. Huỳnh Thị Thanh Bình

Bài giảng "Tính toán tiến hóa: Bài 6 - Differential Evolution (DE)" được biên soạn với các nội dung chính sau: Giải thuật tiến hóa sai phân; Sơ đồ của DE; Các biến thể của DE; Hiệu chỉnh tham số trong DE. Mời các bạn cùng tham khảo bài giảng! | Differential Evolution DE Huỳnh Thị Thanh Bình Email binhht@ Tổng quan 2 Giải thuật tiến hóa sai phân Differential Evolution - DE Thuật toán tối ưu ngẫu nhiên dựa trên quần thể Được giới thiệu bởi Storn và Price vào năm 1996 Thuộc lớp giải thuật tiến hóa Xử lý các bài toán tối ưu tham số thực tìm cực trị hàm đa biến phi tuyến không khả vi Các dạng bài toán mà DE giải quyết Hàm mục tiêu Mục tiêu bài toán tìm giá trị x sao cho Sơ đồ của DE 3 Đột Lai Chọn Khởi tạo biến ghép lọc Mô hình thuật toán 4 Khởi tạo 5 Giả sử cần tối ưu tham số Tham số thứ trong khoảng giá trị Kích thước quần thể Mỗi cá thể được biểu diễn bằng một vector D chiều Cá thể thứ i Đột biến 6 Mỗi cá thể trong DE đều tham gia vào quá trình đột biến lai ghép chọn lọc Quá trình đột biến được thực hiện trước khi lai ghép Với mỗi cá thể ta chọn ngẫu nhiên 3 cá thể khác nhau Toán tử đột biến được thực hiện bằng cách thêm sự chênh lệch giữa 2 cá thể vào cá thể thứ 3 F là hằng số để scale chênh lệnh là vector đột biến Lai ghép 7 Cá thể con được sinh ra bằng cách lai ghép cá thể và vector đột biến Toán tử lai ghép sử dụng lai ghép nhị thức Chọn ngẫu nhiên một số nguyên Sinh ra 1 con Chọn lọc 8 Cá thể con sinh ra được so sánh với cá thể cha của chúng Nếu độ thích nghi của lớn hơn thì cá thể con sẽ thay thế cá thể cha trong thế hệ tiếp theo Các biến thể của DE 9 Khác nhau ở cách tính vector đột biến Adaptive DE rand 1 DE rand 2 DE best 1 DE best 2 DE target-to-best 1 Hiệu chỉnh tham số trong DE 10 Kích thước quần thể N F CR Hiệu chỉnh tham số trong DE Kích thước quần thể 11 Các giải thuật tiến hóa mong muốn khám phá được nhiều không gian tìm kiếm trong các thế hệ đầu Ở các thế hệ cuối quá trình tập trung khai thác những vùng có chứa lời giải hứa hẹn. Các giải thuật tiến hóa khác nhau ở mức độ khám phá và khai thác của chúng Khám phá gt Kích thước quần thể lớn Khai thác gt Kích thước quần thể nhỏ Storn và Price chỉ ra nên chọn kích thước quần thể với D là số chiều không gian tìm kiếm Hiệu