Tài liệu Thuật toán di tuyền song song và ứng dụng giải quyết bài toán Max-sa

ĐỀ TÀI: Thuật toán di tuyền song song và ứng dụng giải quyết bài toán Max-sa


MỤC LỤC
LỜI MỞ ĐẦU2
Chương I : Tổng quan 3
1. Tổng quan thuật toán di truyền 4
1.1 Khái niệm4
1.2 Cấu trúc của thuật toán di truyền 7
2. Ví dụ minh họa12
2.1 Bài toán Max-sat 12
2.2 Giải thuật di truyền giải quyêt bài toán Max-sat14
Chương II : Xây dựng thuật toán di truyền 14
1. Khung thiết kế thuật toán di truyền 15
1.1 Lớp provides – lớp cung cấp15
1.2 Lớp Requide – Lớp yêu cầu 16
2. Khung thuật toán tuần tự 20
3. Khung thuật toán song song 22
3.1 Lựa chọn phần cứng 22
3.2 Lựa chọn phần mềm22
Chương III : sử dụng khung thuật toán di truyền giải quyết bài toán Maxsat26
1. cài đặt bài toán Max-sat26
1.1 file cấu hình .cfg26
1.2 file đầu vào .dat 26
2. Sử dụng khung thuật toán di truyền giải bài toán Max-sat27
Chương III : Kết quả thực nghiệm 28
1. kết quả tuần tự 28
2.Kết quả song song28
LỜI MỞ ĐẦU
Với khả năng hiện nay, máy tính đã giúp giải được rất nhiều bài toán khó mà
trước đây thường bó tay. Mặc dù vậy vẫn có một số lớn các bài toán thú vị mà
chưa có giải thuật hợp lý để giải chúng. Trong đó các bài toán tối ưu là nững bài
toán thường gặp trong thực tiễn.
Trong thực tiễn, có nhiều bài toán tối ưu quan trọng đòi hỏi những thuật toán
có chất lượng cao. Ví dụ ta có thể dùng phương pháp mô phỏng luyện thép để
giải quyết bài toán tìm đường đi ngắn nhất cho xe cứu hỏa hay bài toán người du
lịch Cũng có nhiều bài toán tối ưu tổ hợp (trong đó có nhiều bài toán được
chúng minh là NP - đủ) có thể giải gần đúng trên máy tính hiện đại bằng kỹ thuật
Monte - Carlo.
Nói chung bài toán tối ưu có thể xem như bài toán tìm kiếm giải pháp tốt
nhất trong không gian vô cùng lớn các giải pháp. Khi không gian tìm kiếm nhỏ,
những phương pháp cổ điển như trên cũng đủ thích hợp, nhưng khi không gian
tìm kiếm lớn phải dùng kỹ thuật trí tuệ nhân tạo đặc biệt. Thuật giải di truyền
(GA) là một trong những kỹ thuật đó