Xem trước tài liệu

Đang tải tài liệu...

Thông tin chi tiết tài liệu

Định dạng: PDF
Số trang: 45 trang
Dung lượng: 532 KB

Giới thiệu nội dung

PHƯƠNG PHÁP TỐI ƯU ĐÀN KIẾN CHO BÀI TOÁN ĐIỀU PHỐI XE

Tác giả: LÊ MỸ HẠNH

Lĩnh vực: CÔNG NGHỆ THÔNG TIN

Nội dung tài liệu:

Luận văn này trình bày về phương pháp tối ưu đàn kiến (Ant Colony Optimization – ACO) và ứng dụng của nó để giải quyết bài toán điều phối xe (Vehicle Routing Problem – VRP). Bài toán điều phối xe là một bài toán tối ưu tổ hợp phức tạp, nhằm thiết lập hành trình tối ưu cho các phương tiện vận chuyển. Luận văn giới thiệu cơ sở lý thuyết của phương pháp ACO, lịch sử phát triển, các nguyên tắc áp dụng, các quy tắc cập nhật mùi, cũng như các ứng dụng của ACO trong nhiều lĩnh vực khác nhau. Đặc biệt, luận văn tập trung vào việc trình bày cách thức áp dụng ACO cho bài toán điều phối xe, bao gồm việc xây dựng lời giải, cập nhật mùi và thực nghiệm. Các phương pháp heuristic, bao gồm cả các thuật toán metaheuristic như ACO, được đề xuất để tìm kiếm các lời giải gần tối ưu cho các bài toán tối ưu tổ hợp NP-khó trong giới hạn thời gian cho phép.

Mục lục chi tiết:

  • MỤC LỤC
  • DANH SÁCH CÁC HÌNH
  • BẢNG TỪ VIẾT TẮT
  • MỞ ĐẦU
  • CHƯƠNG 1: PHƯƠNG PHÁP TỐI ƯU ĐÀN KIẾN VÀ ỨNG DỤNG
    • 1.1 Lịch sử phát triển:
    • 1.2 Phương pháp tối ưu hóa đàn kiến.
      • 1.2.1 Bài toán tối ưu hóa tổ hợp
      • 1.2.2 Bài toán tổng quát.
      • 1.2.3 Thuật toán tổng quát
      • 1.2.4 Các ứng dụng của ACO
    • 1.3 Các nguyên tắc khi áp dụng tối ưu đàn kiến
      • 1.3.1 Nồng độ vệt mùi
      • 1.3.2 Thông tin heuristic
      • 1.3.3 ACO và Local search
      • 1.3.4 Số lượng kiến.
      • 1.3.5 Điều chỉnh sự học tăng cường và sự khám phá.
      • 1.3.6 Sử dụng giới hạn danh sách láng giềng
    • 1.4 Đánh giá về phương pháp ACO
  • CHƯƠNG 2: BÀI TOÁN ĐIỀU PHỐI XE VÀ CÁC CÁCH GIẢI HIỆN NAY.
    • 2.1 Giới thiệu về bài toán điều phối xe
      • 2.1.1 Lịch sử phát triển
      • 2.1.2 Các biến thể của bài toán điều phối xe
    • 2.2 Tóm tắt nội dung bài toán
    • 2.3 Mô hình hóa bài toán:
    • 2.4 Các cách tiếp cận bài toán :
      • 2.4.1 Thuật toán nhánh cận
      • 2.4.2 Giải thuật di truyền …
  • CHƯƠNG 3: PHƯƠNG PHÁP TỐI ƯU ĐÀN KIẾN CHO BÀI TOÁN ĐIỀU PHỐI XE
    • 3.1 Bài toán điều phối xe (Vehicle Routing Problem – VRP ).
    • 3.2 Sinh giải pháp.
    • 3.3 Cập nhật mùi
      • 3.3.1 Cập nhật mùi theo chiến lược kiến trọng lượng
      • 3.3.2 Cập nhật mùi theo quy tắc Smooth-Max Min Ant System(SMMAS) …
    • 3.4 Tiến hành thực nghiệm…
      • 3.4.1 Bộ dữ liệu chuẩn:
      • 3.4.2 Kết quả thực nghiệm và đánh giá
  • KẾT LUẬN