71
1 INTRODUCTION
Neuroevolution is a combination of two different
methods: artificial neural networks (ANN) and
evolutionary algorithms (EA). Neuroevolutionary
methods are part of intelligent computational
methods (Kwaśnicka, 2007) capable of finding
solutions to complex tasks by means of artificial
neuralnetworksarisingfromevolution(Lehmanand
Miikkulainen, 2013). This combinat
ion gives the
advantage of flexibility and adaptability, which
allows to adjust the computational structures to the
dynamicallychangingconditionsencounteredduring
ship maneuvering and are intensively studied and
implementedindifferentfieldsofscience,including:
robotics(Haasdijketal.,2010)(Leeetal.,2013);
automationprocesses(Stanleyetal.,2005);
multi‐agentsystems(Nowaketal.,2008);
designinganddiagnostics(Larkinetal.,2006)and
ma
nyothers.
Neuroevolutionary algorithms are successful
methods for optimizing neural networks topologies,
especially in dynamic continuous reinforcement
learning tasks. Their significant advantage over
gradient‐basedalgorithmsisthecapabilitytomodify
networktopol
ogiesalongwithconnectionweights.
The operation of ship maneuvering on confined
waterisessentialtothesafetyofpeople,equipment,
cargoandtheenvironment.Increaseofcomputational
power of electronic devices allows to implement
complex algorithms into advanced decision support
systemsalsointhefieldofmarinenavigation.
Suchasystemshouldincludethefollowing ma
in
functions:
ability to analyze the navigational situation in
continuousmode,
warningbeforethedangerous situation maytake
place, e.g. possible collision or exit from a
particularlimitedareainanundesirabledirection,
Indirect Encoding in Neuroevolutionary Ship Handling
M.Łącki
GdyniaMaritimeUniversity,Gdynia,Poland
ABSTRACT:Inthispapertheauthorcomparestheefficiencyoftwoencodingschemesforartificialintelligence
methods used in the neuroevolutionary ship maneuvering system. This may be also be seen as the ship
handlingsystemthatsimulatesalearningprocessofagroupofartificialhelmsmen‐aut
onomouscontrolunits,
createdwithanartificialneuralnetwork.Thehelmsmanobservesinputsignalsderivedformanenfironment
and calculates the values of required parameters of the vessel maneuvering in confined waters. In
neuroevolutionsuchunitsaretreatedasindividualsinpopulationofartificialneuralnetworks,whichthrough
environmentalsensingandevolutionaryalgorit
hmslearntoperformgiventaskefficiently.Themaintaskof
thisprojectistoevolveapopulationofhelmsmenwithindirectencodingandcompareresultsofsimulation
withdirectencodingmethod.
http://www.transnav.eu
the International Journal
on Marine Navigation
and Safety of Sea Transportation
Volume 12
Number 1
March 2018
DOI:10.12716/1001.12.01.07
72
providing transparent information that can be
used in co‐operation with local authorities and
otherauxiliaryunitsofthearea,
abilitytofindregularitiesandpatternsincomplex
multi‐stagenavigationaltasks.
All these requirements may be fulfilled with
neuroevolutionarymethods.
The basic concept of a pattern‐finding
task is
presentedinfigure1.
Figure1. Exploiting regularities on restricted water in a
pattern‐findingtaskexample.
Through continuous learning process, the system
shall predict the vessel position and state of the
environmentafterspecifiedtime interval as accurate
aspossibleincomparisontofinalrealpositionofthe
ship. It is possible to calculate a probable position
when there is a simulation model of the vessel
available.
It is required that simulation model
includes the equations and coefficients for wind,
currentandwaves.Butinmostcasessuchadvanced
non‐linear simulation model is not available. And
again, a good solution for this problem is
neuroevolution.
2 NEUROEVOLUTIONWITHDIRECTENCODING
Neuroevolutionisabletofinda
solutionofacomplex
and dynamically changing task with ANN created
andmodifiedwithEA.
InneuroevolutionANNistreatedasanindividual
in a population of multiple networks. With direct
encodingapproach the basictopologiesof theinitial
populationarerandomlydeterminedatthebeginning
of learning process. Each individual
begins the
process of finding a solution with the same starting
parameters. The action of each individual is usually
assessedwiththereinforcementlearningalgorithms
(Stanley et al., 2005) and evolutionary stage of the
systemshallselectindividualsbestsuitedtothetask
during selection stage, which determines the whole
populationtoimproveitsgeneticmaterialovertime.
Evolutionary stage of the system consist three
mainprocesses:
selectionofthebestindividuals,
reproduction (with cross‐over and mutation sub‐
processes),
replacement (offspring replaces worst
individuals).
The neuroevolutionary method with direct
encoding of neural network topology has been
implemented
inearlierworksoftheauthor,withthe
modifiedNEATalgorithm(Figure2).
NEAT (NeuroEvolution of Augmenting
Topologies) adjust the topology of ANN’s with EA
(Stanley and Risto, 2002) gradually to given task,
allowstoobtainasetofANN’sthatarebestfittedto
thistask.
Each node represents
a neuron that produces a
realvaluebetween0and1asaresultofnormalized
weighted sum of its inputs. Normalization of
weightedsumisperformedwithsigmoidfunction,as
inEquation1.
1
1
j
j
j
S
o
e
(1)
where:
o
j–outputvalueofanneuron,
S
j–weightedsumofinputvaluesxnjwithweightswnj,
–slopecoefficient,
j–bias.
Addingthebiassignalofconstantva lue1,allows
to shift the output value of the activation function.
Influenceof bias may be adjusted through changing
weight of this signal, when the mutation stage is
performedinevolutionaryprocessduringcreationof
anoffspringinthereproductionstage.
1
2
i1 i2 i3
o1
i2
1
0.02
2
i1
1
‐0.11
4
i3
2
0.9
5
1
2
‐1.0
9
2
o1
0.52
12
‐ Yes ‐ ‐ ‐
i1
o1
‐0.4
1
‐
From
To
Weight
Innov.No.
Disabled?
4
2
1
Inputs
Nodes
Outputs
i4
Figure2. An example of direct encoding of an artificial
neural network topology (phenotype) from a connection
genome(genotype)inNEATmethod
73
Inthisstagetwobestneuralnetworksarechosen
anditsgeneticmaterialiscrossed‐overtocreatetwo
newindividuals.Cross ‐overofdisparatetopologiesis
processed in a meaningful way by pairing up genes
withthe same historical markings, calledinnovation
numbers. With this approach the offspring may
be
formedinoneofthreeways:
In uniform crossover, matching genes are
randomly chosen for the offspring genome, with
higherprobabilityforbetterfittedparent.
In blended crossover, the connection weights of
matchinggenesareaveraged.
Inelitecrossoverdisjointsandexcesses are taken
from more
fit parent only, all redundant genes
from less fit parent are discarded. All matching
genesareaveraged.
Genes that do not match with the range of the
otherparent’sinnovationnumbersarecalleddisjoints
(when they occur within the genome) or excesses
(whentheyoccuroutsideofthegenome).
These three
types of crossover were found to be
most effective in neuroevolutionary algorithms in
comparisontoothercrossovermethods(Stanleyand
Risto,2002).
Genes that have been disabled in previous
generationshave asmall chance of being re‐enabled
during new offspring creation, allowing ANNs to
makeuseofoldersolutions
onceagain(Łącki,2012).
Evolutionary neural network can keep historic
trails of the origin of every gene in the population,
allowing matching genes to be found and identified
even in different genome structures. Old behaviors
encodedinthepre‐existingnetworkstructurehavea
chance to not to be destroyed
and pass their
properties through evolution to the new structures,
thus provide an opportunity to elaborate on these
originalbehaviors.
Thenumberofinputsandoutputsisfixed.During
evolution, in mutation stage, the number of internal
neurons and connections may change. In classic
NEATmethodthenumberofnodes
andconnections
may only increase over time, with possibility to
temporarydisabletheconnection.Thisguarantiesto
transfer learning experience from ancestors to new
offspring and fast learning of new tasks for new
population but it may be disadvantageous in such
dynamic environments as ship maneuvering in
restricted waters. In this
case an experience of old
populationmaybeinsufficientanditslearningability
toslow, due to sizeofexperiencedANN’s.Through
mutation, the genomes in modified NEAT will
graduallygetlargerforcomplextasksandlowertheir
size in simpler ones. Genomes of varying sizes will
result, sometimes with
different connections at the
samepositions.
Historical markings represented by innovation
numbers allow neuroevolutionary algorithm to
perform crossover operation without analyzing
topologies. Genomes of different organizations and
sizes stay compatible throughout evolution, thus
allowingthem to interchange genes in a meaningful
way. This procedure allows for used method to
increase complexity
of the structure while different
networksstillremaincompatible.
During elite selection process the system
eliminates the lowest performing members of every
specializedgroupofindividualsfromthepopulation.
In the next step the offspring replaces eliminated
worst individuals. Thus the quantity of the
population remains the same while its
quality shall
improveaccordingtoassumedgoalsandrestrictions
ofthetask.
3 NEUROEVOLUTIONWITHINDIRECT
ENCODING
First effective indirect encoding of artificial neural
networks, called Cellular Encoding,was proposed
by Gruau in his PhD thesis (Gruau, 1994). In this
method each neuron was represented by a cell
connected to other
cells. Each cell was able to
duplicate in parallel or serial connection of its two
offspring. In that approach the neural networks can
be generated and developed with modularity.
Modular structure is made of several subnetworks,
arranged in a hierarchical way. In some cases the
samesubnetworkcanberepeated.
Generallyinindirectencodingagenomespecifies
how to build a topology. It allows to create more
compact representation of genes in comparison to
directencodinggenomes.
The general set of instruction include commands
thatallowtocreateatopologyinameaningfulway,
i.e.:
Splitconnection,
Addconnection,
Addnode,
Copyconnection,
Removeconnection.
The weights of evolved neural networks
architectures are trained using backpropagation
method.
4 INPUTSANDOUTPUTSOFTHENETWORKS
Input and output signals of ANN’s must be
determinedatthebeginningofdesigningphaseofthe
system.Propersetofsignals
consideredinthemodel
iscrucialforefficientperformanceofthemethodand
foritsfidelityandaccuracyincomparisontothereal
navigationalsituation.
Inputsignalsinthesystem,withthreedegreesof
freedomofthevesselmovement,areasfollows:
Ships’courseoverground,
Ships’angularvelocity,
Ships’speedoverground,
Ships’position,
Angleandvelocityofacurrent,
Angleandvelocityofawind.
Mainpropellerrevolutions(currentandpreset),
Rudders’deflection(currentandpreset).
Infutureresearchothersignalsfromenvironment
maybetakenintoaccount,i.e.waves,cargo,
trimand
roll.
74
Outputsignals of ANNs generates the values for
steeringthevessel:
rpmofmainpropeller,
rudders’deflection.
Alloftheinputandoutputsignalsarenormalized
andencodedasrealvaluesbetween0and1.
Computational flexibility and ability to adapt a
network topology to a given task
allows to design
complexsetsofinputsandoutputsofANN’s.
This is a very sophisticated neuroevolutionary
method that can deal with premature convergence
that preserves diversity and gradual complexity of
exploredsolutions.
Each group has separate ranking list and
individuals compete only within their own group.
This approach requires
much more memory
allocation for higher amount of genetic material but
eliminates unnecessary influence of unwanted input
signalstooutputvalues.
Performance of each individual is measured in
defined time interval and its fitness value is
calculatedasasumofcollected rewards (positiveof
negative values) using Reinforcement Learning (RL)
algorithms. The rewards in RL are determined
arbitrarilybysystemdesigneroruserandtheir values
may depend on actual overall performance of the
population.
In the evolution process, the system selects the
individualsbestsuitedtothetaskduringtheselection
stageandinsertstheirgeneticmaterialinplace
ofthe
worstperformingindividuals.
In this case the individuals with the least cost
criteria fitness values are more likely to reproduce
theirgeneticmaterialinnextgeneration.
The input signals have been divided into two
groups–environmentalsignalsandsteeringsignals.
Group of environmental signals consist all data
incoming
from vessels surroundings (i.e. winds and
currentsspeedanddirection)whichcreatesaninput
statevectorforthesystem.
Implementationofmathematicalmodelofwindto
the motion control in neuroevolutionary ship
handling system increases its performance and
robustnessinsimulatedenvironment.
The smaller the speed and draft of the
ship, the
greater the influence of wind. Of course, the size of
the side surface exposed to wind is essential to the
ships movement. Under pressure of wind force,
depending of the ships’ design (location of the
superstructure, the deployment of on‐board
equipmentandcargo,etc.)shetendstodeviate
from
thecourse,withthewindorintothewind.
Whentheshipmovesforwardthecenterofeffort
of the wind (wind point, WP) is generally close to
amidships, away from pivot point (PP). This
differencecreatesasubstantialturningleverbetween
PP and WP, thus making the ship,
with the
superstructuredeploymentatstern,toswingthebow
intothewind.
Forshipmovingforwardtherearedefinedterms
of relative wind speed V
rw and angle of attack
rw
(Isherwood,1973)
.Windforcesactingonsymmetrical
ship are in general calculated from data as ship’s
overall length, surfaces affected by the wind, air
density and coefficients calculated from available
characteristics of ships model, i.e. from wind loads
data of Oil Companies International Marine Forum
(OCIMF,1977).Thisorganizationidentifiessafetyand
environmental issues facing oil tankers, barges,
terminals and offshore marine operations, and
developsandpublishesrecommendedstandardsthat
serve as technical benchmarks for regional and
worldwideexploitation.
Additional forces that affect ships movement are
waterflowsfromwatercurrent.Inthiscasethewater
movesinrelation to the bottom of
ariver,sea or an
ocean.
Underthepressureofacurrentashipisdrifting
together with the water, relative to the ground and
anyfixedobjects.Whentheshipismovingincurrent
thespeedovergroundisaresultantvelocityofspeed
ofthevesselandthe
velocityoftheseacurrent.
Steeringsignalsconsistdatathatmaybechanged
by a user of the system (i.e. a navigator or a
commander on the bridge). Steering signals include
propellersrevolutions(orthrust)andruddersangles.
All these input signals affect ship’s movement
whichcreatesanewstateof
theenvironmentwiththe
movingvesselinit.
Atthesametimethesimilarnewstateparameters
arebeingcalculatedintheneuroevolutionarysystem,
regarding the same input signals. The result of
calculations provides substantial information for the
systemthatallowstoelaboratethequalityofcreated
ANN’sandoverall
performanceofwholepopulation.
During evaluation the ranking of ANNs it created
and the best networks are stored for future
exploitation.
5 THEEXPERIMENTALRESULTS
For the purpose of a ship movement simulation an
applicationhasbeencreatedbytheauthor(Figure6).
Figure6. Anapplicationfor testingbehaviorof simulation
models of different vessels in water current and windy
environment
75
Thedesignedapplicationallowstochoosespecific
model of the vessel, to set a starting parameters of
navigational situation in restricted waters, including
placementofobstacles,settingspeedanddirectionof
a wind and a water current, and run a simulation
with observable environmental data and ships
parametersandcharacteristics
thatcanbesavedtoa
fileandanalyzedofflineafterthesimulation.
Two simulation models of ships with three‐
degrees‐of‐freedom had been usedin the system for
the purpose of systems performance test. Main
parametersofshipshasbeencomparedintable1.
Table1.Mainparametersofsimulationshipmodels.
_______________________________________________
NameBlueLady CapeNorman
_______________________________________________
TypeVLCCContainership
Scale1:241:1
Length13,78[m] 175[m]
Beam2,38[m]26,5[m]
Draft0,86[m]14,2[m]
Capacity/Tonnage 22,83[T]1504[TEU]
Max.speed3,1[kn]20,4[kn]
_______________________________________________
The sets of output data of ANN’s has been
calculated and recorded during task evaluation in
every generation as the results of simulation. The
populationconsists 100ANNs.Theinitialcontent of
eachgenomeisdeterminedrandomlyfromavailable
setofinstructionswithaspecificsetofrules.
Figure7. The comparison of two encoding methods in
simulationof thecontainership maneuvering inrestricted
area
The simulation example presents the results for
400 generations (Figure 7). The routes of the best
helmsmen of two different encoding methods are
shown. These simulation results prove a good
performance of learning process of a single output
neuralnetworkforbothmethods.
Table2. The time of reaching a goal for two different
encodings.
_______________________________________________
Encoding Avg.time Stddev. ofavg.time
_______________________________________________
Direct 00:28:13 00:09:25 33,4%
Indirect 00:21:01 00:02:09 10,2%
_______________________________________________
The average time of reaching a goal for two
differentencodingmethodsispresentedintable2.
Standard deviation of goal reaching time is
significantlygreaterfordirectencoding,regardingits
greaterrangeofpossiblepredictedspeedvalues.
Thesetworoutesillustratesthatlearningspeedin
neuroevolutionaryalgorithmsstrictlydependson
the
encoding method. Furthermore the directly encoded
population in modified NEAT method adopts faster
tonewsuddenchanges duetogreaterchangesinan
offspring genomes. But on the other hand, the
indirectly encoded population has ability to learn
every individual during its lifetime and is able to
reactto
newstatesrelyingonlearnedpatterns.
6 REMARKS
Neuroevolutionary ship handling system with
indirectencodinghasproperties thatdistinguishesit
fromdirectencodingsystem:
smallgenotypemaycreatelargephenotype,
itiscapableoffindingpatternsandregularities,
additional learning process is required for
connectionsweights,
an
individualcanlearnduringitslifetime,
is capable of implementing scalability and
modularity,
an additional time consuming computation is
neededforcreatingaphenotype.
Intelligentmaneuveringpattern‐findingsystemfor
maritime transport that uses indirect encoding has
somevaluablebenefits:
increaseofthesafetyofnavigationin
arestricted
water area by improving the data analysis for
decision‐makerduringmaneuvers,
improvementoftheoperationofshipsinport,due
totheincreasedbandwidth,
reductionofoperatingcostsofvessels,
minimizationoftheoccurrenceofhumanerrors,
reduction of the harmful impact of transport
on
theenvironment.
It is important to notice that all these benefits in
directencodingstrictlydependonproperadjustment
of evolutionary parameters, the size of ANNs
population and the encoding methods of signals
consideredinservicedenvironment.
Neuroevolutionary approach to ship handling in
confinedwatersimprovesaqualityof
maneuversand
safety of navigation effectively. For the simulation
study, mathematical model of three‐degrees‐of‐
freedom maneuvering container ship and VLCC
vessel with the single‐propeller and single‐rudder
wereappliedtotestthepattern‐findingperformance
of the system. Artificial neural networks based on
modified NEAT method increase complexity
and
performance of considered model of ship
maneuveringinconfinedwaters.
Implementation of input signals related to
influence of wind and current allows to simulate
complex behavior of the vessel in the environment
withmuchlargerstatespacethanitwaspossibleina
classic state machine learning algorithms (Łą
cki,
2007). Simulation results of maneuvers in variable
76
current and windy conditions for different ship
models encourage to further research of the
neuroevolutionary methods which may be
successfullyimplementedintoadvancednavigational
systemstoincreasethesafetyofnavigation.
It is also necessary to introduce and examine
additional disturbances from the influence of sea
waves on the movement
of the vessel in the further
research of the neuroevolutionary ship handling
system.
REFERENCES
Gruau, F. 1994. Neural Network Synthesis Using Cellular
EncodingAndTheGeneticAlgorithm.
Haasdijk, E., Rusu, A.A. & Eiben, A.E. 2010. HyperNEAT
forLocomotionControlinModularRobots.
Isherwood, J.W. 1973. Trans. R. Inst. Nav. Archit., Wind
resistanceofmerchantships,vol.115,327–332.
Kwaśnicka, H. 2007. Ewolucyjne projektowanie sieci
neuronowych , Oficyna Wydawnicza Politechniki
Wrocławskiej.
Łącki, M. 2007. Machine Learning Algorithms in Decision
Making Support in Ship Handling. , Katowice‐Ustroń:
WKŁ,.
Łącki, M. 2012. TransNav‐Int. J. Mar. Navig. Saf. Sea
Transp.,NeuroevolutionaryShipHandlingSystemina
WindyEnvironment,Vol.6,No.4,
pp.453‐458
Larkin, D., Kinane, A. & O’Connor, N. 2006. Towards
hardwareaccelerationofneuroevolutionformultimedia
processingapplicationsonmobiledevices,HongKong,
China.
Lee, S., Yosinski, J., Glette, K., Lipson, H. & Clune J 2013.
Appl.Evol.Comput.,Evolvinggaitsforphysicalrobots
withtheHyperNEATgenerative
encoding:thebenefits
ofsimulation,.
Lehman, J. & Miikkulainen, R. 2013. Scholarpedia,
Neuroevolution,vol.8,30977.
Nowak, A., Praczyk, T. & Szymak, P. 2008. Zeszty Nauk.
Akad. Mar. Wojennej, Multi‐agent system of
autonomous underwater vehicles‐preliminary report,
vol.4,99–108.
OCIMF 1977. Prediction of Wind and Current Loads on
VLCCs,OilCompaniesInternational MarineForum.
Stanley, K.O. & Risto, M. 2002. Efficient Reinforcement
Learning Through Evolving Neural Network
Topologies.
Stanley, K.O., Bryant, B.D. & Risto, M. 2005. IEEE Trans.
Evol. Comput., Real‐time neuroevolution in the NERO
videogame,vol.9,653–668.
