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

    TIẾN SĨ Các thuật toán gần đúng giải bài toán cây khung với chi phí định tuyến nhỏ nhất

    D
    dream dream Đang Ngoại tuyến (18524 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. Các thuật toán gần đúng giải bài toán cây khung với chi phí định tuyến nhỏ nhất

    LUẬN ÁN TIẾN SĨ
    NĂM 2015
    MỤC LỤC

    MỞ ĐẦU 1
    Chương 1. TỔNG QUAN . 5
    1.1.BÀI TOÁN MRCST 5
    1.1.1.Một số định nghĩa 5
    1.1.2.Thuật toán tính chi phí định tuyến của cây khung 7
    1.1.3.Đánh giá chi phí định tuyến của cây khung 9
    1.2.ỨNG DỤNG 11
    1.2.1.Ứng dụng của bài toán MRCST trong lĩnh vực thiết kế mạng 11
    1.2.2.Ứng dụng của bài toán MRCST trong lĩnh vực tin sinh học 11
    1.3.CÁC NGHIÊN CỨU LIÊN QUAN BÀI TOÁN MRCST . 12
    1.3.1.Thuật toán giải đúng 12
    1.3.2.Thuật toán gần đúng cận tỉ lệ 13
    1.3.3.Thuật toán heuristic . 16
    1.3.4.Thuật toán metaheuristic . 18
    1.3.5.Danh sách các thuật toán giải bài toán MRCST hiện biết 25
    1.4.TIÊU CHÍ ĐÁNH GIÁ THUẬT TOÁN . 26
    1.5.HỆ THỐNG DỮ LIỆU THỰC NGHIỆM CHUẨN . 29
    1.5.1.Đồ thị đầy đủ Euclid 30
    1.5.2.Đồ thị đầy đủ ngẫu nhiên 30
    1.5.1.Đồ thị thưa . 31
    1.6.KHẢO SÁT THỰC NGHIỆM CÁC THUẬT TOÁN GIẢI BÀI TOÁN MRCST . 32
    1.6.1.Cấu hình máy tính thực nghiệm các thuật toán . 32
    1.6.2.Chất lượng lời giải . 32
    1.6.3.Thời gian tính 34
    1.6.4.Hình vẽ minh họa so sánh chất lượng của các thuật toán hiện biết . 36
    1.7.KẾT LUẬN CHƯƠNG 1 37
    Chương 2. THUẬT TOÁN TÌM KIẾM LEO ĐỒI 39
    2.1.CÂY KHUNG LÂN CẬN . 39
    2.2.THUẬT TOÁN HCSRI . 40
    2.2.1.Ý tưởng thuật toán HCSRI 40
    2.2.2.Sơ đồ thuật toán HCSRI 41
    2.2.3.Độ phức tạp của thuật toán HCSRI . 42
    2.3.THUẬT TOÁN HCSIR . 42
    2.3.1.Ý tưởng thuật toán HCSIR 42
    2.3.2.Sơ đồ thuật toán HCSIR 43
    2.3.3.Độ phức tạp của thuật toán HCSIR . 44
    2.4.THỰC NGHIỆM VÀ ĐÁNH GIÁ 45
    2.4.1.Môi trường thực nghiệm 45
    2.4.2.Tham số thực nghiệm 45
    2.4.3.Chất lượng lời giải . 45
    2.4.4.Thời gian tính 51
    2.4.5.Hình vẽ minh họa chất lượng HCSRI, HCSIR với các thuật toán khác 53
    2.5.KẾT LUẬN CHƯƠNG 2 55
    Chương 3. THUẬT TOÁN DI TRUYỀN 56
    3.1.THUẬT TOÁN GST . 56
    3.1.1.Tạo quần thể ban đầu . 56
    3.1.2.Phép lai 57
    3.1.3.Phép đột biến . 60
    3.1.4.Phép chọn lọc 62
    3.1.5.Sơ đồ thuật toán GST . 63
    3.1.6.Độ phức tạp của thuật toán GST 64
    3.2.THỰC NGHIỆM VÀ ĐÁNH GIÁ 64
    3.2.1.Môi trường thực nghiệm 64
    3.2.2.Tham số thực nghiệm 65
    3.2.3.Chất lượng lời giải . 65
    3.2.4.Thời gian tính 69
    3.2.5.Hình vẽ minh họa chất lượng thuật toán GST với các thuật toán khác . 70
    3.3.KẾT LUẬN CHƯƠNG 3 73
    Chương 4. THUẬT TOÁN TÌM KIẾM TABU . 74
    4.1.THUẬT TOÁN TST 74
    4.1.1.Ý tưởng và một số khái niệm của thuật toán tìm kiếm Tabu 74
    4.1.2.Thuật toán TST tìm bước chuyển tốt nhất . 75
    4.1.3.Thuật toán TST cập nhật danh sách Tabu 76
    4.1.4.Chiến lược đa dạng hóa lời giải của thuật toán TST 76
    4.1.5.Sơ đồ của thuật toán TST . 77
    4.1.6.Độ phức tạp của thuật toán TST 79
    4.2.THỰC NGHIỆM VÀ ĐÁNH GIÁ 79
    4.2.1.Môi trường thực nghiệm 79
    4.2.2.Tham số thực nghiệm 79
    4.2.3.Chất lượng lời giải . 80
    4.2.4.Thời gian tính 84
    4.2.5.Hình vẽ minh họa chất lượng thuật toán TST với các thuật toán khác 86
    4.3.KẾT LUẬN CHƯƠNG 4 88
    Chương 5. THUẬT TOÁN BẦY ONG . 89
    5.1.THUẬT TOÁN BẦY ONG CƠ BẢN 89
    5.2.THUẬT TOÁN BST 91
    5.2.1.Tạo quần thể ban đầu . 91
    5.2.2.Phân nhóm các cá thể 92
    5.2.3.Tìm cây khung lân cận 93
    5.2.4.Chiến lược đa dạng hóa lời giải . 95
    5.2.5.Sơ đồ của thuật toán BST . 96
    5.2.6.Độ phức tạp của thuật toán BST 98
    5.3.THỰC NGHIỆM VÀ ĐÁNH GIÁ 98
    5.3.1.Môi trường thực nghiệm 98
    5.3.2.Tham số thực nghiệm 98
    5.3.3.Chất lượng lời giải . 99
    5.3.4.Thời gian tính 104
    5.3.5.Hình vẽ minh họa chất lượng thuật toán BST với các thuật toán khác 106
    5.3.6.Hình vẽ minh họa độ lệch chuẩn của các thuật toán . 109
    5.4.KẾT LUẬN CHƯƠNG 5 111
    KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN 112
    KẾT LUẬN . 112
    HƯỚNG PHÁT TRIỂN 113 DANH MỤC CÁC CÔNG TRÌNH ĐÃ CÔNG BỐ CỦA LUẬN ÁN . 114
    TÀI LIỆU THAM KHẢO 115
    PHỤ LỤC. KẾT QUẢ THỰC NGHIỆM TỪ CÁC CÔNG TRÌNH LIÊN QUAN . 119


    MỞ ĐẦU
    Tối ưu hóa mạng liên quan đến nhiều lĩnh vực như toán ứng dụng, khoa học máy tính, vận trù
    học, kỹ thuật, mạng truyền thông, Nhiều bài toán thực tế trong lĩnh vực mạng truyền thông,
    chẳng hạn như bài toán cây khung truyền thông tối ưu (Optimal Communication Spanning
    Trees - OCST), bài toán cây Steiner nhỏ nhất (Steiner Minimal Trees - SMT), bài toán cây khung
    nhỏ nhất với đường kính bị chặn (Bounded Diameter Minimum Spanning Trees - BDMST) [20],
    bài toán cây khung với chi phí định tuyến nhỏ nhất (Minimum Routing Cost Spanning Trees -
    MRCST) đã được chứng minh thuộc lớp bài toán NP-khó hoặc NP-đầy đủ.
    MRCST là một bài toán tối ưu đồ thị nổi tiếng; bài toán này lần đầu tiên được giới thiệu bởi T.
    C. Hu vào năm 1974 qua bài báo “Optimum communication spanning trees” [37]. Bài toán
    MRCST được xem là một trường hợp đặc biệt của bài toán cây khung truyền thông tối ưu khi
    mà lượng cầu truyền thông giữa tất cả mọi cặp đỉnh của bài toán OCST đều bằng nhau [9,10,37].
    Mô hình toán học của bài toán MRCST có thể phát biểu như sau: Cho G là một đồ thị vô hướng
    liên thông có chi phí định tuyến không âm trên cạnh. Giả sử T là một cây khung của G. Chi phí
    định tuyến cho mỗi cặp đỉnh trên T được định nghĩa là tổng các chi phí định tuyến trên các cạnh
    của đường đi đơn nối chúng trên T và chi phí định tuyến của T được định nghĩa là tổng của tất
    cả các chi phí định tuyến giữa mọi cặp đỉnh của T. Bài toán MRCST đặt ra là tìm một cây khung
    có chi phí định tuyến nhỏ nhất trong số tất cả các cây khung của G [10]. Bài toán MRCST đã



    được chứng minh thuộc lớp bài toán NP-khó [10,13,37].
    Bài toán MRCST có nhiều ứng dụng trong lĩnh vực thiết kế mạng truyền thông
    [7,10,15,27,31,33], chẳng hạn bài toán xây dựng các hệ thống mạng nhằm tối ưu chi phí đường
    đi trung bình giữa các nút mạng; đặc biệt là ở các mạng ngang hàng – khi mà các nút có xác
    suất truyền tin và độ ưu tiên là như nhau. Bài toán MRCST cũng tìm được những ứng dụng quan
    trọng trong lĩnh vực tin sinh học [10,41].
    Việc đề xuất thuật toán dạng metaheuristic giải bài toán MRCST có ý nghĩa quan trọng, một
    mặt, nhằm giải quyết những bài toán ứng dụng thực tiễn vừa nêu; mặt khác, còn là cơ sở để giải
    quyết những bài toán cây khung tối ưu dạng NP-khó khác trên đồ thị. Bài toán MRCST đã thu hút được sự quan tâm nghiên cứu của nhiều nhà khoa học trong hơn bốn
    mươi năm qua. Hiện nay đã có hàng loạt thuật toán giải bài toán MRCST được đề xuất và có thể
    chia chúng làm các hướng tiếp cận sau: Hướng thứ nhất là các thuật toán tìm lời giải đúng.
    Hướng tiếp cận giải đúng phát triển trên thuật toán nhánh cận được đề xuất bởi R. Dionne và M.
    Florian vào năm 1979 [30], thuật toán nhánh cận kết hợp với phương pháp sinh cột được đề xuất
    bởi Matteo Fischetti, Giuseppe Lancia, Paolo Serafini vào năm 2002 [24]. Các thuật toán giải
    đúng chỉ có thể giải được bài toán MRCST đối với đồ thị có không quá 40 đỉnh và do đó tính
    ứng dụng thực tiễn của nó không cao [1,24,30]. Hướng thứ hai là các thuật toán tìm lời giải gần
    đúng cận tỉ lệ, như thuật toán WONG được đề xuất bởi Richard T. Wong vào năm 1980 [31],
    thuật toán GENERAL STAR được đề xuất bởi Bang Ye Wu và Kun-Mao Chao vào năm 1999
    [8], sơ đồ xấp xỉ thời gian đa thức – PTAS được đề xuất bởi Bang Ye Wu và Kun-Mao Chao
    vào năm 2004 [10], thuật toán xấp xỉ xử lý song song được đề xuất bởi Ching-Lueh Chang và
    Yuh-Dauh Lyuu vào năm 2008 [12], thuật toán gần đúng cận tỉ lệ được đề xuất bởi Alexandra
    Hochuli, Stephan Holzer, Roger Wattenhofer năm 2014 [4]. Ưu điểm của các thuật toán này là
    có sự đảm bảo về mặt toán học theo nghĩa lời giải tìm được gần đúng một cận tỉ lệ α nào đó so
    với lời giải tối ưu. Hướng thứ ba là các thuật toán heuristic, bao gồm thuật toán ADD được đề
    xuất bởi Vic Grout vào năm 2005 [41], thuật toán CAMPOS được đề xuất bởi Rui Campos và
    Manuel Ricardo vào năm 2008 [33]. Các thuật toán ADD, CAMPOS có độ phức tạp thời gian
    tính tốt nhất trong số tất cả các thuật toán giải bài toán MRCST hiện biết. Thuật toán CAMPOS
    tìm được lời giải với chất lượng tốt hơn so với các thuật toán WONG ở một số loại đồ thị cụ thể.
    Hướng thứ tư là các thuật toán metaheuristic. Hướng tiếp cận metaheuristic phát triển trên các
    thuật toán di truyền, thuật toán tìm kiếm địa phương và thuật toán bầy ong. Hướng tiếp cận này
    bao gồm thuật toán di truyền mã hóa dạng cạnh – ESCGA được đề xuất bởi Bryant A. Julstrom
    vào năm 2005 [11], thuật toán di truyền mã hóa dạng dãy số Prüfer – BCGA được đề xuất bởi
    Bryant A. Julstrom vào năm 2005 [11], thuật toán tìm kiếm leo đồi ngẫu nhiên – SHC được đề
    xuất bởi Bryant A. Julstrom vào năm 2005 [11], thuật toán tìm kiếm địa phương có sử dụng
    chiến lược đa dạng hóa lời giải – PBLS được đề xuất bởi Alok Singh vào năm 2008 [5], thuật
    toán tìm kiếm địa phương– CYCLELS được đề xuất bởi Steffen Wolf và Peter Merz vào năm
    2010 [36], thuật toán bầy ong (Artificial Bee Colony - PABC) [6] và thuật toán bầy ong kết hợp
    với thuật toán tìm kiếm địa phương (ABC+LS) cùng được đề xuất bởi Alok Singh vào năm 2011
    [6] – hai thuật toán này được phát triển dựa vào sơ đồ của thuật toán Artificial Bee Colony
    (ABC) [16,17]. Các thuật toán metaheuristic này cho lời giải với chất lượng tốt hơn các thuật
    toán giải gần đúng còn lại. Tuy nhiên, hiệu quả của các thuật toán metaheuristic chủ yếu được
    đánh giá thông qua thực nghiệm mà chưa chứng minh được về mặt toán học. Thời gian tính các thuật toán metaheuristic là chậm hơn rất nhiều so với các thuật toán WONG [10,31], ADD [41],
    CAMPOS [33].
    Mục đích của luận án là phát triển một số thuật toán gần đúng dạng metaheuristic giải bài toán
    MRCST cho chất lượng lời giải tốt hơn so với các thuật toán có cùng cỡ thời gian tính hoặc đòi
    hỏi thời gian tính ít hơn khi so sánh với các thuật toán có chất lượng lời giải tương đương hoặc
    đưa ra lời giải tốt nhất mới cho một số bộ dữ liệu thực nghiệm chuẩn.

    Xem Thêm: Các thuật toán gần đúng giải bài toán cây khung với chi phí định tuyến nhỏ nhất
    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 Các thuật toán gần đúng giải bài toán cây khung với chi phí định tuyến nhỏ nhất 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ài liệu mới

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