论文部分内容阅读
系统全局最短路径是非线性组合优化中的经典问题之一，在实际中有着广泛的应用，最小Steiner树问题是全局最短路径研究的理论基础。因此研究最小Steiner树的全局优化算法具有重要的理论意义和广泛的应用价值。由于最小Steiner树问题已被证明是NP-hard问题，除非P=NP，否则Steiner树问题不存在多项式时间算法，因此寻找合适的智能优化算法是求解此问题的有效途径。本文以物理可视化实验为依托，采用实验→算法→实验→工程应用的技术研究路线，对可视化实验装置、实验过程以及实验结果进行详细的分析、研究，探索固定点的分布形状对构造最小Steiner树的影响，以及Steiner虚设点的位置、数目与给定端点的位置以及分布形状之间的关系，将最小Steiner树问题分为两种情况进行求解。当固定点集为凸集时，我们直接用Melzak法构造最小Steiner树；当固定点为非凸集时，通过改进的遗传算法对它进行求解。对于存在障碍物的Steiner树问题，本文也进行了一些实验，并分析了障碍物的形状和位置与Steiner虚设点的关系。本文设计的遗传算法采用试探选择算法来选取初始种群，并且构造出满足自适应过程的交叉算子。通过采用试探选择算法来选取初始种群，使得遗传算法的收敛速度大大提高。而交叉算子满足自适应过程，有利于遗传算法得到自身最适合的交叉概率，提高算法的精度和收敛速度。同时通过遗传算法搜索得到的最优解直接以Steiner虚设点的形式存在，弥补了国际SteinLib测试数据库中目标函数未计入Steiner虚设点的不足。本文通过简单的图形实例验证了本算法的可行性，并通过几个具体实例，如某高校教职工住宅区供热管道规划实例，五省一市选址实例，输电网线路规划实例等，对遗传算法与可视化实验得到的结果进行对比分析，证明了算法的实用性与有效性。大量的实例证明本算法能够与可视化实验配套使用来解决工程实际问题，并为下一步的实验方法的改进和完善奠定基础。