Search

Many real-world optimization problems are subject to dynamic environments that require an optimization algorithm to track the optimum during changes. Ant colony optimization (ACO) algorithms have proved to be powerful methods to address combinatorial dynamic optimization problems (DOPs), once they are enhanced properly. The integration of ACO algorithms with immigrants schemes showed promising performance on different DOPs. The principle of immigrants schemes is to introduce new solutions (called immigrants) and replace a small portion in the current population. In this paper, immigrants schemes are specifically designed for the dynamic vehicle routing problem (DVRP). Three immigrants schemes are investigated: random, elitism- and memory-based. Their difference relies on the way immigrants are generated, e.g., in random immigrants they are generated randomly whereas in elitism- and memory-based the best solution from previous environments is retrieved as the base to generate immigrants. Random immigrants aim to maintain the population diversity in order to avoid premature convergence. Elitism- and memory-based immigrants aim to maintain the population diversity and transfer knowledge from previous environments, simultaneously, to enhance the adaptation capabilities. The experiments are based on a series of systematically constructed DVRP test cases, generated from a general dynamic benchmark generator, to compare and benchmark the proposed ACO algorithms integrated with immigrants schemes with other peer ACO algorithms. Sensitivity analysis regarding some key parameters of the proposed algorithms is also carried out. The experimental results show that the performance of ACO algorithms depends on the properties of DVRPs and that immigrants schemes improve the performance of ACO in tackling DVRPs. [ABSTRACT FROM AUTHOR]

Abstract: Traditional Genetic Algorithms (GAs) mating schemes select individuals for crossover independently of their genotypic or phenotypic similarities. In Nature, this behavior is known as random mating. However, non-random protocols, in which individuals mate according to their kinship or likeness, are more common in natural species. Previous studies indicate that when applied to GAs, dissortative mating – a type of non-random mating in which individuals are chosen according to their similarities – may improve their performance (on both speed and reliability). Dissortative mating maintains genetic diversity at a higher level during the run, a fact that is frequently observed as a possible cause of dissortative GAs’ ability to escape local optima. Dynamic optimization demands a special attention when designing and tuning a GA, since diversity plays an even more crucial role than it does when tackling static ones. This paper investigates the behavior of the Adaptive Dissortative Mating GA (ADMGA) in dynamic problems and compares it to GAs based on random immigrants. ADMGA selects parents according to their Hamming distance, via a self-adjustable threshold value. The method, by keeping population diversity during the run, provides an effective means to deal with dynamic problems. Tests conducted with dynamic trap functions and dynamic versions of Road Royal and knapsack problems indicate that ADMGA is able to outperform other GAs on a wide range of tests, being particularly effective when the frequency of changes is low. Specifically, ADMGA outperforms two state-of-the-art algorithms on many dynamic scenarios. In addition, and unlike preceding dissortative mating GAs and other evolutionary techniques for dynamic optimization, ADMGA self-regulates the intensity of the mating restrictions and does not increase the set of parameters in GAs, thus being easier to tune. [Copyright &y& Elsevier]