欧氏Steiner最小树问题,即在欧氏平面上连接给定原点的最小树长问题,是组合优化中的一个NP难题。难计算是该问题的固有属性,因此目前尚无有效算法对其进行精确求解。但此问题在实际中却有广泛应用,因而寻找其实际而有效的启发式算法就显得颇为重要。近年来,新出现的智能优化算法,如模拟退火算法、遗传算法、禁忌搜索法、人工神经网络法、蚂蚁算法、微粒群算法等,以其独特的优点和机制,引起了国内外学者的广泛重视并掀起了该领域的研究热潮。因此,除研究传统意义上的启发式算法外,本文重点讨论了智能优化算法。传统的启发式算法是建立在对问题有全面清晰的认识基础上,本文的插入算法和递增优化算法也不例外。它们根据欧氏Steiner最小树的性质设计而出,试验结果表明它们具有良好的性能,但也存在着一定的缺陷。转而采用遗传算法、模拟退火算法和蚂蚁算法来求解此问题。遗传算法是一种高度并行、随机和自适应的优化算法,其将问题的求解表示成“染色体”的适者生存过程,从而求得最优解或满意解;模拟退火算法是基于Monte Carlo迭代求解的一种随机寻优算法,其出发点是基于物理学中固体物质的退火过程与组合优化问题之间的相似性;新近出现的蚂蚁算法是一种模仿生物世界中蚂蚁觅食行为的仿生类算法,用蚁群在搜索食物源过程中所体现出来的寻优能力来解决优化问题。本文的具体内容包括:第一章提出了本文的选题背景、研究内容和研究意义。第二章介绍了各种Steiner树问题,重点阐述欧氏Steiner最小树。第三章给出了本文用到的算法工具,包括领域函数、局部搜索、最小生成树等。详细阐述了插入算法和递增优化算法的实现过程,并对问题实例进行测试,依据测试结果对两者进行比较。稍候引出智能优化算法,并进行简要介绍。第四、五、六章分别详述遗传算法、模拟退火算法和蚂蚁算法的有关情况,包括发展历史、原理、流程、构成要素、特征、优缺点等方面,最终给出三种算法的具体实现过程。第七章主要讨论了采用遗传算法、模拟退火算法和蚂蚁算法对不同规模的问题实例进行测试,从运行时间、计算结果值大小和计算结果值稳定性三方面来比较算法的性能。最后还对智能优化算法和传统算法进行比较。第八章对本文内容进行总结,简要评价上述算法,并提出改进的方法。上述5种算法在微机上予以实现。测试所得结果大多优于最小生成树,表现了良好的性能。因欧氏Steiner最小树问题本身所固有的难解特性,其理论和解决方法还没有完全发展成熟,有待进一步研究。