基于粒子群优化的复杂网络社区挖掘

为解决复杂网络社区结构挖掘的优化问题,根据复杂网络拓扑结构的先验知识,提出一种基于离散粒子群优化的社区结构挖掘算法。将粒子的位置和速度定义在离散环境下,设计粒子的更新规则,在不需要事先指定社区个数的前提下自动判断网络的最佳社区个数,给出局部搜索算子,该算子可以帮助算法跳出局部最优解,提高算法的收敛速度和全局寻优能力。实验结果表明,与iMeme-net算法相比,该算法能够准确地挖掘出复杂网络中隐藏的社区结构,且执行速度较快。     

基于多种群遗传算法的复杂网络社区结构发现*

提出了一种基于多种群遗传算法的复杂网络社区结构发现新算法,该算法无须预先知道社区内节点的数量以及任何门限值,同时引入并行遗传算法的思想,进一步提高了算法的运行效率。实验结果表明,与传统算法相比,在无先验信息的条件下,使用该算法对不同规模的网络图Zachary和Dophins网络结构进行验证时,能够以较低的时间复杂度、高效并准确地完成对网络社区的有效划分。     

改进免疫遗传算法的篦冷机二次风温故障诊断

针对遗传算法学习贝叶斯结构时局部寻优能力差的问题, 本文提出一种改进的免疫遗传算法(IIGA)学习贝 叶斯结构. 首先利用最大支撑树与评分函数构建两个初始种群, 然后在种群内部引入改进免疫算子与自动交叉变 异算子, 在种群之间引入改进的联姻策略与师生交流机制, 最后通过迭代搜索到最优贝叶斯结构. 在标准网络中与 遗传算法相比, 提升了遗传算法的局部寻优能力. 利用IIGA算法得到篦冷机水泥熟料换热工艺参数的结构, 并以此 结构为基础进行参数学习与故障推理, 最终得到二次风温的故障诊断模型, 对节约燃煤, 保护环境具有一定实际意 义.     

基于免疫遗传算法的负载均衡策略

针对基于遗传算法的负载均衡策略(SGALB)搜索效率不高、局部寻优性能不佳、容易产生退化的问题,提出一种基于免疫遗传算法的负载均衡策略(IGALB)。通过在SGALB基础上对种群进行亲和力和浓度计算,增加基于浓度的调节概率因子,确保种群的多样性,克服了SGALB早熟收敛;同时在一定条件下引入免疫算子,进行接种疫苗和免疫选择,有效缓解了SGALB的退化现象。仿真实验表明,该算法的寻优能力高于SGALB,并有效提高了集群系统的性能。     

一种基于种群划分及杂交的免疫遗传算法

在免疫遗传算法中引入免疫算子可以提高算法的收敛速率,但也会降低种群个体多样性,不利于搜索.该文提出一种基于种群划分和杂交的免疫遗传算法,通过划分种群并对种群间的最优个体进行杂交来提高算法的速率和稳定性.实验表明,该算法在性能上可提高10%左右,收敛速度快、稳定性好、精确度高.     

一种基于混合遗传的贝叶斯网络分解算法

针对最优贝叶斯网络分解是一个NP-完全问题,提出了一种基于混合遗传贝叶斯网络分解算法PHGA.PHGA算法将进化过程划分为三个不同的阶段,在前期和中期阶段采用较大的种群规模和交叉率,以及较小的群体选择压力,来增强PHGA算法的全局探索能力,避免早熟现象;在后期采用较小的种群规模和交叉率,以及较大的群体选择压力,并引入爬山局部优化算子,以增强群体在进化后期中的局部寻优能力,提高算法的收敛速度.三个标准的贝叶斯网络上的实验表明该算法在最优解方面要优于遗传算法和模拟退火算法.     

基于改进遗传算法的可重构计算任务划分

为实现可重构计算中的软硬件任务自动划分,引入了遗传算法来搜寻最优解。为解决标准遗传算法可能出现种群早熟和种群进化后期收敛速度慢的问题,使用了小生境技术来保护种群中基因的多样性。设计了能够随适应度自动改变的自适应遗传算子（杂交算子和变异算子）。对算法进行了50次随机实验,并对结果进行分析。实验表明,改进后的遗传算法搜寻到全局最优任务划分的概率和搜寻到最优任务划分时的进化代数都要优于标准遗传算法。     

改进的遗传算法求解旅行商问题

提出一种解决旅行商问题的改进遗传算法.在传统遗传算法的基础上,引入贪婪算法进行种群初始化;从遗传进化代数和个体适应函数值两个方面实现遗传参数自适应调节,在加快寻优速度的同时防止寻优陷入局部最优;采用基于贪婪方法的启发式交叉算子优化交叉结果;对交叉前后的种群分别实施精英个体保留策略,保证最优基因结构得以延续.实验结果分析表明,改进的遗传算法可以在种群规模较小的情况下具有更可靠的寻优能力.     

基于混沌免疫遗传优化的粒子滤波重采样

针对粒子滤波算法中粒子多样性退化问题,提出一种利用混沌免疫遗传算法进行重采样的粒子滤波改进方法。该算法利用混沌的局部寻优加快搜索速度;通过免疫原理的浓度计算及加入新的混沌序列来增加种群的多样性,提高全局搜索能力,避免早熟收敛。实验结果表明该方法与基于免疫遗传算法的重采样相比较,具有更好的全局寻优能力和更快的收敛速度。     

生成树编码遗传算法种群退化分析及抑制方法

种群退化现象导致了遗传算法对解空间区域进行重复搜索,从而降低了算法的搜索效率和延缓了算法的收敛,这源于重组算子、采样误差和变异算子的反作用力。通过对生成树编码遗传算法的研究,分析了重组算子的种群退化现象。证明了在解决固定费用运输问题时,重组算子发生种群退化现象的一个充分条件及其概率。针对种群退化现象提出了基于概率选择模型抑制算法（Probabilistic Selection Model Crossover,PSDC）,对其有效性进行了分析证明。与小生境技术相比,它具有可以通过控制选择概率来抑制种群退化和不需要额外的时间开销两大优势,这为遗传算法的设计和应用提供了理论研究依据。     

An improved cuckoo search optimization algorithm with genetic algorithm for community detection in complex networks

This paper improved Cuckoo Search Optimization (CSO) algorithm with a Genetic Algorithm (GA) for community detection in complex networks. CSO algorithm has problems such as premature convergence, delayed convergence, and getting trapped in the local trap. GA has been quite successful in terms of community detection in complex networks to increase exploration and exploitation. GA operators have been used dynamically in order to increase the speed and accuracy of the CSO. The number of populations is dynamically adjusted based on the amount of exploration and exploitation. Modularity objective function (Q) and Normalized Mutual Information (NMI) is used as an optimization function. It was carried out on six types of real complex networks. The proposed algorithm was tested with GA, Artificial Bee Colony (ABC), Grey Wolf Optimizer (GWO), and CSO, with different iterations in modularity and NMI criteria. The results show that in most comparisons, the proposed algorithm has been more successful than the basic comparative algorithms, and it has proven its superiority in terms of modularity and NMI. The proposed algorithm performed an average of 54% better in modularity and 88% in NMI than other algorithms. It performed on average in modularity criteria 84.3%, 58.8%, 33.7% and 38.8%, respectively, compared to CSO, ABS, GWO and GA algorithms, and in terms of NMI index, 188.7%, 39.1%, 52.3% and 73.8%, respectively in CSO, ABS, GWO and GA algorithms performed better.

     

求解多目标社区发现问题的离散化随机漂移粒子群优化算法

针对求解复杂网络的多目标社区发现问题,提出了一种离散化随机漂移粒子群优化（DRDPSO）算法。首先,通过对社区进行随机化编码操作和针对随机漂移算法的离散化操作,来改善局部网络结构并逐渐增强全局模块度值;其次,根据核K均值（KKM）和比例割（RC）两个目标函数来控制网络中的社区规模、缓解模块度分辨率限制;最后,根据多目标求解策略逐步更新Pareto非劣解集,从Pareto非劣解集选取满足需求的目标社区结构。为了验证所提算法的有效性,将DRDPSO算法与其他社区发现算法在三种具有10个不同参数设置的生成网络及三种真实网络上进行对比实验,并采用两个最佳社区评价指标对各算法获得的社区发现结果进行对比分析。实验结果表明,使用DRDPSO算法求解复杂网络的多目标社区发现问题时,获得的社区发现评价指标（归一化互信息和模块度）最高的概率达到95%以上。可见DRDPSO算法在真实网络进行应用能进一步地提高网络社区划分的精确度和鲁棒性。     

A Posteriori Approach for Community Detection

Conventional community detection approaches in complex network are based on the optimization of a priori decision, i.e., a single quality function designed beforehand. This paper proposes a posteriori decision approach for community detection. The approach includes two phases: in the search phase, a special multi-objective evolutionary algorithm is designed to search for a set of tradeoff partitions that reveal the community structure at different scales in one run; in the decision phase, three model selection criteria and the Possibility Matrix method are proposed to aid decision makers to select the preferable solutions through differentiating the set of optimal solutions according to their qualities. The experiments in five synthetic and real social networks illustrate that, in one run, our method is able to obtain many candidate solutions, which effectively avoids the resolution limit existing in priori decision approaches. In addition, our method can discover more authentic and comprehensive community structures than those priori decision approaches.     

Community Detection in Complex Networks

With the rapidly growing evidence that various systems in nature and society can be modeled as complex networks, community detection in networks becomes a hot research topic in physics sociology, computer society, etc. Although this investigation of community structures has motivated many diverse algorithms, most of them are unsuitable when dealing with large networks due to their computational cost. In this paper, we present a faster algorithm ComTector which is more efficient for the community detection in large complex networks based on the nature of overlapping cliques. This algorithm does not require any priori knowledge about the number or the original division of the communities. With respect to practical applications, ComTector is challenging with five different types of networks including the classic Zachary Karate Club, Scientific Collaboration Network South Florida Free Word Association Network, Urban Traffic Network North America Power Grid and the Telecommunication Call Network. Experimental results show that our algorithm can discover meaningful communities that meet both the objective basis and our intuitions.     

基于蚁群优化的二分网络社区挖掘

近年来,网络社区挖掘得到了极大的关注,尤其是针对二分网络的社区挖掘。二分网络社区挖掘对于研究复杂网络有非常重要的理论意义和实用价值。提出了一个基于蚁群优化的二分网络社区挖掘算法。该算法首先将二分网络社区挖掘问题转化成一个优化问题,建立一个可供蚂蚁搜索的图模型。同时,根据顶点的拓扑结构定义启发式信息。每只蚂蚁根据每条路径上的信息素和启发式信息选择路径,构造出一个社区的划分,再用二分模块度去衡量社区划分的优劣。实验结果表明,该算法不但可以较准确地识别二分网络的社区数。而且可以获得高质量的社区划分。     

Dual modularity optimization for detecting overlapping communities in bipartite networks

Many algorithms have been designed to discover community structure in networks. These algorithms are mostly dedicated to detecting disjoint communities. Very few of them are intended to discover overlapping communities, particularly the bipartite networks have hardly been explored for the detection of such communities. In this paper, we describe a new approach which consists in forming overlapping mixed communities in a bipartite network based on dual optimization of modularity. To this end, we propose two algorithms. The first one is an evolutionary algorithm dedicated for global optimization of the Newman’s modularity on the line graph. This algorithm has been tested on well-known real benchmark networks and compared with several other existing methods of community detection in networks. The second one is an algorithm that locally optimizes the graph Mancoridis modularity, and we have adapted to a bipartite graph. Specifically, this second algorithm is applied to the decomposition of vertices, resulting from the evolutionary process, and also characterizes the overlapping communities taking into account their semantic aspect. Our approach requires a priori no knowledge on the number of communities searched in the network. We show its interest on two datasets, namely, a group of synthetic networks and real-world network whose structure is also difficult to understand.     

一种基于云模型的改进型量子遗传算法*

针对量子遗传算法在函数优化中易陷入局部最优和早熟收敛等缺点,采用云模型对其进行改进,采用量子种群基因云对种群进化进行定性控制,采用基于云模型的量子旋转门自适应调整策略进行更新操作,使算法在定性知识的指导下能够自适应控制搜索空间范围,能在较大搜索空间条件下避开局部最优解。典型函数对比实验表明,该算法可以避免陷入局部最优解,能提高全局寻优能力,同时能以更快的速度收敛于全局最优解,优化质量和效率都要优于遗传算法和量子遗传算法。     

一种基于因子图模型的半监督社区发现方法

社区发现是社交网络分析中一个重要的研究方向.当前大部分的研究都聚焦在自动社区发现问题,但是在具有数据缺失或噪声的网络中,自动社区发现算法的性能会随着噪声数据的增加而迅速下降.通过在社区发现中融合先验信息,进行半监督的社区发现,有望为解决上述挑战提供一条可行的途径.本文基于因子图模型,通过融入先验信息到一个统一的概率框架中,提出了一种基于因子图模型的半监督社区发现方法,研究具有用户引导情况下的社交网络社区发现问题.在三个真实的社交网络数据（Zachary社会关系网、海豚社会网和DBLP协作网）上进行实验,证明通过融入先验信息可以有效地提高社区发现的精度,且将我们的方法与一种最新的半监督社区发现方法（半监督Spin-Glass模型）进行对比,在三个数据集中F-measure平均提升了6.34%、16.36%和12.13%.     

离散Jaya算法的复杂网络社区发现

社区结构是复杂网络的重要特性之一, 基于模块度的复杂网络社区发现问题是一个NP难度的组合优化问题, 常用启发式算法求解. 最近出现的Jaya算法是求解连续优化问题的一种简单有效的元启发式方法. 本文在遵循Jaya算法按靠近最好解、远离最差解的方式更新种群个体的基础上, 针对复杂网络社区发现问题给出了Jaya算法离散化的策略, 提出一种复杂网络社区发现的离散Jaya算法. 实验表明, 在几个典型真实网络实例和一类人造网络实例上, 与几个经典算法和元启发式算法相比, 本文算法具有求解精度高、能自动确定社区数目等优点.     

Multi-level learning based memetic algorithm for community detection

Complex network has become an important way to analyze the massive disordered information of complex systems, and its community structure property is indispensable to discover the potential functionality of these systems. The research on uncovering the community structure of networks has attracted great attentions from various fields in recent years. Many community detection approaches have been proposed based on the modularity optimization. Among them, the algorithms which optimize one initial solution to a better one are easy to get into local optima. Moreover, the algorithms which are susceptible to the optimized order are easy to obtain unstable solutions. In addition, the algorithms which simultaneously optimize a population of solutions have high computational complexity, and thus they are difficult to apply to practical problems. To solve the above problems, in this study, we propose a fast memetic algorithm with multi-level learning strategies for community detection by optimizing modularity. The proposed algorithm adopts genetic algorithm to optimize a population of solutions and uses the proposed multi-level learning strategies to accelerate the optimization process. The multi-level learning strategies are devised based on the potential knowledge of the node, community and partition structures of networks, and they work on the network at nodes, communities and network partitions levels, respectively. Extensive experiments on both benchmarks and real-world networks demonstrate that compared with the state-of-the-art community detection algorithms, the proposed algorithm has effective performance on discovering the community structure of networks.