Mục lục

Chương I: Tổng quan thuật toán mụ phỏng luyện kim (Simulated

Annealing = SA) 5

I. Giới thiệu chung về thuật toán SA .5

II. Mô hình toán học của thuật toán SA .8

1. Không gian trạng thái 8

2. Hàm nhiệt độ 9

3. Hàm chi phí và hàm sức khoẻ 10

4. Sự phân bố trạng thái giới hạn 11

5. Sự hội tụ và điều kiện dừng .12

Sự hội tụ .12

Điều kiện dừng .12

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

I. Lý do xây dựng khung thuật toán 13

II. Khung chung của thuật toán SA .13

III. Sơ đồ khung thuật toán 16

1. Lớp cung cấp (Provided) .17

2. Lớp đòi hỏi (Required) 22

3. Một số hàm quan trọng trong hai lớp Required và Provide .24

3.1. SA.pro.cpp 24

3.2. SA.req.cpp 25

Chương III: Ứng dụng của thuật toán SA .26

I. Bài toán MAXSAT 26

1. Giới thiệu bài toán 26

Hàm Main_Seq 29

III. Khung thuật toán SA song song giải quyết bài toán MAXSAT 30

1. Lựa chọn mô hình .30

2. Cài đặt Bài toán Maxsat. .31

2.1 Sử dụng thuật toán SA .31

2.1.1 Đọc file cấu hình .31

2.1.2 Lớp Problem đọc bài toán MAXSAT .31

2.1.3 Hàm khởi tạo nhiệt độ 33

2.1.4 Hàm khởi tạo lời giải 34

2.1.6 Hàm tính sức khoẻ 36

2.1.7 Hàm chấp nhận lời giải 37

2.1.8 . Hàm kết thúc thuật toán 38

2.2 Hàm void Solver_Lan::DoStep() .38

2.3 Hàm Main_Lan .39

Kết quả thực nghiệm 40

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

2. Kết quả song song 4