Báo cáo khoa học: SO SÁNH MỘT SỐ PHƯƠNG PHÁP TÌM KIẾM TỐI ƯU ỨNG DỤNG TRONG KỸ THUẬT

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 tối ưu dựa trên cơ sở mô phỏng Monte - Carlo đang được ứng dụng để giải các bài toán kỹ thuật trên thế giới. Kết quả nghiên cứu có thể áp dụng cho bài toán tối ưu ứng dụng.
Nội dung trích xuất từ tài liệu:
Báo cáo khoa học: "SO SÁNH MỘT SỐ PHƯƠNG PHÁP TÌM KIẾM TỐI ƯU ỨNG DỤNG TRONG KỸ THUẬT" SO SÁNH MỘT SỐ PH ƯƠNG PHÁP TÌM KIẾM TỐI ƯU ỨNG DỤNG TRONG KỸ THUẬT TS. NGUYỄN QUÁN THĂNG Phòng Khoa học Công nghệ MT Bộ Tư lệnh Công binh TS. NGUYỄN TUẤN ANH Bộ môn Kỹ thuật ATGT Trường Đại học Giao thông Vận tải ThS. NGUYỄN THẾ MINH Bộ môn Xe máy Công binh Học viện Kỹ thuật Quân sự 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 tối ưu dựa trên cơ sở mô phỏng Monte - Carlo đang được ứng dụng để giải các bài toán kỹ thuật trên thế giới. Kết quả nghiên cứu có thể áp dụng cho bài toán tối ưu ứng dụng. Summary: The article is introduced about result searched and evaluated for some optimal method bese on Monte - Carlo simulation that be using in the world. The result can be apllied for optimal mechanism design. CT 2I. ĐẶT VẤN ĐỀ1.1. Xác định nhiệm vụ của bài toán tối ưu Trong k ỹ thuật, khi giải quyết bất kỳ nhiệm vụ nào chúng ta đ ều mong muốn có phương ántốt nhất theo một hoặc một vài tiêu chí nào đó. Có thể liệt kê rất nhiều những ví dụ cụ thể như:tiết kiệm thời gian nhất, chi phí nhỏ nhất, năng suất lớn nhất, quãng đường đi ngắn nhất, thiết kếkết cấu với trọng lượng vật liệu nhỏ nhất… Để giải được những bài toán này, toán học đã cho rađời một ngành là “Quy hoạch toán học” hay “tối ưu hóa” [1], [3]. Bài toán tối ưu nói chung được viết dưới dạng toán học 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: gi(x) ≥ 0; i = 1,2,... , m 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, … ,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). Thực ra tìm cực tiểu hoặc cực đại trong toán học không khác nhau nhiều (dùng phép biến đổi hàm ngược), do vậy trong bài báo này chủ yếu ta xét bài toán tìm cực tiểu. Hàm f(x) trong biểu thức (1) đ ược gọi là hàm mục tiêu hoặc tiêu chuẩn tối ư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 dưới dạng đẳng thức và bất đẳng thức. 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). Nếu như D  Rn (với R là số chiều của hàm mục tiêu), có nghĩa là không tồn tại bất kỳ một điều kiện giới hạn nào ta nói rằng bài toán quy hoạch phi tuyến không có điều kiện ràng buộc. Tuy nhiên trong phần lớn các b ài toán tối ưu, người sử dụng thường có băn khoăn đó là: kết quả nhận được từ quá trình tính đã thật sự là phương án tốt nhất chưa. Để minh họa vấn đ ề này ta có thể xét 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ư trên hình 1. (-x12-(x2 +1)2 ) (-x2-x2 ) 1 (-(x +1)2-x2 ) x f(x) = 3.(1- x1)2.e -10.( 1 - x1 - x5 ).e 1 2 - .e 1 3 2 (2) 2 5 3CT 2 Hình 1. Minh hoạ tối ưu toàn cục Như trên hình 1, xung quanh phương án t ốt nhất (ở đây chọn là điểm thấp nhất - đi ểm A) còn có một điểm đạt cực trị địa phương là điểm B và một số điểm nghi ngờ có cực tiểu khác. Trong quá trình giải, rất có khả năng kết quả giải b ài toán tối ưu của chúng ta bị kẹt tại một cực trị nào đó (không phải điểm A) và không thoát ra được. Vì vậy, việc phát triển các thuật toán đủ mạnh tiệm cận đ ược giá trị tối ưu luôn được người làm kỹ thuật quan tâm. 1.2. Các dạng bài toán tìm kiếm tối ưu dựa trên cơ sở mô phỏng Monte - Carlo ...