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

遗传算法(GAs)作为稳健的黑盒优化技术被广泛应用于各种实际问题。对于可以分解为具有有限难度的子问题的问题，GAS应该工作得很好。然而，固定的、与问题无关的变异算子往往不能有效地利用选定的高质量解决方案的群体。最有前途的研究方向之一是将生成新的候选解视为一个学习问题，并使用选定解的概率模型来生成新的候选解。基于概率分布估计算法(EDAS)或概率建模遗传算法(PMBGA)，通过学习和采样有希望解的概率模型来生成新的候选解。Howev…更重要的是，对于许多组合问题，排列为候选解提供了一种更自然的表示。尽管EDAS在定长离散和连续向量领域取得了巨大的成功，但对于置换问题的EDAS研究却很少。在这项研究中，我们将精力集中在解决置换问题的EDAS问题上。学习和采样置换问题的概率模型的一个很有前途的方法是使用边缘直方图模型。该算法称为基于边缘直方图的采样算法(EHBSA)。在EHBSA中，通过将当前种群中存在的部分解与基于当前种群的边缘直方图模型新生成的部分解相结合来创建新的解。EHBSA在旅行商问题(TSP)的几个基准实例上运行良好。然而，所提出的方法并不局限于TSP，就像大多数其他TSP求解器和专门的变异算子一样。因此，该方法为解决定长排列领域内的其他问题提供了一个很有前途的方向，Flow shop调度就是这样一个例子。EHBSA中的基本采样算法与蚁群算法中使用的采样算法非常相似，该方法可以应用于蚁群算法。因此，我们也对蚁群算法进行了广泛的研究，并取得了可喜的成果。较少

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