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. Nhưng bằng cách kết hợp thêm phương pháp tối ưu ngẫu nhiên (stochastic) người ta vẫn tìm thấy nghiệm đử tốt dựa trên tập các biến ngẫu nhiê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 và nội dung nghiên cứu
Mục đích nghiên cứu của luận văn là nhằm hiểu biết thấu đáo về các phương pháp tối ưu hiện đại.
Nội dung nghiên cứu là
(1) Hệ thống lại các thuật toán heuristic tìm nghiệm tối ưu (tối ưu không ràng buộc, tối ưu phi tuyến).
(2) 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.
4. Ý nghĩa khoa học và thực tiễn của đề tài
Về mặt khoa học, đề tài 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 (chẳng hạn bài toán xác định bộ gen người). 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: Cơ bản về tối ưu hóa.
Chương 2: Thuật toán heuristic tìm nghiệm tối ưu.
2.1. Phương pháp tìm nghiệm của bài toán tối ưu không ràng buộc
2.2. Bài toán quy hoạch phi tuyến
Chương 3: Hai thuật toán Metaheuristic tìm nghiệm tối ưu và Phần mềm ứng dụng
Tối ưu hóa xuất hiện hầu khắp mọi nơi, từ sản xuất kinh doanh đến thiết kế kỹ thuật, từ lập kế hoạch kỳ nghỉ của bạn đến chọn công việc cho tương lai. Do đó, các nghiên cứu về tối ưu hóa luôn có ý nghĩa khoa học và thực tế, đặc biệt các phương pháp giải quyết bài toán tối ưu có vai trò ứng dụng to lớn.
Trong chương này, trình bày các khái niệm cơ bản về bài toán tối ưu và các thuật giải sơ cấp.
Xét bài toán thực tế có thể đưa về bài toán tối ưu sau:
Bài toán. Một xí nghiệp sản xuất n loại sản phẩm cần sử dụng m loại nguyên liệu khác nhau. Gọi là số lượng sản phẩm thứ và là lãi thu được của một sản phẩm thứ j. Biết rằng để sản xuất một sản phẩm loại j cần một lượng nguyên liệu . Gọi là số lượng tối đa của nguyên liệu i mà xí nghiệp có. Bài toán đặt ra là hãy sản xuất mỗi loại sản phẩm với số lượng bao nhiêu để tổng lợi nhuận thu được là lớn nhất.
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:
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 đó, được gọi là tập nghiệm chấp nhận được hay tập ràng buộc và là hàm mục tiêu. Mỗi điểm được gọi là một nghiệm chấp nhận được hay một phương án chấp nhận được.
Không giảm tổng quát, ta chỉ xét bài toán .
Điểm thỏa mãn được gọi là nghiệm tối ưu, hoặc nghiệm tối ưu toàn cục, hoặc nghiệm cực tiểu toàn cục hoặc chỉ đơn giản là nghiệm của bài toán .
Điểm được gọi là nghiệm cực tiểu toàn cục chặt nếu:
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
và .
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 là trường hợp hàm mục tiêu 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 .
Nếu bài toán có nghiệm tối ưu là thì . Ta ký hiệu là tập nghiệm tối ưu của bài toán . Nếu bài toán chỉ có một nghiệm tối ưu thì có thể viết .
Điểm được gọi là nghiệm tối ưu địa phương chặt hoặc nghiệm cực tiểu địa phương chặt của bài toán nếu tồn tại một -lân cận của điểm sao cho: và
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
Hình 1.2 minh họa ví dụ 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 .
Các khái niệm tương tự cũng được định nghĩa cho bài toán .
Chú ý 1.1. 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. Trong bài toán tối ưu có ràng buộc, tập D thường được xác định bởi
với là các hàm thực xác định trên tập (thông thường ). Ta gọi là các hàm ràng buộc. Mỗi hệ thức được gọi là một ràng buộc của bài toán. Vì ràng buộc
và
Nên rõ ràng biểu diễn (1.1) bao gồm hết các loại ràng buộc.
Chú ý 1.2. 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. Tuy nhiên, nếu D là tập lồi và là hàm lồi thì nghiệm tối ưu địa phương của bài toán cũng là nghiệm tối ưu toàn cục. Cụ thể,
Mệnh đề 1.1. Cho hàm lồi và tập lồi khác rỗng . Xét bài toán . Khi đó:
- Nếu là một nghiệm tối ưu địa phương của bài toán này thì cũng là nghiệm tối ưu toàn cục.
- Nếu là một nghiệm tối ưu địa phương chặt hoặc là hàm lồi chặt thì là nghiệm tối ưu toàn cục duy nhất của bài toán.
Chứng minh: (Xem bản đầy đủ)
Chú ý 1.3. 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 trên
Giả sử, 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 trên bé nhất (hay giá trị supremum) của hàm f trên D .
Nhắc lại, thì và
sao cho .
Tương tự, thì và sao cho .
Mục đích của quy hoạch toán học là nghiên cứu tính chất của tập nghiệm và xây dựng các thuật toán để tìm nghiệm của bài toán tối ưu. Câu hỏi đầu tiên đặt ra là: “Bài toán cần giải có nghiệm tối ưu hay không?”
Xét bài toán tối ưu , có bốn phương án có thể xảy ra:
- Bài toán không có phương án chấp nhận được, tức
- Bài toán có nghiệm tối ưu, tức tồn tại sao cho: và giá trị tối ưu của bài toán là ;
- Bài toán không có nghiệm tối ưu và giá trị hàm mục tiêu giảm vô hạn trên tập chấp nghiệm được D, tức giá trị tối ưu ;
- Bài toán không có nghiệm tối ưu và giá trị tối ưu là hữu hạn.
Như vậy trừ trường hợp tập chấp nhận được bằng rỗng, giá trị tối ưu của bài toán luôn tồn tại nhưng nghiệm tối ưu thì không nhất thiết tồn tại. Việc tìm kiếm điều kiện đảm bảo để bài toán có nghiệm tối ưu là vấn đề quan trọng.
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.
Chứng minh: (Xem bản đầy đủ)
Định lý 1.1. Cho D là tập compact khác rỗng. Khi đó:
- Nếu hàm f nửa liên tục dưới trên D thì bài toán có nghiệm tối ưu.
- Nếu hàm f nửa liên tục trên trên D thì bài toán có nghiệm tối ưu.
Chứng minh: (Xem bản đầy đủ)
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.
Chứng minh: Hàm liên tục là hàm nửa liên tục trên và nửa liên tục dưới. Như vậy hệ quả trên được trực tiếp suy ra từ định lý 1.1. □
Nếu tập khác rỗng D chỉ đóng mà không bị chặn và hàm f nửa liên tục dưới trên D thì nói chung, có thể hàm f không đạt cực tiểu trên D, tức bài toán không có nghiệm tối ưu. Tuy nhiên,
Định lý 1.2. Cho tập đóng khác rỗng Nếu hàm là nửa liên tục dưới trên D và thỏa mãn điều kiện bức (coercive) trên D: khi và , thì bài toán có nghiệm tối ưu.
Chứng minh. (Xem bản đầy đủ)
Bản chất của việc tìm kiếm các nghiệm của một bài toán tối ưu tương đương với việc tìm kiếm điểm tới hạn (điểm cực trị). Để tìm điểm tới hạn, chúng ta thường giải quyết các điều kiện dừng khi đạo hàm cấp một bằng không, tuy vậy sẽ có sự khác nhau cơ bản khi điểm cực trị đạt tại các biên. Do đó, tìm hiểu các thuật toán sơ cấp rất quan trọng.
Ví dụ 1.1. Tìm
Ta có với giá trị ban đầu và lặp 5 lần như sau:
Như vậy, 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
của
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ứ hai: :
ta có cận dưới mới là
Điểm chia đôi thứ ba: :
ta có cận trên 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
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 (hay còn gọi là phương pháp Newton-Raphson).
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ề :
dẫn đến
hoặc
Hình 1.4. Phương pháp Newton cho nghiệm gần đúng
bởi từ giá trị trước đó
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ó:
Theo công thức (1.8) ta có:
Xuất phát . Ta có:
và
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à .
Thí 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ó
Trong đó, ma trận Jacobi J là:
với ma trận nghịch đảo là:
Đặt , ta có
Xuất phát từ ta có ước lượng thứ nhất
Với lần lặp thứ hai, ta có
Tiếp tục quá trình như trên, ta có
Cuối cùng, với lần lặp thứ tư
Nghiệm chính xác của bài toán là . Ta nhận thấy rằng sau bốn lần lặp ta đã ước lượng gần đúng với giá trị chính xác.
THUẬT TOÁN HEURISTIC TÌM NGHIỆM
2.1. Bài toán tối ưu không ràng buộc
Bài toán tối ưu không ràng buộc đơn giản mà việc tìm nghiệm không gặp khó khăn có lẽ là bài toán tìm kiếm cực đại hoặc cực tiểu của hàm đơn biến .
Ví dụ 2.1. Tìm cực đại và cực tiểu của hàm số:
Lời giải. Giải phương trình . Tức là,
Vì nên
Ta có:
Tại ta có suy ra giá trị cực đại
Tại ta có suy ra giá trị cực tiểu
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:
Cho hàm là hàm bậc hai. Theo phép khai triển Taylor tại sao cho
trong đó, và là vector gradient và ma trận Hessian, với đủ nhỏ, là vector. Chẳng hạn: ta có
với
Do đó để tìm hiểu hàm bậc hai, ta tìm hiểu và . Hơn nữa, để đơn giản chọn vì là hằng số bất kỳ.
Tại điểm dừng thì . Do đó, biểu thức trở thành
Nếu thì là một giá trị riêng. Cho ma trận cấp có giá trị riêng với vector riêng Vì ma trận đối xứng nên các vector riêng trực giao. Tức là
Bất kỳ lân cận của điểm dừng nếu thì ta có
là một biến thể của , khi chuyển từ điểm dừng dọc theo hướng là đặc trưng bởi các giá trị riêng. Nếu dẫn đến Nói cách khác, tăng khi tăng. Ngược lại, nếu thì giảm khi tăng. Đặc biệt, khi đó hàm không thay đổi theo hướng tương ứng.
Cho trước hàm liên tục khả vi, ta có khai triển Taylor tại điểm (với )
đây là điểm tới hạn khi là nghiệm của phương trình tuyến tính sau
Điều này dẫn đến
trong đó là ma trận Hessian. Nếu thủ tục lặp bắt đầu từ vector thì công thức lặp của Newton cho lần thứ n là
Để tăng tốc độ hội tụ, ta thường xét bước nhỏ hơn vì vậy phương pháp Newton được sửa đổi
2.1.4. 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 . Từ phép khai triển Taylor hàm tại ta có:
trong đó,là vector số gia. 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. Tức là:
Trong giải tích, ta đã biết tích của hai vector u và v là lớn nhất khi chúng cùng phương nhưng hướng ngược nhau. Vì vậy, nhỏ nhất khi
trong đó, là số bước. Trong trường hợp này, khihướng giảm theo hướng giảm âm. Như ta đã nêu ở trên, đây là phương pháp bán Newton.
Việc lựa chọn số bước là rất quan trọng. Một số bước nhỏ có nghĩa là di chuyển theo hướng cực tiểu địa phương, trong khi với số bước lớn hơn rất có thể vượt qua và tiến ra xa cực tiểu địa phương. Do đó, phải khác nhau sau mỗi bước lặp và phải chọn để cực tiểu hóa hàm mục tiêu Vì vậy, phương pháp hướng giảm được viết lại như sau
Trong mỗi lần lặp, gradient và số bước cần được tính toán. Một lần nữa, việc chọn điểm khởi đầu và số bước là rất hữu ích.
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:
Tại bước lặp thứ nhất ta có
Chọn sao cho là giá trị cực tiểu, có nghĩa là
đạt cực tiểu. Điều này trở thành bài toán tối ưu cho biến độc lập .Tất cả các kỹ thuật giải bài toán tối ưu như phương pháp Newton có thể được sử dụng để tìm . Ta có thể tìm được nghiệm bằng cách thiết lập:
Suy ra:
Bước thứ hai, ta có:
Tương tự cực tiểu của hàm tại và có được hướng giảm mới
Bước lặp thứ ba, ta có:
Tương tự cực tiểu của hàm tại . Vì vậy,
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.2. Bài toán tối ưu phi tuyến
Quy hoạch phi tuyến thường được phân loại theo độ lồi của hàm xác định. Một điều thú vị của hàm lồi là thì tại là một cực tiểu toàn cục hoặc cực đại toàn cục của hàm lồi. Nếu một hàm là không lồi hoặc lõm thì để tìm cực tiểu toàn cục hoặc cực đại toàn cục thì khó khăn hơn nhiều.
2.2.1. Bài toán phi tuyến không ràng buộc
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.
Định lý 2.1. (Điều kiện bậc nhất) Cho hàm xác định, khả vi trên Nếu là nghiệm cực tiểu địa phương của bài toán thì .
Chứng minh. Do là nghiệm cực tiểu địa phương nên
Suy ra □
Định lý 2.2. Giả sử là hàm lồi khả vi trên Khi đó, là nghiệm cực tiểu toàn cục của bài toán khi và chỉ khi
Chứng minh. (Xem bản đầy đủ)
Định lý 2.3. (Điều kiện bậc hai) Giả sử hàm khả vi, liên tục hai lần trên Khi đó:
- Nếu là điểm cực tiểu địa phương của trên thì
- Ngược lại, nếu thì là điểm cực tiểu địa phương chặt của trên .
Chứng minh. (Xem bản đầy đủ)
Nhận xét 2.2.
Vì hai bài toán và maxtương đương với nhau theo định nghĩa tập nghiệm của hai bài toán là trùng nhau và giá trị tối ưu ngược dấu nên
- Nếu là điểm cực đại địa phương của f trên thì
- Ngược lại, nếu thì là điểm cực đại địa phương chặt của trên
Thí dụ 2.4. 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, theo định lý 2.3, điểm là điểm cực tiểu địa phương của trên nhưng không phải là điểm cực tiểu toàn cục của trên vì
Xét bài toán
trong đó là tập compact được xác định bởi
là các hàm khả vi, liên tục.
Mục này trình bày hai cách tiếp cận của phương pháp hàm phạt.
2.2.1.1. Phương pháp hàm phạt điểm trong
Định nghĩa 2.1. Hàm được gọi là hàm phạt điểm trong trên miền nếu thỏa mãn:
- liên tục trên tập hợp
- ta có
Xây dựng bài toán phụ
- Xây dựng hàm tham số một biến
- liên tục và
- đơn điệu giảm
- Xây dựng bài toán phụ
Đặt hàm với miền xây dựng bài toán phụ không ràng buộc
Thuật toán 2.1.
Bước chuẩn bị. Cho số đủ bé (để kiểm tra điều kiện dừng của thuật toán). Xác định điểm thỏa mãn Chọn tham số phạt và một số Đặt
Bước lặp
Bước Xuất phát từ giải bài toán tối ưu không ràng buộc nhận được nghiệm
Bước If Then Dừng thuật toán
(lấy là nghiệm tối ưu của bài toán 2.10)
Else Chuyển bước
Bước Đặt tham số phạt mới Đặt Chuyển về bước lặp k
2.2.1.2. Phương pháp hàm phạt điểm ngoài
Định nghĩa 2.2. Hàm được gọi là hàm phạt điểm ngoài trên miền của bài toán 2.10, nếu thỏa mãn:
- liên tục trên tập hợp
Xây dựng bài toán phụ
- Xây dựng hàm tham số một biến
- liên tục và
- đơn điệu tăng
- Với mỗi cố định xây dựng bài toán phụ
Đặt hàm với miền xây dựng bài toán phụ không ràng buộc
Thuật toán 2.2.
Bước chuẩn bị. Cho số đủ bé (để kiểm tra điều kiện dừng của thuật toán). Chọn điểm Chọn tham số phạt và một số Đặt
Bước lặp
Bước Xuất phát từ giải bài toán tối ưu không ràng buộc nhận được nghiệm
Bước If Then Dừng thuật toán
(lấy là nghiệm tối ưu của bài toán 2.10)
Else Chuyển bước
Bước Đặt tham số phạt mới Đặt Chuyển về bước lặp
2.2.3. Phương pháp nhân tử Lagrange
Nếu ta muốn tìm cực tiểu của hàm
với ràng buộc bởi phương trình phi tuyến thì ta có thể kết hợp hàm mục tiêu 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
trong đó là nhân tử Lagrange, một đại lượng vô hướng được xác định.
Nếu chúng ta có phương trình
thì ta cần nhân tử Lagrange Do đó, ta có
Yêu cầu của điều kiện dừng dẫn đến
và
Có phương trình sẽ xác định thành phần của và là nhân tử Lagrange.
Xét bài toán quy hoạch phi tuyến : trong đó là tập nghiệm của hệ:
trong đó và là các hàm số khả vi bất kỳ xác định trên có thể không lồi.
2.2.4.1. Khái niệm điều kiện chính quy
Cho là nghiệm chấp nhận được của bài toán . Đặt
là tập các chỉ số của các ràng buộc thỏa mãn chặt tại
Ký hiệu là tập hợp các vector thỏa mãn hệ tuyến tính:
Ta nói điều kiện chính quy được thỏa mãn tại nếu
Bổ đề 2.1. ta có
Chứng minh. (Xem bản đầy đủ)
Định lý 2.4. Điều kiện chính quy được thỏa mãn tại nếu có một trong các điều kiện sau:
- Các hàm và đều là các hàm afin;
- Các hàm là afin và là lồi và điều kiện Slater sau đây thỏa mãn và
- Các vector và là độc lập tuyến tính.
2.2.4.2. Định lý Karush-Kuhn-Tucker
Định lý 2.5. Cho các hàm và là các hàm khả vi liên tục trên một tập mở chứa X. Giả sử là điểm cực tiểu địa phương của bài toán và điều kiện chính quy thỏa mãn tại . Khi đó tồn tại các vector và sao cho:
Nếu là các hàm lồi và là hàm afin và thỏa mãn điều kiện chính quy thì cũng là điều kiện đủ để là lời giải của
Chứng minh. (Xem bản đầy đủ)
TÌM NGHIỆM TỐI ƯU VÀ PHẦN MỀM ỨNG DỤNG
Hai thuật toán trình bày ở chương 3 này là những thuật toán áp dụng phương pháp Metaheuristic, Meta ở đây có nghĩa là “cấp độ cao hơn” hay “siêu” và heuristic nghĩa là “tìm kiếm bằng cách thử và sai”
3.1. Phương pháp mô phỏng đàn chim di (PSO)
Thuật toán mô phỏng đàn chim di (PSO) do Eberhart và Kennedy phát triển năm 1995. Ý tưởng phát minh của các tác giả dựa trên tập tính di trú của đàn chim, hoặc đàn cá trong tự nhiên.
Mục đích của thuật toán là tìm nghiệm tối ưu toàn cục của hàm mục tiêu trên tập các vị trí tốt nhất hiện thời của cả đàn cho đến khi hàm mục tiêu không thể cải thiện được nữa (không thể nhỏ hơn được nữa), hoặc dừng sau hữu hạn bước.
3.1.1. Ngôn ngữ giả mã của thuật toán mô phỏng đàn chim di (PSO)
Các bước hiệu chỉnh của thuật toán mô phỏng đàn chim di được tóm tắt như đoạn chương trình giả lập dưới đây. Trong đó quỹ đạo chuyển động của con chim thứ i được vẽ như hình 3.1, là vị trí tốt nhất hiện thời của con chim thứ i và là nghiệm tối ưu toàn cục hiện thời của cả đàn xác định trên tập của n cá thể chim.
BEGIN
Hàm mục tiêu
Khởi tạo vị trí và vector của hạt
Ban đầu giá trị tại
While (điều kiện)
For duyệt qua tất cả và chiều
Tạo vận tốc mới bởi công thức 3.1
Tính vị trí mới
Đánh giá hàm mục tiêu tại vị trí mới
Tìm giá trị cực tiểu hiện tại
End for
Tìm vị trí hiện tại tốt nhất và toàn cục tốt nhất
End while
Xuất kết quả và
END.
Chim i
hướng có thể
Hình 3.1. Sơ đồ biểu diễn các chuyển động của các con chim trong PSO, di chuyển về vị trí toàn cục tốt nhất và vị trí tốt nhất hiện thời của mỗi con chim thứ .
Cho tương ứng là vector vị trí và vận tốc của con chim . Vector vận tốc mới được xác định bởi
(3.1)
trong đó, và là các vector ngẫu nhiên mà mỗi thành phần lấy giá trị thuộc đoạn . Tích Hadamard của hai ma trận được xác định bởi .
Giá trị ban đầu của có thể là các giá trị biên và
Các thông số gọi là hằng số gia tốc thường được xác định Vị trí mới có thể được cập nhật bởi công thức
(3.2)
Mặc dù có thể nhận giá trị bất kỳ, nhưng thông thường thuộc
3.1.2. Tăng tốc thuật toán mô phỏng đàn chim di (PSO)
Thuật toán PSO có nhiều biến thể được mở rộng so với thuật toán chuẩn và đáng chú ý nhất các thuật toán sử dụng hàm quán tính sao cho được thay thế bởi trong đó, có giá trị trong khoảng. Trong trường hợp đơn giản, hàm quán tính có thể lấy hằng số. Điều này tương đương với đám lớn trong bầy chim giữ sự ổn định chuyển động của cả bầy, do đó các thuật toán dự kiến sẽ hội tụ nhanh hơn.
Thuật toán PSO chuẩn (như trình bày ở phần 3.1.1) sử dụng cả toàn cục hiện tại tốt nhất và cá thể tốt nhất Lý do của việc sử dụng cá thể tốt nhất chủ yếu là để làm tăng sự đa dạng cho chất lượng của nghiệm. Tuy nhiên, sự đa dạng này có thể được mô phỏng bằng cách sử dụng tính ngẫu nhiên. Sau đó, không có lý do thuyết phục để sử dụng vị trí tốt nhất của từng con chim. Một phiên bản đơn giản, điều mà có thể đẩy nhanh sự hội tụ của thuật toán là chỉ sử dụng nghiệm toàn cục tốt nhất . Như vậy, trong tăng tốc thuật toán PSO, các vector vận tốc được tạo ra bởi
(3.3)
trong đó là một biến ngẫu nhiên có giá trị trong khoảng . Việc cập nhật vị trí chỉ đơn giản là
(3,4)
Để tăng sự hội tụ hơn nữa, ta cũng có thể cập nhật các vị trí trong một bước duy nhất
(3.5)
Phiên bản đơn giản này cũng có cấp độ hội tụ tương tự. Các giá trị chuẩn cho thuật toán tăng tốc PSO này là và tuy nhiên, và được khuyến cáo sử dụng cho các hàm mục tiêu đơn đỉnh.
Để tăng tốc thuật toán PSO nhanh hơn nữa thì cần giảm tính ngẫu nhiên khi chạy các bước lặp. Điều này có nghĩa là ta có thể sử dụng hàm đơn điệu giảm như
hoặc (3.6)
trong đó là giá trị ban đầu của tham số ngẫu nhiên, là số lần lặp hoặc số lượng bước, là một tham số điều khiển. Ví dụ, trong đoạn coding của chương trình này, ta có
(3.7)
trong đó Nhiều nghiên cứu cho thấy rằng các thuật toán PSO có thể tốt hơn các thuật toán di truyền và các thuật toán thông thường khác trong việc giải các bài toán tối ưu hóa. Điều này có được là do khả năng thông tin về vị trí toàn cục tốt nhất hiện tại cho phép sự hội tụ tốt hơn và nhanh hơn về hướng tối ưu. Hơn nữa, thuật toán này hầu như không tốn bộ nhớ vì nó không cần ghi lại các con đường chuyển động của mỗi con chim và hy vọng rằng nó có thể được cải tiến tốt hơn khi sử dụng bộ nhớ tạm thời.
3.1.3. Hàm có đồ thị đa đỉnh (Multimodal Function)
Hàm có đồ thị đa đỉnh thường được sử dụng để kiểm tra hiệu lực của các thuật toán mới. Ta có thể xây dựng hàm có đồ thị đa đỉnh sau đây (xem hình 3.2) để kiểm tra thuật toán đàn chim di:
(3.8)
trong đó Rõ ràng, đối với vấn đề cực tiểu ta có thể viết nó như sau:
(3.9)
Hình 3.2: Hàm Michaelewicz đạt cực tiểu toàn cục tại
Trong luận văn này, để đơn giản minh họa, chúng ta sẽ sử dụng hàm Michaelewicz cho việc chạy thử thuật toán Matlab.
Lý do xây dựng hàm kiểm tra thuật toán này là vì hàm có đồ thị nhiều đỉnh này có cực đại toàn cục trong miền xác định và nghiệm của nó là độc lập với Nếu rất nhỏ (chẳng hạn ) thì nhiều thuật toán đã vấp phải rất nhiều khó khăn để tìm thấy nghiệm tối ưu.
Đạo hàm đầu tiên của hàm (3.8) là
Do hàm đối xứng theo và , cực đại phải đạt trên đường và được xác định bởi
Bằng cách sử dụng và ta có
hoặc
Cực đại toàn cục xảy ra tại
.
Điều đó là chỉ ra rằng các nghiệm là độc lập với sao cho
3.1.4. Mã chương trình tăng tốc thuật toán PSO
Sau khi gõ đoạn mã dưới đây và lưu thành file pso_simpledemo.m, mở Matlab đánh dòng pso_simpledemo sẽ cho kết quả:
Với chương trình này, ta có thể tìm nghiệm tối ưu toàn cục chỉ trong một vài chục giây với giá trị tối ưu.
Và chương trình này phù hợp với hầu hết các máy tính cá nhân hiện tại.
Hình 3.3: Vị trí bắt đầu và vị trí cuối cùng của 20 con chim sau 10 bước lặp
Nếu chạy chương trình này, ta sẽ có giá trị tối ưu sau 200 lần đánh giá hàm mục tiêu (cho 20 con chim với 10 bước lặp). Kết quả hiển thị ở hình 3.3
3.1.5. Thuật toán đàn chim di (PSO) trong trường hợp bài toán có ràng buộc
Phần mềm vừa trình bày ở trên chỉ dùng cho bài toán tối ưu không ràng buộc. Với bài toán tối ưu có ràng buộc ta cần bổ sung vào chương trình các đẳng thức và bất đẳng thức ràng buộc. Tuy nhiên, chúng ta có hai cách tiếp cận: bổ sung trực tiếp vào chương trình các ràng buộc hoặc biến đổi về tối ưu hóa không ràng buộc.
Cách tiếp cận thứ nhất là kiểm tra tất cả các vị trí mới có thỏa mãn tất cả các ràng buộc. Các vị trí mới được loại bỏ nếu các ràng buộc không thỏa mãn. Sau đó, các nghiệm mới được đánh giá bằng cách sử dụng thủ tục PSO chuẩn. Bằng cách này, tất cả các nghiệm mới phải nằm trong miền chấp nhận được và tất cả các nghiệm ngoài miền chấp nhận không được chọn. Ví dụ, để cực đại hàm mục tiêu với ràng buộc thuật toán PSO chuẩn đã thảo luận trước đó được sử dụng, tuy nhiên, các vị trí mới của hạt được kiểm tra tại mỗi lần lặp sao cho đáp ứng được Nếu bất kỳ nào không thỏa mãn ràng buộc thì nó được thay thế bằng một vị trí khác thỏa mãn ràng buộc.
Cách tiếp cận thứ hai, ta có thể chuyển về bài toán tối ưu không ràng buộc bằng cách sử dụng phương pháp hàm phạt hoặc phương pháp nhân tử Lagrange như được thảo luận trong Chương 2. Sử dụng một tham số phạt trong ví dụ đơn giản sau đây, ta có hàm phạt
Đối với bất kỳ giá trị cố định của ta sẽ xác định mức độ chính xác của các nghiệm tương ứng, bấy giờ ta có thể tối ưu hóa như đối với bài toán tối ưu không ràng buộc chuẩn.
Có những biến thể khác cho bài toán tối ưu mô phỏng đàn chim di và thuật toán PSO thường được kết hợp với các thuật toán đã có khác để đưa ra các thuật toán lai. Trong thực tế, việc kết hợp này vẫn là một lĩnh vực nghiên cứu sôi động với nhiều kết quả nghiên cứu mới được công bố hàng năm.
3.2. Thuật toán mô phỏng quá trình tôi thép (SA)
Tìm một nghiệm tối ưu cho một bài toán tối ưu cụ thể là một nhiệm vụ vô cùng khó khăn. Điều này là do khi có một bài toán đủ lớn ta cần tìm kiếm thông qua một số lượng lớn các nghiệm khả thi để tìm thấy nghiệm tối ưu. Ngay cả với sức mạnh của máy tính hiện đại vẫn khó giải quyết vấn đề. Trong trường hợp này, do không thể tìm thấy chính xác một giải pháp tối ưu trong một khoảng thời gian hợp lý nên ta phải xét đến một giải pháp gần đúng nhất có thể.
Mô phỏng quá trình tôi thép (SA), là kỹ thuật tìm kiếm ngẫu nhiên nghiệm tối ưu toàn cục, nó mô phỏng quá trình tôi thép là quá trình thép được làm lạnh và đông cứng thành trạng thái tinh thể sao cho tốn ít năng lượng nhất và tinh thể đạt cỡ lớn nhất để hạn chế các khuyết điểm trong cấu trúc thép. Quá trình tôi thép liên quan đến việc điều khiển cẩn thận nhiệt độ và tốc độ làm lạnh, thường được gọi là quy trình tôi thép.
Áp dụng phương pháp mô phỏng quá trình tôi thép để giải bài toán tối ưu được bắt đầu từ năm 1983 bởi các tác giả tiên phong Kirkpatrick, Gelatt và Vecchi. Đến nay phương pháp này vẫn được nghiên cứu mở rộng.
Ý tưởng cơ bản của thuật toán mô phỏng quá trình tôi thép là dùng một phương pháp tìm kiếm ngẫu nhiên có khả năng không chỉ chấp nhận các sự thay đổi nghiệm làm cải thiện giá trị hàm mục tiêu (làm hàm mục tiêu giảm) mà còn chấp nhận luôn một số nghiệm không tốt. Ví dụ, một bài toán cực tiểu hóa thì bất cứ một di chuyển tốt hơn hoặc bất cứ thay đổi nào làm giảm hàm mục tiêu f thì đều được chấp nhận. Tuy nhiên, một số thay đổi làm tăng f cũng được chấp nhận với xác suất p nào đó. Xác suất p này gọi là xác suất chuyển đổi và được xác định bởi công thức
(3.10)
trong đó, k là hằng số của Boltzmann, T là nhiệt độ điều khiển quá trình tôi thép, là gia số năng lượng tại T độ.
Xác suất chuyển đổi này được dựa trên sự phân phối Boltzmann trong vật lý. Một liên kết đơn giản nhất của và hàm mục tiêu là sử dụng
(3.11)
trong đó, là hằng số.
Không mất tính tổng quát, ta chọn và . Như vậy, xác suất chỉ đơn giản trở thành
Ta thường sử dụng một số ngẫu nhiên làm ngưỡng. Vì vậy, nếu hoặc , thay đổi sẽ được chấp nhận.
Lựa chọn nhiệt độ thích hợp là điều vô cùng quan trọng. Với chuyển đổi cho trước, nếu quá lớn thì , tức là hầu hết các thay đổi sẽ được chấp nhận. Nếu quá nhỏ thì bất kỳ (nghiệm xấu) sẽ hiếm khi được chấp nhận vì và như vậy sự đa dạng của nghiệm bị hạn chế, nhưng bất kỳ cải thiện nào sẽ hầu như luôn được chấp nhận. Trong thực tế, trường hợp đặc biệt tương ứng với các phương pháp gradient bởi vì chỉ các nghiệm tốt hơn được chấp nhận và hệ thống chủ yếu giống như việc chỉ tụt xuống (hoặc chỉ leo lên) ngọn đồi. Do đó, nếu quá lớn thì hệ thống rơi vào trạng thái năng lượng cao và cực tiểu không dễ dàng xác định được. Nếu quá nhỏ thì hệ thống có thể bị kẹt tại cực tiểu địa phương (không phải là cực tiểu toàn cục) và không có đủ năng lượng để hệ thống thoát ra khỏi cực tiểu địa phương để khai thác những điểm cực tiểu toàn cục tiềm năng khác. Vì vậy, nhiệt độ thích hợp cần phải được tính toán.
Một vấn đề quan trọng khác là làm thế nào để điều khiển quá trình làm mát sao cho hệ thống nguội dần từ nhiệt độ cao đến trạng thái đóng băng cuối cùng để đạt cực tiểu toàn cục. Có nhiều cách để kiểm soát tốc độ làm mát hoặc giảm nhiệt độ. Có hai sơ đồ tôi thép (hoặc cách làm mát) thường được sử dụng: Làm mát tuyến tính và làm mát hình học.
Đối với quá trình làm mát tuyến tính, ta có hoặc , trong đó là nhiệt độ ban đầu, là số lần giả lặp. là tốc độ làm mát và được chọn sao cho khi (số lần lặp lớn nhất), thường chọn là .
Làm mát hình học cơ bản là làm giảm nhiệt độ bằng hệ số làm mát sao cho được thay bởi hoặc với .
Ưu điểm của cách thứ hai là khi , do đó không cần xác định số lần lặp lớn nhất . Với lý do này, ta sẽ sử dụng quá trình làm mát hình học. Quá trình làm mát cần phải đủ chậm để hệ thống dễ chuyển về trạng thái ổn định. Trong thực hành thường chọn
Cũng cần chú ý thêm rằng với nhiệt độ cho trước, thì việc đánh giá hàm mục tiêu nhiều lần là cần thiết. Nếu đánh giá quá ít thì hệ thống có nguy cơ hoạt động không ổn định và sau đó sẽ không hội tụ về điểm tối ưu toàn cục. Nếu đánh giá quá nhiều, thường sẽ tốn thời gian, hệ thống sẽ hội tụ quá chậm vì số lần lặp tăng cấp mũ so với cỡ bài toán (không gian p_chiều). Vì vậy, cần phải cân bằng số lượng đánh giá hàm mục tiêu và chất lượng nghiệm. Ta có thể chọn: có nhiều đánh giá tại vài mức nhiệt độ và một vài đánh giá ở nhiều mức nhiệt độ khác nhau. Có hai cách hay dùng để thiết lập số lần lặp: cố định hoặc thay đổi. Cách một, cố định số lần lặp tại mỗi mức nhiệt độ. Cách hai, tăng số bước lặp tại thời điểm có nhiệt độ thấp hơn để cực tiểu địa phương được khai thác đầy đủ.
3.2.3. Thuật toán mô phỏng quá trình tôi thép
Giả mã của thuật toán mô phỏng quá trình tôi thép được thể hiện như sau:
Begin
Hàm mục tiêu
Nhiệt độ ban đầu , giá trị ban đầu đoán là
Đặt nhiệt độ cuối cùng và số lần lặp lớn nhất
Xác định lịch trình làm mát
while and
Di chuyển ngẫu nhiên đến vị trí mới
Tính
Chấp nhận nghiệm mới nếu tốt hơn, tức là
If không tốt hơn
Khởi tạo một số ngẫu nhiên
Chấp nhận nếu
end if
Cập nhật và
end while
end
Trong đoạn mã giả lập trên, tìm nhiệt độ ban đầu thích hợp ta có thể sử dụng bất kỳ thông tin nào được biết trước của hàm mục tiêu. Nếu ta biết độ chênh cực đại của hàm mục tiêu ta có thể dùng nó để ước tính nhiệt độ ban đầu với xác suất cho trước . Khi đó Nếu ta không biết độ chênh cực đại của hàm mục tiêu thì có thể sử dụng một phương pháp heuristic để tính .
Hình 3.4. Đồ thị hàm Rosenbrock với cực tiểu toàn cục tại
3.2.4. Mã chương trình Matlab của thuật toán mô phỏng quá trình tôi thép
Gõ đoạn mã chương trình dưới đây, lưu thành file có tên là sa_simpledemo.m. Mở matlab gõ sa_simpledemo sẽ cho kết quả
Chuong trinh chay khoang mot phut!
F_min =
-Inf
T =
1
Ham muc tieu:(1-x).^2+100.*(y-x.^2).^2
So luong danh gia:1800
Best location:0.77455 0.57303
Best estimate:0.12321
Nội dung bản luận văn nhằm cung cấp cho người đọc những hiểu biết cơ bản về bài toán tối ưu hóa và các phương pháp giải để tìm nghiệm cực tiểu toàn cục của chúng, từ các phương pháp kinh điển đến các phương pháp hiện đại. Luận văn được chia thành 3 chương.
Chương 1. Cơ bản về tối ưu hóa. Chương này cho ta khái niệm bài toán tối ưu hóa, tức là tìm nghiệm để có giá trị cực tiểu trên một miền ràng buộc nào đó. Đồng thời, giới thiệu một số phương pháp cổ điển giải bài toán tối ưu một biến, có từ thời Newton, mà bạn đọc gặp đâu đó trong chương trình phổ thông nhưng chưa có dịp xem lại một cách hệ thống.
Chương 2. Thuật toán heuristic tìm nghiệm của bài toán tối ưu. Chương này giới thiệu hàng loạt phương pháp kinh điển được sử dụng thường xuyên trong nghiên cứu cũng như trong ứng dụng của ngành toán tối ưu để giải các bài toán tối ưu đa biến, phi tuyến. Tuy nhiên, điểm đáng nhấn mạnh là các thuật toán heuristic này, đặc biệt các thuật toán dựa trên tính khả vi của hàm mục tiêu và các hàm ràng buộc chỉ cho ta được nghiệm cực tiểu địa phương. Việc tìm nghiệm cực tiểu toàn cục là khó khăn, trừ trường hợp quy hoạch lồi.
Chương 3. Hai thuật toán Metaheuristic tìm nghiệm tối ưu và phần mềm ứng dụng.
Như đã trình bày ở chương 2, các phương pháp heuristic kinh điển tuy được sử dụng nhiều trong nhiều lĩnh vực kỹ thuật, kinh tế, xã hội và có nhiều thành tựu, nhưng một hạn chế lớn là dễ bị kẹt tại điểm dừng (đặc biệt các phương pháp khai thác tính khả vi) tức là tại nghiệm cực tiểu địa phương, rất khó thoát khỏi “bẫy địa phương” này để tìm đến nghiệm toàn cục.
Chương 3 cũng là chương cuối cùng, giới thiệu hai thuật toán hiện đại để tìm nghiệm toàn cục, hy vọng khắc chế được nhược điểm kẹt “bẫy địa phương” của các phương pháp heuristic đã biết. Hai thuật toán này gọi là thuật toán Metaheuristic với tên gọi
1 – Thuật toán mô phỏng đàn chim di (PSO)
2 – Thuật toán mô phỏng quá trình tôi thép (SA)
Tính heuristic của thuật toán thể hiện ở chỗ các tác giả nảy sinh ý tưởng dựa vào quan sát tập tính bay di trú của đàn chim tìm chỗ tốt nhất (ví dụ minimum ô nhiễm) hoặc quy trình tôi thép trong công nghiệp xử lý thép tại từng mức nhiệt hạ dần cho đến khi đạt chất lượng thép tốt nhất (minimum khuyết tật cấu trúc của thép). Việc tìm nghiệm mới bắt chước tự nhiên này đã cho kết quả khả quan.
Tính meta (tức “mức cao” hoặc “siêu” so với heuristic truyền thống) thể hiện ở chỗ tính heuristic kết hợp thêm tính ngẫu nhiên bằng bộ số phát ngẫu nhiên để điều chỉnh hướng tìm nghiệm mới nhằm hy vọng thoát khỏi “bẫy địa phương” để tìm được nghiệm tốt hơn. Điều này cũng là sự bắt chước tập tính phần lớn con chim bay theo hướng chung của đàn nhưng cũng có những con chim khác bay theo hướng ngẫu nhiên, nhờ đó hy vọng tìm được chỗ đậu tốt hơn chỗ đậu mà cả đàn đang theo.
Chương này còn có thêm nội dung thú vị là hai phần mềm được viết bằng ngôn ngữ Matlab cụ thể cho hai thuật toán Metaheuristic nêu trên. Người đọc có thể gõ code này để chạy kiểm chứng.
Do hạn chế về mặt thời gian và khuôn khổ luận văn được ấn định nên có một số vấn đề thú vị và hấp dẫn không đưa vào được luận văn. Tôi hy vọng sẽ tiếp tục nghiên cứu phát triển đề tài theo hướng này.
Luận văn này là một tài liệu bổ ích cho bản thân tác giả và hy vọng luận văn sẽ là tài liệu tham khảo bổ ích cho người đọc nhiều thông tin về hoạt động thời sự của ngành toán tối ưu hiện nay. Vì vậy, tôi rất mong nhận được sự góp ý, nhận xét của các thầy cô và đồng nghiệp.
E:\DỮ LIỆU COP CỦA CHỊ YẾN\DAI HOC DA NANG\LUAN VAN KY THUAT\THINH
