基于分层搜索的蚁群算法及收敛性分析
2016-03-17游晓明
刘 锴 游晓明* 刘 升
1(上海工程技术大学电子电气工程学院 上海 201620)
2(上海工程技术大学管理学院 上海 201620)
基于分层搜索的蚁群算法及收敛性分析
刘锴1游晓明1*刘升2
1(上海工程技术大学电子电气工程学院上海 201620)
2(上海工程技术大学管理学院上海 201620)
摘要针对蚁群算法容易陷入局部最优的问题,提出一种新的解决连续空间优化的蚁群分层搜索算法。该算法将蚁群搜索空间逐层分割,用信息素分布函数给出了基于分层结点的信息素分布方法。定义了适用于连续域的信息素局部更新、全局更新、状态转移规则,其中局部更新算子能够通过选取合适的参数来增加解的多样性。实验结果表明,相比传统算法,该算法全局搜索能力强,求解精度更高。该算法能达到连续域问题的理论最优值,通过下鞅的停时理论证明了算法以概率1收敛。
关键词蚁群算法连续空间优化分层搜索下鞅
ANT COLONY ALGORITHM BASED ON HIERARCHICAL SEARCH AND ITS CONVERGENCE ANALYSIS
Liu Kai1You Xiaoming1*Liu Sheng2
1(College of Electronic and Electrical Engineering,Shanghai University of Engineering Science,Shanghai 201620,China)2(School of Management,Shanghai University of Engineering Science,Shanghai 201620,China)
AbstractFor ant colony algorithm easily falling into local optimum, we proposed a novel ant colony hierarchical search algorithm for solving continuous space optimisation. The algorithm partitions the ant colony search space hierarchically, and presents a hierarchical nodes-based pheromone distribution approach with pheromone distribution function. We defined the rules of pheromone local update, global update and state transition suitable for continuous domains, in which the local update operator could increase the diversity of solutions by selecting the appropriate parameters. Experimental results showed that comparing with traditional ant colony algorithms, the ant colony hierarchical search algorithm had stronger global search capability and higher solution accuracy. It could achieve the theoretical optimum of continuous domains problem. Moreover, by using the stopping theory of submartingale, it was concluded that the algorithm converges with probability 1.
KeywordsAnt colony algorithmContinuous space optimisationHierarchical searchSubmartingale
0引言
意大利学者M.Dorigo等人从蚂蚁觅食行为中受到启发,于1991年首次提出了蚁群算法。常见的蚁群算法模型有AS(ant system)模型、ACS(ant colony system)模型、MMAS(max-min ant system)模型等[1]。目前蚁群算法已成功应用于多种优化问题,如车辆路径[2]、资源调配[3]、机器人路径规划[4,5]等。
虽然这种自适应人工智能技术在组合优化中应用较广泛,求解连续空间优化问题的蚁群算法尚缺乏理论基础,它将搜索周期模拟成个体的进化或觅食过程,将个体对环境的适应能力作为目标函数,总体上将个体的觅食过程或优胜劣汰过程抽象成用较好可行解取代较差可行解的迭代过程。……
