Giải thuật di truyền song song và ứng dụng giải bài toán Max- Sat

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 đó.

NỘI DUNG:

LỜI MỞ ĐẦU……………………………………………………………………2

Chương I : Tổng quan ….………………………………………………………..3

1. Tổng quan thuật toán di truyền ………………………………………………4

1.1 Khái niệm……………………………………………………………………..4

1.2 Cấu trúc của thuật toán di truyền …………………………………………….7

2. Ví dụ minh họa………………………………………………………………12

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-sat……………………………..14

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ấp………………………………………………..15

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ềm………………………………………………………….22

Chương III : sử dụng khung thuật toán di truyền giải quyết bài toán Maxsat……26

1. cài đặt bài toán Max-sat………………………………………………………...26

1.1 file cấu hình .cfg……………………………………………………………….26

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-sat……………………..27

Chương III : Kết quả thực nghiệm ………………………………………………..28

1. kết quả tuần tự …………………………………………………………………..28

2.Kết quả song song……………………………………………………………….28

LINK DOWNLOAD