本文選題：進化算法 + 塊模型��； 參考：《西安電子科技大學》2014年碩士論文

【摘要】：本文以進化算法為基礎,先后研究了基于圖分割的塊模型問題和基于分解的多目標進化在社區(qū)檢測上的問題。論文主要進行了以下三個工作:1.研究進化算法求解塊模型問題。算法過程包括利用提取完全子圖的思想進行種群初始化,采用沖突交叉算子產生子代,再采用修復操作優(yōu)化子代。最后,經過反復迭代,算法逐漸收斂,目標函數(shù)值達到最大。通過在四組不同來源的網絡上分別用進化算法EA和分組遺傳算法GGA做塊模型分割,證明了本章提出了基于進化算法EA的塊模型方法在處理大規(guī)模網絡上具有明顯的優(yōu)勢,尤其在節(jié)點數(shù)較多和邊密度較大的網絡上。2.提出了一種基于模塊度的符號網絡多目標社區(qū)檢測方法。文中針對符號網絡的特性,首先定義了兩個目標函數(shù),然后采用分解的方法使得種群不斷進化,其中遺傳操作過程包括采用提取完全子圖的方法對種群進行初始化,單路交叉算子產生子代和基于正鄰居的變異操作,從而使個體不斷向最優(yōu)解收斂。實驗中通過分析符號網絡呈現(xiàn)的Pareto前端驗證了本章提出的兩個多目標函數(shù)在符號網絡社區(qū)檢測上是可行的,通過與對比算法的實驗結果比較、分析,證明了本章提出的基于模塊的MOEA/D在呈現(xiàn)網絡不同層次結構和提取小社區(qū)方向上具有明顯的優(yōu)勢。3.提出了一種基于密度型的多目標社區(qū)檢測算法。此算法在是第二個工作的基礎上,重新定義了兩個目標函數(shù),使得此算法不僅可以檢測符號網絡的社區(qū)結構還可以檢測無符號網絡的社區(qū)結構。文中詳細描述了目標函數(shù)的具體定義和其動機來源,遺傳操作同樣包括提取完全子圖的方法、單路交叉算子和基于鄰居的變異。通過分別對符號網絡和無符號網絡做社區(qū)檢測,驗證了本章提出的兩個多目標函數(shù)在社區(qū)檢測上是可行的,通過與基于模塊度MOEA/D及其他算法的實驗結果比較,證明了本章提出的基于密度型的MOEA/D是一種更全面更高效的社區(qū)檢測方法。
[Abstract]:In this paper, based on evolutionary algorithm, the block model problem based on graph segmentation and the problem of multi-objective evolution based on decomposition in community detection are studied successively. The thesis mainly carries on the following three work: 1. The evolutionary algorithm is studied to solve the block model problem. The algorithm includes initializing the population using the idea of extracting the complete subgraph, using the collision crossover operator to generate the offspring, and then using the repair operation to optimize the offspring. Finally, after repeated iteration, the algorithm converges gradually and the value of the objective function reaches the maximum. By using evolutionary algorithm EA and packet genetic algorithm GGA as block model segmentation in four groups of networks from different sources, it is proved that the block model method based on evolutionary algorithm EA has obvious advantages in dealing with large-scale networks. Especially in the network with more nodes and more edge density. In this paper, a multi-target community detection method based on modularity is proposed. In this paper, two objective functions are defined for the characteristics of symbolic networks, and then the decomposition method is used to make the population evolve continuously. The genetic operation process includes the initialization of the population by extracting the complete subgraph. The single path crossover operator generates offspring and mutation operations based on positive neighbors, which makes the individual converge to the optimal solution. In the experiment, the Pareto front-end presented by symbolic network is analyzed to verify the feasibility of the two multi-objective functions proposed in this chapter in community detection of symbolic networks. It is proved that MOEA / D proposed in this chapter has obvious advantages in presenting different network hierarchies and extracting small communities. A density-based multi-objective community detection algorithm is proposed. This algorithm redefines two objective functions on the basis of the second work so that the algorithm can not only detect the community structure of the symbolic network but also the community structure of the unsigned network. In this paper, the definition of objective function and its motive source are described in detail. The genetic operation also includes the method of extracting complete subgraph, single path crossover operator and neighbor based mutation. The two multiobjective functions proposed in this chapter are proved to be feasible in community detection by doing community detection for symbolic network and unsigned network, respectively. The results are compared with the experimental results based on Modular MOEA-D and other algorithms. It is proved that the density-based MOEA / D is a more comprehensive and efficient method for community detection.
【學位授予單位】：西安電子科技大學
【學位級別】：碩士
【學位授予年份】：2014
【分類號】：O157.5;TP393.09

【相似文獻】

相關期刊論文 前10條

1 張暉;任俊義;;民營化進程、企業(yè)目標函數(shù)選擇與轉軌效率[J];財經研究;2006年03期

2 王西靜;;會議籌備優(yōu)化模型探析[J];長治學院學報;2010年05期

3 龐拴琴;如何建立求解最值應用問題的目標函數(shù)[J];高等數(shù)學研究;1998年03期

4 郝稚傳;;兩類線性約束的目標函數(shù)為齊次正系數(shù)的規(guī)劃問題的解[J];運籌學雜志;1987年02期

5 袁志發(fā);常智杰;;模糊數(shù)學在農業(yè)上的應用[J];陜西農業(yè)科學;1987年05期

6 劉昌勝,鄔行彥,俞俊棠;最小成本為目標函數(shù)時最優(yōu)循環(huán)量的確定[J];生物工程學報;1996年03期

7 鄧霞;董曉華;薄會娟;;目標函數(shù)對HEC-HMS模型參數(shù)率定的影響研究[J];水電能源科學;2010年08期

8 李習彬;隨機目標優(yōu)選的幾個基本問題[J];北京工業(yè)學院學報;1984年02期

9 李國麗;吳宜燦;宋鋼;王世芳;;目標函數(shù)設置對放療逆向計劃多目標優(yōu)化過程的影響[J];原子核物理評論;2006年02期

10 D.g.Witde,C.S.Beighteel;優(yōu)選法理論——收縮法[J];科技譯報;1972年01期

相關會議論文 前3條

1 李國麗;吳宜燦;;放療逆向計劃中采用不同目標函數(shù)時多目標優(yōu)化過程的比較研究[A];第二屆全國反應堆物理與核材料學術研討會論文集[C];2005年

2 史金平;劉長標;;單目標群組決策的目標函數(shù)研究[A];1996年中國控制會議論文集[C];1996年

3 胡健行;郭繼如;李幼銘;;計算非線性目標函數(shù)的子空間方法[A];1993年中國地球物理學會第九屆學術年會論文集[C];1993年

相關重要報紙文章 前1條

1 高文;工業(yè)結構設計的新手段[N];計算機世界;2008年

相關博士學位論文 前1條

1 鐘雪靈;帶強制工期非正則目標函數(shù)的排序問題研究[D];暨南大學;2010年

相關碩士學位論文 前7條

1 王佳利;塊模型和復雜網絡社區(qū)檢測[D];西安電子科技大學;2014年

2 楊夏勰;基于目標函數(shù)的誤差估算及網格自適應處理[D];南京航空航天大學;2013年

3 馬翠玲;面向地面搜索的雙目標函數(shù)規(guī)劃模型的研究與實踐[D];電子科技大學;2011年

4 袁淑娟;最優(yōu)化合成目標函數(shù)的加速梯度算法[D];浙江大學;2013年

5 蘇丹;甘油代謝目標函數(shù)推斷問題的計算方法研究[D];渤海大學;2014年

6 江珊;帶有權重偏好的進化多目標算法[D];廣東工業(yè)大學;2015年

7 林明春;圖的布局中若干問題的研究[D];福州大學;2011年

，

本文編號：2100812