The Candidate Factory generates an initial set of candidate routes (individuals) within the problem space, together with further randomly generated routes.

No specific algorithm is used to generate initial population, it simply generates the required number of random solutions according to the following steps.

Usually start and end polygons contain part of corresponding bearing line. When present, the target bearing measurement is the most effective observation on the target track, so the best solutions start with initial points on this line. Where the polygon does contain part of bearing line this line splits on multiple segments and the candidate factory takes a random point from each segment consequentially, as shown on Figure 20.5, “Bearing lines for new points”.

Figure 20.5. Bearing lines for new points

When the candidate factory needs to generate a point for above polygon it takes first segment and generates c₁, when it needs a new point again it takes second segment and generates c₂ etc.

On occasions when the start or end polygon doesn't have part of corresponding bearing line (there is no sensor data for that time), the candidate factory generates a grid of points for this polygon, it applies a grid to the polygon then takes a random one each time, as in Figure 20.6, “Polygon without bearing line”.

Figure 20.6. Polygon without bearing line

To generate random chromosomes the candidate factory takes the start and end polygons for each straight leg and generates a point from each one using the above rules. The following pseudocode documents this:

I = empty chromosome
for (leg = every straight of Legs)
  S = start polygon of (leg)
  E = end polygon of (leg)
  sa = take next point of (S)
  ea = take next point of (E)
  a = route(sa, ea)
  add new gene (a) to chromosome (I)
end

To select the chromosome to use in genetic operators we use tournament selection (http://en.wikipedia.org/wiki/Tournament_selection) with tournament size = 2 and a probability to allow the worse candidate, depending on the island type.

The tournament strategy is implemented according to this pseudocode:

population = current population
population = current population
p = probability to accept worse
selected = empty set of chromosomes
while (selected.size < populationSize)
  better = take random chromosome from (population)
  worse = take random chromosome from (population)
  if (better.score > worse.score)
    better <=> worse (swap them over)
  end
  if (use_worse_event(p))
    add new chromosome(worse) to (selected)
  else
    add new chromosome(better) to (selected)
  end
end

Two types of genetic operator are used: crossover and mutation.

20.3.5.1. Crossover

Crossover is genetic operator which is used to produce new chromosomes based on crossing two parent chromosomes. There are several techniques to implement crossover, we use two of them: one-point list crossover and arithmetic crossover.

20.3.5.1.1. One-point list crossover

One-point list crossover is well known and widely used crossover operator http://en.wikipedia.org/wiki/Crossover_(genetic_algorithm). It selects random split point in parent chromosomes and generates two child chromosome based on the following rule:

In our example (Figure 20.3, “Example”): our two chromosomes

X₁ = { a₁, b₁, c₁} - black straight lines

X₂ = { a₂, b₂, c₂} - blue straight lines

let's take our split point = 1, in this case we will have two new chromosomes:

Figure 20.7. one point crossover example

I₁ = { a₂, b₁, c₁} - black lines on the above figure

I₂ = { a₁, b₂, c₂} - blue lines on the above figure

20.3.5.1.2. Arithmetic crossover

Arithmetic crossover is GA crossover operator designed for continuous search spaces, it has several modification and described in many papers (for instance: http://www.researchgate.net/publication/228618503_A_new_genetic_algorithm_with_arithmetic_crossover_to_economic_and_environmental_economic_dispatch/file/9fcfd50a6971a00cc5.pdf)

The general idea of arithmetic crossover is to take two corresponding genes from parent individuals and create new gene as linear combination of parent genes:

where

• a - gene from first parent

• b - gene from second parent

• c - new gene

• r - random number [0; 1]

Because the above formula restricts a new gene to be between its parents, several authors propose extending the random number interval to [-d; 1 + d], where d is parameter which allows new gene to go outside. Usually d is less than 0.25.

For 2D points arithmetic crossover looks like: a, b - (blue) parent genes, c - (green) possible new genes:

Figure 20.8. Illustration of arithmetic crossover for 2D points

In our application we will use the following implementation of arithmetic crossover. Initial parameters: two parent chromosomes P₁, P₂.

Pseudocode:

I = empty chromosome

for (a = every gene of X1) (b = every gene of X2)
  sa = take start point of a
  sb = take start point of b
  ea = take end point of a
  eb = take end point of b

  // generate random from [-0.1; 1.1)
  // this allows to create new individuals
  // which aren't in parent's bounds sometimes
  r = 1.2 * random() - 0.1
  // new start point on road from sa to sb
  sc = r * sa + (1 - r) * sb
  // new end point on road from ea to eb
  ec = r * ea + (1 - r) * eb
  c = route(sc, ec)
  add new gene (c) to chromosome (I)
end

For our example from Figure 20.3, “Example”, we generate new chromosome (green) with arithmetic crossover.

Figure 20.9. Arithmetic crossover example

20.3.5.2. Mutation

The goal of mutation is to produce individuals which aren't present in current population - thus individuals that aren't achievable by crossover. Mutation is a genetic operator which produces new chromosomes by substituting genes in parent chromosome for newly generated ones with some specified probabilit. The specific mutation used in a GA instance depends on an understanding of the problem domain and data patterns.In our implementation we will use two techniques.

20.3.5.2.1. Random mutation

Random mutation substitutes some genes of a parent chromosome for corresponding genes randomly generated by candidates factory chromosome. Pseudocode of random mutation looks like:

X = parent chromosome
R = new random chromosome (from CandidatesFactory.generateRandom)
p = mutation probability
I = empty chromosome
for (a every gene of X) (b every gene of R)
  if (mutation_event(p))
    add new gene (b) to chromosome (I)
  else
    add new gene (a) to chromosome (I)
  end
end

Example: Let's take parent chromosome X (black) and random chromosome R (red). Mutation is made only on second gene this will produce new chromosome I (green)

Figure 20.10. Random mutation

20.3.5.2.2. Mutation to vertex

Mutation to vertex comes to GA from Debrief's experimental Simulated Annealing (SA) optimized point generation implementation (see Section 20.3.5.4, “Optimised point generation”), this algorithm gives good results for SA optimization and there is value in also using it within GA with some specific modifications.

Because in GA on each iteration there are multiple individuals there is no reason to use two vertices and take a new point between them. It's simpler to take only one vertex and create a new point as linear combination of current point and chosen vertex:

where

• a - current point

• b - chosen vertex

• c - new point

• r - random number between [0, 1]

To generate "r” we use Y distribution from SA implementation (see Section 20.3.5.3, “Standard VFA strategy”). This distribution depends on current iteration and produces values which are closest to 0 when number of iterations goes to infinity. To avoid very small values for "r” we take iteration parameter for this distribution as follows:

iteration = real iteration % 300

Pseudocode for mutation to vertex:

X - parent chromosome
p - mutation probability

I = empty chromosome
for (a every gene of X)
  if (mutation_event(p))
    sa = start point of a
    ea = end point of a  
    S = find start polygon for (a)
    E = find end polygon for (a)
    r = y_random(iteration % 300)
    sc = vertex(S) * r + (1-r) * sa
    ec = vertex(E) * r + (1-r) * ea
    c = route(sc, se)
    add new gene (c) to chromosome (I)
  else
    add new gene (a) to chromosome (I)
  end
end

Example: Parent chromosome X (black), new chromosome I (green). Mutation was made for first and third genes.

Figure 20.11. Mutation to vertex example

20.3.5.4. Optimised point generation

The VFA selection strategy described above has a high performance cost when run later in the process - a cost that isn't justified when the temperature is cooling, and only small steps are needed (when SA is in the "discrete improvements" phase as temperature approaches zero and only small jumps are allowed). So, a custom selection strategy is provided, which selects a random point in area with current point (P) and current temperature (T):

1. Select two random vertices of current polygon (V₁, V₂)

2. Create two segments: (P, V₁), (P, V₂)

3. Calculate two random values y₁ and y₂ based on Y distribution from VFA (VFA - 1)

4. find X point on (P, V₁) segment on road from P to V₁, with distance d₁ = abs(y₁) * distance(P, V₁)

5. find Y point on (P, P₂) segment on road from P to V₂, with distance d₂ = abs(y₂) * distance(P, V₂)

6. find P_new on road from X to Y with distance = rand(0, 1) * distance(X, Y)

Figure 20.12. Point generation

As previously explained, each chromosome in GA is a set of straight routes. The fitness function starts by verifying that each of these straight routes are achievable. If everything is ok it then constructs altering routes (cubic bezier curves) between them. The GA fitness score is the sum of two scores:

The detail of the a) scores is described in the Debrief-SATC contribution documentation.

Score b) is very effective in producing a solution that is the sum of consistent straight line legs. It's quite easy for the GA to produce a solution that is the collection of the best performing individual legs, but where the legs aren't consistent with each other. In Figure 20.13, “Inconsistent range” it is clear that whilst the green and purple legs are both valid, they aren't consistent with each other.

Figure 20.13. Inconsistent range

Figure 20.14, “Consistent legs” demonstrates the inclusion of the consistent legs scoring - used to verify that it is possible for a vehicle to transition between the two legs in the available time.

Figure 20.14. Consistent legs

Note that in Figure 20.14, “Consistent legs”, the solutions still don't match the true ("SUBJECT") track - that requires further contribution from the analyst. But, the legs in the solution route are consistent with each other.

To score how well altering route is compatible with its previous and next straight routes the GA fitness function uses speed changes during alteration.

A smooth speed plot (without peaks) is the best situation (Figure 20.15, “Speed plot with smooth speed change”), peaks which are near to previous and next speed are worse but valid (Figure 20.16, “Speed plot with peaks near to straight legs”), and huge peaks are the worst situation (Figure 20.17, “Speed plot with huge peaks”)

Figure 20.15. Speed plot with smooth speed change

Figure 20.16. Speed plot with peaks near to straight legs

Figure 20.17. Speed plot with huge peaks

Pseudocode for altering route score is:

a - altering route
previous - previous straight route
next - next straight route

peaks = a.speed_peaks_count
score = 0;
if (peaks == 0)
  score = 0;
else if (peaks == 1)
  score = (a.speed_peak - closest(previous.speed, next.speed))2
else
  score = 1.5 * (a.max_speed_peak - a. min_speed_peak)2
end

Pseudocode of fitness function:

X - chromosome to score
score = 0;
if (some route from (X) is impossible)
  score = MAX_SCORE;
  return;
end
alterings = generate alterings for (X)
for (every straight route (s) from X)
  score = score + calculate contributions score for (s)
end
for (every altering route (a) from (alterings))
  score = score + calculate contributions score for (a)
  score = score + compatible score (a, previous of(a), next of (a))
end