# Copyright (c) 2022 AIRBUS and its affiliates.
# This source code is licensed under the MIT license found in the
# LICENSE file in the root directory of this source tree.
import random
from collections.abc import Iterable, Sequence
from typing import Any, Optional
from discrete_optimization.generic_tools.do_mutation import (
LocalMove,
LocalMoveDefault,
SingleAttributeMutation,
)
from discrete_optimization.tsp.problem import (
PermutationTsp,
Point2D,
Point2DTspProblem,
TspProblem,
TspSolution,
)
[docs]
def ccw(A: Point2D, B: Point2D, C: Point2D) -> bool:
return (C.y - A.y) * (B.x - A.x) > (B.y - A.y) * (C.x - A.x)
# Return true if line segments AB and CD intersect
[docs]
def intersect(A: Point2D, B: Point2D, C: Point2D, D: Point2D) -> bool:
return ccw(A, C, D) != ccw(B, C, D) and ccw(A, B, C) != ccw(A, B, D)
[docs]
def find_intersection(
variable: TspSolution,
points: Sequence[Point2D],
test_all: bool = False,
nb_tests: int = 10,
) -> list[tuple[int, int]]:
perm = variable.permutation
intersects: list[tuple[int, int]] = []
its = (
range(len(perm))
if test_all
else random.sample(range(len(perm)), min(nb_tests, len(perm)))
)
jts = (
range(len(perm) - 1)
if test_all
else random.sample(range(len(perm) - 1), min(nb_tests, len(perm) - 1))
)
for i in its:
for j in jts:
ii = i
jj = j
if jj <= ii + 1:
continue
A, B = points[perm[ii]], points[perm[ii + 1]]
C, D = points[perm[jj]], points[perm[jj + 1]]
if intersect(A, B, C, D):
intersects += [(ii + 1, jj)]
if len(intersects) > 5:
break
if len(intersects) > 5:
break
return intersects
[docs]
def get_points_index(
it: int, jt: int, variable: TspSolution, length_permutation: int
) -> tuple[int, int, int, int]:
perm = variable.permutation
i = perm[it]
j = perm[jt]
if it == 0:
i_before = variable.start_index
else:
i_before = perm[it - 1]
if jt == length_permutation - 1:
j_after = variable.end_index
else:
j_after = perm[jt + 1]
return i_before, i, j, j_after
[docs]
class TwoOptTspMutation(SingleAttributeMutation):
attribute_type_cls = PermutationTsp
attribute_type: PermutationTsp
node_count: int
points: Sequence[Point2D]
problem: Point2DTspProblem
def __init__(
self,
problem: Point2DTspProblem,
attribute: str | None = None,
test_all: bool = False,
nb_test: Optional[int] = None,
return_only_improvement: bool = False,
**kwargs: Any,
):
super().__init__(problem=problem, attribute=attribute, **kwargs)
self.node_count = problem.node_count
self.length_permutation = problem.length_permutation
self.points = problem.list_points
self.test_all = test_all
if nb_test is None:
self.nb_test = max(1, self.node_count // 10)
else:
self.nb_test = min(nb_test, self.node_count - 1)
self.evaluate_function_indexes = problem.evaluate_function_indexes
self.return_only_improvement = return_only_improvement
[docs]
def get_points(
self, it: int, jt: int, variable: TspSolution
) -> tuple[Point2D, Point2D, Point2D, Point2D]:
perm = variable.permutation
if it == 0:
point_before_i = self.points[variable.start_index]
else:
point_before_i = self.points[perm[it - 1]]
point_i = self.points[perm[it]]
point_j = self.points[perm[jt]]
if jt == self.length_permutation - 1:
point_after_j = self.points[variable.end_index]
else:
point_after_j = self.points[perm[jt + 1]]
return point_before_i, point_i, point_j, point_after_j
[docs]
def get_points_index(
self, it: int, jt: int, variable: TspSolution
) -> tuple[int, int, int, int]:
perm = variable.permutation
i = perm[it]
j = perm[jt]
if it == 0:
i_before = variable.start_index
else:
i_before = perm[it - 1]
if jt == self.length_permutation - 1:
j_after = variable.end_index
else:
j_after = perm[jt + 1]
return i_before, i, j, j_after
[docs]
def mutate_and_compute_obj(
self, solution: TspSolution
) -> tuple[TspSolution, LocalMove, dict[str, float]]: # type: ignore # avoid isinstance checks for efficiency
if solution.length is None or solution.lengths is None:
self.problem.evaluate(solution)
assert solution.length is not None and solution.lengths is not None
it = random.randint(0, self.length_permutation - 2)
jt = random.randint(it + 1, self.length_permutation - 1)
min_change = float("inf")
range_its = (
range(self.length_permutation)
if self.test_all
else random.sample(
range(self.length_permutation),
min(self.nb_test, self.length_permutation),
)
)
for i in range_its:
if i == self.length_permutation - 1:
range_jts: Iterable[int] = []
else:
range_jts = (
range(i + 1, self.length_permutation)
if self.test_all
else random.sample(
range(i + 1, self.length_permutation),
min(1, self.nb_test, self.length_permutation - i - 1),
)
)
for j in range_jts:
i_before, i_, j_, j_after = self.get_points_index(i, j, solution)
change = (
self.evaluate_function_indexes(i_before, j_)
- self.evaluate_function_indexes(i_before, i_)
- self.evaluate_function_indexes(j_, j_after)
+ self.evaluate_function_indexes(i_, j_after)
)
if change < min_change:
it = i
jt = j
min_change = change
fitness = solution.length + min_change
i_before, i_, j_, j_after = self.get_points_index(it, jt, solution)
permut = (
solution.permutation[:it]
+ solution.permutation[it : jt + 1][::-1]
+ solution.permutation[jt + 1 :]
)
lengths = []
if it > 0:
lengths += solution.lengths[:it]
lengths += [self.evaluate_function_indexes(i_before, j_)]
lengths += solution.lengths[it + 1 : jt + 1][::-1]
lengths += [self.evaluate_function_indexes(i_, j_after)]
if jt < self.length_permutation - 1:
lengths += solution.lengths[jt + 2 :]
if min_change < 0 or not self.return_only_improvement:
v = TspSolution(
start_index=solution.start_index,
end_index=solution.end_index,
permutation=permut,
lengths=lengths,
length=fitness,
problem=self.problem,
)
return v, LocalMoveDefault(solution, v), {"length": fitness}
else:
return (
solution,
LocalMoveDefault(solution, solution),
{"length": solution.length},
)
[docs]
def mutate(self, solution: TspSolution) -> tuple[TspSolution, LocalMove]: # type: ignore # avoid isinstance checks for efficiency
v, move, f = self.mutate_and_compute_obj(solution)
return v, move
[docs]
class TwoOptIntersectionTspMutation(TwoOptTspMutation):
def __init__(
self,
problem: Point2DTspProblem,
attribute: str | None = None,
test_all: bool = True,
nb_test: Optional[int] = None,
return_only_improvement: bool = False,
i_j_pairs: Optional[list[tuple[int, int]]] = None,
**kwargs: Any,
):
super().__init__(
problem=problem,
attribute=attribute,
test_all=test_all,
nb_test=nb_test,
return_only_improvement=return_only_improvement,
**kwargs,
)
self.i_j_pairs = i_j_pairs
[docs]
def mutate_and_compute_obj(
self, solution: TspSolution
) -> tuple[TspSolution, LocalMove, dict[str, float]]: # type: ignore # avoid isinstance checks for efficiency
if solution.length is None or solution.lengths is None:
self.problem.evaluate(solution)
assert solution.length is not None and solution.lengths is not None
reset_end = True
ints = find_intersection(
solution, self.points, nb_tests=min(3000, self.node_count - 2)
)
self.i_j_pairs = ints
if len(self.i_j_pairs) == 0:
return (
solution,
LocalMoveDefault(solution, solution),
{"length": solution.length},
)
min_change = float("inf")
for i, j in self.i_j_pairs:
i_before, i_, j_, j_after = self.get_points_index(i, j, solution)
change = (
self.evaluate_function_indexes(i_before, j_)
- self.evaluate_function_indexes(i_before, i_)
- self.evaluate_function_indexes(j_, j_after)
+ self.evaluate_function_indexes(i_, j_after)
)
if change < min_change:
it = i
jt = j
min_change = change
fitness = solution.length + min_change
i_before, i_, j_, j_after = self.get_points_index(it, jt, solution)
permut = (
solution.permutation[:it]
+ solution.permutation[it : jt + 1][::-1]
+ solution.permutation[jt + 1 :]
)
lengths = []
if it > 0:
lengths += solution.lengths[:it]
lengths += [self.evaluate_function_indexes(i_before, j_)]
lengths += solution.lengths[it + 1 : jt + 1][::-1]
lengths += [self.evaluate_function_indexes(i_, j_after)]
if jt < self.length_permutation - 1:
lengths += solution.lengths[jt + 2 :]
if reset_end:
self.i_j_pairs = None
if min_change < 0 or not self.return_only_improvement:
v = TspSolution(
start_index=solution.start_index,
end_index=solution.end_index,
permutation=permut,
lengths=lengths,
length=fitness,
problem=self.problem,
)
return v, LocalMoveDefault(solution, v), {"length": fitness}
else:
return (
solution,
LocalMoveDefault(solution, solution),
{"length": solution.length},
)
[docs]
class SwapTspMove(LocalMove):
def __init__(self, attribute: str, tsp_model: TspProblem, swap: tuple[int, int]):
self.attribute = attribute
self.tsp_model = tsp_model
self.swap = swap
[docs]
def apply_local_move(self, solution: TspSolution) -> TspSolution: # type: ignore # avoid isinstance checks for efficiency
if solution.length is None or solution.lengths is None:
solution.problem.evaluate(solution)
assert solution.length is not None and solution.lengths is not None
current = getattr(solution, self.attribute)
i1, i2 = self.swap
v1, v2 = current[i1], current[i2]
i_before, i, j, j_after = get_points_index(
i1, i2, solution, self.tsp_model.length_permutation
)
current[i1], current[i2] = v2, v1
previous = (
solution.lengths[i1],
solution.lengths[i1 + 1],
solution.lengths[i2],
solution.lengths[i2 + 1],
)
solution.lengths[i1] = self.tsp_model.evaluate_function_indexes(
i_before, current[i1]
)
solution.lengths[i1 + 1] = self.tsp_model.evaluate_function_indexes(
current[i1], current[i1 + 1]
)
solution.lengths[i2] = self.tsp_model.evaluate_function_indexes(
current[i2 - 1], current[i2]
)
solution.lengths[i2 + 1] = self.tsp_model.evaluate_function_indexes(
current[i2], j_after
)
solution.length = (
solution.length
+ solution.lengths[i1]
+ solution.lengths[i1 + 1]
+ solution.lengths[i2]
+ solution.lengths[i2 + 1]
- sum(previous)
)
return solution
[docs]
def backtrack_local_move(self, solution: TspSolution) -> TspSolution: # type: ignore # avoid isinstance checks for efficiency
return self.apply_local_move(solution)
[docs]
class SwapTspMutation(SingleAttributeMutation):
problem: Point2DTspProblem
attribute_type_cls = PermutationTsp
attribute_type: PermutationTsp
def __init__(
self, problem: TspProblem, attribute: str | None = None, **kwargs: Any
):
super().__init__(problem=problem, attribute=attribute, **kwargs)
self.length_permutation = problem.length_permutation
[docs]
def mutate(self, solution: TspSolution) -> tuple[TspSolution, LocalMove]: # type: ignore # avoid isinstance checks for efficiency
i = random.randint(0, self.length_permutation - 3)
j = random.randint(i + 2, min(self.length_permutation - 1, i + 1 + 4))
two_opt_move = SwapTspMove(self.attribute, self.problem, (i, j))
new_sol = two_opt_move.apply_local_move(solution)
return new_sol, two_opt_move