PBIL算法在组合优化问题中的应用研究

doi:10.3969/j.issn.1007130X.2011.

J4 ›› 2011, Vol. 33 ›› Issue (3): 141-145.doi: 10.3969/j.issn.1007130X.2011.

PBIL算法在组合优化问题中的应用研究

袁利永1,倪应华2,金炳尧3,马永进1

(1.浙江师范大学数理与信息工程学院,浙江金华 321004；2.浙江师范大学行知学院,浙江金华 321004；
3.浙江师范大学信息传播实验教学中心,浙江金华 321004)

收稿日期:2010-03-11 修回日期:2010-05-29 出版日期:2011-03-25 发布日期:2011-03-25
作者简介:袁利永(1978),男,浙江嵊州人，讲师，研究方向为进化计算和机器学习。倪应华（1977）,男，浙江海盐人，讲师，研究方向为计算机辅助技术和多媒体技术应用。金炳尧（1964），男，浙江兰溪人，硕士，教授,研究方向为模式识别和进化计算。
基金资助:
2008年度浙江省教育厅项目(Y200805671)

Application of the PBIL Algorithm to the Combinatorial Problem

YUAN Liyong1,NI Yinghua2,JIN Bingyao3,MA Yongjin1

(1.School of Mathematics Physics and Information Engineering,Zhejiang Normal University,Jinhua 321004;
2.Xinzhi School,Zhejiang Normal University,Jinhua 321004;
3.Information Dissemination Experimental Teaching Center,Zhejiang Normal University,Jinhua 321004,China)

Received:2010-03-11 Revised:2010-05-29 Online:2011-03-25 Published:2011-03-25

摘要/Abstract

摘要：

基于群体的增量学习(PBIL)算法有效结合了遗传算法和竞争学习的优点，运行过程简单，解决问题快速准确。本文提出将PBIL算法应用于求解CMN组合优化问题，以物流中心选址优化问题为例，介绍了基于PBIL求解CMN组合优化问题的一般方法，提出了针对此类问题的个体产生算法。为了提高算法的收敛速度和寻优能力，提出了基于当代最优解与历代最优解比较结果的概率学习加速方法。最后,通过实验仿真验证了上述改进的有效性。

关键词: PBIL, 组合优化, 进化计算, 基因算法, 物流中心选址

Abstract:

PBIL combines the features of genetic algorithms(GA) and competitive learning in an efficient way, which has the advantage of simple execution process, quick and accurate solutions to problems. In this paper, the PBIL algorithm is applied to solving combinatorial optimization problems. Using the logistics center location as an example,we illustrate a general method of solving the combinatorial optimization problems based on PBIL.A new algorithm for producing individuals for such problems is proposed. In order to improve the convergence speed and search capability, an acceleration method of probability learning is put forward based on the comparison of contemporary optimal solution and the successive optimal solution. Finally, the effectiveness of improvement is verified through simulation experiments.

Key words: PBIL;combinatorial optimization;evolutionary computation;genetic algorithm;logistics center location

袁利永1,倪应华2,金炳尧3,马永进1. PBIL算法在组合优化问题中的应用研究[J]. J4, 2011, 33(3): 141-145.

YUAN Liyong1,NI Yinghua2,JIN Bingyao3,MA Yongjin1. Application of the PBIL Algorithm to the Combinatorial Problem[J]. J4, 2011, 33(3): 141-145.

[1]	李进生，蒙江，童名文. 基于分布式遗传算法的水质传感器布置优化研究[J]. 计算机工程与科学, 2019, 41(03): 545-550.
[2]	覃远年，梁仲华. 蚁群算法研究与应用的新进展[J]. 计算机工程与科学, 2019, 41(01): 173-184.
[3]	周忠宝1,刘悦悦1,2,金倩颖1,肖和录1,程旭曼3. 基于FDH的分区域多目标遗传算法[J]. 计算机工程与科学, 2018, 40(07): 1295-1302.
[4]	李锋刚1,2，骆林1,2，陈亚波1,2,蒋祥飞1,2. 求解均值-CVaR投资组合模型的改进粒子群算法[J]. 计算机工程与科学, 2016, 38(09): 1870-1877.
[5]	张映玉1，付樟华2. 绝热量子优化算法研究进展[J]. J4, 2015, 37(03): 429-433.
[6]	王志刚，夏慧明. 求解车辆路径问题的人工蜂群算法[J]. J4, 2014, 36(06): 1088-1094.
[7]	王君. 带时间窗车辆路径问题的多目标文化基因算法[J]. J4, 2013, 35(1): 124-129.
[8]	张云明. 基于新变异算子的改进粒子群优化算法[J]. J4, 2011, 33(9): 95-99.
[9]	童科,毛力. 基于蚁群优化算法求解矩形件排样问题[J]. J4, 2011, 33(7): 158-162.
[10]	任晓娜1，张大方1,2，向旭宇2. 基于离散粒子群的DNA编码序列组合优化方法[J]. J4, 2011, 33(3): 179-184.
[11]	殷人昆[1] 吴阳[2,3] 张晶炜[3,4]. 蚁群算法解决指派问题的研究和应用[J]. J4, 2008, 30(4): 43-45.
[12]	虞成诚[1] 钟声[1] 胡绍华[2]. 基于深度优先搜索的一般图匹配算法[J]. J4, 2008, 30(12): 45-48.
[13]	李倩文贵华丁月华. 一种改进的求解旅行商问题的单亲遗传算法[J]. J4, 2007, 29(2): 89-92.
[14]	刘洋苏德富. 基于混合思维进化计算的网格资源分配算法[J]. J4, 2007, 29(1): 76-78.
[15]	马立肖王江晴. 遗传算法在组合优化问题中的应用[J]. J4, 2005, 27(7): 72-73.

PBIL算法在组合优化问题中的应用研究

Application of the PBIL Algorithm to the Combinatorial Problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

相关文章 15

编辑推荐

Metrics

本文评价