ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG - VŨ THỊ KHÁNH TRÌNH GIẢI THUẬT DI TRUYỀN VÀ ỨNG DỤNG ĐỐI VỚI BÀI TỐN VẬN TẢI Chun ngành: Khoa học máy tính Thái Nguyên - 2014 i LỜI CAM ĐOAN Sau trình học tập Trường Đại học Công nghệ thông tin Truyền thông, với kiến thức lý thuyết thực hành tích lũy được, với việc vận dụng kiến thức vào thực tế, em tự nghiên cứu tài liệu, cơng trình nghiên cứu, đồng thời có phân tích, tổng hợp, đúc kết phát triển để hoàn thành luận văn thạc sĩ Em xin cam đoan luận văn cơng trình thân em tự tìm hiểu, nghiên cứu hoàn thành hướng dẫn thầy giáo, TS Vũ Vinh Quang Thái Nguyên, tháng năm 2014 Học viên Vũ Thị Khánh Trình ii LỜI CẢM ƠN Trong thời gian hai năm chương trình đào tạo thạc sĩ, gần nửa thời gian dành cho mơn học, thời gian cịn lại dành cho việc lựa chọn luận văn, giáo viên hướng dẫn, tập trung vào nghiên cứu, viết, chỉnh sửa hoàn thiện luận văn Với quỹ thời gian với vị trí cơng việc phải đảm nhận, khơng riêng thân em mà hầu hết sinh viên cao học muốn hồn thành tốt luận văn trước hết phải có xếp thời gian hợp lý, có tập trung học tập nghiên cứu với tinh thần nghiêm túc, nỗ lực hết mình; tiếp đến có ủng hộ tinh thần, giúp đỡ chuyên môn - điều kiện thiếu định đến việc thành công luận văn Để hoàn thành luận văn trước tiên em xin gửi lời cảm ơn sâu sắc đến thầy giáo hướng dẫn TS Vũ Vinh Quang, người định hướng nội dung, hướng phát triển luận văn có nhiều ý kiến đóng góp quan trọng vấn đề chuyên môn luận văn, giúp em tháo gỡ kịp thời vướng mắc trình làm luận văn Em xin chân thành cảm ơn thầy, cô giáo Trường Đại học Công nghệ thông tin Truyền thông bạn bè lớp có ý kiến bổ ích để luận văn hồn thiện Xin cảm ơn gia đình, người thân, đồng nghiệp quan tâm, ủng hộ tinh thần suốt thời gian học tập hoàn thành luận văn Em xin hứa cố gắng tự nghiên cứu, nâng cao lực chun mơn để sau hồn thành luận văn có hướng tập trung nghiên cứu sâu hơn, tiếp tục hoàn thiện luận văn để có ứng dụng thiết thực thực tế Thái Nguyên, tháng năm 2014 Học viên Vũ Thị Khánh Trình iii MỤC LỤC Lời cam đoan i Lời cám ơn ii Danh mục chữ viết tắt vi Danh mục bảng vii Danh mục hình viii LỜI MỞ ĐẦU Chương Bài toán vận tải 1.1 Bài toán quy hoạch tuyến tính 1.1.1 Mơ hình số tốn thực tế 1.1.2 Bài tốn quy hoạch tuyến tính 1.2 Bài toán vận tải 11 1.3 Thuật toán phân phối giải toán vận tải 13 1.3.1 Định nghĩa 13 1.3.2 Cơ sở lý luận thuật toán 14 1.3.3 Thuật toán phân phối 16 1.3.4 Vấn đề chọn phương án ban đầu 17 1.4 Các dạng khác toán vận tải 18 1.4.1 Bài tốn vận tải khơng cân thu phát 18 1.4.2 Bài toán vận tải dạng cực đại 20 Chương Giải thuật di truyền ứng dụng toán vận tải 28 2.1 Giới thiệu Giải thuật di truyền 28 iv 2.2 Các khái niệm 29 2.2.1 Cá thể, nhiễm sắc thể 29 2.2.2 Quần thể 2.2.3 Chọn lọc (Selection) 29 30 2.2.4 Lai ghép (Crossover) 30 2.2.5 Đột biến (Mutation) 30 2.3 Mơ hình GA 30 2.4 Các tham số GA 32 2.4.1 Kích thước quần thể 32 2.4.2 Xác suất lai ghép 32 2.4.3 Xác suất đột biến 32 2.5 Cơ chế thực GA 33 2.5.1 Mã hóa 33 2.5.2 Khởi tạo quần thể ban đầu 34 2.5.3 Xác định hàm thích nghi 34 2.5.4 Cơ chế lựa chọn 34 2.6 Thuật toán di truyền kinh điển 36 2.6.1 Mã hóa 36 2.6.2 Toán tử chọn lọc 36 2.6.3 Toán tử lai ghép 37 2.6.4 Toán tử đột biến 39 2.7 Thuật tốn di truyền mã hóa số thực (RCGA) 40 2.7.1 Giới thiệu 40 2.7.2 Các toán tử RCGA 41 2.8 Thuật toán di truyền với toán vận tải cân 46 2.8.1 Biểu diễn lời giải toán vận tải véc tơ 46 2.8.2 Biểu diễn lời giải toán vận tải ma trận 51 Chương Một số kết thực nghiệm 56 3.1 Mô tả thuật toán di truyền 56 3.1.1 Toán tử khởi tạo 56 v 3.1.2 Toán tử lai ghép 58 3.1.3 Toán tử đột biến 58 3.1.4 Toán tử lựa chọn 59 3.2 Một số kết cài đặt 59 Phần kết luận 63 Tài liệu tham khảo 64 Phần phụ lục 65 vi DANH MỤC CÁC CHỮ VIẾT TẮT GA – Genetic Algorithm: EC - Evolutionary computation: EP - Evolutionary Programming: ES - Evolutionary Strategies: GP - Genetic Programming: CS - Classifier Systems: NST: Selection: Crossover: Mutation: Reproduction: pop_size: RCGA: giải thuật di truyền tính tốn tiến hóa quy hoạch tiến hóa chiến lược tiến hóa lập trình di truyền hệ thống phân loại nhiễm sắc thể chọn lọc lai ghép đột biến sinh sản kích cỡ quần thể thuật tốn di truyền mã hóa số thực Arithmetic Crossover: lai số học BLX-α - Blend Crossover: lai ghép BLX-α UNDX - Unimodal Normal Distributed Crossover: lai ghép UNDX CMX - Center of Mass Crossover: lai ghép CMX MFX - Multi-parent Feature-wise Crossover: lai ghép - MFX SX - Seed Crossover: lai ghép SX vii DANH MỤC CÁC BẢNG Bảng Bảng Bảng Bảng Bảng Bảng 1.1: 1.2: 1.3: 1.4: 3.1: 3.2: Hợp đồng chở hàng Cự ly vận chuyển Khả thu - phát Tổng số × km xe rỗng Kết sau 10 lần chạy ngẫu nhiên Kết sau 10 lần chạy ngẫu nhiên viii DANH MỤC CÁC HÌNH Hình 2.1: Sơ đồ mơ tả GA Hình 2.2: Lai ghép CMX Hình 2.3: Phân bố xci j Hình 2.4: Tốn tử lai ghép SX Hình 3.1: Đồ thị nghiệm lần chạy thứ 10 Hình 3.2: Đồ thị nghiệm lần chạy thứ 10 LỜI MỞ ĐẦU Trong thực tế, việc tìm kiếm phương pháp giải lớp toán tối ưu lĩnh vực nhà khoa học giới đặc biệt quan tâm Đã có nhiều cơng trình nghiên cứu lĩnh vực này, chủ yếu phát triển lý thuyết tối ưu hóa áp dụng lý thuyết quy hoạch tốn học mơ hình tốn cơng nghệ thơng tin để tìm kiếm thuật toán giải lớp toán NPC Trong thời gian gần hướng nghiên cứu quan trọng phát triển lĩnh vực tính tốn tiến hóa, nghiên cứu thuật tốn di truyền (Genetic Algorithm - GA) Xuất phát từ thuyết tiến hóa mn lồi Darwin, nhà tốn học John Holland (1975) Goldberg (1989) đề xuất phát triển GA Đây kỹ thuật chung tìm cách giải tốn việc mơ tiến hóa người hay sinh vật nói chung dựa điều kiện qui định sẵn toán GA thuật toán đưa lời giải tương đối tối ưu Tư tưởng thuật tốn tìm kiếm lời giải tối ưu dựa chế lai ghép, chọn lọc, sử dụng nguyên lý tính di truyền, thích nghi sống cá thể thích nghi tự nhiên từ tiếp cận đến lời giải tối ưu toán xét Đối với lý thuyết quy hoạch tuyến tính nói chung tốn vận tải mơ hình có ứng dụng quan trọng thực tế, toán kinh điển nghiên cứu Đã có nhiều thuật tốn đề xuất lý thuyết tối ưu để giải toán như: Các thuật toán vị (thuật toán phân phối, thuật toán quy khơng chọn), tốn quy hoạch ngun Với lý trên, em chọn đề tài "Giải thuật di truyền ứng dụng toán vận tải" làm luận văn tốt nghiệp Nội dung luận văn gồm chương: Chương - Bài toán vận tải: trình bày kiến thức toán vận tải - dạng đặc biệt tốn quy hoạch tuyến tính thuật tốn phân phối để giải toán vận tải 58 xm,2 = b2 − x1,2 − x2,2 − − xm−1,2 xm,n = bn − x1,n − x2,n − − xm−1,n−1 m xij = bj , j = 1, , n thỏa mãn Khi điều kiện i=1 3.1.2 Tốn tử lai ghép Đối với toán vận tải, thực lai ghép, cần đảm bảo điều kiện sinh từ cha mẹ qua phép lai ghép phải đảm bảo điều kiện ràng buộc a) b) đưa Một số thuật toán lai ghép nghiên cứu chương lai ghép số học hay lai ghép dạng DIV − REM thỏa mãn điều kiện Do việc thực việc lai ghép dạng DIV − REM khó cài đặt máy tính Do đó, ta chọn phương án lai ghép dạng số học Các bước tiến hành sau: Bước 1: Chọn xác suất lai ghép = 50% tức 100, chương trình chọn 50 cặp cha mẹ ngẫu nhiên để lai ghép Bước 2: Chọn ngẫu nhiên cha mẹ: + Xác định vị trí cá thể cha giá trị ngẫu nhiên khoảng từ (1, 100) Kí hiệu vị trí cha vị trí a + Xác định vị trí cá thể mẹ giá trị ngẫu nhiên khoảng từ (1, 100) Kí hiệu vị trí mẹ vị trí b (Để đảm bảo cha mẹ khơng trùng chọn a ∈ (1, 50), b ∈ (51, 100) nhiên điều khơng ảnh hưởng đến thuật tốn) Bước 3: Tiến hành lai ghép số học: + Chọn số ngẫu nhiên a1 ∈ (0, 1) + Tiến hành lai ghép: CON = a1 ∗ BO + (1 − a1 ) ∗ M E CON = (1 − a1 ) ∗ BO + a1 ∗ M E Các bước thực lặp lại với 50 cặp bố mẹ 3.1.3 Toán tử đột biến Để đảm bảo cho việc đột biến thành công tức sau đột biến phải đảm bảo điều kiện a) b) Trong trường hợp này, ta chọn 59 phương án thuật toán phân phối lựa chọn tức phương án bất kỳ, ta thực chọn vịng sau đột biến tiến hành theo nguyên tắc sau: + Chọn vòng x1,1 → x1,n → xm,n → xm,1 → x1,1 (Ta chọn loại vịng khác, điều khơng ảnh hưởng đến thuật toán) + Xác định α = min(x1,1 , xm,n )tức giá trị nhỏ tập vịng lẻ + Đột biến: - Các tập vòng lẻ (x1,1 , xm,n ) thêm lượng α - Các tập vịng chẵn (x1,n , xm,1 ) bớt lượng α Trong trình đột biến, ta chọn xác suất đột biến 5% 3.1.4 Toán tử lựa chọn Trong trình lựa chọn, ta ln lấy hàm chi phí hàm đánh giá tức ta chọn phương án cho hàm chi phí nhỏ Q trình lựa chọn thực theo phương án sau: Phương án 1: Từ cặp cha, mẹ hai sinh tương ứng, ta chọn cá thể có hàm chi phí nhỏ đưa vào quần thể để tham gia trình lai tạo tiếp sau Phương án 2: Xuất phát từ 100 cá thể ban đầu, sau thực lai ghép với xác suất 50% ta thu 200 cá thể Từ 200 cá thể này, ta tiến hành chọn 100 cá thể có giá trị hàm chi phí nhỏ đưa vào quần thể để tham gia trình lai tạo tiếp sau Nhận xét 3.1 Trong phương án việc lựa chọn đơn giản, phép so sánh ít, hiệu không cao Ở phương án 2, phép so sánh nhiều hiệu cao Trong trình thực cài đặt phương án để so sánh hiệu 3.2 Một số kết cài đặt Trong chương trình cài đặt Matlab, kích thước cá thể mơ tả ma trận x = (xi,j )3×4 , số cá thể khởi tạo ban đầu theo thuật toán N = 100, số lần lặp lần chạy 1000 Số liệu cụ thể thực hai phương án cài đặt sau: Test 1: (thuật toán áp dụng cho phương án chọn lọc 1) Kết nhận từ chương trình ga1.m 60 + Số liệu kho phát kho thu: a1 = 170, a2 = 200, a3 = 180 b1 = 130, b2 = 160, b3 = 120, b4 = 140 + Ma trận chi phí: c1,1 = 20, c1,2 = 18, c1,3 = 22, c1,4 = 25 c2,1 = 15, c2,2 = 25, c2,3 = 30, c2,4 = 15 c3,1 = 45, c3,2 = 30, c3,3 = 40, c3,4 = 35 STT Phương án Chi phí (27, 80, 24, 39; 97, 9, 10, 86; 6, 71, 86, 17) 13158 (12, 62, 70, 26; 118, 1, 31, 50; 0, 97, 19, 64) 12931 (49, 8, 109, 4; 64, 48, 5, 83; 17, 104, 6, 53) 13157 (74, 29, 66, 1; 42, 42, 13, 103; 14, 89, 41, 36) 13294 (118, 38, 11, 3; 10, 0, 59, 131; 2, 122, 50, 6) 13206 (11, 3, 119, 37; 96, 11, 0, 93; 23, 146, 1, 10) 12732 (73, 14, 81, 2; 31, 33, 4, 132; 26, 113, 35, 6) 13104 (5, 50, 98, 17; 122, 33, 10, 35; 3, 77, 12, 88) 13066 (126, 4, 36, 4; 0, 31, 46, 123; 4, 125, 38, 13) 13389 10 (48, 8, 104, 10; 76, 53, 9, 62; 6, 99, 7, 68) 13209 Bảng 3.1: Kết sau 10 lần chạy ngẫu nhiên Hình 3.1: Đồ thị nghiệm lần chạy thứ 10 Test 2: (thuật toán áp dụng cho phương án chọn lọc 2) 61 Kết nhận từ chương trình ga2.m + Số liệu kho phát kho thu: a1 = 170, a2 = 200, a3 = 180 b1 = 130, b2 = 160, b3 = 120, b4 = 140 + Ma trận chi phí: c1,1 = 20, c1,2 = 18, c1,3 = 22, c1,4 = 25 c2,1 = 15, c2,2 = 25, c2,3 = 30, c2,4 = 15 c3,1 = 45, c3,2 = 30, c3,3 = 40, c3,4 = 35 STT 10 Phương án Chi phí (14, 30, 102, 24; 93, 22, 5, 80; 23, 108, 13, 36) 13014 (95, 10, 49, 16; 35, 40, 18, 107; 0, 110, 53, 17) 13243 (19, 25, 100, 26; 110, 9, 4, 77; 1, 126, 16, 37 ) 12590 (13, 19, 106, 32; 93, 30, 1, 76; 24, 111, 13, 32) 13099 (55, 103, 6, 6; 60, 5, 17, 118; 15, 52, 7, 16) 13216 (1, 50, 85, 34; 115, 2, 28, 55; 14, 108, 7, 51) 13015 (31, 25, 110, 4; 87, 17, 5, 91; 12, 118, 5, 45) 12690 (13, 29, 113, 15; 85, 0, 2, 113; 32, 131, 5, 12) 12663 (51, 105, 13, 1; 74, 6, 1, 119; 5, 49, 106, 20) 12931 (54, 6, 106, 4; 59, 18, 11, 112; 17, 136, 3, 24) 12770 Bảng 3.2: Kết sau 10 lần chạy ngẫu nhiên Hình 3.2: Đồ thị nghiệm lần chạy thứ 10 62 Nhận xét 3.2 Từ kết thực hai phương án, ta có số nhận xét sau: + Thuật toán lai ghép theo phương án chạy tốc độ nhanh khơng phải thực thủ tục xếp, nhiên kết không tốt phép chọn lọc lần chưa chọn cá thể tốt + Thuật toán lai ghép theo phương án chạy tốc độ chậm phải thực thủ tục xếp qua lần chọn lọc Tuy nhiên kết tốt phép chọn lọc lần ln chọn cá thể tốt để tham gia vào lần lai ghép hệ sau + Do thuật toán chọn lọc ngẫu nhiên nên kết lần chạy khác Để thu kết tốt ta cần thực chạy nhiều lần với liệu + Với liệu kho phát, kho thu ma trận chi phí, thuật toán phân phối giải toán vận tải cho kết tối ưu (F (x) = 12140) tốc độ chạy nhanh Tuy nhiên phương pháp nhiều người sử dụng, bên cạnh với khơng gian tìm kiếm lớn phương pháp chạy tốc độ chậm Việc dùng giải thuật di truyền muốn đưa thêm cách giải cho toán vận tải 63 PHẦN KẾT LUẬN Luận văn nghiên cứu thuật toán di truyền GA, thuật toán phân phối toán vận tải, hướng nghiên cứu phát triển lĩnh vực tính toán mềm Các kết đạt luận văn gồm: Nghiên cứu mơ hình tốn quy hoạch tuyến tính tổng qt Nghiên cứu mơ hình tốn học tốn vận tải, phương pháp giải toán vận tải thuật toán phân phối Nghiên cứu thuật toán di truyền tổng quát, phương pháp mã hóa truyền thống GA, toán tử lai ghép đột biến, thuật toán di truyền mã hóa số thực Trình bày lý thuyết thuật toán GA giải toán vận tải cân bằng, đề xuất thuật toán khởi tạo quần thể, lai ghép đột biến chi tiết toán vận tải cân Xây dựng chương trình thực nghiệm mơ tả thuật toán GA giải toán vận tải sở thuật tốn đề xuất mơi trường Matlab version 7.0 Hướng nghiên cứu luận văn phát triển thuật toán GA toán vận tải không cân thu phát số tốn quy hoạch ngun có tính ứng dụng cao thực tế 64 TÀI LIỆU THAM KHẢO Tài liệu tiếng Việt [1] Nguyễn Đức Nghĩa, Tối ưu hóa (Quy hoạch tuyến tính rời rạc), Nhà xuất Giáo dục, Hà Nội, 1999 [2] Bùi Thế Tâm, Trần Vũ Thiệu, Các phương pháp tối ưu hóa, NXB Giao thơng vận tải, Hà Nội, 1998 [3] Bùi Minh Trí, Quy hoạch toán học, NXB Khoa học kỹ thuật, Hà Nội, 2001 [4] Nguyễn Anh Tuấn, Quy hoạch gần lồi - gần lõm ứng dụng vào quy hoạch tuyến tính, Nhà xuất Khoa học Kỹ thuật, Hà Nội, 2011 Tài liệu tiếng Anh [5] David, A.Coley (1995), An Instroduction to Genetic Algorithm [6] Eiben, E et al (1994), Genetic algorithms with multi-parent recombination PPSN III: Proceedings of the International Comference on Evolutionary Computation 78-87 [7] Charbonneau, Paul (1995), Genetic algorithms in astronomy and astrophysics, The Astrophysical Jornal Supplement Series, vol 101, pp 309-334 [8] Adam Marcryk (2004), Genetic Algorithms and Evolutionary Computation [9] Randy L Haupt and Douglas (1998), Genetic Algorithms in Electromagnetics 65 PHẦN PHỤ LỤC Phụ lục 1: Chương trình giải tốn vận tải theo phương án chọn lọc thứ function ga1=ga1(popsize); clc; count=0; s1=170;%So luong cac luong hang phat s2=200; s3=180; d1=130;%So luong cac luong hang thu d2=160; d3=120; d4=140; c=cell(3,4,1);% Ma tran chi phi c{1,1,1}=20; c{1,2,1}=18; c{1,3,1}=22; c{1,4,1}=25; c{2,1,1}=15; c{2,2,1}=25; c{2,3,1}=30; c{2,4,1}=15; c{3,1,1}=45; c{3,2,1}=30; c{3,3,1}=40; c{3,4,1}=35; % Khoi tao Quan the ban dau sd=cell(3,4,popsize); 66 x=cell(3,4,popsize); dem=0; for h=1:popsize % Dong sd{1,1,h}=randint(1,1,[0,min(s1,d1)]); sd{1,2,h}=randint(1,1,[0,min(s1-sd{1,1,h},d2)]); sd{1,3,h}=randint(1,1,[0,min(s1-sd{1,1,h}-sd{1,2,h},d3)]); sd{1,4,h}=s1-(sd{1,1,h}+sd{1,2,h}+sd{1,3,h}); % Dong sd{2,1,h}=randint(1,1,[0,min(s2,d1-sd{1,1,h})]); sd{2,2,h}=randint(1,1,[0,min(s2-sd{2,1,h},d2-sd{1,2,h})]); sd{2,3,h}=randint(1,1,[0,min(s2-sd{2,1,h}-sd{2,2,h},d3-sd{1,3,h})]); sd{2,4,h}=s2-(sd{2,1,h}+sd{2,2,h}+sd{2,3,h}); % Dong so sd{3,1,h}=d1-sd{1,1,h}-sd{2,1,h}; sd{3,2,h}=d2-sd{1,2,h}-sd{2,2,h}; sd{3,3,h}=d3-sd{1,3,h}-sd{2,3,h}; sd{3,4,h}=d4-sd{1,4,h}-sd{2,4,h}; if sd{3,4,h}>=0; % Neu ca the hop le thi bo sung vao quan the dem=dem+1; x(:,:,dem)=sd(:,:,h); end; end; popsize=dem; % Kich thuoc quan the thuc te sau khoi tao for h=1:popsize sd(:,:,h)=x(:,:,h); end; min_ga=10^7 while countFitness(i) min_ga1=Fitness(i); sdmin(:,:,1)=sd(:,:,i); end; if min_ga1=0; % Neu ca the hop le thi bo sung vao quan the dem=dem+1; x(:,:,dem)=sd(:,:,h); end; end; popsize=dem; % Kich thuoc quan the thuc te sau khoi tao for h=1:popsize sd(:,:,h)=x(:,:,h); end; % Bat dau thuc hien thuat toan GA min_ga=10^7 ; while count