基于复杂网络理论的遗传算法分析与设计

发布时间：2020-08-15 09:08

【摘要】：现实生活中各个领域都存在多种多样的优化问题,模拟生物进化过程的遗传算法,由于其鲁棒性高、通用性强、简单易行等优点,已经广泛应用于生产调度、图像处理、机器学习等领域。然而标准遗传算法存在易陷入局部最优、求解精度低、收敛速度慢等缺陷。作为仿生算法的遗传算法个体间的相互关系可视为一个复杂网络,所以可以从复杂网络的角度设计遗传算法的种群结构。种群拓扑结构可以调整个体间信息的传播,因而对遗传算法的种群多样性和收敛性能具有重要影响。因此,本文围绕基于复杂网络理论的遗传算法分析与设计展开研究。首先,遗传算法的进化过程可以建模为复杂网络模型,现有研究称之为信息流网络。本文对信息流网络建模进行改进并提出了更精准、简捷的网络非均匀性分析方法。在信息流网络建模过程中,对被选择但是没有经过交叉、变异的个体进行加边,得到的信息流网络模型可以更完整地描述遗传算法中优势基因信息的传递过程。另外,采用复杂网络理论中的网络结构熵刻画信息流网络的非均匀性。网络结构熵反映了信息流网络的有序程度,即网络的非均匀性。相对于网络幂律度分布曲线中拟合的标度指数,依据网络中节点数目和节点连接度直接计算的网络结构熵可以更加精准简捷的度量信息流网络的非均匀性。其次,为了改善遗传算法种群多样性和收敛性能,本文设计了一种基于自组织动态网络的遗传算法。为了有效地评价节点的重要性,综合考虑节点的目标函数值在邻居节点中的排名以及邻居节点数,给出了一种新的指数型网络节点适应度定义,可避免节点适应度为0造成的无效评价。此外,还提出了双新、单新和选删三种拓扑更新规则,使得遗传算法的种群结构随遗传算法的进化而动态演化,有效地改善了遗传算法在收敛性能方面的表现。最后,将基于自组织动态网络的遗传算法与标准遗传算法和小世界遗传算法进行对比,典型优化函数测试结果表明,基于自组织动态网络的遗传算法在维持种群多样性和收敛性能方面均有优秀的表现。
【学位授予单位】：南京邮电大学
【学位级别】：硕士
【学位授予年份】：2019
【分类号】：O157.5;TP18
【图文】：

流程图,遗传算法,流程图,无向网络

遗传算法流程图

示意图,示意图,节点,网络模型

图 2.5 无标度网络示意图无标度网络模型的两个重要性质为增长性和优先连接性，一方面网络中节点会不断增加，另一方面，新加入的节点会与连接边较多的节点建立新的连边。BA 网络在构造初期是一个较小的网络，此网络模型拥有一定数量的节点，迭代一次后向网络中添加一个新的节点，将新节点与原有的m 个节点之间添加新的连接边。因此，可以计算出 BA 网络的连接度分布如下：32 ( 1)( )( 1)( 2)m mP k kk k k （2.10）由平均场理论计算出 BA 网络的聚类系数为[12]：2 2 2( 1) 1 1 (ln )( ) ln( )4( 1) 1m m m tC tm m m t （2.11）2.3本章小结

流程图,信息流动,信息流网络,示意图

图 3.2 种群迭代流程图图 3.3 解信息迭代流程图满足终止条件后输出遗传算法信息流网络，然后对信息流网络计算网络结构熵。代过程中子代与父代之间会有信息流动，图 3.4 具体描述了这一过程。比如个体 1 00111 是由父代 10111 和 00011 交叉产生。图中箭头的方向表示父代与子代之间方向。初始个体10111 00011 11000 00110 01100 10101变异交叉10010 0011100010 0011101100 1010110011 0011100010 0011101100 10101加边加边Y变异种群 D终止条件ojian结束N

【相似文献】