【摘 要】
：
膜进化算法（Membrane Evolutionary Algorithm,MEA）是受到生物细胞结构和行为启发而提出的一种进化算法,被广泛应用于各类NP难问题的求解上。最长圈问题（Longest Cycle Problem,LCP）是图论中经典的NP难问题之一,不仅在图论研究中有重要的意义,也和现实世界的复杂网络应用密切相关。过往的LCP研究大多通过特殊图的理论性质来寻找最长圈,难以直接运用到现
论文部分内容阅读
膜进化算法（Membrane Evolutionary Algorithm,MEA）是受到生物细胞结构和行为启发而提出的一种进化算法,被广泛应用于各类NP难问题的求解上。最长圈问题（Longest Cycle Problem,LCP）是图论中经典的NP难问题之一,不仅在图论研究中有重要的意义,也和现实世界的复杂网络应用密切相关。过往的LCP研究大多通过特殊图的理论性质来寻找最长圈,难以直接运用到现实世界复杂网络的应用中。近年来,虽然已有一些适用于复杂网络的LCP求解算法被提出,但在中大规模实例上的求解效率较低,无法满足需求。基于此,本文研究了用以缩小问题规模的图约简策略和用以高效扩展圈的路径扰动策略。并设计了基于蚁群算法（Ant Colony Optimization,ACO）的LCP快速求解算法ANTHPDLS（Ant-based Heuristic with Path Disturbance Local Search）。在ANTH-PDLS的基础上,设计了结合膜进化算法的LCP求解算法MEALCP（Membrane Evolutionary Algorithm for Longest Cycle Problem）。实验表明,ANTH-PDLS和MEALCP在求解效率和质量上表现良好。本文主要工作和成果包括:（1）提出了两个图约简的策略:短边删除策略和割分量删除策略。实验表明,图约简策略能够使原实例的顶点规模平均减少61%,边规模平均减少16.6%;提出了一种路径扰动的局部搜索策略PD-LS（Path Disturbance with Local Search）,实验表明该策略能够更高效地扩展圈进而发现LCP更好的解。（2）设计并实现了一个基于蚁群算法的LCP快速求解算法ANTH-PDLS。该算法使用图约简策略和路径扰动策略PD-LS提高了LCP求解的效率。在21个现实世界的复杂网络实例上的实验表明,ANTH-PDLS的平均求解时间花费只有目前优秀算法的15.5%,而且解的精度基本相同。（3）针对于中大规模的LCP实例求解,设计并实现了基于膜进化算法的LCP求解算法MEALCP。该算法利用膜结构重新组织蚂蚁,并使用膜进化算子加快算法的收敛速度,进一步提升了解的精度和稳定性。在现实世界的6个较难实例上发现了2个较ANTH-PDLS更好的最优解。本文研究了用于求解LCP的进化算法。ANTH-PDLS能够快速得到最长圈,使中大规模复杂网络上的LCP求解成为可能。MEALCP结合膜进化算法思想进一步提升了解的质量,并为LCP的求解提供了新的思路。
其他文献
磁耦合无线电能传输（Wireless Power Transfer,WPT）系统通过电磁场或电磁波载能/传能原理,结合谐振技术可以在一个较远的距离内为用电设备无线供电,具有安全无接触的优点,耦合机构是WPT的关键。然而,耦合机构的传能性能对于能量接收（拾取）机构的位置姿态都较为敏感,偏差较大时就会导致输出功率大幅下降。对于一些需要在空间中移动或转动的用电设备的无线供电,传统的耦合机构模式对能量传输
流量仪表标定装置是计量部门和仪器生产厂商进行检定测试的重要设备。在多批量、高精度的标定场景下,任何设备老化及零部件的微小改变都有可能影响标定精度。因此,实现标定装置运行状态的实时监测、健康程度的快速评估,对提升标定装置稳定性、可靠性、企业生产效率及产品质量有重要意义。本文对某仪表公司的液体流量仪表标定装置进行调研分析,针对运行状态监测不全面、设备健康程度掌握不及时等问题,展开了对流量仪表标定装置监
二维矩形条装箱问题（Two-dimensional strip packing problem,简称2DSPP）是一个NP难的组合优化问题,它在现实世界的许多领域都有应用,比如在货物的装载、内存的管理、玻璃的切割加工等有实际需求。目前,求解2DSPP的启发式算法是以改进初始解的改进启发式算法为主。这类算法中,能有效扩大搜素范围的启发式算法不仅能够改进解的质量,同时也能提高求解的效率。膜计算是受生物
近年来,第五代移动通讯技术（5G）的快速普及和边缘基站加速建设,将移动边缘计算（MEC）从概念逐渐落地为助力新兴移动应用、创新人机交互方式、加速物联网大数据治理、完善工业生态的重要基石。移动边缘计算是由云计算演进出的一种新的计算框架,相比于传统云计算,移动边缘计算将计算任务负载从远程云转移到了更靠近用户的网络边缘节点,利用无线接入网络就近为移动终端设备提供各种所需的服务与云端计算功能,从而创造出一
随着信息科学技术与传统工业技术的相互融合,涡扇发动机朝着复杂化、大型化发展。然而,传统维护方式存在着维护过度与维护欠缺等问题,难以胜任涡扇发动机的维护需求。因此,故障预测与健康管理（Prognostics and Health Management,PHM）应运而生。剩余可用寿命（Remaining Useful Life,RUL）预测是PHM的关键技术之一,若能准确预测设备RUL,据此作出合理的
随着边缘计算技术的快速发展,网络边缘接入用户和设备数量急剧上升,海量隐私和敏感数据产生在边缘设备上,边缘计算环境下频繁的数据交换过程带来了大量的数据安全传输需求。然而,资源受限的边缘设备无法满足传统加密技术的资源需求,如何在资源受限设备上保证数据传输的安全性已成为了一个难题。轻量级加密技术使用实现成本较低的密码结构以及加密算法,利用少量资源开销为资源受限设备提供安全性,其具有低存储需求、低执行时间
医学图像分割的主要任务是将图像中的目标器官组织准确提取出来,为诊断或临床治疗提供辅助参考。近年来,基于深度学习的图像分割算法因其卓越的性能,而被广泛用于医学图像分割领域。此外,得益于相关理论以及硬件的快速发展,学者们提出了基于2D-CNN、3D-CNN以及Transformer的多种分割模型,这些模型在较大的器官组织（肺部、肝脏、心脏等）分割中取得了不错的效果。然而,医学图像分割中仍存在很多难点:
属性图可以承载丰富的信息,在社交网络、推荐系统、电子商务等领域应用广泛。对于这类网络平台中产生的大量半结构化数据,使用属性图进行建模分析是最理想的方式。同时,由于网络平台上的图数据规模庞大,常使用随机游走采样对这类图数据进行统计估计。受到“均方误差可以分解成估计值的偏差与方差之和”的启发,开发了一种算法框架以减小图上随机游走采样估计的均方误差。该算法框架可以将各种随机游走采样算法作为基础,对其采样
害虫是造成农作物减产和破环园林生态的主要因素之一。准确而快速的害虫识别是害虫防控过程中的关键所在。传统害虫识别主要依赖农林业专家的经验,而这一过程效率低且成本高昂。近年来,随着深度学习技术在计算机视觉领域取得快速进展,基于卷积神经网络（Convolutional Neural Network,CNN）的害虫图像识别方法被广泛研究与应用,并取得显著成效。然而,野外环境下的害虫图像识别由于受到细粒度、
电子鼻系统模拟了生物的嗅觉系统。它通过传感器技术和人工智能技术实现了对气体的快速检测和分析。然而在实际应用中,电子鼻系统会出现传感器时间漂移和多系统板间差异问题。这些问题会导致电子鼻系统前后采集的数据分布发生变化,使得训练好的模型无法有效地对后续数据进行分析,从而限制了电子鼻的应用。近年来,基于子空间投影的漂移抑制方法发展迅速,但性能需要进一步提高。本论文的研究目的便是提出高性能的基于子空间投影的