Journal of Robotics, Networking and Artificial Life, Vol. 2, No. 2 (September 2015), 107-110

On the Effects of Epigenetic Programming on the Efficiency
of Incremental Evolution of the Simulated Khepera Robot
Yasuto Nishiwaki, Naoki Mukosaka, Ivan Tanev, and Katsunori Shimohara

Graduate School of Science and Engineering, Doshisha University,
1-3 Tatara-Miyakotani, Kyotanabe, Kyoto 610-0321, Japan
E-mail: nishiwaki2012@sil.doshishsa.ac.jp, mukosaka2012@sil.doshisha.ac.jp, itanev@mail.doshisha.ac.jp,kshimoha@mail.doshisha.ac.jp
www.doshisha.ac.jp

Abstract
We present the results of our work on epigenetic programming (EP) and its application to navigation of mobile
cleaning robot. We verify the effect of genetic switches and the feasibility of incorporating histones. The results
show individuals applying Lamarckian EP have better quality and evolve faster than those in canonical geneticprogramming. Such an improved computational effort of evolution, however, is achieved at the cost of somehow
decreased computational performance due to the additional overhead of manipulating the genetic switches. Our
work could be seen as a verification of the accelerating effect of histones on adaptation and evolution in nature.
Keywords: Epigenetic Programming, Genetic Programming, Epigenesis, Histone.

1. Introduction
The objective of our study is to develop an approachof Epigenetic Programming1-2 (EP) and to verify thefeasibility of incorporating histones (the family ofproteins which DNA is wrapped around) in genotype
from both the computationally and natural perspectives.
Epigenesis refers to a changeable gene expression (andconsequently – a variable phenotype) as a result of theinteraction of genotype and surrounding environment(food, stress, toxins, radiation, etc.). We intend to mimic
the recent discoveries in molecular biology that suggestthat epigenesis plays an important role in evolutionary
adaptation of species.

In our previous study1, we verified the beneficial
effects of histones on the quality of solutions obtained
via Genetic Programming (GP). Out approach impliedthat the modifications to histones are implemented after
the completion of GP, and these modifications wereconsidered as a local search (hill-climbing) in theproximity of the genotypic space of the best-evolved
individuals. No modifications to histones in due courseof evolution were assumed in our previous work.

Published by Atlantis Press
Copyright: the authors
107

Yasuto Nishiwaki, Naoki Mukosaka, Ivan Tanev, Katsunori Shimohara

simulated in a Webots4 mobile robot simulation
environment.
The system architecture is shown in Figure 1.

2. Mechanism of EP
2.1. The mechanism of modifying the histoneswitches
We introduce histones as genetic on and off“switches” that modify the gene expression byactivating and deactivating the nodes (andcorresponding sub-trees) in the tree representations (i.e.,the “genotype”) of the evolved individuals in GeneticProgramming (GP). In canonical GP the abilities ofindividuals evolve as a result of modifications (viacrossover and mutation) to the genes alone. In theproposed EP this genetic modifications are superposedwith the modifications of histones to facilitate evenbetter evolutionary adaptation to the environment.
Moreover, in some cases the modification to histone
alone – i.e., by enabling a disabled code (or vice versa)– would achieve a better performing individual without
the need to spend extra time for computationally costly
evolution of a new genotype. In this study, we use
Lamarckian EP (LEP) as elaborated below.
2.2. The mechanism of LEP

Fig. 1. System architecture

The evaluation of the fitness of the evolved
controller is accomplished in following four steps:(i)

LEP is an epigenetic approach in which themodified genetic switches (histones) are stored back in
the genotype (i.e., inherited). The Lamarckism implies
that the modifications to the histones are inherited backinto the genotype of the evolving individuals. LEP
evaluates the fitness of individual after applying
changes to histones, which, in turn, modifies the state of
the genetic on and off switches. In such a way, bychanging the expression of the genes (rather thanchanging the genes) by these switches, it could bepossible to obtain a different phenotype, which
eventually features a better fitness value of the evolvedindividuals. Furthermore, we believe that is possible toevolve better individuals as a result of crossover andmutation operations that operate over the space ofgenotype superposed by histones.
3. System Architecture
In this study, we use the XML-based genetic
programming framework3 (XGP) to maintain thepopulation of evolving individuals and to performgenetic operations (selection, crossover and mutation)on them. The evolved individuals are controllers of asimulated Khepera vacuum cleaning robot. The latter is

XGP sends the genotype of the controller (asXML-text) for evaluation to Webots via UDP
channel,(ii) Using XML parser, Webots parses the received
controller into a DOM-tree,(iii) For each time step of simulation, Webots evaluates
the DOM-tree, and based on current perceptions(sensory information) of the simulated bot, decides
its current action (e.g., moving forward, moving
backward, turning left or turning right). Webots
applies the currently issued command on the robot
and updates its speed and orientation, which, inturn, defines the position, orientation and thevelocity of the bot for the next time step.
(iv) Upon the completion of simulation, Webots
returns (via UDP channel) the fitness value (i.e.,
the area on the floor that was cleaned by the robot)
to the XGP.
The controllers of the robot are evaluated for anumber of time steps, given to the robot to clean aroom, starting from a given starting position in two
consecutive sample 2D scenes – (i) without- and (ii)with obstacles, respectively, as shown in Figure 2.

Published by Atlantis Press
Copyright: the authors108

On the Effects of Epigenetic Programming

investigate their abilities to adapt to the “new”environment. Because of changing environment, thecontrollers would need to evolve new features in orderto perform well in it. We believe that individual used
applying LEP can adapt to the new environment by justswitching some of their genes on and off instead ofevolving new genotype from scratch.
5. Experimental Results
Fig. 2. Experimental setup consisting in two sample scenes:
without- (left) and with obstacles (right), respectively. Therobot evolves the ability to clean these two rooms
consecutively, at two consecutive stages of an incrementalevolution.

4.

5.1. Result of one-staged evolution
The results of applying LEP or GP on individuals
evolved are shown in Figure 3.

Experiments

To verify the feasibility of incorporating histones,
we performed two experiments. These two experiments
were intended to allow us to compare the efficiency ofevolution via LEP and canonical GP, respectively.
4.1. Exploring evolution characteristic of LEP
In this experiment, we explore how histones
influence the efficiency of evolution. The controller ofthe robot is evolved in the first stage (i.e., room withoutobstacles) of LEP under the same conditions as GP. We
believed that introducing histone would facilitate afaster evolution in that it would require lower
computational effort (i.e., would feature a reduced
number of evolved generations).
4.2. Two-staged incremental evolutionDuring the first stage of the incremental evolution,
the robot evolves via GP its ability to efficiently clean
the room without obstacles. Then, the best controllers
are used to seed the second stage of the evolution which
involves an evolution (via GP) of the ability to clean theroom with obstacles. The same two-staged incremental
evolution is used applying LEP with histonemodification at both stages.
After that, the best controllers of second stage areevaluated again in the room without obstacles (i.e., thesame environment that is used during the first stage) toFig. 3. Fitness convergence of LEP (blue) and GP (red),respectively. The maximum number of generations is 100. The
number of evaluations per one generation of individuals
applying LEP is two times as many as GP.

As Figure 3 indicates, the controllers, evolved via
LEP have better fitness and evolve faster (with lower
number of generations) than canonical GP. On the otherhand, the average complexity of genotype (in number ofnodes in their DOM-trees) is higher in LEP, which, inturn result in an increased computational overhead
because of slower evaluation of these genotypes. Thisfinding implies that the improvement of computational
effort due to the incorporation of histones in LEP comesat the cost of some degradation of computationalperformance. This degradation, however, is rather
negligible, because, in the considered application ofLEP, the runtime, needed to simulate the physics of theKhepera robot is much longer than the time spent forevaluating the DOM-tree of the genotype.

Published by Atlantis Press
Copyright: the authors
109

Yasuto Nishiwaki, Naoki Mukosaka, Ivan Tanev, Katsunori Shimohara

5.2. Result of two-staged incremental evolution
In second stage, even if there is no difference in theefficiency of the first stage, performance of controllers
applying LEP was better than GP. LEP’s individual
tended to live but GP’s individual easy to be weeded out
difficult stage. However, some individuals tended to not
adapt in first stage when the best individuals in thesecond stage are returned.
6. Discussion
The experimental results suggest that introducing
histones as genetic switches facilitates a faster evolutionof a simulated Khepera robot. The simulated evolution
is relatively fast anyway, and, features about the same
runtime overhead as the adaptation via changing ofhistones. In the real biological world however, theevolution of one generation requires years of time,
while the effect of modifications to histones could beobserved much sooner. Therefore, we believe that
histones incorporated in the genotypes are capable offacilitating the biological evolution.
In addition, in latter experiment, we discovered thatsome of the controllers could not adapt well to the old“new” environment (room without obstacles), because
the parts of their respective genotypes
that areresponsible for dealing with that environment, was lostduring the second stage of evolution (in a room withobstacles). Therefore, it could be interesting toinvestigate such a genetic mechanism during the second
stage of LEP that could protect the useful features (e.g.,ability to move and clean a room without obstacles)
evolved at the first stage of evolution, from thedestructive effect of crossover and mutation operations.
One possibility is to allow the inactivated histones torepel the crossover and mutation operations, in order topreserve the inactivated code from destruction. This
code could be deactivated later, when an old “new”
environment arises.

Also, we verified the effect of epigenesis on theefficiency of evolution of controllers of simulated
Khepera cleaning robot in two experiments. From theresults of the former experiment we concluded that
applying LEP facilitates an earlier adaptation comparedto canonical GP. The results of the latter experiment with two-staged incremental evolution – indicate thatusing LEP contributes to the efficiency of evolution toold “new” environment. We think these results suggestthat histones could be seen as a mechanism to “store”
dormant abilities once needed to deal with challenging
environments. These abilities could be activated again
when the organisms face “new” environments that havebeen already explored in their evolutionary past.
References
1. Y.Nishiwaki, I.Tanev, and K.Shimohara: Epigenetic
Programming and its Application to Mobile Robot, Int.
Conf. on Humanized Systems 2013, pp.66-68, September
2013
2. I.Tanev and K.Yuta: Epigenetic programming Genetic
programming incorporating epigenetic learning throughmodification of histones, Information Sciences, p13(2008)
3. I.Tanev:
DOM/XML-based
portablegenetic
representation of the morphology, behavior andcommunication abilities of evolvable agents, Artificial
Life and Robotics, 8:52-56,2004.
4. O.Michel, Webots: Professional mobile robot simulation,
Int. J. Adv. Robot. Syst, 1, 39–42 (2004).

7. Conclusion
We proposed an approach of LEP and verified thefeasibility of incorporating histones. In order toimplement histone, we introduced genetic “switches”
that modify the gene expression by activating anddeactivating the nodes in the tree representations (i.e.,the “genotype”) of the evolved individuals in GP. In ourapproach we propose LEP in that the modified genetic
switches are inherited back in the evolving genotypes.

Published by Atlantis Press
Copyright: the authors
110