Incorporating Domain Knowledge in Permutation Gene-pool Optimal Mixing Evolutionary Algorithms

Abstract

The Gene-pool Optimal Mixing Evolutionary Algorithm for permutation problems pGOMEA), is a model based evolutionary algorithm (MBEA) capable of learning problem structure by itself. pGOMEA does so by creating a linkage tree from dependencies found in the population. This problem structure is subsequently used to steer the recombination in pGOMEA. Though pGOMEA models the problem structure, problem specific knowledge can still be added to pGOMEA in order to improve its quality. In this thesis report, different forms of incorporating domain knowledge are applied for the permutation flowshop scheduling problem (PFSP), in order to get insight in their ability to improve pGOMEA. In the first part of this thesis, a literature study discusses pGOMEA, the PFSP and its heuristics and the various ways of incorporating domain knowledge in evolutionary algorithms in general. The second part describes the experiments that are performed to test the effectiveness of using domain knowledge in pGOMEA. The experiments show how pGOMEA cannot be improved using simple improvement heuristics like the swap and insertion heuristic. More informed strategies using domain-specific improvement heuristics however are able to boost pGOMEAs performance signifcantly. Unfortunately, the improvement heuristics do not further benefit from knowledge in the linkage tree. Neither does substructural search on its own achieve a significant improvement over standard improvement heuristics. Other experiments show how pGOMEA can be seeded in two ways. Firstly, good solutions can be added to the initial population, leading to a boost in performance. Secondly, the linkage tree can be build using seeded dependency values from domain knowledge, which can improve the quality of the linkage tree in early generations. As a final experiment, we have tested pGOMEA with domain knowledge (hybridized and using population seeding) against state-of-the-art algorithms solving the PFSP. The experiments show that pGOMEA is able to give good results and that pGOMEA can outperform a state-of-the-art algorithm for the PFSP with the total flowtime criterion. The effect of structure in problems does not give pGOMEA a bigger advantage over other algorithms, though we empirically show that pGOMEAs dependency functions perform better than random dependency functions. Within the scope of this thesis, we propose a better way of generating structured PFSP instances in the appendix.