Luận văn thạc sĩ: Phương pháp đàn kiến trong tối ưu trình tự xe 04

• Tác giả: Đinh Thị Hằng
• Người hướng dẫn: PGS. Hoàng Xuân Huấn
• Trường học: Đại học Quốc gia Hà Nội
• Chuyên ngành: Công nghệ Thông tin
• Đề tài: Tối Ưu Hóa Trình Tự Xe Bằng Phương Pháp Đàn Kiến
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2014
• Địa điểm: Hà Nội

• LỜI CẢM ƠN
• LỜI CAM ĐOAN
• 1. CHƯƠNG 1: TỐI ƯU TỔ HỢP VÀ BÀI TOÁN TRÌNH TỰ XE
• 1.1. Giới thiệu bài toán tối ưu tổ hợp
• 1.2. Giới thiệu bài toán người chào hàng
• 1.3. Các cách tiếp cận giải quyết bài toán tối ưu tổ hợp
• 1.3.1. Heuristic cấu trúc
• 1.3.2. Tìm kiếm địa phương
• 1.3.3. Phương pháp metaheuristic
• 1.3.4. Phương pháp Memetic
• 1.4. Bài toán trình tự xe
• 1.4.1. Giới thiệu bài toán trình tự xe (Car Sequencing Problem – CarSP)
• 1.4.2. Ví dụ cho bài toán CarSP
• 1.5. Các phương pháp tiếp cận giải bài toán trình tự xe
• 1.5.1. Quy hoạch ràng buộc
• 1.5.2. Quy hoạch số nguyên
• 1.5.3. Phương pháp tiếp cận ăn tham ngẫu nhiên
• 1.5.4. Tìm kiếm địa phương
• 2. CHƯƠNG 2: PHƯƠNG PHÁP TỐI ƯU ĐÀN KIẾN
• 2.1. Từ kiến tự nhiên đến kiến nhân tạo
• 2.1.1. Kiến tự nhiên
• 2.1.2. Kiến nhân tạo (Artificial Ant)
• 2.2. Phương pháp tối ưu đàn kiến
• 2.3. Đồ thị cấu trúc
• 2.4. Mô tả thuật toán ACO tổng quát
• 2.4.1. Hệ kiến AS
• 2.4.2. Hệ kiến ACS
• 2.4.3. Hệ kiến MAX-MIN
• 2.6. Một số bài toán liên quan
• 2.6.1. Đặc tính hội tụ
• 2.6.2. ACO kết hợp với tìm kiếm địa phương
• 2.6.3. Thông tin heuristic
• 2.6.4. Số lượng kiến
• 2.6.5. Tham số bay hơi
• 3. CHƯƠNG 3: CÁC PHƯƠNG PHÁP ACO ĐỂ GIẢI BÀI TOÁN CARSP
• 3.1. Thuật toán ACO-CP của Christine Solon để giải CarSP (2007)
• 3.1.1. Xây dựng đồ thị cấu trúc và khởi tạo vết mùi
• 3.1.2. Xây dựng trình tự xe bởi kiến theo thuật toán ACO-CP
• 3.1.3. Thông tin Heuristic
• 3.2. Hai thuật toán của Christine Solon để giải CarSP (2008)
• 3.2.1. ACO1: Cấu trúc mùi đầu tiên để xác định các trình tự con tốt
• 3.2.2. ACO2: Cấu trúc mùi thứ hai để xác định xe ô tô quan trọng
• 3.2.3. ACO 1+2: Sự kết hợp hai cấu trúc mùi
• 3.3. Thuật toán TSIACO (2011)
• 3.3.1. Phương pháp hệ kiến hai giai đoạn
• 3.3.2. Phương pháp chia giai đoạn cập nhật cho thuật toán
• 3.3.3. Giới hạn vết mùi
• 3.3.4. Khởi tạo giá trị mùi
• 3.3.6. Mô tả thuật toán TSIACO giải bài toán trình tự xe
• 3.4. Thuật toán TSIACOLS
• 4. CHƯƠNG 4: KẾT QUẢ THỰC NGHIỆM, SO SÁNH VÀ ĐÁNH GIÁ
• 4.1. Bộ dữ liệu chuẩn
• 4.2. Tiến hành chạy thực nghiệm trên hệ điều hành Ubuntu
• 4.3. Kết quả thực nghiệm và đánh giá
• 4.3.1. Kết quả thực nghiệm ACO1+2
• 4.3.2. Kết quả thực nghiệm TSIACOLS (có thủ tục Local Search)
• 4.3.3. So sánh các thuật toán ACO khác nhau khi cùng vòng lặp
• 4.3.4. So sánh các thuật toán ACO khác nhau trong cùng thời gian chạy
• TÀI LIỆU THAM KHẢO

I. Tối ưu hóa trình tự xe

Bài toán trình tự xe (Car Sequencing Problem - CarSP) là một trong những bài toán tối ưu tổ hợp phức tạp, yêu cầu tìm ra trình tự lắp ráp các xe trên dây chuyền sản xuất sao cho tối thiểu hóa chi phí và thời gian. Tối ưu hóa trong lĩnh vực này không chỉ giúp nâng cao hiệu suất sản xuất mà còn giảm thiểu chi phí vận hành. Các phương pháp truyền thống như quy hoạch ràng buộc và quy hoạch số nguyên đã được áp dụng, nhưng thường gặp khó khăn trong việc tìm ra lời giải tối ưu cho các bài toán lớn. Do đó, việc áp dụng phương pháp đàn kiến (Ant Colony Optimization - ACO) đã trở thành một xu hướng mới, mang lại kết quả khả quan trong việc giải quyết bài toán này.

1.1 Giới thiệu về bài toán trình tự xe

Bài toán trình tự xe được định nghĩa là việc lập kế hoạch cho một tập hợp các xe trên cùng một dây chuyền lắp ráp, trong đó mỗi xe có thể yêu cầu lắp đặt các thành phần khác nhau. Các thành phần này cần được lắp đặt theo một trình tự nhất định để đảm bảo hiệu suất của dây chuyền. Giải thuật tối ưu cho bài toán này không chỉ cần phải đáp ứng các ràng buộc về dung lượng mà còn phải tối ưu hóa thời gian sản xuất. Việc áp dụng thuật toán đàn kiến đã cho thấy khả năng tìm kiếm lời giải gần đúng hiệu quả, đặc biệt trong các bài toán có quy mô lớn và phức tạp.

1.2 Các phương pháp tiếp cận giải bài toán

Có nhiều phương pháp tiếp cận để giải quyết bài toán trình tự xe, bao gồm các phương pháp truyền thống như quy hoạch ràng buộc và quy hoạch số nguyên. Tuy nhiên, những phương pháp này thường không hiệu quả với các bài toán lớn. Phương pháp metaheuristic, đặc biệt là thuật toán đàn kiến, đã được phát triển để cải thiện khả năng tìm kiếm lời giải. Tối ưu hóa đàn kiến sử dụng mô hình hành vi của kiến trong tự nhiên để tìm kiếm các giải pháp tối ưu, cho phép giải quyết các bài toán phức tạp một cách hiệu quả hơn.

II. Phương pháp tối ưu đàn kiến

Phương pháp tối ưu đàn kiến (ACO) là một trong những phương pháp metaheuristic nổi bật, được phát triển từ những năm 1990. ACO mô phỏng hành vi tìm kiếm thức ăn của đàn kiến, trong đó các con kiến để lại dấu vết pheromone trên đường đi của chúng. Các giải pháp được xây dựng dựa trên việc tìm kiếm các đường đi có lượng pheromone cao, từ đó dẫn đến việc tìm ra giải pháp tối ưu cho bài toán. Giải thuật tối ưu này đã được áp dụng thành công trong nhiều lĩnh vực, bao gồm cả quản lý logistics và hệ thống giao thông.

2.1 Từ kiến tự nhiên đến kiến nhân tạo

Kiến tự nhiên có khả năng tìm kiếm thức ăn một cách hiệu quả nhờ vào việc sử dụng pheromone để giao tiếp và dẫn đường. Từ đó, các nhà nghiên cứu đã phát triển kiến nhân tạo (Artificial Ant) để mô phỏng hành vi này trong các bài toán tối ưu. Mô hình đàn kiến cho phép các con kiến nhân tạo tương tác với nhau và chia sẻ thông tin, từ đó cải thiện khả năng tìm kiếm giải pháp tối ưu cho bài toán trình tự xe.

2.2 Mô tả thuật toán ACO tổng quát

Thuật toán ACO tổng quát bao gồm các bước chính như khởi tạo pheromone, xây dựng giải pháp, cập nhật pheromone và lặp lại quá trình cho đến khi đạt được điều kiện dừng. Hệ kiến AS, hệ kiến ACS, và hệ kiến MAX-MIN là các biến thể của ACO, mỗi hệ thống có những ưu điểm riêng trong việc tìm kiếm giải pháp tối ưu cho bài toán. Việc áp dụng các biến thể này trong bài toán trình tự xe đã cho thấy hiệu quả rõ rệt trong việc giảm thiểu chi phí và thời gian sản xuất.

III. Kết quả thực nghiệm và đánh giá

Kết quả thực nghiệm cho thấy rằng các thuật toán ACO, đặc biệt là TSIACOLS, đã đạt được những kết quả khả quan trong việc giải bài toán trình tự xe. Thực nghiệm được thực hiện trên nhiều bộ dữ liệu khác nhau, cho thấy rằng TSIACOLS không chỉ cải thiện chất lượng lời giải mà còn giảm thiểu số lượng vi phạm ràng buộc. Việc so sánh giữa các thuật toán ACO khác nhau cho thấy rằng ACO1+2 cho chất lượng lời giải tốt nhất trong thời gian hạn chế, trong khi TSIACOLS cho kết quả tốt nhất khi không bị giới hạn về thời gian.

3.1 Kết quả thực nghiệm ACO1 2

Kết quả thực nghiệm cho thấy rằng thuật toán ACO1+2 có khả năng tìm kiếm lời giải tối ưu trong thời gian ngắn. Các bài toán được giải quyết cho thấy số lượng vi phạm ràng buộc thấp hơn so với các phương pháp truyền thống. Điều này chứng tỏ rằng tối ưu hóa bằng phương pháp đàn kiến có thể mang lại hiệu quả cao trong việc giải quyết bài toán trình tự xe.

3.2 So sánh các thuật toán ACO khác nhau

Việc so sánh giữa các thuật toán ACO cho thấy rằng mỗi thuật toán có những ưu điểm và nhược điểm riêng. TSIACOLS cho thấy khả năng hội tụ nhanh hơn và chất lượng lời giải tốt hơn trong các bài toán lớn. Trong khi đó, ACO1+2 lại tỏ ra hiệu quả hơn trong các bài toán nhỏ hơn với thời gian chạy hạn chế. Sự kết hợp giữa các phương pháp này có thể tạo ra những giải pháp tối ưu hơn cho bài toán trình tự xe.