基于动态候选列表对蚁群算法的改进及其应用

Improved ant colony algorithm based on dynamic candidate list and application

鉴于基本蚁群算法存在收敛速度慢、易陷于局部最优的问题,笔者提出了一种改进蚁群算法模型。首先,引入动态候选列表,蚂蚁选择路径时只考虑贪婪值达到一定标准的路径,并自适应调整候选列表长度,以此提高了算法求解速度;其次,引入信息熵的概念,基于信息熵的变化在求解过程中对启发式参数动态调整,以适应算法不同时期蚂蚁在路径选择时的特点。实例仿真表明,改进算法无论在求解速度,还是在求解质量上都取得了较好的效果。

There exist such problems as slow convergence and easy partial optimum with the basic ant colony algorithm, to tackle this, the present paper proposes an improved ant colony algorithm. First, dynamic candidate list （DCL） is introduced. In the route construction, candidate routes, whose？fitness value surpasses some criterion, will be put into DCL and the dynamic candidate strategy is adopted to quicken the convergence speed. Second, by using the population＇s entropy to evaluate the evolution state, the algorithm dynamically adjusts the heuristic parameter based on entropy , ？adapting to？different searching stages. The simulation results verify the validity of the improved algorithm.