权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

排列域中概率模型构建遗传算法的研究

基本信息

批准号：
16500143
负责人：
TSUTSUI Shigeyoshi
金额：
$ 1.79万
依托单位：
Hannan University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2004
资助国家：
日本
起止时间：
2004 至 2006
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-16500143/
关键词：
evolutionary computation probabilistic model-building genetic algorithm EDA PMBGA permutation representation problem EHBSA ACO genetic algorithm NHBSA QAP TSP GA 順序表現メタヒューリスティック集合フェロモンシステム Ant Colony Optimization 集合フェロモン

项目摘要

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

遗传算法（GAs）是一种广泛应用于实际问题的鲁棒黑箱优化技术。遗传算法应该很好地工作的问题，可以分解成有限的困难的子问题。然而，固定的，独立于问题的变异算子往往无法有效地利用所选择的高质量的解决方案的人口。最有前途的研究方向之一是将新候选解的生成视为一个学习问题，并使用所选解的概率模型来生成新的候选解。分布估计算法（Estimation of Distribution Algorithms，简称EDA）或概率建模遗传算法（Probabilistic Model-building Genetic Algorithms，简称PMBGAs）是一种基于概率模型的遗传算法，主要研究离散或连续变量的定长向量表示的优化问题。豪夫 ...更多信息呃，对于很多组合问题来说，排列提供了一个更自然的候选解的表示。尽管EDAs在定长离散和连续向量领域取得了巨大的成功，但关于置换问题的EDAs的研究却很少。在这项研究中，我们集中精力在置换问题的EDA。一个有前途的方法来学习和采样置换问题的概率模型是使用边缘直方图模型。该算法被称为基于边缘直方图的采样算法（EHBSA）。在EHBSA中，新的解决方案是通过合并当前种群中存在的部分解决方案，并根据当前种群的边缘直方图模型新生成的部分解决方案。EHBSA在旅行商问题（TSP）的几个基准实例上运行良好。尽管如此，所提出的方法并不限于TSP，像大多数其他TSP求解器和专门的变分算子。因此，这种方法提供了一个很有前途的方向，可以制定在固定长度的排列域的其他问题的解决方案，流水车间调度是这样一个problem. EHBSA的基本采样算法是非常相似的采样算法，用于蚁群优化（ACO），这种方法可以应用到ACO。因此，我们也对蚁群算法进行了广泛的研究，并取得了可喜的成果。少