We use cookies to improve your experience with our site.

基于正交方法求解连续优化问题的蚁群搜索算法

Orthogonal Methods Based Ant Colony Search for Solving Continuous Optimization Problems

  • 摘要: 【研究背景和意义】 目前,以蚁群算法为代表的群体智能算法得到越来越多的重视。原因是其以生物的群体行为为研究对象,通过系统仿真,设计出求解各种问题的优化算法。这些算法无论在速度和灵活性上都比传统的确定性算法更适合于求解大规模的优化问题。蚁群算法利用蚂蚁寻找食物时会释放一定量的信息素,而信息素又会随时间蒸发消失的特点,通过设计信息素的释放和蒸发模型,配合启发式信息的使用,使得蚁群算法中的人工蚂蚁通过协作搜索出问题的最优解。蚁群算法最初由M. Dorigo提出,用于求解旅行商(TSP)问题,后来人们把算法进行扩充和改进,应用到诸如车辆调度、车间调度、路由问题等,并取得很好的计算效果。因此,蚁群算法一直都是用于解决离散组合优化问题的算法。然而,蚁群算法在求解连续优化问题上也具有很好的发展前景,本文就是对蚁群算法求解连续问题的研究成果。【研究的内容,研究中采取的方法,手段和新的发现】通过对蚁群算法的研究,本文作者发现,求解连续问题的最大困难在于如何让蚁群中的蚂蚁学到连续空间中的信息,由于不同于TSP问题已经给定有形的路径,连续空间的搜索是无定向的,因此蚂蚁需要高效的方法了解其所处位置周围的状况。本文提出的正交蚁群搜索方法,首先基于正交试验的方法让蚂蚁快速测试周围正交位置上的优劣程度,根据测试的结果获取当前环境的信息,尝试移动到最优的邻近位置;其次自适应调整测试的邻域的范围,让蚂蚁的搜索更具鲁棒性;最后,通过设计新的信息素释放与蒸发的模式,让蚁群中的蚂蚁以更快的速度交换各自的搜索信息,吸引同伴朝最优的区域探索。【研究的创新点和主要贡献】本文与其他学者已经提出的求解连续空间优化问题的蚁群算法的不同之处,在于本文首次提出利用多因素试验中的正交试验法,加强蚂蚁的搜索能力,并提出动态区域的方法,让蚂蚁以更大的自由度试验连续空间中通过正交表产生的测试点。这些思想在同类型的群体智能优化方法中是首创,通过17个连续问题的测试,显示出本文提出的方法既发扬了蚁群的搜索优点,也大大提高了蚁群在连续空间中的搜索能力。此外,本文提出的正交试验和区域的调整方法是一种基础模型,可以容易地扩充到其他类型优化算法中,为进一步的研究提供良好的借鉴。

     

    Abstract: Research into ant colony algorithms for solvingcontinuous optimization problems forms one of the most significant andpromising areas in swarm computation. Although traditional antalgorithms are designed for combinatorial optimization, they have showngreat potential in solving a wide range of optimization problems,including continuous optimization. Aimed at solving continuous problemseffectively, this paper develops a novel ant algorithm termed``continuous orthogonal ant colony'' (COAC), whose pheromone depositmechanisms would enable ants to search for solutions collaborativelyand effectively. By using the orthogonal design method, ants in thefeasible domain can explore their chosen regions rapidly andefficiently. By implementing an ``adaptive regional radius'' method, theproposed algorithm can reduce the probability of being trapped in localoptima and therefore enhance the global search capability and accuracy.An elitist strategy is also employed to reserve the most valuablepoints. The performance of the COAC is compared with two other antalgorithms for continuous optimization --- API and CACO by testingseventeen functions in the continuous domain. The results demonstratethat the proposed COAC algorithm outperforms the others.

     

/

返回文章
返回