復雜網(wǎng)絡可以用于描述同一系統(tǒng)內不同個體之間、個體與整體之間以及不同整體之間的關系。復雜網(wǎng)絡的最大獨立集問題（MISP）和最小頂點覆蓋問題（MVCP）是兩個典型的集合優(yōu)化問題,且都是NP-hard問題。最大獨立集問題指的是求解一個（或若干個）網(wǎng)絡節(jié)點構成的集合,使得所求得的集合規(guī)模最大、且集合內的節(jié)點相互之間沒有連邊。該優(yōu)化問題得到整個網(wǎng)絡中個體之間互不影響的最大的個體集合。最小頂點覆蓋問題的目的在于找出給定復雜網(wǎng)絡的規(guī)模最小的節(jié)點集合,并保證網(wǎng)絡中任意一條邊至少有一個頂點在所選的節(jié)點集合中�，F(xiàn)實生活中的許多問題可以歸結為這兩種問題,比如高校教師排課系統(tǒng)、監(jiān)控設備安置問題、線路規(guī)劃問題、網(wǎng)絡優(yōu)化問題等。本文首先研究復雜網(wǎng)絡的演化博弈動力學行為,然后創(chuàng)新性地結合網(wǎng)絡的博弈規(guī)律,分別對局部搜索和全局搜索方法進行了研究、改進與實驗,提出了基于囚徒困境博弈求解最大獨立集問題的迭代局部搜索算法（IGLS）和基于雪堆博弈和遺傳機制求解最小頂點覆蓋問題的進化算法（GMA-MVC）。最后,通過實驗,驗證了本文所提出的IGLS算法和GMA-MVC算法的優(yōu)勢。本文的主要內容如下:1.研究復雜網(wǎng)絡上的節(jié)點博弈... 

【文章來源】：西安電子科技大學陜西省 211工程院校 教育部直屬院校

【文章頁數(shù)】：104 頁

【學位級別】：碩士

【文章目錄】：
摘要
ABSTRACT
符號對照表
縮略語對照表
第一章 緒論
    1.1 復雜網(wǎng)絡概述
    1.2 復雜網(wǎng)絡研究現(xiàn)狀
    1.3 復雜網(wǎng)絡研究意義
    1.4 復雜網(wǎng)絡的集合優(yōu)化問題
    1.5 本文結構安排
第二章 問題描述及相關算法簡介
    2.1 最大獨立集問題
    2.2 最小頂點覆蓋問題
    2.3 最大獨立集的求解方法
        2.3.1 基于2-improvement的迭代局部搜索算法
        2.3.2 基于交換的禁忌局部搜索算法
        2.3.3 求解最大團的局部搜索算法
    2.4 最小頂點覆蓋的求解方法
        2.4.1 求解最小頂點覆蓋的遺傳算法
        2.4.2 混合遺傳算法
        2.4.3 基于粗糙集理論的算法
        2.4.4 基于邊權值的局部搜索算法
    2.5 算法綜合對比分析
    2.6 本章小結
第三章 復雜網(wǎng)絡上的演化博弈
    3.1 演化博弈
        3.1.1 囚徒困境博弈
        3.1.2 雪堆博弈
        3.1.3 納什均衡
        3.1.4 博弈策略更新方法
    3.2 復雜網(wǎng)絡的同步演化博弈
        3.2.1 同步演化博弈
        3.2.2 基于同步演化博弈求解最小頂點覆蓋問題
    3.3 復雜網(wǎng)絡的異步演化博弈
        3.3.1 異步演化博弈
        3.3.2 異步囚徒困境博弈與最大獨立集
        3.3.3 異步雪堆博弈與最小頂點覆蓋
    3.4 實驗結果與分析
    3.5 本章小結
第四章 基于PDG求解最大獨立集的迭代局部搜索算法
    4.1 基于囚徒困境博弈的局部搜索機制GLS
        4.1.1 基于囚徒困境博弈求得極大獨立集
        4.1.2 基于囚徒困境博弈的局部搜索
        4.1.3 GLS的博弈順序
        4.1.4 基于博弈的擾動方法
    4.2 基于囚徒困境博弈的迭代局部搜索算法IGLS
        4.2.1 弱擾動機制
        4.2.2 基于模擬退火思想的解集更新方法
        4.2.3 算法整體思路
        4.2.4 時間復雜度分析
        4.2.5 算法可行性分析
    4.3 實驗結果與分析
        4.3.1 實驗網(wǎng)絡簡介
        4.3.2 不同算法搜索合法解的性能對比
        4.3.3 局部搜索性能對比
        4.3.4 綜合對比實驗
        4.3.5 實驗結果分析與統(tǒng)計檢驗
    4.4 本章小結
第五章 基于雪堆博弈求解最小頂點覆蓋的自然進化算法
    5.1 個體進化
        5.1.1 基于雪堆博弈求解合法解
        5.1.2 基于雪堆博弈的局部搜索
        5.1.3 個體進化總體步驟
    5.2 帶有個體進化的自然進化算法GMA-MVC
        5.2.1 基于節(jié)點度的初始化方法
        5.2.2 GMA-MVC算法元素
        5.2.3 GMA-MVC算法總體步驟
        5.2.4 時間復雜度分析
        5.2.5 算法可行性分析
    5.3 實驗結果與分析
        5.3.1 實驗網(wǎng)絡簡介
        5.3.2 初始化性能分析
        5.3.3 個體進化性能分析
        5.3.4 基于演化博弈的不同算法對比
        5.3.5 綜合對比實驗
        5.3.6 實驗結果分析與統(tǒng)計檢驗
        5.3.7 算法參數(shù)分析
    5.4 本章小結
第六章 總結與展望
    6.1 總結
    6.2 展望
參考文獻
致謝
作者簡介


【參考文獻】：
期刊論文
[1]復雜網(wǎng)絡:認知世界的科學新方法[J]. 黃欣榮.  江西財經(jīng)大學學報. 2012(01)
[2]CPU與GPU上幾種矩陣乘法的比較與分析[J]. 劉進鋒,郭雷.  計算機工程與應用. 2011(19)
[3]復雜網(wǎng)絡及其在國內研究進展的綜述[J]. 劉建香.  系統(tǒng)科學學報. 2009(04)
[4]復雜網(wǎng)絡上的博弈[J]. 吳枝喜,榮智海,王文旭.  力學進展. 2008(06)
[5]小世界網(wǎng)絡與無標度網(wǎng)絡的社區(qū)結構研究[J]. 杜海峰,李樹茁,W.F.Marcus,悅中山,楊緒松.  物理學報. 2007(12)
[6]復雜網(wǎng)絡上動力系統(tǒng)同步的研究進展[J]. 趙明,汪秉宏,蔣品群,周濤.  物理學進展. 2005(03)
[7]復雜網(wǎng)絡理論及其應用研究概述[J]. 劉濤,陳忠,陳曉榮.  系統(tǒng)工程. 2005(06)
[8]BA模型的三種擴展[J]. 陳禹,宗驍,郝杰,許彥.  系統(tǒng)工程學報. 2005(02)
[9]從統(tǒng)計物理學看復雜網(wǎng)絡研究[J]. 吳金閃,狄增如.  物理學進展. 2004(01)
[10]網(wǎng)絡“建筑學”[J]. 朱涵,王欣然,朱建陽.  物理. 2003(06)

碩士論文
[1]基于雪堆博弈的復雜網(wǎng)絡最小節(jié)點覆蓋[D]. 皎魁.西安電子科技大學 2015



本文編號：3427030