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: 98 trang
Dung lượng: 8 MB

Giới thiệu nội dung

Giải thuật di truyền giải bài toán p-median có hạn chế khả năng

Tác giả: Dương Minh Tuấn

Lĩnh vực: Công nghệ thông tin

Nội dung tài liệu:

Luận văn này tập trung nghiên cứu và xây dựng giải thuật di truyền để giải quyết bài toán p-median có hạn chế khả năng. Bài toán này đóng vai trò quan trọng trong việc xác định địa điểm đặt dịch vụ sao cho tối ưu hóa các yếu tố như khoảng cách, chi phí, hoặc thời gian phục vụ. Luận văn đi sâu vào phân tích các kiến thức cơ sở liên quan đến các bài toán NP, giới thiệu chi tiết về bài toán p-median có hạn chế khả năng và các hướng tiếp cận khác nhau. Phần cốt lõi của luận văn trình bày về việc áp dụng giải thuật di truyền, bao gồm các khía cạnh như mã hóa, hàm đánh giá, khởi tạo quần thể, lai ghép, đột biến và thay thế. Cuối cùng, luận văn đưa ra kết quả thực nghiệm và phân tích, đánh giá hiệu quả của giải thuật được đề xuất.

Mục lục chi tiết:

  • Lời nói đầu
  • Chương 1: Kiến thức cơ sở
    • 1.1. Các kí hiệu tiệm cận
    • 1.2. Độ phức tạp tính toán của bài toán
    • 1.3. NP- đầy đủ
      • 1.3.1. Bài toán quyết định
      • 1.3.2. Bằng chứng ngắn gọn dễ kiểm tra
      • 1.3.3. Lớp bài toán P, NP và co-NP
      • 1.3.4. Qui dẫn
      • 1.3.5. Lớp bài toán NP-khó và NP-đầy đủ
    • 1.4. Sai số tỉ lệ của thuật toán gần đúng
  • Chương 2: Giới thiệu bài toán p-median có hạn chế khả năng và các hướng tiếp cận
    • 2.1. Giới thiệu chung về bài toán p-median có hạn chế khả năng
    • 2.2. Các hướng tiếp cận để giải quyết bài toán p-median có hạn chế khả năng
      • 2.2.1. Phương pháp sinh cột
      • 2.2.2. Phương pháp tìm kiếm địa phương heuristic
      • 2.2.3. Phương pháp Bionomic
  • Chương 3: Giải thuật di truyền giải quyết bài toán p-median có hạn chế khả năng
    • 3.1 Giới thiệu chung về giải thuật di truyền
    • 3.2 Giải thuật di truyền cho bài toán p-median có hạn chế khả năng
      • 3.2.1 Mã hóa
      • 3.2.2 Hàm đánh giá độ tốt của nhiễm sắc thể
      • 3.2.3 Khởi tạo quần thể ban đầu
      • 3.2.4 Lựa chọn bố mẹ lai ghép
      • 3.2.5 Đột biến
      • 3.2.6 Thay thế
      • 3.2.7 Sơ đồ thuật toán
  • Chương 4: Kết quả thực nghiệm
    • 4.1 Mô tả dữ liệu thực nghiệm
    • 4.2 Mô tả hệ thống chương trình
    • 4.3 Kết quả tính toán
      • 4.3.1 Lựa chọn thông số
      • 4.3.2 Kết quả thực nghiệm
    • 4.4 Phân tích đánh giá
  • Tài liệu tham khảo