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<br /> BỘ QUỐC PHÒNG<br /> HỌC VIỆN KỸ THUẬT QUÂN SỰ<br /> <br /> Vũ Chí Cường<br /> <br /> MỘT LỚP THUẬT TOÁN PHỎNG TIẾN HÓA SINH HỌC<br /> DỰA TRÊN THÔNG TIN ĐỊNH HƯỚNG<br /> GIẢI BÀI TOÁN ĐA CỰC TRỊ<br /> <br /> LUẬN ÁN TIẾN SỸ TOÁN HỌC<br /> Chuyên ngành: Cơ sở toán học trong tin học<br /> Mã số: 62.46.01.10<br /> <br /> Hà Nội - Năm 2016<br /> <br /> BỘ GIÁO DỤC VÀ ĐÀO TẠO<br /> BỘ QUỐC PHÒNG<br /> HỌC VIỆN KỸ THUẬT QUÂN SỰ<br /> <br /> Vũ Chí Cường<br /> <br /> MỘT LỚP THUẬT TOÁN PHỎNG TIẾN HÓA SINH HỌC<br /> DỰA TRÊN THÔNG TIN ĐỊNH HƯỚNG<br /> GIẢI BÀI TOÁN ĐA CỰC TRỊ<br /> <br /> Chuyên ngành: Cơ sở toán học trong tin học<br /> Mã số: 62.46.01.10<br /> <br /> LUẬN ÁN TIẾN SỸ TOÁN HỌC<br /> <br /> NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS. BÙI THU LÂM<br /> <br /> Hà Nội - Năm 2016<br /> <br /> LỜI CAM ĐOAN<br /> <br /> Tôi xin cam đoan đây là công trình nghiên cứu của riêng tác giả dưới<br /> 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<br /> bố với các tác giả khác đều được sự đồng ý của đồng tác giả trước khi đưa<br /> 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<br /> được công bố trong bất cứ công trình nào khác.<br /> Hà Nội, tháng 7 năm 2016<br /> Nghiên cứu sinh<br /> Vũ Chí Cường<br /> <br /> 1<br /> <br /> LỜI CẢM ƠN<br /> <br /> Luận án được thực hiện tại Bộ môn Công nghệ phần mềm, Khoa Công<br /> nghệ thông tin, Học viện Kỹ thuật Quân sự dưới sự hướng dẫn khoa học<br /> của PGS.TS. Bùi Thu Lâm.<br /> Lời đầu tiên, tác giả xin được bày tỏ sự kính trọng và cảm ơn chân<br /> thành nhất đến thầy giáo hướng dẫn: PGS.TS. Bùi Thu Lâm, người đã<br /> định hướng để tác giả có thể tiếp cận lĩnh vực nghiên cứu mới mẻ, khó<br /> khăn nhưng đầy tiềm năng này. Thầy đã cung cấp đầy đủ các kiến thức<br /> cũng như kinh nghiệm nghiên cứu khoa học vô cùng quý báu, thầy cũng<br /> là người động viên, khích lệ tác giả trong suốt quá trình nghiên cứu để tác<br /> giả có thể hoàn thành cuốn luận án này.<br /> 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<br /> Công nghệ phần mềm, Khoa Công nghệ thông tin và Phòng Đào tạo Sau<br /> đạ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<br /> đỡ tác giả trong quá trình học tập và nghiên cứu tại Học viện.<br /> Tác giả cũng xin cảm ơn tập thể cán bộ, giảng viên Khoa Công nghệ<br /> thông tin và Trung tâm Công nghệ thông tin, Trường Đại học Vinh đã tạo<br /> đ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à<br /> hoàn thành luận án đúng tiến độ.<br /> 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<br /> thành kính mến và những người thân trong gia đình, đặc biệt là người vợ<br /> hết mực thủy chung và hai con thân thương đã luôn dành những tình cảm<br /> nồng ấm, sẻ chia và ủng hộ tác giả trong suốt thời gian học tập và nghiên<br /> cứu ở xa nhà. Luận án này như là món quà quý giá nhất của tác giả xin<br /> đáp lại những ân tình của bạn bè, đồng nghiệp và niềm tin tưởng, yêu<br /> thương của tất cả mọi người.<br /> Một lần nữa xin chân thành cảm ơn.<br /> Hà Nội, tháng 7 năm 2016<br /> Nghiên cứu sinh<br /> Vũ Chí Cường<br /> <br /> 2<br /> <br /> Mục lục<br /> Trang<br /> Danh sách ký hiệu, chữ viết tắt<br /> <br /> 6<br /> <br /> Danh sách bảng<br /> <br /> 8<br /> <br /> Danh sách hình vẽ<br /> <br /> 10<br /> <br /> Lời mở đầu<br /> <br /> 11<br /> <br /> 1 CƠ SỞ LÝ THUYẾT<br /> <br /> 15<br /> <br /> 1.1 Mở đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15<br /> .<br /> 1.2 Tối ưu hóa . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15<br /> .<br /> 1.3 Thuật toán tiến hóa<br /> 1.3.1<br /> 1.3.2<br /> 1.3.3<br /> 1.3.4<br /> 1.3.5<br /> <br /> . . . . . . .<br /> Cách biểu diễn di truyền lời giải của bài toán .<br /> Cách khởi tạo quần thể ban đầu . . . . . .<br /> Cách đánh giá cá thể . . . . . . . . . .<br /> Các phép toán tiến hóa . . . . . . . . .<br /> Điều kiện dừng của thuật toán . . . . . . .<br /> <br /> .<br /> .<br /> .<br /> .<br /> .<br /> .<br /> <br /> .<br /> .<br /> .<br /> .<br /> .<br /> .<br /> <br /> .<br /> .<br /> .<br /> .<br /> .<br /> .<br /> <br /> .<br /> .<br /> .<br /> .<br /> .<br /> .<br /> <br /> .<br /> .<br /> .<br /> .<br /> .<br /> .<br /> <br /> .<br /> .<br /> .<br /> .<br /> .<br /> .<br /> <br /> .<br /> .<br /> .<br /> .<br /> .<br /> .<br /> <br /> .<br /> .<br /> .<br /> .<br /> .<br /> .<br /> <br /> .<br /> .<br /> .<br /> .<br /> .<br /> .<br /> <br /> .<br /> .<br /> .<br /> .<br /> .<br /> .<br /> <br /> .<br /> .<br /> .<br /> .<br /> .<br /> .<br /> <br /> .<br /> .<br /> .<br /> .<br /> .<br /> .<br /> <br /> .<br /> .<br /> .<br /> .<br /> .<br /> .<br /> <br /> .<br /> .<br /> .<br /> .<br /> .<br /> .<br /> <br /> . 19<br /> .<br /> . 20<br /> .<br /> . 21<br /> .<br /> . 22<br /> .<br /> . 22<br /> .<br /> . 23<br /> .<br /> <br /> 1.4 Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25<br /> .<br /> 2 NHỮNG NỘI DUNG NGHIÊN CỨU LIÊN QUAN<br /> <br /> 27<br /> <br /> 2.1 Mở đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27<br /> .<br /> 2.2 Các thuật toán tìm kiếm dựa trên thông<br /> 2.2.1 Thuật toán tìm kiếm đơn hình (Simplex Search) . . . .<br /> 2.2.2 Thuật toán tìm kiếm phân tán (Scatter Search) . . . . .<br /> 2.2.3 Tối ưu bầy đàn (Particle Swarm Optimization) . . . . .<br /> 2.2.4 Tiến hóa vi phân (Differential Evolution) . . . . . . .<br /> <br /> tin định hướng 28<br /> .<br /> . . . . . . . . . . 28<br /> .<br /> . . . . . . . . . . 30<br /> .<br /> . . . . . . . . . . 32<br /> .<br /> . . . . . . . . . . 34<br /> .<br /> <br /> 2.3 Phương pháp niching . . . . . . . . . . . . . . . . . . . . . . 38<br /> .<br /> 2.3.1 Phương pháp chia sẻ giá trị đánh giá (Fitness sharing) . . . . . . . . . . . . 38<br /> .<br /> 3<br /> <br />