Geometric Semantic Genetic
Programmingand its Real-Life Applications
Leonardo Vanneschi
NOVA IMS
Universidade Nova De Lisboa
Portugallvanneschi@novaims.unl.pt
Leonardo Vanneschi

Geometric Semantic Genetic Programming1

Leonardo Vanneschi Biographical Sketch• 1996: University Degree in Computer Science at the Universityof Pisa (Italy)• 1996-1999: Software Engineer in Industry• 1999-2004: PhD Student and Assistant at the University of
Lausanne (Switzerland)• Complex Systems, Machine Learning, Genetic Programming• 2004-2011 : Assistant Professor at the Computer Science
Department University of Milano-Bicocca, Italy• 2011-2014 : Assistant Professor at the NOVA IMS, University Nova ofLisbon, Portugal• 2014-... : Associate Professor with Tenure at the NOVA IMS, University
Nova of Lisbon, Portugal
Leonardo Vanneschi

Geometric Semantic Genetic Programming2

Objective• Presenting new operators for Genetic Programming(geometric semantic operators)• Their theoretical advantages• Their practical (real-world) applications

Leonardo Vanneschi

Geometric Semantic Genetic Programming

3

Agenda••••Optimization Problems and Fitness Landscapes
Genetic Algorithms (geometric operators)
Genetic Programming (geometric semantic operators)
Implementation of geometric semantic operators• Real-Life Applications:• Drug Discovery (prediction of pharmacokinetic parameters)• Prediction of the Unified Parkinson’s Disease Rating Scale
Assessment• Prediction of high performance concrete strength• Prediction of the Relative Position of Computer
Tomography (CT) Slices• Forecasting of Energy Consumption• Discussion/Open Issues
Leonardo Vanneschi

Geometric Semantic Genetic Programming

4

Part I – Geometric Semantic GP••••

Optimization Problems and Fitness Landscapes
Genetic Algorithms (geometric operators)
Genetic Programming (geometric semantic operators)
Implementation of geometric semantic operators

Part II – Real-Life Applications••••

Drug Discovery (prediction of pharmacokinetic parameters)
Pred. of the Unif. Parkinson’s Disease Rat. Scale Assess.
Prediction of high performance concrete strength
Pred. of the Rel. Pos. of Computer Tomography (CT) Slices• Forecasting of Energy Consumption

Part III – Conclusions• Discussion/Open Issues
Leonardo Vanneschi

Geometric Semantic Genetic Programming

5

PART I
Geometric Semantic
Genetic Programming

Leonardo Vanneschi

Geometric Semantic Genetic Programming

6

Main reference for this first part:L. Vanneschi.
An Introduction to Geometric Semantic Genetic Programming.
NEO 2015: Results of the Numerical and Evolutionary
Optimization Workshop NEO 2015, held at September 23-25
2015 in Tijuana, Mexico. Pages 3-42.
O. Schutze, L. Trujillo, P. Lagrand and Y. Maldonado Editors.
Springer International Publishing.
2017.

isbn=978-3-319-44003-3
doi=10.1007/978-3-319-440033_1,
url=http://dx.doi.org/10.1007/978-3-319-44003-3_1
Leonardo Vanneschi

Geometric Semantic Genetic Programming

7

Let’s start with a very light introduction to
optimization problem...

The content of this very first part is well-known to the audience, but
it is used to fix a terminology that will be used in the continuation...

Leonardo Vanneschi

Geometric Semantic Genetic Programming

8

Optimization Problems
Informallysolving an optimization problem means to find thebest solution(s) in a (typically huge) set of othercandidate solutions
A little bit more formally
A pair: (S, f)
where S is the set of all possible solutions (we will call it
search space) and f is a function:

f=So Rf quantifies the quality of the solutions in S and it is called costfunction or fitness function.
Leonardo Vanneschi

Geometric Semantic Genetic Programming

9

Optimization Problems - Definitions
An optimization problem is a minimization problem if it consists in looking
for a solution o  S, such that:f(o) ≤ f(i),  i  S

An optimization problem is a maximization problem if it consists inlooking for a solution o  S, such that:f(o) ≥ f(i),  i  S

Such a solution is called global optimum (minimum or maximum)

Leonardo Vanneschi

Geometric Semantic Genetic Programming

10

Hill Climbing
The most natural and immediate method to solve an optimization problem.

It consists in trying to improve fitness step by step (stepwise
improvement) by means of the concept of neighborhood.
INITIALIZE(istart);i := istart;
repeat
GENERATE(j from Ni);
if f(j) better than f(i) then i := j;until f(i) better than f(j),  j  Ni;
Ni = neighborhood of solution i
Leonardo Vanneschi

Geometric Semantic Genetic Programming

11

Hill Climbing - Example
Consider the following maximization problem:
S={i|

i N

&

0 ≤ i ≤ 15 }

 i  S, f(i) = number of "1"s in the binary representation of i
Neighborhood:j  Ni  | j - i | = 1

Steps of the algorithm:• Current solution (randomly generated): i = 6 (0110) f(i) = 2
neighbors of i = 5 (0101), 7 (0111) f(5) = 2, f(7) = 3 new current solution: i := 7
• neighbors of i = 6 (0110), 8 (1000) f(6) = 2, f(8) = 1 algorithm terminates
Solution returned: i = 7 (0111)
Global optimum: o = 15 (1111)
Leonardo Vanneschi

f(i) = 3
f(o) = 4

The solution returned by the Hill
Climbing is a “local optimum”.

Geometric Semantic Genetic Programming

12

Local Optima
A solution j  S is called local optimum (as regards aneighborhood structure N), if:
for minimization problems:f(j) ≤ f(i)  i  Nj

for maximization problems:f(j) ≥ f(i)  i  Nj

Hill Climbing always returns a local optimum (notnecessarily the global one).

Leonardo Vanneschi

Geometric Semantic Genetic Programming

13

Fitness Landscape
Plot: horizontal axis: solutions in the search space (ordered according
to the neighborhood structure); vertical axis: fitness.
Hill Climbing

Leonardo Vanneschi

Geometric Semantic Genetic Programming

14

Fitness Landscape(courtesy of Sebastien Verel)

Leonardo Vanneschi

Geometric Semantic Genetic Programming

15

Importance of Fitness LandscapeIt gives a visual intuition of the facility or difficulty of a search agent (like Hill
Climbing, but also Evolutionary Algorithms) to find the global optimum.
For instance:• Smooth landscape, with only one "peak" (global optimum)
easy problem• Rugged landscape, with many local optima
hard problem

Limitation of fitness landscapes
It is generally impossible to draw a fitness landscape:• Huge search space• Huge neighborhoods (multi-dimensionality!)
Leonardo Vanneschi

Geometric Semantic Genetic Programming

16

Remark that...
if we consider exactly the same problem, but with a different
neighborhood structure, the fitness landscape changes and Hill
Climbing easily finds easily the global optimum:
S={i|

i N

&

0 ≤ i ≤ 15 }

 i  S, f(i) = number of "1"s in the binary representation of i
Neighborhood: j  Ni  the binary repr. of j and i differ by just 1 bit

There are no local optima in this fitness landscape!
Unimodal fitness landscape.
(every individual that is different from the global optimum has at least
one neighbor better than him, that can be obtained by changing a 0
into a 1).
Leonardo Vanneschi

Geometric Semantic Genetic Programming

17

Another Case
S = { vectors of prefixed length of real numbers included in [0,10] } i  S, f(i) = distance to a prefixed (and known and unique) global optimum
Neighborhood:j  Ni  j is equal to i except for the random perturbation ofsome of its coordinates of a quantity included in [0,1].

ExampleThe global optimum[8.0, 6.0, 4.0, 7.0, 5.0]
closer!

A solution i[5.8, 6.4, 2.9, 4.9, 3.6]

[5.2, 6.4, 2.1, 4.9, 3.7]

Leonardo Vanneschi

A solution j neighbor of i
Geometric Semantic Genetic Programming18

Terminology about the previous example
The operator that is “related” to the neighborhood structure of theprevious example is called ball mutation.

Let us give a name to the previous problem:
Continuous Optimization with Notorious Optimum (CONO)

Leonardo Vanneschi

Geometric Semantic Genetic Programming

19

Evolutionary Algorithms
Initial Population

Intermediate Population

Selection

Genetic Operators (Variation)(typically crossover and mutation)... and the winner is...

New Population
Leonardo Vanneschi

Geometric Semantic Genetic Programming

20

Genetic Algorithms (GAs)
Solutions/Individuals = Strings of prefixed length“Traditional situation”: the values in each allele are discrete and:crossover

Leonardo Vanneschi

mutation

Geometric Semantic Genetic Programming

21

Genetic Algorithms (GAs)... but GAs can work also on vectors of continuous values.
In that case, many operators have been introduced.
Interesting: Geometric operators [Moraglio and Poli, 2006]:

Geometric Crossover
Coordinates of the (unique) offspring are the weighted average of thecorresponding coordinates of the parents (with weighs in [0,1] whose sum is 1).
Global optimum
the offspring cannot be worse
than the worse of the parents
this crossover expresses “betweenness”:
the offsrping stands between (in the line joining) the parents
Leonardo Vanneschi

Geometric Semantic Genetic Programming

22

Genetic Algorithms (GAs)... but GAs can work also on vectors of continuous values.
In that case, many operators have been introduced.
Interesting: Geometric operators [Moraglio and Poli, 2006]:

Geometric Mutation
Ball mutation
Unimodal fitness landscape on
the CONO problem.

Leonardo Vanneschi

Geometric Semantic Genetic Programming

23

Genetic Programming (GP)An evolutionary algorithm in which solutions/individuals are computer programs.
Typically (“Lisp-like”) trees.

Example (Symbolic Regression)
Given the set of data:

H=

2 4
3 5

input

targetA possible individual is:

*

10
13

+

x2

x1

x2

It represents the program/function/expression: P(x1, x2) = x2 * (x1 + x2)
And one possible fitness could be:fitness(P) = |P(2,4) – 10| + | P(3,5) – 13| =|4 * (2+4) – 10| + |5 * (3+5) – 13| = |24 – 10| + |40 – 13| = 14 + 27 = 41
Leonardo Vanneschi

Geometric Semantic Genetic Programming24

GP as a Machine Learning Method• Known: the correct outputs for a fixed given set of inputs {Ii, Oi}• Sought: a function belonging to a certain class that interpolates
those points, i.e., f(Ii)= Oi for any i• Output vector: the vector of the outputs of f is f(I)=(f(Ii))• Fitness: a measure on the error on the training set, i.e.,distance
between the output vectors of f and the target output vector
F(f)=D(f(I),O) (ERROR AS DISTANCE)

We are talking of Supervised Learning.
Leonardo Vanneschi

Geometric Semantic Genetic Programming25

What is «Semantics» ?
[Nguyen at al., 2011], [Moraglio et al., 2012], …
Many definition exist, but in GP the most used one is:

The vector of outputs of a program on the different training data

ExampleThe individual:

Given the set of data:

H=

2 4
3 5

*

10
13

+

x2
x1

x2

That represents function: P(x1, x2) = x2 * (x1 + x2)
has a semantics qual to: [P(2,4), P(3,5)] = [24, 40]
Leonardo Vanneschi

Geometric Semantic Genetic Programming

26

Semantics
Let X = [𝒙1, 𝒙2, ..., 𝒙n] be the set of input data (fitness cases)of a supervised learning problem and 𝒕 = [t1, t2, ..., tn] thevector of the respective expected output or target values.
A GP individual (or program) P can be seen as a function
that, for each input vector 𝒙i returns the scalar value P(𝒙i).

We define semantics of an individual P the vector:𝒔 P = [P(𝒙1),P(𝒙2), ...,P(𝒙n)]This is a point in a n-dimensional space
Leonardo Vanneschi

Geometric Semantic Genetic Programming

27

Semantic Space

The target isalso represented
by a point in thesemantic space
and usually it
does notcorrespond tothe origin?
Genotypic space
Leonardo VanneschitargetSemantic space
Geometric Semantic Genetic Programming

28

«Traditional» GP operators

mutationcrossover29«Traditional» GP operators… Produce offspring by blind syntactic manipulation ofparent parse trees, regardless of their semantics.

… Preserve syntactic “genetic material”, but what is theireffect on semantics?

Leonardo Vanneschi

Geometric Semantic Genetic Programming30

Objective

Is it possible to define transformations on the syntax ofindividuals that have known effects on their semantics?

Leonardo Vanneschi

Geometric Semantic Genetic Programming31?

Ball Mutation?
Syntax
Leonardo Vanneschi

Semantics
Geometric Semantic Genetic Programming

32

P1

Geometric
XO

Offspring?

P2?
Syntax
Leonardo Vanneschi

Semantics
Geometric Semantic Genetic Programming

33

Impact
Let us assume that we are able to ﬁnd a transformation on thesyntax of an individual whose effect is ball mutation on thesemantic space.

This transformation, if known, would induce a unimodalﬁtness landscape on every problem consisting in matching
input data into known targets (e.g. regressions andclassiﬁcations),
GP should have a good evolvability on those problems, at leaston training data (we are mapping the problem into theCONO).
The same also holds for transformations on pairs of solutions
that correspond to GA semantic crossovers.
Leonardo Vanneschi

Geometric Semantic Genetic Programming34

Is it a dream?
Yes... but turning into reality

Even though with a big drawback (discussed later) those
operators have been defined:
A. Moraglio, K. Krawiec, and C. G. Johnson.
Geometric semantic genetic programming.
In C. A. Coello Coello, et al., editors, Parallel Problem Solvingfrom Nature, PPSN XII (part 1), volume 7491 of Lecture Notes
in Computer Science, pages 21–31. Springer, 2012.

Leonardo Vanneschi

Geometric Semantic Genetic Programming35

Geometric Semantic Crossover [Moraglio et al., 2012]

TXO =
T1

TR

T2
TR

TR = Random function with codomain [0, 1]
Leonardo Vanneschi

Geometric Semantic Genetic Programming36

Geometric Semantic Crossover [Moraglio et al., 2012]
The (only) offspring generated by this crossover has a semantic
vector that is a linear combination of the semantics of the parents
with random coefﬁcients included in [0,1] and whose sum is equal to 1.

Leonardo Vanneschi

Geometric Semantic Genetic Programming37

Geometric Semantic Mutation[Moraglio et al., 2012]

+

TM =

*

T

-

ms
TR1

TR2

TR1 , TR2 = Random functions
Leonardo Vanneschi

Geometric Semantic Genetic Programming38

Geometric Semantic Mutation[Moraglio et al., 2012]

Each element of the semantic vector of the offspring is a“weak” perturbation of the corresponding element in theparent’s semantics.
“Weak” because (TR1 - TR2) is centered in zeroIt’s importance can be tuned by ms.

Leonardo Vanneschi

Geometric Semantic Genetic Programming39

Geometric Semantic Mutation[Moraglio et al., 2012]

It corresponds to ball mutation in the semantic space, so
the fitness landscape it induces is unimodal (we match
each problem consisting in matching inputs into targets
into the CONO problem!).

Leonardo Vanneschi

Geometric Semantic Genetic Programming40

Cool !! But....

Leonardo Vanneschi

Geometric Semantic Genetic Programming41

Geometric Semantic Operators
Moraglio et al. show interesting results on a set of benchmarks, but....
XO(T1, T2) = (T1 * TR) + ((1 – TR) * T2)

At generation 2 (if we use only crossover), all the trees have this shape, so tocreate the next generation:
XO( (T1 * TR1) + ((1 – TR1) * T2), (T3 * TR2) + ((1 – TR2) * T4) ) =(((T1 * TR1) + ((1 – TR1) * T2)) * TR3) + ((1 – TR3) * ((T3 * TR2) + ((1 –TR2) * T4)))
Now assume to take two trees of this shape and apply the crossover togenerate the offspring of generation 3
And assume to iterate this for hundreds of generations!
Leonardo Vanneschi

Geometric Semantic Genetic Programming

42

Drawback of Geometric Semantic Operators
These operators, by construction, always produce
offspring that are larger than their parents, causing a fast
growth in the size of the individuals (proven in [Moraglio
et al., 2012]

This renders them useless in practice.
A solution that has been proposed: “simplification” of theindividuals during the evolution. But….

Leonardo Vanneschi

Geometric Semantic Genetic Programming

43

Our ContributionIn:
A New Implementation of Geometric Semantic GP Applied to
Predicting Pharmacokinetic Parameters.
L. Vanneschi, M. Castelli, L. Manzoni, S. Silva.
Accepted for publication in the EuroGP 2013 Proceedings
Lecture Notes in Computer Science.

We propose a new implementation of Moraglio’s
geometric semantic operators that is efficient and thus
allows us to use them (for the first time) on complex reallife applications!

Leonardo Vanneschi

Geometric Semantic Genetic Programming

44

The New Implementation
We create the initial population as in standard GP and we store the trees.
We create all the random trees that we need to produce the next population.
We store the next population like this.

These are memory references!

Leonardo Vanneschi

Geometric Semantic Genetic Programming

45

Semantics
7.34

8.62

9.51

4.07

9.73 4.29

5.26

1.45

2.92 3.76

5.23

6.24

7.28 1.78

3.26

5.74

2.57 4.67

3.22

6.91

2.64

3.28

5.93

4.29

6.94

7.53

8.53

2.65

4.84

3.56

2.76

9.76

4.37

5.94

2.59

1.85

4.67 3.27

2.57

7.47

Leonardo Vanneschi

Storing also thesemantics of eachindividual allows us tocalculate the fitness
without evaluating thewhole expresson!!

Obtainabledirectly from here.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

.......

Semantics in thenext population

Geometric Semantic Genetic Programming

46

The New Implementation
Before passing to the next generation:

T2 is not used anymore: it can be deleted from memory !

Leonardo Vanneschi

Geometric Semantic Genetic Programming

47

The New Implementation
For producing the next generation:

We create another pool of random trees to produce the next population.
We store the next population in another table of pointers.
We eventually simplify removing trees that will never be used).

Leonardo Vanneschi

Geometric Semantic Genetic Programming

48

The New Implementation – Comp. Complexity
We keep in memory:

maintains a constant size
(but can be simplified)• (a subset of) the initial population• a pool of random trees• a table of memory references

increases in size ateach generation (but canbe simplified)increases in size ateach generation (but canbe simplified)

Cost of evolving a population of n individuals for g generations.
At every generation, we need O(n) space to store the new individuals. Thus, weneed O(ng) space in total. Since we need to do only O(1) operations for any new
individual (since the ﬁtness can be computed using the ﬁtnessof the parents), the time complexity is O(ng).
Thus, we have a linear complexity with respect to population size and number ofgenerations.
Leonardo Vanneschi

Geometric Semantic Genetic Programming49

Video(a movie will be shown here)

Leonardo Vanneschi

Geometric Semantic Genetic Programming

50

Implementation of GSGP

Available for free at:
http://gsgp.sourceforge.net/

Leonardo Vanneschi

Geometric Semantic Genetic Programming

51

The last step: expression reconstruction
At the end of a run, we have to reconstruct the trees, and those trees
are huge, but:
• Usually we just need one individual (the best on training), so we
can do the reconstruction only once.
• We can do it offline, at the end of the run, so that we do not slow
down the evolution

Leonardo Vanneschi

Geometric Semantic Genetic Programming52

PART II
Real-Life Applications

Leonardo Vanneschi

Geometric Semantic Genetic Programming

53

Prediction of Pharmacokinetic Parameters

L. Vanneschi. Improving genetic programming for the predictionof pharmacokinetic parameters. Memetic Computing, 6(4):255–
262, 2014
L. Vanneschi, S. Silva, M. Castelli, and L. Manzoni. Geometricsemantic genetic programming for real life applications. In R.
Riolo, et al., editors, Genetic Programming Theory and Practice
XI, Genetic and Evolutionary Computation, pages 191–209.
Springer New York, 2014

Leonardo Vanneschi

Geometric Semantic Genetic Programming

54

Drug Discovery
Drug discovery is the process by which new candidate
medications are discovered and commercialized

It is an expensive, slow and risky business.

A recent analysis suggests that it costs on average
more than $1 billion to launch a potentially technically
successful drug, and it takes on average 12.5 years.

(source: http://emedicine.medscape.com/article/169814-overview)

Leonardo Vanneschi

Geometric Semantic Genetic Programming

55

The case of Troglitazone• Approved in 1997 as an antidiabetic drug, and seemed set tobecome a global “bestseller”• In 3 years it caused more than 90 verified cases of hepatotoxicity(with consequent serious liver injuries), among which 63 liverfailure deaths• Withdrawn from the market in 2000 by the Food and Drug
Administration (FDA)• It is estimated that this withdrawal costed approximately$136 million(sources: http://emedicine.medscape.com/article/169814-overview and http://84.19.28.94/troglitazone-story)

Leonardo Vanneschi

Geometric Semantic Genetic Programming

56

The case of Troglitazone is not isolatedSince 2000, more than 900 drugs have been reported to causeliver injury, and drugs account for approximately 40% of all
instances of fulminant hepatic failure.

Why do this happens?

Because predicting drugs toxity is:• Difficult• (Very!) Expansive(source: http://emedicine.medscape.com/article/169814-overview)

Leonardo Vanneschi

Geometric Semantic Genetic Programming

57

How the Toxicity of a Potential New Drug is Measured
test animals

Feed all of them slowly increasing
amounts of drug

The total amount of drug fed iscalled Median Oral Lethal Dose
(LD50) and it is nowadays one of
the most accepted measures of
toxicity
Leonardo Vanneschi

Until 50% of them die

Geometric Semantic Genetic Programming

58

Problems with Toxicity Measurements
The sample of cavies has to be statistically significant and there is anextremely large variance in the amount of drug needed to kill a test
animal, so many cavies are needed in order to obtain significant
results.

Furthermore…
Toxicity is only one important (pharmacokinetic) parameter that has
to be known before commercializing a drug!
In this presentation:• Human oral bioavailability• Plasma protein binding level
Leonardo Vanneschi

Geometric Semantic Genetic Programming

59

Oral Bioavailability (%F)• Drugs have to be absorbed from the gut wall and to enter into systemic
circulation in the portal vein.
• Carried by the blood flux, molecules arrive in the liver, where there are somebiochemical processes that try to demolish them.

Oral Bioavailability = The percentage of molecules initially submitted thatexit the liver and enter the blood circulation.
Leonardo Vanneschi

Geometric Semantic Genetic Programming

60

Plasma Protein Binding Levels (%PPB)
The percentage of the initial drug dose which binds plasma
proteins.
This measure is fundamental, because blood circulation is the
major vehicle of drug distribution into human body

Leonardo Vanneschi

Geometric Semantic Genetic Programming

61

Drug Discovery Process• What does the drug have to do?
• Which organs does it have toinfluence?
• What does the drug have NOT to do?
• Which organs does it have NOT toinfluence?
Leonardo Vanneschi

Geometric Semantic Genetic Programming

62

Drug Discovery Process• Decide the desired value of somepharmacokinetic parameters• Find the set of molecules that
optimize them!

Leonardo Vanneschi

Predicting the values ofpharmacokinetic parameters
is crucial for the
success/failure of the drug
discovery process!!

Geometric Semantic Genetic Programming63

Why are these parameters important?
Main reasons for failure in drug development:

Bound
to LD50 !

• clinical safety (black)• efficacy (red)• formulation (green)• bioavailability (blue)
Leonardo Vanneschi

Bound
to %PPB !

Bound
to %F !

• commercial (yellow)• toxicology (grey)• cost of goods (purple)• others (white)

Geometric Semantic Genetic Programming

64

Q.S.A.R. ApproachH=x11 x12 x13 ... x1Mx21 x22 x23 ... x2M...
xN1 xN2 xN3 ..., xNM

y1
y2
...
yN

drugs

molecular descriptors
goal (or target - the value of thepharmacokinetic parameter to estimate)

We look for a function f such that: i: 1 ≤ i ≤ N f(xi1, xi2, xi3, ..., xiM) = yi... and it has to have a high generalization ability !
Leonardo Vanneschi

Geometric Semantic Genetic Programming

65

Bioavailability Results

Leonardo Vanneschi

Geometric Semantic Genetic Programming66

Plasma Protein Binding Level results

Leonardo Vanneschi

Geometric Semantic Genetic Programming67

Toxicity Results

Leonardo Vanneschi

Geometric Semantic Genetic Programming68Why this good results on test data?
The geometrical properties of Moraglio’s operators hold independetly ofthe dataset on which individuals are evaluated !

Leonardo Vanneschi

Geometric Semantic Genetic Programming

69

Controlling Overfitting
Even though geometric semantic operators do notguarantee an improvement on test data at eachapplication, at least...
... they guarantee that the eventual worsening on test data
is limited, and limited of a well defined quantity:• For crossover:the fitness (on test data) of the worst parent• For mutation:
the mutation step ms
Leonardo Vanneschi

Geometric Semantic Genetic Programming70

Prediction of the Unified Parkinson’s
Disease Rating Scale Assessment

M. Castelli, L. Vanneschi, and S. Silva. Prediction of the unified
Parkinson’s disease rating scale assessment using a genetic
programming system with geometric semantic genetic operators.
Expert Systems with Applications, 41(10):4608 – 4616, 2014

Leonardo Vanneschi

Geometric Semantic Genetic Programming

71

Unified Parkinson’s Disease Rating Scale
The Unified Parkinson’s Disease Rating Scale (UPDRS) is a scale thatwas developed as an effort to incorporate elements from existing
scales to provide a comprehensive, efficient and flexible way ofmeasuring and monitoring Parkinson’s Disease (PD)-related disability
and impairment.

For many persons affected by PD, the necessary specialized
medical examinations to estimate the severity of their symptoms
are difficult and invasive and they have to be performed by trained
medical staff. This highlights the need of reliable and accuratecomputational techniques that allow estimating the UPDRS
automatically and effectively.

Leonardo Vanneschi

Geometric Semantic Genetic Programming72

Datasets•

Total-UPDRS: dataset using as target the values of the severity of thegeneral PD symptoms, taking into account:•••

Mentation, Behavior and Mood.
Activities of daily living.
Motor.

It reflects the presence and severity of symptoms, expressing it in arange from 0 to 176, with 0 representing a healthy state and 176 total
disability.
•

Motor-UPDRS: dataset using as target the values of the severity of the
motor symptoms.
The motor section of the UPDRS encompasses tasks such as speech,
facial expression, tremor and rigidity and expresses the severity of therelated symptoms in a range from 0 to 108, where 0 represents a
symptom free state and 108 denotes severe motor impairment.
Leonardo Vanneschi

Geometric Semantic Genetic Programming73

FeatureFeatures in the considered dataset. MDVP stands for (Kay Pentax) Multidimensional Voice Program

Leonardo Vanneschi

Geometric Semantic Genetic Programming

74

Parkinson’s Desease Results
Motor Dataset

Leonardo Vanneschi

Geometric Semantic Genetic Programming

75

Parkinson’s Desease Results
Total Dataset

Leonardo Vanneschi

Geometric Semantic Genetic Programming

76

Comparison with Other ML Methods
Motor Dataset

LIN -> regression (Weisberg, 2005)
SQ -> Least square regression (Seber & Wild, 2003)
RBF -> Radial Basis Function network (Haykin, 1999)
ISO -> Isotonic regression (Hoffmann, 2009)
SVM-1 -> SVM polynomial kernel of degree 1 (lkopf & Smola, 2002)
SVM-2 -> SVM polynomial kernel of degree 2 (lkopf & Smola, 2002)
Leonardo Vanneschi

Geometric Semantic Genetic Programming

77

Comparison with Other ML Methods
Motor Dataset

LIN -> regression (Weisberg, 2005)
SQ -> Least square regression (Seber & Wild, 2003)
RBF -> Radial Basis Function network (Haykin, 1999)
ISO -> Isotonic regression (Hoffmann, 2009)
SVM-1 -> SVM polynomial kernel of degree 1 (lkopf & Smola, 2002)
SVM-2 -> SVM polynomial kernel of degree 2 (lkopf & Smola, 2002)
Leonardo Vanneschi

Geometric Semantic Genetic Programming

78

Statistical Comparison

As a first step, the Kolmogorov–Smirnov test has shown that the data
are not normally distributed. Then, the Wilcoxon rank-sum test for
pairwise data comparison has been used under the alternative
hypothesis that the samples do not have equal medians.
Used significance level was α = 0.01.
Bonferroni correction was used.
Leonardo Vanneschi

Geometric Semantic Genetic Programming

79

Prediction of high performance
concrete strength

M. Castelli, L. Vanneschi, and S. Silva. Prediction of highperformance concrete strength using genetic programming withgeometric semantic genetic operators. Expert Systems with
Applications, 40(17):6856 – 6862, 2013.

Leonardo Vanneschi

Geometric Semantic Genetic Programming

80

The Problem
Concrete is the most-used man-made product in theworld.
Concrete is a composite construction material madeprimarily with aggregate, cement, and water.
Several way of mixing these ingredients, and several
ways of establishing that the concrete will have therequired performance in different situations.
Reliable and accurate techniques that allow modellingthe behaviour of concrete materials are in demand.
Leonardo Vanneschi

Geometric Semantic Genetic Programming

81

Data
The dataset consist in 1028 instances, each of them described by 8variables:

Dataset from:
Yeh, I.-C. Modeling of strength of high-performance concrete using
artificial neural networks. Cement and Concrete Research, 28(12),1797–1808. 1998.
Leonardo Vanneschi

Geometric Semantic Genetic Programming82

Results

Leonardo Vanneschi

Geometric Semantic Genetic Programming

83

Comparison with other ML Methods
Concrete Strength prediction:

Leonardo Vanneschi

Geometric Semantic Genetic Programming84

Prediction of the Relative Position ofComputer Tomography (CT) Slices

M. Castelli, L. Trujillo, L. Vanneschi, and A. Popovic. Prediction ofrelative position of CT slices using a computational intelligencesystem. Applied Soft Computing. Volume 6. Pages 537-542. 2016.
doi:http://dx.doi.org/10.1016/j.asoc.2015.09.021

Leonardo Vanneschi

Geometric Semantic Genetic Programming

85

The Problem
Scanning large parts of a patient's body with computerized
tomography (CT) is common practice in radiology.
The amount of image data resulting from a full body scan varies
between 40MB to more than 1GB, which has to be stored in a medical
picture archiving and communication system (PACS).
A clinician often needs to compare different scans of the same body
region for differential diagnoses or needs to compare disease patterns
in the same body region between similar patients.
When searching for similar disease patterns in a remote PACS it isimpractical to load complete volume sets and then manually navigate
to the relevant body regions. Instead, transferring only the most similar
body parts is more reasonable, secure and ecient. Nonetheless, inboth scenarios it is necessary to determine the relative position of thegiven CT slice within the body.
Leonardo Vanneschi

Geometric Semantic Genetic Programming

86

Integration of GSGP with Local Search
GSGP’s optimization is very effective, but quite slow.
We recently proposed a GSM operator revisited:

𝑇𝑀 = 𝛼0 + 𝛼1 ⋅ 𝑇 + 𝛼2 ⋅ (𝑇𝑅1 + 𝑇𝑅2 )where 𝛼𝑖 ∈ ℜ and𝛼2 corresponds to the original mutation
step ms. Given a training set of n fitness cases, thisdefines system with n linear equations and three
unknowns (𝛼0 , 𝛼1 , 𝛼2 ).
This is an overdetermined multivariate linear fitting
problem, which can be solved using Singular Value
Decomposition (SVD).
Leonardo Vanneschi

Geometric Semantic Genetic Programming

87

New Algorithm Variants• GSGP• GSGP-LS (using GSM-LS)• HYBRID• Run GSGP-LS for the first M generations/ runstandard GSGP afterwards (Best results foundwith M=10)

Leonardo Vanneschi

Geometric Semantic Genetic Programming

88

Data
The data was retrieved from 53500 CT images taken from 74 different
patients (43 male, 31 female).

Each CT image is described by 385 features. The first feature is the
ID of the patient; features 2 – 241 are related to bone structures;features 242 - 385 are related to air inclusions. The last feature is thetarget variable that is the relative location of the image on the axial
axis.
Values are in the range [0; 180] where 0 denotes the top of the headand 180 the soles of the feet.

Leonardo Vanneschi

Geometric Semantic Genetic Programming

89

Data

Leonardo Vanneschi

Geometric Semantic Genetic Programming

90

Comparison with Other Methods

Leonardo Vanneschi

Geometric Semantic Genetic Programming91

Forecasting of Energy Consumption
M. Castelli, L. Vanneschi, and M. De Felice. Forecasting short-term
electricity consumption using a semantics-based genetic
programming framework: The south Italy case. Energy Economics,
47:37 – 41, 2015

M. Castelli, L. Trujillo, and L. Vanneschi. Energy consumption
forecasting using semantic based genetic programming with local
search optimizer. Computational Intelligence and Neuroscience,
Volume 57, 2015. Article ID 971908.
http://dx.doi.org/10.1155/2015/971908.
M. Castelli, L. Trujillo, L. Vanneschi, and A. Popovic. Prediction ofenergy performance of residential buildings: A genetic programming
approach. Energy and Buildings, 102:67 – 74, 2015.
Leonardo Vanneschi

Geometric Semantic Genetic Programming

92

The Problem
The aim of this forecasting task is to predict the energy
consumption at day 𝑡, providing information until day 𝑡−1(one-day ahead forecasting) using the past samples ofthe load and weather information.

Leonardo Vanneschi

Geometric Semantic Genetic Programming

93

Data
Historical energy consumption data and weather information in Italyin the years between 1999 and 2010 have been used to test theperformance of the proposed system.
Data include temperatures, pressure values, wind speed, and other
weather related information.

Data from 1999 to 2006 have been used during the training phase,
while the remaining available data (i.e., from 2006 to 2010) havebeen used to validate the model on unseen data and hence toassess the quality of the forecasting.

Leonardo Vanneschi

Geometric Semantic Genetic Programming

94

Data Provider
TERNA S.p.A. (Rete Elettrica Nazionale) is an Italian electricity
transmission system operator based in Rome, Italy.

With 63,500 kilometres of power lines or around 98% of the Italianhigh-voltage power transmission grid, TERNA is the firstindependent electricity transmission grid operator in Europe and thesixth in world based on the size of its electrical grid.
TERNA is the owner of the Italian transmission grid and responsible
for energy transmission and dispatching.

Leonardo Vanneschi

Geometric Semantic Genetic Programming95

Results

Leonardo Vanneschi

Geometric Semantic Genetic Programming

96

Comparison with Other ML Methods

Leonardo Vanneschi

Geometric Semantic Genetic Programming

97

PART III
Conclusions

Leonardo Vanneschi

Geometric Semantic Genetic Programming98Summary of the contributions• An efficient implementation of geometric semantic
operators, that has allowed us to use them on real-life
applications.

• Excellent results on the studied applications.
• New insights about the generalization ability ofgeometric semantic operators (without the novel
implementation that allowed us to use geometricsemantic GP on these complex real-life problems, thisinteresting property would probably remain unnoticed).
Leonardo Vanneschi

Geometric Semantic Genetic Programming

99

Open issues
The reconstruction of the expression of the best individual,
even though we do it only once and after the termination of
the run, is still an issue:
Individuals after hundreds of generations get so huge that it
may be impossible to reconstruct their entire expression(even though it is possible to get some information about it,such as the features or primitives it uses...).
Models generated by geometric semantic GP are black (orat least “dark gray” - ) boxes!
We are working on this!
Leonardo Vanneschi

Geometric Semantic Genetic Programming

100

All this would not exist without...

Mauro Castelli
NOVA IMS
Universidade Nova de Lisboa

Leonardo Vanneschi

Sara Silva
Faculdade de Ciências
Universidade de Lisboa

Geometric Semantic Genetic Programming101

Thank you!
lvanneschi@novaims.unl.pt

Leonardo Vanneschi

Geometric Semantic Genetic Programming

102