A Parallel and Distributed Semantic Genetic Programming System

Bernardo Galvão & Leonardo Vanneschi

Nova IMS

The basics

• Island Model

2

Genetic Programming (GP)

• Evolutionary writing of a program
• Individuals can be represented as trees
• A program can be a mathematical function (this case) or even computer programming instructions

3

Image Source

Genetic Programming (GP)

Standard Crossover

• Select a random crossover point in each of the parents
• Pass and substitute the resulting subtrees

4

Image Source

Genetic Programming (GP)

Standard Mutation

• Select a random mutation point
• Generate a random subtree (usually with maximum depth 6)

5

Image Source

Geometric Semantic Genetic Programming (GSGP)

6

Semantics: vector of outputs of an individual (i.e. function), where each element of this vector represents the output of a training instance.

GSGP only uses with different crossover and mutation operators!

7

Geometric Semantic Genetic Programming (GSGP)

GS Crossover

• Take both parents entirely
• Add nodes “around” them according to:

• Equates to a geometric mean of the semantics of the parents

8

Geometric Semantic Genetic Programming (GSGP)

GS Mutation

• Take entirety of unique parent
• Add nodes “around” it according to:

• Equates to a ball mutation in the semantic space

9

where R1 and R2 are random real functions with codomain [0,1]

Island Model

• It’s a parallel and distributed form of genetic programming in which the population is distributed over subpopulations.
• Subpopulations evolve in parallel and synchronize in prefixed migration instants, in which they exchange individuals.
• Migration takes place in a ring configuration.
• The best individuals in the origin subpopulation replace the worst in the destination subpopulation (best-to-worst)

10

Image Source

Island Model

• Traditionally a single flavour of GP is ran for all subpopulations.

11

Image Source

What if each subpopulation ran a different flavour of GP?

Multi-Population

Hybrid

Genetic Programming (MPHGP)

• Proposition
• The model
• Evaluation methodology

12

• Background
• GSGP
• Great optimization power and generalization ability
• Strict growth of individuals given that parents are taken for their entirety
• Linearly if using GS Mutation
• Exponentially if using GS Crossover
• Great sizes of these solutions impact negatively readability and interpretability
• GP
• Ability to find more parsimonious solutions
• Sometimes faces the bloat problem
• Relatively less optimization power

13

Proposition

• By means of a hybrid multi-population system,
• bring down the size of GSGP solutions.

14

The model

15

2-Population Hybrid Genetic Programming (MPHGP-2)

16

Multi-Objective GP

​

(MOGP)

Geometric Semantic GP

​

(GSGP)

• Optimizes for size and training error (NSGA-II)
• Uses standard variation operators

• Optimizes for training error only
• Uses geometric semantic variation operators

MOGP migrants

GSGP migrants

• The datasets

17

18

sub-GSGP

sub-MOGP

200 indivs

200 indivs

400 individuals

MOGP

400 individuals

GSGP

400 individuals

The results

• Cosine operator
• 2-subpopulation MPHGP (MPHGP-2)
• Introspection of MPHGP-2
• Increasing number of subpopulations

19

Cosine operator

20

• The cosine operator is included among addition, subtraction, multiplication and protected division.
• It generally helps in optimizing the fitness function while reducing size of GSGP.

21

Cosine Operator - Bioavailability dataset

22

Legend: *-β: without the cosine operator

Next subsection

toBoxplot()

2-Population Hybrid Genetic Programming

​

(MPHGP-2)

23

MPHGP-2

24

Next subsection

MPHGP-2

25

Next subsection

• Migration Rate: Percentage of subpopulation size determining how many individuals migrate.

​

• Migration Frequency: How many generations before migration taking place.

​

Except where noted, migration frequency is 50 and migration rate is 0.15.

​

MPHGP-2 - Bioavailability dataset

26

Next subsection

toBoxplot()

MPHGP-2 - Introspection

27

What really happened

28

sub-GSGP

sub-MOGP

here

and here

• Migration Rate: Percentage of subpopulation size determining how many individuals migrate.

​

• Migration Frequency: How many generations before migration takes place.

​

MPHGP-2

• Migration rates have almost no impact.
• Tested across migration rates {0.05, 0.15, 0.25, 0.35} and migration frequencies {25, 50, 100}.
• Across 5 datasets for 30 independent runs. Thus, at least 4*3*5*30 = 1800 runs were performed just for MPHGP-2.
• Migration frequency matters. But why?

​

• Both subpopulations need to be on par in terms of fitness.
• Migration frequency determines the moment of the first migration at which the subpopulations may be on par.

29

MPHGP-2 Introspection - Bioavailability dataset

30

Next subsection

MPHGP-2 Introspection - Concrete dataset

31

Next subsection

MPHGP-2 Introspection - Energy dataset

32

Next subsection

f = 25

Increasing number of subpopulations

MPHGP- {2, 4, 8, 20, 40}

33

Increasing number of subpopulations

34

Next section

Increasing number of subpopulations - Energy dataset

35

Next section

toBoxplot()

Right, running times!

36

Closing remarks

• Caveats
• What was learned
• Future work

37

Caveats

• Only Geometric Semantic Mutation was performed and tested. This greatly prevents exponential growth of individuals, but was also what allowed for more experiments.
• Number of elite survivors was too high, especially in subpopulations of lower size. This was to maintain a clean inference without any other parametric interference.
• It is worth a re-run in the cases of number of subpopulations = {8, 20, 40} with only one elite survivor

38

What was learned

• While new, less size-growth dependent, geometric semantic operators are yet to be discovered, it is still possible to find comparable and parsimonious solutions.
• A hybrid system, especially when running different selection methods, need special attention to put the subpopulations on par, in terms of training error.

39

Future Work

• Implement more parsimoniousness-oriented GP algorithms into the hybrid system
• Different migration directions
• Implement mathematical simplification algorithms.

​

​

Allow me to slide this here: nodevo, an implementation in Rust

40

Thank you! Questions?

bgalvao

burnie093

41

Appendix

42

Aiding slides (mainly boxplots) are here

Cosine Operator - Bioavailability dataset

43

Legend: *-β: without the cosine operator

Next subsection

toLines()

Cosine Operator - PPB dataset

44

Legend: *-β: without the cosine operator

Next subsection

toLines()

Cosine Operator - Toxicity dataset

45

*-β: without the cosine operator

Next subsection

toLines()

Cosine Operator - Concrete dataset

46

Legend: *-β: without the cosine operator

Next subsection

toLines()

Cosine Operator - Energy dataset

47

Legend: *-β: without the cosine operator

Next subsection

toLines()

MPHGP-2 - Bioavailability dataset

48

Next subsection

toLines()

MPHGP-2 - PPB dataset

49

Next subsection

toLines()

MPHGP-2 - Toxicity dataset

50

Next subsection

toLines()

MPHGP-2 - Concrete dataset

51

Next subsection

toLines()

MPHGP-2 - Energy dataset

52

Next subsection

toLines()

Note: f = 25

Increasing number of subpopulations - Bioavailability dataset

53

Next section

(ﾉ◕ヮ◕)ﾉ*:･ﾟ✧

toLines()

Increasing number of subpopulations - PPB dataset

54

Next section

(ﾉ◕ヮ◕)ﾉ*:･ﾟ✧

toLines()

Increasing number of subpopulations - Toxicity dataset

55

Next section

(ﾉ◕ヮ◕)ﾉ*:･ﾟ✧

toLines()

Increasing number of subpopulations - Concrete dataset

56

Next section

(ﾉ◕ヮ◕)ﾉ*:･ﾟ✧

toLines()

Increasing number of subpopulations - Energy dataset

57

Next section

(ﾉ◕ヮ◕)ﾉ*:･ﾟ✧

toLines()

Increasing number of subpopulations - Bioavailability dataset

58

Increasing number of subpopulations - PPB dataset

59

Increasing number of subpopulations - Toxicity dataset

60

Increasing number of subpopulations - Concrete dataset

61

Increasing number of subpopulations - Energy dataset