Abstract—Multi-objective genetic programming has been a powerful technique to solve problems of differentareasef?-cientlywith minimum human effort. Literature containshugeresearch on genetic programming. Multi-objective problems in data classi?cation, image processing are detailed explored. This survey reviewed somelatest papersspecially2015-2018 and future directions of ?eld are discussed.Keywords—Evolutionary computation, Multi Objective Genetic Programming,Multi Objective Optimization, Survey, Genetic Pro-gramming I. INTRODUCTIONoptimization problem single and multi objective why gp required?automaticallysolve problems with less human in-teraction/input in last decadesresearch on it problems solved by it cartesian GP paper organizationOptimization problem is ?nding best solution among fea-siblesolutions exists. Having two to threeobjectives in aproblem is common. In multi-objective problems, objectives are usuallycon?icting from each other.
This leads towards statement thattrade-off results obtained for these problems on speci?ed constraints and objective function.Genetic Programming (GP) is an evolutionary algorithm derived from Genetic Algorithm (GA). This heuristic technique ?exibility is so enhanced that it can be used to solve complex problems. GP is a techniquethat automatically solve problem with minimum human input and gives optimal results. In last few decades, GP is used for solving different problemsof machine learning,arti?cial intelligence, medicalissues, computer networks etc.
Different types of GP include linearGP, grammatical evo-lution, stack based GP, stronglytyped GP, tree based GP and cartesian GP.CartesianGenetic Programming (CGP) is highly ?exible andef?cient form of GP invented by Julian Miller in 1999. CGP representsstructures as integer strings and these stringsare nodes of graphs. CGP does not bloatas compared to GP. Also it uses very small population and gives fast results. It used in latest research in medical applications 1, local and global searching 2, control engineering 3 and others applications 4.The remaining paper is organized as follows.
Section II has shrtbackground of evolutionary computation algorithms.SectionIII brief GP structure, its ?owchart and multi-objective GP (MOGP). Section IV discuss MOGP applications in clas-si?cation of data. Section V describes MOGP for image processing i.e. feature selection,object detectionetc. In section VI MOGP in different ?elds are brief.
Section VII concluderemarks and suggested future research directions.II. BACKGROUNDEvolutionary computation (EC) algorithms are naturein-spiredto solve problemsbetter than humanefforts. Some most widely used EC algorithms are Non-dominated Sorting Algo-rithm II (NSGA-II) 5, Strength Pareto Evolutionary Algo-rithm II (SPEA-II) 6, Multi-objective Evolutionary Algorithm based on Decomposition (MOEAD) 7, Genetic Programming (GP) 8 and many hybrid approaches9.
III. GENETIC PROGRAMMINGGenetic Programming (GP) is an natureinspired Evolution-ary Computation algorithm derived from Genetic Algorithm.GP comprised of computer programs to automaticallysolveproblems.The implementation of GP involves three main steps that are generate initial population, genetic operations(selection, reproduction, crossover, mutation) an termination condition. A.
Representation, Functions and TerminalsTree-based Genetic programming represents computer pro-grams in tree shape. Tree based representation of problem based on function set and terminals. Terminalsare leaf nodes of tree and functions are ancestorsof those leaves. For exam-ple, in an arithmetic problem operators are in functions and B.
BloatingIn GP, increase in length of genetic program without im-provement is bloating. Itscounter measure is to limitmaximumlength of child programs. C. Flowchart of GPGA is inspired from nature evolutionary process.
GP is derived from GA. Its population based on computer programs.Tree based representation is most using representation of GP. Others include linearGP, stack-based GP etc.
In tree-based notationsub-trees crossover and mutation performed by ?ip terminal(s) only. Processcontinues until terminationcriteria thatis maximum number of iterations or condition ful?lls. D. Termination criteriaTerminating criteria is a condition that is used for ending the PSO procedure. In the proposed work, algorithm stops when number of iterations completed.EVOLUTIONARY COMPUTATION, SPRING 2017 Fig. 1. Flowchart of GP E.
Multi-Objective GPIn real life problems there are very rare of having single objective. Most scenarios contain two or more objectives. A problem with two or threeobjectives is multi-objective. Genetic programmingis ?exibleon both single and multi-objective problems and gives Pareto optimal solutions. Deci-sion maker have multi choice to select any solution according to IV. MULTI-OBJECTIVE GENETIC PROGRAMMING FOR DATA CLASSIFICATIONData classi?cation is a process of classifying data into different classes based on data features.
Classi?ed information is then used for important decision making.Classifying large datasets with less human interference is itselfchallengingwith data is imbalanced. Conventional machine learningmethods like Naive Bayes (NB, )Arti?cialNeural Networks (ANN) and Support Vector Machine (SVM) outperforms for balanced datasets. In real world, datasets are2 distributed in many classes that are imbalanced dataset. In these datasets two classes are formed, majority class andminority class. NB, ANN and SVM gives overall good resultsbased on majority class while less considering minority class.In medical applications, minority class data can plays crucialrole like classifying smallcancerous cells can save risk of life thatswhy it cannotignore. In 10 each solution in population either in majority or minority class considered in ?tnessevaluation.
Dueto special property of probabilisticGaussian classi?er thatdistribution of one class not impacts on otherclasses distribution, its used for data majority andminority classi?cation.It preventsperformance degradation. Multi-Objective Genetic Programming(MOGP) is very ?ex-ibleto mathematical terminologies, variables andconstants. Each class accuracy considered as separate objective. MOGP gives Pareto optimal solutions and gaussian classi?er classify it. Instead of single solution in a run MOGP gives paretooptimal solutionsfor imbalanced data.
In thisway, user havemultiple optionsto choose solution. Probabilistic Gaussianclassi?er helpsuser to get classi?ed solutions according toprovided threshold.Applying proposedtechnique on highlysix imbalanced datasets gives productive results then conventionaltechniques.To deceive someone in ?nancial matters is criminal activity.
Financialfraud cases are increasing day-by-day. These crimes are performed through many different ways like credit cards,insurance, hacking databases, etc. In 11 this seriouswell growing issue is addressed andnew methodof ?nancial fraud detection using grammarbased multi objective geneticprogramming (GBMGP) is proposed.Two main objectivesaretaken in thisapproach that are con?dence and support.Identi?cationof fallaciouscompanies or persons to forbid such activities this techniqueresulted high accuracy on both available datasets and real time data. Con?dence and support are two objectives covered in this problem while fraudulentcoverage represents by con?dence and count of cases covered in totalis support.
Both objectives are maximized to detect fraudsand cover maximum relevant cases with ef?ciency. In training, NSGA-II is to used for diverse solutionsusing crowd-ing distance. While tokenization techniqueapplied during this process. In tokenization, each solution selected gets unique token and it cannot be taken by any otherselected solution. In testing, classi?cation of fraudulent in Pareto optimal frontssolutionsgrammarbasedmulti-objectivegenetic programming statistical selection learning(GBMGP-SSL) is used. Results arecompared with data mining algorithms on four ?nancial and two real time datasets. GBMGP-SSL outperforms than data mining techniques with maximize diversity and convergence.In 12 MOGP used fordetermining similarities betweendatasets.
Many techniques use meta-datafor measuring sim-ilarityin dataset. Metadata is data aboutdata. Meta-learningidea is machine learning algorithms performance is standard-ized on similar datasets. Instead of utilizing original data thistechnique works on meta-data of given datasets. Meta-datacomprised on information about data attributes, number of classes, data range and others.
Previously authors proposedtechnique using simplegenetic programming for similaritiescomputation. In current publication MOGP used to performEVOLUTIONARY COMPUTATION, SPRING 2017 this functionality while using metrics properties. Two objec-tives are model error rate and measureof similarity in metricsproperties.
Real data utilize from OpenML machine learningrepositoriesonline. Results showed signi?cant similarities and high correlation using metric properties on thesedatasets.In real world applications of data analysis and clustering, MOGP approach quali?esexcellent results also in 13, 14 due to its ?exible tree structure. V.
MULTI OBJECTIVE GENETIC PROGRAMMING IN IMAGE PROCESSINGIn image processing, researchon objectdetection is vast.Its challenging to successfully detect objects from messy images. Multiple techniques are proposed in literaturefor this purpose.Genetic programming tree based structure makes it ?exible tosolve different types of problems. In 15 MOGP proposed for detecting objectswhich provide many solutionswith minimumfalse rate and maximum object detection in simpleshapes dataset and coin images.
Training phase comprise on twolevels. In ?rst level is object classi?cation with two objectives considered thatare true positive and true negative rate. Maxi-mizing both objectives is target in this phase. Second level is object detection with two objectives that are object detection rate should be maximize and false alarm rate minimized. The areas inimage with minimum false rate detected and maximum detection accuracy areselected. Using MOGP approach objectsdetected with highaccuracy as compared to singleobjective genetic programming.
Features transformation using input data to new featuresthat are more powerful using MOGP proposed in 16. UsingMOGP features are transformed into one dimension from two classes thatare true positive and true negative rate. Entities are structured in GP tree and ?tness evaluated usingevaluationcriteria. Random crossover and mutation performed on selected entities. Termination is based on number of generationsor objective entityachieved.Pareto optimal solutions obtainedfrom data ration performed well than round robin method for settingthreshold.
Optimizationis performed using NSGA-II andSPEA-II. Results showed that optimization gives better performance on transformed data with data ratio threshold.In 17 a new technique is proposed named archive-based steadystate micro GP (ASMiGP). In this techniquevarious classi?ers are used that is one for each class and three objectives: false positive, false negative and number of nodes are minimized. Also restricted number of nodes that reducetree size.
Crossover uses male-female differentiation. Roulettewheel techniqueused for mating selection. Featureselection and classi?cation are used as embedded approach.
Authors use discriminant functions based on genetic programming.Every program comprised of mathematical equations and data features. Theseprograms relate to classes, one for each class.Pareto based ?t solutions archive maintain while each tree contains one function andtwo terminal nodes. Data points association with classes if certain threshold quali?es.
Theproposed method is tested on huge features datasets thatis up to 49,151. Also, text datasets of high dimensionsup to 11.Results are better than probabilistic Naive Bayes, tree-based C4.5 and rule-based RIPPER.3 VI. OTHER APPLICATIONS OF GENETIC PROGRAMMINGResearchers using GP in forecasting, searching, sorting, scheduling problems. Also its applications are found in Graph-ical Processing Unit(GPU).
Some latest publications in above mentioned ?elds, genetic programming applicationsare sum-marized below: TABLE I. GENETIC PROGRAMMING APPLICATIONS IN FORECASTING Paper Reference Adaptive load consumption modelling on the user side: contributions to load forecast-ing modelling based on super-vised mixture of experts and genetic programming 18 The Application of Genetic Programming on the Stock Movement Forecasting Sys-tem 19 Understanding Climate-Vegetation Interactions in Global Rainforests Through a GP-Tree Analysis 20 River Flow Forecasting Using an Improved Arti?cial Neural Network 21 TABLE II. GENETIC PROGRAMMING APPLICATIONS IN SEARCHING, SORTING AND SCHEDULING Paper Reference Evolutionary Learning Based Iterated Local Search for Google Machine Reassign-ment Problems 22 Single- and Multi-Objective Genetic Programming New Runtime Results for Sorting 23 On the use of genetic pro-gramming to evolve priority rules for resource constrained project scheduling problems 24 Implementation of GP and MOGP are found in many areas of research. Flexible structureof GP can map on variousreal life problems to solve ef?ciently then existing techniques. VII. CONCLUSION AND FUTURE WORKIn this survey, a brief overview of multi-objective geneticprogramming applications in some ?elds are combined. Plenty of research is on-going for solving problems ef?ciently ascompared to conventionalalgorithms. CGP research is activeasits far better than GP.
This survey covers reviews of latest research papers on MOGP and address four to ?ve different areas implementationEVOLUTIONARY COMPUTATION, SPRING 2017 4 ´ ´ ´ ´ TABLE III. GENETIC PROGRAMMING APPLICATIONS IN GRAPHICS PROCESSING UNIT (GPU) Paper Reference Evolutionary induction of a decision tree for large-scale data a GPU-based approach 25 Faster GPU Based Genetic Programming Using A Two Dimensional 26 Parallel and in-process com-pilation of individuals for ge-netic programming on GPU 27 7 Qingfu Zhang and Hui Li. Moea/d: A multiobjective evolutionaryalgorithm based on decomposition.IEEE Transactionson evolutionary computation, 11(6):712–731, 2007.8 John Koza, Forrest Bennett, and Oscar Stiffelman. Genetic program-ming as a darwinian invention machine.
Genetic Programming, pages651–651, 1999.9 Masaki Takeuchi, Haruna Matsushita, Yoko Uwate, and Yoshifumi Nishio. Hybrid method of genetic algorithm and ?re?yalgorithm distinguishing between males and females.10 Hardik H MahetaandVipulK Dabhi.
Classi?cation of imbalanced data sets using multi objective genetic programming.In Computer Commu-nication and Informatics (ICCCI), 2015 International Conference on,pages 1–6. IEEE, 2015.
11 Haibing Li and Man-LeungWong. Financial fraud detection by using grammar-based multi-objective genetic programming with ensemblelearning.In Evolutionary Computation (CEC), 2015 IEEE Congress on, pages1113–1120. IEEE, 2015.
Arti?cial Intelligence Medical DiagnosticsMachine Learning Classi?cation12 Jakub Sm?d, Martin Pilat, Klara Peskova, and Roman Neruda. Multi-objective genetic programming for dataset similarity induction. In ComputationalIntelligence, 2015 IEEE Symposium Series on, pages 1576–1582. IEEE, 2015.13 Bing Wang, Hemant Kumar Singh, and Tapabrata Ray. A multi-objective genetic programming approach to uncover explicit andim-plicit equations from data. In Evolutionary Computation (CEC), 2015IEEE Congress on, pages 1129–1136. IEEE, 2015.
Forecasting Programming Scheduling Sorting GPUOthers Object Detection14 Qi Feng, Haowei Lian, and Jindong Zhu. Multi-level genetic pro-gramming for fault data clustering. In Prognostics and System HealthManagement Conference(PHM-Harbin), 2017,pages1–5. IEEE, 2017.15 Thomas Liddle, Mark Johnston,and MengjieZhang.Multi-objective genetic programmingfor object detection. In Evolutionary Computation (CEC), 2010 IEEE Congress on, pages 1–8.
IEEE, 2010.16 Tomoyuki Hiroyasu, Toshihide Shiraishi, Tomoya Yoshida, and Utako Yamamoto. A featuretransformation methodusing multiobjective genetic programmingfor two-class classi?cation. In EvolutionaryComputation (CEC), 2015 IEEE Congress on, pages 2989–2995. IEEE, 2015.17 Kaustuv Nag and Nikhil R Pal.
A multiobjective genetic programming-based ensemble for simultaneousfeature selection and classi?cation.IEEE transactions on cybernetics, 46(2):499–510, 2016. 18 Fig. 2.
Applications of Genetic Programming in various ?eldsFrancisco Javier Giacometto Torres. Adaptive load consumption mod-elling on the user side: contributions to load forecasting modelling basedon supervised mixture of expertsand genetic programming.2017. with successful results.
In future research of GP, CGP will be explored. REFERENCES 1 Stephen L Smith and Michael A Lones. Medical applicationsof cartesian genetic programming.In Inspired by Nature, pages 247–266.
Springer, 2018.2 Paul Kaufmann and Marco Platzner. Combining local and globalsearch: A multi-objective evolutionary algorithm for cartesian genetic programming. In Inspired by Nature, pages175–194.
Springer, 2018.3 Tim Clarke. Cartesian genetic programming for control engineering. In Inspired by Nature, pages 157–173. Springer, 2018.
4 Lukas Sekanina. Approximate computing: An old job forcartesiangenetic programming? In Inspired by Nature, pages 195–212. Springer, 2018.19 Yi-Chi Tsai and Cheng-Yih Hong.
The application of genetic program-ming on the stock movement forecasting system. International Journal of Economics and Financial Issues, 7(6):68–73, 2017.20 Anuradha Kodali, Marcin Szubert, Sangram Ganguly, Joshua Bongard,and Kamalika Das. Understanding climate-vegetation interactions in global rainforests through a gp-tree analysis.
2017.21 Josiah Adeyemo, Oluwaseun Oyebode, and Derek Stretch. River ?ow forecasting using an improved arti?cialneural network. In EVOLVE-A Bridge between Probability, Set Oriented Numerics, and Evolutionary Computation VI, pages 179–193. Springer, 2018.22 Ayad Turky, Nasser R Sabar, Abdul Sattar, and Andy Song. Evolution-ary learningbased iterated local search for google machine reassignment problems.
In Asia-Paci?c Conference on Simulated Evolution andLearning,pages 409–421. Springer, 2017.23 Markus Wagner and Frank Neumann.
Single-and multi-objectivegenetic programming: New runtime resultsfor sorting. In Evolutionary Computation(CEC), 2014 IEEE Congress on, pages 125–132. IEEE, 2014. 5 Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal, and TAMTMeyari-van.A fast and elitist multiobjective genetic algorithm: Nsga-ii.
IEEEtransactions on evolutionary computation,6(2):182–197, 2002.6 Eckart Zitzler, Marco Laumanns, and Lothar Thiele. Spea2: Improving the strength pareto evolutionary algorithm. 2001.24 Shelvin Chand, Quang Huynh, Hemant Singh,Tapabrata Ray, and Markus Wagner. On the use of genetic programming to evolve priority rules for resource constrained projectscheduling problems.
Information Sciences, 2017.25 Krzysztof Jurczuk, Marcin Czajkowski, and Marek Kretowski. Evolu-EVOLUTIONARY COMPUTATION, SPRING 2017 5 tionary induction of a decision tree forlarge-scale data: a gpu-basedapproach. Soft Computing, 21(24):7363–7379, 2017.26 Darren M Chitty. Faster gpu-based genetic programming using a two-dimensional stack.
Soft Computing, 21(14):3859–3878,2017. ¨ 27 Hakan Ayral and Songul Albayrak. Parallel and in-process compila-tion of individuals for genetic programming on gpu. arXiv preprint arXiv:1705.07492,2017.