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

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

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

【學(xué)位級別】：碩士

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


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

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



本文編號：3427030