1


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

2

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 40

3



4


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
 Áp dụng khung thuật toỏn luyện kim cho bài toỏn MAXSAT

5

 Cài đặt bài toán MAXSAT và đưa ra kết quả thực nghiệm trờn
cả chương trỡnh tuần tự và chương trỡnh song song.
 Từ đó sử dụng khung thuật toỏn luyện kim để giải quyết cỏc bài
toỏn tối ưu khỏc trong thực tế như: Bài toỏn người du lịch, bài
toỏn khụi phục ảnh, thiết kế mạch IC, bài toỏn sắp xếp thời
khoỏ biểu cho trường đại học…
Chương I:
Tổng quan thuật toỏn mụ phỏng luyện kim (Simulated Annealing = SA)
I. Giới thiệu chung về thuật toỏn SA

 SA là một thuật toỏn tỡm kiếm xỏc suất di truyền, là phương
pháp tối ưu hoá có thể áp dụng để tỡm kiếm tối ưu hoá toàn cục
của hàm chi phí và tránh tối ưu hoá địa phương bằng việc chấp
nhận một lời giải tồi hơn với một xác suất phụ thuộc nhiệt độ T.
 Sơ đồ:
Sơ đồ thể hiện trong một không gian lời giải thuật toán luyện kim
sẽ tỡm đến tối ưu toàn cục với bước nhảy từ tối ưu địa phương









Solution Space:
Khụng gian lời
giải
Initial State:
Trạng thái ban
đầu
Local Minimum:

T
ố
i
ư
u đ
ị

a


6

 Tiền thõn của SA là thuật toán Monte Carlo năm 1953 của
nhúm Metropolis. Thuật toán SA được đề xuất bởi S. Kirk _
partrick năm 1982 và được cụng bố trước công chúng năm 1983.
 SA cú nguồn gốc từ cơ học hệ thống. SA thực thi đơn giản
và tương tự quỏ trỡnh luyện kim vật lý. Trong luyện kim vật lý
kim loại được đốt núng tới nhiệt độ cao và làm lạnh từ từ để nú
kết tinh ở cấu hỡnh năng lượng thấp (tăng kích thước của tinh thể
và làm giảm những khuyết điểm của chỳng). Nếu việc làm lạnh
khụng 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
/
)(
1

trong đó Z(T): là hàm phân phối.
 SA sử dụng một biến điều khiển toàn cục là biến nhiệt độ T.
Ban đầu T ở giỏ trị rất cao và sau đó được giảm dần xuống.
Trong quỏ trỡnh tỡm kiếm SA thay lời giải hiện thời bằng cỏch
chọn ngẫu nhiờn lời giải lỏng giềng với một xỏc suất phụ thuộc

7

vào sự chờnh lệch giữa giỏ trị hàm mục tiờu và tham số điều
khiển T.
 Quỏ trỡnh tối ưu hoỏ được tiếp tục cho tới khi cực tiểu toàn
cục được tỡm thấy hoặc tổng số bước chuyển vượt quỏ một số tối
đa cỏc bước chuyển đó được định trước. Sự chuyển tiếp ở một
nhiệt độ kết thỳc khi đạt tới trạng thỏi cõn bằng nhiệt. Sauk hi đạt
tới trạng thỏi cõn bằng nhiệt thỡ nhiệt độ được giảm thấp hơn.
Nếu hệ thống khụng đông lạnh và cũng khụng tỡm được cực tiểu
toàn cục thỡ vũng lặp vẫn tiếp tục và chỉ số k tăng. Hệ thống
đông lạnh khi T tiến tới nhiệt độ T
cuối

do người dựng đưa ra. Ta
cú sơ đồ thuật toỏn.
















Yes

Yes

Kh
ở
i t
ạ
o k

=


l=

0;

L
ấ
y ng
ẫ
u nhi
ờ
n s
i
và phõn
tớch
T = T
; s = s
Tr
ạ
ng th
ỏ
i

cõn bằng nhiệt
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

l = l +

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


8



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|.
 Một quan hệ lỏng giềng trờn S:
SS




o Cỏc phần tử của à được gọi là cỏc di chuyển
o (s, s’) ê à kết nối qua một di chuyển được gọi là lỏng
giềng
o (s, s’) ê à
k
kết nối qua một tập k di chuyển
SS
k
k





1
U

 Tập trạng thỏi kết nối với trạng thái đó cho s
i
ê S được kớ
hiệu là N
i
, số phần tử của N
i
gọi là cấp độ của s
i
. N
i
là tập cỏc
lỏng giềng của s
i
.
 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.
 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.

9













''
1
' )',()),'(),((
),',(
)'',()),''(),((
s
ssssTss
TssP
ssTss






ỏ: hàm xỏc suất chấp nhận (acceptance probability
function)
õ: hàm xỏc suất lựa chọn (selection probability function)
õ cho phộp chỉ một cặp trạng thỏi trong ỡ được lựa chọn.
Xỏc suất lựa chọn khụng bao giờ bằng 0 cho một cặp trạng thái
được kết nối bởi một di chuyển đơn.


 


















1
'
)',(
0)',(
)',(
0)',(
)',(
Ns
ss
Ss
ss
ss
ss
ss







Hàm chấp nhận ỏ: R
3
+
 [0,1]

R
2. Hàm nhiệt độ
Đầu tiờn khởi tạo nhiệt độ T là T
0.
Quy trỡnh phổ biến nhất là quy
trỡnh làm lạnh cõn xứng: T
new
= T
old
* alpha khi alpha < 1.
Thuật toỏn kết thỳc khi T = 0.

10

Sơ đồ:









3. Hàm chi phớ và hàm sức khoẻ
Hàm đánh giá cost là hàm xác định chi phí được dùng để ước
lượng một lời giải đó cho. Hàm chi phớ của lời giải s kớ hiệu là
f(s).
Hàm sức khoẻ Fitness được định nghĩa:
%100*
cost1
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
đồ:

T
o
: nhiệt độ khởi
đầu
T
n
: nhiệt độ kết
thỳc
N
N
i
T
T

TT
1
0
0










11

4. Sự phõn bố trạng thỏi giới hạn
Cho ð
Tk
(s
i
) là xỏc suất mà s
i
là lời giải hiện thời sau k bước của
thuật toỏn ở nhiệt độ T.
Vectơ xỏc suất trạng thỏi: ð
Tk
= (ð
Tk
(s

1
), ð
Tk
(s
2
),…,ð
Tk
(s
i
),…). Cho
chuỗi Markov, vector xỏc suất trạng thỏi hội tụ tới 1 vộctơ xỏc
suất giới hạn
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


(Phõn bố Boltzmann)
 Phõn bố giới hạn cho T

0
- Cõn nhắc 2 lời giải s
i
và s
j
với f(s
i
) < f(s
j
). Trong trường hợp
này cú:








 








 
0

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

)(
)(
T
T
i
sf
j

sf
T
j
sf
T
i
sf
k
j
S
Tk
i
S
Tk



- Sự khẳng định cuối cựng là giả thiết 0)()(


i
sf
j
sf
- Hội tụ tới ∞ chỉ cú thể xảy ra nếu cú:
0)(
limlim
0



j
s
Tk
Tk


- Chứng minh rằng: Cho lời giải khả thi s, k∞ và T0 xỏc
suất ð
Tk
(s) hội tụ tới 0, nếu s khụng phải lời giải tối ưu
0)(
lim
0
lim


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ỡ

12

||
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
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
j
T
ij
T
i




Trong đó ð
i
(T) là sự phõn bố ổn định của trạng thỏi s
i
ở nhiệt độ
T.
Sự phõn phối ổn định là một vectơ
ð(T) = (ð
1
(T), ð
2
(T), …, ð
|s|
(T))
Thỏa món phương trỡnh: ð
T
(T)*P(T) = ð
T
(T)
P(T): ma trận chuyển tiếp
ð
T
: Hoỏn vị của ð.
|S| : là số phần tử của khụng gian trạng thỏi S.
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ể.

13

 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.
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.

14

 Bước 5: Nếu biến ngẫu nhiờn lớn hơn hoặc nhỏ hơn một
ngưỡng cho trước thỡ chấp nhận lỏng giềng vừa tỡm được
làm phương án hiện tại
 Bước 6: Giảm nhiệt độ T.
 Bước 7: Quay trở lại từ đầu
 Đó chứng minh được khi T  0 thỡ tỡm được lời giải tối ưu
toàn cục. Tại những giỏ trị nhiệt độ cao các bước chuyển được
chấp nhận một cỏch ngẫu nhiờn bất luận chúng là bước chuyển
cú cải thiện hàm chi phớ hay khụng. Khi nhiệt độ được giảm
xuống xỏc suất chấp nhận lời giải cú cải thiện tăng lên và xác
suất chấp nhận lời giải khụng cú cải thiện giảm xuống.
 Khung thuật toỏn SA gồm 3 lớp:
- Problem: Định nghĩa bài toỏn
- Solution: Định nghĩa lời giải
- Default Move: Định nghĩa sự chuyển đổi (sự phỏt sinh
lời giải mới)
 Thuật toỏn Metropolis heuristic:
Algorithm Metropolis (S,T,M)
(*Trả lại giỏ trị giảm của hàm chi phớ*)
Begin
Repeat
M = M + 1;
NewS  neighbor(S);(*sinh ra lời giải mới NewS*)
gain  Gain(NewS,S);(*chờnh lệch hàm chi phớ*)
If ((gain > 0) or (random < e

gain/K
B
T
)) then
{
S  NewS; (*Chấp nhận lời giải*)
If (cost(NewS) < cost(BestS)) then

15

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

Initialize(T); //khởi tạo nhiệt độ T
S
0
= Initial_Solution()// khởi tạo lời giải S
0

M = 0;
Repeat

16

Call Metropolis (S
0
,T,M) ;

T  alpha * T;//Cập nhật T

Until (T = 0)

Lời giải tốt nhất được tỡm thấy


End.


o alpha: tốc độ làm lạnh
o Thuật toỏn SA ban đầu khởi tạo nhiệt độ T và lời giải S
0

o Gọi hàm Metropolis để tỡm lời giải tốt nhất BestS. Sau
khi đó tỡm được lời giải tốt nhất thỡ cập nhật lại nhiệt độ T theo
thụng số alpha.Thực hiện vũng lặp cho tới khi T = 0 sẽ tỡm
được lời giải tốt nhất toàn cục của bài toỏn.
 Một điều quan trọng nữa là khi thực hiện thuật toỏn SA
người dựng phải cấu 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

17


 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

1. Lớp cung cấp (Provided)
 Provided: bao hàm cỏc thủ tục chung cho thuật toỏn SA và được
ỏp dụng cho hầu hết cỏc bài toỏn sử dụng thuật toỏn SA (vớ dụ
như khung của thuật toỏn SA tuần tự, khung của thuật toỏn SA
song song, thiết đặt cỏc thụng số của bài toỏn ). Bao gồm cỏc
lớp:
o SetupParams: Là một lớp quan trọng để đọc file cấu hỡnh
và khởi tạo cỏc giỏ trị trong file cấu hỡnh.

18

o Solver: Thực hiện cỏc chiến lược đưa ra và duy trỡ cỏc
thụng tin cú liờn quan tới trạng thỏi tỡm kiếm trong suốt
quỏ trỡnh thực hiện.
class Solver
{
protected:
const Problem& problem;
const SetUpParams& params;
UserStatistics _userstat;
Statistics _stat;
Move* move;
Solution current;
double curfit;
Solution tentative;

double currentTemperature;
unsigned int k; // to control temperature
update.
StateCenter _sc;
float total_time_spent;
float time_spent_in_trial;
float start_trial;
float start_global;
bool _end_trial;
State_Vble sol; // Một vector cỏc lời giải
tạm thời của bài toỏn
const Direction _direction;
bool AcceptQ(double tent, double cur, double
temperature);

19

// chấp nhận lời giải
double Set_Initial_Temperature(const Problem&
pbm);
// khởi tạo nhiệt độ của bài toỏn
void KeepHistory(const Solution& sol, const
double curfit,const float
time_spent_trial,const float
total_time_spent);
double UpdateT(double temp, int K);//cập nhật
nhiệt độ
public:
Solver (const Problem& pbm, const
SetUpParams& setup);

// Full execution
virtual void run () =0;
virtual void run (cú tham số) =0;
// Partial execution
virtual void StartUp () =0;
virtual void StartUp (cú tham số) =0;
virtual void DoStep () =0;
}
Cú 2 lớp kế thừa từ lớp Solver:
 Solver_Seq: Chứa cỏc thủ tục run() để giải quyết bài
toỏn một cỏch tuần tự
provides class Solver_Seq: public Solver
{
public:

20

Solver_Seq ( const Problem& pbm, const
SetUpParams& setup);
void run ();
virtual void run (unsigned long int
max_evaluations);
virtual void run (const Solution& sol, unsigned
long int max_evaluations);
virtual void run (const double
initialTemperature);
virtual void run (const Solution& sol,const double
initialTemperature);
virtual void run (const double initialTemperature,
unsigned long int nb_evaluations);

virtual void run (const Solution& sol,const double
initialTemperature, unsigned long int nb_evaluations);
// Partial execution
virtual void StartUp ();
virtual void StartUp (const Solution& sol);
virtual void StartUp (const double
initialTemperature);
virtual void StartUp (const Solution& sol, const
double initialTemperature);
virtual void DoStep ();
};
 Solver_Lan: Chứa thủ tục run(int argc, char** argv)
để giải quyết bài toỏn một cỏch song song trờn mụi
trường mạng LAN. Với tham số truyền vào của hàm

21

chớnh là cỏc tờn mỏy tham gia vào quỏ trỡnh tớnh
toỏn.
provides class Solver_Lan: public Solver
{
private:
NetStream _netstream;
int mypid;
void send_local_state_to(int _mypid);
int receive_local_state_from(int source_pid);
void check_for_refresh_global_state();
unsigned int _current_trial;
unsigned int _current_iteration;
double _best_cost_trial;

Solution _best_solution_trial;
float _time_best_found_in_trial;
unsigned int _iteration_best_found_in_trial;
double _temperature_best_found_in_trial;
int cooperation();
// Termination phase //
bool final_phase;
int acum_evaluations;
public:
Solver_Lan (const Problem& pbm, const
SetUpParams& setup,int argc,char **argv);
virtual ~Solver_Lan ();
virtual int pid() const;
NetStream& netstream();

22

void run ();
virtual void run (cú tham số);
………………
// Partial execution
virtual void StartUp ();
virtual void StartUp (cú tham số);
…………………
virtual void DoStep ();
void reset();
};
o Statistic: được ỏp dụng cho bất kỳ khung nào trong
MALLBA và bao gồm thụng tin cần để bảo đảm toỏn tử
thớch hợp của thuật toỏn.

o Stop_Condition: Điều kiện dừng của bài toỏn
o …….
2. Lớp đũi hỏi (Required)
 Required: bao hàm cỏc thủ tục riờng trong thuật toỏn SA của
từng bài toỏn cụ thể (vớ dụ như cỏc thủ tục tớnh nhiệt độ, thủ tục
tớnh hàm sức khoẻ, thủ tục sinh lời giải ).
 Cỏc lớp đũi hỏi được sử dụng để lưu trữ dữ liệu cơ bản của
thuật toỏn : bài toỏn, trạng thỏi khụng gian tỡm kiếm và vào/ra.
Bao gồm cỏc lớp:
o Problem: Mụ tả bài toỏn cần được giải quyết. Nhận cỏc
thụng số của bài toỏn từ file định nghĩa bài toỏn.
o Solution: Miờu tả tập lời giải cú thể được thực hiện.

23

o UserStatistic: lưu trữ thụng tin cuối cựng của bài toỏn :lời
giải tốt nhất, số đánh giá, thời gian thực thi,…
o DefaultMove: Thực hiện việc cập nhật lời giải mới của bài
toỏn.
o TerminateQ: Thực hiện điều kiện dừng của bài toỏn.
Ta cú sơ đồ khung thuật toỏn SA như sau:

Những lớp cú dấu * là cỏc lớp Required
Trong đó:
 NetStream: Là một lớp trung gian giữa khung và MPI dễ
dàng cho việc xử lý song song như hỡnh vẽ. (thể hiện việc
gửi nhận dữ liệu)

24



 State_Center: cho phộp tỡm kiếm một biến trạng thỏi, thờm
một biến trạng thỏi, và loại bỏ một biến trạng thỏi hoặc cập
nhật nội dung của một biến trạng thỏi. Tất cả cỏc trường hợp
của StateVariable được xếp bờn trong StateCenter
 State_Vble: cho phép định nghĩa và thiết đặt, lấy tờn cỏc
biến trạng thỏi.
3. Một số hàm quan trọng trong hai lớp Required và Provide
3.1. SA.pro.cpp
Một số hàm chớnh í nghĩa
istream& operator>> (istream&
is, SetUpParams& setup)
Đọc vào file cấu hỡnh
ostream& operator<< (ostream&
os, const SetUpParams& setup)
In ra file cấu hỡnh vừa đọc
được
Khởi tạo cỏc biến của
SetupParams

ostream& operator<< (ostream& In ra kết quả thụng kờ.

25

os, const Statistics& stats)
void Statistics::update(const
Solver& solver)
Cập nhật cỏc giỏ trị mới
Cỏc hàm của Slover tớnh toỏn cỏc giỏ trị như: thời gian, các
bước lặp, nhiệt độ hiện tại, lời giải hiện tại…

double Solver::UpdateT(double
temp, int K)
Cập nhật nhiệt độ với tham
số K
double
Solver::Set_Initial_Temperature(c
onst Problem& pbm)
Thiết đặt nhiệt độ ban đầu
cho bài toỏn

3.2. SA.req.cpp
Một số hàm chớnh í nghĩa
ostream& operator<< (ostream&
os, const Problem& pbm){ return
os; }
In ra bài toỏn
istream& operator>> (istream& is,
Problem& pbm){ return is; }
Đọc vào bài toỏn
const Problem& Solution::pbm()
const { return _pbm; }

istream& operator>> (istream& is, Đọc vào và trả ra lời giải