BỘ GIÁO DỤC VÀ ĐÀO TẠO<br />
ĐẠI HỌC ĐÀ NẴNG<br />
<br />
TRƢƠNG VĂN HIỀN<br />
<br />
ỨNG DỤNG GIẢI THUẬT<br />
DI TRUYỀN GIẢI QUYẾT BÀI TOÁN TỐI<br />
ƢU HÓA XẾP DỠ HÀNG HÓA<br />
<br />
Chuyên nghành : Khoa học máy tính<br />
Mã số :<br />
60.48.01<br />
<br />
TÓM TẮT LUẬN VĂN THẠC SĨ KỸ THUẬT<br />
<br />
Đà Nẵng - Năm 2013<br />
<br />
Công trình đƣợc hoàn thành tại<br />
ĐẠI HỌC ĐÀ NẴNG<br />
<br />
Ngƣời hƣớng dẫn khoa học: PGS. TSKH Trần Quốc Chiến<br />
<br />
Phản biện 1: PGS.TS Lê Văn Sơn<br />
<br />
Phản biện 2: TS Nguyễn Quang Thanh<br />
<br />
Luận văn đƣợc bảo vệ tại Hội đồng chấm Luận văn tốt nghiệp<br />
thạc sỹ kỹ thuật họp tại Đại học Đà Nẵng vào ngày 16 tháng 11<br />
năm 2013.<br />
<br />
* Có thể tìm hiểu luận văn tại:<br />
- Trung tâm Thông tin - Học liệu, Đại học Đà Nẵng.<br />
<br />
1<br />
MỞ ĐẦU<br />
1. Lý do chọn đề tài<br />
Trong cuộc sống, việc đạt lợi nhuận cao hay thấp trong kinh<br />
doanh buôn bán, cung cấp dịch vụ phụ thuộc rất nhiều yếu tố..Trong<br />
đó, có một yếu tố quan trọng đầu tiên, đóng góp một phần rất lớn đó<br />
là xác định đƣợc dự án xếp dỡ hàng hóa từ trong kho chuyển đến các<br />
phƣơng tiện vận chuyển. Có rất nhiều tiêu chí đặt ra khi chọn các<br />
phƣơng án: thuận tiện về giao thông, ít tốn thời gian, ... để làm sao<br />
chi phí bốc xếp là thấp nhất từ đó thu đƣợc lợi nhuận cao nhất.<br />
Sau khi tìm hiểu kiến thức tổng quan và thực tế tồn tại nhiều<br />
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<br />
ƣu, các nhà nghiên cứu đã đề xuất một phƣơng pháp tính toán dựa<br />
trên quan sát về quá tình tiến hoá trong tự nhiên.Phƣơng pháp tính<br />
toán đó đƣợc gọi là tính toán tiến hóa (Evolutionary Computation).<br />
Tính toán tiến hóa có nhiều nhánh nhỏ khác nhau, trong đó có thể kể<br />
tới giải thuật di truyền (Genetic Algorithms).<br />
Giải thuật di truyền đã thu hút đƣợc nhiều chú ý trong những<br />
năm gần đây. Lớp giải thuật này đã đƣợc chứng minh là có nhiều ƣu<br />
đ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<br />
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<br />
dụng trong đời sống thực tiễn.<br />
Chính những ƣu điểm nổi bật của Giải thuật di truyền và nhu<br />
cầu thực tế kinh doanh buôn bán lập dự án xếp dỡ hàng hóa, em<br />
nghiên cứu về giải thuật này và thực hiện đề tài: “Ứng dụng giải<br />
thuật di truyền giải quyết bài toán tối ưu xếp dỡ hàng hóa”.<br />
<br />
2<br />
2. Mục tiêu và nhiệm vụ nghiên cứu<br />
Mục tiêu của đề tài là tìm hiểu giải thuật di truyền, xây dựng<br />
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.<br />
Đề tài tập trung vào các nhiệm vụ cụ thể sau:<br />
- Trình bày khái quát thuật toán di truyền giải quyết bài toán<br />
lập dự án bốc xếp hàng hóa để cung cấp cho khách hàng.<br />
- Triển khai thực nghiệm áp dụng thuật toán<br />
3. Đối tƣợng, phạm vi và phƣơng pháp nghiên cứu<br />
Đối tượng nghiên cứu của đề tài<br />
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<br />
bằng thu phát và hƣớng tiếp cận bài toán.<br />
Phạm vi nghiên cứu của đề tài<br />
Đề tài tập trung nghiên cứu thuật toán di truyền giải quyết bài<br />
toán tối ƣu xếp dỡ hàng hóa.<br />
4. Phƣơng pháp nghiên cứu<br />
Nghiên cứu lý thuyết: Tìm hiểu, nghiên cứu lý thuyết về thuật<br />
toán di truyền, các đặc điểm, đặc trƣng của giải thuật và ứng dụng<br />
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.<br />
Nghiên cứu thực tiễn: nghiên cứu đánh giá thực nghiệm, xây<br />
dựng chƣơng trình thực nghiệm thuật toán di truyền.<br />
5. Bố cục luận văn<br />
Nội dung luận văn bao gồm các chƣơng đƣợc tổ chức nhƣ sau:<br />
Chƣơng 1: Cơ sở lý thuyết. Giới thiệu lý thuyết về giải thuật di<br />
truyền. Đây là kĩ thuật chính để giải quyết bài toán tối ƣu chọn các<br />
địa điểm để xếp dỡ hàng hóa phục vụ khách hàng.<br />
Chƣơng 2: Giải thuật di truyền giải quyết bài toán tối ƣu xếp<br />
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<br />
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<br />
toán.<br />
<br />
3<br />
Chƣơng 3: Xây dựng và cài đặt chƣơng trình. Chƣơng này mô<br />
tả chức năng của hệ thống chƣơng trình và sử dụng ngôn ngữ lập<br />
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<br />
kết quả thực nghiệm.<br />
<br />