Luận án Tiến sỹ Toán học: Một lớp thuật toán phỏng tiến hoá 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 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), 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,... Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Luận án Tiến sỹ Toán học: Một lớp thuật toán phỏng tiến hoá sinh học dựa trên thông tin định hướng giải bài toán đa cực trị 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