ソルバの抽象化とTSPコアロジック～連載 TSPソルバ実装記03～

はじめに

前回の記事「連載 2: 制御とインフラストラクチャの実装」では, 依存性逆転の原則に基づき, 実験のライフサイクルを制御する Processor 層と, MLflow 連携を担う ExternalInterfaces 層の実装を解説しました. これで, 外部サービス連携と実行フローに関するフレームワークの基盤は整いました.

本記事では, ビジネスロジックの核が格納されている Solver 層について解説します.

Solver層の設計目標は, 「多様なアルゴリズムの拡張性」と, アルゴリズムの繰り返し評価に耐えうる「計算効率」の両立です. 将来的に焼きなまし法, 遺伝的アルゴリズムなど, さまざまなメタヒューリスティクスを追加できるよう, 設計を抽象化します.

この目標を達成するために導入された, 以下の 3 つの重要な抽象化構造を解説します.

• 契約と制御の分離の設計
  • Processor層とSolver層を繋ぐ実行契約(ISolver)
  • 共通機能を担う基盤(AbstractSolver)
• ドメインロジックの徹底分離
  • TSP の経路評価ロジックを独立させた IEvaluator インターフェースの意図
  • 差分評価による効率化
• 動的な実行
  • 設定に基づき, 適切なソルバインスタンスに切り替える SolverFactory の仕組み

これらがどのように相互作用しているのかをご覧ください.

連載の構成

本連載「TSP ソルバ実装記」は全 4 回の予定です.

• 連載 1: プロジェクトの全体像と設計原則
• 連載 2: 制御とインフラストラクチャの実装
• 連載 3: ソルバの抽象化と TSP コアロジック ← 本記事
• 連載 4: 個別アルゴリズムの実装と実験

---

目次

• はじめに
• 目次
• ソルバ設計
  • 共有プロジェクトでの契約: ISolver の役割
  • ソルバ設計の土台: AbstractSolver
• TSP の評価エンジン
  • IEvaluator の設計意図
  • Evaluator の実装
  • 差分評価ロジックについて
• ソルバの生成
  • 思想: ファクトリーパターン(SolverFactory)
  • 実装: 設定に基づくソルバインスタンスの切り替え
• まとめと次回予告

---

ソルバ設計

共有プロジェクトでの契約: ISolver の役割

ISolverはCommonプロジェクトに定義された, Processor層がSolver層とやり取りするための唯一の窓口です.
このインターフェースは, 「ソルバは何が出来るか」という機能のみを定義し, その具体的な中身(アルゴリズム/評価方法)を隠蔽します.

AbstractSolverは, この契約を果たすために以下のメソッドを実装します.

// Common/Interfaces/Solver/ISolver.cs
public interface ISolver
{
    public void SetParamDict(Dictionary<string, string> paramDict);
    public void SetProblem(ProblemModel problem);
    public Task<CalculationResult> SolveAsync(IProgress<ProgressReport> progress);
}

ソルバ設計の土台: AbstractSolver

AbstractSolverはISolverを実装し, 全ての具象ソルバ(AnnealingModelなど)に共通の機能を提供します.
具体的には, MLflow クライアントの保持, 問題データやパラメータの保持, 評価器の利用などの機能を提供します.

プライマリコンストラクタによる依存性の注入(IMLflowClient)

AbstractSolverは, 実行環境との連携に必要なIMLflowClient のみを, プライマリコンストラクタを通じて受け取ります.
これは, 依存性注入(DI)の原則に従った標準的な実装です.

// Solver/AbstractSolver.cs (抜粋)
public abstract class AbstractSolver(IMLflowClient client) : ISolver
{
    protected readonly IMLflowClient _client = client;
    // ...
}

これにより, ソルバは初期化の時点で, ロギング機能を提供するIMLflowClientのインスタンスを確実に受け取ることが保証されます.

外部設定による問題データと評価器のセットアップ

問題データ (ProblemModel) と評価器 (IEvaluator) は, コンストラクタではなく, ISolverインターフェースの契約であるSetProblemメソッド内でセットアップされます. 評価器(IEvaluator)は, このSetProblemメソッド内で生成されています.

// Solver/AbstractSolver.cs の SetProblem メソッド(抜粋)
public void SetProblem(ProblemModel problem)
{
    _problem = problem;
    // ここで具象クラスをインスタンス化
    _evaluator = new Evaluator(_problem.Coordinates);
}

この実装の理由を, 少し深掘りしてみましょう. 通常, クリーンアーキテクチャでは, 上位層(AbstractSolver)が下位層の具象クラス(Evaluator)を直接newで生成することは, 「依存性逆転の原則」に反するとされます.

通常であれば, 以下のような依存関係にすると思います.

しかし, 以下の実装により, 依存関係の方向性AbstractSolverがEvaluatorという具体的な実装の詳細に依存してしまっています.

この実装により, AbstractSolverは, Evaluatorという具体的な実装の詳細に依存してしまっています. もしEvaluatorクラス名が変わったり, コンストラクタの引数が変わったりした場合, AbstractSolverのコードも変更が必要になってしまいます.

この設計を採用した意図は以下の点にあります.

• 段階的な初期化の必要性
  • IEvaluatorの具体的な実装(Evaluator)は, ProblemModel のデータ(都市の座標など)がなければ構築できません.
  • ISolverの契約上, ProblemModelの受け取りはSetProblemメソッドで行う必要があるため, 初期化処理がこのタイミングに集中します.
• TSP 問題のコアロジック統合
  • Evaluatorは純粋な TSP のコアロジックであり, 他のインフラストラクチャ層(DB, WebAPI など)への依存が一切ありません.
  • このような純粋なドメイン実装は, 具象ソルバクラスからアクセスできるように, 共通基盤であるAbstractSolverが責任を持ってセットアップするのが合理的である, と判断しました.

これにより, 具象ソルバ(AnnealingModelなど)は, アルゴリズムの実装に集中でき, 評価ロジックを意識することなく, protectedメソッドを通じて評価器の機能を利用できます.

継承による機能の限定公開(protected化)

AbstractSolverは, 評価器の存在を具象ソルバから隠すため, protectedメソッドを通じて提供しています.

// AbstractSolver.cs の protected メソッド(抜粋)
protected double Evaluate(List<int> orderList)
{
    // ... nullチェック
    return _evaluator.Evaluate(orderList);
}

protected double CalculateDelta_2Opt(List<int> orderList, int i, int j)
{
    // ... nullチェック
    return _evaluator.CalculateDelta_2Opt(orderList, i, j);
}
// ...

この設計により, 評価器の存在や操作はAbstractSolverの内部にカプセル化され,
具象ソルバは「経路を評価する」「差分を計算する」という抽象的なアクションだけを利用できます.
外部層からはこれらの詳細が見えないため, アルゴリズムのコアロジックが安全に保たれます.

TSP の評価エンジン

前章で, AbstractTspSolverがSetProblemメソッド内で評価器Evaluatorを生成し, 保持していることを見ました.
本章では, この評価器の設計と, 計算効率を左右する差分評価の仕組みを解説します.

IEvaluator の設計意図

IEvaluatorTSP の経路コスト評価ロジックをソルバの実行ロジックから完全に分離するためのインターフェースです.
このインターフェースは, 以下の 2 つの主要な計算機能のみを提供します.

メソッド名	役割	目的
Evaluate(List<int> order)	全経路評価	経路全体の総コストを算出します
CalculateDelta_2Opt(List<int> order, int i, int j)	差分評価(2-opt)	2-opt 操作によるコストの変化量を計算します

IEvaluatorは抽象インターフェースなので, 通常であれば Common プロジェクトに置くのがセオリーです.

しかし, 実装はこのようにしています.

抽象インターフェースであるIEvaluatorを, 実装であるEvaluatorと同じ場所に置いています.
この理由は, Evaluatorを参照するクラスは Solver プロジェクトのみに存在するからです.
Solver 以外のプロジェクトからはEvaluatorは参照されず,
したがって Common プロジェクトに置くのは不適切であると判断しました.

Evaluator の実装

Evaluatorの設計目標は, 計算結果の再利用による効率化です.
これを実現するため, Evaluatorは距離のキャッシュとルートコストキャッシュという,
2 段構えのキャッシュ戦略を採用しています.

1. 距離キャッシュ(_distanceDict): 都市間の距離計算結果を保持
2. ルートコストキャッシュ(_routeCostCache): 過去に評価した経路の総コストを保持

1. 距離キャッシュ(エッジコストの再利用)

都市間の距離計算(GetDistanceメソッド)は平方根の計算を含み, コストがかかります.
TSP の評価計算では同じ都市間の距離を何度も参照するため, Evaluatorは計算結果を都度キャッシュします

private double GetDistance(int cityId0, int cityId1)
{
    double dist;
    bool existence = _distanceDict.TryGetValue((cityId0, cityId1), out double value);
    if (existence)
    {
        dist = value;
    }
    else
    {
        var coordnate0 = _coordinates[cityId0];
        double x0 = coordnate0.X;
        double y0 = coordnate0.Y;

        var coordinate1 = _coordinates[cityId1];
        double x1 = coordinate1.X;
        double y1 = coordinate1.Y;

        dist = Math.Sqrt((x1 - x0) * (x1 - x0) + (y1 - y0) * (y1 - y0));
        _distanceDict[(cityId0, cityId1)] = dist;
        _distanceDict[(cityId1, cityId0)] = dist;
    }

    return dist;
}

2. ルートコストキャッシュ(経路評価の再利用)

Evaluateメソッドは, 与えられた訪問順序(orderList)をキーとして, すでに計算結果が無いかを確認します.

public double Evaluate(List<int> orderList)
{
    string routeKey = string.Join(",", orderList);
    if (_routeCostCache.TryGetValue(routeKey, out double cachedCost))
    {
        // 過去に計算済みなら, それを返す
        return cachedCost;
    }
    // ... 計算ロジック ...
}

これは, 特に探索アルゴリズムが過去に探索した解に再び遭遇した場合に有効です.
全経路の総和計算(O(N))をスキップして定数時間(O(1))でコストを返すことで,
動的計画法のような効率化を実現します.

差分評価ロジックについて

メタヒューリスティクスが最適化を実行する際, 最も多く実行される操作が近傍探索です.
近傍探索とは, 解を僅かに変更することにより, 次の解のベースを探すことです.
この評価には, CalculateDelta_2Optが使用されます.

このメソッドは, 全経路のコストを再計算せず, 2-opt 操作によって削除される 2 つのリンクと,
新しく生成される 2 つのリンクの距離だけを参照して, コストの変化量を計算します.

// CalculateDelta_2Optの核となる計算
double oldDist = GetDistance(city_before_i, city_i) + GetDistance(city_j, city_after_j);
double newDist = GetDistance(city_before_i, city_j) + GetDistance(city_i, city_after_j);

return newDist - oldDist;

この計算は, 都市数 N に関わらず定数時間(O(1))で完了します.
GetDistance内部も距離キャッシュによって高速化されているため,
評価のオーバーヘッドは最小限に抑えられます.

ソルバの生成

思想: ファクトリーパターン(SolverFactory)

本フレームワークは, 将来的に焼きなまし法, 遺伝的アルゴリズム, 島モデルなど, 様々なアルゴリズム(具象ソルバ)を追加・切り替えられるように設計されています. この「生成されるオブジェクト(ソルバ)の種類を, 生成要求元が知らずに済む」という設計思想を実現するのが, ファクトリーパターンを実装した SolverFactory です.

クラス	責務	メリット
Processor 層	ISolver の使用	具象クラス(AnnealingModel など)に依存せず, 実行の契約のみに集中できる.
SolverFactory	ISolver の生成	実行設定に基づき, 適切な具象クラスを選択し, 必要な依存関係を注入してインスタンス化する責務を一手に引き受ける.

依存関係は以下の通りです.

Processorは, SolverFactoryに対して「設定ファイルに基づいたソルバをください」と要求するだけで済みます.

実装: 設定に基づくソルバインスタンスの切り替え

SolverFactoryの核心は, 受け取ったモデル種別(AlgorithmModels)に基づき, 対応する具象ソルバクラスを瞬時に選択し, 必要な依存関係(IMLflowClient)を注入することにあります.

この切り替え機構は, C# 8.0以降で導入されたスイッチ式(switch expression)を用いて実装されています.

// SolverFactory.cs
public static ISolver GetSolver(AlgorithmModels modelType, IMLflowClient client)
{
    return modelType switch
    {
        AlgorithmModels.AnnealingModel => new AnnealingModel(client),
        AlgorithmModels.GeneticAlgorithm => new GeneticModel(client),
        AlgorithmModels.IslandModel => new IslandModel(client),
        _ => throw new Exception($"Invalid type: {modelType}")
    };
}

この実装により, IMLflowClientはプライマリコンストラクタを通じて具象ソルバに注入され,
設定に応じた完全に初期化済みのISolverインスタンスが上位層に提供されることで, すべての依存解決が完了します.

まとめと次回予告

この連載は, このSolverFactoryの仕組みをもって, フレームワーク設計と共通基盤の実装に関する解説を完了します.

次回は, いよいよ具象ソルバであるAnnealingModelやGeneticModelなどの個別アルゴリズムの実装と, それらを用いた実験結果について解説する予定です.