Báo cáo Sử dụng thuật toán luyện kim song song giải quyết bài toán Maxsat

Nội dung text: Báo cáo Sử dụng thuật toán luyện kim song song giải quyết bài toán Maxsat

1. Báo cáo khoa học: SỬ DỤNG THUẬT TOÁN LUYỆN KIM SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT
2. SỬ DỤNG THUẬT TOÁN LUYỆN KIM SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT Chương I: Tổng quan thuật toán mô phỏng luyện kim (Simulated Annealing = SA) 4 I. Giới thiệu chung về thuật toán SA 4 II. Mô hình toán học của thuật toán SA 6 1. Không gian trạng thái 6 2. Hàm nhiệt độ 7 3. Hàm chi phí và hàm sức khoẻ 8 4. Sự phân bố trạng thái giới hạn 8 5. Sự hội tụ và điều kiện dừng 9 Sự hội tụ 9 Điều kiện dừng 10 Chƣơng II: Xây dựng khung thuật toán SA 10 I. Lý do xây dựng khung thuật toán 10 II. Khung chung của thuật toán SA 10 III. Sơ đồ khung thuật toán 13 1. Lớp cung cấp (Provided) 13 2. Lớp đòi hỏi (Required) 17 3. Một số hàm quan trọng trong hai lớp Required và Provide 18 3.1. SA.pro.cpp 18 3.2. SA.req.cpp 19 Chƣơng III: Ứng dụng của thuật toán SA 20 I. Bài toán MAXSAT 20 1. Giới thiệu bài toán 20 Hàm Main_Seq 22 TRƢƠNG THỊ THÚY LAN(K54A) – KIỀU TUẤN DŨNG(K55B) - NGUYỄN MINH CHÂU K55B 1
3. SỬ DỤNG THUẬT TOÁN LUYỆN KIM SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT III. Khung thuật toán SA song song giải quyết bài toán MAXSAT 22 1. Lựa chọn mô hình 22 2. Cài đặt Bài toán Maxsat. 23 2.1 Sử dụng thuật toán SA 23 2.1.1 Đọc file cấu hình 23 2.1.2 Lớp Problem đọc bài toán MAXSAT 23 2.1.3 Hàm khởi tạo nhiệt độ 24 2.1.4 Hàm khởi tạo lời giải 25 2.1.6 Hàm tính sức khoẻ 27 2.1.7 Hàm chấp nhận lời giải 27 2.1.8 . Hàm kết thúc thuật toán 28 2.2 Hàm void Solver_Lan::DoStep() 28 2.3 Hàm Main_Lan 29 Kết quả thực nghiệm 29 1. Kết quả tuần tự 30 2. Kết quả song song 30 TRƢƠNG THỊ THÚY LAN(K54A) – KIỀU TUẤN DŨNG(K55B) - NGUYỄN MINH CHÂU K55B 2
4. SỬ DỤNG THUẬT TOÁN LUYỆN KIM SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT BÁO CÁO KHOA HỌC ĐỂ TÀI: THUẬT TOÁN LUYỆN KIM SONG SONG (Parallel Simulated Annealing Algorithms) GIẢI QUYẾT BÀI TOÁN MAX-SAT MỞ ĐẦU - Nhiều bài toán tối ƣu chƣa có thuật toán chính xác để giải quyết cho nên cần có một thuật toán gần đúng để tìm lời giải gần tối ƣu. - Không gian lời giải cần tìm là rất lớn nếu một máy tính tìm kiếm sẽ rất lâu nên cần nhiều máy giải quyết và các máy phải thực hiện đồng thời. Điều này có thể thực hiện dễ dàng nếu các máy tính tính toán song song. Vì vậy việc tìm hiểu về các thuật toán song song là cần thiết và mang tính khả thi đối với các bài toán tối ƣu - Để rút ngắn thời gian lập trình chúng ta cần xây dựng khung thuật toán giúp giải quyết các bài toán khác nhanh chóng hơn. - Mục đích của đề tài này là sử dụng thuật toán luyện kim song song để giải quyết bài toán tối ƣu MAXSAT. Đề tài bao gồm các nhiệm vụ sau: Nghiên cứu lý thuyết về thuật toán luyện kim Xây dựng khung thuật toán chung cho các bài toán sử dụng thuật toán luyện kim Áp dụng khung thuật toán luyện kim cho bài toán MAXSAT 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. TRƢƠNG THỊ THÚY LAN(K54A) – KIỀU TUẤN DŨNG(K55B) - NGUYỄN MINH CHÂU K55B 3
5. SỬ DỤNG THUẬT TOÁN LUYỆN KIM SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT 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 phương Global Minimum: Tối ưu toàn cục  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 TRƢƠNG THỊ THÚY LAN(K54A) – KIỀU TUẤN DŨNG(K55B) - NGUYỄN MINH CHÂU K55B 4
6. SỬ DỤNG THUẬT TOÁN LUYỆN KIM SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT xảy ra từ từ thì chất rắn không đạt đƣợc trạng thái có cấu hình năng lƣợng thấp sẽ đông lạnh đến một trạng thái không ổn định (cấu trúc tối ƣu địa phƣơng)  Gọi E là năng lƣợng của trạng thái s, E’ là trạng thái năng lƣợng của trạng thái s’ và ∆E = E’ – E là sự chệnh lệch nhiệt độ giữa trạng thái s’ và trạng thái s. Nếu E / k T ∆E ≤ 0 thì sự thay đổi kết quả đƣợc chấp nhận với xác suất e B 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 E / k T 1 thái s ở nhiệt độ T là e B trong đó Z(T): là hàm phân phối. Z (T )  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 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. Khởi tạo k = l= 0; Lấy ngẫu nhiên si và phân tích T = Tk; s = sk l = l + 1;  k, l: là biến điều Trạng thái No khiển vòng lặp cân bằng nhiệt  l đánh dấu việc lặp lại ở nhiệt độ T , k Yes  k tăng khi đạt cân bằng nhiệt ở nhiệt độ Nhiệt độ giảm T k. k = k+1; l = 0;  Tk và sk điều khiển quá trình xử lý ngẫu TRƢƠNG THỊ THÚY LAN(K54A) – KIỀU TUẤN DŨNG(K55B) - nhiNGUYên ỄN MINH CHÂU K55B 5 Đông lạnh? No T ≤ Tcuối
7. SỬ DỤNG THUẬT TOÁN LUYỆN KIM SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT II. Mô hình toán học của thuật toán SA 1. Không gian trạng thái  SA thực thi trong một không gian trạng thái. Không gian trạng thái là một tập hợp các trạng thái, mỗi trạng thái đại diện cho một cấu hình. Kí hiệu không gian trạng thái là S, số phần tử của không gian trạng thái là |S|.  Một quan hệ láng giềng trên S:   S S 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 U k S S k 1  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. ((s),(s'),T)(s,s')  s s' P(s,s',T) 1  ((s),(s''),T)(s,s'') s'' α: 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. TRƢƠNG THỊ THÚY LAN(K54A) – KIỀU TUẤN DŨNG(K55B) - NGUYỄN MINH CHÂU K55B 6
8. SỬ DỤNG THUẬT TOÁN LUYỆN KIM SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT Xác suất 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. (s,s')   (s, s') 0 (s,s')   (s, s') 0    (s, s') 1 s S s' N 3 Hàm chấp nhận α: R + [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. TRƢƠNG THỊ THÚY LAN(K54A) – KIỀU TUẤN DŨNG(K55B) - NGUYỄN MINH CHÂU K55B 7
9. SỬ DỤNG THUẬT TOÁN LUYỆN KIM SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT Sơ đồ: To : nhiệt độ khởi đầu 1 N TN Tn: nhiệt độ kết thúc Ti T0 T0 Ti: nhiệt độ vòng i khi i = 1, ,N 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: 1 fitness *100% 1 cost Sự giảm bớt chi phí tƣơng đƣơng với sự tăng của hàm sức khoẻ Giá trị hàm sức khoẻ tăng khi nhiệt độ giảm thể hiện trong biểu đồ: 4. Sự phân bố trạng thái giới hạn 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. TRƢƠNG THỊ THÚY LAN(K54A) – KIỀU TUẤN DŨNG(K55B) - NGUYỄN MINH CHÂU K55B 8
10. SỬ DỤNG THUẬT TOÁN LUYỆN KIM SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT 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 lim Tk T k Trên thực tế có thể chứng minh rằng: exp( f (s ) / T ) (S ) i lim Tk i k s S exp( f (s ) / T ) j j (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ó: (S ) exp( f (s ) /T ) f (s ) f (s ) Tk i k i j i T 0  exp  (S ) exp( f (s ) /T ) T Tk j j - Sự khẳng định cuối cùng là giả thiết f (s ) f (s ) 0 j i (s ) 0 - Hội tụ tới ∞ chỉ có thể xảy ra nếu có: lim lim Tk j k T 0 - 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 (s) 0 tụ tới 0, nếu s không phải lời giải tối ƣu lim lim Tk k T 0 - Ngoài ra có thể chứng minh rằng nếu s là một lời giải tối ƣu thì 1 (s) lim lim Tk k T 0 | S | opt Ở đâ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: i (T).ij(T) j (T). ji(T) TRƢƠNG THỊ THÚY LAN(K54A) – KIỀU TUẤN DŨNG(K55B) - NGUYỄN MINH CHÂU K55B 9
11. SỬ DỤNG THUẬT TOÁN LUYỆN KIM SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT 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ể.  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 TRƢƠNG THỊ THÚY LAN(K54A) – KIỀU TUẤN DŨNG(K55B) - NGUYỄN MINH CHÂU K55B 10
12. SỬ DỤNG THUẬT TOÁN LUYỆN KIM SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT 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. 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í*) gain/K T If ((gain > 0) or (random < e B )) then { S  NewS; (*Chấp nhận lời giải*) If (cost(NewS) < cost(BestS)) then BestS  NewS; } Until (M mod MarkovChain_length == 0); End;(* of metropolis) Trong đó: o Thủ tục nhận lời giải s ở nhiệt độ T và cải thiện nó qua sự tìm kiếm địa phƣơng o M là số phép lặp ở nhiệt độ T o Hàm neighbor sinh ra lời giải mới NewS TRƢƠNG THỊ THÚY LAN(K54A) – KIỀU TUẤN DŨNG(K55B) - NGUYỄN MINH CHÂU K55B 11
13. SỬ DỤNG THUẬT TOÁN LUYỆN KIM SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT 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 gain/K NewS nhƣng với xác suất là radom 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 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 TRƢƠNG THỊ THÚY LAN(K54A) – KIỀU TUẤN DŨNG(K55B) - NGUYỄN MINH CHÂU K55B 12
14. SỬ DỤNG THUẬT TOÁN LUYỆN KIM SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT o // số bƣớc lặp để phối hợp ( nếu là 0 không phối hợp)  Thuật toán SA có thể chạy đƣợc cả ở môi trƣờng tuần tự và môi trƣờng song song. III. Sơ đồ khung thuật toán  SA có hai phân lớp chính là lớp Required (lớp đòi hỏi) và lớp Provided (lớp cung cấp) đƣợc thể hiện trong hình vẽ dƣới đây 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. 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. TRƢƠNG THỊ THÚY LAN(K54A) – KIỀU TUẤN DŨNG(K55B) - NGUYỄN MINH CHÂU K55B 13
15. SỬ DỤNG THUẬT TOÁN LUYỆN KIM SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT 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); // 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; TRƢƠNG THỊ THÚY LAN(K54A) – KIỀU TUẤN DŨNG(K55B) - NGUYỄN MINH CHÂU K55B 14
16. SỬ DỤNG THUẬT TOÁN LUYỆN KIM SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT } 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: 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 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; TRƢƠNG THỊ THÚY LAN(K54A) – KIỀU TUẤN DŨNG(K55B) - NGUYỄN MINH CHÂU K55B 15
17. SỬ DỤNG THUẬT TOÁN LUYỆN KIM SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT 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(); 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 . TRƢƠNG THỊ THÚY LAN(K54A) – KIỀU TUẤN DŨNG(K55B) - NGUYỄN MINH CHÂU K55B 16
18. SỬ DỤNG THUẬT TOÁN LUYỆN KIM SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT 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. 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) TRƢƠNG THỊ THÚY LAN(K54A) – KIỀU TUẤN DŨNG(K55B) - NGUYỄN MINH CHÂU K55B 17
19. SỬ DỤNG THUẬT TOÁN LUYỆN KIM SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT  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, Đọc vào file cấu hình SetUpParams& setup) ostream& operator<< (ostream& os, In ra file cấu hình vừa đọc const SetUpParams& setup) được Khởi tạo các biến của SetupParams ostream& operator<< (ostream& os, In ra kết quả thông kê. const Statistics& stats) void Statistics::update(const Cập nhật các giá trị mới Solver& solver) 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 Cập nhật nhiệt độ với tham temp, int K) số K TRƢƠNG THỊ THÚY LAN(K54A) – KIỀU TUẤN DŨNG(K55B) - NGUYỄN MINH CHÂU K55B 18
20. SỬ DỤNG THUẬT TOÁN LUYỆN KIM SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT double Thiết đặt nhiệt độ ban đầu Solver::Set_Initial_Temperature(c cho bài toán onst Problem& pbm) 3.2. SA.req.cpp Một số hàm chính Ý nghĩa ostream& operator > (istream& is, Đọc vào bài toán Problem& pbm){ return is; } const Problem& Solution::pbm() const { return _pbm; } istream& operator>> (istream& is, Đọc vào và trả ra lời Solution& sol) giải bài toán { return is; } ostream& operator > (NetStream& ns, Solution& sol) { return ns; } double Solution::fitness () const Hàm sức khoẻ { return 0.0; } void UserStatistics::update(const Solver& solver) bool TerminateQ (const Problem& Hàm kết thúc pbm, const Solver& solver,const TRƢƠNG THỊ THÚY LAN(K54A) – KIỀU TUẤN DŨNG(K55B) - NGUYỄN MINH CHÂU K55B 19
21. SỬ DỤNG THUẬT TOÁN LUYỆN KIM SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT SetUpParams& setup) 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 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ì F  G là công thức trong CNF o Nếu F và G là công thức thì F  G 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ứcG  H thì T thoả mãn G và H • F là một công thứcG  H thì T thoả mãn G hoặc H Ví dụ: F (x  x )  (x  x )Công thức này bao gồm 3 biến x0, x1 và ¬x và có 0 1 1 2 2 hai mệnh đề (x  x ) và (x  x ) . Một ví dụ của chỉ thị T cho công thức 0 1 1 2 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. Bài toán MAX-SAT đƣợc định nghĩa nhƣ sau: TRƢƠNG THỊ THÚY LAN(K54A) – KIỀU TUẤN DŨNG(K55B) - NGUYỄN MINH CHÂU K55B 20
22. SỬ DỤNG THUẬT TOÁN LUYỆN KIM SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT 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ự x Mỗi kí tự là một biến khẳng định xk hoặc phủ định k và có mệnh đề (C x  x   x ) j i1 i2 ik . Trọng số wi 0 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 đề F C1C2   Cm 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ẻ 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); TRƢƠNG THỊ THÚY LAN(K54A) – KIỀU TUẤN DŨNG(K55B) - NGUYỄN MINH CHÂU K55B 21
23. SỬ DỤNG THUẬT TOÁN LUYỆN KIM SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT 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; 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 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. TRƢƠNG THỊ THÚY LAN(K54A) – KIỀU TUẤN DŨNG(K55B) - NGUYỄN MINH CHÂU K55B 22
24. SỬ DỤNG THUẬT TOÁN LUYỆN KIM SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT 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ừ > (istream& is, Problem& pbm) { TRƢƠNG THỊ THÚY LAN(K54A) – KIỀU TUẤN DŨNG(K55B) - NGUYỄN MINH CHÂU K55B 23
25. SỬ DỤNG THUẬT TOÁN LUYỆN KIM SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT 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 > l; pbm._clauses[i][j] = l; } is >> l; } 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(); TRƢƠNG THỊ THÚY LAN(K54A) – KIỀU TUẤN DŨNG(K55B) - NGUYỄN MINH CHÂU K55B 24
26. SỬ DỤNG THUẬT TOÁN LUYỆN KIM SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT for (int i=0; i Apply(newsol); if (AcceptQ(newsol.fitness(),fit,temperature)) ac += 1.0/test; } } while (ac > (istream& is, Solution& sol) { for (int i=0;i > sol._var[i]; return is; TRƢƠNG THỊ THÚY LAN(K54A) – KIỀU TUẤN DŨNG(K55B) - NGUYỄN MINH CHÂU K55B 25
27. SỬ DỤNG THUẬT TOÁN LUYỆN KIM SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT } Sử dụng NetStream tính toán song song NetStream& operator >> (NetStream& ns, Solution& sol) { for (int i=0;i > 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 { 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; } TRƢƠNG THỊ THÚY LAN(K54A) – KIỀU TUẤN DŨNG(K55B) - NGUYỄN MINH CHÂU K55B 26
28. SỬ DỤNG THUẬT TOÁN LUYỆN KIM SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT 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 () { double fitness = 0.0; int acum = 0; for(int i = 0; i 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 TRƢƠNG THỊ THÚY LAN(K54A) – KIỀU TUẤN DŨNG(K55B) - NGUYỄN MINH CHÂU K55B 27
29. SỬ DỤNG THUẬT TOÁN LUYỆN KIM SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT return (tent > cur) || ((rand01()*(1+exp((cur-tent)/temperature))) > sol << pack_end; 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)) { TRƢƠNG THỊ THÚY LAN(K54A) – KIỀU TUẤN DŨNG(K55B) - NGUYỄN MINH CHÂU K55B 28
30. SỬ DỤNG THUẬT TOÁN LUYỆN KIM SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT 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 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) TRƢƠNG THỊ THÚY LAN(K54A) – KIỀU TUẤN DŨNG(K55B) - NGUYỄN MINH CHÂU K55B 29
31. SỬ DỤNG THUẬT TOÁN LUYỆN KIM SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT 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 [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 TRƢƠNG THỊ THÚY LAN(K54A) – KIỀU TUẤN DŨNG(K55B) - NGUYỄN MINH CHÂU K55B 30