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

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:26

Thêm vào BST

Báo xấu

16
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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.40 TÓ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ăn tốt nghiệp thạc sĩ Khoa học tại Đại học Đà Nẵng vào ngày 10 thá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Ở ĐẦU 1. Lý do chọn đề tài 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.
2 4. 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 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ể. 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 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
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 được Chú ý 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 đó t có 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ụ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 h ng có nghiệm Nghiệm cực tiểu toàn cục chặt cực tiểu toàn cục 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  P1  được kí hiệu là: min f  x  hoặc min  f  x  | x  D . xD Nghiệm cực tiểu Nghiệm cực Nghiệm cực tiểu đị toàn cục chặt tiểu đị phương phương kh ng chặt 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 D  Chú ý 1.2. Nếu D  n thì ta nói bài toán  P1  là bài toán tối ưu không ràng buộc. Ngược lại, nếu D  n thì ta nói bài toán  P1  là bài toán tối ưu có ràng buộc.
5 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  P1  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à inf f  D  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à đủ để ài to n  P1  có nghiệm tối ưu là tập f  D   t  | t  f  x  , x  D đó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à comp ct và hàm f liên tục trên D thì c h i ài to n  P1  và  P2  đề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 1.2.1. Phƣơng pháp lặp đơn 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 5 Ta có k  5 với giá trị ban đầu x0  1 và sau 5 lần lặp ta được kết quả khá chính xác 5  2.236067977... 1.2.2. Phƣơng pháp chia đôi Phương pháp lặp nói trên để tìm x  k là tương đương với tìm
6 nghiệm của hàm f  x   x  k  0 . Đối với bất kỳ f  x  trong 2 đoạn  a, b , phương pháp chia đôi hoạt động theo cách như thể hiện trong Hình 1.3. f(x) A x xn xb * O xa x B Hình 1.3. Phương pháp chia đôi tìm thấy nghiệm x* của f  x   0, x  a, b Ví dụ 1.2. Tính  . Ta có: f  x   x    0 . Chọn xa  1 và xb  2 (vì   4 ), ta 2 có f  xa   1    0, f  xb   4    0. Điểm chia đôi đầu tiên, ta có cận dưới mới là xa  x1  1,5. 1 Điểm chia đôi thứ tư là x4   xa  xb   1,8125. 2
7 Đây là giá trị gần đúng bằng 2,5% giá trị đúng của   1,7724539509... 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. 1.2.3. Phƣơng pháp Newton 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 f  x   0 trên đoạn  a, b . f(x) A x * O xn x n+1 x B Hình 1.4. Phương pháp Newton cho nghiệm gần đúng x* bởi xn1 từ giá trị xn trước đó Tại bất kỳ điểm xn (xem hình 1.4), ta có hàm gần đúng nhờ khai triển Taylor từ x  xn1  xn về xn : f  xn1   f  xn  x   f  xn   f '  xn  .x (1.7) f  xn 1   f  xn  dẫn đến xn 1  xn  x  (1.8) f '  xn 
8 f  xn 1   f  xn  hoặc xn 1  xn  (1.9) f '  xn  Ví dụ 1.3. Tìm nghiệm của f  x   x  e  0 x Ta sử dụng phương pháp Newton bắt đầu từ x0  1 1  e1 Ta có: x1  1   0,5378828427; x2  0,5669869914 1  e1 x3  0,5671432859 Ta thấy rằng chỉ với 3 lần lặp có được x3 là giá trị nghiệm gần đúng với nghiệm đúng là x*  0,5671432904 . 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 F  x    F1  x  , F2  x  ,..., FN  x  T (1.11) trong đó x   x, y,..., z    x1 , x2 ,..., x p  cần một phương pháp lặp T T để tìm ra nghiệm F  x   0. Ví dụ 1.4. Tìm nghiệm của hệ: x  e y  0 ; x2  y  0. Trước hết ta có  x  e x2   x1   x  F  x    12  , x      .  x1  x2   x2   y  Theo công thức lặp Newton-Raphson ta có x n 1  x n  J 1 F  x n  . Nghiệm của bài toán là  0,6529186405;0,4263027510  .
9 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: x  g  x  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ệ: x  e y  0 ; x2  y  0.
10 CHƢƠNG 2 THUẬT TOÁN HEURISTIC TÌM NGHIỆM CỦA BÀI TOÁN TỐI ƢU 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: min f  x  với điều kiện x  n  2.1 trong đó, f : n  là hàm phi tuyến. Định lý 2.1. Định lý 2.2. Định lý 2.3. Nhận xét 2.1. Ví dụ 2.1. Xét hàm số f  x1 , x2   e 2  3x1e 2  x1 3x x 3  3e x2  3x12  Ta có: f  x    3 x2 x2   3e  3x1e   6 x1 3e x2  và  f  x    2 x   3e 9e  3x1e  x2 3 x2 Tại điểm x0  1,0  T  0  6 3  f  x 0     và  2 f  x0      0  3 6 
11 Vì f  x0   0 và  2 f  x 0  là ma trận xác định dương, nên điểm x0  1,0  là điểm cực tiểu địa phương của f T 2.1.2. Bài toán hàm đơn biến Ví dụ 2.2. Tìm cực đại và cực tiểu của hàm số: f  x   xe x ,    x   2 2 Giải phương trình e x  2 x2e x  0.  x   2 2 . 2 Ta có: f " x    4 x 2  6  xe x . 2  2 1  1 1 Tại x*  ta có f " x*   2 2.e 2  0  f max  e 2 . 2 2 1 2  1 1 Tại x*  ta có f " x*   2 2.e 2  0  f min   e 2 . 2 2 2.1.3. Bài toán hàm nhiều biến Cho hàm nhiều biến x   x1 , x2 ,..., xn   T 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: min/ max f  x . n x  2.1 2.1.4. Phƣơng pháp Newton 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 f  x  trên đoạn  a, b . 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 f  x  thấp nhất có thể từ điểm x n  .
12 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 f  x1 , x2   10 x12  5x1 x2  10  x2  3 2 với  x1 , x2   10,10  15,15 Áp dụng phương pháp hướng giảm bắt đầu với x0  10,15 T Ta có: f   20 x1  5x2 ,5x1  20 x2  60  T Suy ra: f  x0    275,290  T 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 f f bằng không.  20 x1  5 x2  0;  5 x1  20 x2  60  0. x1 x2 T  4 16  Ta biết giá trị cực tiểu chính xác là x*    ,   5 5 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: f  x1 , x2   3x1  4 x1 x2  5x22 . Chọn điểm cơ sở ban đầu v  b    4,3 , độ dài bước 1 T   h  1,   103. Giá trị ban đầu fb  f b1  141 Đặt v  b1 . Xét tọa độ x1
13 v  he1   5,3 , f  v  he1   180  f b  141 T v  he1   3,3 , f  v  he1   108  f b  141 T v : v  he1   3,3 T Đặt đây là giá trị tốt nhất mới, fb  f  v   108. Xét tọa độ x2 v  he2   3, 4  , f  v  he2   155  f b  108 T v  he2   3, 2  , f  v  he2   71  f b  108 T b 2 : v  he2   3,2   b1   4,3 , giá trị ban đầu T T Đặt   fb  f b 2  71. Đặt v  2b   b    2,1 , f  v   25  fb  25. Xét tọa độ x1 2 1 T v  he1   3,1 , f  v  he1   44  f b  25 T v  he1  1,1 , f  v  he1   12  fb  25 T v : v  he1  1,1 T Đặt đây là giá trị tốt nhất mới, fb  f  v   12 . Xét tọa độ x2 v  he2  1, 2  , f  v  he2   31  f b  12 T v  he2  1,0  , f  v  he2   3  f b  12 T b 2 : v  he2   3,2   b1   4,3 , giá trị ban đầu T T Đặt   fb  f b 2  71. Đặt b3 : v  he2  1,0   b 2   3,2  , fb  f b3  3 T T   Tiếp tục dò tìm theo mẫu
14 Lặp lại một số lần dò tìm quanh b1 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à  0,0  . T 2.2. BÀI TOÁN TỐI ƢU PHI TUYẾN CÓ RÀNG BUỘC 2.2.1. Phƣơng pháp nhân tử Lagrange Một phương pháp với giới hạn của tham số  là phương pháp nhân tử Lagrange. Nếu ta muốn tìm cực tiểu của hàm f  x  minn f  x  , x   x1 , x2 ,..., xn   T n , (2.18) x với ràng buộc bởi phương trình phi tuyến g  x   0, thì ta có thể kết hợp hàm mục tiêu f  x  với phương trình phi tuyến này để có một hàm mới được gọi là hàm Lagrange   f  x   g  x, trong đó  là nhân tử Lagrange, một đại lượng vô hướng được xác định. Ví dụ 2.5. Tìm cực đại của hàm f  x, y   xy 2 ,  x, y   2 thỏa mãn x 2  y 2  1 Giả sử g  x, y   x 2  y 2  1  0. Đặt   f  x, y    g  x, y   xy 2    x 2  y 2  1 Điều kiện dừng:     y 2  2 x  0;  2 xy  2 y  0;  x 2  y 2  1  0. x y  1 Giải hệ 3 phương trình trên ta được: x   3
15 Ta có 4 điểm dừng:  1 2   1  2   1 2   1  2  P1  ;  , P2  ;  , P3  ;  , P4  ;   3 3  3 3   3 3   3 3  Giá trị của hàm f  x, y  tại bốn điểm đó là: 2 2 2 2 f  P1   ; f  P1   ; f  P3   ; f  P4   3 3 3 3 3 3 3 3  1 2  1  2 Vậy hàm số đạt cực đại tại P1  ;  , P2  ;   3 3  3 3  2.2.2. Điều kiện Kuhn - Tucker Xét bài toán quy hoạch phi tuyến min  f  x  | x X, trong đó X  n là tập nghiệm của hệ:  gi  x   0, i  1,..., m,  (2.24) h j  x   0, j  1,..., k , trong đó f , gi ,  i  1,..., m  và h j ,  j  1,..., k  là các hàm số khả vi bất kỳ xác định trên n , có thể không lồi. a. Khái niệm điều kiện chính quy  Bổ đề. x0  X ta có T X , x0  S x0 .    Định lý 2.4. b. Định lý Karush-Kuhn-Tucker Định lý 2.5. 2.2.3. Phƣơng pháp hàm phạt Để giải bài toán tối ưu có ràng buộc (2.24) ta giải dãy bài toán tối ưu không ràng buộc với hàm mục tiêu phụ thuộc vào tham số 
16 min f  x    p  x  trong đó p  x  là hàm phạt. Các phương pháp hàm phạt chia thành hai nhóm: a. Phương pháp hàm phạt điểm trong Hàm p : n  được gọi là hàm phạt điểm trong trên miền D nếu thỏ mãn: a. p liên tục trên tập hợp D : x  0  n  | g j  0, j  1, m . b. xk   D0 , x k  k   x  D0 ta có lim p x k  . k    Xây dựng bài toán phụ  Bt  b. Phương pháp hàm phạt điểm ngoài Hàm p : n  được gọi là hàm phạt điểm ngoài trên miền D củ ài to n 2.24, nếu thỏ mãn: n a) p liên tục trên tập hợp b) p  x   0, x  D, p  x   0, x  D. Xây dựng bài toán phụ  Pt  Ví dụ 2.6. Tìm cực tiểu của hàm số sau: 1  f1  x    x1  1  0 f  x   x1  1  x2 với điều kiện 3  3  f 2  x    x2  0 1  1 1 Đặt   x,  :  x1  1  x2      3 3   x1  1 x2          x1  1   0;  1  2   0 2 Ta có: x1 1  x1  x2  2 x2 
17 Khi   0 thì min    f min ; x1    x1* ; x2    x2* . Chọn dãy  dần đến 0 ta tính được các giá trị tương ứng. 8 x1*  1; x2*  0; f min  . 3 2.3. MỘT SỐ CHƢƠNG TRÌNH LẬP TRÌNH MATLAB 2.3.1. Phƣơng pháp Newton bằng Matlab Trước hết, ta xây dựng hàm newtons(x) Xây dựng hàm tính Jacobian của hàm f(x) Để tìm cực tiểu của hàm f(x) bằng phương pháp Newton ta chạy chương trình ctnewtons.m Ta được kết quả: xo = -0.800000000000000 3.200000000000000 fo = 0 0 2.3.2. Phƣơng pháp giảm nhanh nhất bằng Matlab Tạo M-file trong phần mềm Matlab. Xây dựng chương trình steepest.m có nội dung như sau: Để tính gradient của hàm f(x), nhập chương trình có nội dung như sau, rồi lưu lại với tên grad.m Để thực hiện tính toán cực tiểu hàm mục tiêu f(x) ta chạy chương trình ctsteepest.m Kết quả sẽ cho xo = -0.799997670795486 3.200000186470315 fo = -5.999999999943229 2.3.3. Chƣơng trình Matlab tìm nghiệm của bài toán có ràng buộc Ví dụ 2.7. Tìm cực tiểu hàm Rosenbrock’s:
18 f  x   100  x2  x12   1  x1  thỏa mãn x1  x2  1 2 2 2 2 Bằng chương trình Matlab ta thực hiện lần lược như sau: Hình 2.1: Đồ thị hàm Rosenbrock's Trước hết, tạo file chứa hàm Rosenbrock’s: rosenbrock.m Xây dựng hàm chứa các ràng buộc: unitdisk.m Thực hiện chương trình sau 24 bước lặp ta được kết quả: Iter F-count f(x) Feasibility optimality step 0 3 1.000000e+000 0.000e+000 2.000e+000 1 13 7.753537e-001 0.000e+000 6.250e+000 1.768e-001 2 18 6.519648e-001 0.000e+000 9.048e+000 1.679e-001 21 75 4.568281e-002 0.000e+000 6.437e-005 3.974e-005 22 78 4.568281e-002 0.000e+000 8.000e-006 1.083e-007 23 81 4.567641e-002 0.000e+000 1.601e-006 2.793e-005 24 84 4.567482e-002 0.000e+000 2.437e-008 6.916e-006 Giá trị cực tiểu: 0.04567482475809566 tại (0.786,0.618)