tailieunhanh - Báo cáo nghiên cứu khoa học: "PHƯƠNG PHÁP GIẢI BÀI TOÁN TỐI ƯU HÀM NHIỀU BIẾN BẰNG THUẬT TOÁN SONG SONG VÀ DI TRUYỀN"

Các phương pháp giải bài toán tối ưu của hàm nhiều biến được biết đến khá sớm trong toán học. Nhưng đối với một số bài toán phức tạp các phương pháp này khó có thể tìm kiếm được lời giải tối ưu. | TẠP CHÍ KHOA HỌC Đại học Huế Số 59 2010 PHƯƠNG PHÁP GIẢI BÀI TOÁN TỐI ƯU HÀM NHIỀU BIẾN BẰNG THUẬT TOÁN SONG SONG VÀ DI TRUYỀN Nguyễn Mậu Hân Nguyễn Đình Quý Nguyễn Hoàng Hà Trường Đại học Khoa học Đại học Huế TÓM TẮT Các phương pháp giải bài toán tối ưu của hàm nhiều biến được biết đến khá sớm trong toán học. Nhưng đối với một số bài toán phức tạp các phương pháp này khó có thể tìm kiếm được lời giải tối ưu. Trong phạm vi bài báo này chúng tôi đề xuất phương pháp giải bài toán tối ưu hàm nhiều biến bằng cách sử dụng giải thuật di truyền và tính toán song song. 1. Giới thiệu Xử lý song song là xử lý trên nhiều bộ xử lý và các bộ xử lý này phải tham gia giải quyết cùng một bài toán 1 4 5 . Xử lý song song cần kết hợp giữa lập trình song song và thuật toán song song. Thông thường để tối ưu hóa một hàm số nào đó người ta phải tính đạo hàm rồi tìm những điểm mà tại đó đạo hàm triệt tiêu. Tuy nhiên đối với các hàm phức tạp thì việc này khó thực hiện. Giải thuật di truyền Genetic Algorithms - GA là một trong những giải thuật thích hợp nhất cho vấn đề này. Tuy nhiên thời gian chạy GA là rất dài đối với bài toán có không gian tìm kiếm lớn. Mặt khác GA là một giải thuật mang bản chất song song luôn duy trì n lời giải chứa trong quần thể vì vậy song song hóa GA là hướng tiếp cận phù hợp cho việc cải thiện thời gian tính toán. 2. Lập trình song song và thuật toán song song Trong môi trường song song ở cùng một thời điểm có thể có nhiều hơn một chương trình được thực hiện nghĩa là mỗi chương trình sẽ tự thực hiện các tiến trình của mình và chúng tương tác với nhau để không làm ảnh hưởng tới nhịp độ thực hiện của nhau 6 7 . Do đó người lập trình không chỉ viết chương trình dữ liệu như trong môi trường tuần tự mà còn phải cung cấp các công cụ để đồng bộ hoá và điều khiển sự tương tác giữa các tiến trình. Lập trình song song có các cách tiếp cận tương ứng với các loại kiến trúc của các máy tính song song như lập trình song song kiểu SIMD kiểu MIMD với bộ nhớ chia sẻ hay phân tán

TỪ KHÓA LIÊN QUAN