遺伝的アルゴリズムで巡回セールスマン問題を解いてみる(Pythonコード編)

はじめに

「巡回セールスマン問題　遺伝的アルゴリズム」でググるとたくさんヒットすることを自分でもやってみました。

この記事は、Python コードの解説です。

• 理論編
• Python コード編
• 実行結果編

仕様

Breed

交叉・突然変異を表す enum

• ScrambleMutation ... 撹拌 (Scramble)
• TranslocationMutation ... 転座 (Translocation)
• SwapAdjacentPoints ... 隣接する点を交換
• SwapMutation ... 交換 (Swap)
• InversionMutation ... 逆位 (Inversion)
• CyclicCrossover ... 循環交叉 (Cycle Crossover: CX)
• PartialCrossover ... 部分的交叉 (Partial Crossover)
• OrderCrossover ... 順序交叉 (Oder Crossover: OX)
• OrderBasedCrossover ... 一様順序交叉 (Order Based Crossover: OX2)
• PositionBasedCrossover ... 一様位置交叉 (Position Based Crossover: POX)
• PartiallyMappedCrossOver ... 部分写像交叉 (Partial Mapped Crossover: PMX)
• SubtourExchangeCrossOver ... サブツアー交換交叉(Sub tour Exchange Crossover: SXX)
• EdgeRecombinationCrossOver ... 辺組換え交叉 (Edge Recombination Crossover: ERX)
• EdgeAssemblyCrossOver ... 枝組立て交叉 (Edge Assembly Crossover: EAX)
• SingleSinglePtCrossover ... 1 点交叉 (Single Point Crossover)
• TwoPtsCrossover ... 2 点交叉 (2 Points Crossover)
• MultiPtsCrossover ... 多点交叉 (Multi Points Crossover)
• UniformCrossover ... 一様交叉 (Uniform Crossover)
• SubstitutionMutation ... 置換 (Substitution)

Species クラス

セールスマンの種を表すクラスです。
$N$ 個の 2 次元の点の座標を保持し、経路の長さや適応度を測ります。
点の種類や測り方を変える場合は、このクラスから派生します。

属性・プロパティ

• points ... 点群。省略するとランダムな点群を使う
• N ... points=None のときランダムに生成する点の個数
• fig_projection ... 経路を 3D グラフに表示するなら '3d'

メソッド

• Species(points:np.ndarray=None, N:int=10, seed=None) ... コンストラクタ
  • points ... 点群。省略するとランダムな点群を使う
  • N ... points=None のときランダムに生成する点の個数
  • seed ... points=None のときの乱数の種
• _prepare() ... 適応度・長さを計算するための準備をしておく。原点から各点までの距離を _to_origin に、点同士の距離を _distance_map にキャッシュしている
• measure(path) ... 経路の長さを計算する
  • path ... $0 \dots N-1$ で表された経路
• bonus(path) ... 経路の適応度のボーナス分を計算する
  • path ... $0 \dots N-1$ で表された経路
• penalty(path) ... 経路の適応度のペナルティ分を計算する
  • path ... $0 \dots N-1$ で表された経路
• evaluate(path) ... 経路の適応度を計算する
  • path ... $0 \dots N-1$ で表された経路
• plot_a_path(ax, path, plot_kwargs={}) ... 経路をグラフに表示する
  • ax ... matplotlib.pyplot.subplots() などで得られた、グラフ 1 個分の領域
  • path ... $0 \dots N-1$ で表された経路

Salesman クラス

すべての点を通る経路 1 本を表します。

属性・プロパティ

• species: Species ... セールスマンの種
• path: numpy.ndarray ... 経路
• picked_indeces: numpy.ndarray ... 序数コーディングで表した経路
• fitness: float ... 適応度
• length: float ... 経路の長さ

メソッド

• Salesman(species:Species, path=None, picked_indeces=None) ... コンストラクタ
  • species ... セールスマンの種
  • path ... 経路。None ならば、picked_indeces から作る
  • picked_indeces ... 序数コーディングで表した経路。path も picked_indeces も None ならば、ランダムな経路を生成する
• plot(ax, show_title:bool=True, plot_kwargs={}) ... セールスマンの経路を表示する
  • ax ... matplotlib.pyplot.subplots() などで得られた、グラフ1個分の領域
  • show_title ... タイトルに適応度と長さを表示する
  • plot_kwargs ... plt.plot() に渡すキーワード引数
• sample_betters(salesmans, k:int, nelites:int=0) ... エリート選択とルーレット選択でセールスマンを選択する
• breed(breed:Breed, mother:Salesman, father:Salesman) ... 指定された交雑方法で両親から子個体 2 個を生成する
  • breed:Breed ... 交雑方法
  • mother:Salesman ... 親 1
  • father:Salesman ... 親 2
• scramble_mutation(mother:Salesman, father:Salesman) ... 撹拌 (Scramble)
• translocation_mutation(mother:Salesman, father:Salesman) ... 転座 (Translocation)
• swap_adjacent_points(mother:Salesman, father:Salesman) ... 隣接する点を交換
• swap_mutation(mother:Salesman, father:Salesman) ... 交換 (Swap)
• inversion_mutation(mother:Salesman, father:Salesman) ... 逆位 (Inversion)
• cyclic_crossover(mother:Salesman, father:Salesman) ... 循環交叉 (Cycle Crossover: CX)
• partial_crossover(mother:Salesman, father:Salesman) ... 部分的交叉 (Partial Crossover)
• order_crossover(mother:Salesman, father:Salesman) ... 順序交叉 (Oder Crossover: OX)
• position_based_crossover(mother:Salesman, father:Salesman) ... 一様位置交叉 (Position Based Crossover: POX)
• single_pt_crossover(mother:Salesman, father:Salesman) ... 1 点交叉 (Single Point Crossover)
• two_pts_crossover(mother:Salesman, father:Salesman) ... 2 点交叉 (2 Points Crossover)
• multi_pts_crossover(mother:Salesman, father:Salesman) ... 多点交叉 (Multi Points Crossover)
• uniform_crossover(mother:Salesman, father:Salesman) ... 一様交叉 (Uniform Crossover)
• substitution_mutation(mother:Salesman, father:Salesman) ... 置換 (Substitution)

Generation クラス

1世代分のセールスマンの集合です。

属性・プロパティ

• species: Species ... セールスマンの種
• salesmans: sequence of Salesman ... この世代の全ての個体
• leader: Salsesman ... この世代の適応度トップの個体
• population: int ... 世代の個体数

メソッド

• Generation(species:Species, salesmans) ...
  • species ... セールスマンの種
  • salesmans ... この世代の全ての個体
• generate_0th(species:Species, population:int=1000) ... 第 0 世代を生成する
  • species ... セールスマンの種
  • population ... 世代の個体数

Model クラス

世代交代をして適切な個体を探索します。

属性・プロパティ

• species: Species ... セールスマンの種
• generation: Generation ... 現在の世代
• max_population: int ... 世代の個体数
• nelites: int ... エリート選択される個体数
• breeded_population: int ... 生成された子個体の数
• leader_changed_epoch: int ... 最後にトップ交代があった世代の番号
• stopped_epoch: int ... 探索を終了した世代の番号

メソッド

• Model(species:Species, max_population:int=None) ... 第 0 世代を生成し、モデルを構築する
  • species ... セールスマンの種
  • max_population ... 世代の個体数。None ならば、$N (\log_2 N)^2 \le N^2$
• fit(nepochs:int=None, loggers=()) ... 世代交代して適切な個体を探索する
  • nepochs ... 世代交代の回数。None ならば、$N (\log N)^2 \le N^2$
  • loggers ... 世代交代中の情報をためる Logger の子クラスのオブジェクト
• _evoluate(epoch) ... 次の世代の子個体を生成・選別する

Logger クラス

Model.fit() の実行中の情報を記録してグラフに表示します。

属性・プロパティ

• _is_subplot: bool ... True: _plot() で 1 行使って自分だけのグラフを描く。False で 1 個分のグラフを描く
• _nlogs: int ... 記録する情報の種類の数

メソッド

• log_begin(model:Model) ... fit() 開始時の処理
• log_end(model:Model) ... fit() 中の処理
• log(model:Model, epoch:int) ... fit() 終了時の処理
• plot(ax=None, epochs=None) ... グラフを描画する
  • ax ... matplotlib.pyplot.subplots() などで得られた、グラフ1個分の領域
  • epochs ... グラフ描画に使う世代。None ならば、(0 世代, 1/4 世代, 1/2 世代, 最終世代)
• _plot(ax=None, epochs=None) ... 子クラスで実際にグラフを描いている関数
• plot_all(loggers, epochs=None) ... 全ての情報をグラフに描画する
  • loggers ... Model.fit() に渡して情報を集めたオブジェクト
  • epochs ... グラフ描画に使う世代。None ならば、(0 世代, 1/4 世代, 1/2 世代, 最終世代)

以下の子クラスを用意してあります。

• Logger_trace(level:int=1) ... Model.fit() の進捗状況を表示する
  • level ... 0: 何も表示しない、1: 終了時のみ結果を表示、2: 実行中に点を表示する、3: 10 世代ごとに結果表示
• Logger_leaders() ... 世代のトップの経路を描く
• Logger_fitness() ... 世代の適応度のトップと平均を描く
• Logger_population(show_breeded=False) ... 世代の個体数の推移を描く
  • 生成した子個体の数も描く
• Logger_last_fitness_histgram() ... 最終世代の適応度のヒストグラムを描く

ヘルパー関数

• get_subplots(nax=1) ... 複数のグラフ領域をリストにして返す
  • nax ... グラフ領域の個数

実装

このコードは、Python 3.7.5 と Google Colaboratory で確認済みです。

紙面の都合で、いろいろ省略しています。

• 交叉法ごとの利用割合を調整する処理(名残が Model.breed_rates にあります)
• 早期終了処理
• クラスや関数の説明

GaTsp.py

from datetime import datetime
import enum
import functools as ft
import itertools as it
import math
import random
import matplotlib.pyplot as plt
# from mpl_toolkits.mplot3d import Axes3D  # enable if use 3D plotting.
import numpy as np


@enum.unique
class Breed(enum.Enum):
    ScrambleMutation = enum.auto()
    TranslocationMutation = enum.auto()
    SwapAdjacentPoints = enum.auto()
    SwapMutation = enum.auto()
    InversionMutation = enum.auto()
    CyclicCrossover = enum.auto()
    PartialCrossover = enum.auto()
    OrderCrossover = enum.auto()
    # OrderBasedCrossover = enum.auto()
    PositionBasedCrossover = enum.auto()
    # PartiallyMappedCrossOver = enum.auto()
    # SubtourExchangeCrossOver = enum.auto()
    # EdgeRecombinationCrossOver = enum.auto()
    # EdgeAssemblyCrossOver = enum.auto()
    SinglePtCrossover = enum.auto()
    TwoPtsCrossover = enum.auto()
    MultiPtsCrossover = enum.auto()
    UniformCrossover = enum.auto()
    SubstitutionMutation = enum.auto()


## Coords of customers, all of which each salesman must travel.
## Generic property of the Salesmans
class Species:
    MIN_FITNESS = -100000
    fig_projection = None  # '3d' to plot a salesman's path on 3D

    def __init__(self, points:np.ndarray=None, N:int=10, seed=None, *args, **kwargs):
        if points is None:
            np.random.seed(seed)
            points = np.random.randn(N, 2)
            np.random.seed(None)
        self.points = points
        self.N = self.points.shape[0]
        self.indeces = np.arange(self.N, dtype=int)
        self._prepare(*args, **kwargs)

    def _prepare(self, *args, **kwargs):
        self._to_origin = np.sqrt(np.sum(self.points ** 2, axis=1))
        self._distance_map = np.zeros((self.N, self.N), dtype=np.float)
        for idx in range(self.N):
            xy_dist = np.sqrt(np.sum((self.points[idx]-self.points[:])**2, axis=1))
            self._distance_map[idx] = xy_dist

    def measure(self, path, *args, **kwargs):
        length = self._distance_map[path[:-1], path[1:]].sum()
        length += self._to_origin[path[0]]
        length += self._to_origin[path[-1]]
        return length

    def bonus(self, path, *args, **kwargs):
        bonus = 0.0
        return bonus

    def penalty(self, path, *args, **kwargs):
        penalty = 0.0
        return penalty

    def evaluate(self, path, *args, **kwargs):
        length = self.measure(path=path, *args, **kwargs)
        bonus = self.bonus(path=path, *args, **kwargs)
        penalty = self.penalty(path=path, *args, **kwargs)
        fitness = - length + bonus - penalty
        return fitness, length

    def plot_a_path(self, ax, path, plot_kwargs={}, *args, **kwargs):
        coords = self.points[path]
        ax.plot(coords[:,0], coords[:,1], **plot_kwargs)
        ax.plot((coords[-1,0], 0, coords[0,0]), (coords[-1,1], 0, coords[0,1]), **plot_kwargs)
        ax.scatter([coords[0,0]], [coords[0,1]])
        abs_max_val = np.max(np.abs(self.points)) * 1.1
        lim = (-abs_max_val, abs_max_val)
        ax.set_xlim(lim)
        ax.set_ylim(lim)


## Indivisual Salesman
class Salesman:
    _breeders = None  # initialized by Salesman.breed()

    def __init__(self, species:Species, path=None, picked_indeces=None, *args, **kwargs):
        self.species = species
        self._fitness = None
        self._length = None
        self.__indeces = None
        if path is not None:
            self.path = path if isinstance(path, np.ndarray) else np.array(path)
            self._picked_indeces = None
        elif picked_indeces is not None:  # encode picked_indeces to path.
            self._picked_indeces = picked_indeces if isinstance(picked_indeces, np.ndarray) else np.array(picked_indeces)
            indeces = np.arange(self.species.N, dtype=int)
            self.path = np.zeros(self.species.N, dtype=int)
            for idx, gene in enumerate(picked_indeces):
                self.path[idx] = indeces[gene]
                indeces[gene:-1] = indeces[gene+1:]
        else:  # generate new.
            self.path = np.random.permutation(self.species.N)
            self._picked_indeces = None
        self._hash = tuple(self.path).__hash__()

    def __hash__(self):
        return self._hash

    def __eq__(self, theother):
        return self.__hash__() == theother.__hash__()

    def __repr__(self):
        return f'- fitness: {self.fitness:.3f}\n- length: {self.length:.3f}\n- path: {self.path}'

    @property
    def picked_indeces(self):
        if self._picked_indeces is None:  # encode path to picked_indeces.
            bits = np.ones(self.species.N, dtype=np.int)
            self._picked_indeces = np.zeros(self.species.N, dtype=int)
            for idx, p in enumerate(self.path):
                self._picked_indeces[idx] = np.sum(bits[:p], initial=0)
                bits[p] = 0
        return self._picked_indeces

    @property
    def fitness(self):
        self._evaluate()
        return self._fitness

    @property
    def length(self):
        self._evaluate()
        return self._length

    def _evaluate(self):
        if self._fitness is None:
            self._fitness, self._length = self.species.evaluate(self.path)

    @property
    def _indeces(self):
        if self.__indeces is None:
            self.__indeces = np.zeros(self.species.N, dtype=int)
            self.__indeces[self.path] = self.species.indeces
        return self.__indeces

    def plot(self, ax, show_title:bool=True, plot_kwargs={}, *args, **kwargs):
        self.species.plot_a_path(ax=ax, path=self.path, plot_kwargs=plot_kwargs, *args, **kwargs)
        ax.legend()
        if show_title:
            title = plot_kwargs.get('label', '') + f': fit {self.fitness:.3f} / len {self.length:.3f}'
            ax.set_title(title)

    @staticmethod
    def sample_betters(salesmans, k:int, nelites:int=0, *args, **kwargs):
        salesmans = salesmans if isinstance(salesmans, tuple) or isinstance(salesmans, list) else tuple(salesmans)
        fits = np.array([s.fitness for s in salesmans])
        # select some part of k by roulette.
        fit_ave = fits.mean()
        fit_std = fits.std()
        weights = 1.0 / (1.0 + np.exp((fit_ave - fits) / fit_std))
        k1 = k if nelites == 0 else random.randrange(k - nelites)
        yield from random.choices(salesmans, weights=weights, k=k1)
        # select elites.
        if nelites > 0:
            fit_elite = np.sort(fits)[-nelites]
            yield from (s for s in salesmans if s.fitness >= fit_elite)
            # select lest of k by roulette.
            k2 = k - k1 - nelites
            yield from random.choices(salesmans, weights=weights, k=k2)

    @staticmethod
    def scramble_mutation(mother:'Salesman', father:'Salesman', *args, **kwargs):
        idx0, idx1 = sorted(random.sample(range(mother.species.N-1), k=2))  # at least 3 points may be shuffled.
        child1 = mother._scramble_mutation(idx0, idx1)
        child2 = father._scramble_mutation(idx0, idx1)
        return child1, child2

    def _scramble_mutation(self, idx0:int, idx1:int, *args, **kwargs):
        child_path = self.path.copy()
        np.random.shuffle(child_path[idx0:idx1+2])
        child = Salesman(species=self.species, path=child_path)
        return child

    @staticmethod
    def translocation_mutation(mother:'Salesman', father:'Salesman', *args, **kwargs):
        idx0, idx1, idx2 = sorted(random.sample(range(mother.species.N+1), k=3))
        child1 = mother._translocation_mutation(idx0, idx1, idx2)
        child2 = father._translocation_mutation(idx0, idx1, idx2)
        return child1, child2

    def _translocation_mutation(self, idx0:int, idx1:int, idx2:int, *args, **kwargs):
        child_path = np.concatenate((self.path[:idx0], self.path[idx1:idx2], self.path[idx0:idx1], self.path[idx2:]))
        child = Salesman(species=self.species, path=child_path)
        return child

    @staticmethod
    def swap_adjacent_points(mother:'Salesman', father:'Salesman', *args, **kwargs):
        indeces = np.array(random.sample(range((mother.species.N-1)//2), k=mother.species.N//10), dtype=int) * 2
        child1 = mother._swap_adjacent_points(indeces)
        child2 = father._swap_adjacent_points(indeces)
        return child1, child2

    def _swap_adjacent_points(self, indeces, *args, **kwargs):
        child_path = self.path.copy()
        child_path[indeces], child_path[indeces+1] = child_path[indeces+1], child_path[indeces]
        child = Salesman(species=self.species, path=child_path)
        return child

    @staticmethod
    def swap_mutation(mother:'Salesman', father:'Salesman', *args, **kwargs):
        idx0, idx1, idx2, idx3 = sorted(random.sample(range(mother.species.N), k=4))
        child1 = mother._swap_mutation(idx0, idx1, idx2, idx3)
        child2 = father._swap_mutation(idx0, idx1, idx2, idx3)
        return child1, child2

    def _swap_mutation(self, idx0:int, idx1:int, idx2:int, idx3:int, *args, **kwargs):
        child_path = np.concatenate((self.path[:idx0], self.path[idx2:idx3], self.path[idx1:idx2], self.path[idx0:idx1], self.path[idx3:]))
        child = Salesman(species=self.species, path=child_path)
        return child

    @staticmethod
    def inversion_mutation(mother:'Salesman', father:'Salesman', *args, **kwargs):
        idx0, idx1 = sorted(random.sample(range(mother.species.N-1), k=2))  # at least 3 points may be reversed.
        child1 = mother._inversion_mutation(idx0, idx1)
        child2 = father._inversion_mutation(idx0, idx1)
        return child1, child2

    def _inversion_mutation(self, idx0:int, idx1:int, *args, **kwargs):
        child_path = self.path.copy()
        child_path[idx0:idx1+2] = np.flip(self.path[idx0:idx1+2])
        child = Salesman(species=self.species, path=child_path)
        return child

    @staticmethod
    def cyclic_crossover(mother:'Salesman', father:'Salesman', *args, **kwargs):
        child1_path = mother.path.copy()
        child2_path = father.path.copy()
        idx = random.randrange(mother.species.N)
        val_1st = mother.path[idx]
        val_next = -1
        while val_next != val_1st:
            val_next = father.path[idx]
            child1_path[idx] = val_next
            child2_path[idx] = mother.path[idx]
            idx = mother._indeces[val_next]
        child1 = Salesman(species=mother.species, path=child1_path)
        child2 = Salesman(species=mother.species, path=child2_path)
        return child1, child2

    @staticmethod
    def partial_crossover(mother:'Salesman', father:'Salesman', *args, **kwargs):
        child1_path = mother.path.copy()
        child2_path = father.path.copy()
        child1_indeces = np.zeros(mother.species.N, dtype=int)
        child2_indeces = np.zeros(father.species.N, dtype=int)
        idx0, idx1 = sorted(random.sample(range(mother.species.N+1), k=2))  # at least 3 points may be reversed.
        for idx in range(idx0, idx1):
            child1_indeces[child1_path] = mother.species.indeces
            child2_indeces[child2_path] = father.species.indeces
            pt1 = child1_path[idx]
            pt2 = child2_path[idx]
            child1_path[idx] = pt2
            child2_path[idx] = pt1
            child1_path[child1_indeces[pt2]] = pt1
            child2_path[child2_indeces[pt1]] = pt2
        child1 = Salesman(species=mother.species, path=child1_path)
        child2 = Salesman(species=mother.species, path=child2_path)
        return child1, child2

    @staticmethod
    def order_crossover(mother:'Salesman', father:'Salesman', *args, **kwargs):
        idx = random.randrange(mother.species.N)
        child1 = mother._order_crossover(father, idx)
        child2 = father._order_crossover(mother, idx)
        return child1, child2

    def _order_crossover(self, other:'Salesman', idx, *args, **kwargs):
        head = self.path[:idx]
        tail = np.delete(other.path, other._indeces[head])
        child_path = np.concatenate((head, tail))
        child = Salesman(species=self.species, path=child_path)
        return child

    @staticmethod
    def position_based_crossover(mother:'Salesman', father:'Salesman', *args, **kwargs):
        flags = random.choices((0,1), k=mother.species.N)
        child1 = mother._position_based_crossover(father, flags)
        child2 = father._position_based_crossover(mother, flags)
        return child1, child2

    def _position_based_crossover(self, other:'Salesman', flags, *args, **kwargs):
        child_path = self.path.copy()
        swap_pts = self.path[flags == 1]
        child_path[flags == 0] = np.delete(other.path, other._indeces[swap_pts])
        child = Salesman(species=self.species, path=child_path)
        return child

    @staticmethod
    def single_pt_crossover(mother:'Salesman', father:'Salesman', *args, **kwargs):
        return Salesman._n_pts_crossover(mother, father, 1)

    @staticmethod
    def two_pts_crossover(mother:'Salesman', father:'Salesman', *args, **kwargs):
        return Salesman._n_pts_crossover(mother, father, 2)

    @staticmethod
    def multi_pts_crossover(mother:'Salesman', father:'Salesman', *args, **kwargs):
        return Salesman._n_pts_crossover(mother, father, mother.species.N // 4)

    @staticmethod
    def _n_pts_crossover(mother:'Salesman', father:'Salesman', k:int, *args, **kwargs):
        indeces = [None] + sorted(random.sample(range(mother.species.N), k=k)) + [None]
        child1_picked_indeces, child2_picked_indeces, *_ = ft.reduce(
                lambda gs, ii: (gs[0] + gs[2][ii[0]:ii[1]], gs[1] + gs[3][ii[0]:ii[1]], gs[3], gs[2]),
                zip(indeces[:-1], indeces[1:]),
                ([], [], list(mother.picked_indeces), list(father.picked_indeces)))
        child1 = Salesman(species=mother.species, picked_indeces=child1_picked_indeces)
        child2 = Salesman(species=mother.species, picked_indeces=child2_picked_indeces)
        return child1, child2

    @staticmethod
    def uniform_crossover(mother:'Salesman', father:'Salesman', *args, **kwargs):
        indeces = mother.species.indeces[random.choices((0,1), k=mother.species.N) == 1]
        child1 = mother._uniform_crossover(indeces)
        child2 = father._uniform_crossover(indeces)
        return child1, child2

    def _uniform_crossover(self, indeces, *args, **kwargs):
        child_picked_indeces = self.picked_indeces.copy()
        child_picked_indeces[indeces] = self.picked_indeces[indeces]
        child = Salesman(species=self.species, picked_indeces=child_picked_indeces)
        return child

    @staticmethod
    def substitution_mutation(mother:'Salesman', father:'Salesman', *args, **kwargs):
        child1 = mother._substitution_mutation()
        child2 = father._substitution_mutation()
        return child1, child2

    def _substitution_mutation(self, *args, **kwargs):
        N = self.species.N
        indeces = np.array([random.randint((idx-N)*N, N-idx-1) for idx in range(N)])
        child_picked_indeces = self.picked_indeces.copy()
        child_picked_indeces[indeces >= 0] = indeces[indeces >= 0]
        child = Salesman(species=self.species, picked_indeces=child_picked_indeces)
        return child

    @classmethod
    def breed(cls, breed:Breed, mother:'Salesman', father:'Salesman', *args, **kwargs):
        if cls._breeders is None:
            cls._breeders = {
                Breed.ScrambleMutation: Salesman.scramble_mutation,
                Breed.TranslocationMutation: Salesman.translocation_mutation,
                Breed.SwapAdjacentPoints: Salesman.swap_adjacent_points,
                Breed.SwapMutation: Salesman.swap_mutation,
                Breed.InversionMutation: Salesman.inversion_mutation,
                Breed.CyclicCrossover: Salesman.cyclic_crossover,
                Breed.PartialCrossover: Salesman.partial_crossover,
                Breed.OrderCrossover: Salesman.order_crossover,
                # Breed.OrderBasedCrossover: Salesman.order_based_crossover,
                Breed.PositionBasedCrossover: Salesman.position_based_crossover,
                Breed.SinglePtCrossover: Salesman.single_pt_crossover,
                Breed.TwoPtsCrossover: Salesman.two_pts_crossover,
                Breed.MultiPtsCrossover: Salesman.multi_pts_crossover,
                Breed.UniformCrossover: Salesman.uniform_crossover,
                Breed.SubstitutionMutation: Salesman.substitution_mutation,
            }
        breeder = cls._breeders.get(breed, lambda *_: None)
        return breeder(mother, father, *args, **kwargs)


## Group of Salesmans
class Generation:
    def __init__(self, species:Species, salesmans, *args, **kwargs):
        self.species = species
        self.salesmans = salesmans if isinstance(salesmans, tuple) else tuple(salesmans)
        self.leader = max(self.salesmans, key=lambda s: s.fitness)
        self.population = len(self.salesmans)

    @staticmethod
    def generate_0th(species:Species, population:int=1000, *args, **kwargs):
        children = set(Salesman(species=species) for _ in range(population - 1))
        children.add(Salesman(species=species, path=np.arange(species.N)))  # add the original path (0, 1, 2, ..., N-1)
        generation = Generation(species=species, salesmans=children)
        return generation


## Model of Genetic Algorithm for Traveling Salesman Problem.
class Model:
    def __init__(self, species:Species, max_population:int=None, *args, **kwargs):
        self.species = species
        self.max_population = int(species.N * math.log2(species.N)**2) if max_population is None else int(max_population)
        self.nelites = self.max_population // 10
        self.generation = Generation.generate_0th(species, self.max_population)
        self.breeded_population = 0
        self.leader_changed_epoch = 0
        self.stopped_epoch = 0
        self.breed_rates = {
            Breed.ScrambleMutation: 0.6,
            Breed.TranslocationMutation: 0.6,
            Breed.SwapAdjacentPoints: 0.6,
            Breed.SwapMutation: 0.6,
            Breed.InversionMutation: 0.6,
            Breed.CyclicCrossover: 0.6,
            Breed.PartialCrossover: 0.6,
            Breed.OrderCrossover: 0.6,
            # Breed.OrderBasedCrossover: 0.6,
            Breed.PositionBasedCrossover: 0.6,
            Breed.SinglePtCrossover: 0.6,
            Breed.TwoPtsCrossover: 0.6,
            Breed.MultiPtsCrossover: 0.6,
            Breed.UniformCrossover: 0.6,
            Breed.SubstitutionMutation: 0.6,
        }

    def fit(self, nepochs:int=None, loggers=(), *args, **kwargs):
        nepochs = int(self.species.N * math.log(self.species.N)**2) if nepochs is None else int(nepochs)
        epoch_to_stop = nepochs
        last_best_fitness = -1000000
        any(p.log_begin(self) for p in loggers)
        for epoch in range(nepochs):
            evoluated = self._evoluate(epoch)
            self.generation = Generation(species=self.species, salesmans=evoluated)
            if self.generation.leader.fitness > last_best_fitness:
                last_best_fitness = self.generation.leader.fitness
                self.leader_changed_epoch = epoch + 1
                epoch_to_stop = epoch + self.species.N
            any(p.log(self, epoch+1) for p in loggers)
            if epoch > epoch_to_stop:
                self.stopped_epoch = epoch + 1
                break
        any(p.log_end(self) for p in loggers)

    def _evoluate(self, epoch, *args, **kwargs):
        children = set(self.generation.salesmans)
        nparents = self.max_population - epoch * self.species.N // 10
        mothers = Salesman.sample_betters(self.generation.salesmans, nparents, self.nelites)
        fathers = Salesman.sample_betters(self.generation.salesmans, nparents, self.nelites)
        for _ in (children.update(Salesman.breed(breed, mother, father))
                for mother, father in zip(mothers, fathers) if mother != father
                for breed, rate in self.breed_rates.items() if random.random() < rate):
            pass
        self.breeded_population = len(children)
        betters = set(Salesman.sample_betters(children, self.max_population, self.nelites))
        return betters


## Loggers for Model.fit()
class Logger:
    COLORS=('red','green','blue','magenta','cyan')
    STYLES=('-','--','-.')
    _is_subplot = True
    _nlogs = 1

    def __init__(self, *args, **kwargs):
        pass

    def log_begin(self, model:Model, *args, **kwargs):
        self._logs = [[] for _ in range(self._nlogs)]
        self.log(model=model, epoch=0)

    def log_end(self, model:Model, *args, **kwargs):
        self._stopped_epoch = model.stopped_epoch

    def log(self, model:Model, epoch:int, *args, **kwargs):
        pass

    def plot(self, ax=None, epochs=None, *args, **kwargs):
        if epochs is None:
            nepochs = self._stopped_epoch
            epochs = (0, nepochs // 4, nepochs // 2, nepochs) if nepochs > 3 else (0, nepochs)
        self._plot(ax=ax, epochs=epochs, *args, **kwargs)

    def _plot(self, ax=None, epochs=None, *args, **kwargs):
        pass

    def _plot_epoch_lines(self, ax, epochs, y_lim, *args, **kwargs):
        ax.set_ylim(y_lim)
        for epoch in epochs:
            ax.plot((epoch, epoch), y_lim, color='gray', linestyle=':')

    def _offset_lim(self, y_min, y_max, *args, **kwargs):
        offset = (y_max - y_min) / 20
        return y_min - offset, y_max + offset

    @staticmethod
    def plot_all(loggers, epochs=None, *args, **kwargs):
        any(p.plot(ax=None, epochs=epochs, *args, **kwargs) for p in loggers if not p._is_subplot)
        subloggers = [p for p in loggers if p._is_subplot]
        if len(subloggers) > 0:
            axes = get_subplots(nax=len(subloggers))
            any(p.plot(ax=axes.pop(0), epochs=epochs, *args, **kwargs) for p in subloggers)
            plt.show()


class Logger_trace(Logger):
    _is_subplot = False

    def __init__(self, level:int=1, *args, **kwargs):
        self._level = level
        self._trace = self._l3 if level == 3 else self._l2 if level == 2 else (lambda *_: None)

    def log_begin(self, model:Model, *args, **kwargs):
        self._st = datetime.now()
        if self._level == 1:
            print('start at', self._st.strftime('%Y/%m/%d %H:%M:%S'))
        elif self._level == 2:
            print('start at', self._st.strftime('%Y/%m/%d %H:%M:%S'), end='')
        super().log_begin(model=model, *args, **kwargs)

    def log_end(self, model:Model, *args, **kwargs):
        et = datetime.now()
        super().log_end(model=model, *args, **kwargs)
        if self._level > 0:
            print(f'\n- time: {str(et - self._st)[:-3]}')
            print(f'- epoch: {model.stopped_epoch}({model.leader_changed_epoch})')
            print(f'{model.generation.leader}')

    def log(self, model:Model, epoch:int, *args, **kwargs):
        self._trace(model, epoch)

    def _l2(self, model:Model, epoch:int, *args, **kwargs):
        dot = '+' if epoch % 10 == 0 else '.'
        print(dot, end='')
        if epoch % 100 == 0:
            ct = datetime.now()
            print(f' fitness: {model.generation.leader.fitness:.3f}({model.leader_changed_epoch}) {str(ct - self._st)[:-3]}')

    def _l3(self, model:Model, epoch:int, *args, **kwargs):
        if epoch % 10 == 0:
            print(f'{epoch}: {model.generation.leader}')


class Logger_leaders(Logger):
    _is_subplot = False

    def log_begin(self, model:Model, *args, **kwargs):
        super().log_begin(model=model, *args, **kwargs)
        self._original = Salesman(model.species, path=model.species.indeces)
        self._projection = model.species.fig_projection

    def log(self, model:Model, epoch:int, *args, **kwargs):
        self._logs[0].append(model.generation.leader)

    def _plot(self, ax=None, epochs=None, *args, **kwargs):
        nplots = len(epochs)
        axes = get_subplots(nax=nplots+1, projection=self._projection)
        self._original.plot(ax=axes.pop(0), plot_kwargs=dict(label=f'original'))
        for epoch in epochs:
            self._logs[0][epoch].plot(ax=axes.pop(0), plot_kwargs=dict(label=f'{epoch}th'))
        plt.show()


class Logger_fitness(Logger):
    _nlogs = 2

    def log(self, model:Model, epoch:int, *args, **kwargs):
        self._logs[0].append(model.generation.leader.fitness)
        self._logs[1].append(sum(s.fitness for s in model.generation.salesmans) / model.generation.population)

    def _plot(self, ax, epochs=None, *args, **kwargs):
        xs = np.arange(len(self._logs[0]))
        ax.plot(xs, self._logs[0], label='best in the history', color=(0,0,1))
        ax.plot(xs, self._logs[1], label='average of each generation', color=(0,0,1), linestyle='--')
        y_lim = self._offset_lim(min(self._logs[0]), max(self._logs[0]))
        self._plot_epoch_lines(ax, epochs, y_lim)
        ax.set_xlabel('generation')
        ax.set_ylabel('fitness')
        ax.set_title('fitness')
        ax.legend()


class Logger_population(Logger):
    _nlogs = 2

    def __init__(self, show_breeded:bool=False, *arggs, **kwargs):
        self._show_breeded = show_breeded

    def log_begin(self, model:Model, *args, **kwargs):
        super().log_begin(model=model, *args, **kwargs)
        self._max_population = model.max_population

    def log(self, model:Model, epoch:int, *args, **kwargs):
        self._logs[0].append(model.generation.population)
        self._logs[1].append(model.breeded_population)

    def _plot(self, ax=None, epochs=None, *args, **kwargs):
        xs = np.arange(len(self._logs[0]))
        ax.plot(xs, [v for v in self._logs[0]], label='population')
        if self._show_breeded:
            ax.plot(xs, [v for v in self._logs[1]], label='breeded')
            y_max = max(self._logs[1])
        else:
            y_max = max(self._logs[0])
        ax.plot((epochs[0], epochs[-1]), (self._max_population, self._max_population), color='gray', linestyle=':')
        y_lim = self._offset_lim(min(self._logs[0]), y_max)
        self._plot_epoch_lines(ax, epochs, y_lim)
        ax.set_xlabel('epoch')
        ax.set_ylabel('population')
        ax.set_title('population')
        ax.legend()


class Logger_last_fitness_histgram(Logger):
    def log_end(self, model:Model, *args, **kwargs):
        super().log_end(model=model, *args, **kwargs)
        self._logs[0] = [s.fitness for s in model.generation.salesmans]

    def _plot(self, ax=None, epochs=None, *args, **kwargs):
        ax.hist(self._logs[0], 20)
        ax.set_xlabel('fitness')
        ax.set_ylabel('count of salesmans')
        ax.set_title('fitnesses at last')


class Logger_breed_legend(Logger):
    def _plot(self, ax=None, epochs=None, *args, **kwargs):
        for breed, color, style in zip(Breed, it.cycle(self.COLORS), it.cycle(self.STYLES)):
            ax.plot((0, 1), (0, 0), label=f'{breed.value} {breed}', color=color, linestyle=style)
        ax.legend()
        ax.set_xlim((0.0, 1.0))
        ax.set_xticks(())
        ax.set_ylim((0.0, 1.0))
        ax.set_yticks(())
        ax.set_title('legend')


## support functions.
def get_subplots(nax=1, *args, **kwargs):
    rows = 1 if nax == 5 else (nax + 3) // 4
    cols = 5 if nax == 5 else 4 if nax > 4 else nax
    fig = plt.figure()
    fig.set_figwidth(20.0)
    fig.set_figheight(rows * (20 // cols))
    axes = [fig.add_subplot(rows, cols, ridx * cols + cidx + 1, *args, **kwargs) for ridx in range(rows) for cidx in range(cols)]
    return axes

おわりに

多くの交雑を実装したのでコードが長くなりました。
実行結果は別記事にします。