Computer Engineering & Science >
Application of the PBIL Algorithm to the Combinatorial Problem
Received date: 2010-03-11
Revised date: 2010-05-29
Online published: 2011-03-25
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.
YUAN Liyong1,NI Yinghua2,JIN Bingyao3,MA Yongjin1 . Application of the PBIL Algorithm to the Combinatorial Problem[J]. Computer Engineering & Science, 2011 , 33(3) : 141 -145 . DOI: 10.3969/j.issn.1007130X.2011.
［1］Baluja S.PopulationBased Incremental Learning［R］.Technical Report CMUCS94163,CarnegieMellon University,1994.
［2］Rastegar R,Hariri A,Mazoochi M.A Convergence Proof for the Population Based Incremental Learning Algorithm［C］∥Proc of the 17th IEEE Int’l Conf on Tools with Artificial Intelligence,2005:387391.
［3］金炳尧,蔚承建,何振亚.一个用于优化搜索的学习算法［J］.软件学报,2001,12(3):448453.
［4］Zhang Qingbin, Wu Tihua, Liu Bo. A Population Based Incremental Learning Algorithm with Elitist Strategy［C］∥Proc of the 3rd Int’l Conf on Natural Computation,2007:583587.
［5］GallagherM, Frean M. Population Based Continuous Optimization Probabilistic Modeling and Mean Shift［J］. Evolutionary Computation,2005,13(1):2942.
［6］金炳尧,马永进,骆红波.基于PBIL 算法的自动组卷系统研究［J］.计算机工程与科学,2005,27(10):4849.
［7］Baluja S,Caruana R.Removing the Genetics form the Standardgenetic Algorithm［C］∥Proc of the Int’l Conf on Machine Learning,1995:3846.
［8］万莉,黄挚雄,李志勇.基于GIS优化Dijkstra算法在物流中心选址中的研究［J］.计算机应用研究,2007,24(8):289291.
/
| 〈 |
|
〉 |