Abstract—Multi-objective genetic programming has been a powerful technique to solve problems of different
with minimum human effort. Literature contains
research on genetic programming. Multi-objective problems in data classi?cation, image processing are detailed explored. This survey reviewed some
2015-2018 and future directions of ?eld are discussed.
Keywords—Evolutionary computation, Multi Objective Genetic Programming,
Multi Objective Optimization, Survey, Genetic Pro-gramming
optimization problem single and multi objective why gp required?
solve problems with less human in-teraction/input in last decades
research on it problems solved by it cartesian GP paper organization
Optimization problem is ?nding best solution among fea-sible
solutions exists. Having two to three
objectives in a
problem is common. In multi-objective problems, objectives are usually
con?icting from each other. This leads towards statement that
trade-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 technique
that automatically solve problem with minimum human input and gives optimal results. In last few decades, GP is used for solving different problems
of machine learning,
arti?cial intelligence, medical
issues, computer networks etc.
Different types of GP include linear
GP, grammatical evo-lution, stack based GP, strongly
typed GP, tree based GP and cartesian GP.
Genetic Programming (CGP) is highly ?exible and
ef?cient form of GP invented by Julian Miller in 1999. CGP represents
structures as integer strings and these strings
are nodes of graphs. CGP does not bloat
as 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 shrt
background of evolutionary computation algorithms.
III 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,
etc. In section VI MOGP in different ?elds are brief. Section VII conclude
remarks and suggested future research directions.
Evolutionary computation (EC) algorithms are nature
to solve problems
better than human
efforts. 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 approaches
III. GENETIC PROGRAMMING
Genetic Programming (GP) is an nature
inspired Evolution-ary Computation algorithm derived from Genetic Algorithm.
GP comprised of computer programs to automatically
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 Terminals
Tree-based Genetic programming represents computer pro-grams in tree shape. Tree based representation of problem based on function set and terminals. Terminals
are leaf nodes of tree and functions are ancestors
of those leaves. For exam-ple, in an arithmetic problem operators are in functions and
In GP, increase in length of genetic program without im-provement is bloating. Its
counter measure is to limit
length of child programs.
C. Flowchart of GP
GA 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 linear
GP, stack-based GP etc. In tree-based notation
sub-trees crossover and mutation performed by ?ip terminal(s) only. Process
continues until termination
is maximum number of iterations or condition ful?lls.
D. Termination criteria
Terminating 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 GP
In real life problems there are very rare of having single objective. Most scenarios contain two or more objectives. A problem with two or three
objectives is multi-objective. Genetic programming
on 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 CLASSIFICATION
Data 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 itself
with data is imbalanced. Conventional machine learning
methods like Naive Bayes (NB, )Arti?cial
Neural Networks (ANN) and Support Vector Machine (SVM) outperforms for balanced datasets. In real world, datasets are
distributed in many classes that are imbalanced dataset. In these datasets two classes are formed, majority class and
minority class. NB, ANN and SVM gives overall good results
based on majority class while less considering minority class.
In medical applications, minority class data can plays crucial
role like classifying small
cancerous cells can save risk of life thats
why it cannot
ignore. In 10 each solution in population either in majority or minority class considered in ?tness
to special property of probabilistic
Gaussian classi?er that
distribution of one class not impacts on other
classes distribution, its used for data majority and
performance degradation. Multi-Objective Genetic Programming
(MOGP) is very ?ex-ible
to mathematical terminologies, variables and
constants. 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 pareto
for imbalanced data. In this
way, user have
to choose solution. Probabilistic Gaussian
user to get classi?ed solutions according to
technique on highly
six imbalanced datasets gives productive results then conventional
To deceive someone in ?nancial matters is criminal activity. Financial
fraud cases are increasing day-by-day. These crimes are performed through many different ways like credit cards,
insurance, hacking databases, etc. In 11 this serious
well growing issue is addressed and
of ?nancial fraud detection using grammar
based multi objective genetic
programming (GBMGP) is proposed.
Two main objectives
taken in this
approach that are con?dence and support.
companies or persons to forbid such activities this technique
resulted high accuracy on both available datasets and real time data. Con?dence and support are two objectives covered in this problem while fraudulent
coverage represents by con?dence and count of cases covered in total
is support. Both objectives are maximized to detect frauds
and cover maximum relevant cases with ef?ciency. In training, NSGA-II is to used for diverse solutions
using crowd-ing distance. While tokenization technique
applied during this process. In tokenization, each solution selected gets unique token and it cannot be taken by any other
selected solution. In testing, classi?cation of fraudulent in Pareto optimal fronts
genetic programming statistical selection learning(GBMGP-SSL) is used. Results are
compared 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 for
determining similarities between
datasets. Many techniques use meta-data
for measuring sim-ilarity
in dataset. Metadata is data about
idea is machine learning algorithms performance is standard-ized on similar datasets. Instead of utilizing original data this
technique works on meta-data of given datasets. Meta-data
comprised on information about data attributes, number of classes, data range and others. Previously authors proposed
technique using simple
genetic programming for similarities
computation. In current publication MOGP used to perform
EVOLUTIONARY COMPUTATION, SPRING 2017
this functionality while using metrics properties. Two objec-tives are model error rate and measure
of similarity in metrics
properties. Real data utilize from OpenML machine learning
online. Results showed signi?cant similarities and high correlation using metric properties on these
In real world applications of data analysis and clustering, MOGP approach quali?es
excellent results also in 13, 14 due to its ?exible tree structure.
V. MULTI OBJECTIVE GENETIC PROGRAMMING IN IMAGE PROCESSING
In image processing, research
detection is vast.
Its challenging to successfully detect objects from messy images. Multiple techniques are proposed in literature
for this purpose.
Genetic programming tree based structure makes it ?exible to
solve different types of problems. In 15 MOGP proposed for detecting objects
which provide many solutions
false rate and maximum object detection in simple
shapes dataset and coin images. Training phase comprise on two
levels. In ?rst level is object classi?cation with two objectives considered that
are 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 in
image with minimum false rate detected and maximum detection accuracy are
selected. Using MOGP approach objects
detected with high
accuracy as compared to single
objective genetic programming.
Features transformation using input data to new features
that are more powerful using MOGP proposed in 16. Using
MOGP features are transformed into one dimension from two classes that
are true positive and true negative rate. Entities are structured in GP tree and ?tness evaluated using
criteria. Random crossover and mutation performed on selected entities. Termination is based on number of generations
or objective entity
Pareto optimal solutions obtained
from data ration performed well than round robin method for setting
is performed using NSGA-II and
SPEA-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 steady
state micro GP (ASMiGP). In this technique
various 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 reduce
tree size. Crossover uses male-female differentiation. Roulette
used for mating selection. Feature
selection 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. These
programs relate to classes, one for each class.
Pareto based ?t solutions archive maintain while each tree contains one function and
two terminal nodes. Data points association with classes if certain threshold quali?es. The
proposed method is tested on huge features datasets that
is up to 49,151. Also, text datasets of high dimensions
up to 11.
Results are better than probabilistic Naive Bayes, tree-based C4.5 and rule-based RIPPER.
VI. OTHER APPLICATIONS OF GENETIC PROGRAMMING
Researchers 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 applications
are sum-marized below:
TABLE I. GENETIC PROGRAMMING APPLICATIONS IN FORECASTING
Adaptive load consumption modelling on the user side: contributions to load forecast-ing modelling
mixture of experts and genetic programming
The Application of Genetic Programming
on the Stock Movement
Interactions in Global Rainforests Through a GP-Tree Analysis
River Flow Forecasting Using an Improved Arti?cial Neural Network
TABLE II. GENETIC PROGRAMMING APPLICATIONS IN SEARCHING, SORTING AND SCHEDULING
Evolutionary Learning Based Iterated
for Google Machine Reassign-ment
Single- and Multi-Objective
Runtime Results for Sorting
On the use of genetic pro-gramming to evolve priority rules for resource
constrained project scheduling problems
Implementation of GP and MOGP are found in many areas of research. Flexible structure
of GP can map on various
real life problems to solve ef?ciently then existing techniques.
VII. CONCLUSION AND FUTURE WORK
In this survey, a brief overview of multi-objective genetic
programming applications in some ?elds are combined. Plenty of research is on-going for solving problems ef?ciently as
compared to conventional
algorithms. CGP research is active
its far better than GP.
This survey covers reviews of latest research papers on MOGP and address four to ?ve different areas implementation
EVOLUTIONARY COMPUTATION, SPRING 2017 4
´ ´ ´ ´
TABLE III. GENETIC PROGRAMMING APPLICATIONS IN GRAPHICS PROCESSING UNIT (GPU)
of a decision tree for large-scale
data a GPU-based
Faster GPU Based Genetic
Parallel and in-process com-pilation of individuals for ge-netic programming on GPU
7 Qingfu Zhang and Hui Li. Moea/d: A multiobjective evolutionary
algorithm based on decomposition.
on 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, pages
9 Masaki Takeuchi, Haruna Matsushita, Yoko Uwate, and Yoshifumi Nishio. Hybrid method of genetic algorithm and ?re?y
algorithm distinguishing between males and females.
10 Hardik H Maheta
K 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-Leung
Wong. Financial fraud detection by using grammar-based multi-objective genetic programming with ensemble
In Evolutionary Computation (CEC), 2015 IEEE Congress on, pages
1113–1120. IEEE, 2015.
12 Jakub Sm?d, Martin Pilat, Klara Peskova, and Roman Neruda. Multi-objective genetic programming for dataset similarity induction. In Computational
Intelligence, 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 and
im-plicit equations from data. In Evolutionary Computation (CEC), 2015
IEEE Congress on, pages 1129–1136. IEEE, 2015.
14 Qi Feng, Haowei Lian, and Jindong Zhu. Multi-level genetic pro-gramming for fault data clustering. In Prognostics and System Health
1–5. IEEE, 2017.
15 Thomas Liddle, Mark Johnston,
Multi-objective genetic programming
for 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 feature
using multiobjective genetic programming
for two-class classi?cation.
Computation (CEC), 2015 IEEE Congress on, pages 2989–2995. IEEE, 2015.
17 Kaustuv Nag and Nikhil R Pal. A multiobjective genetic programming-based ensemble for simultaneous
feature selection and classi?cation.
IEEE transactions on cybernetics, 46(2):499–510, 2016.
18 Fig. 2. Applications of Genetic Programming in various ?elds
Francisco Javier Giacometto Torres. Adaptive load consumption mod-elling on the user side: contributions to load forecasting modelling based
on supervised mixture of experts
and genetic programming.
with successful results. In future research of GP, CGP will be explored.
1 Stephen L Smith and Michael A Lones. Medical applications
of cartesian genetic programming.
In Inspired by Nature, pages 247–266. Springer, 2018.
2 Paul Kaufmann and Marco Platzner.
Combining local and global
search: A multi-objective evolutionary algorithm for cartesian genetic programming. In Inspired by Nature, pages
175–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 for
genetic 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?cial
neural 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 learning
based iterated local search for google machine reassignment problems. In Asia-Paci?c Conference on Simulated Evolution and
pages 409–421. Springer, 2017.
23 Markus Wagner and Frank Neumann. Single-and multi-objective
genetic programming: New runtime results
for sorting. In Evolutionary Computation
(CEC), 2014 IEEE Congress on, pages 125–132. IEEE, 2014.
5 Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal, and TAMT
A fast and elitist multiobjective genetic algorithm: Nsga-ii. IEEE
transactions on evolutionary computation,
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 project
scheduling problems. Information Sciences, 2017.
25 Krzysztof Jurczuk, Marcin Czajkowski, and Marek Kretowski. Evolu-
EVOLUTIONARY COMPUTATION, SPRING 2017 5
tionary induction of a decision tree for
large-scale data: a gpu-based
approach. 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,
27 Hakan Ayral and Songul Albayrak. Parallel and in-process compila-tion of individuals for genetic programming on gpu. arXiv preprint arXiv:1705.07492,