A STUDY ON BROBABILISTIC MODEL-BUILDING GENETIC ALGORITHM IN PERMUTATION DOMAINS

点击翻译按钮获取中文摘要

Genetic Algorithms (GAs) are widely used as robust black-box optimization techniques applicable across a broad range of real-world problems. GAs should work well for problems that can be decomposed into sub-problems of bounded difficulty. However, fixed, problem-independent variation operators are often incapable of effective exploitation of the selected population of high-quality solutions. One of the most promising research directions is to look at the generation of new candidate solutions as a learning problem, and use a probabilistic model of selected solutions to generate the new ones. The algorithms based on learning and sampling a probabilistic model of promising solutions to generate new candidate solutions are called estimation of distribution algorithms (EDAs) or probabilistic model-building genetic algorithms (PMBGAs).Most work on EDAs focuses on optimization problems where candidate solutions are represented by fixed-length vectors of discrete or continuous variables. Howev … More er, for many combinatorial problems permutations provide a much more natural representation for candidate solutions. Despite the great success of EDAs in the domain of fixed-length discrete and continuous vectors, only few studies can be found on EDAs for permutation problems. In this research, we focused our effort on EDAs for permutation problems. One promising approach to learning and sampling probabilistic models for permutation problems is to use edge histogram models. This algorithm is called the edge histogram based sampling algorithm (EHBSA). In EHBSA, new solutions are created by combining partial solutions which exist in the current population, and partial solutions newly generated based on the edge histogram model of the current population. The EHBSA worked well on several benchmark instances of the traveling salesman problem (TSP). Nonetheless, the methods proposed are not limited to TSP, like most other TSP solvers and specialized variation operators. As a result, this approach provided a promising direction for solutions of other problems that can be formulated within the domain of fixed-length permutations ; flow shop scheduling is an example of such a problem.The basic sampling algorithms in EHBSAs are very similar to the sampling algorithms that are used in ant colony optimization (ACO) and this method can be applied to ACO. Thus, we also studied ACO extensively and got promising results. Less