Thuật toán Metaheuristic giải bài toán tối ưu và phần mềm ứng dụng
Trong bộ môn tối ưu toán học, phương pháp Metaheuristic được hiể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ấp hơn để có thể tìm ra nghiệm đủ tốt cho bài toán tối ưu, đặc biệt đối với các bài toán tối ưu với thông tin không đầy đủ hoặc đòi hỏi khối lượng tính toán quá lớn.
Phương pháp Metaheuristic được phát triển mạnh mẽ từ thập niê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ớp bài toán.. Hoặc, với tập chấp nhận được khá lớn, thì phương pháp Metaheuristic sẽ tìm thấy nghiệm đủ tốt với khối lượng tính toán ít hơn nhiều so với các phương pháp kinh điển hoặc các phương pháp heuristic đơn giản.
Trên đây là lý do tôi chọn đề tài: “Thuật toán Metaheuristic giải bài toán tối ưu và phần mềm ứng dụng”
2. 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 ưu hiện đại
Phạm vi nghiên cứu của luận văn là hai thuật toán Metaheuristic tì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.
Phương pháp tham khảo tài liệu: Nghiên cứu các tài liệu trong nướ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, đồng nghiệ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ất toá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 cho nhữ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ài toán cụ thể.
Ngoài phần mở đầu, kết luận và phần phụ lục, luận văn gồm 3 chươ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 ưu và Phần mềm ứng dụng
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.
Ta có mô hình toán học của bài toán trên như sau:
với điều kiệ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 với điều kiện
hoặc
max với điều kiện
trong đó, gọi là tập nghiệm chấp nhận được và là hàm mục tiêu. Mỗi điểm gọi là một nghiệm chấp nhận được
Chú ý 1.1. Không giảm tổng quát, ta chỉ xét bài toán
và tập các lời giải tối ưu cho hai bài toán này trùng nhau. Do đó, ta có thể đưa bài toán tìm cực đại về bài toán tìm cực tiểu và ngược lại.
Không phải bài toán nào cũng có nghiệm cực tiểu toàn cục và 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 toàn cục chặt
Không có nghiệm cực tiểu toàn cục
Nghiệm cực tiểu toàn cục không chặt
Hình 1.1: Hàm mục tiêu f(x) là hàm một biến
Giá trị tối ưu (hay giá trị cực tiểu) của bài toán được kí hiệu là: hoặc .
Nghiệm cực tiểu toàn cục chặt
Nghiệm cực tiểu địa phương chặt
Nghiệm cực tiểu địa phương không chặt
Hình 1.2: Minh họa về nghiệm cực tiểu địa phương, nghiệm cực tiểu địa phương chặt và nghiệm toàn cục chặt của hàm một biến f trên tập
Chú ý 1.2. Nếu thì ta nói bài toán là bài toán tối ưu không ràng buộc. Ngược lại, nếu thì ta nói bài toán là bài toán tối ưu có ràng buộc.
Chú ý 1.3. Nghiệm tối ưu toàn cục cũng là nghiệm tối ưu địa phương nhưng điều ngược lại chưa chắc đúng.
Mệnh đề 1.1.
Chú ý 1.4. Nếu bài toán không có nghiệm tối ưu thì giá trị tối ưu của bài toán này, ký hiệu là là cận dưới lớn nhất (hay giá trị infimum) của hàm f trên D.
1.1.2. Điều kiện tồn tại nghiệm
Mệnh đề 1.2. Điều kiện cần và đủ để bài toán có nghiệm tối ưu là tập đóng và có cận dưới hữu hạn.
Định lý 1.1.
Hệ quả 1.1. (Định lý Weierstrass) Nếu tập D là compact và hàm f liên tục trên D thì cả hai bài toán và đều có nghiệm tối ưu.
Định lý 1.2.
1.2. CÁC THUẬT TOÁN TÌM NGHIỆM SƠ CẤP
Bản chất của thuật toán sơ cấp này là lặp đi lặp lại thủ tục để có được nghiệm gần đúng (đôi khi cũng khá chính xác), bắt đầu từ một phương án dự đoán ban đầu.
Ví dụ 1.1. Tìm
Ta có với giá trị ban đầu và sau 5 lần lặp ta được kết quả khá chính xác
Phương pháp lặp nói trên để tìm là tương đương với tìm nghiệm của hàm . Đối với bất kỳ trong đoạn , phương pháp chia đôi hoạt động theo cách như thể hiện trong Hình 1.3.
Hình 1.3. Phương pháp chia đôi tìm thấy nghiệm
Ví dụ 1.2. Tính .
Ta có: . Chọn và (vì ), ta có
Điểm chia đôi đầu tiên, ta có cận dưới mới là
Điểm chia đôi thứ tư là
Đây là giá trị gần đúng bằng 2,5% giá trị đúng của
Nhìn chung, sự hội tụ của phương pháp chia đôi là rất chậm, phương pháp Newton là sự lựa chọn tốt hơn cho hầu hết các trường hợp.
Phương pháp của Newton là một phương pháp cổ điển sử dụng rộng rãi cho việc tìm nghiệm của một hàm phi tuyến đơn biến trên đoạn .
Hình 1.4. Phương pháp Newton cho nghiệm gần đúng
Tại bất kỳ điểm (xem hình 1.4), ta có hàm gần đúng nhờ khai triển Taylor từ về :
(1.7)
dẫn đến (1.8)
hoặc (1.9)
Ví dụ 1.3. Tìm nghiệm của
Ta sử dụng phương pháp Newton bắt đầu từ
Ta có:
Ta thấy rằng chỉ với 3 lần lặp có được là giá trị nghiệm gần đúng với nghiệm đúng là .
1.2.4. Phương pháp Newton dùng cho giải hệ phi tuyến
Cho hàm vectơ phi tuyến nhiều biến
(1.11)
trong đó cần một phương pháp lặp để tìm ra nghiệm
Ví dụ 1.4. Tìm nghiệm của hệ:
Trước hết ta có
Theo công thức lặp Newton-Raphson ta có
Nghiệm của bài toán là .
1.3. CHƯƠNG TRÌNH MATLAB GIẢI PHƯƠNG TRÌNH
1.3.1. Phương pháp lặp đơn
Trước hết, ta xây dựng hàm simpiter() để giải phương trình: sử dụng phương pháp lặp đơn
Để thực hiện ví dụ trên ta dùng chương trình vidu1_1.m
Ta được kết quả:
xx =
1
Hoi tu sau 7 lan lap
x =
2.2361
ss =
1.8829e-013
xx =
1.0000 3.0000 2.3333 2.2381 2.2361 2.2361 2.2361
1.3.2. Phương pháp chia đôi
Ta được kết quả:
hoi tu sau 20 lan lap
x = 1.7725
ss = 9.5367e-007
xx = 1.7724 1.7724 1.7725 1.7725 1.7725 1.7725
1.3.3. Phương pháp Newton-Raphson
Ta được kết quả:
Hoi tu sau 4 lan lap
x = 0.5671
ss = -1.1102e-016
xx = 1.0000 0.5379 0.5670 0.5671 0.5671
1.3.4. Phương pháp Newton dùng cho giải hệ phi tuyến
Sử dụng Matlab, tìm nghiệm của hệ:
CHƯƠNG 2
THUẬT TOÁN HEURISTIC TÌM NGHIỆM
2.1. BÀI TOÁN TỐI ƯU PHI TUYẾN KHÔNG RÀNG BUỘC
Hầu hết các bài toán tối ưu là phi tuyến, quy hoạch phi tuyến do đó một phần quan trọng của phương pháp tối ưu hóa toán học.
2.1.1. Bài toán cực trị hàm nhiều biến
Bài toán quy hoạch phi tuyến không ràng buộc được phát biểu như sau: với điều kiện
trong đó, là hàm phi tuyến.
Ví dụ 2.1. Xét hàm số
Ta có:
và
Tại điểm
và
Vì và là ma trận xác định dương, nên điểm là điểm cực tiểu địa phương của
Ví dụ 2.2. Tìm cực đại và cực tiểu của hàm số:
Giải phương trình
Ta có:
Tại ta có
Tại ta có
2.1.3. Bài toán hàm nhiều biến
Cho hàm nhiều biến bài toán tối ưu được phát biểu tương tự đối với hàm một biến:
Phương pháp Newton là một phương pháp lặp thông thường để tìm nghiệm của hàm phi tuyến một biến trên đoạn .
2.1.5. Phương pháp giảm nhanh nhất
Bản chất của phương pháp này là để tìm hàm mục tiêu thấp nhất có thể từ điểm .
Vì ta cố gắng tìm xấp xỉ thấp hơn (tốt hơn) cho hàm mục tiêu, cần số hạng vế phải là âm.
Ví dụ 2.3. Tìm cực tiểu của hàm
với
Áp dụng phương pháp hướng giảm bắt đầu với
Ta có:
Suy ra:
Sau đó, việc lặp lại cho đến khi đáp ứng được yêu cầu bài toán.
Trong tính toán, ta biết rằng công thức đạo hàm riêng của chúng bằng không.
Ta biết giá trị cực tiểu chính xác là
Phương pháp giảm nhanh nhất có được nghiệm gần đúng của bài toán chỉ sau 3 lần lặp.
2.1.6. Phương pháp tìm kiếm trực tiếp (Hooke-Jeeves-Wood)
Ví dụ 2.4. Tìm cực tiểu của hàm sau:
Chọn điểm cơ sở ban đầu độ dài bước Giá trị ban đầu
Đặt Xét tọa độ
Đặt đây là giá trị tốt nhất mới, Xét tọa độ
Đặt , giá trị ban đầu
Đặt Xét tọa độ
Đặt đây là giá trị tốt nhất mới, . Xét tọa độ
Đặt , giá trị ban đầu
Đặt
Tiếp tục dò tìm theo mẫu
Lặp lại một số lần dò tìm quanh với h nhỏ hơn 10 lần, sau mỗi lần dò tìm ta nhận được giá trị cực tiểu của hàm là 0 và điểm cực tiểu là .
F:\DỮ LIỆU COP CỦA CHỊ YẾN\DAI HOC DA NANG\LUAN VAN KY THUAT\LUAN VAN 2014\LUAN VAN TOAN SO CAP\NGUYEN QUANG THINH
