Ant Colony Optimization in Stationary and Dynamic Environments
Ant Colony Optimization in Stationary and Dynamic Environments
复制标题
DOI：
--
复制
发表时间：
2013-05
期刊：
影响因子：
--
通讯作者：
Michalis Mavrovouniotis
中科院分区：
文献类型：
--
作者：
Michalis Mavrovouniotis
蚁群优化（ACO）元启发式算法的灵感来自于真实的蚁群的觅食行为。与其他元算法类似，蚁群算法也存在停滞行为，所有的蚂蚁从早期阶段就构建了相同的解决方案。结果，解的质量可能会下降，因为人口可能会陷入局部最优。在这篇论文中，我们提出了一种新的方法，称为直接通信（DC）计划，帮助ACO算法摆脱局部最优，如果他们陷入困境。两个布线问题的实验结果表明，DC方案是有效的。通常，研究者关注的问题都是静态环境下的问题。在过去的十年中，有越来越多的兴趣，应用自然启发的元分析在动态环境中的优化问题。通常，动态优化问题（DOP）使用进化算法来解决。在这篇论文中，我们将几种新颖的蚁群优化算法应用于两种路由选择问题。所提出的蚁群优化算法与移民计划，其中移民蚂蚁产生，随机或使用以前的环境（S）的知识，并取代当前人口中的其他蚂蚁。实验结果表明，在不同的动态情况下，所提出的算法都有较好的性能，并且总体上优于其他同类蚁群算法。现有的DOP基准生成器是针对二进制编码的组合问题开发的。由于路由问题通常是排列编码的组合问题，在实验中使用的动态环境中使用一种新的基准生成器，将静态问题的实例转换为动态的。特定的动态基准生成器改变了问题的适应度景观，这导致最优值在每次环境变化中都会发生变化。此外，在本文中，提出了另一种基准生成器，它将种群移动到适应度景观中的另一个位置，而不是修改它。通过这种方式，最优解是已知的，人们可以看到在环境变化期间算法的性能有多接近最优解。
The ant colony optimization (ACO) metaheuristic is inspired by the foraging behaviour of real ant colonies. Similarly with other metaheuristics, ACO suffers from stagnation behaviour, where all ants construct the same solution from early stages. In result, the solution quality may be degraded because the population may get trapped on local optima. In this thesis, we propose a novel approach, called direct communication (DC) scheme, that helps ACO algorithms to escape from a local optimum if they get trapped. The experimental results on two routing problems showed that the DC scheme is effective. Usually, researchers are focused on problems in which they have static environment. In the last decade, there is a growing interest to apply nature-inspired metaheuristics in optimization problems with dynamic environments. Usually, dynamic optimization problems (DOPs) are addressed using evolutionary algorithms. In this thesis, we apply several novel ACO algorithms in two routing DOPs. The proposed ACO algorithms are integrated with immigrants schemes in which immigrant ants are generated, either randomly or with the use of knowledge from previous environment(s), and replace other ants in the current population. The experimental results showed that each proposed algorithm performs better in different dynamic cases, and that they have better performance than other peer ACO algorithms in general. The existing benchmark generators for DOPs are developed for binary-encoded combinatorial problems. Since routing problems are usually permutation-encoded combinatorial problems, the dynamic environments used in the experiments are generated using a novel benchmark generator that converts a static problem instance to a dynamic one. The specific dynamic benchmark generator changes the fitness landscape of the problem, which causes the optimum to change in every environmental change. Furthermore in this thesis, another benchmark generator is proposed which moves the population to another location in the fitness landscape, instead of modifying it. In this way, the optimum is known and one can see how close to the optimum an algorithm performs during the environmental changes.