[FONT=Times New Roman]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 đó