By Iorwerth
#968226 Link tải luận văn miễn phí cho ae Kết nối


CHƢƠNG 1. TỐI ƢU TỔ HỢP VÀ BÀI TOÁN TRÌNH TỰ XE...............................11
1.1 Giới thiệu bài toán tối ƣu tổ hợp......................................................................11
1.2 Giới thiệu bài toán ngƣời chào hàng................................................................12
1.3 Các cách tiếp cận giải quyết bài toán tối ƣu tổ hợp .........................................13
1.3.1 Heuristic cấu trúc ......................................................................................13
1.3.2 Tìm kiếm địa phƣơng ................................................................................14
1.3.3 Phƣơng pháp metaheuristic.......................................................................15
1.3.4 Phƣơng pháp Memetic ..............................................................................16
1.4 Bài toán trình tự xe..........................................................................................16
1.4.1 Giới thiệu bài toán trình tự xe (Car Sequencing Problem – CarSP) ........16
1.4.2 Ví dụ cho bài toán CarSP ..........................................................................20
1.5 Các phƣơng pháp tiếp cận giải bài toán trình tự xe ........................................24
1.5.1 Quy hoạch ràng buộc ................................................................................24
1.5.2 Quy hoạch số nguyên ................................................................................26
1.5.3 Phƣơng pháp tiếp cận ăn tham ngẫu nhiên ...............................................27
1.5.4 Tìm kiếm địa phƣơng ................................................................................28
CHƢƠNG 2. PHƢƠNG PHÁP TỐI ƢU ĐÀN KIẾN..................................................29
2.1 Từ kiến tự nhiên đến kiến nhân tạo..................................................................29
2.1.1 Kiến tự nhiên.............................................................................................29
2.1.2 Kiến nhân tạo (Artificial Ant) ...................................................................32
2.2 Phƣơng pháp tối ƣu đàn kiến ...........................................................................33

2.3 Đồ thị cấu trúc..................................................................................................34
2.4 Mô tả thuật toán ACO tổng quát......................................................................36
2.5 Các hệ kiến.......................................................................................................39
2.5.1 Hệ kiến AS ................................................................................................39
2.5.2 Hệ kiến ACS..............................................................................................42
2.5.3 Hệ kiến MAX-MIN...................................................................................44
2.6 Một số bài toán liên quan.................................................................................46
2.6.1 Đặc tính hội tụ...........................................................................................46
2.6.2 ACO kết hợp với tìm kiếm địa phƣơng.....................................................47
2.6.3 Thông tin heuristic ....................................................................................47
2.6.4 Số lƣợng kiến ............................................................................................48
2.6.5 Tham số bay hơi........................................................................................48
CHƢƠNG 3. CÁC PHƢƠNG PHÁP ACO ĐỂ GIẢI BÀI TOÁN CARSP ................49
3.1 Thuật toán ACO-CP của Christine Solon để giải CarSP (2007) .....................49
3.1.1 Xây dựng đồ thị cấu trúc và khởi tạo vết mùi...........................................49
3.1.2 Xây dựng trình tự xe bởi kiến theo thuật toán ACO-CP...........................51
3.1.3 Thông tin Heuristic ...................................................................................52
3.2 Hai thuật toán của Christine Solon để giải CarSP (2008)................................53
3.2.1 ACO1:Cấu trúc mùi đầu tiên để xác định các trình tự con tốt..................53
3.2.2 ACO2: Cấu trúc mùi thứ hai để xác định xe ô tô quan trọng ...................55
3.2.3 ACO 1+2:Sự kết hợp hai cấu trúc mùi......................................................56
3.3 Thuật toán TSIACO (2011) .............................................................................58
3.3.1 Phƣơng pháp hệ kiến hai giai đoạn ...........................................................58
3.3.2 Phƣơng pháp chia giai đoạn cập nhật cho thuật toán................................59
3.3.3 Giới hạn vết mùi........................................................................................60
3.3.4 Khởi tạo giá trị mùi ...................................................................................60
3.3.5 Nhận xét ....................................................................................................60
3.3.6 Mô tả thuật toán TSIACO giải bài toán trình tự xe...................................61
3.4 Thuật toán TSIACOLS ....................................................................................61
CHƢƠNG 4. KẾT QUẢ THỰC NGHIỆM, SO SÁNH VÀ ĐÁNH GIÁ....................64
4.1 ộ dữ liệu chu n ..............................................................................................64
4.2 Tiến hành chạy thực nghiệm trên hệ điều hành Ubuntu ..................................65

4.3 Kết quả thực nghiệm và đánh giá.....................................................................67
4.3.1 Kết quả thực nghiệm ACO1+2 .................................................................69
4.3.2 Kết quả thực nghiệm TSIACOLS (có thủ tục Local Search) ...................70
4.3.3 So sánh các thuật toán ACO khác nhau khi cùng vòng lặp ......................71
4.3.4 So sánh các thuật toán ACO khác nhau trong cùng thời gian chạy ..........72
KẾT UẬN ...................................................................................................................74
TÀI LIỆU THAM KHẢO .............................................................................................75

M
Ở ĐẦU
Trong quá trình sản xuất ra sản ph m thì việc lập kế hoạch sản xuất là cực
kỳ quan trọng, nó ảnh hƣởng trực tiếp tới hiệu suất của hệ thống máy móc và
qua đó ảnh hƣởng đến chất lƣợng của toàn bộ quá trình sản xuất. Đặc biệt ngày
nay khi mà quy mô sản xuất lớn, việc đƣa ra lịch sản xuất hợp lý càng có ý
nghĩa quan trọng, thực tế việc lập kế hoạch sản xuất là không hề đơn giản và
không thể chỉ đơn thuần dựa trên kinh nghiệm. Chính vì lý do đó lĩnh vực tối ƣu
hóa đã tiến hành nghiên cứu bài toán trình tự xe từ năm 1986 nhằm mục đích
số hóa bài toán và xây dựng lời giải trên máy tính nhằm giảm thiểu thời gian sản
xuất và đảm bảo đƣợc dung lƣợng làm việc của các trạm sản xuất không tốn quá
nhiều chi phí (ràng buộc về dung lƣợng) để mang lại hiệu quả về kinh tế và năng
suất. Bài toán đã thu hút đƣợc sự chú ý quan tâm của đông đảo giới chuyên môn
và đƣợc đầu tƣ nghiên cứu môt cách thích đáng. Đây là bài toán NP-khó trong
lớp bài toán tối ƣu tổ hợp có nhiều ràng buộc nên chỉ có thể tìm ra lời giải gần
đúng trong thời gian đa thức. Trƣớc đây ngƣời ta từng sử dụng các thuật toán
xấp xỉ và mô phỏng tự nhiên nhƣ thuật toán di truyền, thuật toán leo đồi, thuật
toán tìm kiếm địa phƣơng, … để giải bài toán, gần đây nổi lên một phƣơng pháp
mới là phƣơng pháp tối ƣu đàn kiến (Ant Colony Optimization) với kết quả thực
nghiệm nổi trội đƣợc đánh giá cao.
Tối ƣu hóa đàn kiến (Ant Colony Optimization - ACO) là cách tiếp cận
metaheuristic tƣơng đối mới, do Dorigo giới thiệu vào năm 1991 và liên tục
đƣợc phát triển cho đến nay. Thành công đầu tiên của các thuật toán ACO là giải
quyết bài toán Ngƣời chào hàng nổi tiếng với số đỉnh lên tới hơn 2000 với kết
quả thu đƣợc là tốt, hiệu quả của nó đƣợc chứng minh bằng thực nghiệm.
Trƣớc tiên, luận văn đã hệ thống hóa các nội dung lý thuyết và thuật
toán liên quan đến vấn đề nghiên cứu: bài toán sắp xếp lập lịch sản xuất xe (gọi
tắt là bài toán trình tự xe) và các phƣơng pháp tiếp cận, phƣơng pháp ACO và
các phƣơng pháp biến thể mới áp dụng cho bài toán nêu trên.
Sau đó, luận văn đã sử dụng quy tắc cập nhật mùi do Christin Solon [2]
đề xuất để xây dựng thuật toán giải bài toán nêu trên, đó là thuật toán
ACO1, ACO2 và kết hợp ACO1+ACO2 (gọi là ACO1+2). Đồng thời tui cũng
sử dụng quy tắc cập nhật mùi do Zhaojun Zhang và Zuren Feng [10] đề xuất
trong bái toán ngƣời chào hàng để giải bài toán trình tự xe (CarSP), đó là
thuật toán TSIACO.
Luận văn đề xuất thuật toán mới TSIACOLS là thuật toán thêm kỹ thuật
tìm kiếm địa phƣơng vào giai đoạn 2 của thuật toán TSIACO.
tui đã tiến hành cài đặt các thuật toán ACO1+2, TSIACO,
TSIACOLS . Sau đó, tui chạy thực nghiệm và so sánh kết quả giữa các
thuật toán trên.
Thực nghiệm cho thấy, thuật toán mới TSIACOLS có những ƣu điểm
nhất định, số lƣợng vi phạm ràng buộc của các xe đƣa ra trung bình tìm đƣợc
thấp hơn so với các thuật toán đã có, tuy thời gian thực hiện lâu hơn khi phải xử
lý tìm kiếm địa phƣơng. Thực nghiệm cũng cho thấy, nếu thời gian và số
lƣợng vòng lặp hạn chế thì thuật toán cho chất lƣợng lời giải tốt nhất và
hội tụ nhanh nhất là ACO1+2, nếu thời gian không hạn chế thì thuật toán cho
chất lƣợng lời giải tốt nhất là TSIACOLS.
Nội dung chính trong bài luận văn của tui gồm 4 chƣơng nhƣ sau:
Chƣơng 1:Giới thiệu về bài toán tối ƣu tổ hợp tổng quát và bài toán trình tự xe,
các cách tiếp cận giải bài toán.
Chƣơng 2:Giới thiệu phƣơng pháp tối ƣu đàn kiến, lịch sử và phát triển.Phƣơng
pháp tối ƣu đàn kiến và bài toán ngƣời chào hàng.
Chƣơng 3:Trình bày các phƣơng pháp ACO giải bài toán trình tự xe.
Chƣơng 4: Tiến hành chạy thực nghiệm chƣơng trình trên bộ dữ liệu chu n,
thống kê, đánh giá kết quả thu đƣợc và so sánh giữa các thuật toán ACO.
Link Download bản DOC
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link tải, không dùng IDM để tải:

Bấm vào đây để đăng nhập và xem link!
Hình đại diện của thành viên
By dungtnut
Kết nối đề xuất:
Learn Synonym
Advertisement