SỬ DỤNG THUẬT TOÁN LUYỆN KIM SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT
Chương I: ................................................................................................................ 3
Tổng quan thuật toán mô phỏng luyện kim (Simulated Annealing = SA) ........ 3
Sự hội tụ ................................................................................................................................................ 9
Điều kiện dừng ...................................................................................................................................... 9
Chương II: ............................................................................................................... 9
Xây dựng khung thuật toán SA .............................................................................. 9
Hàm Main_Seq ........................................................................................................................................ 22
Kết quả thực nghiệm ................................................................................................................................... 31
1. Kết quả tuần tự ................................................................................................................................... 31
2. Kết quả song song ............................................................................................................................... 31
TRƯƠNG THỊ THÚY LAN(K54A) – KIỀU TUẤN DŨNG(K55B) - NGUYỄN MINH CHÂU K55B 1
SỬ DỤNG THUẬT TOÁN LUYỆN KIM SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT
BÁO CÁO KHOA HỌC
ĐỂ TÀI:
THUẬT TOÁN LUYỆN KIM SONG SONG
(Parallel Simulated Annealing Algorithms)
GIẢI QUYẾT BÀI TOÁN MAX-SAT
MỞ ĐẦU
- Nhiều bài toán tối ưu chưa có thuật toán chính xác để giải quyết cho nên cần có một
thuật toán gần đúng để tìm lời giải gần tối ưu.
- Không gian lời giải cần tìm là rất lớn nếu một máy tính tìm kiếm sẽ rất lâu nên cần
nhiều máy giải quyết và các máy phải thực hiện đồng thời. Điều này có thể thực hiện dễ
dàng nếu các máy tính tính toán song song. Vì vậy việc tìm hiểu về các thuật toán song
song là cần thiết và mang tính khả thi đối với các bài toán tối ưu
- Để rút ngắn thời gian lập trình chúng ta cần xây dựng khung thuật toán giúp giải quyết
các bài toán khác nhanh chóng hơn.
- Mục đích của đề tài này là sử dụng thuật toán luyện kim song song để giải quyết bài
toán tối ưu MAXSAT. Đề tài bao gồm các nhiệm vụ sau:
• Nghiên cứu lý thuyết về thuật toán luyện kim
• Xây dựng khung thuật toán chung cho các bài toán sử dụng thuật toán luyện kim

Trạng thái ban đầu
Local Minimum:
Tối ưu địa phương
Global Minimum:
Tối ưu toàn cục
SỬ DỤNG THUẬT TOÁN LUYỆN KIM SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT
xảy ra từ từ thì chất rắn không đạt được trạng thái có cấu hình năng lượng thấp sẽ
đông lạnh đến một trạng thái không ổn định (cấu trúc tối ưu địa phương)
 Gọi E là năng lượng của trạng thái s, E’ là trạng thái năng lượng của trạng thái s’
và ∆E = E’ – E là sự chệnh lệch nhiệt độ giữa trạng thái s’ và trạng thái s. Nếu
∆E ≤ 0 thì sự thay đổi kết quả được chấp nhận với xác suất
T
B
kE
e
/
∆−
trong đó
T là nhiệt độ, k
B
là một hằng số vật lý được gọi là hằng số Boltzmann.
 Nếu có số lượng lớn các bước lặp được thực hiện ở mỗi nhiệt độ, hệ thống sẽ đạt
trạng thái cân bằng nhiệt. Khi đó, sự phân bố xác suất của hệ thống trong trạng
thái s ở nhiệt độ T là
T
B
kE
e
TZ
/

Nhiệt độ giảm
k = k+1; l = 0;
Đông lạnh?
T ≤ T
cuối
Đạt tới cực tiểu toàn cục
l = l + 1;
No
No
k, l: là biến điều khiển
vòng lặp
l đánh dấu việc lặp lại ở
nhiệt độ T
k
,
k tăng khi đạt cân bằng
nhiệt ở nhiệt độ T
k.
T
k
và s
k
điều khiển quá
trình xử lý ngẫu nhiên
SỬ DỤNG THUẬT TOÁN LUYỆN KIM SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT
II. Mô hình toán học của thuật toán SA
1. Không gian trạng thái
 SA thực thi trong một không gian trạng thái. Không gian trạng thái là một tập
hợp các trạng thái, mỗi trạng thái đại diện cho một cấu hình. Kí hiệu không gian
trạng thái là S, số phần tử của không gian trạng thái là |S|.

.
 Có hai trạng thái s
i
và s
i-1
và xác suất để s
i
là trạng thái hiện thời phụ thuộc vào
hàm chi phí của s
i
và hàm chi phí của s
i-1
và nhiệt độ T.
 Có ba trạng thái liên tiếp s
i-1
, s
i
, s
i+1
thì trạng thái s
i-1
và s
i+1
không phục thuộc
vào nhau.
TRƯƠNG THỊ THÚY LAN(K54A) – KIỀU TUẤN DŨNG(K55B) - NGUYỄN MINH CHÂU K55B 5
SỬ DỤNG THUẬT TOÁN LUYỆN KIM SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT
 Xác suất mà s’ là trạng thái kế tiếp của s kí hiệu là P(s,s’,T) gọi là xác suất
chuyển tiếp.






∀
∀
∀
=
∑
∈
∈
≠
∈
=
∉
1
'
)',(
0)',(
)',(
0)',(
)',(
Ns
ss
Ss
ss
ss
ss
ss
β

1
+
=fitness
Sự giảm bớt chi phí tương đương với sự tăng của hàm sức khoẻ
Giá trị hàm sức khoẻ tăng khi nhiệt độ giảm thể hiện trong biểu đồ:
4. Sự phân bố trạng thái giới hạn
TRƯƠNG THỊ THÚY LAN(K54A) – KIỀU TUẤN DŨNG(K55B) - NGUYỄN MINH CHÂU K55B 7
T
o
: nhiệt độ khởi đầu
T
n
: nhiệt độ kết thúc
T
i
: nhiệt độ vòng i khi i
= 1,..,N
N
N
i
T
T
TT
1
0
0





TTk
k
ππ
=
∞→
lim
Trên thực tế có thể chứng minh rằng:
∑
∈
−
−
=
∞→
S
j
s
T
j
sf
T
i
sf
i
S
Tk
k
)/)(exp(
)/)(exp(
)(
lim

 →
0

)()(
exp
)/)(exp(
)/)(exp(

)(
)(
T
T
i
sf
j
sf
T
j
sf
T
i
sf
k
j
S
Tk
i
S
Tk
π

Tk
π
- Ngoài ra có thể chứng minh rằng nếu s là một lời giải tối ưu thì
||
1
)(
lim
0
lim
opt
S
s
Tk
Tk
=
→∞→
π
Ở đây S
opt
là tập tất cả các lời giải tối ưu.
5. Sự hội tụ và điều kiện dừng
TRƯƠNG THỊ THÚY LAN(K54A) – KIỀU TUẤN DŨNG(K55B) - NGUYỄN MINH CHÂU K55B 8
SỬ DỤNG THUẬT TOÁN LUYỆN KIM SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT
Sự hội tụ
Cho không gian tìm kiếm hữu hạn S, điều kiện đủ cho sự hội tụ là sự cân bằng
chi tiết (detail balance) phụ thuộc vào xác suất giữa hai lời giải bất kỳ sj , si
trong không gian trạng thái là bằng nhau:
)().()().( T
ji
T

Nếu P là tối giản và không có chu kỳ thì tồn tại một xác suất ổn định duy nhất π.
Điều kiện đủ cho tính không chu kỳ là tồn tại trạng thái s
i
є S sao cho P
ii
≠ 0.
Điều kiện dừng
 Thuật toán dừng khi đã tìm được một lời giải đủ tốt và T là quá nhỏ mà xác
suất tránh được là không đáng kể.
 Một tiêu chuẩn kết thúc khác là chi phí trung bình thay đổi không đáng kể ở
một vài giá trị liên tiếp nhau của T
Chương II:
Xây dựng khung thuật toán SA
I. Lý do xây dựng khung thuật toán
Chúng ta cần xây dựng khung chung cho thuật toán nhằm đảm bảo:
• Giảm thiểu quá trình code cho người sau
• Cho những người sau thử nghiệm bài toán trên lập trình song song
• Việc xây dựng khung sẽ khiến người đọc hiểu được tổng quan thuật toán
và cách cài đặt thuật toán một cách nhanh hơn. Giúp cho người sau học có tính
khoa học hơn.
TRƯƠNG THỊ THÚY LAN(K54A) – KIỀU TUẤN DŨNG(K55B) - NGUYỄN MINH CHÂU K55B 9
SỬ DỤNG THUẬT TOÁN LUYỆN KIM SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT
II. Khung chung của thuật toán SA
 Tất cả các bài toán giải bằng SA đều thực hiện theo các bước:
• Bước 1: Đầu tiên, tìm điểm xuất phát của bài toán
• Bước 2: Liệt kê các láng giềng có thể có của lời giải hiện thời
• Bước 3: Tiến hành ước lượng hàm mục tiêu hiện thời và hàm mục tiêu
của láng giềng vừa tìm được
• Bước 4: Sinh một biến ngẫu nhiên thường là phân bố mũ có các tham số
phụ thuộc vào hiệu quả của các giá trị hàm mục tiêu và tham số T.

)) then
{
S  NewS; (*Chấp nhận lời giải*)
If (cost(NewS) < cost(BestS)) then
BestS  NewS;
}
Until (M mod MarkovChain_length == 0);
End;(* of metropolis)
Trong đó:
o Thủ tục nhận lời giải s ở nhiệt độ T và cải thiện nó qua sự tìm kiếm địa
phương
o M là số phép lặp ở nhiệt độ T
o Hàm neighbor sinh ra lời giải mới NewS
o Hàm Gain: độ chênh lệch hàm chi phí của lời giải S và lời giải mới
NewS tức là gain = chi phí của S – chi phí của NewS.
o Random là số ngẫu nhiên từ 0 đến 1
o Nếu chi phí NewS thấp hơn chi phí của S thì chấp nhận lời giải NewS
còn nếu chi phí NewS lớn hơn chi phí của S thì vẫn chấp nhận lời giải
NewS nhưng với xác suất là radom < e
gain/K
B
T
o Nếu NewS được chấp nhận sẽ so sánh với BestS. Nếu cost(BestS) >
cost(NewS ) thì BestS được thay thế bởi NewS . Còn không thì vẫn giữ
nguyên lời giải BestS và tiếp tục thực hiện vòng lặp.
 Thuật toán SA
Algorthm Simulated_Annealing

Begin


hình các thông số của thuật toán trong file cấu hình SA.cfg bao gồm:
o // số bước chạy độc lập
o // số ước lượng
o // Markov-Chain Length
o // độ giảm nhiệt độ
o // có hiển thị trạng thái ?
o LAN-configuration
o // trạng thái toàn cục được cập nhật trong n ước lượng
o // 0: asynchronized mode // 1: synchronized mode
o // số bước lặp để phối hợp ( nếu là 0 không phối hợp)
 Thuật toán SA có thể chạy được cả ở môi trường tuần tự và môi trường song
song.
III. Sơ đồ khung thuật toán
 SA có hai phân lớp chính là lớp Required (lớp đòi hỏi) và lớp Provided (lớp
cung cấp) được thể hiện trong hình vẽ dưới đây
TRƯƠNG THỊ THÚY LAN(K54A) – KIỀU TUẤN DŨNG(K55B) - NGUYỄN MINH CHÂU K55B
12