Tìm kiếm
Đang tải khung tìm kiếm
Kết quả 1 đến 1 của 1

    THẠC SĨ Giải thuật di truyền cho bài toán đa mục tiêu

    D
    dream dream bây giờ đang trực tuyến (18495 tài liệu)
    .:: Cộng Tác Viên ::.
  1. Gửi tài liệu
  2. Bình luận
  3. Chia sẻ
  4. Thông tin
  5. Công cụ
  6. Giải thuật di truyền cho bài toán đa mục tiêu

    5

    Mục Lục
    LỜI CẢM ƠN . 3
    LỜI CAM ĐOAN 4
    Danh mục các ký hiệu và chữ viết tắt . 7
    Danh mục các hình vẽ đồ thị . 8
    Danh mục các bảng . 9
    MỞ ĐẦU . 10
    CHƯƠNG 1 TỔNG QUAN VỀ TỐI ƯU ĐA MỤC TIÊU 12
    1.1. Giới thiệu bài toán tối ưu đa mục tiêu 12
    1.1.1. Mô hình bài toán tối ưu đa mục tiêu có ràng buộc . 12
    1.1.2. Khái niệm tối ưu Pareto 13
    1.1.3. Khái niệm trội Pareto 13
    1.1.4. Tập các lời giải tối ưu Pareto 13
    1.2. Bài toán cái túi (Knapsack) 14
    1.2.1. Bài cái túi dạng 0-1 . 14
    1.2.2. Bài toán cái túi bị chặn 15
    1.2.3. Bài toán cái túi không bị chặn . 15
    1.3. Bài toán cái túi đa mục tiêu 15
    1.4. Mô hình bài toán cái túi đa mục tiêu 17
    1.4.1. Mô hình mã nhị phân 17
    1.4.2. Mô hình mã hóa hoán vị 18
    1.4.3. Một số ví dụ mã hóa đối với bài toán cái túi đa mục tiêu . 18
    1.4.3.1 Mô hình mã hóa nhị phân 18
    1.4.3.2. Mô hình mã hóa hoán vị . 19
    CHƯƠNG 2 GIẢI THUẬT DI TRUYỀN CHO BÀI TOÁN TỐI ƯU ĐA MỤC TIÊU . 21
    2.1.Giới thiệu về giải thuật di truyền 21
    2.1.1. Các nguyên tắc căn bản của giải thuật di truyền . 21
    2.1.2. Các vấn đề chính trong tìm kiếm đa mục tiêu 23
    2.1.3. Mô hình tổng quát giải thuật tiến hóa . 24
    2.2. Một số thuật toán thường được áp dụng giải bài toán tối ưu đa mục tiêu . 25
    2.2.1. Thuật toán MOGA 25
    2.2.2. Thuật toán VEGA . 26
    2.2.3. Thuật toán SEAMO, SEAMO2 . 27
    2.2.4. Thuật toán NSGA, NSGA2 . 30
    2.2.5. Thuật toán SPEA, SPEA2 . 35
    CHƯƠNG 3 KẾT QUẢ THỰC NGHIỆM VÀ ĐÁNH GIÁ 39
    3.1. Cài đặt thuật toán SEAMO2 39
    3.1.1. Thuật toán SEAMO2 . 39
    3.1.2. Dữ liệu của bài toán 39
    3.1.3. Phương pháp so sánh . 39
    3.1.4. Mô hình và các toán tử cho bài toán cái túi 0-1 đa mục tiêu 39
    3.2. Thuật toán SEAMO2_LG 42
    3.2.1. Chiến lược chọn lọc cá thể của thuật toán SEAMO2 . 42 6
    3.2.2. Đề xuất cải tiến 43
    3.2.3. Kết quả thực nghiệm . 46
    3.3. So sánh với thuật toán SPEA2, NSGA2 49
    KẾT LUẬN . 51
    TÀI LIỆU THAM KHẢO . 52
    Tiếng Việt 52
    Tiếng Anh 52

    7
    Danh mục các ký hiệu và chữ viết tắt

    GA : Genetic Algorithms
    MOGA : Multi-Objective Evolutionary Algorithms
    NSGA
    : Nondominated Sorting in Genetic
    Algorithms
    SEAMO
    : A Simple Evolutionary Algorithm for
    Multi-objective Optimization
    SPEA : Strength Pareto Evolutionary Algorithm ⃗ =(x 1 , ,x n ) : Vector biến quyết định ( ⃗) ( ( ⃗) ( ⃗) ( ⃗)) : Vector hàm mục tiêu
    n u : Số nghiệm trội hơn nghiệm u
    S u : Tập nghiệm trội bởi nghiệm u
    P : Quần thể ban đầu
    F j : Biên chứa các nghiệm không trội thứ j, j
    =1, ,R
    Q : Tập lưu trữ nghiệm không trội qua mỗi
    thế hệ
    P t : Quần thể cha
    Q t : Quần thể con tạo thành t các cá thể trong
    P t
    F j : Biên chứa các nghiện không trội thứ j,
    {j=1, ,R}
    N : Số lượng cá thể trong quần thể P t
    N
    E
    : Số lượng lớn nhất mà tập E có thể chứa
    được các nghiệm không trội
    N
    P
    : Số lượng cá thể trong quần thể/kích thước
    tập P
    k Tham số của mật độ tính toán: k = √ : khoảng cách giữa nghiệm x đếm nghiệm
    lân cận gần nhất thứ k trong tập Et+1
    8
    Danh mục các hình vẽ đồ thị
    Hình 2.1 Mối liên hệ giữa không gian cá thể, vectơ quyết định và mục tiêu . 23
    Hình 2.2: Mô hình tổng quát giải thuật di truyền . 25
    Hình 2.3: Minh họa thuật toán MOGA . 26
    Hình 2.4:Minh họa biên chứa các nghiệm không trội và thứ hạng tương ứng . 31
    Hình 2.6: Minh họa khoảng cách quy tụ quanh nghiệm i . 34
    Hình 2.7: Minh họa các biên và thứ hạng . 34
    Hình 2.8: Minh họa sự quy tụ của các nghiệm quanh một nghiệm 35
    Hình 2.9: Minh họa tính toán độ thích nghi của các cá thể 37
    Hình 2.10: Minh họa cách xóa bỏ các nghiệm nào có δ k
    nhỏ nhất 37
    Hình 3.1: Mô hình mã hóa nhị phân . 40
    Hình 3.2: Mô hình mã hóa hoán vị . 41
    Hình 3.3: So sánh mã hóa nhị phân - mã hóa hoán vị 42
    Hình 3.4: Minh họa không gian tìm kiếm . 44
    Hình 3.5: Thuật toán SEAMO2_LG . 46
    Hình 3.6: So sánh SEAMO2 và SEAMO2_LG – 500 thế hệ . 48
    Hình 3.7: So sánh SEAMO2 và SEAMO2_LG – 1920 thế hệ . 49
    Hình 3.8: So sánh thuật toán SEAMO2_LG với NSGA2, SPEA2 . 50
    9

    Danh mục các bảng


    Bảng 1.1: Ví dụ bài toán cái túi đa mục tiêu 19
    Bảng 3.1: Tỷ lệ % thực hiện của các trường hợp thay thế - SEAMO2 43
    Bảng 3.2: Tỷ lệ % thực hiện của các trường hợp thay thế - SEAMO2_LG . 47
    Bảng 3.3: Độ bao phủ trung bình – 500 thế hệ . 48
    Bảng 3.4: Độ bao phủ trung bình – 1920 thế hệ . 49
    Bảng 3.5: Độ bao phủ trung bình 50
    10

    MỞ ĐẦU
    1. Lý do chọn đề tài
    Trên thực tế, tồn tại rất nhiều bài toán yêu cầu tối ưu hóa đồng thời nhiều
    mục tiêu (thường là cạnh tranh lẫn nhau) ví dụ như: định tuyến các phương tiện
    giao thông để xác định các tuyến đường tối ưu nhằm cung cấp dịch vụ cho một
    tập hợp các khách hàng có thể liên quan đến một số mục tiêu khác nhau: tổng
    quãng đường đi (hoặc thời gian thực hiện), lượng xe sử dụng, độ hài lòng của
    khách hàng (giao hàng trong khoảng thời gian đã thỏa thuận trước), hay việc
    đi chợ mua thức ăn cần đảm bảo sao cho đủ lượng calo cần thiết, chất lượng bữa
    ăn đảm bảo, số tiền chi tiêu không vượt quá giới hạn,
    Giải thuật di truyền (GA) là một trong những mô hình tính toán phổ biến và
    thành công nhất trong lĩnh vực tính toán thông minh. Cùng với các kỹ thuật tính
    toán thông minh khác như tính toán mờ (fuzzy computing), mạng Nơ-ron
    (neural networks), hệ đa tác tử (multi- agent systems), trí tuệ bầy đàn (swarm
    intelligence), giải thuật di truyền ngày càng phát triển, được áp dụng rộng rãi
    trong các lĩnh vực của cuộc sống.
    Đối với bài toán đa mục tiêu, đã có nhiều phương pháp nghiên cứu đề xuất ra
    các thuật toán để giải quyết bài toán như: MOGA, NSGA2, SPEA2, SEAMO2,
    trong đó giải thuật SEAMO2 là hiệu quả hơn cả [4]. Với giải thuật SEAMO2,
    việc thay thế cá thể vào quần thể (thực hiện chiến lược chọn lọc tự nhiên) thì độ
    hội tụ về tập nghiệm tối ưu (với lần chạy ngắn) là chưa cao và khi quần thể
    nghiệm đã đạt ngưỡng tối ưu (với lần chạy dài) thì sẽ mất nhiều thời gian để loại
    cá thể không phù hợp. Chính vì vậy, tác giả mạnh dạn nghiên cứu phương pháp
    cải tiến chiến lược chọn lọc tự nhiên trong giải thuật SEAMO2 để giải các bài
    toán tối ưu đa mục tiêu trong luận văn: “Giải thuật di truyền cho bài toán đa
    mục tiêu”.
    2. Mục đích nghiên cứu
    Mục tiêu của luận văn là nghiên cứu các toán tử trong giải thuật di truyền
    (hay giải thuật tiến hóa nói chung) đặc biệt là toán tử chọn lọc tự nhiên để chọn
    lọc và thay thế các lời giải nhằm tối ưu tập lời giải thu được giúp cho giải thuật
    di truyền giải quyết hiệu quả các bài toán tối ưu đa mục tiêu.
    Mục đích cụ thể của luận văn là sử dụng các toán tử di truyền khác nhau đối
    với thuật toán SEAMO2, ứng dụng cho bài toán cái túi đa mục tiêu, thay đổi
    chiến lược chọn lọc tự nhiên của thuật toán nhằm cải tiến thuật toán. Phương 11
    pháp này sẽ được so sánh với kết quả của các thuật toán tối ưu đa mục tiêu khác
    như: SPEA2, NSGA2, [3,13,16,17].
    Do đó mục tiêu của luận văn là: Nghiên cứu giải thuật di truyền cho bài toán
    đa mục tiêu.
    3. Nhiệm vụ nghiên cứu
    Nghiên cứu các mô hình của giải thuật di truyền có áp dụng các nguyên lý
    tiến hóa và trên cơ sở đó tiếp cận các ý tưởng t thuật toán di truyền để giải bài
    toán cái túi đa mục tiêu như: NSGA2, SPEA2, SEAMO2, cách thức tìm nghiệm
    của các thuật toán này để cải tiến thuật toán di truyền có áp dụng nguyên lý tiến
    hóa SEAMO2.
    4. Đối tượng và phạm vi nghiên cứu
    Tìm hiểu về bài toán tối ưu đa mục tiêu, bài toán cái túi 0-1 đa mục tiêu.
    Tìm hiểu về giải thuật tiến hóa, các mô hình giải thuật tiến hóa có thể áp
    dụng cho bài toán cái túi 0 - 1 đa mục tiêu.
    Xây dựng ứng dụng giải bài toán cái túi 0 - 1 đa mục tiêu với giải thuật
    SEAMO2 và đề xuất phương pháp cải tiến giải thuật.
    So sánh kết quả thực nghiệm của phương pháp đề xuất với các kết quả của
    các thuật toán khác.
    5. Phương pháp nghiên cứu
    Dựa trên tài liệu thu thập t nhiều nguồn (tài liệu, bài báo do giảng viên
    hướng dẫn cung cấp, sách, báo, tạp chí, internet ) tổng hợp, phân tích và trình
    bày lại theo sự hiểu biết của bản thân
    Mở rộng các cách tiếp cận trước đây trên cơ sở phân tích đặc thù giải thuật,
    bài toán cần giải quyết để đưa ra những ý kiến, đề xuất cải tiến hợp lý.
    Ứng dụng những kết quả dựa trên nghiên cứu để xây dựng chương trình thực
    nghiệm, t đó so sánh với kết quả của các thuật toán tối ưu đa mục tiêu khác.

    Xem Thêm: Giải thuật di truyền cho bài toán đa mục tiêu
    Nội dung trên chỉ thể hiện một phần hoặc nhiều phần trích dẫn. Để có thể xem đầy đủ, chi tiết và đúng định dạng tài liệu, bạn vui lòng tải tài liệu. Hy vọng tài liệu Giải thuật di truyền cho bài toán đa mục tiêu sẽ giúp ích cho bạn.
    #1
  7. Đang tải dữ liệu...

    Chia sẻ link hay nhận ngay tiền thưởng
    Vui lòng Tải xuống để xem tài liệu đầy đủ.

    Gửi bình luận

    ♥ Tải tài liệu

social Thư Viện Tài Liệu

Từ khóa được tìm kiếm

Nobody landed on this page from a search engine, yet!

Quyền viết bài

  • Bạn Không thể gửi Chủ đề mới
  • Bạn Không thể Gửi trả lời
  • Bạn Không thể Gửi file đính kèm
  • Bạn Không thể Sửa bài viết của mình
  •  
DMCA.com Protection Status