Luận văn Bài toán thuê xe du lịch có hạn ngạch

=(11100010010011011) u2 3. 0,11 0,40 0,70 v6=(00010100001001010) u3 4. 0,11 0,51 0,78 v8=(10000110000111010) u4 5. 0,08 0,59 0,42 v4=(10001100010110100) u5 6. 0,08 0,67 0,31 v4=(00001000001100100) u6 7. 0,10 0,76 0,42 v4=(10001100010110100) u7 8. 0,08 0,84 0,28 v2=(11100010010011011) u8 9. 0,06 0,90 0,64 v6=(00010100001001011) u9 10 0,10 1,00 0,95 v10=(00010100001001010) u10 Tương giao chéo. Với pc=0,25 ta chọn được cặp tương giao chéo là u3= (00010100001001010) u5= (10001100010110100) với điểm trao đổi k=5. Sau khi tương giao ta được u ′ 3= (00010100010110100) u ′ 5= (10001100001001010) Với xác suất đột biến là pm=0,01 ; các gene đánh số từ 1 đến 170 ta chọn được gene thứ 81 (gene thứ 13 của cá thể thứ 5) và gene thứ 127 (gene thứ 8 của cá thể thứ 8) Ta được P(1) là : 23 v ′ 5 = (00011101100101001) v ′ 2 = (11100010010011011) v ′ 6 = (00010100010110100) v ′ 8 = (10000110000111010) v ′ 4 = (10001100001011010 v ′ 3 = (00001000001100100) v ′ 4 = (10001100010110100) v ′ 2 = (11100011010011011) v ′ 6 = (00010100001001011) v ′ 10 = (00010100001001010) Độ thích hợp toàn phần là F= 107,65 ; cá thể tốt nhất vẫn là v ′ 2=(11100010010011011) với eval=14,78 nhưng thế hệ này tốt hơn p(0) nhiều quá trình tiếp tục cho tới lúc dừng ta được lời giải gần tối ưu. 2.1.2. Biễu diễn bằng véc tơ số thực Sau khi GA cổ điển được Holland công bố nó chứng tỏ là một phương pháp tốt để giải các bài toán tối ưu khó và nó được cải tiến phong phú để tăng hiệu quả ứng dụng. Đối với các bài toán có miền chấp nhận được lớn và đòi hỏi sai số bé thì độ dài của mỗi mỗi nhiễm sắc thể theo phương pháp GA cổ điển rất lớn nên việc áp dụng GA rất khó khăn. Vì vậy người ta cải tiến bằng biễu diễn nhiễm sắc thể bằng véc tơ thực để giải bài toán (I,1). Trong biễu diễn này, người ta dùng các véc tơ thực trong miền chấp nhận đươc (thuôc tập M) làm nhiễm sắc thể và thiết kế các nhóm toán tử di truyền cho thích hợp với biễu diễn này mà vẫn giữ nguyên thủ tục GA đã đặc tả ở trên. Dưới đây giới thiệu một số toán tử dễ dùng. Các toán tử tương giao chéo Người ta chó thể chọn một vài toán tử tương giao chóe trong số các toán tử sau. Tương giao đơn giản Toán tử này thực hiện trao đổi hai nhóm gene tương tự như giải thuật cổ điển. Nếu tương giao hai véc tơ x = (x1, x2, ..., xn), x = (y1, y2, ..., yn) với điểm chọn ở vị trí thứ k thì ta được x ′ = (x1, ...xk, yk+1, ..., yn) , y ′ = (y1, ...yk, xk+1, ..., xn) Tương giao số học đơn 24 Nếu tương giao hai véc tơ: x = (x1, x2, ..., xn), y = (y1, y2, ..., yn) với điểm chọn ở vị trí thứ k thì ta được : x ′ = (x1, ...x ′ k.., xn) , y ′ = (y1, ...y ′ k.., yn) trong đó x ′ k = axk + (1− a)yk với a ∈ (0, 1) là số cho trước hoặc chọn ngẫu nhiên. Tương giao số học toàn cục Nếu tương giao hai véc tơ x = (x1, x2, ..., xn), y = (y1, y2, ..., yn) thì được x ′ = ax+ (1− a)y , y ′ = ay+ (1− a)x với a ∈ (0, 1) là số cho trước hoặc chọn ngẫu nhiên. Các toán tử biến dị Người ta có thể dùng nhiều kiểu toán tử biến dị, chẳng hạn, một trong hai toán tử biến dị sau. Biến dị đều Giả sử gene xk diến dị thành x ′ k thì x ′ k là số ngẫu nhiên phân bố đều trên miền chấp nhận được [ak, bk] của nó. Biến dị không đều Giả sử gene xk diến dị thành thì x ′ k = xk + δ(t, xk) trong đó δ(t, xk) là số ngẫu nhiên phân bố không đều trên đoạn [ak − xk, bk − xk] và hội tụ theo xác suất về không khi t tăng ra vô hạn, tham số tchỉ vòng lặp. Thông dụng nhất là chọn phân bố chuẩn. 2.1.3. GA trong tối ưu tổ hợp Thuật toán di truyền giải các bài toán tối ưu tổ hợp có cùng lược đồ với GA cổ điển được mô tả trong hình I.1. Trong ứng dụng, ta thường gặp nhiều bài toán thực tiễn mà hàm mục tiêu chưa có dạng tường minh. Khi đó ta cần xây dựng bài toán tói ưu cho nó và áp dụng GA để tìm lời giải. Cách tiếp cận này mở ra các phương pháp tính toán tiến hóa (Evolutionary computation viết tắt là EC) Lược đồ tính toán tiến hóa Trong tối ưu hóa, thuật ngữ tính toán tiến hóa có thể hiểu theo hai tiếp cận. Theo nghĩa rộng, EC dùng để chỉ các phương pháp lặp tạo sinh hoặc phát triển 25 quần thể lời giải, trong đó chất lượng lời giải được cải thiện theo thời gian. Theo nghĩa hẹp mà ta dùng trong mục này, EC dùng để chỉ các phương pháp giải các bài toán nhờ ứng dụng GA. Khí áp dụng EC, ta cần đưa bài toán được xét về bài toán tìm lời giải tối ưu để áp dụng GA để giải. Chương trình áp dụng EC để giải bài toán gọi là chương trình tiến hóa. Mối liên hệ giữa EC và GA đươc minh hoạ bởi sơ đồ trong hình I.2. Hình 2.2: Sơ đồ quan hệ áp dụng tính toán tiến hóa Các bước cơ bản để5 xây dựng chương trình tiến hóa Đối với một bài toán cần giải P, để xây dựng một chương trình tiến hoá giải nó, người ta thường tiến hành theo năm bước cơ bản sau: • Bước 1. Chọn cấu trúc nhiễm sắc thể / kiểu gene biễu diễn lời giải tiềm năng của bài toán sao cho nó chứa đủ các thông tin quan trọng và dễ làm việc. Tuy nhiên không có sự hướng dẫn nào về cách chọn này. Thiết kế chương trình mã hóa và giải mã • Bước 2. Khởi tạo tập lời giải ban đầu. Việc khởi tạo là ngẫu nhiên hay có thể áp dụng một vài thuật toán heuristic, nhưng phải đảm bảo sao cho các ràng buộc của bài toán được đảm bảo. • Bước 3. Chọn hàm đánh giá mức độ tốt của lời giải (để đánh giá các cá thể trong quần thể lời giải theo độ thích nghi của chúng ). • Bước 4. Thiết kế các toán tử di truyền. Các toán tử này được thiết kế nên dựa trên kiểu gene/ nhiễm sắc thể , đặc điểm bài toán và các ràng buộc của nó. 26 • Bước 5: Xác định các tham số cho bài toán. Các tham số này có thể không thay đổi trong quá trình tiến hoá hoặc có thể tự điều chỉnh tham số theo thời gian. Một số nhận xét GA có phổ ứng dụng rộng, dễ sử dụng và hướng tới lời giải tối ưu toàn cục nên được người dùng ưa thích. Tuy nhiên khi cáp dụng GA, cần lưu ý các điểm sau. 1. Trong tối ưu liên tục, GA thích hợp cho các bài toán nhiều cực trị và không khả vi. Đối với các bài toán đã có phương pháp truyền thống thì thường GA mất nhiều thời gian chạy hơn. Với các bài toán nhiều cực trị nhưng áp dụng được phương pháp gradient thì có thể khởi tạo nhiều điểm xuất phát có phân bố đều và áp dụng tìm kiếm gradient để chọn lời giải tốt nhất sẽ hiệu quả hơn GA. 2. Trong tối ưu tổ hợp, việc chọn cấu trúc nhiễm sắc thể và kiểu gene rất quan trọng đối với hiệu quả thuật toán. Kiểu gene chọn tốt sẽ thỏa mãn được nhiều ràng buộc, hạn chế phạm vi tìm kiếm trong không gian trạng thái. 3. Việc tìm kiếm trong các thuật toán giải các bài toán tối ưu tổ hợp thường có 2 cơ chế chính: tìm kiếm tăng cường (intensification)/khai thác (exploitation) quanh miền có lời giải tốt tìm được và khám phá (exploration)/ đa dạng (diver- sification) nhằm tạo sinh các lời giải đa dạng để mở rộng tìm kiếm hướng tới tối ưu toán cục. Trong GA, thủ tục chọn lọc là khâu chính hướng tới tìm kiếm tăng cường còn các toán tử di truyền hướng tới sự khám phá. Khi áp dụng GA cần cân bằng giữa hai cơ chế này. Việc chọn tham số cho các toán tử di truyền cũng rất quan trọng đối với hiệu quả thuật toán 4. GA là thuật toán dễ sử dụng cho cả tối ưu liên tục và tối ưu tổ hơp. Tuy nhiên khi dùng cho tối ưu liên tục, nó thích hợp cho các bài toán không khả vi và có nhiều cực trị địa phương. Đối với các bài toán đã có các phương pháp truyền thống tốt thì GA chạy lâu và chất lượng lời giải thường kém hơn. Các toán tử di truyền có thể vận dụng mềm dẻo và đa dạng để tăng tính khám phá của thuật toán. 5. Khi áp dụng GA, việc chọn biễu diễn gene và cấu trúc nghiếm sắc thể rất quan trọng. Một cách chọn biễu diễn gene thích hợp sẽ cho phép đáp ứng nhiều ràng buộc, thu hẹp không gian tìm kiếm và dễ xây dựng các toán tử di truyền. 27 2.2. Phương pháp tối ưu hóa đàn kiến Tối ưu hoá đàn kiến (Ant colony optimization, viết tắt là ACO) được đề xuất bởi Dorigo vào năm 1991, mô phỏng cách tìm đường đi của các con kiến thực nhờ kết hợp các thông tin heuristic và cách học tăng cường để giải các bài toán tối ưu tổ hợp. 2.2.1. Cách tìm đường đi của kiến tự nhiên Trên đường đi của mình đường đi từ tổ tới nguồn thức ăn và ngược lại, 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). Vết mùi này là có khả năng tích lũy, bay hơi và là phương tiện giao tiếp báo cho các con kiến khác thông tin về đường đi đó một cách gián tiếp. Ở mỗi lối rẽ, các con kiến sẽ lựa chọn lối tiếp theo dựa trên nồng độ lượng mùi trên đó, nồng độ càng cao thì càng nhiều khả năng được chọn. Những lối rẽ thuộc đường đi dài thì vết mùi bay hơ nhiều nên nồng độ thấp, dần dần các con kiến sẽ chọn lối rẽ có nồng độ mùi cao và do đó thuọc đương đi ngắn nhất. Nhờ cách giao tiếp mang tính gián tiếp và cộng đồng này mà đàn kiến trong tự nhiên tìm được đường đi ngắn nhất trong quá trình tìm thức ăn mang về tổ và ngược lại. Hành vi của đàn kiến khi gặp chướng ngại vật trên đường đi được minh họa trong hình 2.3, ở hình a cho thấy kiến chưa gặp vật cản, bất ngờ cómột chướng ngại vật (hình b), kiến phân bố ngẫu nhiên theo nồng độmùi (hình c) và khi đường ngắn có nồng độ mùi cao thì kiến luôn chọn đường này (hình d). 28 Hình 2.3: Phân bố của đàn kiến trên đường đi từ tổ tới nguồn thức ăn 2.2.2. Kiến nhân tạo Thực nghiệm cây cầu đôi cho thấy đàn kiến tự nhiên có thể sử dụng luật di chuyển theo xác suất, dựa trên thông tin địa phương để tìm được đường đi ngắn nhất giữa hai địa điểm. Vết mùi của đàn kiến cho phép liên tưởng tới cách học tăng cường (reinforcement learning) trong bài toán chọn tác động tối ưu, gợi mở mô hình mô phỏng cho bài toán tìm đường đingắn nhất giữa hai nút (tương ứng là tổ và nguồn thức ăn) trên đồ thị, trong đó các tác tử (agent) là đàn kiến nhân tạo. Tuy nhiên, trong các bài toán ứng dụng các đồ thị thường phức tạp hơn.Từ mỗi đỉnh có thể có nhiều cạnh, nên nếu mô phỏng thực sự hành vi của đàn kiến tự nhiên nhiều con kiến sẽ đi luẩn quẩn và do đó hiệu quả thuật toán sẽ rất kém. Vì vậy, người ta dùng kỹ thuật đa tác tử (multiagent) mô phỏngđàn kiến nhân tạo, trong đó mỗi con kiến nhân tạo có khả năng nhiều hơn so với kiến tự nhiên. Kiến nhân tạo (về sau trong luận án ta sẽ gọi đơn giản là kiến) có bộ nhớ riêng, có khả năng ghi nhớ các đỉnh đã thăm trong hành trình và tính được độ dài đường đi nó chọn. Ngoài ra, kiến có thể trao đổi thông tin với nhau, thực hiện tính toán cần thiết, cập nhật mùi. . . 2.2.3. Phương pháp ACO tổng quát Để trình bày phương pháp ACO tổng quát giải các bài toán tối ưu tổ hợp khó, ta cần phát biểu lại bài toán tối ưu tổ hợp theo khung nhìn của heuristic cấu trúc. 29 Bài toán tối ưu tổ hợp tổng quát Các cách tiếp cận trên được áp dụng rộng rãi và phong phú để giải các bài toán tối ưu tổ hợp trong đó bài toán tối ưu tổng quát được phát biểu như sau. Xét bài toán cực tiểu hóa 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 : • 1) 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 xâu thành phần trong C có độ dài không quá h : X = {}. • 2) 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, hơn nữa, tập X∗ này xây dựng được từ tập con C0 của C và Ω theo đặc tính 3. • 3) Từ C0 mở rộng được thành X∗theo thủ tục tuần tự : – x0 = là mở rộng được với ∀u ∈ C0 . – Nếu xk = là mở rộng được thì từ Ω xác định được tập con J(xk) của C sao cho với mọi uk=1 ∈ J(xk)ta có xk+1 = là mở rộng được và xk ∈ X∗ khi J(xk) là rỗng. – Với mọi u0 ∈ C , 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∗ với mỗi đường đi được mở rộng từ mỗi u0 trong C0. Thuật toán tổng quát 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 bùng nổ tổ hợp thì khi số phần tử n của C lớn ta không thực hiện được đối với bài toán thuộc loại NP-khó. Để giải bài toán người ta đưa nó về bài toán tìm đường đi tối ưu trên đồ thị cấu trúc sao cho mỗi lời giải chấp nhận được s ứng với đường đi , trong đó xi thuộc tập đỉnh (thành phần C) của đồ thị, x1 thuộc tập đỉnh C0 (tham khảo phương pháp constructive heuristics). Đồ thị cấu trúc thường là đồ 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à vectơ các trọng số heuristic của cạnh/đỉnh tương ứng, còn τ là vectơ vết mùi tích lũy được ban đầu với khởi tạo bằng τ0 . Thông tin heuristic và vết mùi có thể để ở đỉnh hoặc các cạnh của đồ thị tùy theo đặc điểm bài toán dùng để định hướng tìm kiếm heuristic ngẫu nhiên khi xây 30 dựng lời nhờ mở rộng tuần tự từ một đỉnh trong C0 theo đặc điểm thứ 3 của bài toán tổng quát. Dựa trên đồ thị cấu trúc này, ta xây dựng thủ tục bước bước tuần tự tìm lời giải cho các kiến nhân tạo. Thông thường ta có thể đã có các phương pháp heuristic để tim 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. Với quy tắc cập nhật mùi, các tham số, số kiến và điều kiện dừng (thường là số lần lặp Nc định trước) đã được chọn các thuật toán được mô tả hình thức trong hình 2.4. Hình 2.4: Lược đồ thuật toán ACO tổng quát Xây dựng lời giải Để tiện trình bày, ta giả sử bài toán có vết mùi và thông tin heuristic để ở các cạnh. Sau khi khởi tạo các tham số và cường độ mùi ban đầu, các con kiến chọn ngẫu nhiên một đỉnh xuất phát trong C0 để thực hiện thủ tục xây dựng lời giải. Trong mỗi lần lặp t, kiến chọn ngẫu nhiên một đỉnh tiếp theo trong C 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 ở trên với quy tắc chuyển trạng thái như mô tả ở dưới. Quá trình mở rộng tiếp tục cho tới khi mỗi con kiến k đều tìm được lời giải chấp nhận được xk ∈ X∗ và do đó s(k) = ϕ(x(k)) . Để tiện trình bày, về sau ta sẽ xem x(k) và s(k)như nhau không phân biệt X∗ với S. Ký hiệu ω∗(t) là trạng thái tốt nhất các con kiến tìm được cho tới lúc này và ωi(t) là lời giải tốt nhất trong bước lặp. Ở bước lặp t, ω∗(t) sẽ được xem là lời giải gần đúng của bài toán. Quy tắc chuyển trạng thái Giả sử con kiến k đã xây dựng được lời giải tiềm năng xk = , nó sẽ 31 chọn đỉnh y thuộc J(xkn) để có xkn+1 với xác suất : P(y|τ, xkn) =  ταu,yhu,y ∑j∈J(xk) τ α u,jhu,j y ∈ J(xk)0 ngược lại (2.2.2) Quy tắc cập nhật mùi Quy tắc cập nhật mùi có tính phổ dụng cho các thuật toán và là yếu tố ảnh hưởng lớn tới chất lượng thuật toán. Để đảm bảo vết mùi hội tụ, người ta sử dụng hằng số bay hơi vết mùi 0 < ρ <= 1 hay hệ số chiết khấu trong học tăng cường, khi một cạnh được cập nhật mùi thì vết mùi biến đổi theo công thức: τij ← (1− ρ)τij + ∆ij Điểm then chốt là cạnh nào được cập nhật và lượng them vào thế nào là tùy theo quy tắc được chon. Có nhiều quy tắc cập nhật mùi đã được đề xuất, trong đó điển hình là các quy tắc hệ kiến (Ant System: AS), hệ đàn kiến (ACS), hệ kiến Max- Min(Max–Min Ant System: MMAS) và hệ kiến Max-min trơn (Smooth Max-Min Ant System: SMMAS). Hệ kiến AS Hệ kiến AS áp dụng quy tắc cập nhật mùi địa phương, và là quy tắc đầu tiên được áp dụng trong số các thuật toán ACO. Theo quy tắc này, ở bước lặp t, mỗi kiến k áp dụng cập nhật mùi cho tất cả các cạnh (ui, ui+1) thuộc lời giải ωk(t) theo công thức: ∆i,j = ρ 1Lk nếu(i, j) ∈ (ω(t))0 khác (2.2.3) trong đó Lk là giá trị hàm mục tiêu f (ωk(t)) (không giảm tổng quát,được giả thiết là dương). Nhược điểm của quy tắc là vết mùi ở các cạnh không được cập nhật sẽ nhanh chóng dần về không nên hạn chế không gian tìm kiếm và thuật toán kém hiệu quả. Quy tắc ACS Quy tắc này do Dorigo đề xuất năm (1997). Trong thuật toán ACS, việc cập nhật mùi bao gồm cả hai hình thức địa phương và toàn cục. Cập nhật mùi địa phương áp dụng cho mọi cạnh có kiến k sử dụng khi nó tìm lời giải. có hai cách cập nhật mùi toàn cục. a) Cập nhật mùi toàn cục áp dụng cho các cạnh thuộc lời giải tốt nhất của bước lặp ω(t)hay toàn cục ω∗(t) và gọi tương ứng là i-best hay G-best. Theo cách i-besst, ∆τi,j được xác định theo công thức: ∆τi,j = ρ f (ω(t)) (2.2.4) 32 b) Cập nhật mùi toàn cục áp dụng cho tất cả các cạnh và cũng các hai cách i-best hay G-best, với G-best thì ∆τij xác định theo công thức: ∆i,j = ρ 1f (ω∗(t)) nếu(i, j) ∈ (ω∗(t))0 khác (2.2.5) Quy tắc MMAS Để khắc phục nhược điểm nêu trên của AS và ACS, Stutzle Hoos (2000) đề xuất MMAS gồm 2 bước. Bước thứ nhất, cập mùi toàn cục cho tất cả các cạnh theo phương thức i-best hoặc G-best. Bước thứ hai, so sánh các τi,jvới hai đại lượng τmax và τmin với τmax > τmin > 0 để giới hạn vết mùi trong đoạn [τmax, τmin], cụ thể như sau: τi,j =  τmax nếuτi,j > τmax τi,j nếuτi,j ∈ [τmin, τmax] τmin nếuτi,j < τmin (2.2.6) Nói chung, MMAS dùng i-best tốt hơn G-best nhưng cũng có thể dung luân phiên cho các bước lặp. Khi bắt đầu thuật toán, vết mùi thường được thiết đặt bằng ước lượng cận trên của vết mùi τmax. Cách khởi tạo như vậy kết hợp với tham số bay hơi nhỏ làm chậm sự khác biệt vết mùi của các cạnh, do đó giai đoạn đầu của MMAS mang tính khám phá. Nhờ giới hạn vết mùi trong đoạn [τmin, τmax] , MMAS hạn chế được tình trạng vết mùi dần về không, khắc phục được nhược điểm của AS và ACS. Quy tắc SMMAS Quy tắc SMMAS lần đầu tiên được Đỗ Đức Đông và cộng sự dùng cho bài toán lập lịch sản xuất và được trình bày chặt chẽ cho bài toán TSP. SMMAS được đề xuất dựa trên nhận xét hai nhược điểm của MMAS: • Thứ nhất, nếu chọn τmax, τmin lệch nhau ít thì làm triệt tiêu hiệu quả học tăng cường, còn nếu chọn lệch nhau nhiều thì vết mùi ở các cạnh ít được cập nhật sẽ nhanh chóng về τmin làm hạn chế không gian tìm kiếm mặc dù có nhẹ hơn AS và ACS. • Thứ hai là đâị lượng ∆τi,j phụ thuộc giá trị hàm mục tiêu làm cho thuật toán phải tính toán phức tạp, tuy nhiên trong học tăng cường thì không cần thiết. Một trong các cải tiến là khi khởi tạo lại vết mùi, việc cập nhật mùi thường xuyên bằng lời giải tốt nhất tìm được mới nhất thay vì cố định. 33 Với nhận xét trên, SMMAS không giảm vết mùi ở các cạnh không thuộc lời giải tốt quá nhanh như quy tắc MMAS mà dùng quy tắc Max-Min trơn bằng cách cập nhật τi,j toàn cục cho mọi cạnh với ∆τi,j xác định bởi: τij ← (1− ρ)τij + ∆ij trong đó: ∆i,j = ρτmax nếu(i, j) ∈ (t)ρτmin khác (2.2.7) Quy tắc này cũng khởi tạo τ0 = τmax. Đây là một phương pháp cập nhật mùi dễ cài đặt và có độ phức tạp tính toán cũng thấp hơn so với các phương pháp trước nó. Thực nghiệm và phân tích toán học cho thấy nó tốt hơn MMAS. Tái khởi tạo vết mùi Việc sử dụng thông tin vết mùi như cơ chế học tăng cường giúp ta tìm kiếm quanh lời giải tốt, tuy nhiên có thể bỏ sót những miền tiềm năng chứa lời giải tốt hơn. Để tăng tính khám phá, nếu sau một số bước lặp mà lời giải tốt nhất ω∗(t) tìm được không đổi so với các bước trước đó thì nên khởi tạo lại vết mùi. Tìm kiếm địa phương Lược đồ ACO ở trên thực hiện tìm kiếm ngẫu nhiên để tìm lời giải gần đúng nên không gian tìm kiếm rộng. Thông thường thì các kỹ thuật tìm kiếm địa phương hội tụ đến cực trị địa phương nhanh hơn. Vì vậy người ta thường áp dụng kỹ thuật tìm kiếm địa phương để tăng cường chất lượng lời giải cho lời giải tốt nhất hoặc cho mọi lời giải trong mỗi bước lặp trước khi cập nhật mùi. 34 Chương 3 Thuật giải di truyền cho bài toán q-CaRS Như đã giới thiệu trong chương 1, thuật toán tiến hóa sử dụng những nguyên tắc của sự tiến hóa để khai thác và tìm kiếm các giải pháp trong bài toán tối ưu. Giải thuật di truyền cũng tương tự như vậy. Giải thuật di truyền cổ điển sử dụng những nguyên tắc của sự tiến hóa dựa trên sự chuyển đổi của gen theo chiều dọc, ví dụ sự kế thừa của con cái từ cha mẹ. Với sự phổ biến của lý thuyết tiến hóa trong ngành khoa học máy tính, các cơ chế tiến hóa khác được tạo ra ví dụ như chuyển đổi gen theo chiều ngang (HGT), và HGT cũng được coi là nền tảng cho sự tiến hóa của nhiều ngành khoa học. HGT, còn được gọi là chuyển gen ngoài, tức là ngoài việc kế thừa từ cha mẹ sang con thì gen có thể được kế thừa từ những sinh vật khác [10]. Các cơ chế chính của HGT là chuyển đổi, phân chia và truyền dẫn. Chuyển đổi là sự hấp thụ thông tin di truyền tự nhiên của sinh vật từ bên ngoài, phân chia là quá trình chuyển giao thông tin di truyền thông qua sự tiếp xúc vật lý từ tế bào cho sang tế bào nhận. Và truyền dẫn là quá trình chuyển đổi gen thông qua một virus trung gian. Các yếu tố di truyền di động như transposons và plasmid là phương tiện quan trọng giữa HGT và vi khuẩn. Transposons hay các gen nhảy là các đoạn DNA có khả năng dịch chuyển nơi cư trú của chính mình trong một bộ gen. Một plasmid là một phân tử AND nhỏ có khả năng sao chép độc lập. Các bài toán dựa trên sự dịch chuyển của transposon được lần đầu giới thiệu trong [35] . Tuy nhiên, những nghiên cứu dựa trên hành động của plasmid ít được nghiên cứu rộng rãi. Một giải thuật tiến hóa dựa trên sự biến đổi của plasmids được giới thiệu trong [36, 37] và được áp dụng cho bài toán xếp ba lô dạng 0/1, thuật toán sử dụng sự tổng hợp các đoạn DNA vào nhiễm sắc thể. Các đoạn DNA là những chuỗi nhị phân được thu thập từ một kho lưu trữ được tạo ra từ lúc bắt đầu của quá trình tiến hóa và được cập nhật theo thời gian thực. Một ý tưởng tương tự được giới thiệu trong 35 [13], đã sử dụng một virus để vận hành sự chuyển đổi gen giữa các nhiễm sắc thể trong giải thuật di truyền. Cơ chế HGT cũng đóng một vài trò quan trọng trong giải thuật tiến hóa vi khuẩn (BEA) trong [31]. Thuật toán BEA lấy những phần tốt nhất của nhiễm sắc thể để sao chép sang những nhiễm sắc thể xấu. Một biến thể memetic của BEA được giới thiệu trong [12] và được áp dụng trong TSP. Thao tác của plasmid và transposon đều được sử dụng trong thuật chuyển đổi gen trong [19, 22] để thúc đẩy sự phát triển của những giải pháp tiềm năng mới. Các thao tác tái tổ hợp và chéo nhau không được sử dụng cho những thuật toán trên. Những nghiên cứu của lý thuyết tiến hóa cũng được xem xét cho những sinh vật nhân sơ(prokaryotes), gần đây có nhiều nghiên cứu đã cung cấp bằng chứng rằng nó cũng xảy ra với cả những sinh vật nhân chuẩn(eukaryotes). Trong luận văn này, thuật toán tiến hóa sử dụng thao tác plasmid của nhiễm sắc thể và đồng thời sử dụng thao tác tái sản sinh . 3.1. Biểu diễn quần thể Trong bài toán này ta sẽ biểu diễn nhiễm sắc thể dạng nguyên. Mỗi nhiễm sắc thể là một mảng hai chiều với một hàng là tập tuần tự các thành phố đến thăm và một hàng là tập các xe được sử dụng. Hình 3.1: Nhiễm sắc thể Thuật toán láng giềng gần nhất được sử dụng để xây dựng đường dẫn giữa 2 thành phố theo chi phí cạnh của chiếc xe gắn liền với con đường đó. Tour bắt đầu tại thành phố 1. Xe c1 được chọn ngẫu nhiên để di chuyển từ thành phố 1 tới thành phố ngẫu nhiên i (c1 được trả lại ở i). Nếu giá trị ràng buộc tối thiểu không được thu thập, thành phố i sẽ là điểm khởi tạo trong phần tiếp theo của tour. Một xe mới c2 và một thành phố chưa đến thăm j sẽ được chọn ngẫu nhiên. Một đường dẫn sẽ được tạo ra giữa thành phố i và j bằng việc chỉ xem xét đến các thành phố chưa đến thăm. Tiến trình sẽ tiếp diễn cho đến khi thu được giá trị ràng buộc nhỏ nhất. Chu trình sẽ được đóng với một cạnh từ thành phố cuối cùng trong tour đi đến thành phố 1. Bài toán biến thể được xem xét đến trong nghiên cứu này không cho 36 phép một xe có thể được thuê nhiều hơn 1 lần, vậy nên nếu không còn xe mới nào được thêm thì chiếc xe cuối cùng sẽ được sử dụng dể di chuyển đến các thành phố khác cho đến khi thu được giá trị rằng buộc tối thiểu . 3.2. Quá trình tái tạo Quá trình tái tạo được thực hiện dựa vào toán tử di truyền và biến dị. Toán tử tương giao chéo: Khi khởi tạo quần thể, một tập các cá thể tốt nhất sẽ được chọn ra gọi là tập elite. Trong mỗi lần tái tạo ta sẽ chọn ngẫu nhiên một cá thể trong quần thể và một cá thể trong tập các cá thể tốt nhất để tương giáo chéo với điểm tương giao chéo là ngẫu nhiên. Sau khi tái tạo tập các cá thể tốt nhất được cập nhật lại. Toán tử biến dị: Toán tử biến dị ở đây chính là một đoạn plasmid là đoạn gen được chọn ra từ tập elite. Một đoạn gen trong cá thể được chọn lọc để tái tạo sẽ được thay thể tương ứng với plasmid. Hình 3.2: Plasmid Ví dụ trong hình 3.2 một cá thể sol được chọn ra từ quần thể và cá thể sol’ được chọn ra từ tập elite. Một đoạn plasmid được chọn ra từ sol’. Tương tự ta loại bỏ 1 đoạn gen ngẫu nhiên có kích thước bằng với plasmid từ sol cho kết quả là sol". Thay thể đoạn gen bị loại bỏ bằng plasmid ta có kết quả là sol”’. 37 3.3. Thủ tục tìm kiếm địa phương Để tăng cường chất lượng của lời giải "sol" ta có thủ tục tìm kiếm địa phương multiOperatorsSearch với 6 thủ tục: -removeSaving: sẽ loại bỏ các thành phố có giá trị hạn ngạch thấp nhất từ sol cho đến khi tổng ràng buộc yêu cầu là nhỏ nhất. Ví dụ như hình ta có một nhiễm sắc thể với 1 chiều là mảng các thành phố, mỗi thành phố có một mức độ hài lòng. Tổng mức độ hài lòng yêu cầu là 288 nhưng tổng mức độ hài lòng hiện tại đang là 330, vì thế ta sẽ loại bỏ một số thành phố. Thành phố 7 đang có mức độ hài lòng thấp nhất nên sẽ là điểm loại bỏ đầu tiên. Sau khi loại bỏ thành phố 7 mức độ hài lòng là 317 vẫn lớn hơn yêu cầu, ta tiếp tục xét đến thành phố liền kề đứng trước thành phố 7 là thành phố 6. Tiếp tục loại bỏ thành phố 6 mức độ hài lòng là 290 vẫn lớn hơn 288. Xét tiếp thành phố 5 nhưng tồng mức độ hài lòng là 257 nhỏ hơn 288 vì vậy ta không thể loại bỏ thành phố 5. Đây là kết cuối cùng sau thủ tục removeSaving. Hình 3.3: removeSaving -invertSol: Hàm đảo ngược invertSol của sol có kết quả là sol ′ . Những xe liên quan tới các thành phố trong sol cũng có giá trị sol ′ tương đương. Thứ tự của các 38 lượt thăm được đảo ngược, do đó các điểm cho thuê và các điểm trả lại được trao đổi, điều này làm ảnh hưởng đến chi phí của giải pháp. Thủ tục invertSol trả về giải pháp tốt nhất giữa sol và sol ′ . Hình 3.4: invertSol -replaceSavingCity: Tất cả những thành phố chưa thăm được xem xét cho sự bổ sung. Mỗi thành phố chưa thăm được kiểm tra để thay thế 1 thành phố trong sol. Những xe đã được gán sẽ không thay đổi. Trong hình 3.5 , thành phố 7 là thành phố chưa được thăm. Ta sẽ xét thay thế thành phố 7 cho các thành phố 2, 3, 4, 5 Hình 3.5: replaceSavingCity -insertSavingCity: Thủ tục insertSavingCity cũng tập trung vào các thành phố chưa được thăm, các thành phố chưa được thăm sẽ được chèn vào các vị trí mà không loại bỏ bất kì thành phố nào trong sol. Xe được thuê là xe tương ứng với thành phố trước đó. Trong hình 3.6, thành phố 2 là thành phố chưa được thăm. Ta sẽ bổ sung thành phố 2 39 Hình 3.6: insertSavingCity -replaceSavingCar: Thủ tục replaceSavingCar kiểm tra việc chèn xe chưa được sử dụng . Tất cả những chiếc xe chưa sử dụng được xem xét và chèn vào tại tất cả các điểm của sol. Ví dụ minh họa thay thế chiếc xe 1 trong các hình: 3.7, 3.8, 3.9, 3.10 Hình 3.7: Thay thế xe 1 bắt đầu từ vị trí 2 40 Hình 3.8: Thay thế xe 1 bắt đầu từ vị trí 3 Hình 3.9: Thay thế xe 1 bắt đầu từ vị trí 4 41 Hình 3.10: Thay thế xe 1 bắt đầu từ vị trí 5 - 2-opt.:Tất cả 2-opt di chuyển đều được kiểm tra. Trình tự của xe gắn với tour cũng sẽ được giữ nguyên. Lời giải cụ thể được biểu diễn trong thuật toán MemPlas dưới đây 3.4. Thuật toán MemPlas Mã giả của thuật toán MemPlas được biểu diễn trong (thuật toán 1) . Đầu vào của thuật toán có 5 tham số: số lượng quần thể (sizePop), kích thước của plasmid (sizePlas), tỉ lệ tái tổ hợp (#cross), kích thước của các lớp (#elite) và số lần lặp tối đa (limitIter). Tâp giá trị elite sẽ chứa những #elite tốt nhất từ quần thể. Plasmid bao gồm những đoạn gen thu được trong tập elite. Trong 9 lần lặp, nhiễm sắc thể sẽ được tái tổ hợp. Trong lần lặp cuối cùng, một plasmid sẽ được sử dụng để thay đổi nhiễm sắc thể đã chọn. 42 Hình 3.11: Thuật toán MemPlas Thao tác khôi phục có thể cần thiết sau khi thực hiện tái tổ hợp hoặc plasmid. Giải pháp có thể cần được sửa chữa do các tour du lịch không khả thi hoặc việc phân chia xe không khả thi hoặc là việc thu thập hạn mức là không khả thi. Hình 2 minh hoạ một nhiễm sắc thể C mà cần phải sửa chữa. Thành phố 3 và 7 trong C đã đến thăm 2 lần và xe 2 và 3 đã được thuê 2 lần. Thao tác sửa chữa được mô tả trong [22]. Để xóa bỏ tính chất không khả thi của tour, một dấu sao (*) sẽ thay thế một thành phố trong nhiễm sắc thể. Những thành phố được chọn ngẫu nhiên trong những thành phố chưa thăm. Nếu không còn thành phố nào chưa thăm thì gen tương ứng với dấu sao sẽ được xóa. Để bỏ tính chất không khả thi của việc phân chia xe, dấu * sẽ thay thế cho việc lặp đi lặp lại việc thuê xe như trong nhiễm sắc thế thứ hai trong hình 2. Sau đó ta sẽ quét từ trái sang phải và dấu * trong index i sẽ được thay thế bởi thành phần index i-1. Cuối cùng, giá trị ràng buộc nhỏ nhất được xác nhận. Đặt l là giá trị biểu diễn số lượng thành phố đã thăm. Nếu yều cầu ràng buộc không được thỏa mãn thì các giá trị ràng buộc sẽ được sắp xếp theo thứ tự không giảm và thành phố tương ứng được đánh số từ 1 đến l. Thủ tục bắt đầu từ thành phố đầu tiên và nó sẽ duyệt để thay thế một thành phố đã thăm với một thành phố chưa thăm mà có giá trị ràng buộc cao hơn cho đến khi yêu cầu được thỏa mãn. Nếu thành phố thứ l đã được thay thế mà yêu cầu vẫn chưa được thỏa mãn thì các thành phố sẽ được bổ sung ngẫu nhiên vào vị trí cuối cùng cho đến khi yêu cầu ràng buộc đạt yêu cầu. Khi đó xe sẽ được gán với mỗi thành phố được thêm cho đến thành phố cuối cùng. 43 Hình 3.12: Sửa chữa tour 3.5. Kết quả thực nghiệm 3.5.1. Bộ dữ liệu chuẩn Trong phần này sẽ giới thiệu kết quả của việc tính toán thực nghiệm dựa trên 40 trường hợp q-CaRS. Dữ liệu được lấy từ Các thông số trong mỗi file: DIMENSION: Số lượng thành phố. CARS_NUMBER: Số lượng xe để thuê. NODE_COORD_SECTION: Tọa độ thành phố . EDGE_WEIGHT_SECTION: Giá thuê xe tại mỗi thành phố. RETURN_RATE_SECTION: Giá thuế trả lại xe tại mỗi thành phố. Chí phí di chuyển từ thành phố i đến thành phố j với chiếc xe c được tính theo công thức như sau: dcij = 2Lc[i] + 3Lc[j] 3 + d[i][j] (3.5.1) Mức độ hài lòng tại mỗi thành phố được tạo ngẫu nhiên trong khoảng(0, 100); 3.5.2. Tiến hành chạy thực nghiệm Chương trình được viết bằng ngôn ngữ Java chạy trên máy Desktop cấu hình CPU intel core i5 2.5Ghz Ram 4GB, sử dụng hệ điều hànhWindow10. Vì GA là lớp thuật toán meta-heuristic nên mỗi lần chạy sẽ cho các kết quả cụ thể là khác nhau, nên tôi tiến hành chạy chương trình 10 lần trên mỗi bộ dữ liệu, thống kê kết quả lấy giá trị kết quả tốt nhất và kết quả trung bình. Bên cạnh đó là thời gian tương ứng chạy với các kết quả. 3.5.3. Kết quả thực nghiệm Phần này thực hiện với hai bộ tham số khác nhau để đánh giá về mức độ ảnh hưởng khi thay đổi các tham số đầu vào 44 Tiến hành thực nghiệm với các tham số Tham số Giá trị Số lượng quần thể( sizePop) 150 Số lượng vòng lặp 10 Tỉ lệ tái tổ hợp(#cross) 0.4 Tỉ lệ chọn các cá thể tối ưu ( #elite) 0.3 Kích thước của plasmid(sizePlas) [3, 0.4s] với s là kích thước cá thể chứa plasmid 45 Hình 3.13: Kết quả thực nghiệm 1 của GA 46 Tiến hành thực nghiệm với các tham số Tham số Giá trị Số lượng quần thể( sizePop) 150 Số lượng vòng lặp 10 Tỉ lệ tái tổ hợp(#cross) 0.5 Tỉ lệ chọn các cá thể tối ưu ( #elite) 0.5 Kích thước của plasmid(sizePlas) [3, 0.4s] với s là kích thước cá thể chứa plasmid 47 Hình 3.14: Kết quả thực nghiệm 2 của GA Bảng trên thống kê kết quả sau 10 lần chạy thực nghiệm đối vởi cả 35 bộ dữ. Trong đó mỗi hàng thể hiện cho một bộ dữ liệu. Kết quả trung bình là kết quả chạy trung bình của 10 lần chạy, kết quả tốt nhất là kết quả tốt nhất trong 10 lần chạy. Tương ứng là thời gian chạy với các kết quả. Từ các kết quả thực nghiệm khi tỉ lệ tương giao và tỉ lệ chọn các nhiễm sắc thể ưu tú cao thì kết quả không tốt với tỉ lệ thấp hơn. Việc lựa chọn ngẫu nhiên các nhiễm 48 sắc thể từ một tập lớn hơn sẽ bị ảnh hưởng đến chất lượng, bởi khi đó có thể chọn vào các nhiễm sắc thể không tốt. Tuy nhiên nếu chọn tỉ lệ quá thấp có thể rơi vào trạng thái cục bộ, bỏ qua kết quả tốt khác. Vì vậy tùy vào từng yêu cầu bài toán ta có thể lựa chọn tỉ lệ một cách mềm dẻo để cho chất lượng lời giải tốt nhất. 49 Chương 4 Thuật toán ACO giải bài toán q-CaRS 4.1. Đồ thị cấu trúc Giải bài toán tối ưu tổ hợp bằng thuật toán ACO việc quan trọng nhất là xây dựng cấu trúc đồ thị. Ta có: A = a1, a2, ..., an là tập các thành phố. C = c1, c2, ..., cm là tâp các xe để di chuyển. Đồ thị cấu trúc của bài toán G = {V, E} được xây dựng như sau: Đồ thị bao gồm l tầng như hình 4.1 . Mỗi đỉnh bao gồm thành phố xuất phát và chiếc xe để di chuyển đến thành phố tiếp theo : vci = (i, c) : i ∈ A, c ∈ C. Các cạnh của đồ thị ei j = (vci , v c′ j ) : vi, vj ∈ A, i < j, c, c′ ∈ C nối các đỉnh đồ thị. Thông tin heuristic được đặt trên các cạnh của đồ thị kí hiệu là τ(vci , v c′ j ). Quy tắc cập nhật vết mùi được áp dụng theo thuật toán SMMAS[2]. 50 Hình 4.1: Đồ thị cấu trúc Thuật toán được xây dựng như dưới đây: Bước 1. Khởi tạo ma trận vết mùi, và tập K gồm k kiến. Bước 2. Thực hiện lặp trong khi chưa thoả mãn điều kiện dừng Với mỗi kiến ta tiến hành các bước sau: 2.1. Khởi tạo đỉnh xuất phát vci bằng cách chọn thành phố cơ sở và chiếc xe di chuyển c thuộc C. Cập nhật lại A = A− i . 2.2 Thực hiện lặp với t >= 2. Chọn đỉnh tiếp theo vc ′ j = (j, c ′) với xác suất Pvci vc ′ j = [τ vci v c′ j ]α[η vci v c′ j ]β ∑l∈A,c′∈C[τvci vc ′ l ]α[η vci v c′ l ]β .Cập nhật lại A = A − i . Nếu đỉnh trước đó được chọn có xe c 6= c′ ta cập nhật lại C = C− c 2.3. Thực hiện tìm kiếm cục bộ trên lời giải tốt nhất do các kiến tìm được để cải thiện chất lượng lời giải. 2.4. Cập nhật lại lời giải tốt nhất. 2.4. Cập nhật vết mùi theo quy tắc SMMAS dựa trên lời giải tốt nhất. Bước 3. Lưu lại lời giải tốt nhất. Sơ đồ thuật toán của việc xây dựng một lời giải pi bởi một con kiến được phác thảo dưới đây: 51 Hình 4.2: Xây dựng lời giải của kiến 4.2. Vết mùi và thông tin heuristic Vết mùi τ(vci , v c′ j ) trên cạnh τ(v c i , v c′ j ) được khởi tạo bằng τmax và được cập nhật lại theo mỗi vòng theo công thức. Thông tin heuristic đươc tính theo công thức: ηvci v c′ j = 1 dcij + γ c ij (4.2.1) trong đó dcij là chi phí di chuyển từ thành phố i đến thành phố j và γ c ij là chi phí trả lại chiếc xe nếu tại j xe c không được thuê . 4.3. Quy tắc cập nhật mùi Sau khi tất cả các kiến đã xây dựng lời giải, lời giải của kiến tốt nhất được áp dụng thủ tục tìm kiếm cục bộ để tăng chất lượng lời giải. Lời giải tốt nhất này được sử dụng để cập nhật vết mùi trên các cạnh theo quy tắc cập nhật mùi SMMAS: τ(vci , v c′ j ) = (1− ρ)τ(vci , vc ′ j ) + ∆vci ,vc ′ j (4.3.2) 52 trong đó: ∆vci ,vc ′ j = ρτmax nếu(vci , vc ′ j ) ∈ bestsolution ρτmin nếu (vci , v c′ j ) /∈ bestsolution (4.3.3) Trong đó τmax và τmin là các tham số được cho trước, ρ ∈ (0, 1) là tham số bay hơi cho trước quy định 2 thuộc tính, ρ nhỏ thể hiện việc tìm kiếm quanh thông tin học tăng cường, ρ lớn thể hiện tính khám phá. 4.4. Thủ tục tìm kiếm cục bộ Để tăng cường chất lượng lời giải, ta sử dụng thêm thủ tục tìm kiếmđịa phương. Thục tục tìm kiếm cục bộ trong phần này được áp dụng hàmmultiOperatorsSearch như trong thuật toán GA ở phần trên. 4.5. Kết quả thực nghiệm Thực nghiệm được tiến hành để so sánh với thuật toán GA nên sử dụng bộ dữ liệu chuẩn như trong GA với cấu hình máy tương tự. Vì ACO là lớp thuật toán meta-heuristic nên mỗi lần chạy sẽ cho các kết quả cụ thể là khác nhau, nên tôi tiến hành chạy chương trình 10 lần trên mỗi bộ dữ liệu, thống kê kết quả thu được, so sánh thông qua 2 tiêu trí là kết quả tốt nhất, kết quả xấu nhất và kết quả trung bình của 10 lần chạy đó. Để so sánh với thuật toán GA ta sẽ chạy thực nghiệm của ACO với cùng số lời giải. Như giới thiệu ở trên, GA sử dụng số lượng quần thể là 150 và số vòng lặp là 10, do đó trong ACO ta sử dụng 10 kiến và đẩy số lượng vòng lặp là 150. 4.6. Kết quả thực nghiệm và đánh giá Tương tự với thuật toán GA ta cũng thực nghiệm với hai bộ tham số khác nhau để đánh giá mức độ ảnh hưởng của các tham số 53 Tiến hành thực nghiệm với các tham số Tham số Giá trị Tham số bay hơi( ρ) 0.03 α 2 β 6 Số kiến ban đầu 10 Số vòng lắp 150 τmax 0.1 τmin 0.008 Kết quả chạy: 54 Hình 4.3: Kết quả thực nghiệm 1 của ACO 55 Tiến hành thực nghiệm với các tham số Tham số Giá trị Tham số bay hơi( ρ) 0.03 α 2 β 6 Số kiến ban đầu 10 Số vòng lắp 150 τmax 0.1 τmin 0.008 Kết quả chạy: 56 Hình 4.4: Kết quả thực nghiệm 2 của ACO Bảng trên thống kê kết quả sau 10 lần chạy thực nghiệm đối vởi cả 35 bộ dữ. Trong đó mỗi hàng thể hiện cho một bộ dữ liệu. Kết quả trung bình là kết quả chạy trung bình của 10 lần chạy, kết quả tốt nhất là kết quả tốt nhất của 10 lần chạy. Tương ứng là thời gian chạy với các kết quả. Kết quả cho thấy khi tham số bay hơi nhỏ thì thực nghiệm tốt hơn. Điều này cho thấy việc học tăng cường trong bài toán này là quan trọng hơn. 57 So sánh với kết quả thực nghiệm của thuật toán GA Trong phần này ta sẽ so sánh kết quả của hai thuật toán GA và ACO với bộ tham số cho kết quả tốt nhất. Hình 4.5: So sánh kết quả thực nghiệm của ACO và GA Từ bảng so sánh ta thấy thuật toán ACO cho kết quả tốt hơn GA rất nhiều cả về chất lượng và thời gian chạy trong nhiều trường hợp. Chỉ có 4 trường hợp được 58 in đậm trên tổng số 35 trường hợp tức là khoảng 11.5% kết quả cho thấy GA tốt hơn. Như vậy tùy từng yêu cầu của bài toán về thời gian và chất lượng, nếu yêu cầu thời gian chạy thấp ta có thể hoàn toàn sử dụng ACO để tìm kiếm lời giải.Tuy nhiên mức độ ảnh hưởng của các tham số là khá lớn, vì vậy cần linh hoạt trong bước lựa chọn tham số. 59 Phụ lục Phụ lục này sẽ trình bày cách chạy chương trình và một số modules cơ bản của thuật toán MemPlas dưới dạng ngôn ngữ Java 8. Cách chạy chương trình: Bước 1: mở chương trình với IDE ’ItelliJ IDEA’ như hình 4.6 Hình 4.6: Mở chương trình Bước 2: Bấm nút ’Run’ để chạy chương trình như hình 4.7 60 Hình 4.7: Chạy chương trình Kết quả được ghi vào file ’myfile.txt’. Một số modules cơ bản: Class City public class City implements Comparable{ private String name; private double x = 0; private double y = 0; private double satisfaction = 0; public double getX() { return x; } public double getY() { return y; } public String getName() { return this.name; } 61 public double getSatisfaction() { return this.satisfaction; } public double getDistance(City city) { return Math.sqrt(Math.pow(city.getX() - x, 2) + Math.pow(city.getY() - y, 2)); } public City(String name, double x, double y, double satisfaction) { this.name = name; this.x = x; this.y = y; this.satisfaction = satisfaction; } public int compareTo(City city) { double compareSatisfaction = ((City) city).getSatisfaction(); return (int) (compareSatisfaction - this.satisfaction); } } Class Car: import java.util.HashMap; public class Car { private String name; public HashMap prices = new HashMap(); public HashMap returnTaxes = new HashMap(); public String getName() { return name; } 62 public Car(String name) { this.name = name; } public void setCityReturnTax(City city, double value) { returnTaxes.put(city, value); } public double getCityReturnTax(City city) { return returnTaxes.get(city); } public void setCityPrice(City city, double value) { prices.put(city, value); } public double getCityPrice(City city) { return prices.get(city); } public double getCarTax(City city) { return getCityReturnTax(city); } public double getCarPrice(City fromCity, City toCity) { double distance = fromCity.getDistance(toCity); double price = (2 * getCityPrice(fromCity) + 3 * getCityPrice(toCity)) / 3 + distance; return price; } } Class CityCar public class CityCar { private City city; private Car car; 63 public CityCar(City city, Car car) { this.city = city; this.car = car; } public City getCity() { return city; } public Car getCar() { return car; } } 64 KẾT LUẬN Trong luận văn này emđã trình bày được nội dung thuật toán di truyền, phương pháp tối ưu hóa đàn kiến, mô hình quy hoạch nguyên, bài toán thuê xe có hạn ngạch, đưa ra mô hình nguyên cho bài toán và áp dụng thuật toán di truyền và phương pháp tối ưu hóa đàn kiến giải bài toán trên. Kết quả thực nghiệm tính toán được biểu diễn bằng cách cố định số lần lặp, cố định số lần đánh giá và cố định thời gian xử lý đồng thời sử dụng hệ thống kiểm định để phát hiện sự khác biệt trọng yếu trong thuật toán nhẳm đảm bảo chất lượng của giải pháp. Kết quả thu được chỉ ra rằng thuật toán phương pháp tối ưu hóa đàn kiến cho kết quả và thời gian chạy tốt hơn trong nhiều trường hợp. Vấn đề được trình bày trong nghiên cứu này là mới, vậy nên có thể có một số vấn đề có thể được nghiên cứu trong tương lai, ví dụ như ứng dụng của meta- heuristic và thủ tục tìm kiếm địa phương, hoặc là nghiên cứu các biến thể khác của q-CaRS, ví dụ một phiên bản với 2 tham số mà tổng ràng buộc được tối đa và chi phí là nhỏ nhất. Đóng góp chính của luận văn bao gồm: 1 Tìm hiểu và trình bày lại nội dung bài toán thuê xe có hạn ngạch q-CaRS. 2 Trình bày lại thuật toán di truyền giải bài toán q-CaRS và đề xuất thêm phương pháp tối ưu hóa đàn kiến để giải bài toán. 3 Lập trình và đưa ra kết quả thực nghiệm đánh giá của hai thuật toán. Tuy nhiên do thời gian thực hiện luận văn không nhiều còn có những sai sót em rất mong nhận được sự góp ý của quý thầy cô và bạn đọc. 65 Tài liệu tham khảo [1] Hoàng Xuân Huấn, Giáo trình tối ưu tổ hợp. [2] D.D.Do, Q.H.Dinh, H.X.Hoang (2008), On the pheromone update rules of ant- colony optimization approaches for the job shop scheduling problem. In The 11th Paci-c Rim International Conference on Multi-Agents:Intelligent Agents and Multi-Agent Systems, volume 5357 of Lecture Notes in ComputerScience, 153- 160, Springer, Heidelberg. [3] W.P. Adams, R.J. Forrester, F.W. Glover, Comparisons and enhancement strategies for linearizing mixed 0–1 quadratic programs, Discrete Optim, 1 (2)(2004) 99–120. [4] J.O. Andersson, Lateral gene transfer in eukaryotes, Cell. Mol. Life Sci. 62 (11) (2005) 11821197. [5] G. Ausiello, M. Demange, L. Laura, V. Paschos, Algorithms for the on-line quota traveling salesman problem,Inf. Process. Lett. 92 (2) (2005) 89–94 [6] B. Awerbuch, Y. Azar, A. Blum, S. Vempala, New approximation guarantees for minimum-weight k-trees and prize-collecting salesmen, SIAM J. Comput.28 (1) (1998) 254–262. [7] T.-M. Chan, K.-F. Man, K.-S. Tang, S.A. Kwong, A jumping gene algorithm for multiobjective resource management in wideband cdma systems, Comput.J. 48 (6) (2005) 749–768. [8] K. Cheverst, K. Mitchell, N. Davies, The role of adaptive hypermedia in a context- aware tourist guide, Commun. ACM 45 (5) (2002) 47–51. [9] G.A. Croes, A method for solving traveling-salesman problems, Oper. Res. 6 (1958) 791–812. [10] J.D.V. Elsas, S. Turner, M.J. Bailey, Horizontal gene transfer in the phytosphere, New Phytol. 157 (3) (2003) 525–537. 66 [11] A. Fink , T. ReinersModeling and solving the short-term car rental logistics problem, Transp. Res. Part E 42 (4) (2006) 272–292 . [12] P. Fo¨ldesi, J. Botzheim, Modeling of loss aversion in solving fuzzy road transport traveling salesman problem using eugenic bacterial memetic algo- rithm, Memetic Comput. 2 (2010) 259–271. [13] T. Fukuda , N. Kubota , K. Shimojima ,Virusevolutionary genetic algorithm and its application to travelling salesmam problem, in: X. Yao (Ed.), Evolu-tionary Com- putation, Theory and Applications, World Scientific, 1999, pp. 235–255. [14] A. Garcia, P. Vansteenwegen, O. Arbelaitz, W. Souffriau, M.T. Linaza, Integrat- ing public transportation in personalised electronic tourist guides, Comput.Oper. Res. 40 (3) (2013) 758–774. [15] D. Gavalas, C. Konstantopoulos, K. Mastakas, G. Pantziou, A survey on algo- rithmic approaches for solving tourist trip design problems, J. Heuristics 20(3) (2014) 291–328. [16] D.K. George, C.H. Xia, Fleet-sizing and service availability for a vehicle rental sys- tem via closed queueing networks, Eur. J. Oper. Res. 211 (1) (2011)198–207. [17] F. Glover, E. Woolsey, Converting the 0–1 polynomial programming problem to a 0–1 linear program, Oper. Res. 22 (1) (1974) 180–182. [18] GLPK, A. Makhorin, Gnu linear programming kit. [19] E.F.G. Goldbarg, M.C. Goldbarg, Transgenetic algorithm: A new endosymbiotic approach for evolutionary algorithms, in: A. Abraham, A.-E. Hassanien, P. Siarry, A. Engelbrecht (Eds.), Foundations of Computational Intelligence Volume 3, Studies in Computational Intelligence, volume 203, Springer Berlin Heidel- berg, 2009, pp. 425–460. [20] M.C. Goldbarg, P.H. Asconavieta, E.F.G. Goldbarg, Memetic algorithm for the traveling car renter problem: an experimental investigation, Memetic Comput. 4 (2) (2012) 89–108. [21] M.C. Goldbarg, E.F. Goldbarg, M. da S. Menezes, H.P. Luna, A transgenetic algorithm applied to the traveling car renter problem, Expert Syst. Appl. 40 (16) (2016) 6298–6310 [22] M.C. Goldbarg, E.F. Goldbarg, P.H. Asconavieta, M. da S. Menezes, H.P. Luna, Quota traveling car renter problem: Model and evolutionary algorithm, Expert Syst. Appl. 40 (16) (2013) 6298–6310 67 [23] B. Golden, L. Levy, R. Vohra, The orienteering problem, Nav. Res. Logist. 34 (3) (1987) 307–318. [24] K. Hagen , R. Kramer , M. Hermkes , B. Schumann , P. Mueller , Semantic matching and heuristic search for a dynamic tour guide, in: Information and Com- munication Technologies in Tourism, Springer, 2005, pp. 149–159 . [25] Hansen, C. Meyer, Improved compact linearizations for the unconstrained quadratic 0–1 minimization problem, Discr. Appl. Math. 157 (6) (2009) 1267–1290. [26] R. Kramer , M. Modsching , K. ten Hagen , A city guide agent creating and adapt- ing individual sightseeing tours based on field trial results, Int. J. Comput.Intel. Res. 2 (2) (2006) 191–206 . [27] P. Hansen, C. Meyer, Improved compact linearizations for the unconstrained quadratic 0–1 minimization problem, Soft Comput. 11 (2007) 923941. [28] P. Kumar, D. Gospodaric, P. Bauer, Improved genetic algorithm inspired by biolog- ical evolution, Soft Comput. 11 (2007) 923941. [29] M.S. Menezes, M.C. Goldbarg, E.F.G. Goldbarg, A memetic algorithm for the prize-collecting traveling car renter problem, Evolutionary Computation(CEC), 2014 IEEE Congress on, 2014, pp. 3258–3265. [30] C.E. Miller, A.W. Tucker, R.A. Zemlin, Integer programming formulation of trav- eling salesman problems, J. ACM 7 (4) (1960) 326–329. [31] N.E. Nawa, T. Furuhashi, Fuzzy systems parameters discovery by bacterial evolu- tionary algoritm, IEEE Trans. Fuzzy Syst. 7 (5) (1999) 608–616. [32] A.M. Nedelcu, I.H. Miles, A.M. Fagir, K. Karol, Adaptative eukaryote-to- eukaryote lateral gene transfer: stress-related genes of algal origin in the closest uni- cellular relatives of animals, J. Evol. Biol. 21 (6) (2008) 18521860. [33] G. Reinelt, Tsplib– a traveling salesman problem library, ORSA J. Comput. 3 (4) (1991) 376. [34] M. Schilde, K. Doerner, R. Hartl, G. Kiechle, Metaheuristics for the bi-objective orienteering problem, Swarm Intel. 3 (3) (2009) 179–201. [35] A. Simões , E. Costa , Transposition: a biologically inspired mechanism to use with genetic algorithms, in: Proceedings of the Fourth International Conference on Neural Networks and Genetic Algorithms (ICANNGA’99), 1999, pp. 178–186. 68 [36] W. Souffriau, P. Vansteenwegen, G.V. Berghe, D.V. Oudheusden, A path relink- ing approach for the team orienteering problem, Comput. Oper. Res. 37(11) (2010) 1853–1859. [37] W. Souffriau, P. Vansteenwegen, J. Vertommen, G.V. Berghe, D.V. Oudheus- den, A personalised tourist trip design algorithm for mobile tourist guides, Appl. Artif. Intel. 22 (10) (2008) 964–985. [38] W. Souffriau, P. Vansteenwegen, G.V. Berghe, D.V. Oudheusden, A path relink- ing approach for the team orienteering problem, Comput. Oper. Res. 37(11) (2010) 1853–1859 . [39] W. Souffriau, P. Vansteenwegen, J. Vertommen, G.V. Berghe, D.V. Oudheus- den, A personalised tourist trip design algorithm for mobile tourist guides, Appl. Artif. Intel. 22 (10) (2008) 964–985. [40] T. Tsiligirides, Heuristic methods applied to orienteering, J. Oper. Res. Soc. 35 (9) (1984) 797–809 . [41] P. Vansteenwegen, D.V. Oudheusden, The mobile tourist guide: An or opportu- nity, OR Insights 20 (3) (2007) 21–27. [42] P. Vansteenwegen, W. Souffriau, G.V. Berghe, D.V. Oudheusden, Iterated local search for the team orienteering problem with time windows, Comput.Oper. Res. 36 (12) (2009) 3281–3290. [43] P. Vansteenwegen, W. Souffriau, G.V. Berghe, D.V. Oudheusden, The city trip planner: An expert system for tourists, Expert Syst. Appl. 38 (6) (2011)6540–6546 [44] P. Vansteenwegen, W. Souffriau, D.V. Oudheusden, The orienteering problem: A survey, Eur. J. Oper. Res. 209 (1) (2011) 1–10. [45] Y. Yang, W. Jin, X. Hao, Car rental logistics problem: A review of literature, in: Ser- vice Operations and Logistics, and Informatics, 2008. IEEE/SOLI 2008.IEEE Inter- national Conference on, 2, 2008, pp. 2815–2819. [46] S.-H. Yeung, H.-K. Ng, K.-F. Man, Multi-criteria design methodology of a dielec- tric resonator antenna with jumping genes evolutionary algorithm, Int.J. Electron. Commun. (AEU¨) 62 (2008) 266–276. [47] W. Yu, Z. Bao, X. Bao, Optimal deterministic algorithms for some variants of online quota traveling salesman problem, Eur. J. Oper. Res. 238 (3) (2014)735–740. 69 [48] J.R. Zaneveld, D.R. Nemergut, R. Knight„Are all horizontal gene transfers created equal? prospects for mechanism-based studies of HGT patterns, Microbiology 154 (2008) 1–15. 70