MỘT LỚP THUẬT TOÁN PHỎNG TIẾN HÓA SINH HỌC DỰA TRÊN THÔNG TIN ĐỊNH HƯỚNG GIẢI BÀI TOÁN ĐA CỰC TRỊ
Cơ sở toán học trong tin học
Luận án này đề xuất một lớp thuật toán phỏng tiến hóa sinh học mới, được gọi là Thuật toán tiến hóa dựa trên thông tin định hướng (DEAL), nhằm giải quyết bài toán đa cực trị. Thuật toán tiến hóa (EAs) là một lớp các thuật toán heuristic mạnh mẽ trong tối ưu hóa và học máy, lấy cảm hứng từ quá trình chọn lọc tự nhiên. Mặc dù các EAs hiện có đã sử dụng thông tin định hướng, nhưng thường thiếu cách tiếp cận toàn cục và có hệ thống để quản lý thông tin này, điều này có thể ảnh hưởng đến chất lượng lời giải.
Đóng góp chính của luận án là thuật toán DEAL được đề xuất, sử dụng cân đối hai dạng thông tin định hướng: hướng hội tụ (từ một cá thể kém ưu tú đến một cá thể ưu tú) và hướng tản mát (giữa hai cá thể ưu tú). Các thông tin định hướng này được quản lý toàn cục thông qua một tập các cá thể ưu tú (ETS) và liên tục được cập nhật trong suốt quá trình tiến hóa. Luận án cũng nghiên cứu các tùy chọn về bước nhảy định hướng và hai chiến lược lai ghép, bao gồm một phiên bản cải tiến gọi là MDEAL.
Để nâng cao hiệu năng tính toán cho các bài toán phức tạp, luận án đã phát triển thuật toán song song hóa DEAL có tên là PCCDEAL (Parallel CoOperative CoEvolution for DEAL). Mô hình này kết hợp mô hình master/slave truyền thống với kỹ thuật đồng tiến hóa hợp tác, cho thấy khả năng cải thiện chất lượng lời giải bên cạnh việc tăng tốc độ thực thi.
Ngoài ra, luận án còn mở rộng DEAL bằng cách tích hợp nó với bốn kỹ thuật niching phổ biến: Fitness Sharing, Crowding, Species-based và Clustering-based, tạo ra các thuật toán SharingDEAL, CrowdingDEAL, SpeciesDEAL và NBCDEAL. Các thuật toán lai này được thiết kế đặc biệt để giải quyết hiệu quả các bài toán tối ưu đa cực trị.
Các kết quả thực nghiệm rộng rãi đã chứng minh tính hiệu quả của DEAL và MDEAL trên nhiều hàm kiểm tra đơn cực trị và đa cực trị, cho thấy hiệu suất cạnh tranh so với các EAs nổi tiếng khác. Đặc biệt, thuật toán NBCDEAL được đánh giá là có thể so sánh được với các thuật toán tiến hóa hiện đại. Những phát hiện này khẳng định lợi thế đáng kể của việc sử dụng thông tin định hướng được quản lý một cách có hệ thống trong tính toán tiến hóa.
Luận án được tổ chức thành bốn chương chính: Chương 1 cung cấp cơ sở lý thuyết; Chương 2 trình bày các nội dung nghiên cứu liên quan; Chương 3 giới thiệu thuật toán DEAL và phiên bản song song PCCDEAL; và Chương 4 mô tả các biến thể của DEAL kết hợp với kỹ thuật niching cho bài toán đa cực trị.