Delivery Routes
In this notebook you find a short delivery route. A van leaves the depot, visits four stops once each, and returns. Each candidate is an ordering of the stops. Genetic search minimizes the round-trip distance with operators that never drop or repeat a stop, and a parent selector that you supply. The notebook runs offline and needs no credentials.
Setup
Mix.install([
{:tune, "~> 0.5.0"}
])
Measure a route
Stops sit on a street grid, so the distance between two points is the number of blocks across plus the number of blocks up or down.
stops = %{depot: {0, 0}, a: {0, 2}, b: {2, 2}, c: {2, 0}, d: {1, 0}}
distance = fn route ->
[:depot | route ++ [:depot]]
|> Enum.chunk_every(2, 1, :discard)
|> Enum.sum_by(fn [from, to] ->
{x, y} = stops[from]
{u, v} = stops[to]
abs(x - u) + abs(y - v)
end)
end
routes = [[:a, :c, :b, :d], [:b, :a, :d, :c], [:d, :b, :a, :c], [:c, :d, :a, :b]]
Enum.map(routes, &{&1, distance.(&1)})
[
{[:a, :c, :b, :d], 12},
{[:b, :a, :d, :c], 12},
{[:d, :b, :a, :c], 12},
{[:c, :d, :a, :b], 12}
]
The four starting routes all cover 12 blocks.
Write permutation-safe operators
A route is a permutation: every stop appears exactly once. Ordinary operators can break that rule. Joining the front of one route to the back of another can repeat a stop and lose another.
This crossover keeps a prefix of the left parent, then appends the right
parent's remaining stops in their order. This mutation swaps two positions.
Both take Tune's random state last and return {new_route, new_random_state}.
crossover = fn left, right, rng ->
{cut, rng} = :rand.uniform_s(3, rng)
prefix = Enum.take(left, cut)
{prefix ++ (right -- prefix), rng}
end
mutate = fn route, rng ->
{i, rng} = :rand.uniform_s(length(route), rng)
{j, rng} = :rand.uniform_s(length(route), rng)
first = Enum.at(route, i - 1)
second = Enum.at(route, j - 1)
{route |> List.replace_at(i - 1, second) |> List.replace_at(j - 1, first), rng}
end
rng = :rand.seed_s(:exsss, 3)
{child, rng} = crossover.([:a, :c, :b, :d], [:d, :b, :a, :c], rng)
{swapped, _rng} = mutate.([:a, :b, :c, :d], rng)
{child, swapped}
{[:a, :d, :b, :c], [:a, :d, :c, :b]}
The child keeps :a from the left parent, then takes :d, :b, and :c in
the right parent's order.
Choose parents with your own policy
By default, genetic search picks each parent by tournament. Pass
select_parent to apply your own policy. Tune calls it with the eligible
candidates of the current generation and its random state. It must return
{candidate_id, new_random_state}.
This selector always picks the candidate with the best score:
strongest = fn candidates, rng ->
{Enum.max_by(candidates, & &1.evaluation.selected_score).id, rng}
end
selected_score is always higher-is-better. For a score with
direction: :minimize, Tune stores the negated value, so the shortest route
has the largest selected_score.
Run the search
direction: :minimizemakes a shorter route a better route.valid?rejects any child that is not a permutation of the four stops.target_score: 8is in the score's own units: stop at 8 blocks or fewer.
study =
Tune.new(hd(routes), run: fn route, :roundtrip -> distance.(route) end)
|> Tune.data(validation: [:roundtrip])
|> Tune.score(:distance, & &1, direction: :minimize)
|> Tune.search(:genetic,
initial_population: routes,
generations: 12,
valid?: &(Enum.sort(&1) == [:a, :b, :c, :d]),
select_parent: strongest,
crossover_rate: 1,
mutation_rate: 1,
crossover: crossover,
mutate: mutate,
target_score: 8
)
|> Tune.limit(evaluations: 52, seed: 7)
{:ok, winner} = Tune.tune(study)
IO.puts("Selected #{inspect(winner.value)}")
IO.puts("Round-trip distance #{winner.best.evaluation.summaries.distance.mean}")
IO.puts("Stop reason #{winner.stop_reason} after #{length(winner.history)} evaluations")
Selected [:d, :c, :b, :a]
Round-trip distance 8.0
Stop reason target_score after 8 evaluations
The winner goes depot, :d, :c, :b, :a, depot: 1 + 1 + 2 + 2 + 2 = 8
blocks, the perimeter of the grid.
Call the selector on generation zero to see what it receives and returns:
generation_zero = Enum.filter(winner.history, &(&1.lineage.generation == 0))
IO.inspect(Enum.map(generation_zero, &{&1.id, &1.evaluation.selected_score}))
{id, _rng} = strongest.(generation_zero, :rand.seed_s(:exsss, 1))
id
[{"0", -12.0}, {"1", -12.0}, {"2", -12.0}, {"3", -12.0}]
"0"
All four routes tie, so Enum.max_by/2 returns the first one. Every candidate
in generation 1 comes from route "0", and the swap mutation supplies the
variety. A different policy, such as breaking ties at random, changes which
routes breed.
Compare with the starting route
Tune.compare/3 runs the starting route and the winner on the same cases.
{:ok, comparison} = Tune.compare(study, winner, split: :validation)
metric = comparison.metrics.distance
IO.puts("#{metric.baseline_mean} -> #{metric.challenger_mean} blocks (#{metric.status}, #{metric.delta})")
12.0 -> 8.0 blocks (improved, -4.0)
For a minimized score, a negative delta is an improvement.
Check every route is a permutation
Confirm that no candidate in the history lost or repeated a stop.
Enum.all?(winner.history, &(Enum.sort(&1.value) == [:a, :b, :c, :d]))
true
Next steps
- Evolve a Word shows each genetic operator step by step.
- Dispatch Policies watches generations and stops a search early.
- Search API lists every genetic search option.