Thuật toán luyện kim song song (Parallel Simulated Annealing Algorithms) giải quyết bài toán max - Sat

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 độ, 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à 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 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ố 0iw 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,temperature)) ac += 1.0/test; 34 } } while (ac < acrat); initial_temperature_trial(temperature); return temperature; } Hàm cập nhật nhiệt độ double Solver::UpdateT(double temp, int K) { if(K == 1) return temp / exp(2); else return (temp * exp(K)) / exp(K+1); } 2.1.4 Hàm khởi tạo lời giải Giả sử cú n biến: x1,, x2, x3, …, xn. Lời giải là một mảng n phần tử mà mỗi phần tử trong mảng chỉ nhận một trong hai giỏ trị là 0 hoặc 1 bằng cỏch sinh cỏc số nguyờn ngẫu nhiờn từ 0 đến 1 để gỏn cho mảng này. Vớ dụ với 5 biến ta cú cỏc lời giải như: (có 25 lời giải tất cả) x1,, x2, x3, x4, x5 --- {0, 0, 0, 0, 0}; {1, 0, 0, 0, 0}; {1, 0, 0, 1, 0}… Hàm khởi tạo lời giải void Solution::initialize() { for (int i=0;i<_pbm.numvar();i++) _var[i]= rand_int(0,1); // Khởi tạo một mảng gồm cỏc phần tử là 0 và 1 } 35 Hàm nhận lời giải istream& operator>> (istream& is, Solution& sol) { for (int i=0;i<sol.pbm().numvar();i++) is >> sol._var[i]; return is; } Sử dụng NetStream tớnh toỏn song song NetStream& operator >> (NetStream& ns, Solution& sol) { for (int i=0;i<sol._var.size();i++) ns >> sol._var[i]; return ns; } Hàm ỏp dụng lời giải mới, vớ dụ 0 0 0 chuyển thành 1 1 1. void DefaultMove::Apply (Solution& sol) const { const float probability = 0.03; for (int i=0;i<sol.pbm().numvar();i++) { if (rand01() <= probability) { if (sol.var(i)==1) sol.var(i)=0; else sol.var(i)=1; } } } 2.1.5 Một số hàm tớnh chi phớ Hàm tớnh chi phớ tốt nhất hiện tại double Solver::current_best_cost() const 36 { double value=0.0; unsigned long nitems,length; _sc.get_contents_state_variable("_current_best_cost",(char *)&value, nitems, length); return value; } Hàm chi phớ hiện tại double Solver::current_cost() const { double value=0.0; unsigned long nitems,length; _sc.get_contents_state_variable("_current_cost",(char *)&value, nitems, length); return value; } Hàm chi phớ tốt nhất toàn cục double Solver::global_best_cost() const { double value=0.0; unsigned long nitems,length; _sc.get_contents_state_variable("_global_best_cost",(char *)&value, nitems, length); return value; } 2.1.6 Hàm tớnh sức khoẻ Là hàm tớnh tổng số mệnh đề đúng đối với mỗi lời giải: double Solution::fitness () 37 { double fitness = 0.0; int acum = 0; for(int i = 0; i < _pbm.numclause(); i++) { int *rl = _pbm.clause(i); acum = 0; for(int j = 0; (j < _pbm.lenclause()) && (acum != 1);j++) { if( ((rl[j] < 0) && (_var[(int)abs(rl[j])-1] == 0)) || ((rl[j] > 0) && (_var[rl[j]-1] == 1)) ) acum = 1; } fitness += acum; } return fitness; } 2.1.7 Hàm chấp nhận lời giải bool Solver::AcceptQ (double tent, double cur, double temperature) { if (_direction==minimize) return (tent < cur) || ((rand01()*(1+exp((tent- cur)/temperature)))<2.0); else return (tent > cur) || 38 ((rand01()*(1+exp((cur- tent)/temperature)))<2.0); } 2.1.8 . Hàm kết thỳc thuật toỏn bool TerminateQ (const Problem& pbm, const Solver& solver, const SetUpParams& setup) { StopCondition_3 stop; return stop.EvaluateCondition(pbm,solver,setup); } bool StopCondition_3::EvaluateCondition(const Problem& pbm,const Solver& solver,const SetUpParams& setup) { return ((int)solver.current_best_cost() == pbm.numclause()); } 2.2 Hàm void Solver_Lan::DoStep() DoStep() { //Tăng bước lặp hiện tại lờn 1; current_iteration  current_iteration(current_iteration()+1); set_source(0); // Thiết đặt nguồn _netstream._probe(packed, pending); if(pending) { Solution sol (problem); _netstream > sol << pack_end; 39 final_phase  true; } received  cooperation(); if (!received) { tentative  current; Apply(tentative); // Áp dụng lời giải mới } tentfit  tentative.fitness();//gỏn lại giỏ trị hàm sức khoẻ if (AcceptQ(tentfit,curfit, currentTemperature)) { current  tentative; curfit  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(); } Nếu như pid() != 0 thỡ mỏy con thực hiện và thực hiện cõu lệnh DoStep() như trờn cũn pid() = 0 mỏy chủ thực hiện . 2.3 Hàm Main_Lan 40 Main_Lan { 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; Khai bỏo: Solver_Seq solver (pbm,cfg, argc,argv); 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. } Kết quả thực nghiệm (Chương trỡnh đó chạy nhưng chưa đủ máy để chạy song song nờn thứ 6 sẽ trỡnh bày sau) 1. Kết quả tuần tự 2. Kết quả song song TÀI LIỆU THAM KHẢO [1.] Chen Tao. Multi-FPGA Partitioning Using Simulated Annealing. May 2003 [2.] S. Kirkpatrick, J. C. G., And Vecchi, M. Optimization by simulated annealing. Science 220(4598)(May 1983), 498-516 [3.] MALLBA LIBRARY v2.0 41 [4.]Teknillinen Korkeakoulu. Implementation of Simulated Annealing Optimization method for APLAC Circuit Simulator. 29-10-1996 [5.]Integrated Logic Synthesis Using Simulated Annealing. Petra Farrm. 2007