Bài giảng Tính toán tiến hóa - Chương 7: Differential Evolution

Differential Evolution (DE) Tổng quan 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 Khởi tạo Đột biến Lai ghép Chọn lọc Mô hình thuật toán Khởi tạo 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 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 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 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 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 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ể 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á => Kích th ư ớc quần thể lớn Khai thác => 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 chỉnh tham số trong DE  Tỷ lệ lai ghép (CR) và hệ số scale F jDE Điều kiển F và CR bởi 2 tham số Cập nhật F và CR Hiệu chỉnh tham số trong DE  Tỷ lệ lai ghép (CR) và hệ số scale F SaDE F = lấy ngẫu nhiên theo phân phối chuẩn N(0.5,0.3) . Giá trị trung bình ban đầu =0.5 Trong một số thế hệ (cụ thể 5), CR không đổi. Sau đó CR đ ư ợc sinh lại theo phân phối Sau một số thế hệ (25 thế hệ) , được tính lại từ giá trị trung bình của các giá trị CR của các cá thể con thành công ở các thế hệ trước Mỗi khi tính lại , các giá trị CR cũ bị xóa bỏ Hiệu chỉnh tham số trong DE  Tỷ lệ lai ghép (CR) và hệ số scale F JADE , Cập nhật là tập các giá trị CR của các cá thể con thành công F , F Cập nhật Hiệu chỉnh tham số trong DE  Tỷ lệ lai ghép (CR) và hệ số scale F SHADE Sử dụng Lehmer mean (Cec 14) để tính Lưu trữ cảu mỗi thế hệ vào trong lịch sử là mảng số thực có H phần tử Cặp giá trị được chọn bằng cách lấy ngẫu nhiên một số k trong khoảng [1,H] Hiệu chỉnh tham số trong DE  Tỷ lệ lai ghép (CR) và hệ số scale F SHADE k = 2 Hiệu chỉnh tham số trong DE  Tỷ lệ lai ghép (CR) và hệ số scale F SHADE Các phần tử trong ban đầu được khởi tạo đều là 0.5 được sử dụng bởi các cá thể con thành công được lưu trong Sau mỗi thế hệ thứ i, tính lại và lưu trữ lại vị trí k = i mod H +1 trong mảng tương ứng Hiệu chỉnh tham số trong DE  Tỷ lệ lai ghép (CR) và hệ số scale F SHADE Thanks for your attention