Statistical Analysis of Various Hybridization of Evolutionary Algorithm for Traveling Salesman Problem

摘要

The paper focus on statistical analysis of separate, combined and partial hybridization performance of evolutionary algorithm and neighborhood searcher with a goal to find an intelligent way of hybridization of evolutionary algorithms. On the Traveling Salesman Problem (TSP) we measured the influence of hybridization a 2-opt heuristic-based local searcher into the evolutionary algorithm. Evolutionary Algorithm gives a diversification, while 2-opt improves intensification. The TSP is nowadays already solved for small instances rather efflciently by exact algorithms (e.g concorde) and by local search heuristics as LKH by Helsgaun. Nevertheless, the paper shows statistical analysis that intelligently hybridized algorithm combines good qualities from the both applied components and outperforms each individual method and suggest what level and type of hybridization is best for a given problem to make them intelligent. In tests we applied hybridization at various percentages (level) of evolutionary algorithm iterations. The main contribution of the paper is to show statistical analysis of hybridized evolutionary algorithms. For that purpose we used well known statistical tools. Since the evaluation scores were not normally distributed, the nonparametric Kruskal-Wallis Test (KWT) was used instead of the standard one-way ANOVA. The differences were considered to be statistically significant in cases where the estimated p-values of statistical tests were less than or equal to 0.05. The analysis with KWT showed that there exist statistically significant differences in place of hybridization. The analysis revealed significant differences in all levels of the hybridization. However, intensifying the level of hybridization further increased the p-value of the KWT, which means that the place of hybridization becomes of a less importance when the level of hybridization increases.