Áp dụng giải thuật di truyền cho một bài toán mới của giao thông vận - Vũ Đình Hòa

90 HNUE JOURNAL OF SCIENCE DOI: 10.18173/2354-1059.2018-0009 Natural Sciences 2018, Volume 63, Issue 3, pp. 90-98 This paper is available online at ÁP DỤNG GIẢI THUẬT DI TRUYỀN CHO MỘT BÀI TOÁN MỚI CỦA GIAO THÔNG VẬN TẢI Vũ Đình Hòa1 và Đỗ Tuấn Hạnh2 1 Khoa Công nghệ Thông tin, Trường Đại Học Sư Phạm Hà Nội 2Trường Đại Học Kinh Tế Kĩ Thuật Công Nghiệp, Trường Đại Học Bách Khoa Hà Nội Tóm tắt. Các bài toán giao thông và vận tải được quan tâm khá sớm trên thế giới từ vài thế kỉ trước [1, 2] như bài toán người du lịch và bài toán luồng. Hiện nay, các bài toán giao thông vận tải được nghiên cứu dưới nhiều cách tiếp cận khác nhau [3]. Trong bài báo này chúng tôi đặt ra một bài toán giao thông vận tải mới chưa được khảo sát từ trước đến nay. Bài toán nghiên cứu một mạng có n đỉnh và m cạnh với một đỉnh nguồn và một đỉnh đích cùng với m đội vận tải cho trước. Mục tiêu bài toán đặt ra là tìm một cách phân công cho mỗi đội vận tải một cung đường sao cho có thể vận tải một lượng hàng lớn nhất từ đỉnh nguồn s tới đỉnh đích t. Trong bài báo này, chúng tôi chứng minh bài toán phân công vận tải là một bài toán NPH, và đưa ra một cách tiếp cận và giải quyết bài toán này bằng giải thuật di truyền. Từ khóa: Bài toán luồng, bài toán phân công vận tải, giải thuật di truyền. 1. Mở đầu Những khái niệm cơ bản dưới đây có thể tham khảo từ [1, 2] hoặc từ các cuốn sách chuyên môn khác về đồ thị. Một mạng được hiểu là một đồ thị có hướng ( , )G V E gồm n đỉnh, m cung với một đỉnh nguồn s (nhiều khi được qui ước là chỉ có cung đi ra) và một đỉnh thu t (nhiều khi được qui ước là chỉ có cung đi vào). Mỗi cung ( , )e u v  E được gán với một số không âm ( ) ( , )c e c u v gọi là khả năng thông qua của cung đó. Đôi khi, để thuận tiện cho việc trình bày, ta gọi hàm :c E R đó là hàm thông luồng và qui ước rằng nếu không có cung ( , )u v thì ta coi như có cung này và khả năng thông qua ( ) ( , )c e c u v của nó được gán bằng 0. Nếu có mạng ( , )G V E , ta gọi luồng p trong mạng G là một phép gán cho mỗi cung ( , )e u v  E một số tự nhiên ( ) ( , )p e p u v (gọi là luồng trên cung e ), thoả mãn các điều kiện sau: - Luồng trên mỗi cung không vượt quá khả năng thông qua của nó: 0  ( , )p u v  ( , )c u v ,  , u v E  , - Với mọi đỉnh v không trùng với đỉnh nguồn s và đỉnh thu t , tổng luồng trên các cung đi vào v bằng tổng luồng trên các cung đi ra khỏi v : ( ) ( ) ( , ) ( , ) u v w v p u v p u v      . Trong đó: Ngày nhận bài: 12/4/2017. Ngày sửa bài: 12/3/2018. Ngày nhận đăng: 20/3/2018. Tác giả liên hệ: Vũ Đình Hòa. Địa chỉ e-mail: hoavd@hnue.edu.vn. Áp dụng giải thuật di truyền cho một bài toán mới của giao thông vận tải 91     | , { }K v u V u v E    ,     | , { }K v w V v w E    . * Bài toán luồng cực đại trên mạng Cho mạng ( , )G V E với đỉnh s , đỉnh thu t và thông luồng :c E N . Hãy tìm luồng *p trong mạng ( , )G V E sao cho *( ) ( ),p e e Ec  và giá trị * * ( ) ( ) ( , ) ( , ) v s v s p s v p v s      (được gọi là giá trị của luồng) lớn nhất có thể. Luồng như vậy gọi là luồng cực đại trong mạng và bài toán này gọi là bài toán tìm luồng cực đại trên mạng. Bài toán luồng cực đại trên mạng được quan tâm từ rất sớm do tầm quan trọng của nó. Đã có nhiều giải thuật được đề xuất để giải quyết bài toán này, mà một trong các giải thuật quan trọng quen biết nhất là giải thuật của Ford-Fulkerson [1, 2]. Thuật toán này được cải tiến trong một số năm sau đó để đạt được độ phức tạp thuật toán là 2( )O nm [4]. Trong đời sống thực tế thì khả năng thông qua của các luồng trên các cạnh được thể hiện là khả năng vận tải của đội vận tải phụ trách tuyến đường đó. Khi có một sự phân công các đội vận tải trên các cung đường thì chúng ta phải giải quyết bài toán luồng cực đại trên sơ đồ mạng tương ứng, trong đó khả năng thông qua của mỗi cung chính là khả năng vận tải của đội phụ trách cung đường đó. Trong bài toán này chúng ta xem xét vấn đề phân công mỗi đội vận tải phụ trách một cung đường để luồng cực đại tương ứng với phân công đó lớn hơn luồng cực đại ứng với các phân công khác. * Bài toán phân công vận tải Cho một mạng ( , )G V E gồm n đỉnh, m cung, đỉnh nguồn s , đỉnh thu t và một tập hợp C gồm m số tự nhiên 1 2, ,..., mc c c . Hãy tìm một song ánh :c E C sao cho luồng cực đại của mạng ( , )G V E , với khả năng thông qua của cạnh e là ( )c e , lớn nhất có thể. Bài toán này có ý nghĩa thực tế rất lớn, nhưng cho đến nay chưa được nghiên cứu [3]. Ví dụ: Ta xét một mạng như trong Hình 1. Hình 1 Mạng ( , )G V E có 3 đỉnh ,s t và u với hàm thông luồng 1,: { }2,3c E  . Xét hai phương án phân công khác nhau: (i) Nếu ta phân bố 1 2 3( ) 1, ( ) 2, ( ) 3,c e c e c e   thì luồng cực đại là * 4.p  (ii) Nếu ta phân bố 1 2 3( ) 3, ( ) 2, ( ) 1,c e c e c e   thì luồng cực đại chỉ đạt giá trị * 3.p  Vũ Đình Hòa và Đỗ Tuấn Hạnh 92 * Đánh giá độ khó của bài toán phân công vận tải "Bài toán luồng cực đại trên mạng" được nghiên cứu và có nhiều giải thuật giải quyết bài toán này. Có nhiều thuật toán giải quyết bài toán này, và các thuật toán này đều là giải thuật hiệu quả. Giải thuật Ford-Fulkerson cải tiến (chọn đường tăng luồng là đường ít cạnh nhất) có độ phức tạp đa thức [4]. Độ khó của bài toán phân công vận tải tối ưu chưa được nghiên cứu trên thế giới. Chúng ta sẽ chứng minh bài toán này là bài toán NPH [5]. Để chứng minh được điều đó, ta dẫn bài toán PAR, là một bài toán NPC [5], về bài toán phân công vận tải. Bài toán Partition (PAR) Instance: Cho trước số nguyên dương n và một tập hợp 1 2{ , ,..., }nA a a a N  . Question: Tồn tại hay không một phân hoạch 1 2A AA  sao cho 1 2i i i A i Aa a a a     . "Bài toán phân công vận tải" được phát biểu dưới dạng bài toán quyết định như sau. * Bài toán phân công vận tải Instance: mạng ( , )G V E gồm n đỉnh, m cung, đỉnh nguồn s , đỉnh thu t và một tập hợp C gồm m số tự nhiên 1 2, ,..., mc c c và một số tự nhiên B . Question: Tồn tại hay không song ánh :c E C sao cho luồng lớn nhất từ s đến t , với khả năng thông qua của cạnh e là ( )c e , không nhỏ hơn B . Định lí. Bài toán phân công vận tải là bài toán NPH . Chứng minh: Ta sử dụng bài toán PAR, là một bài toán NPC [5], để dẫn về bài toán PCVT. Ta xây dựng phép dẫn thời gian đa thức biến mỗi instance của bài toán PAR thành một instance của bài toán phân công vận tải như sau: Với mỗi số nguyên dương n và một tập hợp 1 2{ , ,..., }nA a a a N  , ta xây dựng một mạng ( , )G V E với 3 đỉnh ,s t và u và 2m n cung, bao gồm n cung kép ( , )s u , và n cung kép ( , )u t , như trong hình vẽ sau: Hình 2. Ta chọn 1 2{ ,..., }n nC A a a với 0ia  cho mọi 1i n  và 1 1 / 2 n n i iB a a           ở đó [ ]a kí hiệu số nguyên lớn nhất không vượt quá a . Với mỗi hàm thông luồng :c E C Đặt 1A là tập hợp các giá trị của A ứng với các cung đi từ s đến u và 2 1A A A  . Dễ dàng thấy luồng đi từ s đến t đạt giá trị 1 2 n ia B             ( a   ký hiệu số nguyên nhỏ nhất không nhỏ hơn a ) khi và chỉ khi có phân hoạch 1 2A AA  sao cho 1 2 . i iA i a A i a a a     Áp dụng giải thuật di truyền cho một bài toán mới của giao thông vận tải 93 Ngoài ra cũng dễ dàng thấy phép xây dựng một mạng ( , )G V E như vậy từ một instance của bài toán PAR thực hiện được trong thời gian đa thức. Do đó, phép dẫn của chúng ta là một phép dẫn thời gian đa thức từ bài toán PAR đến bài toán PCVT. Vậy PCVT là một bài toán NPH . 2. Nội dung nghiên cứu 2.1. Sử dụng giải thuật di truyền tìm phân công tối ưu 2.1.1. Lát cắt, đường tăng luồng, định lí Ford - Fulkerson Định nghĩa: Ta gọi lát cắt  , S F là một cách phân hoạch tập đỉnh V của mạng thành hai tập rời nhau S và F , trong đó S chứa đỉnh phát s và F chứa đỉnh thu t . Khả năng thông qua của lát cắt  , S F là tổng tất cả các khả năng thông qua của các cung  , u v có u S và v F . Lát cắt với khả năng thông qua nhỏ nhất gọi là lát cắt hẹp nhất. Định lí Ford-Fulkerson: Giá trị luồng cực đại trên mạng đúng bằng khả năng thông qua của lát cắt hẹp nhất. Ford- Fulkerson xây dựng được một thuật toán tìm luồng cực đại trên mạng: Giả sử p là một luồng trong mạng   , G V E . Ta xây dựng đồ thị có trọng số   , p pG V E như sau: Xét những cạnh   , e u v E  ,  , 0c u v  : - Nếu ( , ) ( , )p u v c u v thì ta thêm cung  , u v vào pE với trọng số ( , ) ( , )c u v p u v , cung đó gọi là cung thuận. Về ý nghĩa, trọng số cung này cho biết còn có thể tăng luồng p trên cung này một lượng không quá trọng số đó. - Xét tiếp nếu như ( , ) ( , )p u v c u v thì ta thêm cung  , v u vào pE với trọng số ( , ) ( , )p u v c u v , cung đó gọi là cung nghịch. Về ý nghĩa, trọng số cung này cho biết còn có thể giảm luồng p trên cung  , u v một lượng không quá trọng số đó. Đồ thị pG được gọi là đồ thị tăng luồng. Giả sử R là một đường đi cơ bản từ đỉnh phát s tới đỉnh thu t . Gọi d là giá trị nhỏ nhất của các trọng số của các cung trên đường đi R . Ta sẽ tăng giá trị của luồng p bằng cách đặt: - ( , ) : ( , )p u v p u v d  , nếu  , u v là cung trong đường R và là cung thuận, - ( , ) : ( , )p u v p u v d  , nếu  , u v là cung trong đường R và là cung nghịch, - Còn luồng trên những cung khác giữ nguyên. Có thể kiểm tra luồng p mới xây dựng vẫn là luồng trong mạng và giá trị của luồng p mới được tăng thêm d so với giá trị luồng p cũ. Ta gọi thao tác biến đổi luồng như vậy là tăng luồng dọc đường R , đường đi cơ bản R từ s tới t được gọi là đường tăng luồng. Đến đây ta có thể hình dung ra được thuật toán tìm luồng cực đại trên mạng: khởi tạo một luồng bất kỳ, sau đó cứ tăng luồng dọc theo đường tăng luồng, cho tới khi không tìm được đường tăng luồng nữa. Vũ Đình Hòa và Đỗ Tuấn Hạnh 94 Các bước của thuật toán tìm luồng cực đại trên mạng có thể mô tả như sau: Bước 1: Khởi tạo. Một luồng bất kì trên mạng, chẳng hạn như luồng 0 (luồng trên các cung đều bằng 0), sau đó: Bước 2: Lặp hai bước sau. - Tìm đường tăng luồng R đối với luồng hiện có  Tìm đường đi cơ bản từ s tới t trên đồ thị tăng luồng, nếu không tìm được đường tăng luồng thì bước lặp kết thúc. - Tăng luồng dọc theo đường R Bước 3: Thông báo giá trị luồng cực đại tìm được. Gán nhãn trong cài đặt thuật toán Ford - Fulkerson (L.R.Ford & D.R.Fulkerson - 1962) bằng cách sau: Mỗi đỉnh v được gán nhãn     , Trace v d v . Trong đó   Trace v  là đỉnh liền trước v trong đường đi từ s tới v ,  Trace v âm hay dương tuỳ theo  (| | ), Trace v v là cung nghịch hay cung thuận trên đồ thị tăng luồng,  d v là trọng số nhỏ nhất của các cung trên đường đi từ s tới v trên đồ thị tăng luồng. Bước lặp sẽ tìm đường đi từ s tới t trên đồ thị tăng luồng đồng thời tính luôn các nhãn     , Trace v d v . Sau đó tăng luồng dọc theo đường tăng luồng nếu tìm thấy. 2.1.2. Giải thuật di truyền Theo Định lí 1, Bài toán “Phân Công Vận Tải Tối ưu” là một bài toán NPH do đó ta không thể có lời giải tối ưu. Ta có thể sử dụng phương pháp vét cạn để có thể giải quyết bài toán trên tuy nhiên vì độ phức tập quá lơn không đáp ứng được, do đó chúng tôi đề xuất sử dụng giải thuật di truyền để giải quyết bài toán trên. Người được xem đặt nền móng đầu tiên cho giải thuật di truyền là John Holland [6], lần đầu nghiên cứu thuật giải này không có tên. Do nguồn gốc của phương pháp này từ gen di truyền nên nó có tên là giải thuật di truyền. GA (Genetic Algorithms) được đặc trưng bởi các chiến lược tìm kiếm dựa trên quần thể và các toán tử di truyền như là chọn lọc, đột biến và trao đổi chéo. Mã hoá dữ liệu mới cho bài toán phân công vận tải Bài toán có m đội vận tải đánh số từ 1 đến m và đồng thời đánh số các cung đường từ 1 đến m Khi đó mỗi một hoán vị từ 1 đến m là một cách phân công đội vận tải tương ứng với một cung đường. Sử dụng phương pháp mã hóa dữ liệu gen chuyển từ nhị phân 0 và 1 mã hóa gen dưới dạng thập phân [8, 9]. Ví dụ có 9 đội vận tải 9 cung đường là: (1,2); (1,3); (2,3); (2,4); (3,2); (3,5); (4,6); (5,4); (5,6) và có 6 địa điểm điểm xuất phát là 1 và kết thúc là 6. Có giá trị vận chuyển của 9 đội vận tại lầ lượt nhận các giá trị là 16; 16; 14; 4; 14; 12; 7; 4; 20 Với phương pháp mã hóa trên ta có gen phân công là:134569872. Toán tử đột biến Chúng tôi áp dụng phương pháp đột biến đảo ngược như sau: Pháp sinh ngẫu nhiên 2 vị trí H1 và H2 (1<=H1<H2<=độ dài của gen) trong cá thể cha mẹ các gen từ vị trí H1 đến H2 chúng tôi đảo ngược các gen đó lại các gen ở các vị trí khác vẫn giữ nguyên kế thừa từ gen cha mẹ.Tiến hành theo trình tự trên sẽ sinh được cá thể mới cá thể đó là đột biến mới của cá thể cha mẹ. Ví dụ với cách đột biến trong bài toán phân công vận tải: Nếu chúng ta có cá thể cha mẹ là P = 134569872; sinh ngẫu nhiên có H1= 2; H2 = 8. Khi đó đoạn gen từ vị trí 2 đến vị trí 8 là đoạn gen 3456987 đảo ngược lại là đoạn gen mới là 7896543 còn lại có vị trí các gen còn lại là vị trí 1 và vị trí 9 giữ nguyên. Gen đột biến sinh mới được sinh ra là P’ = 1|7896543|2 Áp dụng giải thuật di truyền cho một bài toán mới của giao thông vận tải 95 Toán tử lai ghép Toán tử lai ghép tạo trên 2 cá thể cha mẹ P1 và P2 được tiến hành theo các bước sau: Pháp sinh ngẫu nhiên 2 vị trí H1 và H2 (1<=H1<H2<=độ dài của gen), khi đó cá thể con sẽ giữ lại đoạn gen từ vị trí H1 đến H2 của cá thể cha mẹ P1. Các gen tiếp theo được lấy theo ưu tiên từ trái sang phải của cá thể cha mẹ P2 lần lượt được ghép vào vị trí chưa có và thỏa mãn điều kiện không có trong các gen từ H1 đến H2 của cha mẹ P1. Ví dụ: P1=143567982 ; P2=416523897 Sinh ngẫu nhiên H1=3; H2=6 Khi đó biểu diễn gen cha mẹ chuẩn bị lai ghép như sau: P1=14|3567|982 ; P2=416523897 Từ vị trí gen 3 đến đén vị trí gen 6 là giữ nguyên sẽ là đoạn gen 3567. Tiếp theo duyệt từ trái sang phải các gen của cá thể cha mẹ P2. Cá thể được lai ghép trong ví dụ trên như sau ghen vị trí 1 nhận giá trị 4 vì 4 không nằm trong đoạn gen 356 vị trí thứ 2 nhận giá trị 1 tiếp theo đoạn gen 356 ta có cá thể mới 413567. Tiếp theo gen thứ 7 sẽ nhận giá trị 2 gen 8 nhận giá trị 8 và gen 9 nhận giá trị 9 vì theo thứ tự ưu tiên gen còn lại chưa lấy tính theo ưu tiên từ trái sang phải của cá thế cha mẹ P2. Khi đó ta sẽ có được cá thể lai ghép giữa 2 cá thể cha mẹ P1 và P2 được lai ghép ra cá thể con P’=41|3567|289 Toán tử chọn lọc: Toán tử chọn lọc chọn n_gen cá thể cho thế hệ t + 1 được tiến hành như sau: 1- Xây dựng tập lời giải trung gian P'(t) bằng cách áp dụng phép đột biến và phép lai ghép: + Áp dụng toán tử đột biến đối với P(t) được P1(t) + Áp dụng toán tử trao đổi chéo đối với P(t) được P2(t) +        1 2' P t P t P t P t   2- Chọn 1 cá thể có độ thích nghi tốt nhất kể từ thế hệ đầu đến thế hệ t gọi là Pmin bằng cách sau: Chọn cá thể đó là cá thể có độ thích nghi nhất trong tập P'(t) gọi là P'min nếu t=1 thì Pmin= P'min. Nếu t>1 ta so sánh P'min có độ thích nghi tốt hơn Pmin ta sẽ thay thế Pmin= P'min 3- Xây dựng tập PP'(t) P'(t) sao cho PP'(t) toàn các cá thể khác nhau. Nếu số cá thể P'(t) lớn hơn n_gen cá thể thì lấy ngẫu nhiên theo nguyên tác bánh xe số n_gen-1 cá thể khác nhau, ngược lại n_gen-1 cá thể lấy bằng cách lấy hết toàn bộ cá thể trong P'(t) còn thiếu bao nhiêu ta lấy lấy ngẫu nhiên theo nguyên tác bánh xe số cá thể còn thiếu trong P'(t) . Sau đó P(t) là hợp giữa PP'(t) và Pmin Thuật toán di truyền cho bài toán Phân công vận tải: Void GA_Phancongvantai () { t  0 ; { t là số thế hệ tiến hóa} Khởi tạo  P t Áp dụng luồng cực đại tính cách phân công cho các thế hệ t quần thể P while ( t < n_thehe ) do { Xây dựng tập lời giải )'(P t bằng cách áp dụng phép đột biến và phép lai ghép: + Áp dụng toán tử đột biến đối với  P t được  1P t , sau đó áp dụng luồng cực đại tính cách phân công cho các thế hệ t quần thể  1P t Vũ Đình Hòa và Đỗ Tuấn Hạnh 96 + Áp dụng toán tử trao đổi chéo đối với P(t) được P2(t), sau đó Áp dụng luồng cực đại tính cách phân công cho các thế hệ t quần thể P2(t) +        1 2' P t P t P t P t   . Chọn lọc  P t từ )'(P t 1t t  ; } } Tính đúng đắn của thuật toán được đề nghị: Tính đúng đắn của thuật toán được khẳng định thông qua các đặc trưng sau đây: 1-Khi khởi tạo n_gen cá thể của quần thể ban đầu chúng tôi sử dụng thuật toán di truyền để sinh ra các lịch biểu, cho nên mỗi cá thể con được sinh ra đều là một lịch biểu tích cực theo phương pháp vẫn sử dụng trong [7-9]. 2-Trong phép đột biến, cá thể tham gia đột biến được sửa đổi bằng lấy một số gen cá thể cha thông qua ma trận H áp dụng thuật toán di truyền do đó nó vẫn là một lịch biểu tích cực . 3-Phép trao đổi chéo từ 2 cá thể cha mẹ P1 và P2 lấy các gen cá thể cha hoạc mẹ thông qua ma trận H áp dụng thuật toán di truyền để sinh ra các lịch biểu con F1, cho nên mỗi cá thể con được sinh ra đều là một lịch biểu tích cực. 4-Thuật toán sẽ dừng khi chạy qua đủ các thế hệ. 5-Vì thuật toán luôn duy trì lời giải tốt nhất trong quần thể, trước hoặc sau khi chọn lọc, vì vậy thuật toán được chứng tỏ hội tụ nhờ thuộc tính không giảm của các thế hệ tiếp theo. Tuy nhiên vấn đề chứng minh nó hội tụ tới giá trị tối ưu toàn cục không đơn giản chút nào, có thể sử dụng phương pháp dùng xích Marvkow tương tự như phương pháp trong [7]. 2.2. Kết quả thử nghiệm Dựa vào phương pháp đề xuất trong bài báo này, chúng tôi đã cài đặt một chương trình bằng ngôn ngữ C ++ và chạy thử nghiệm trên máy PC với bộ vi xử lí Core i7 Dual có tốc độ 3.4 GHz. Do chưa có các test mẫu chúng tôi lấy một đồ thị trên mạng và thêm vào đó sẽ là các đội vận tải có giá chị vận chuyển số ngẫu nhiên sinh ra .Với một số test lớn chưa xác định được kết quả tối ưu một số test nhỏ dùng phương pháp vét cạn và một số test đặc biệt dùng một số phương pháp đặc trưng để có kết quả tối ưu. Theo kết quả Bảng 1 với các test nhỏ dùng phương pháp vét cạn so sánh với dùng phương pháp di truyền chúng tôi đề xuất cho kết quả trùng nhau. Chúng tôi tiến hành chạy 1000 lần ngẫu nhiên với các test trên. Bảng 1. Kết quả chạy thử nghiệm với 4 địa điểm và 5 đội vận tải Bài toán Cỡ lời giải Số thế hệ Xác suất trao đổi chéo (pc) Xác suất đột biến (pm ) Kết quả chạy Tối ưu thực sự VT 1(4 5 ) 20 30 0.8 0.01 22 22 VT1 (4  5) 30 50 0.8 0.01 22 22 VT1 (4  5) Phương pháp vét cạn 22 22 Áp dụng giải thuật di truyền cho một bài toán mới của giao thông vận tải 97 Bảng 2. Kết quả chạy thử nghiệm với 6 địa điểm và 9 đội vận tải Bài toán Cỡ lời giải Số thế hệ Xác suất trao đổi chéo (pc) Xác suất đột biến (pm ) Kết quả chạy Tối ưu thực sự VT2 (6  9) 30 100 0,8 0,01 30 30 VT2 (6  9) 100 200 0,8 0,05 30 30 VT2(6  9) Phương pháp đặc biệt 30 30 Kết quả chạy thực nghiệm thông qua Bảng 2 không dùng được phương pháp vét cạn chúng tôi sử dụng test đặc biệt đưa ra kết quả trùng với phương pháp di truyền chúng tôi đề xuất. Với giải thuật di truyền chúng tôi cũng tiến hành chạy 1000 lần để thống kê. Bảng 3. Kết quả chạy thử nghiệm với 50 địa điểm và 90 đội vận tải Bài toán Cỡ lời giải Số thế hệ Xác suất trao đổi chéo (pc) Xác suất đột biến (pm ) Kết quả chạy Tối ưu thực sự VT3 (50  90) 100 500 0,8 0,01 1237 Chưa xác định VT3 (50  90) 150 700 0,8 0,05 1452 Chưa xác định VT3 (50  90) 250 1000 0,8 0,05 2310 Chưa xác định VT3 (50  90) 500 2000 0,8 0,05 2310 Chưa xác định Kết quả thực nghiệm thông qua Bảng 3 chúng tôi thấy kết quả hội tụ ra kết quả chạy nhưng chưa chứng minh đó là kết quả tối ưu. Hiện tại chạy với độ lớn 50 địa điểm và 90 đội vận tải thấy hội tụ ở kết quả 2310. Để có kết quả hội tụ trên chúng tôi tiến hành chạy 1500 lần để tổng hợp đưa ra được kết quả tốt nhất hiện tại. Thông qua so sánh kết quả thử nghiệm có thể cho thấy phương pháp mà chúng tôi đề nghị có các điểm mạnh sau đây: Việc sử dụng cách tổ chức dữ liệu phương pháp mã hóa dạng thập phân giúp cho giải thuật chạy nhanh hơn. Khi sử dụng phương pháp di truyền có được các kết quả hội tụ tốt hơn so với phương pháp vét cạn và phương pháp tham lam. Phép chọn lọc lấy nhiều nhất số cá thể khác nhau trong quần thể nhưng vẫn lấy ngẫu nhiên vẫn đảm bảo tính ngẫu nhiên của giải thuật GA thông thường. Mặt khác vẫn hỗ trợ đảm bảo giúp cho bài toán nhanh chóng tìm được kết quả tối ưu cục bộ thế hệ sau có kết quả tối ưu ít nhất thich nghi hơn thế hệ trước. Bài toán Phân công vận tải đã được chứng minh là bài toán NPH. Do đó sử dụng giải thuật di truyền là một trong phương án chấp nhận được để có thể đưa ra đáp án kịp thời đáp ứng nhu cầu trong các ứng dụng thời gian thực. Tuy nhiên giải thuật di truyền có nhược điểm là không phải lúc nào cũng cho ta kết quả tốt nhất có thể. Vũ Đình Hòa và Đỗ Tuấn Hạnh 98 3. Kết luận Trong bài báo này chúng tôi đặt ra một bài toán giao thông vận tải mới chưa được khảo sát từ trước đến nay. Chúng tôi chứng minh trong bài báo này rằng bài toán phân công vận tải này là một bài toán NPH. Để giải quyết bài toán NPH này, chúng tôi đã xây dựng một mô hình giải thuật di truyền, lập trình tiến hóa và chạy thử nghiệm. Với những số liệu mà nghiệm tối ưu có thể kiểm chứng được, nghiệm tìm được qua giải thuật di truyền hoàn toàn chính xác là nghiệm tối ưu thật sự. Với những dữ kiện lớn hơn, nghiệm tối ưu không xác định trước để kiểm chứng được, thì kết quả chạy của chương trình cũng cho kết quả khá tốt và trong thời gian chấp nhận được. TÀI LIỆU THAM KHẢO [1] Dieter R., 2000. Graph Theory, Second Edition, Springer. [2] Joan M. Aldous and Robin J. Wilson, 2000. Graphs and Applications. Springer Verlag. [3] Paolo Toth and Daniele Vigo, 2014. Vehicle Routing Problems, Methods, and Applications. SIAM Society for Industrial and Applied Mathematics Philadelphia ( /journals/ojsa.php). [4] https://vi.wikipedia.org/wiki/Thu%E1%BA%ADt_to%C3%A1n_Edmonds%E2%80%93Karp [5] Garey M.R., Johnson D.S., 1978, Computer and intractability, Springer Verlag, 1978. [6] Holland J. H., 1975. Adaptation in Natural and Artificial Systems. University of Michigan Press, 1975. [7] Lục Trí Tuyên, Nguyễn Hữu Mùi & Vũ Đình Hòa, 2013. Phân tích tính hội tụ của thuật toán di truyền lai mới. Tạp chí Tin học và Điều khiển học, T. 29, S. 2, p. 165-172. [8] Nguyễn Hữu Mùi, Vũ Đình Hoà, 2011. Một thuật toán di truyền lai mới cho bài toán lập lịch công việc. Kỉ yếu hội nghị khoa học công nghệ quốc gia lần thứ V, tr. 239-249. [9] Đỗ Tuấn Hạnh, Vũ Đình Hòa, Nguyễn Hữu Mùi, 2014. Dual hybrid algorithm for job shop scheduling problem. International Journal of Computer Science and Business Informatics, pp 14-24 2014. ABSTRACT Using genetic algorithm for a new transport problem Vu Dinh Hoa 1 and Do Tuan Hanh 2 1 Faculty of Information Technology, Hanoi National University of Education 2 University of Economic and Technical Industries, Hanoi University of Science and Technology In this paper we propose a new transport problem that has not been investigated yet. Given a network of n vertices and m edges with a source vertex and a vertex along with a given transport fleet. The goal of the problem is to find a way of assigning each transport team a supply curve so that it can transport the greatest amount of goods from the source s to the top of the destination t. This paper demonstrates that the transport assignment problem is an NPH problem, and offers an approach and solution by genetic algorithms. Keywords: Maxflow, assinging transport teams problem, genetic algorithms.