论文部分内容阅读
在计算机科学、高能物理科学、生物学、超大规模集成电路设计、地球学、电子工程等领域,都存在着大量的优化组合问题,如旅行商问题、图着色问题、设备布局问题,其中的一些问题至今都还没找到有效的多项式时间算法,这些问题已被证明是NPC问题。其中一些问题能被智能优化算法较好的解决,如遗传算法、蚁群算法、模拟退火算法等算法在解决一些复杂问题上都有较好的表现。我们需要研究的就是如何能够提高这些算法效率和寻优效果,其中蚁群算法所具有鲁棒性强、较好的寻优能力、易于并行性、正反馈性、对初始路径不敏感等特点,是其它算法所不能比拟的,所以我们选择蚁群算法来作为研究的对象。
首先通过实验数据分析了蚁群算法的优缺点,并提出了一些改进方法。同时我们发现蚁群算法的寻优过程和量子谐振子系统高能态到低能态的转换过程有一些极为相似的特点。蚁群算法的信息素更新对应到量子谐振子系统中能级的跃迁,它们都是从一种无序的状态逐渐的变为有序的状态。量子谐振子的概率函数的每个波峰可以看做为每轮循环所取得的局部最优解,当粒子到达基态的时候,这时的概率最大,可以看做是蚁群算法中最优解。基态是量子谐振子所必然达到的状态,为算法寻找到最优解提供了理论依据。通过这些对应关系,我们找到了一种新的转移规则和信息素更新规则,并形成了一种基于量子谐振子的蚁群算法。
将量子旋转门、Pauli-Z门以及能级转化公式运用到蚁群算法中,系统的阐述了量子谐振子蚁群算法的原理和过程。通过将量子谐振子蚁群算法和一些经典的算法应用到TSP和函数优化问题上,实验数据表明其性能确实优于这些算法。总结了量子谐振子蚁群算法所具有的一些特点和创新性的发现,提出了一种新的信息素更新规则。最后总结了两点需要在下步工作中改进的方向,展望以后具有普适性的蚁群算法和在根源上理解蚁群算法所具有高效性的原因。