Giải thuật di truyền và ứng dụng đối với bài toán vận tải

ĐẠ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 TOÁN VẬN TẢI

Chuyên ngành: Khoa học máy tính

Thái Nguyên - 2014

i

LỜI CAM ĐOAN

Sau quá trình học tập tại Trường Đại học Công nghệ thông

tin và Truyền thông, với những kiến thức lý thuyết và thực hành đã

tích lũy được, với việc vận dụng các kiến thức vào thực tế, em đã tự

nghiên cứu các tài liệu, các công trình nghiên cứu, đồng thời có sự phân

tích, tổng hợp, đúc kết và phát triển để hoàn thành luận văn thạc sĩ của

mình. Em xin cam đoan luận văn này là công trình do bản thân em tự

tìm hiểu, nghiên cứu và hoàn thành dưới sự hướng dẫn của thầy giáo,

TS. Vũ Vinh Quang.

Thái Nguyên, tháng 7 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 của chương trình đào tạo thạc sĩ, trong đó

gần một nửa thời gian dành cho các 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 và hoàn thiện luận văn. Với quỹ thời gian như vậy và với

vị trí công việc đang phải đảm nhận, không riêng bản thân em mà hầu

hết các sinh viên cao học muốn hoàn thành tốt luận văn của mình trước

hết đều phải có sự sắp xếp thời gian hợp lý, có sự tập trung học tập và

nghiên cứu với tinh thần nghiêm túc, nỗ lực hết mình; tiếp đến là có sự

ủng hộ về tinh thần, sự giúp đỡ về chuyên môn - một trong những điều

kiện không thể thiếu quyết định đến việc thành công của luận văn.

Để hoàn thành được luận văn này 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, là người định

hướng nội dung, hướng phát triển của luận văn và có nhiều ý kiến đóng

góp quan trọng về những vấn đề chuyên môn của luận văn, giúp em tháo

gỡ kịp thời những vướng mắc trong quá trình làm luận văn.

Em cũng xin chân thành cảm ơn các thầy, cô giáo Trường Đại học

Công nghệ thông tin và Truyền thông và bạn bè cùng lớp đã có những

ý kiến bổ ích để luận văn được hoàn thiện hơn. Xin cảm ơn gia đình,

người thân, đồng nghiệp luôn quan tâm, ủng hộ về tinh thần trong suốt

thời gian học tập và hoàn thành luận văn.

Em xin hứa sẽ cố gắng tự nghiên cứu, nâng cao năng lực chuyên môn

của mình để sau khi hoàn thành luận văn này sẽ 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 này để có những ứng

dụng thiết thực trong thực tế.

Thái Nguyên, tháng 7 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 các chữ viết tắt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi

Danh mục các bảng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii

Danh mục các hình . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii

LỜI MỞ ĐẦU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

Chương 1. Bài toán vận tải . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.1. Bài toán quy hoạch tuyến tính . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.1.1. Mô hình một số bài toán thực tế. . . . . . . . . . . . . . . . . . . . . . . . . 3

1.1.2. Bài toán quy hoạch tuyến tính. . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.2. Bài toán vận tải. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.3. Thuật toán phân phối giải bài toán vận tải . . . . . . . . . . . . . . . . . 13

1.3.1. Định nghĩa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.3.2. Cơ sở lý luận của 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 của bài toán vận tải . . . . . . . . . . . . . . . . . . . . . . . . 18

1.4.1. Bài toán vận tải không cân bằng thu phát . . . . . . . . . . . . . . 18

1.4.2. Bài toán vận tải dạng cực đại. . . . . . . . . . . . . . . . . . . . . . . . . . . 20

Chương 2. Giải thuật di truyền và ứng dụng đối với bài toán

vận tải . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

2.1. Giới thiệu về Giải thuật di truyền . . . . . . . . . . . . . . . . . . . . . . . . . . 28

iv

2.2. Các khái niệm cơ bản . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

2.2.1. Cá thể, nhiễm sắc thể . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

2.2.2. Quần thể . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

2.2.3. Chọn lọc (Selection) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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ố của 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 hiện 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 toá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ử của RCGA. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

2.8. Thuật toán di truyền với bài toán vận tải cân bằng. . . . . . . . . 46

2.8.1. Biểu diễn lời giải bài toán vận tải bằng véc tơ . . . . . . . . . . 46

2.8.2. Biểu diễn lời giải bài toán vận tải bằng ma trận . . . . . . . . 51

Chương 3. Một số kết quả thực nghiệm . . . . . . . . . . . . . . . . . 56

3.1. Mô tả các 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 quả 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: giải thuật di truyền

EC - Evolutionary computation: tính toán tiến hóa

EP - Evolutionary Programming: quy hoạch tiến hóa

ES - Evolutionary Strategies: các chiến lược tiến hóa

GP - Genetic Programming: lập trình di truyền

CS - Classifier Systems: các hệ thống phân loại

NST: nhiễm sắc thể

Selection: chọn lọc

Crossover: lai ghép

Mutation: đột biến

Reproduction: sinh sản

pop_size: kích cỡ quần thể

RCGA: thuật toá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 1.1: Hợp đồng chở hàng

Bảng 1.2: Cự ly vận chuyển

Bảng 1.3: Khả năng thu - phát

Bảng 1.4: Tổng số tấn × km xe rỗng ít nhất

Bảng 3.1: Kết quả sau 10 lần chạy ngẫu nhiên.

Bảng 3.2: Kết quả sau 10 lần chạy ngẫu nhiên.