Study on the Distributed Probabilistic Model-Building Genetic Algorithms for Real-Parameter Optimization

实参数优化的分布式概率模型构建遗传算法研究

• 批准号: 13680469
• 负责人: TSUTSUI Shigeyoshi
• 金额: $ 1.98万
• 依托单位: HANNAN UNIVERSITY
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2001
• 资助国家: 日本
• 起止时间: 2001 至 2003
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-13680469/
• 关键词: Genetic Algorithm; Probabilistic Model-Building GA; Real-Coded GA; Real-Parameter Optimization; EDA; Distributed GA; GA with Permutation Representation; PMBGA; 正規分布; 順序表現問題; Ant Colony Optimization; ヒストグラム; 確立モデルGA; 関数最適化

Recently, there has been a growing interest in developing evolutionary algorithms based on probabilistic models. In this scheme, the offspring population is generated according to the estimated probabilistic model of the parent population instead of using traditional recombination and mutation operators. The model is expected to reflect the problem structure, and as a result it is expected that this approach provides more effective mixing capability than recombination operators in traditional GAs. These algorithms are called probabilistic model-building genetic algorithms(PMBGAs) or estimation of distribution algorithms(EDAs). In a PMBGA, better individuals are selected from an initially randomly generated population like in standard GAs. Then, the probability distribution of the selected set of individuals is estimated and new individuals are generated according to this estimate, forming candidate solutions for the next generation. The process is repeated until the termination conditions are satisfied.In this research, a distributed PMBGA model was studied. The results showed that the proposed model had much better performance than traditional GAs in solving real-parameter optimization problems. In this research, an approach of PMBGAs in permutation domains, such as TSP, scheduling problems, vehicle routing problems, was studied, as well. The proposed approach, which is called edge histogram based sampling algorithm(EHBSA), also showed much better performance than traditional GAs in various problems of permutation domains.

最近，人们对基于概率模型的进化算法越来越感兴趣。在该方案中，根据亲本群体的估计概率模型产生后代群体，而不是使用传统的重组和突变算子。期望该模型能够反映问题的结构，因此期望该方法比传统气体中的重组算子提供更有效的混合能力。这些算法被称为概率模型构建遗传算法（PMBGAs）或分布估计算法（EDAs）。在PMBGA中，像在标准ga中一样，从最初随机生成的种群中选择更好的个体。然后，估计所选个体集的概率分布，并根据该估计生成新的个体，形成下一代的候选解。重复该过程，直到满足终止条件。本文研究了一种分布式PMBGA模型。结果表明，该模型在求解实参数优化问题时比传统的遗传算法具有更好的性能。本文还研究了置换域的pmbga问题，如TSP问题、调度问题、车辆路径问题。该方法被称为基于边缘直方图的采样算法（EHBSA），在各种排列域问题上也表现出比传统GAs更好的性能。

项目成果

筒井 茂義: "Solving Flow Shop Scheduling Problems with Probabilistic Model-Building Genetic Algorithms using Edge Histograms"Proceeding of the 4th Asia-Pacific Conference on Simulated Evolution And Learning(SEAL02). (2002)

Shigeyoshi Tsutsui：“使用边缘直方图通过概率模型构建遗传算法解决流程车间调度问题”第四届亚太模拟进化与学习会议论文集 (SEAL02) (2002)。

筒井 茂義: "エッジヒストグラムを用いる順序表現向き確率モデルGAの提案"人工知能学会論文誌. 18・4. 173-182 (2003)

Shigeyoshi Tsutsui：“使用边缘直方图进行有序表示的概率模型 GA”日本人工智能学会杂志 18・4（2003 年）。

筒井 茂義: "Using Edge Histogram Models to Solve Flow Shop scheduling Prolblems with Probabilistic Model-Building Genetic Algorithms(in Recent Advances in Simulated Evolution and Learning)"World Scientific(印刷中). 20 (2004)

Shigeyoshi Tsutsui：“使用边缘直方图模型通过概率模型构建遗传算法解决流水车间调度问题（模拟进化和学习的最新进展）”World Scientific（出版中）20（2004 年）。

Tsutsui, S.: "Probabilistic Model-Building Genetic Algorithms in Permutation Representation Domain using Edge Histogram"Proc. of the 7th International Conference on Parallel Problem from Nature (PPSN VII). (学会発表). 224-233 (2002)

Tsutsui, S.：“使用边缘直方图在排列表示域中构建概率模型”Proc. 第七届自然并行问题国际会议 (PPSN VII)（会议演示文稿）。

Tsutsui, S., Pelikan, M., Goldberg, D.E.: "Solving Sequence Problems by Building and Sampling Edge Histograms"Illi GAL Report No.2002024 University of Illinois. Report 2002024. 1-16 (2002)

Tsutsui, S.、Pelikan, M.、Goldberg, D.E.：“通过构建和采样边缘直方图解决序列问题”Illi GAL 报告第 2002024 号伊利诺伊大学。