Tóm tắt Luận văn Thạc sĩ Khoa học: Thuật toán Metaheuristic giải bài toán tối ưu và phần mềm ứng dụng

Mục tiêu nghiên cứu của đề tài là luận văn tập trung nghiên cứu một số phương pháp tối ưu hiện đại để giải quyết các bài toán tối ưu và phần mềm ứng dụng Matlab.
Nội dung trích xuất từ tài liệu:
Tóm tắt Luận văn Thạc sĩ Khoa học: Thuật toán Metaheuristic giải bài toán tối ưu và phần mềm ứng dụng BỘ GIÁO DỤC VÀ ĐÀO TẠO ĐẠI HỌC ĐÀ NẴNG NGUYỄN QUANG THỊNH THUAÄT TOAÙN METAHEURISTIC GIAÛI BAØI TOAÙN TOÁI ÖU VAØ PHAÀN MEÀM ÖÙNG DUÏNG Chuyên ngành: Phương pháp Toán sơ cấp Mã số: 60.46.40TÓM TẮT LUẬN VĂN THẠC SĨ KHOA HỌC Đà Nẵng – Năm 2015 Công trình được hoàn thành tại ĐẠI HỌC ĐÀ NẴNG Người hướng dẫn khoa học: TS. HOÀNG QUANG TUYẾN Phản biện 1: PGS.TSKH. Trần Quốc Chiến Phản biện 2: TS. Nguyễn Đắc Liêm Luận văn đã được bảo vệ trước Hội đồng chấm Luận văntốt nghiệp thạc sĩ Khoa học tại Đại học Đà Nẵng vào ngày 10tháng 01 năm 2015. Có thể tìm hiểu luận văn tại:  Trung tâm Thông tin-Học liệu, Đại học Đà Nẵng  Trung tâm Học liệu, Đại học Đà Nẵng 1 MỞ ĐẦU1. Lý do chọn đề tài Trong bộ môn tối ưu toán học, phương pháp Metaheuristic đượchiểu là thủ tục cấp cao hơn nhằm tìm, tạo, hoặc chọn thủ tục cấp thấphơn để có thể tìm ra nghiệm đủ tốt cho bài toán tối ưu, đặc biệt đốivới các bài toán tối ưu với thông tin không đầy đủ hoặc đòi hỏi khốilượng tính toán quá lớn. Phương pháp Metaheuristic được phát triển mạnh mẽ từ thậpniên 80 của thế kỷ trước cho đến nay. So với các phương pháp kinhđiển (các phương pháp bước hóa), phương pháp Metaheuristic có thểkhông chắc tìm thấy nghiệm tối ưu toàn cục chính xác ở một số lớpbài toán.. Hoặc, với tập chấp nhận được khá lớn, thì phương phápMetaheuristic sẽ tìm thấy nghiệm đủ tốt với khối lượng tính toán íthơn nhiều so với các phương pháp kinh điển hoặc các phương phápheuristic đơn giản. Trên đây là lý do tôi chọn đề tài: Thuật toán Metaheuristicgiải bài toán tối ưu và phần mềm ứng dụng2. Mục đích nghiên cứu Luận văn tập trung nghiên cứu một số phương pháp tối ưu hiệnđại để giải quyết các bài toán tối ưu và phần mềm ứng dụng Matlab.3. Đối tượng và phạm vi nghiên cứu Đối tượng nghiên cứu của luận văn là một số phương pháp tối ưuhiện đại Phạm vi nghiên cứu của luận văn là hai thuật toán Metaheuristictìm nghiệm tối ưu (nội dung chính của luận văn) cùng với phần mềmứng dụng chạy thử nghiệm trên một số ví dụ cụ thể theo ngôn ngữlập trình Matlab. 24. Phương pháp nghiên cứu Phương pháp tham khảo tài liệu: Nghiên cứu các tài liệu trongnước và nước ngoài, giáo trình hoặc các bài báo liên quan có ở thưviện, bài giảng của giáo viên, Internet... Phương pháp trao đổi, thảo luận trực tiếp: với chuyên gia, đồngnghiệp, thầy hướng dẫn.5. Ý nghĩa khoa học và thực tiễn của đề tài Về mặt khoa học, luận văn cho người đọc hiểu được bản chấttoán học trong ứng dụng của khoa học kỹ thuật. Về mặt thực tiễn, đề tài sẽ tạo ra một tài liệu tham khảo có ích chonhững ai muốn thực hành tính toán thực sự trên máy tính với các bàitoán cụ thể.6. Cấu trúc của luận văn Ngoài phần mở đầu, kết luận và phần phụ lục, luận văn gồm 3chương: Chương 1: Bài toán tối ưu và các khái niệm Chương 2: Thuật toán heuristic tìm nghiệm tối ưu. Chương 3: Hai thuật toán Metaheuristic tìm nghiệm tối ưuvà Phần mềm ứng dụng 3 CHƢƠNG 1 BÀI TOÁN TỐI ƢU VÀ CÁC KHÁI NIỆM Trong chương này, trình bày mô hình toán học của bài toán tốiưu, các khái niệm cơ bản và các phương pháp sơ cấp.1.1. BÀI TOÁN TỐI ƢU n Ta có mô hình toán học của bài toán trên như sau: max  c j x j j 1  n  aij x j  bi i  1, m  với điều kiện:  j 1 x  0  j  j  1, n  1.1.1. Một số khái niệm cơ bản Dạng tổng quát của bài toán tối ưu được phát biểu như sau: min f  x  với điều kiện x  D,  P1 hoặc max f  x  với điều kiện x  D.  P2 trong đó, D  n gọi là tập nghiệm chấp nhận được và f : D là hàm mục tiêu. Mỗi điểm x  D gọi là một nghiệm chấp nhậnđượcChú ý 1.1. h ng gi m t ng qu t t ch t ài to n  P1  min  f  x  | x  D    max   f  x  | x  D  ,và tập c c lời gi i tối ưu cho h i ài to n này trùng nh u. Do đó tcó thể đư ài to n tìm cực đại về ài to n tìm cực tiểu và ngược lại. 4 Không phải bài toán  P1  nào cũng có nghiệm cực tiểu toàn cụcvà nếu bài toán có nghiệm cực tiểu toàn cục thì cũng chưa chắc cónghiệm cực tiểu toàn cục chặt. Xem minh họa Hình 1.1. Nghiệm cực tiểu h ng có nghiệm Nghiệm cực ...