Lời nói đầu

Những năm gần đây, cùng với sự phát triển của khoa học kỹ thuật, người ta đã giải quyết được nhiều bài toán hóc búa bằng máy tính. Nhưng bên cạnh đó, vẫn còn khá nhiều các bài toán vẫn chưa tìm được giải thuật phù hợp để giải nó, đó là các bài toán tối ưu, trí tuệ nhân tạo và các bài toán xuất phát từ thực tế cuộc sống như bài toán lập lịch, bài toán điều khiển Robot, bài toán người du lịch, . Đây là các bài toán có khá nhiều ràng buộc phức tạp, không rõ ràng, ko gian tìm kiếm lớn. Do đó các phương pháp truyền thống như quay lui vét cạn, leo đồi, mô phỏng luyện thép, tỏ ra ít hiệu quả, và người ta đã sử dụng một phương pháp khá tối ưu đó là phương pháp CHC và sử dụng trong mô hình song song.

Trong bài nghiên cứu này nhóm tác giả nghiên cứu về phương pháp CHC sử dụng mô hình song song để giải quyết bài toán MAXSAT. Chúng ta sẽ thấy được sự độ tối ưu khi sử dụng mô hình song song so với mô hình tuần tự về thời gian, độ thích nghi

Trong tương lai nhóm sẽ tiếp tục phát triển đề tài nghiên cứu bằng cách sử dụng thuật toán để giải quyết một số bài toán khác.

Nhóm tác giả xin chân thành cảm ơn sự giúp đỡ tận tình của thầy giáo Đỗ Trung Kiên đã giúp cho nhóm trong quá trình thực hiện.

Cuối cùng xin chúc hội nghị nghiên cứu khoa học của chúng ta thành công rực rỡ.

Hà Nội, tháng 04 năm 2008.

Nhóm tác giả.

MỤC LỤC

Chương I: Tổng quan về phương pháp CHC 3

I. Tìm hiểu chung về thuật toán di truyền 3

II. Tổng quan về phương pháp CHC 4

1. Khái niệm 4

2. Tư tưởng của thuật toán CHC 4

3. Sự Chọn lọc Elitist 6

4. Tránh sự giao phối gần 7

Chương II: Xây dựng khung thuật toán CHC 8

I. Thiết kế khung thuật toán CHC 9

1. Các lớp đòi hỏi (Requires) 10

ã Lớp bài toán (Problem) 10

ã Lớp lời giải (Solution) 10

ã Lớp toán tử người sử dụng (Uer_Operator) 10

ã Lớp kiểm tra điều kiện dừng (StopCondition) 10

2. Các lớp cung cấp (Provided) 11

ã Lớp thiết lập tham số đầu vào (SetUpParams) 11

ã Lớp quần thể (Population) 11

ã Lớp lựa chọn (Selection) 12

ã Lớp chỉ định toán tử sử dụng (Intra_Operator): 13

ã Lớp định nghĩa giao diện toán tử (Inter_Operator) 13

ã Lớp lai ghép (Crossover) 13

ã Lớp thực thi giải thuật (Solver) 14

II. Khung thuật toán tuần tự 14

1. Hàm void Solver_Seq::DoStep() 14

III. Khung thuật toán song song 16

Chương III. Sử dụng khung thuật toán giải quyết bài toán MAXSAT 17

I. Đọc file cấu hình 17

II. Sử dụng khung thuật toán giải quyết bai toán MAXSAT 18

III. Kết quả thực nghiệm 24

1. Kết quả tuần tự 24

2. Kết quả song song 2