So sánh một số phương pháp tìm nghiệm tối ưu xây dựng trên cơ sở mô phỏng quá trình tự nhiên

Bài báo giới thiệu kết quả nghiên cứu, đánh giá một số thuật toán tìm kiếm nghiệm tối ưu được xây dựng trên cơ sở mô phỏng quá trình tự nhiên ứng dụng để giải các bài toán trong kỹ thuật. Kết quả nghiên cứu có thể giúp định hướng chọn thuật toán phù hợp cho một số bài toán cụ thể.
Nội dung trích xuất từ tài liệu:
So sánh một số phương pháp tìm nghiệm tối ưu xây dựng trên cơ sở mô phỏng quá trình tự nhiên Cơ kỹ thuật & Kỹ thuật cơ khí động lực So s¸nh Mét sè ph­¬ng ph¸p t×m nghiÖm tèi ­u x©y dùng trªn c¬ së m« pháng qu¸ tr×nh tù nhiªn NGUYỄN TRANG MINH Tóm tắt: Bài báo giới thiệu kết quả nghiên cứu, đánh giá một số thuật toán tìm kiếm nghiệm tối ưu được xây dựng trên cơ sở mô phỏng quá trình tự nhiên ứng dụng để giải các bài toán trong kỹ thuật. Kết quả nghiên cứu có thể giúp định hướng chọn thuật toán phù hợp cho một số bài toán cụ thể. Từ khóa: Thuật giải di truyền, Thuật mô phỏng luyện kim, Thuật tiến hóa vi phân. 1. ĐẶT VẤN ĐỀ Dạng toán học của bài toán tối ưu tổng quát được viết như sau: Tìm giá trị cực tiểu (hoặc cực đại) hàm: f  x   min(max); x  R n (1) Với các điều kiện ràng buộc: gi  x   0; i  1, 2,..., , m (2) hi  x   0; i  1, 2,..., l. Bài toán đặt ra yêu cầu là tìm tập hợp các biến {xi}; i = 1, 2, …, n thoả mãn các điều kiện ràng buộc đồng thời hàm f(x) đạt giá trị cực tiểu (hoặc cực đại). Hàm f(x) được gọi là hàm mục tiêu - biểu diễn mối quan hệ giữa tiêu chuẩn chất lượng của quá trình khảo sát và các biến độc lập x. Các hàm số gi(x), hi(x) là các điều kiện ràng buộc của bài toán tối ưu. Trong không gian các biến, các hàm số này tạo ra miền giới hạn D các khả năng cho phép của hàm f(x). Trong miền cho phép D nếu hàm f(x) đơn điệu và tồn tại một cực trị thì nghiệm tìm được luôn luôn là duy nhất. Tuy vậy trong thực tế không phải lúc nào cũng vậy, ví dụ như hàm Peaks [2]- hai biến là hàm đơn điệu đa cực trị, được biểu diễn bằng đồ thị như hình 1. 2 2 x 2 2 1 2 2 f ( x)  3.(1  x1 )2 .e(  x1 ( x2 1) )  10.( 1  x13  x25 ).e(  x1  x2 )  .e(  ( x1 1)  x2 ) ; (3) 5 3 Hình 1. Hàm Peaks và các đường mức. Từ đồ thị hình 1 cho thấy, xung quanh phương án tốt nhất (điểm A đạt giá trị Min) còn có điểm B đạt cực trị địa phương và một số điểm nghi ngờ cực trị khác. Với phương pháp số xây dựng trên cơ sở các thuật toán truyền thống, trong quá trình giải, rất có khả năng kết quả cho là một điểm cực trị địa phương nào đó chứ không phải điểm Min trong toàn miền khảo sát. Hay nói một cách khác, thuật toán đã hội tụ sớm. Điều này hay xảy ra với 158 Nguyễn Trang Minh, “So sánh một số phương pháp … mô phỏng quá trình tự nhiên.” Nghiên cứu khoa học công nghệ những bài toán có số chiều lớn và hàm mục tiêu không liên tục. Vì vậy, việc phát triển các thuật toán đủ tin cậy để tìm nghiệm tối ưu toàn cục luôn được nhiều nhà khoa học quan tâm. Với sự phát triển mạnh của kỹ thuật tính toán trên máy tính điện tử đã xuất hiện một số thuật toán tìm nghiệm tối ưu dựa trên cơ sở mô phỏng các quá trình xảy ra trong tự nhiên. Điển hình là: - Thuật giải di truyền (GA- Genetic Algorithms) - Thuật mô phỏng luyện kim (SA- Simulated Annealing Algorithm) - Thuật tiến hoá vi phân (DE- Differential Evolution Algorithm) Đây là các thuật toán thuộc lớp các thuật giải xác suất, cả ba thuật toán trên chủ yếu dựa vào giá trị hàm mục tiêu không phụ thuộc vào đặc điểm của hàm và các biến. Những thuật toán này cũng chỉ hoạt động được nhờ kỹ thuật số. Cả ba thuật toán đều đã được ứng dụng để giải những bài toán tối ưu khó trong nhiều lĩnh vực của khoa học kỹ thuật. 2. NGUYÊN LÝ VÀ THUẬT TOÁN 2.1. Thuật giải di truyền 2.1.1 Nguyên lý hoạt động Thuật toán di truyền - GA do D.E. Goldberg đề xuất năm 1968, sau này được phát triển bởi L.Davis và Z.Michalevicz. Đây là thuật toán hình thành từ việc nhận mô phỏng lại quá trình tiến hóa của tự nhiên. Trong quá trình tiến hoá, các thế hệ mới được sinh ra bổ sung, thay cho thế hệ cũ, cá thể nào phát triển hơn thích ứng hơn với môi trường sẽ tồn tại, cá thể nào kém thích ứng hơn sẽ bị đào thải. Như vậy thuật toán di truyền mô phỏng ba quá trình tiến hoá cơ bản: Tái sinh và lựa chọn (Reproduction - Selection) Lai ghép (Crossover) Đột biến (Mutation) Để thực hiện được những thuật toán trên trước tiên cần tiến hành mã hóa các biến. Có hai phiên bản được sử dụng là phiên bản mã thực và phiên bản mã nhị phân. Trong phiên bản mã nhị phân, mỗi một chuỗi nhị phân với chiều dài xác định (chuỗi nhiễm sắc thể hay còn gọi là “gen”) sẽ tương ứng với một lời giải của bài toán đang khảo sát. Quá trình tiến hoá sẽ được thực hiện trên một tập các ...