MỞ ĐẦU Trƣớc đây, công việc lập kế hoạch sản xuất thƣờng phụ thuộc vào kinh nghiệm của ngƣời phụ trách lập lịch và vấn đề này mất rất nhiều thời gian tính toán trong khi kết quả lại có ảnh hƣởng lớn đến toàn bộ quá trình sản xuất. Ngày nay, quy mô sản xuất ngày càng lớn, số lƣợng ngày càng nhiều, vừa mang tính cạnh tranh cao về chất lƣợng sản phẩm vừa phải đáp ứng đƣợc yêu cầu về thời gian, đồng nghĩa với việc đòi hỏi phải có một lịch sản xuất hợp lý, tối ƣu trên nhiều phƣơng diện. nhằm làm giảm thời gian sản xuất, mang lại hiệu quả kinh tế đã cộng đồng. Do b sản xuất thuộc lớp - nên u trong thời gian đa thức.
Vì vậy kim, tối ƣu (Ant Colony Optimization algorithms) quả này. (Ant Colony Optimization - ACO , .T hơn 20 khi ứng dụng giải ,. Luận văn đi sâu nghiên cứu các phƣơng pháp cập nhật mùi trong các thuật toán ACO sản xuất. văn , dựa trên phân tích toán học các đặc tính hội tụ của vết mùi, chúng tôi đã hai mức để từ đó các.
Ƣu điểm của phƣơng pháp đề xuất kiểm kết quả trên các bộ dữ liệu chuẩn (benchmark data) của 7 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com sản xuất sản xuất. Các kết quả nghiên cứu đƣợc công bố trong hai báo cáo khoa học ở hội nghị quốc tế IEEE RIVF 2006 và PRIMA 2008 (xem [17], [4]). Ngoài phần kết luận, luận văn đƣợc trình bày nhƣ sau : Chƣơng 1 : Giới thiệu : lịch sử phát triển, ACO, và. Chƣơng 2 : B sản xuất và các phƣơng pháp giải chính Trong chƣơng này, chúng tôi sản xuất chính gi.
Chƣơng 3 : sản xuất T chung để lập lịch sản xuất. (Đồng thời trong chƣơng này chúng tôi trình bày các cải tiến cụ thể trong áp dụng tối ƣu hóa đàn kiến với bài toán lập lịch) Chƣơng 4 lập lịch sản xuất nghiệm và đánh giá. 8 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com sản xuất CHƢƠNG 1 TỐI ƢU HÓA ĐÀN KIẾN VÀ ỨNG DỤNG Tối ƣu hóa đàn kiến (Ant Colony Optimization - ACO) là cách tiếp cận meta- heuristic tƣơng đối mới (xem [5], [6], [9], [10]) đƣợc đề xuất bởi Dorigo vào năm 1991 mô phỏng hành vi tìm đƣờng -khó. Trên đƣờng đi của mình các con kiến thực để lại một vết hóa chất đƣợc gọi là vết mùi (pheromone trail), đặc điểm sinh hóa học củ chọn để đi, nhờ cách giao tiếp mang tính gián tiếp và cộng đồng (xem [5].
Theo ý tƣởng này, các thuật toán ACO sử dụng thông tin heuristic kết hợp thông tin học tăng cƣờng (xem [6]) qua các vết mùi của các con kiến nhân tạo (artificial ant) để giải các bài toán tối ƣu tổ hợp khó bằng cách đƣa về bài toán tìm đƣờng đi tối ƣu trên đồ thị cấu trúc tƣơng ứng đƣợc xây dựng từ đặc điểm của t (xem [7] (Ant System - AS) (Travelling Salesman Problem - TSP (xem [9]. , (Marie Curie Excellence Award) trao hai năm 9 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com sản xuất 6 (ANT’ 98, ANT’ 2000, ANTS 2002, ANTS 2004, ANTS 2006, ANTS 2008) - (xem http://iridia. Nhƣ vậy, với đồ thị không đối xứng sẽ có (n 1)! đƣờng đi chấp nhận đƣợc và (n 1)! với đồ thị đối xứng. Với n lớn thì ta không thể tìm hết các đƣờng đi và chỉ 2 có thể tìm đƣợc một lời giải đủ tốt bằng các phƣơng pháp tìm kiếm địa phƣơng, tìm kiếm heuristic, tính toán tiến hóa h.
10 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com sản xuất 1. Xây dựng lời giải [ ij (t )] [ ij ] j Ni k Pij k (t ) [ il (t )] [ il ] (1.1) l Ni k 0 , ij 1 0 ij d ij 0 ), N i k. 11 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com sản xuất Cập nhật mùi (0,1) : m k ij (t 1) (1 ) ij (t ) ij (t ) (1. (reinforcement learning 12 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com sản xuất.
: s sau : arg max j N k { ij (t ) ij } q0 s i (1.4) j 13 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com sản xuất [0 0 [0 1. MMAS (xem [22] g - i - (stagnation 14 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com sản xuất ( max ( min -MIN). min max 0 max ). Trong hệ này, thủ tục xây dựng lời giải thực hiện nhƣ trong AS (đƣợc thực nghiệm với tham số : ij (1 ) ij ij (1.8) max{ min (1 ) ij ,0} 15 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com sản xuất min min .2 (ACO metaheuristic (ACO Algorithms.
: Xét bài toán cực tiểu hóa (S , f , ) trong đó S là tập hợp hữu hạn trạng thái, f là hàm mục tiêu xác định trên S còn là các ràng buộc để xác định S qua các thành phần của tập hữu hạn C và các liên kết của tập này. Các tập S, C, và có các đặc tính sau : C = {c1, c2, …, cn} là tập hữu hạn gồm n thành phần. Ta ký hiệu X là tập các dãy trong C có độ dài không quá h : X={<u0, …, uk> | uk C i k h } Tồn tại tập con X* của X và ánh xạ từ X* lên S sao cho 1 ( s) không rỗng với mọi s S và là tập xây dựng đƣợc từ tập con C0 của C và theo đặc tính 3. Từ C0 mở rộng đƣợc thành X* theo thủ tục tuần tự : x0 u0 là mở rộng đƣợc với u1 C 0 ., u k là mở rộng đƣợc thì tồn tại từ xác định đƣợc tập con J(xk) của C sao cho với mọi uk+1 J(xk) thì xk 1 u 0 , u1 ,., u k 1 là mở rộng đƣợc và x k X * khi J(xk) là rỗng.
Với mọi u 0 C 0 , thủ tục mở rộng nêu trên xây dựng đƣợc mọi phần tử của X*. Không giảm tổng quả ta giả thiết rằng có tƣơng ứng giữa các phần tử trong X * đi đƣợc mở rộng từ mỗi u0 trong C 0. 16 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com sản xuất , C0. Với bài toán tổng quát trên, về lý thuyết ta có thể áp dụng thủ tục mở rộng để xây dựng X* và chọn lời giải tốt nhất bằng phƣơng pháp vét cạn nhƣng trên thực tế, do sự bùng nổ tổ hợp thì với số phần tử n của C lớn thì không thực hiện đƣợc và bài toán đƣợc xét thuộc dạng NP-khó.
Thông thƣờng ta sẽ có các phƣơng pháp heuristic để tìm lời giải đủ tốt cho bài toán. Các thuật toán ACO kết hợp thông tin heuristic này với phƣơng pháp học tăng cƣờng nhờ mô phỏng hành vi của đàn kiến để tìm lời giải tốt hơn. Giả sử với mỗi cạnh (i, j) C có trọng số heuristic hi,j để định hƣớng chọn thành phần mở rộng là j khi thành phần cuối cùng của x k là i theo thủ tục nêu trên (hi,j>0 (i,j)). Đàn kiến m con sẽ xây dựng lời giải trên đồ thị đầy đủ có trọng số G = (V, E, H, ) trong đó V là tập đỉnh tƣơng ứng với tập thành phần C ở trên, E là tập các cạnh, H là vector các trọng số heuristic của cạnh tƣơng ứng còn là vector vết mùi tích lũy đƣợc ban đầu với khởi tạo bằng 0.
Đồ thị G đƣợc gọi là đồ thị cấu trúc của bài toán. Với điều kiện dừng đã chọn (giả sử nhƣ là với số lần lặp N c xác định trƣớc) các thuật toán đƣợc mô tả hình thức nhƣ sau : 17 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com sản xuất Procedure Begin while ) do begin ) end; End; Hình 1 : Lƣợc đồ thuật toán ACO Sau khi khởi tạo các tham số và cƣờng độ mùi ban đầu, các con kiến thực hiện thủ tục xây dựng lời giải. Trong mỗi lần lặp t, mỗi con kiến chọn ngẫu nhiên một đỉnh xuất phát trong C0 và kết hợp thông tin heuristic với thông tin mùi để xây dựng lời giải ngẫu nhiên theo thủ tục mở rộng tuần tự nêu ở phần trƣớc với xác suất chọn đỉnh tiếp theo nhƣ sau : Quy tắc chuyển trạng thái : Giả sử con kiến s đã xây dựng xk u 0 ,., u , nó sẽ chọn đỉnh y thuộc J(xk) để xk 1 u 0 ,., u, y với xác suất : u, y hu , y y J ( xk ) P( y | , xk ) u, j hu , j (1. Để tiện trình bày, về sau ta sẽ xem x(l) và s(l) nhƣ nhau đều là thể hiện của lời giải chấp nhận đƣợc và không phân biệt X* với S.
Ký hiệu w(t) là trạng thái tốt nhất các con kiến tìm đƣợc cho tới lúc 18 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com sản xuất này và wi(t) là lời giải tốt nhất trong bƣớc lặp, ta sẽ quy ƣớc chọn w(t) = w(t-1) trong trƣờng hợp wi(t)=w(t-1)và quan tâm đến lời giải gần đúng w(t) này. Trong lý thuyết để tiện cho việc chứng minh, các tác giả đã chọn w(t) còn trong thực nghiệm wi(t) lại tỏ ra hiệu quả hơn do việc này tăng cƣờng tính khám phá của thuật toán. Do giả thiết (3.iii) của bài toán và để tiện cho trình bày, về sau ta không phân biệt mỗi x X * với trạng thái s S tƣơng ứng. Giả sử g là một hàm giá trị thực xác định trên S sao cho 0 g (s) , s S và g ( s) g ( s' ) nếu f (s) f (s' ) , khi đó ở mỗi bƣớc lặp cƣờng độ vết mùi sẽ thay đổi theo một trong hai quy tắc thƣờng dùng sau đây, đƣợc gọi là các quy tắc cập nhật mùi hai mức.
Quy tắc ACS : Quy tắc này phỏng theo quy tắc cập nhật mùi của thuật toán hệ đàn kiến ACS bao gồm cả cập nhật địa phƣơng và cập nhật toàn cục. Cập nhật mùi địa phương : nếu con kiến l thăm cạnh (i, j), tức là (i, j) s(l) thì cạnh này sẽ thay đổi mùi theo công thức : ij (1 ) ij 1 (1.1) Cập nhật mùi toàn cục : Cập nhật mùi toàn cục chỉ áp dụng cho các cạnh thuộc w(t) nhƣ sau : ij (1 ) ij g ( w(t )) (i, j ) w(t ) (1.2) Quy tắc MMAS : Quy tắc này thực hiện theo cách cập nhật mùi của thuật toán MMAS, sau khi mỗi con kiến đề xây dựng xong lời giải ở mỗi bƣớc lặp, vết mùi đƣợc thay đổi theo công thức sau : ij (1 ) ij ij (1.11) 19 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com sản xuất L 1 ( w(t )) (i,j) w(t) ij (1.1) max{ min (1 ) ij ,0} , trong [15 .