294
operatingbasedonabaseandelitepopulationswas
presented. Theelite populationconsisted of the best
individualsandthebase onecontainsindividualsof
lesser fitness score. Both populations are evolved
using different methods i.e. mutation and crossover
probability. The paper shows the superiority of a
multi‐populationvariation
overthesinglepopulation
whileusingthesamenumberofgenerations.
Multi‐population distributed evolutionary
algorithm can work both in parallel and sequential
modes.Differentvariationsareusedtosolvecomplex
optimization tasks. In (Gehring and Bortfeldt 2002)
Gehring and Bortfeldtshowed multi‐population
algorithm that calculated the optimal container
loading sequence. The DGA modification used by
them provided results better than those of a single
population algorithm. There are many publication
such as (Whitley 1997; Cantu‐Paz 1999; Martikainen
2006) that show an overview currently used
variations of the multi‐population algorithms.
Differentwaysofindividualmigrationanddedicated
genetic
operators that allow for an exchange of
individualsbetweenpopulationsareshown.
One of the tasks that the multi‐population
algorithm can be used with is remote control of a
mobile object (i.e. mobile robot or autonomous
overwaterships).Itconsistsinleadinganobjectfrom
astartingpositionto
itsdestinationortheoperation
(mission)area.Inordertodothis,anoptimal(bythe
criteriaofi.e.length)pathhastobeplotted.Thispath
hastoavoidobstacles:staticanddynamicconstraints
of the environment. The dynamic constraints can
present themselves as other moveable objects
travelling along their
own trajectory with certain
speed.The problemcanbeexamined intwo modes:
off‐line and on‐line. The off‐line mode of path
planningiscarriedoutinanenvironmentwherethe
movement parameters of other dynamic objects are
knownandareconstant.Theon‐linemodetakesinto
account the changes in the environment and the
uncertainty of the movement of other objects. As a
result of this, a constant control over the
environment’s changes and the other objects
parameters is required. In the event of changes, a
modificationofpreviouslyplottedpathtakesplace.
Theproblemwasreduced
toanoptimizationtasks
with static (islands, forbidden areas) and dynamic
(other ships, changeable weather conditions)
constraints(Śmierzchalski1997).Inordertosolvethe
presentedproblemanadaptiveevolutionarymethod
wasused (Goldberg 1989; Michalewicz 1996),which
operated based on the Evolutionary
Planner/Navigator(νEP/N++)(XiaoandMichalewicz
1999).
Thisalgorithmusestheevolutionaryalgorithm
library GALib (Wall 1996). Based on the available
library components a multi‐population distributed
evolutionaryalgorithm(Tanese1989a;Tanese1989b;
Belding 1995) was examined and its results were
comparedwithasinglepopulationversion.
This article presents a multi‐population
distributed evolutionary algorithm used in
the
problemofmaritimepathplanning.Itsorganizedso
that in the chapter two the maritime path planning
problem is presented. The evolutionary method and
the multi‐population variant is described in chapter
three and four. Chapter five defines the simulation
environment, while chapter six presents the results.
Chapterseven
concludesthepaper.
2 PATHPLANNINGFORACOLLISION
SCENARIO
The problem of collision avoidance consists of
plottingapathP,asapartofgivenroute,whichthe
mobileobjectcoversoftheinitialposition(startpoint)
(x
0,y0)totheactualdestinationpoint(xe,ye).Thepath
is composed of a linear segment sequence p
i (i =
1,...,n), interconnected by the turning points (x
i, yi).
The start and destination points are chosen by the
operator. Taking the above into account, path P is
feasible (belongs to the safe paths set): if every
segment p
i (i = 1,…,n) remains in the area of the
environmentanditdoesnotcrosswithanydynamic
or static constrain. The paths that do not meet this
requirement are considered unfeasible (Cochran,
HorngandFowler2003).
According to the collision avoidance rules, when
an encountered object is in
the area of observation
and if the object’s course crosses own path in an
unsafe distance, we consider the object to be on a
potentialcollisioncourse(target1,pointp
k,Fig1).
Figure1.Potentialcollisionscenario.
The safedistance from theown ship depends on
theadoptedcollisiondangerlevel(usuallyadistance
of 5‐8 nautical miles in front of the bow and 2‐4
nauticalmilesastern,dependingon thesize,type of
vesseland the ratioof ownand target ships’speed)
(Śmierzchalski
1998). The distance of the closest
approachandthetimeneededtoreachthisdistance
has to be also considered. The collision danger
conditionisreducedtodetectingif(Lenart1986):
min kr
DD
(1)
min
kr
TT
(2)
where:
D
min–closestapproachdistance,
T
Dmin–timetoachieveclosestapproachdistance,
Dkr,Tkr–criticalvaluesofDminandTDminsetby
thesystem’soperator.
Incaseofthecollisionavoidancetask,theobjects
the present a collision danger are interpreted as
mobile objects travelling with certain speed and
course.