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ụngcủ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ảsongsong . 40
41 trang |
Chia sẻ: netpro | Lượt xem: 1937 | Lượt tải: 4
Bạn đang xem trước 20 trang tài liệu Đề 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, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
ư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
độ, kB 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 độ Tcuố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 si 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 ≤ Tcuố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 độ Tk,
k tăng khi đạt cõn
bằng nhiệt ở nhiệt
độ Tk.
Tk và sk đ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
SSkk
1U
Tập trạng thỏi kết nối với trạng thái đó cho si ê S được kớ
hiệu là Ni, số phần tử của Ni gọi là cấp độ của si. Ni là tập cỏc
lỏng giềng của si.
Cú hai trạng thỏi si và si-1 và xỏc suất để si là trạng thỏi hiện
thời phụ thuộc vào hàm chi phớ của si và hàm chi phớ của si-1 và
nhiệt độ T.
Cú ba trạng thỏi liờn tiếp si-1, si, si+1 thỡ trạng thỏi si-1 và si+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
ssSs
ssss
ssss
Hàm chấp nhận ỏ: R3+ [0,1] R
2. Hàm nhiệt độ
Đầu tiờn khởi tạo nhiệt độ T là T0. Quy trỡnh phổ biến nhất là quy
trỡnh làm lạnh cõn xứng: Tnew = Told * 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
đồ:
To : nhiệt độ khởi
đầu
Tn: nhiệt độ kết
thỳc
N
N
i T
TTT
1
0
0
11
4. Sự phõn bố trạng thỏi giới hạn
Cho ðTk(si) là xỏc suất mà si 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(s1), ðTk(s2),…,ðTk(si),…). 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 TTkk
lim
Trờn thực tế cú thể chứng minh rằng:
S
j
s Tj
sf
T
i
sf
i
S
Tkk )/)(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 si và sj với f(si) < f(sj). Trong trường hợp
này cú:
0
)()(
exp
)/)(exp(
)/)(exp(
)(
)( T
T
i
sf
j
sf
T
j
sf
T
i
sfk
j
S
Tk
i
S
Tk
- Sự khẳng định cuối cựng là giả thiết 0)()( isfjsf
- Hội tụ tới ∞ chỉ cú thể xảy ra nếu cú: 0)(limlim
0
j
s
TkTk
- Chứng minh rằng: Cho lời giải khả thi s, k∞ và T0 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
TkTk
- 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
TkTk
Ở đây Sopt 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:
)().()().( TjiTjTijTi
Trong đó ði(T) là sự phõn bố ổn định của trạng thỏi si ở 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 si º S sao cho Pii ≠ 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 < egain/KBT)) 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 < egain/KBT
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
S0 = Initial_Solution()// khởi tạo lời giải S0
M = 0;
Repeat
16
Call Metropolis (S0,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 S0
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
26
Solution& sol)
{ return is; }
ostream& operator<< (ostream&
os, const Solution& sol)
{return os;}
bài toỏn
NetStream& operator <<
(NetStream& ns, const Solution&
sol){ return ns; }
NetStream& operator >>
(NetStream& ns, Solution& sol) {
return ns; }
Đọc vào và trả ra lời giải
bài toỏn sử dụng cho song
song
double Solution::fitness () const
{ return 0.0; }
Hàm sức khoẻ
void UserStatistics::update(const
Solver& solver)
bool TerminateQ (const Problem&
pbm, const Solver& solver,const
SetUpParams& setup)
Hàm kết thỳc
Chương III:
Ứng dụng của thuật toỏn SA
I. Bài toỏn MAXSAT
1. Giới thiệu bài toỏn
27
Bài toỏn MAXSAT bao gồm tập n biến {x1, x2,…,xn } và tập m
mệnh đề. Mục đích của bài toỏn MAXSAT là tỡm một phõn phối
cỏc giỏ trị chõn lý T cho cỏc biến sao cho ớt nhất k mệnh đề đúng
CNF = Conjunctive Normal Form - Dạng chuẩn hội. Ta cú:
o Bất kỳ một kớ hiệu vị từ P nào đều là một cụng thức trong
CNF
o Nếu F là một cụng thức trong CNF thỡ ơF là một cụng thức
o Nếu F và G là cụng thức thỡ GF là cụng thức trong CNF
o Nếu F và G là cụng thức thỡ GF là cụng thức trong CNF
o Một hàm T: P-> {TRUE, FALSE} nghĩa là T là sự phõn bố
cỏc giỏ trị chõn lý {TRUE, FALSE} cho cỏc vị từ trong P.
Một cụng thức F thoả món bởi một chỉ thị chõn lý T nếu:
• F là một biến logic x thỡ T(x) = TRUE
• F là một cụng thức ơG thỡ T( G) = FALSE
• F là một cụng thức HG thỡ T thoả món G và H
• F là một cụng thức HG thỡ T thoả món G hoặc H
Vớ dụ:
)()( 2110 xxxxF Cụng thức này bao gồm 3 biến x0, x1 và
ơx2 và cú hai mệnh đề )( 10 xx và )( 21 xx . Một vớ dụ của chỉ
thị T cho cụng thức này: T1 = {x0 FALSE, x1 FALSE, x2
TRUE}. T1 khụng thoả món cụng thức F. Tuy nhiờn cú một chỉ thị
khỏc thoả món cụng thức F là: T2 = {x0 FALSE, x1 TRUE,
x2 TRUE}. Thấy rằng F thoả món và T2 là chỉ thị làm thoả
món F.
28
Bài toán MAX-SAT được định nghĩa như sau:
Input:
n biến logic x1, x2, x3,…,xn mà cú thể chỉ nhận giỏ trị TRUE
hoặc FALSE
m mệnh đề C1, C2, C3,…,Cm mỗi mệnh đề là một sự phõn cỏch
của cỏc kớ tự
Mỗi kớ tự là một biến khẳng định xk hoặc phủ định kx và cú
mệnh đề )( ...21 ikxixixjC . Trọng số 0iw cho mỗi mệnh
đề Ci
Một cụng thức CNF là một sự kết hợp cỏc mệnh đề
mCCCF ...21
Output
Tỡm một phõn bố T (TRUE/FALSE) cho n biến logic mà số
mệnh đề được thoả món cú tổng trọng số là lớn nhất.
II. Khung thuật toỏn SA tuần tự giải quyết bài toỏn MAXSAT
1. Hàm void Solver_Seq::DoStep()
DoStep()
{
//Tăng bước lặp hiện tại lờn 1;
current_iteration
current_iteration(current_iteration()+1)
tentative = current;
Apply(tentative); //Áp dụng lời giải mới
tentfit tentative.fitness(); //Tớnh giỏ trị hàm sức khoẻ
29
if (AcceptQ(tentfit,curfit, currentTemperature)) //chấp
nhận //lời giải
mới
{
current tentative; // lời giải hiện tại giờ là
tentative;
curfit tentfit; // giỏ trị hàm sức khoẻ là tentfit
}
k k + 1;
if (k >= MarkovChain_length())
{
UpdateT;
k = 0;
}
total_time_spent start_global + time_spent_in_trial;
RefreshState();
_stat.update(*this);
_userstat.update(*this);
if (display_state()) show_state();
}
Hàm Main_Seq
Main_Seq
{
Sử dụng khung SA
Khai bỏo: SetupParams cfg; Problem pbm;
Mở file f1 là “SA.cfg” để đọc vào cấu hỡnh
Đọc file f1>>cfg;
Mở file f2 để đọc “Problem.dat”
Đọc file f2>>pbm;
30
Khai bỏo: Solver_Seq solver (pbm,cfg);
Gọi hàm solver.run();
Nếu (solver.pid()==0) thỡ hiển thị trạng thỏi. In ra lời
giải tốt nhất toàn cục và giỏ trị hàm sức khỏe.
}
III. Khung thuật toỏn SA song song giải quyết bài toỏn
MAXSAT
1. Lựa chọn mụ hỡnh
Cú cỏc loại mụ hỡnh như sau:
Mụ hỡnh khuyếch tỏn (Diffusion model): Cỏc cỏ thể được
sắp xếp trong khụng gian và giao với cỏc cỏ thể khỏc. Khi
song song hoỏ, cú nhiều tiến trỡnh truyền thụng nờn mỗi cỏ
thể phải liờn lạc với lỏng giềng của nú trong mọi bước lặp
nhưng truyền thụng chỉ là cục bộ. Vỡ vậy mụ hỡnh này phự
hợp cho cỏc mỏy tớnh song song lớn với một mạng thụng tin
nội bộ địa phương.
Mụ hỡnh chủ - thợ (Master-slave): Bộ xử lý chủ nắm giữ tất
cả cỏc thụng tin về khụng gian trạng thỏi. Bộ xử lý mỏy chủ
phõn phối tới mỏy thợ rỗi và nhận cỏc thụng tin mới được sinh
ra từ mỏy thợ. Cỏc mỏy thợ tiến hành xử lý cỏc thụng tin vừa
được sinh ra. Mụ hỡnh này cú ưu điểm là dễ cài đặt nhưng
thực hiện chậm, tốn thời gian.
Mụ hỡnh đảo (Island model): Trong mụ hỡnh này mọi tiến
trỡnh chạy độc lập và cỏc tiến trỡnh hợp tỏc bởi việc đều đặn
31
trao đổi những cỏ thể tốt vừa tỡm được. Mụ hỡnh này đặc biệt
thớch hợp cho một nhúm mỏy tớnh.
Với những đặc điểm trờn quyết định dựng mụ hỡnh đảo vỡ nếu
dựng cỏc mụ hỡnh kia thỡ tốn kộm hoặc nếu khụng tốn kộm
thỡ cũng thực hiện thuật toỏn với tốc độ chậm. Thờm vào đó
sử dụng thư viện MPI để cỏc mỏy tớnh truyền thụng với nhau
và dựng NetStream để thõn thiện hơn với người sử dụng.
2. Cài đặt Bài toỏn Maxsat.
2.1 Sử dụng thuật toỏn SA
2.1.1 Đọc file cấu hỡnh
5 // số bước chạy độc lập
500 // số ước lượng
100 // Markov-Chain Length
0.99 // độ giảm nhiệt độ
1 // cú hiện thị trạng thỏi ?
LAN-configuration
10 // trạng thỏi toàn cục được cập nhật trong n
ước lượng
0 // 0: asynchronized mode // 1: synchronized mode
10 // số bước lặp để cooperate ( if 0 no
cooperation)
2.1.2 Lớp Problem đọc bài toỏn MAXSAT
Đầu vào của bài toỏn là n biến và m mệnh đề được thể hiện
trong một file là Sat.dat với định dạng:
// số lượng biến, số lượng mệnh đề, chiều dài mỗi mệnh đề
// mệnh đề 1 (kết thỳc là 0), nếu vị từ < 0 thỡ vị từ là phủ định.
……….
// mệnh đề N (kết thỳc là 0), nếu vị từ < 0 thỡ vị từ là phủ định
32
Vớ dụ cụ thể : Bài toỏn cú
5 7 3 //5 biến, 7 mệnh đề, độ dài mỗi mệnh đề là 3
-1 -2 3 0 ơx1 ơx2 x3
2 3 -1 0 x2 x3 ơx1
1 -2 3 0 x1 ơx2 x3
-2 -3 4 0 ơx2 ơx3 x4
3 4 5 0 x3 x4 x5
-5 1 -4 0 ơx5 x1 ơx4
2 5 3 0 x2 x5 x3
istream& operator>> (istream& is, Problem& pbm)
{
int l;
int n;
is >> pbm._numvar >> pbm._numclause >>
pbm._lenclause;
n = pbm._lenclause;
// read clauses
pbm._clauses = new int*[pbm._numclause];
for (int i = 0; i < pbm._numclause; i++)
{
pbm._clauses[i] = new int[n];
for(int j = 0; j < n;j++)
{
is >> l;
pbm._clauses[i][j] = l;
}
is >> l;
}
33
return is;
}
2.1.3 Hàm khởi tạo nhiệt độ
double Solver::Set_Initial_Temperature(const Problem& pbm)
{
const double beta = 1.05;
const double test = 10;
const double acrat = .8;
const double T = 1.0;
Solution current (pbm);
Solution newsol (pbm);
double ac;
double fit;
double temperature = T;
do
{
temperature *= beta;
ac = 0;
current.initialize();
fit = current.fitness();
for (int i=0; i<test; i++)
{
newsol = current;
move->Apply(newsol);
if (AcceptQ(newsol.fitness(),fit,temperatur
Các file đính kèm theo tài liệu này:
- Thuật toán luyện kim song song (Parallel Simulated Annealing Algorithms) giải quyết bài toán max-sat.pdf