求解分类问题的文法多蜂算法

计算机科学 ›› 2015, Vol. 42 ›› Issue (Z6): 33-37.

求解分类问题的文法多蜂算法

刘坤起,周冲,吴志健

石家庄经济学院计算机科学系石家庄050031,石家庄经济学院计算机科学系石家庄050031,武汉大学软件工程国家重点实验室武汉430072

出版日期:2018-11-14 发布日期:2018-11-14
基金资助:
本文受国家自然科学基金项目(61402481),教育部计算机科学与技术专业综合改革试点(石家庄经济学院)项目,石家庄经济学院博士科研启动基金项目(2011)资助

Grammatical Bees Algorithm for Classification Problem

LIU Kun-qi, ZHOU Chong and WU Zhi-jian

Online:2018-11-14 Published:2018-11-14

摘要/Abstract

摘要： 多蜂算法(Bees Algorithm,BA)和文法演化算法(Grammatical Evolution,GE)是两个著名的演化算法。BA尽管收敛速度较快,但用于求解分类问题时,个体编码不易实现。而基于GE的分类算法的演化算子较简单,仅进行杂交和变异两个操作,但分类精度不高。针对两个算法的优点和不足,将BA和GE相结合,提出了一种新的混合演化算法——文法多蜂算法(Grammatical Bees Algorithm,GBA),并将其用于求解分类问题。在几个标准数据集上的实验验证了GBA的可行性和有效性。与基本基因表达式编程(Gene Expression Programming,GEP)分类算法和改进的GEP分类算法相比,GBA能获得较好的分类精度和更快的收敛速度。

Abstract: Bees Algorithm(BA) and Grammatical Evolution(GE) are two well-known evolutionary algorithms.BA for classification problems has shown faster convergence speed,but the individual coding is complicated.The operators of GE for classification problems are simple,which include crossover and mutation operators,but their classification accuracy is not high.In view of the strengths and weaknesses of the two algorithms,a new algorithm,named Grammatical Bees Algorithm(GBA) combining BA and GE,was proposed to solve the classification problems.Experiments on several benchmark data sets demonstrate the feasibility and effectiveness of GBA.Compared with gene expression programming(GEP) and improved GEP,GBA can achieve better classification accuracy and faster convergence speed.

Key words: Hybrid evolutionary algorithm,Evolutionary modeling,Bees algorithm,Grammatical evolution,Classification

刘坤起,周冲,吴志健. 求解分类问题的文法多蜂算法[J]. 计算机科学, 2015, 42(Z6): 33-37. https://doi.org/

LIU Kun-qi, ZHOU Chong and WU Zhi-jian. Grammatical Bees Algorithm for Classification Problem[J]. Computer Science, 2015, 42(Z6): 33-37. https://doi.org/

参考文献

[1] 范明.数据挖掘概念和技术[M].孟小峰,译.北京:机械工业出版社,2001
[2] Domingos,Pedro,Pazzanion M.The optimality of the simplebayesian classifier under Zero-One loss[J].Machine Learning,1997,29:103-137
[3] Shakhnarovish,Darrell,Indyk.K nearest neighbor methods inlearning and vision [M].MA:The MIT Press,2005
[4] Meyer D,Leisch F,Hornik K.The support vector machine under test[J].Neuro computing,2003,55(1/2):169-186
[5] Yuan Y,Shaw M J.Induction of fuzzy decision trees[J].Fuzzy Sets and Systems,1995,9:125-139
[6] Bazan J,Nguyen H S,Nguyen S H,et al.Rough set algorithms in classification problem[M]∥Rough Set Methods and Applications.Physica-Verlag,2000:49-88
[7] Alvarez J L,Mata J,Riquelme J C.OBLIC:classification system using evolutionary algorithm[C]∥6th International Work-Conference on Artificial and Natural Neural Networks.2001
[8] Bandyopadhyay S,Pal S K.Classification and learning using genetic algorithms[M].Springer Verlag,2007
[9] Winkler S M,Affenzeller M,Wagner S.Advances in applying genetic programming to machine learning focussing on classification problems [C]∥Parallel and Distributed Processing Symposium.2006
[10] Zhou Chi.Gene expression programming and rule induction for domain knowledge discovery and management [D].Chicago:University of Illinois at Chicago,2003
[11] Zhou C,Xiao W,Tirpak T M,et al.Evolving Accurate and Compact Classification Rules with Gene Expression Programming[J].IEEE Transactions on Evokutionary Computation,2003,7(6):519-513
[12] 张建伟,吴志健,黄樟灿.基于多表达式编程的分类算法研究[J].小型微型计算机系统,2010,131(7)
[13] Pham D T,Ghanbarzadeh A,Koc E,et al.The Bees Algorithm[Z].Technical Note,Manufacturing Engineering Centre,Cardiff University,UK,2005
[14] Pham D T,Ghanbarzadeh A,Koc E,et al.The Bees Algorithm,A Novel Tool for Complex Optimisation Problems[C]∥Proc 2nd Virtual International Conference on Intelligent Production Machines and Systems.Elsevier(Oxford),2006:454-459
[15] Ryan C,Collins J J,O’Neill M.Grammatical evolution:evolving programs for an arbitrary language[C]∥First EuropeanWorkshop on Genetic Programming,1998.Paris,France,April 1998:83-96
[16] O’Neill M,Ryan C.Grammatical Evolution[J].IEEE Trans.on Evolutionary Computation,2001,5(4):349-358
[17] O’Neill M,Ryan C.Grammatical Evolution:Evolutionary Automatic Programming in an Arbitrary Language[M].Kluwer Academic Publishers
[18] 刘坤起,康立山,赵致琢.关于认知演化计算分支领域的研究简报(Ⅰ)[J].计算机科学,2009,6(7):26-31
[19] 刘坤起,康立山,赵致琢.关于认知演化计算分支领域的研究简报(Ⅱ)[J].计算机科学,2009,6(8):35-39
[20] Witten I H,Frank E.Data mining:practical machine learning tools and techniques[M].San Francisco,CA:Morgan Kaufmann,2005
[21] 王卫红,杜燕烨,李曲.基于克隆选择和量子进化的GEP分类算法[J].计算机科学,2011,8(10):236-239
[22] 柳益君,朱明放,习海旭,等.基于最大隶属度原则的基因表达式编程分类[J].计算机工程与应用,2012,8(26):48-52
[23] Sugiura H,Mizuno T,Kita E.Santa Fe Trail Problem SolutionUsing Grammatical Evolution[J].2012 International Conference onIndustrial and Intelligent Information,Singapore,2012,2:36-40
[24] Ahmad S A.A Study of Search Neighbourhood in the Bees Algorithm[D].Cardiff University,2012
[25] Alfonsecaa M,Gil F J S.Evolving an ecology of mathematical expressions with grammatical evolution[J].BioSystems,2013,111(2):111-119
[26] 王璞.基于遗传规划的分类算法研究[D].安徽:中国科技大学,2013
[27] 陈剑,马光志.一种基于文法演化自动拟合非线性数据的蜂群算法[J].计算机应用研究,2013,30(10):3257-3260
[28] Ganesh Kumar P.Hybrid Ant Bee Algorithm for Fuzzy Expert System Based Sample Classification[J].IEEE/ACM Transactions on Computational Biology and Bioinformatics,2014,11(2):347-360
[29] UCI数据集.http://archive.ics.uci.edu/ml/

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed