蚁群算法解决CSAHLP问题时的修正因子的研究

Research on Correction Factor in Resolving CSAHLP Through ACO

优化蚁群算法是一种基于种群的模拟进化算法,其高效的仿生过程在各类组合问题中有了广泛的应用。CSAHLP经常被用来描述物流在大范围运输时所产生的问题。在CSAHLP问题中,枢流点和节点都是未知参变量,这使得此问题归类于典型的NP问题。ACO作为高效解决NP问题的算法之一,在CSAHLP上有了越来越多的研究应用。但是,蚁群算法也有其自身缺点,受容量约束的条件作为外部约束使得蚁群有时无法得出正确的解。文中详细讨论了蚁群产生非可行解的原因及其处理方法,并通过实验证明方法的有效性。

ACO is a simulation evolutionary algorithm based on population. Its effective bionics process has been widely used in various combinatorial problems. CSAHLP is often used to describe those problems produced when logistics happen in a large scale. In the CASHLP,both hub and nodes are unknown parameters,which classifies it to the typical NP. As one of the effective algorithms to solve NP ,ACO has more and more research application in CSAHLP. However,ACO has its own weakness,too. With the conditions restricted by the capacity as the external constraints, ACO can not produce the correct solution sometimes. It gives a detailed analysis of the reasons for producing this infeasible solution and proper solutions to this problem and proves that the method is effective by experiment.