Đăng ký Đăng nhập
Trang chủ 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à...

Tài liệu 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ị

.PDF
146
464
59

Mô tả:

BỘ GIÁO DỤC VÀ ĐÀO TẠO BỘ QUỐC PHÒNG HỌC VIỆN KỸ THUẬT QUÂN SỰ Vũ Chí Cường 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Ị LUẬN ÁN TIẾN SỸ TOÁN HỌC Chuyên ngành: Cơ sở toán học trong tin học Mã số: 62.46.01.10 Hà Nội - Năm 2016 BỘ GIÁO DỤC VÀ ĐÀO TẠO BỘ QUỐC PHÒNG HỌC VIỆN KỸ THUẬT QUÂN SỰ Vũ Chí Cường 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Ị Chuyên ngành: Cơ sở toán học trong tin học Mã số: 62.46.01.10 LUẬN ÁN TIẾN SỸ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS. BÙI THU LÂM Hà Nội - Năm 2016 LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của riêng tác giả dưới sự hướng dẫn khoa học của PGS.TS. Bùi Thu Lâm. Các kết quả được công bố với các tác giả khác đều được sự đồng ý của đồng tác giả trước khi đưa vào luận án. Các kết quả nêu trong luận án là trung thực và chưa từng được công bố trong bất cứ công trình nào khác. Hà Nội, tháng 7 năm 2016 Nghiên cứu sinh Vũ Chí Cường 1 LỜI CẢM ƠN Luận án được thực hiện tại Bộ môn Công nghệ phần mềm, Khoa Công nghệ thông tin, Học viện Kỹ thuật Quân sự dưới sự hướng dẫn khoa học của PGS.TS. Bùi Thu Lâm. Lời đầu tiên, tác giả xin được bày tỏ sự kính trọng và cảm ơn chân thành nhất đến thầy giáo hướng dẫn: PGS.TS. Bùi Thu Lâm, người đã định hướng để tác giả có thể tiếp cận lĩnh vực nghiên cứu mới mẻ, khó khăn nhưng đầy tiềm năng này. Thầy đã cung cấp đầy đủ các kiến thức cũng như kinh nghiệm nghiên cứu khoa học vô cùng quý báu, thầy cũng là người động viên, khích lệ tác giả trong suốt quá trình nghiên cứu để tác giả có thể hoàn thành cuốn luận án này. Tác giả cũng xin chân thành cảm ơn tập thể cán bộ, giảng viên Bộ môn Công nghệ phần mềm, Khoa Công nghệ thông tin và Phòng Đào tạo Sau đại học, Học viện Kỹ thuật Quân sự đã tạo mọi điều kiện thuận lợi, giúp đỡ tác giả trong quá trình học tập và nghiên cứu tại Học viện. Tác giả cũng xin cảm ơn tập thể cán bộ, giảng viên Khoa Công nghệ thông tin và Trung tâm Công nghệ thông tin, Trường Đại học Vinh đã tạo điều kiện về thời gian để tác giả có thể thực hiện kế hoạch nghiên cứu và hoàn thành luận án đúng tiến độ. Cuối cùng, tác giả xin bày tỏ lòng biết ơn sâu sắc đến các bậc sinh thành kính mến và những người thân trong gia đình, đặc biệt là người vợ hết mực thủy chung và hai con thân thương đã luôn dành những tình cảm nồng ấm, sẻ chia và ủng hộ tác giả trong suốt thời gian học tập và nghiên cứu ở xa nhà. Luận án này như là món quà quý giá nhất của tác giả xin đáp lại những ân tình của bạn bè, đồng nghiệp và niềm tin tưởng, yêu thương của tất cả mọi người. Một lần nữa xin chân thành cảm ơn. Hà Nội, tháng 7 năm 2016 Nghiên cứu sinh Vũ Chí Cường 2 Mục lục Trang Danh sách ký hiệu, chữ viết tắt 6 Danh sách bảng 8 Danh sách hình vẽ 10 Lời mở đầu 11 1 CƠ SỞ LÝ THUYẾT 15 1.1 Mở đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 . 1.2 Tối ưu hóa . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 . 1.3 Thuật toán tiến hóa 1.3.1 1.3.2 1.3.3 1.3.4 1.3.5 . . . . . . . Cách biểu diễn di truyền lời giải của bài toán . Cách khởi tạo quần thể ban đầu . . . . . . Cách đánh giá cá thể . . . . . . . . . . Các phép toán tiến hóa . . . . . . . . . Điều kiện dừng của thuật toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 . . 20 . . 21 . . 22 . . 22 . . 23 . 1.4 Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 . 2 NHỮNG NỘI DUNG NGHIÊN CỨU LIÊN QUAN 27 2.1 Mở đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 . 2.2 Các thuật toán tìm kiếm dựa trên thông 2.2.1 Thuật toán tìm kiếm đơn hình (Simplex Search) . . . . 2.2.2 Thuật toán tìm kiếm phân tán (Scatter Search) . . . . . 2.2.3 Tối ưu bầy đàn (Particle Swarm Optimization) . . . . . 2.2.4 Tiến hóa vi phân (Differential Evolution) . . . . . . . tin định hướng 28 . . . . . . . . . . . 28 . . . . . . . . . . . 30 . . . . . . . . . . . 32 . . . . . . . . . . . 34 . 2.3 Phương pháp niching . . . . . . . . . . . . . . . . . . . . . . 38 . 2.3.1 Phương pháp chia sẻ giá trị đánh giá (Fitness sharing) . . . . . . . . . . . . 38 . 3 2.3.2 2.3.3 2.3.4 . . . . . . . . . . . . . . . . . . . 40 . Phương pháp dựa vào loài (Species-based) . . . . . . . . . . . . . . . . . 42 . Phương pháp phân cụm (Clustering-based) . . . . . . . . . . . . . . . . . 44 . Phương pháp đám đông (Crowding) 2.4 Kỹ thuật song song 2.4.1 Mô hình master/slave . . 2.4.2 Mô hình island . . . . . 2.4.3 Mô hình tế bào (cellular) . 2.4.4 Mô hình lai (hybrid) . . . 2.4.5 hóa thuật toán tiến hóa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Kỹ thuật đồng tiến hóa hợp tác (cooperation co-evolution) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 . . 47 . . 48 . . 49 . . 50 . . 51 . 2.5 Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 . 3 THUẬT TOÁN TIẾN HÓA DỰA TRÊN THÔNG TIN ĐỊNH HƯỚNG 54 3.1 Mở đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 . 3.2 Thuật toán DEAL . . . . . . . . 3.2.1 Độ phức tạp tính toán . . . . . . . . . 3.2.2 Các tùy chọn về bước nhảy định hướng . . 3.2.3 Các chiến lược lai ghép . . . . . . . . . . . . . . . . . . . . . 3.3 Song song DEAL với kỹ thuật đồng 3.3.1 Mô hình song song . . . . . . . . . . . . . 3.3.2 Thuật toán song song . . . . . . . . . . . . 3.3.3 Thời gian thực thi và hệ số tăng tốc . . . . . . . . . . . . . . . . . . tiến . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 . . 59 . . 60 . . 60 . hóa hợp tác . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 . . 61 . . 63 . . 65 . 3.4 Đánh giá thực nghiệm . . . . . . . . . . . . . . . . . . . . . 69 . 3.4.1 Thực nghiệm DEAL và MDEAL . . . . . . . . . . . . . . . . . . . . . 69 . 3.4.2 Thực nghiệm DEAL song song . . . . . . . . . . . . . . . . . . . . . . 76 . 3.5 Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 . 4 THUẬT TOÁN TIẾN HÓA DỰA TRÊN THÔNG TIN ĐỊNH HƯỚNG VỚI BÀI TOÁN TỐI ƯU ĐA CỰC TRỊ 83 4.1 Mở đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 . 4.2 DEAL với phương pháp Fitness Sharing . . . . . . . . . . 84 . 4.3 DEAL với phương pháp Crowding . . . . . . . . . . . . . . 85 . 4 4.4 DEAL với phương pháp Species-based . . . . . . . . . . . 86 . 4.5 DEAL với phương pháp Clustering-based . . . . . . . . . 88 . 4.6 Thực nghiệm . . . . . . . . . . . . . . . 4.6.1 Môi trường thực nghiệm . . . . . . . . . . . . 4.6.2 Thực nghiệm 1: Hiệu quả của SharingDEAL . . . . 4.6.3 Thực nghiệm 2: Hiệu quả của CrowdingDEAL . . . 4.6.4 Thực nghiệm 3: Hiệu quả của SpeciesDEAL . . . . 4.6.5 Thực nghiệm 4: Hiệu quả của NBCDEAL . . . . . 4.6.6 So sánh các thuật toán đã đề xuât . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 . . 91 . . 93 . . 96 . 101 . . 106 . . 111 . . 4.7 Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 . . Kết luận 117 Danh sách công trình của tác giả 119 Tài liệu tham khảo 120 Phụ lục 131 A CÁC SƠ ĐỒ THUẬT TOÁN 131 A.1Thuật toán Simplex Search . . . . . . . . . . . . . . . . . 132 . . A.2Thuật toán Scatter Search . . . . . . . . . . . . . . . . . 133 . . A.3Thuật toán Particle Swarm Optimization . . . . . . . . 134 . . B CÁC BÀI TOÁN THỰC NGHIỆM MẪU 135 B.1Các bài toán tối ưu cơ bản . . . . . . . . . . . . . . . . . 135 . . B.2Các bài toán tối ưu đa cực trị . . . . . . . . . . . . . . . 139 . . 5 Danh sách ký hiệu, chữ viết tắt Ký hiệu Diễn giải ACO Thuật toán tối ưu hóa đàn kiến AIS Hệ miễn nhiễm nhân tạo CC Kỹ thuật đồng tiến hóa hợp tác (Cooperative Coevolution) CF Tham số Crowding Factor của phương pháp Crowding CrowdingDEAL Thuật toán DEAL với phương pháp Crowding D Số chiều của hàm mục tiêu (hàm đánh giá) DE Thuật toán tiến hóa vi phân DEAL Thuật toán tiến hóa dựa trên thông tin định hướng Thuật toán tiến hóa (Evolutionary Algorithm) EA EDA Thuật toán ước lượng các thuật toán phân phối EP Quy hoạch tiến hóa (Evolutionary Programming) Chiến lược tiến hóa (Evolution Strategies) ES ETS Tập các cá thể ưu tú (Elite Set) GA Giải thuật di truyền (Genetic Algorithm) GP Lập trình di truyền (Genetic Programming) M axGens Số thế hệ tối đa M axF Es Số lần tính giá trị hàm đánh giá tối đa (Maximum Fitness Evaluations) Thuật toán DEAL theo chiến lược lai ghép cải tiến MDEAL N , P opSize Kích thước quần thể NBC Kỹ thuật phân cụm Nearest-better Clustering NBCDEAL Thuật toán DEAL với phương pháp Clustering-based PCCDEAL Thuật toán song song hóa DEAL theo kỹ thuật CC PSO Thuật toán tối ưu bầy đàn SharingDEAL Thuật toán DEAL với phương pháp Fitness Sharing SpeciesDEAL Thuật toán DEAL với phương pháp Species-based SSS Tập các cá thể hạt giống (Species Seed Set) 6 Danh sách bảng 3.1 3.2 3.3 Danh sách các bài toán thực nghiệm cho DEAL . . . . . . . Thời gian thực thi thuật toán DEAL (Đơn vị tính: giây) . . So sánh giá trị tối ưu trung bình theo các tùy chọn bước nhảy định hướng . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 So sánh hai chiến lược lai ghép . . . . . . . . . . . . . . . . 3.5 So sánh DEAL với các thuật toán khác . . . . . . . . . . . . 3.6 Danh sách các bài toán thực nghiệm cho DEAL song song . 3.7 Thời gian thực thi với Evolution_Cycle = 1 (ĐVT: giây) . 3.8 Thời gian thực thi với Evolution_Cycle = 5 (ĐVT: giây) . 3.9 Thời gian thực thi với Evolution_Cycle = 10 (ĐVT: giây) . 3.10 Giá trị tối ưu trung bình của PCCDEAL . . . . . . . . . . . 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 4.10 4.11 4.12 4.13 4.14 4.15 4.16 . . . 70 . . . 70 . . . . . . . . . . . . . . . . . . . . . . . . Danh sách các bài toán thực nghiệm . . . . . . . . . . . . . . . . Kết quả thực nghiệm của SharingDEAL . . . . . . . . . . . . . . So sánh SharingDEAL với các thuật toán khác . . . . . . . . . . Kết quả thực nghiệm của CrowdingDE . . . . . . . . . . . . . . . Kết quả thực nghiệm của CDE . . . . . . . . . . . . . . . . . . . Kết quả thực nghiệm của CrowdingDEAL . . . . . . . . . . . . . Thống kê số trường hợp xếp hạng nhất theo các độ đo PR và SR Kết quả thực nghiệm của SpeciesDEAL_Op1 . . . . . . . . . . . Kết quả thực nghiệm của SpeciesDEAL_Op2 . . . . . . . . . . . Kết quả thực nghiệm của SpeciesDEAL_Op3 . . . . . . . . . . . Kết quả thực nghiệm của SpeciesDEAL_Op4 . . . . . . . . . . . So sánh độ đo PR của SpeciesDEAL và các thuật toán khác . . . Kết quả thực nghiệm của NBCDEAL_Op1 . . . . . . . . . . . . Kết quả thực nghiệm của NBCDEAL_Op2 . . . . . . . . . . . . Kết quả thực nghiệm của NBCDEAL_Op3 . . . . . . . . . . . . Kết quả thực nghiệm của NBCDEAL_Op4 . . . . . . . . . . . . 7 74 74 76 77 78 79 79 81 92 94 95 98 98 99 99 102 102 103 103 105 106 107 107 108 4.17 4.18 4.19 4.20 4.21 4.22 4.23 4.24 4.25 4.26 4.27 Tổng hợp xếp hạng theo các tùy chọn của NBCDEAL . . . . . . 108 So sánh độ đo PR của NBCDEAL khi điều chỉnh φ . . . . . . . . 110 So sánh độ đo PR của NBCDEAL và các thuật toán khác . . . . 111 Giá trị độ đo PR ở độ chính xác  = 1.0E − 01 của các thuật toán112 Giá trị độ đo PR ở độ chính xác  = 1.0E − 02 của các thuật toán113 Giá trị độ đo PR ở độ chính xác  = 1.0E − 03 của các thuật toán113 Giá trị độ đo PR ở độ chính xác  = 1.0E − 04 của các thuật toán114 Giá trị độ đo PR ở độ chính xác  = 1.0E − 05 của các thuật toán114 Kiểm định Friedman của các thuật toán . . . . . . . . . . . . . . 115 Thứ hạng của các thuật toán theo kiểm định Friedman . . . . . . 115 Kiểm định Wilcoxon của các thuật toán . . . . . . . . . . . . . . 116 8 Danh sách hình vẽ 1.1 1.2 1.3 Phương án tối ưu địa phương và phương án tối ưu toàn cục . . . 17 Bài toán tối ưu đơn cực trị Sphere . . . . . . . . . . . . . . . . . 17 Bài toán tối ưu đa cực trị (Ackley và Shubert) . . . . . . . . . . . 18 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9 2.10 Biễu diễn cộng trừ hai véc tơ . . . . Thuật toán Simplex Search . . . . . Các thủ tục của Scatter Search . . . Cập nhật vị trí tìm kiếm trong PSO Thông tin định hướng trong DE . . Xác định tập hạt giống . . . . . . . Kỹ thuật NBC . . . . . . . . . . . . Mô hình Master/Slave . . . . . . . . Mô hình Island . . . . . . . . . . . . Mô hình Cellular . . . . . . . . . . . . . . . . . . . . . 29 30 32 32 34 43 46 47 48 50 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 3.10 3.11 Hai dạng thông tin định hướng của DEAL . . . . . . . . . . . . . Các chiến lược lai ghép của DEAL . . . . . . . . . . . . . . . . . Mô hình song song PCCDEAL . . . . . . . . . . . . . . . . . . . Mô hình cập nhật cá thể tối ưu toàn cục . . . . . . . . . . . . . . Mô hình thời gian thực thi PCCDEAL . . . . . . . . . . . . . . . Đồ thị biểu diễn hệ số tăng tốc theo mô hình song song 3.3 . . . . Giá trị đánh giá tốt nhất của Sphere’ problem trong 100 lần chạy Giá trị đánh giá tốt nhất của Ackley’ problem trong 100 lần chạy Độ đa dạng quần thể của bài toán đơn cực trị Sphere’s Problem . Độ đa dạng quần thể của các bài toán đa cực trị . . . . . . . . . Giá trị tối ưu trung bình đạt được khi D = 30 của các bài toán . 59 60 62 62 66 69 71 72 73 73 77 4.1 4.2 Thuật toán SpeciesDEAL với bài toán Himmelblau . . . . . . . . 89 Thuật toán NBCDEAL với bài toán Himmelblau . . . . . . . . . 90 9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 4.4 4.5 4.6 4.7 4.8 4.9 Thuật toán NBCDEAL với bài toán Shubert . . . . . . . . . Ảnh hưởng của thủ tục loại bỏ một nửa số cá thể . . . . . . Ảnh hưởng của kích thước quần thể . . . . . . . . . . . . . Giá trị tối ưu trung bình của hàm F6 (2D) . . . . . . . . . . Giá trị tối ưu trung bình của hàm F7 (3D) . . . . . . . . . . Giá trị tối ưu trung bình của SpeciesDEAL khi điều chỉnh rs Giá trị tối ưu trung bình của NBCDEAL khi điều chỉnh φ . 10 . . . . . . . . . . . . . . . . . . . . . 91 96 97 100 101 104 110 Lời mở đầu 1. Giới thiệu chung Thuật toán phỏng tiến hóa sinh học hay gọi ngắn gọi là thuật toán tiến hóa (Evolutionary Algorithms - EAs) là một lớp các thuật toán heuristic trong tối ưu hóa và học máy. EAs đã được áp dụng rộng rãi và thu được nhiều thành công trong việc giải quyết các bài toán tối ưu số và tối ưu tổ hợp. Về nguyên tắc, EA là một thuật toán lấy ý tưởng từ quá trình chọn lọc tự nhiên trong thuyết tiến hóa của Darwin. EAs hoạt động trên tập các phương án (còn gọi là quần thể - population) để tìm kiếm phương án tối ưu. Nguyên tắc tính toán dựa vào quần thể đã được khẳng định là một mô hình tiềm năng cho việc giải quyết các bài toán tối ưu toàn cục [4, 31, 32, 63, 65, 85]. Trong quá trình nghiên cứu và phát triển, đã có 4 dạng EAs truyền thống được đề xuất, bao gồm Quy hoạch tiến hóa (Evolutionary Programming - EP), Chiến lược tiến hóa (Evolutionary Strategies - ES), Giải thuật di truyền (Genetic Algorithm - GA) và Lập trình di truyền (Genetic Programming - GP). Các đặc điểm quan trọng nhất đối với các EAs là: • EAs điều khiển quá trình tiến hóa của một quần thể gồm nhiều cá thể, mỗi cá thể đại diện (hay mã hóa) cho một phương án (hay một lời giải) chấp nhận được của bài toán tối ưu. • Các cá thể con (offsprings) được sinh ra một cách ngẫu nhiên thông qua các quá trình đột biến và lai ghép. Quá trình đột biến là một sự thay đổi (rất nhỏ) của một cá thể trong khi đó quá trình lai ghép là sự hoán đổi thông tin giữa 2 hay nhiều cá thể hiện tại. • Một hàm đánh giá được sử dụng để đo chất lượng hay tính toán mức độ phù hợp của các cá thể. Cá thể có giá trị đánh giá cao hơn được xem là tốt hơn cá thể khác. Quá trình lựa chọn thực hiện việc lựa chọn và ưu tiên cho các cá thể tốt hơn với mục đích là tạo ra một thế hệ mới với các cá thể tốt hơn. Bên cạnh các lớp EAs, trong khoảng thời gian 15 năm gần đây, đã có một số mô hình thuật toán phỏng tự nhiên mới được đề xuất, chẳng hạn như Tối ưu bầy đàn (PSO) [43], Tối ưu đàn kiến (ACO) [19], Ước lượng các thuật toán phân phối (EDA) [49], Hệ miễn nhiễm nhân tạo (AIS) [12],... Trong các mô hình này, các thủ tục tính toán được lấy ý tưởng từ những hiện tượng khác nhau của thế giới tự nhiên như bầy chim, đàn cá hay đàn kiến,... Trong thiết kế các thuật toán heuristic, cả truyền thống cũng như hiện đại, vấn đề sử dụng thông tin định hướng luôn nhận được sự quan tâm của các nhà nghiên cứu. Nếu có thông tin định hướng tốt thì quá trình tìm kiếm phương án tối ưu sẽ diễn ra nhanh chóng và đạt kết quả tốt. Phương pháp tụt Gradient (Gradient Descent), thuật toán tìm kiếm đơn hình (Simplex Search) [66], thuật toán tìm kiếm phân tán (Scatter Search) [30, 47] là những ví dụ điển hình trong việc sử dụng thông tin định hướng để giải quyết các bài toán tối ưu. Trong các mô hình thuật toán tiến hóa mới, lớp các thuật toán tiến hóa vi phân (Differential Evolution) [75] là một ví dụ khác về những lợi ích đạt được khi sử dụng thông tin định hướng để chỉ dẫn quá trình tìm kiếm lời giải. Tuy nhiên, trong các thuật toán này, thông tin định hướng chỉ được xác định một cách cục bộ trong từng thế hệ của quá trình tiến hóa mà chưa có tính toàn cục, cách tổ chức quản lý thông tin hướng còn thiếu tính hệ thống. Bởi thế sẽ tồn tại những trường hợp mà thông tin định hướng có thể làm suy giảm chất lượng (giá trị đánh giá) của các phương án đã tìm được. Vấn đề xác định các thông tin định hướng tốt và cách thức quản lý, sử dụng thông tin đó một cách có hệ thống để hỗ trợ quá trình tiến hóa sẽ là chủ đề nghiên cứu chính của luận án. Ngoài ra, trong cách thức tổ chức quản lý các cá thể, có thể thấy rằng một quần thể các cá thể có thể bao hàm các thông tin định hướng, các thông tin định hướng này hoàn toàn có thể được xác định một cách có hệ thống và hỗ trợ quá trình tìm kiếm tiến hóa. 2. Đóng góp của luận án Đóng góp của luận án là phương pháp xác định và sử dụng thông tin định hướng hỗ trợ các thuật toán tiến hóa. Chi tiết các đóng góp cụ thể bao gồm: 1. Đề xuất thuật toán tiến hóa dựa trên thông tin định hướng DEAL (Direction-guided Evolutionary ALgorithm) với một số đặc trưng: • Sử dụng cân đối 2 dạng thông tin định hướng: (1) hướng hội tụ (Convergence Direction) là hướng từ một cá thể kém hơn (hạng 2) 12 đến một cá thể ưu tú và (2) hướng tản mát (Spread Direction) là hướng giữa 2 cá thể ưu tú. • Các thông tin định hướng được quản lý một cách toàn cục. Các cá thể ưu tú được lưu trữ trong tập ETS (Elite Set), liên tục được cập nhật trong suốt quá trình tiến hóa. Tập ETS chứa đựng thông tin định hướng. • Có 4 tùy chọn khác nhau về bước nhảy định hướng và 2 chiến lược lai ghép. • Có thể mở rộng, nâng cao hiệu năng tính toán thông qua kỹ thuật song song hóa. Thuật toán song song PCCDEAL được đề xuất sử dụng mô hình song song kết hợp giữa mô hình master/slave truyền thống với kỹ thuật đồng tiến hóa hợp tác. Các kết quả thực nghiệm cho thấy tính hiệu quả của thuật toán và mô hình. 2. Đề xuất thuật toán tiến hóa dựa trên thông tin định hướng nhằm giải quyết các bài toán đa cực trị: Gồm 4 thuật toán SharingDEAL, CrowdingDEAL, SpeciedDEAL và NBCDEAL là giải pháp kết hợp giữa DEAL và các phương pháp niching phổ biến. Kết quả thực nghiệm của các thuật toán này đều cho thấy sự khả quan của hướng nghiên cứu khi so sánh được với các thuật toán nổi tiếng được xếp hạng trong thời gian gần đây. 3. Bố cục của luận án Các nội dung nghiên cứu của luận án được bố trí trong 4 chương và 2 phụ lục, bao gồm: Chương 1: Cơ sở lý thuyết. Chương này trình bày những khái niệm lý thuyết cơ bản của tối ưu hóa, làm quen với các dạng bài toán tối ưu đơn cực trị (uni-modal optimization problems) và đa cực trị (multi-modal optimization problems). Phần lý thuyết về thuật toán tiến hóa, các thành phần của một thuật toán cũng được trình bày một cách chi tiết. Chương 2: Những nội dung nghiên cứu liên quan. Chương này tập trung khảo sát những nội dung nghiên cứu liên quan đến luận án. Trong phần đầu, luận án mô tả một cách chi tiết nội dung các thuật toán tìm kiếm tiêu biểu dựa trên thông tin định hướng. Các thuật toán được trình bày theo trình tự từ cổ điển đến hiện đại để thấy được sự quan tâm của các nhà nghiên cứu đối với nội dung này. Trong các phần tiếp theo, luận án lần lượt trình bày các phương pháp nhằm nâng cao hiệu năng của các EAs đối với các lớp bài toán khác nhau như các phương pháp niching, song song hóa, đồng tiến hóa hợp tác. Đối với mỗi phương pháp, luận án 13 trình bày rõ ý tưởng, các bước thực hiện của phiên bản đề xuất, sau đó khảo sát một số các nghiên cứu gần đây có liên quan. Chương 3: Thuật toán tiến hóa dựa trên thông tin định hướng. Chương này tập trung trình bày một cách chi tiết nội dung thuật toán tiến hóa dựa trên thông tin định hướng (gọi tắt là DEAL) do tác giả đề xuất. Bao gồm ý tưởng, bố cục thuật toán, các tùy chọn và chiến lược tiến hóa, độ phức tạp tính toán. Các thực nghiệm được tổ chức cho thấy thuật toán DEAL làm việc hiệu quả đối với lớp các bài toán tối ưu đơn cực trị và lớp bài toán tối ưu đa cực trị nhưng chỉ có một phương án tối ưu toàn cục. Trong phần thứ hai của chương, tác giả đã trình bày phương án mở rộng nhằm nâng cao hiệu năng tính toán của thuật toán DEAL bằng phương pháp song song hóa. Mô hình song song được sử dụng là một mô hình mới, không hoàn toàn giống với mô hình master/slave truyền thống. Mô hình và thuật toán song song được phân tích lý thuyết về thời gian thực thi, hệ số tăng tốc và tổ chức kiểm chứng thông qua các thực nghiệm ở phần cuối của chương. Chương 4: Thuật toán tiến hóa dựa trên thông tin định hướng với bài toán đa cực trị. Chương này trình bày các mở rộng của thuật toán DEAL nhằm giải quyết các bài toán tối ưu đa cực trị (multi-modal optimization problems). Đây là lớp bài toán thường gặp trong thực tế và để giải quyết nó, thuật toán DEAL cần có những biến đổi phù hợp về mặt hành vi bằng các phương pháp niching. Trong nội dung của chương, tác giả lần lượt trình bày 4 thuật toán mới SharingDEAL, CrowdingDEAL, SpeciesDEAL và NBCDEAL là sự kết hợp giữa các phương pháp niching tương ứng với thuật toán DEAL. Các thực nghiệm với 20 bài toán tối ưu đa cực trị phổ biến để kiểm tra, đánh giá và so sánh các thuật toán thuộc luận án với các thuật toán nổi tiếng khác, đặc biệt có những thuật toán được đánh giá cao trong các cuộc thi thiết kế thuật toán gần đây. Phần cuối của luận án là kết luận với các đánh giá về những đóng góp chính của luận án và một số ý tưởng về hướng nghiên cứu trong tương lai của tác giả. 14 Chương 1 CƠ SỞ LÝ THUYẾT 1.1. Mở đầu Mục đích của chương này là cung cấp các kiến thức cơ sở lý thuyết liên quan đến nội dung nghiên cứu của luận án. Cấu trúc của chương gồm 2 phần chính. Phần đầu trình bày những khái niệm lý thuyết tổng quan về tối ưu hóa, liên quan nhiều nhất đến thuật toán tiến hóa. Phần thứ hai mô tả các nội dung cơ bản của thuật toán tiến hóa như khái niệm, bản chất, các dạng phân loại truyền thống. Trong phần này, tác giả cũng dành thời gian để mô tả một cách cụ thể các thành phần chính của một thuật toán tiến hóa và cuối cùng là sơ đồ tổng quát của thuật toán. 1.2. Tối ưu hóa Tối ưu hóa là một trong những lĩnh vực nghiên cứu kinh điển của toán học có ảnh hưởng đến nhiều lĩnh vực Khoa học – Công nghệ và Kinh tế – Xã hội. Trong thực tế, việc tìm kiếm phương án tối ưu cho một vấn đề nào đó chiếm một vai trò hết sức quan trọng. Phương án tối ưu là phương án hợp lý, tiết kiệm chi phí, tài nguyên, nguồn lực,... Định nghĩa 1.1. Cho hàm số thực f , bài toán tìm cực trị f (x) −→ max(min) với điều kiện x ∈ Ω ⊆ Rn (1.1) được gọi là bài toán tối ưu hóa. Hàm số thực f : Rn −→ R được gọi là hàm mục tiêu hay hàm đánh giá, n gọi là chiều của bài toán. Véc tơ x = (x1 , . . . , xn )T ∈ Ω ⊆ Rn gọi là véc tơ quyết định, chính là lời giải chấp nhận được hay phương án chấp nhận được của bài toán, các biến thành phần x1 , . . . , xn là các biến quyết định. 15 Định nghĩa 1.2. Cho bài toán tối ưu hóa dạng (1.1). Nếu Ω = Rn thì bài toán (1.1) gọi là bài toán tối ưu không ràng buộc. Ngược lại Ω ⊂ Rn thì bài toán (1.1) là bài toán tối ưu có ràng buộc. Tập Ω được gọi là tập ràng buộc hay tập khả thi của bài toán. Tập ràng buộc Ω thường có dạng   hi (x) = 0, i ∈ {1, 2, . . . , p} Ω = x gj (x) ≤ 0, j ∈ {1, 2, . . . , q} trong đó hi và gj là các hàm cho trước và được gọi là các hàm ràng buộc, p, q là số lượng các hàm ràng buộc. Định nghĩa 1.3. Cho bài toán tối ưu hóa dạng (1.1). Một phương án chấp nhận được x∗ được gọi là phương án tối ưu hay lời giải của bài toán nếu thỏa mãn: hoặc f (x) ≤ f (x∗ ), ∀x ∈ Ω đối với bài toán max f (x) ≥ f (x∗ ), ∀x ∈ Ω đối với bài toán min. Khi đó f ∗ = f (x∗ ) được gọi là giá trị tối ưu của bài toán. Có 2 loại phương án tối ưu là phương án tối ưu địa phương và phương án tối ưu toàn cục. Định nghĩa 1.4. Phương án x∗ ∈ Ω được gọi là phương án tối ưu địa phương trên Ω nếu tồn tại  > 0 sao cho f (x) ≤ f (x∗ ) đối với bài toán max (hoặc f (x) ≥ f (x∗ ) đối với bài toán min), trong đó x ∈ Ω \ {x∗ } và |x − x∗ | < . Phương án x∗ ∈ Ω được gọi là phương án tối ưu toàn cục trên Ω nếu f (x) ≤ f (x∗ ) đối với bài toán max (hoặc f (x) ≥ f (x∗ ) đối với bài toán min), trong đó x ∈ Ω \ {x∗ }. Ta dễ nhận thấy rằng mọi phương án tối ưu toàn cục sẽ là phương án tối ưu địa phương. Trong khi đó, một phương án tối ưu địa phương không nhất thiết là phương án tối ưu toàn cục. Trong định nghĩa trên, nếu ta thay phép so sánh ” ≥ ” bằng phép so sánh ” > ” trong bài toán max (hoặc thay phép so sánh ” ≤ ” bằng phép so sánh ” < ” trong bài toán min) thì ta có các khái niệm phương án tối ưu địa phương chặt và phương án tối ưu toàn cục chặt. Xem xét ví dụ về bài toán tìm cực đại trong Hình 1.1, ta có x3 là phương án tối ưu toàn cục chặt, x2 là phương án tối ưu địa phương chặt trong khi đó x1 là phương án tối ưu địa phương không chặt. 16 Hình 1.1: Phương án tối ưu địa phương và phương án tối ưu toàn cục Định nghĩa 1.5. Cho bài toán tối ưu hóa dạng (1.1), x∗ là phương án tối ưu của bài toán. Với một số  > 0 đủ nhỏ, một phương án chấp nhận được x được gọi là phương án  - tối ưu của bài toán nếu |f (x) − f (x∗ )| ≤ . Định nghĩa 1.6. Bài toán tối ưu đơn cực trị (uni-modal optimization problem) là bài toán tối ưu hóa chỉ có một phương án tối ưu địa phương. Ngược lại, bài toán tối ưu hóa có nhiều phương án tối ưu địa phương được gọi là bài toán tối ưu đa cực trị (multi-modal optimization problem). Hình 1.2: Bài toán tối ưu đơn cực trị Sphere Xét Hình 1.2 là dạng biểu diễn 3D của hàm Sphere có công thức f (x) = 2 X x2i i=1 Bài toán tìm cực tiểu với hàm mục tiêu Sphere có duy nhất một phương án tối ưu địa phương là x∗ = (0, 0). Như vậy đây là bài toán tối ưu đơn 17 (a) Ackley (b) Shubert Hình 1.3: Bài toán tối ưu đa cực trị (Ackley và Shubert) cực trị. Chú ý rằng, ở đây phương án tối ưu địa phương x∗ = (0, 0) cũng là phương án tối ưu toàn cục. Hình 1.3a là dạng biểu diễn 3D của hàm Ackley có công thức v   ! u 2 2 u1 X X 1 f (x) = −20 exp −0.2t x2i  − exp cos(2πxi ) + 20 + e 2 i=1 2 i=1 Bài toán tìm cực tiểu với hàm mục tiêu Ackley có 1 phương án tối ưu toàn cục và nhiều phương án tối ưu địa phương. Như vậy bài toán này là bài toán tối ưu đa cực trị và thuộc dạng bài toán tối ưu đa cực trị có một phương án tối ưu toàn cục. Hình 1.3b là dạng biểu diễn 3D của hàm Shubert có công thức f (x) = − 2 X 5 Y j cos[(j + 1)xi + j] i=1 j=1 Bài toán tìm cực đại với hàm mục tiêu Shubert có nhiều phương án tối ưu toàn cục, tất nhiên đó cũng chính là các phương án tối ưu địa phương. Bởi vậy bài toán tìm cực đại với hàm mục tiêu Shubert là bài toán tối ưu đa cực trị và thuộc dạng bài toán tối ưu đa cực trị có nhiều phương án tối ưu toàn cục. Một trong những phương pháp hiển nhiên nhất để giải bài toán tối ưu là: Tìm giá trị hàm mục tiêu f (x) trên tất cả các phương án chấp nhận được, sau đó so sánh các giá trị tính được để tìm ra giá trị tối ưu và phương án tối ưu của bài toán. Tuy nhiên cách giải quyết này là khó có thể thực 18
- Xem thêm -

Tài liệu liên quan