Luận văn Ứng dụng giải thuật di truyền giải quyết bài toán tối ưu hóa xếp dỡ hàng hóa

BỘ GIÁO DỤC VÀ ĐÀO TẠO ĐẠI HỌC ĐÀ NẴNG TRƢƠNG VĂN HIỀN ỨNG DỤNG GIẢI THUẬT DI TRUYỀN GIẢI QUYẾT BÀI TOÁN TỐI ƢU HÓA XẾP DỠ HÀNG HÓA Chuyên nghành : Khoa học máy tính Mã số : 60.48.01 TÓM TẮT LUẬN VĂN THẠC SĨ KỸ THUẬT Đà Nẵng - Năm 2013 Công trình đƣợc hoàn thành tại ĐẠI HỌC ĐÀ NẴNG Ngƣời hƣớng dẫn khoa học: PGS. TSKH Trần Quốc Chiến Phản biện 1: PGS.TS Lê Văn Sơn Phản biện 2: TS Nguyễn Quang Thanh Luận văn đƣợc bảo vệ tại Hội đồng chấm Luận văn tốt nghiệp thạc sỹ kỹ thuật họp tại Đại học Đà Nẵng vào ngày 16 tháng 11 năm 2013. * Có thể tìm hiểu luận văn tại: - Trung tâm Thông tin - Học liệu, Đại học Đà Nẵng. 1 MỞ ĐẦU 1. Lý do chọn đề tài Trong cuộc sống, việc đạt lợi nhuận cao hay thấp trong kinh doanh buôn bán, cung cấp dịch vụ phụ thuộc rất nhiều yếu tố..Trong đó, có một yếu tố quan trọng đầu tiên, đóng góp một phần rất lớn đó là xác định đƣợc dự án xếp dỡ hàng hóa từ trong kho chuyển đến các phƣơng tiện vận chuyển. Có rất nhiều tiêu chí đặt ra khi chọn các phƣơng án: thuận tiện về giao thông, ít tốn thời gian, ... để làm sao chi phí bốc xếp là thấp nhất từ đó thu đƣợc lợi nhuận cao nhất. Sau khi tìm hiểu kiến thức tổng quan và thực tế tồn tại nhiều bài toán chƣa có phƣơng pháp giải chấp nhận đƣợc hay lời giải tối ƣu, các nhà nghiên cứu đã đề xuất một phƣơng pháp tính toán dựa trên quan sát về quá tình tiến hoá trong tự nhiên.Phƣơng pháp tính toán đó đƣợc gọi là tính toán tiến hóa (Evolutionary Computation). Tính toán tiến hóa có nhiều nhánh nhỏ khác nhau, trong đó có thể kể tới giải thuật di truyền (Genetic Algorithms). Giải thuật di truyền đã thu hút đƣợc nhiều chú ý trong những năm gần đây. Lớp giải thuật này đã đƣợc chứng minh là có nhiều ƣu điểm nỗi trội so với các loại thuật toán khác đặc biệt khi áp dụng chúng vào lớp bài toán tối ƣu - một lớp bài toán khó và có nhiều ứng dụng trong đời sống thực tiễn. Chính những ƣu điểm nổi bật của Giải thuật di truyền và nhu cầu thực tế kinh doanh buôn bán lập dự án xếp dỡ hàng hóa, em nghiên cứu về giải thuật này và thực hiện đề tài: “Ứng dụng giải thuật di truyền giải quyết bài toán tối ưu xếp dỡ hàng hóa”. 2 2. Mục tiêu và nhiệm vụ nghiên cứu Mục tiêu của đề tài là tìm hiểu giải thuật di truyền, xây dựng thuật toán di truyền giải quyết bài toán tối ƣu xếp dỡ hàng hóa. Đề tài tập trung vào các nhiệm vụ cụ thể sau: - Trình bày khái quát thuật toán di truyền giải quyết bài toán lập dự án bốc xếp hàng hóa để cung cấp cho khách hàng. - Triển khai thực nghiệm áp dụng thuật toán 3. Đối tƣợng, phạm vi và phƣơng pháp nghiên cứu Đối tượng nghiên cứu của đề tài Nghiên cứu xây dựng giải thuật di truyền, bài toán vận tải cân bằng thu phát và hƣớng tiếp cận bài toán. Phạm vi nghiên cứu của đề tài Đề tài tập trung nghiên cứu thuật toán di truyền giải quyết bài toán tối ƣu xếp dỡ hàng hóa. 4. Phƣơng pháp nghiên cứu Nghiên cứu lý thuyết: Tìm hiểu, nghiên cứu lý thuyết về thuật toán di truyền, các đặc điểm, đặc trƣng của giải thuật và ứng dụng của giải thuật di truyền trong việc tìm ra lời giải tối ƣu cho bài toán. Nghiên cứu thực tiễn: nghiên cứu đánh giá thực nghiệm, xây dựng chƣơng trình thực nghiệm thuật toán di truyền. 5. Bố cục luận văn Nội dung luận văn bao gồm các chƣơng đƣợc tổ chức nhƣ sau: Chƣơng 1: Cơ sở lý thuyết. Giới thiệu lý thuyết về giải thuật di truyền. Đây là kĩ thuật chính để giải quyết bài toán tối ƣu chọn các địa điểm để xếp dỡ hàng hóa phục vụ khách hàng. Chƣơng 2: Giải thuật di truyền giải quyết bài toán tối ƣu xếp dỡ hàng hóa. Chƣơng này phát biểu mô hình bài toán và hƣớng tiếp cận giải quyết bài toán. Xây dựng giải thuật di truyền giải quyết bài toán. 3 Chƣơng 3: Xây dựng và cài đặt chƣơng trình. Chƣơng này mô tả chức năng của hệ thống chƣơng trình và sử dụng ngôn ngữ lập trình cài đặt thuật toán giải bài toán tối ƣu xếp dỡ hàng hóa. Thể hiện kết quả thực nghiệm. 4 CHƢƠNG 1 CƠ SỞ LÝ THUYẾT 1.1 TỔNG QUAN VỀ GIẢI THUẬT DI TRUYỀN 1.1.1 Lịch sử phát triển 1.1.2 Ƣu và nhƣợc điểm giải thuật di truyền 1.1.3 Sơ đồ tổng thể của giải thuật di truyền Quá trình hoạt động của giải thuật di truyền có thể đƣợc biểu diễn bởi lƣu đồ dƣới đây: Bắt đầu Kết thúc Khởi tạo quần thể Tính giá trị thích nghi Tái sinh Chọn lọc Lai ghép Đột biến Kiểm tra dừng 5 1.1.4 Các cách biểu diễn trong giải thuật di truyền - Biểu diễn bằng chuỗi nhị phân - Biểu diễn bằng số nguyên - Biểu diễn bằng chữ cái 1.1.5 Hàm thích nghi 1.1.6 Các toán tử của giải thuật di truyền a) Chọn lọc + Chọn lọc tỷ lệ + Chọn lọc xếp hạng + Chọn lọc ƣu tú + Chọn lọc cạnh tranh b) Lai ghép c) Đột biến d) Tái Sinh e) Các tham số của giải thuật di truyền + Kích thƣớc của quần thể + Xác suất lai ghép + Xác suất đột biến 1.1.7. Lập trình song song và thuật toán song song 1.1.8. Thuật toán di truyền tuần tự cho bài toán tối ƣu hóa hàm nhiều biến 1.1.9. Song song hóa giải thuật di truyền trong bài toán tối ƣu hóa hàm nhiều biến 1.1.10. Đánh giá chƣơng trình song song với chƣơng trình tuần tự 1.2 TỔNG QUAN VỀ BÀI TOÁN TỐI ƢU 1.2.1 Bài toán tối ƣu tổng quát và phân loại a) Bài toán tối ưu tổng quát Tối ƣu hóa là một trong những lĩnh vực kinh điển của toán học 6 có ảnh hƣởng đến hầu hết các lĩnh vực khoa học – công nghệ và kinh tế – xã hội. Trong thực tế, việc tìm giải pháp tối ƣu cho một vấn đề nào đó chiếm một vai trò hết sức quan trọng. Phƣơng án tối ƣu là phƣơng án hợp lý nhất, tốt nhất, tiết kiệm chi phí, tài nguyên, nguồn lực mà lại cho hiệu quả cao. b) Phân loại các bài toán tối ưu Các bài toán tối ƣu, cũng còn đƣợc gọi là các bài toán quy hoạch toán học, đƣợc chia ra thành các lớp sau: – Bài toán quy hoạch tuyến tính. – Bài toán tối ƣu phi tuyến hay còn gọi là bài toán quy hoạch phi tuyến, bao gồm cả bài toán quy hoạch lồi và bài toán quy hoạch toàn phƣơng. – Bài toán tối ƣu rời rạc, bài toán tối ƣu nguyên và hỗn hợp nguyên. – Bài toán quy hoạch động, – Bài toán quy hoạch đa mục tiêu, – Bài toán quy hoạch ngẫu nhiên / mờ ... Các phƣơng pháp toán học giải các lớp bài toán tối ƣu tổng quát nhƣ nêu trên đây đƣợc gọi là các phƣơng pháp tối ƣu toán học (hay các phƣơng pháp quy hoạch toán học). Trong luận văn này, chúng ta nghiên cứu các phƣơng pháp giải dạng đặc biệt của bài toán quy hoạch tuyến tính, đó là bài toán vận tải cân bằng thu phát. 1.2.2 Ứng dụng bài toán tối ƣu giải quyết các vấn đề thực tế 1.2.3 Bài toán vận tải a) Giới thiệu bài toán vận tải Bài toán vận tải đƣợc áp dụng rất rộng rãi trong lĩnh vực lập kế hoạch phân bổ sản phẩm hàng hoá (dịch vụ) từ một số địa điểm cung / cấp phát tới một số địa điểm cầu / tiêu thụ. Thông thƣờng, tại mỗi địa điểm cung (nơi đi) chỉ có một số lƣợng giới hạn hàng, còn mỗi địa điểm cầu (nơi đến) cần một số lƣợng nhất định hàng để đáp 7 ứng nhu cầu tiêu thụ. Với các cung đƣờng vận chuyển hàng đa dạng, với cƣớc phí vận tải khác nhau, mục tiêu đặt ra là xác định phƣơng án vận tải tối ƣu. Nói cách khác, vấn đề đặt ra là cần xác định nên vận chuyển từ mỗi địa điểm cung tới mỗi địa điểm cầu bao nhiêu đơn vị hàng nhằm thoả mãn nhu cầu của từng địa điểm tiêu thụ đồng thời đạt tổng chi phí vận tải là nhỏ nhất. *Khái niệm bảng vận tải: Bảng vận tải có m hàng, n cột gồm m n ô, m là số điểm cung, n là số điểm cầu với cƣớc phí cij đƣợc ghi trong ô (i, j) cho cung đƣờng (i, j). *Các phương pháp tạo phương án xuất phát: +Phương pháp "góc tây bắc" +Phương pháp cước phí tối thiểu b) Các tính chất của bài toán vận tải Tính chất 1: Bài toán vận tải cân bằng thu phát luôn có phƣơng án tối ƣu. Để nghiên cứu tính chất 2 của bài toán vận tải, trƣớc hết chúng ta xem xét các định nghĩa sau đây. Định nghĩa 1. Một tập hợp các ô trong bảng vận tải đƣợc nói là tạo nên một chu trình khép kín nếu có thể tìm đƣợc một đƣờng đi khép kín xuất phát từ một ô nào đó thuộc tập hợp trên lại trở về ô xuất phát sau khi lần lƣợt đi qua các ô khác trong tập hợp (mỗi ô đi qua đúng một lần) dọc theo các hàng hay các cột của bảng vận tải, bƣớc này theo hàng thì bƣớc sau phải theo cột hoặc ngƣợc lại. Nhƣ vậy, số ô tối thiểu trong một chu trình khép kín là 4. Định nghĩa 2. Một tập hợp một số ô của bảng vận tải đƣợc nói là không tạo nên đƣợc một chu trình khép kín nào là một tập hợp các ô có tính chất: không một tập con nào của nó có thể tạo nên một chu trình khép kín. 8 Tính chất 2: Với một phƣơng án bất kỳ, số ô chọn của phƣơng án không vƣợt quá tổng số điểm cung và cầu. Tính chất 3: Một phƣơng án cực biên của bài toán vận tải (m hàng và n cột) là một phƣơng án ứng với m + n– 1 ô sử dụng không tạo nên một chu trình khép kín nào. Tính chất 4: Nếu lƣợng cung và lƣợng cầu là số nguyên thì bài toán có lời giải nguyên. CHƢƠNG 2 GIẢI THUẬT DI TRUYỀN GIẢI QUYẾT BÀI TOÁN TỐI ƢU XẾP DỠ HÀNG HÓA 2.1 PHÁT BIỂU BÀI TOÁN TỐI ƢU XẾP DỠ HÀNG HÓA 2.1.1 Giới thiệu 2.1.2 Mô hình bài toán Có m kho hàng, kho i có ai đơn vị hàng. Có n xe chở, xe j cần nhận bj đơn vị hàng. cij là chi phí bốc 1 tấn hàng từ kho i đến xe j (i= ; j= ) Gọi xij là số đơn vị hàng hóa: Từ kho i đến xe j (i= ; j= ) f(x) tổng chi phí theo kế hoạch bốc xếp x: min)( 1 1 ij m i n j ij xcxf (1) Kho chứa bốc hết hàng: n j ijx 1 = ai , i= (2) Xe chở bốc đủ hàng: m i ijx 1 = bj , j= (3) Điều kiện cân bằng thu - phát: n j j m i i ba 11 9 Đầu vào: m là số lƣợng kho chứa hàng hóa ( các nguồn) n là số lƣợng xe chở hàng hóa (các đích) số lƣợng hàng hóa cung cấp của mỗi nguồn số lƣợng hàng hóa thu của mỗi đích cost() : ma trận chi phí bốc xếp 1 đơn vị hàng hóa Đầu ra: Ma trận chứa các lời giải tốt nhất của tất cả các thế hệ Tổng chi phí thấp nhất 2.2 PHƢƠNG PHÁP THẾ VỊ GIẢI BÀI TOÁN Thuật toán thế vị được trình bày như sau : Bƣớc 1 : lập bảng vận tải (1) Kiểm tra điều kiện cân bằng thu phát (2) Xác định phƣơng án cực biên ban đầu (bằng phƣơng pháp chi phí bé nhất) (3) Kiểm tra phƣơng án cực biên có suy biến hay không + Nếu suy biến : thêm vào ô (i, j) bất kỳ với xij=0, không tạo thành chu trình. + Nếu không suy biến : thì chuyển sang bƣớc 2 Bƣớc 2 : Kiểm tra tính tối ƣu của bài toán (1) Tính vj = ui + cij ui = vj – cij ,trong đó ô (i, j) là ô chọn Chọn ui = 0 tại dòng bất kỳ (2) Đặt ij = vj – ui – cij Nếu ij ≤ 0 : ta có phƣơng án tối ƣu Nếu ij> 0 : chuyển sang bƣớc 3 Bƣớc 3 : Xác định vòng điều chỉnh (1) chọn ô vào : Max ij( ij>0) (2) chọn ô ra : 10 + xác định vào điều chỉnh + ô vào sẽ đƣợc đánh dấu (+). Xen kẽ dấu (-) và dấu (+) trên vòng điều chỉnh. + lƣợng điều chỉnh q= min {xij/ (i, j) có dấu (-)} Bƣớc 4 : Xác định phƣơng án cực biên mới xij + q dấu (+) x’ij = xij – q dấu (-) xij không dấu quay về bƣớc 2. Sau một số bƣớc lặp hữu hạn, bài toán có phƣơng án tối ƣu. 2.3 GIẢI THUẬT DI TRUYỀN GIẢI BÀI TOÁN TỐI ƢU XẾP DỠ 2.3.1 Biểu diễn lời giải bài toán Có lẽ biểu diễn lời giải tự nhiên nhất cho bài toán bốc dỡ hàng hóa (m nguồn và n đích) là cấu trúc hai chiều, sử dụng ma trận V= (vij) ( 1 ≤ i ≤ m, 1≤ j ≤ n). V= [ ] Với cách biểu diễn này ta sẽ đi tìm cách diễn tả ràng buộc, hàm lƣợng giá, cùng các toán tử di truyền tƣng ứng. 2.3.2 Hệ thống ràng buộc Rõ ràng với mỗi lời giải khi biểu diễn bằng ma trận (mảng 2 chiều) lời giải V= (vij) có thể thỏa mãn ràng buộc của bài toán n j ijv 1 = sour (i) i= 1, 2, , m m i ijv 1 = dest (j) j= 1, 2, , n 11 vij ≥ 0 i= 1, 2, , m ; j= 1, 2, , n Thêm vào đó các thông số về số lƣợng hàng của các nguồn sour(i) và các đích dest(j), còn bảng chi phí bốc dỡ một đơn vị hàng hóa sẽ đƣợc biểu diễn bằng ma trận hai chiều cost(i, j). Với cách biểu diễn bằng ma trận thì các ràng buộc đƣợc diễn tả dễ dàng và tự nhiên hơn. 2.3.3 Hàm lƣợng giá Hàm lƣợng giá là tính tổng chi phí bốc dỡ hàng hóa từ các kho (nguồn) đến các xe (đích), cũng chính là hàm mục tiêu của bài toán. eval(vij)= ),(cos. 1 1 jitv m i n j ij 2.3.4 Thủ tục khởi tạo Để mô tả cách tạo một lời giải thỏa tất cả ràng buộc, ta xây dựng một giải thuật có tên là khoi_tao . Có thể lời giải thu đƣợc sẽ là tối ƣu nhƣng vấn đề đó ta chƣa đề cập ở đây. Procedurekhoi_tao ( ) Input: mảng sour(m), dest(n) Output : mảng (vij) sao cho vij ≥ 0 với i,j thỏa mãn ràng buộc toàn cục Begin L ←{1,2,,mx n} là danh sách các điểm chưa được xét Repeat Chọn ngẫu nhiên 1 số q trong L chưa được xét Đánh dấu q đã xét (hàng) i ← (q-1) div n +1 (cột) j ← (q-1)mod n +1 val ←min {sour(i),dest(j)} vij ← val 12 sour(i) ← sour(i) – val dest( j) ← dest(j) – val Until ( tất cả các điểm trong L đều được thăm ) End; 2.3.5 Các toán tử di truyền a) Đột biến Cho 2 ≤ p ≤ n , 2 ≤ q ≤ m, giả sử rằng { i1, i2,,ip} là tập con của {1, 2, , n} và {j1, j2,,jq} là tập con của {1, 2, , m}. Ta biểu diễn một cha (mẹ) của đột biến bằng ma trận kích thƣớc (n x m) là V = (vij). Rồi tạo ma trận con kích thƣớc (p x q) là W = (wij), từ tất cả các phần tử của ma trận V theo cách sau: một phần tử vij V trong W nếu và chỉ nếu i { i1, i2,,ip} và j {j1, j2,,jq}. Điều này có nghĩa là nếu i = ir, j = js thì phần tử vij đƣợc đặt trong hàng r và cột s của ma trận W. Bây giờ ta mới có thể gán các giá trị mới sour W(i) và dest W(j) cho ma trận W (1 ≤ i ≤ p , 1 ≤ j ≤ q) : sour W(i) = ∑ 1 ≤ i ≤ p dest W(j) = ∑ 1 ≤ j ≤ q Ta sẽ áp dụng thủ tục khoi_tao để gán các giá trị mới cho ma trận W sao cho tất cả các ràng buộc sour W(i) và dest W(j) đƣợc thỏa mãn. Sau đó, ta thay phần tử thích hợp của ma trận V bằng các phần tử mới của ma trận W. Bằng cách này ta đã tạo ra đƣợc đột biến mà tất cả các ràng buộc toàn cục (sour(i) và dest(j) đƣợc bảo toàn). b) Lai tạo Giả sử rằng sau khi thực hiện lựa chọn hai lần để chọn ra hai ma trận V1= (vij) và V2 = (uij) làm cha mẹ để thực hiện lai tạo. Ta có giải thuật đƣợc dùng để sinh hai con V3 và V4 : - Tạo hai ma trận tạm : 13 + D : lƣu các giá trị trung bình đƣợc làm tròn (dƣới) từ cả cha lẫn mẹ : D= (dij) =(⌊ + ⌋/2) + R : theo dõi xem việc làm tròn nào ở trên là cần thiết, là ma trận nhị phân : R = (rij) = ((vij + uij) mod 2) - Ta biến đổi ma trận R thành 2 ma trận R1=(tij) và R2=(sij) sao cho R= R1 + R2 và : n j n j ijij n j ij rst 1 11 2 1 i = 1, 2, ., m m i m i ijij m i ij rst 1 11 2 1 j = 1, 2, ., n -Kết quả sinh ra 2 con của V1 và V2: V3 = D + R1 V4 = D + R2 2.3.6 Sơ đồ thuật toán Bước 1: Khởi tạo 1. Đọc (sinh) dữ liệu 2. Khởi tạo quần thể 3. Sắp xếp quần thể theo thứ tự tăng dần của chi phí 4. Giữ lại cá thể tốt nhất 5. Ghi nhận cá thể tốt nhất Cbest Bước 2: Vòng lặp chính 1. Sinh thêm cá thể qua các bƣớc lai ghép và đột biến. Nếu các cá thể này tốt hơn cá thể tốt nhất trong quần thể cũ thì nó sẽ có mặt trong quần thể mới. 2. Chuyển cá thể tốt nhất ở quần thể cũ sang quần thể mới 3. Sắp xếp quần thể theo thứ tự tăng dần của chi phí 14 4. Nếu cá thể tốt nhất ở quần thể mới tốt hơn CBest thì: đặt CBest - cá thể tốt nhất này và Counter= 0; nếu không tăng biến Counter lên l. Bước 3: Kiểm tra điều kiện kết thúc 1. Nếu Counter= Max (chạy quá số lần lặp cho phép, dừng) 2. Hiển thị kết quả Nhƣ vậy, thuật toán sẽ kết thúc nếu sau Max bƣớc lặp vẫn không tạo ra đƣợc nhiễm sắc thể mới tốt hơn nhiễm sắc thể tốt nhất hiện có. 15 CHƢƠNG 3 XÂY DỰNG VÀ CÀI ĐẶT CHƢƠNG TRÌNH 3.1 THIẾT KẾ MÔ HÌNH CƠ SỞ DỮ LIỆU 3.1.1 Xác định các thực thể Qua quá trình nghiên cứu, đã xác định các thực thể của bài toán nhƣ sau: - Thực thể KHO: mô tả mỗi kho có kí hiệu kho, cho biết số lƣợng gạo chứa trong mỗi kho. - Thực thể XE: mô tả kí hiệu của mỗi xe, số lƣợng gạo bốc lên xe. - Thực thể CHI PHÍ: Cho biết thông tin về chi phí bốc xếp một tấn gạo từ mỗi kho đến mỗi xe. - Thực thể PHƢƠNG ÁN XẾP DỠ: lƣu trữ kết quả sau khi xử lý, thể hiện phƣơng án xếp dỡ tối ƣu, thông tin chi tiết về số lƣợng gạo bốc ở mỗi kho lên mỗi xe để tổng chi phí bốc xếp là thấp nhất. * Xây dựng lược đồ cơ sở dữ liệu - KHO (MaKho, TenKho, SoLuong) - XE (MaXe, TenXe, SoLuong) - CHI PHÍ (MaKho, MaXe, ChiPhi, MoTa) - PHƢƠNG ÁN XẾP DỠ (MaKho, MaXe, Soluong) 3.1.2 Mô tả cơ sở dữ liệu Bảng kho: STT Khóa Tên trƣờng Kiểu dữ liệu Null Mô tả 1 PK MaKho vachar(5) Not null Khóa chính 2 TenKho nvarchar(50) Tên Kho 3 SoLuong int(4) Số lƣợng gạo chứa trong kho 16 Bảng xe: STT Khóa Tên trƣờng Kiểu dữ liệu Null Mô tả 1 PK MaXe vachar(5) Not null Khóa chính 2 TenXe nvarchar(50) Tên xe 3 SoLuong int(4) Số lƣợng gạo xếp dỡ lên xe Bảng chi phí: STT Khóa Tên trƣờng Kiểu dữ liệu Null Mô tả 1 PK MaKho vachar(5) Not null Khóa chính 2 PK MaXe varchar(5) Khóa chính, tên xe 3 ChiPhi int(4) Chi phí bốc một tấn gạo từ một kho lên một xe 4 MoTa nvarchar(50) Mô tả tuyến bốc xếp từ kho đến xe 17 Bảng phương án xếp dỡ: STT Khóa Tên trƣờng Kiểu dữ liệu Null Mô tả 1 MaKho vachar(5) Mã kho gạo 2 MaXe varchar(5) Mã xe vận chuyển 3 SoLuong int(4) Số lƣợng gạo từ kho cần bốc xếp lên xe 3.2 CẤU TRÚC DỮ LIỆU CỦA BÀI TOÁN Bài toán đƣợc nêu ra để tìm phƣơng án xếp dỡ tối ƣu. Dữ liệu của bài toán đƣợc biểu diễn dƣới dạng sau đây: Dùng cấu trúc mảng một chiều biểu diễn số lƣợng gạo cung cấp của các kho và số lƣợng gạo bốc lên các xe. int sour[ ] ; int dest [ ] ; Sử dụng mảng hai chiều biểu diễn ma trận chi phí bốc xếp cho một tấn gạo. int cost [ ] [ ]; Dữ liệu ra của bài toán: int Result[ ][ ]; //ma trận chứa các lời giải của thế hệ int Best [ ][ ]; //ma trận chứa lời giải tốt nhất Ngoài ra chƣơng trình còn sử dụng các biến sau: int m, n, pop_size, gen_mun; //n: số kho cung cấp gạo //m: số xe chở gạo //pop_size: kích thƣớc quần thể 18 //gen_num: số thế hệ hay số lần lặp float Pc, Pm; // Pc: xác suất lai // Pm: xác xuất đột biến 3.3 THIẾT KẾ GIAO DIỆN CỦA CHƢƠNG TRÌNH Chƣơng trình gồm các form sau: * Form nhập dữ liệu kho * Form nhập dữ liệu xe * Form nhập chi phí bốc xếp một tấn gạo của các kho hàng lên các xe * Form nhập thông số của giải thuật di truyền * Form hiển thị kết quả 3.4 KẾT QUẢ THỰC NGHIỆM CỦA CHƢƠNG TRÌNH Hệ thống chƣơng trình đƣợc cài đặt bằng ngôn ngữ Visual Basic, chạy trên môi trƣờng Windows Seven trên máy Dual Core 2.0 Ghz. Dữ liệu vào của bài toán xếp dỡ thể hiện ở bảng sau: X1 X2 X3 X4 Xe Kho Kho 5 15 15 10 K1 15 10 0 20 11 K2 25 12 7 9 20 K3 5 0 14 16 18 Nhập dữ liệu vào chƣơng trình nhƣ các hình bên dƣới: 19 Hình 3.1: Giao diện nhập thông tin kho chứa Hình 3.2: Giao diện nhập thông tin xe vận chuyển 20 Hình 3.3: Giao diện nhập chi phí bốc xếp Cùng với các thông số của giải thuật di truyền của bài toán nhƣ sau: Hình 3.4: Thông số giải thuật di truyền 21 Kết quả chạy chƣơng trình: Bảng phân phối số lƣợng xếp dỡ Xe Kho X1 X2 X3 X4 K1 5 10 0 0 K2 0 5 15 5 K3 0 0 0 5 Tổng chi phí là : 410 Lời giải tối ƣu của bài toán: Hình 3.5: Lời giải tối ƣu của bài toán Sau khi chƣơng trình hoàn tất sẽ cho ra kết quả tốt nhất dựa trên bộ dữ liệu vào.Kết quả sẽ hiển thị bảng số lƣợng phân bố xếp dỡ 22 của kết quả đó và hiển thị tổng chi phí bốc xếp của lời giải nhƣ hình 5 ở trên. Đặc biệt chƣơng trình còn cho phép ta xem kết quả của từng cá thể trong từng thế hệ. Rất đơn giản, ta chỉ cần chọn số thế hệvà thế tự cá thể ở trong quần thể (đã sắp xếp theo chiều tăng dần của tổng chi phí bốc xếp) , chọn xong nhấn vào nút Xem bên cạnh để xem kết quả mong muốn nhƣ hình 6 bên dƣới. Hình 3.6: Lời giải của từng thế hệ Hơn nữa, chƣơng trình có thể thực hiện lại thuật toán trên với bộ dữ liệu vào nhƣ cũ nhƣng với các tham số của quần thể nhƣ: số cá thể, kích thƣớc quần thể, xác suất lai, xác suất đột biến có thể thay đổi đƣợc bằng cách sau khi đã nhận đƣợc kết quả cuối cùng thì ta nhấn vào nút nhập lại để thực hiện lại thuật toán. 23 KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN 1. Kết luận Từ những kết quả nghiên cứu của luận văn cho phép rút ra một số kết luận sau: +Về lý thuyết Tìm hiểu đƣợc thuật toán di truyền trong việc tìm lời giải tối ƣu cho bài toán xếp dỡ hàng hóa. Hiểu đƣợc các phƣơng pháp tiếp cận tối ƣu giải bài toán, qua đó so sánh lựa chọn đƣợc giải thuật để giải quyết bài toán nâng cao độ chính xác. Từ đó đánh giá đƣợc giải thuật dựa trên các tiêu chí về tốc độ, hiệu suất và chi phí. +Về thực nghiệm Phân tích và mô tả đƣợc các nhóm chức năng của chƣơng trình ứng dụng. Đây là cơ sở để tiếp tục phát triển đề tài trong tƣơng lai. Cài đặt thành công chƣơng trình thực nghiệm tìm kế hoạch bốc xếp với tổng chi phí nhỏ nhất của thuật toán di truyền ứng dụng vào bài toán tối ƣu xếp dỡ hàng hóa. Ưu điểm và hạn chế của đề tài + Về lý thuyết Luận văn chỉ tập trung nghiên cứu thuật toán di truyền, chƣa nghiên cứu các thuật toán khác (nhƣ thuật toán đàn kiến, thuật toán đàn ong) để có những đánh giá so sánh. Giải thuật di truyền trong luận văn đƣợc thiết kế có một đặc trƣng quan trọng là nó xử lý bất cứ loại hàm chi phí nào (không cần phải liên tục), cũng có thể hiệu chỉnh nó để xử lý nhiều bài toán nghiên cứu những toán tử giống nhau. Việc lựa chọn trƣờng hợp đơn giản nhất bánh xe roulette , điểm đột biến , và một điểm giao nhau với cả hai cá thể và quần thể hiện bằng chiều dài cố định vector - có phức tạp thời gian O ( gens * ( đột biến + lai tạo + chọn lọc ) ), ở đây 24 gens là số lƣợng của các thế hệ, độ phức tạp của điểm đột biến (n * m với n kích thƣớc của quần thể và m là kích thƣớc của các cá thể), độ phức tạp thời gian của lai tạo (n * m một lần nữa), và độ phức tạp của lựa chọn (n trong trƣờng hợp bánh xe roulette thực hiện có hiệu quả). Do đó, độ phức tạp của thuật toán di truyền là O (gens * n * m) (với gens là số thế hệ hay số lần lặp). + Về thực nghiệm Mặc dù đã cài đặt đƣợc một số chức năng nhƣng chƣa kiểm tra thực nghiệm với nhiều bộ dữ liệu khác nhau và còn nhiều chức năng chƣa cài đặt hoàn chỉnh. Chƣơng trình còn tính chất mô phỏng chƣa phải là một ứng dụng hoàn chỉnh. Đánh giá ý nghĩa đóng góp của đề tài Luận văn này mang lại cái nhìn tổng quan về giải thuật di truyền. Tìm hiểu cách thức áp dụng giải thuật di truyền trong bài toán vận tải phi tuyến. Có thể cải tiến giải thuật di truyền trong luận văn áp dụng vào bài toán tối ƣu khác để ứng dụng trong nhiều tình huống, chẳng hạn nhƣ lập lịch trình các công việc trong máy tính, phân phối dòng vốn trong một công ty, phân phối kho. 2. Hƣớng phát triển + Về lý thuyết Tiếp tục nghiên cứu sâu thêm về thuật toán di truyền với những phƣơng pháp tối ƣu hóa đƣợc cải tiến áp dụng trong các bài toán tối ƣu. + Về thực nghiệm Tiếp tục cài đặt các chức năng còn thiếu, cài đặt chƣơng trình chạy trên mô hình xử lý song song.