intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

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

Chia sẻ: Xuan Hien | Ngày: | Loại File: DOC | Số trang:33

Thêm vào BST
Báo xấu
157
lượt xem 12
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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" được nghiên cứu với các nội dung: Tổng quan thuật toán mô phỏng luyện kim (Simulated Annealing = SA), xây dựng khung thuật toán SA, ứng dụng của thuật toán SA. Để nắm vững hơn nội dung kiến thức bài báo cáo mời các bạn cùng tham khảo tài liệu.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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

  1.  SỬ DỤNG THUẬT TOÁN LUYỆN KIM SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT  Chương I:                                                                                                                    ...............................................................................................................      3  Tổng quan thuật toán mô phỏng luyện kim  (Simulated Annealing = SA)          3 .....     Sự hội tụ..............................................................................................................................10 Điều kiện dừng....................................................................................................................10  Chương II:                                                                                                                 ............................................................................................................       10  Xây dựng khung thuật toán SA                                                                               ...........................................................................       10 Hàm Main_Seq.......................................................................................................................24 Kết quả thực nghiệm..................................................................................................................33 1. Kết quả tuần tự...................................................................................................................33 2. Kết quả song song.............................................................................................................33 TRƯƠNG THỊ THÚY LAN(K54A) – KIỀU TUẤN DŨNG(K55B) ­ NGUYỄN MINH CHÂU K55B  1
  2.  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  2
  3.  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 TRƯƠNG THỊ THÚY LAN(K54A) – KIỀU TUẤN DŨNG(K55B) ­ NGUYỄN MINH CHÂU K55B  3
  4.  SỬ DỤNG THUẬT TOÁN LUYỆN KIM SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT  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  E/k T B trong  đó T  là nhiệt  độ, kB là một hằng số vật lý được gọi là  e 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  E/k T trong trạng thái s ở nhiệt độ T là  1 e B   trong đó Z(T): là hàm phân  Z (T ) 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 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  TRƯƠNG THỊ THÚY LAN(K54A) – KIỀU TUẤN DŨNG(K55B) ­ NGUYỄN MINH CHÂU K55B  4
  5.  SỬ DỤNG THUẬT TOÁN LUYỆN KIM SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT 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 khiển  Trạng thái  No vòng lặp cân bằng nhiệt l đánh dấu việc lặp lại  ở nhiệt độ Tk, Yes k tăng khi đạt cân bằng  Nhiệt độ giảm nhiệt ở nhiệt độ Tk. k = k+1; l = 0; Tk và sk điều khiển quá  trình xử lý ngẫu nhiên Đông lạnh? No T ≤ Tcuối Yes Đạt tới cực tiểu toàn cục II. Mô hình toán học của thuật toán SA 1. Không gian trạng thái TRƯƠNG THỊ THÚY LAN(K54A) – KIỀU TUẤN DŨNG(K55B) ­ NGUYỄN MINH CHÂU K55B  5
  6.  SỬ DỤNG THUẬT TOÁN LUYỆN KIM SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT  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 1 k S S  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.  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. TRƯƠNG THỊ THÚY LAN(K54A) – KIỀU TUẤN DŨNG(K55B) ­ NGUYỄN MINH CHÂU K55B  6
  7.  SỬ DỤNG THUẬT TOÁN LUYỆN KIM SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT ( s , s ') ( s, s ' ) 0 ( s , s ') ( s, s ' ) 0 s S ( s, s ' ) 1 s' N 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 
  8.  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 TN N Tn: nhiệt độ kết thúc            Ti T0 T0 3. Hàm chi phí và hàm sức khoẻ Ti: nhiệt độ vòng i khi  i = 1,..,N 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 TRƯƠNG THỊ THÚY LAN(K54A) – KIỀU TUẤN DŨNG(K55B) ­ NGUYỄN MINH CHÂU K55B  8
  9.  SỬ DỤNG THUẬT TOÁN LUYỆN KIM SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT 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  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 j ) / T ) 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) 
  10.  SỬ DỤNG THUẬT TOÁN LUYỆN KIM SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT 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 ) 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 TRƯƠNG THỊ THÚY LAN(K54A) – KIỀU TUẤN DŨNG(K55B) ­ NGUYỄN MINH CHÂU K55B  10
  11.  SỬ DỤNG THUẬT TOÁN LUYỆN KIM SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT • 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. 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: TRƯƠNG THỊ THÚY LAN(K54A) – KIỀU TUẤN DŨNG(K55B) ­ NGUYỄN MINH CHÂU K55B  11
  12.  SỬ DỤNG THUẬT TOÁN LUYỆN KIM SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT 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 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   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; TRƯƠNG THỊ THÚY LAN(K54A) – KIỀU TUẤN DŨNG(K55B) ­ NGUYỄN MINH CHÂU K55B  12
  13.  SỬ DỤNG THUẬT TOÁN LUYỆN KIM SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT 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 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 TRƯƠNG THỊ THÚY LAN(K54A) – KIỀU TUẤN DŨNG(K55B) ­ NGUYỄN MINH CHÂU K55B  13
  14.  SỬ DỤNG THUẬT TOÁN LUYỆN KIM SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT 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.  class Solver  {      protected: const Problem&     problem;      const SetUpParams& params; TRƯƠNG THỊ THÚY LAN(K54A) – KIỀU TUẤN DŨNG(K55B) ­ NGUYỄN MINH CHÂU K55B  14
  15.  SỬ DỤNG THUẬT TOÁN LUYỆN KIM SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT   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; TRƯƠNG THỊ THÚY LAN(K54A) – KIỀU TUẤN DŨNG(K55B) ­ NGUYỄN MINH CHÂU K55B  15
  16.  SỬ DỤNG THUẬT TOÁN LUYỆN KIM SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT 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: 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 ();   TRƯƠNG THỊ THÚY LAN(K54A) – KIỀU TUẤN DŨNG(K55B) ­ NGUYỄN MINH CHÂU K55B  16
  17.  SỬ DỤNG THUẬT TOÁN LUYỆN KIM SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT   };  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; 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); TRƯƠNG THỊ THÚY LAN(K54A) – KIỀU TUẤN DŨNG(K55B) ­ NGUYỄN MINH CHÂU K55B  17
  18.  SỬ DỤNG THUẬT TOÁN LUYỆN KIM SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT 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 ……. 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. TRƯƠNG THỊ THÚY LAN(K54A) – KIỀU TUẤN DŨNG(K55B) ­ NGUYỄN MINH CHÂU K55B  18
  19.  SỬ DỤNG THUẬT TOÁN LUYỆN KIM SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT 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  19
  20.  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
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

LV.11: Bộ Luận Văn Tốt Nghiệp Chuyên Ngành Tài Chính Ngân Hàng
172 tài liệu
841 lượt tải
THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2