Đề 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

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);