y_uti のブログ

統計、機械学習、自然言語処理などに興味を持つエンジニアの技術ブログです

巡回セールスマン問題の近似解法と 2-opt 改善法

前回の記事に続き、巡回セールスマン問題の近似解法について調べてみます。前回は、いくつかの近似解法を実装して、問題を解く様子をアニメーションで紹介しました。今回は、それぞれの解法でどのくらい良い解が求められるのかを比較してみます。
巡回セールスマン問題の近似解法を眺める - y_uti のブログ

まず、サンプルデータを作成します。次のコードを引数 100 として実行し、1 ≤ x, y ≤ 1,000,000 の範囲に 100 都市をランダムに生成します。今回は、これを 100 回実行して 100 個のデータを作成しました。なお、都市の範囲や出力書式は paiza の問題 の設定に合わせたものです。

<?php
$n = $argv[1];
echo $n, "\n";
for ($i = 0; $i < $n; ++$i) {
    $x = mt_rand(1, 1000000);
    $y = mt_rand(1, 1000000);
    echo "$x $y\n";
}

作成された 100 サンプルを近似解法で解いた結果は以下のとおりです。NN, RI 等は、それぞれ前回の記事で紹介したアルゴリズムです。縦軸が 100 都市を訪れるルートの総距離です。箱ひげ図に重ねて各サンプルを描画しています。左右の位置は見やすいようにランダムに散らしたもので、特に意味はありません。箱ひげ図は既定の設定で描画しました。真ん中の橙線が中央値、箱の上下端が四分位数です。ひげの上下端は、上端の場合は Q3 + (Q3 - Q1) * 1.5 を超えない最大のデータを示しており*1、これを超えるデータは外れ値として丸印で描画されます。
f:id:y_uti:20171109230342p:plain

この結果からは、Farthest Insertion 法や Random Insertion 法で良い結果が得られているようです。4 種類の Insertion 法の比較については、前回の記事で参照した MIT の講義資料ともよく一致しています。

In practice "Farthest Insertion" and "Random Insertion" (+9%, +11%) seem to perform better than "Cheapest" and "Nearest" (+16%, +19%)

Network: Lecture 2, "Emperical Performance: Insertion Heuristics" (MIT OCW の講義資料)
2-opt 改善法

巡回セールスマン問題では、近似解法で得られた経路を改善していく方法も知られています。今回は、2-opt 法を実装して改善の効果を確認してみます。

2-opt 法は、経路の中から適当に二つの辺を選択して、ルートを入れ替えてみる方法です。その結果として距離が短縮されれば新ルートを採用する、という処理を繰り返します。例として、ルートが交差している場合を考えると分かりやすいと思います。下図の左のようにルートが交差している場合、右のように入れ替えることで距離が短縮されます。
f:id:y_uti:20171111095242p:plain:w480

前回と同様に PHP を用いて、2-opt 法を次のように実装しました。make_candidates 関数で入れ替えの候補を列挙し*2、ルートを改善できなくなるまで処理を繰り返します。improve 関数ではルートを入れ替えて距離が短縮されるかどうかを調べます。距離が短縮される場合には optimize 関数でルートを入れ替えます。上図に示したように、ルートを入れ替えると中間の都市の訪問順が逆転します。連結リストを利用すれば計算量の面では効率がよいと思いますが、今回は簡単のため array_reverse を用いました。

<?php
function solve($data) {
    $candidates = make_candidates($data);
    $improved = true;
    while ($improved) {
        $improved = false;
        shuffle($candidates);
        foreach ($candidates as [$i, $j]) {
            if (improve($data, $i, $j)) {
                $improved = true;
                optimize($data, $i, $j);
            }
        }
    }
    return $data;
}

function make_candidates($data) {
    $candidates = [];
    $n = count($data);
    for ($i = 0; $i < $n - 1; ++$i) {
        for ($j = $i + 2; $j <= $n; ++$j) {
            $candidates[] = [$i, $j];
        }
    }
    return $candidates;
}

function improve($data, $i, $j) {
    $prev = $i == 0 ? [0, 0] : $data[$i - 1];
    $next = $j < count($data) ? $data[$j] : false;
    $cost = distance($prev, $data[$j - 1]) - distance($prev, $data[$i]);
    if ($next) {
        $cost += distance($data[$i], $next) - distance($data[$j - 1], $next);
    }
    return $cost < 0;
}

function optimize(&$data, $i, $j) {
    $reversed = array_reverse(array_slice($data, $i, $j - $i));
    array_splice($data, $i, $j - $i, $reversed);
}

2-opt 法の動作の様子をアニメーションで示します。Nearest Neighbour 法で求められたルートを 2-opt で改善していきます。Iteration の数字は、実際にルートの入れ替えが行われた回数を表しており、この例では 34 回の改善で収束しています。
f:id:y_uti:20171111102707g:plain

さて、記事の最初に示した近似解法ごとの結果の比較について、それぞれを 2-opt 法で改善した場合は以下のようになりました。Greedy 法や Nearest Neighbour 法は 2-opt 法で大きな改善が見られ、Insertion 法よりも良い解が得られるようになっています。
f:id:y_uti:20171111103111p:plain

このことについては、下記の紀要論文の 2 節で触れられていました。論文では「改善法にかかりやすい」「改善法にかかりにくい」と表現されています。Nearest Neighbour 法や Greedy 法は、終盤で極端に長い辺を作ってしまうために全体の距離が長くなってしまうものの、部分的には最適な経路と同じ辺を多く含む傾向があり、2-opt のような改善法で大きく改善できるということのようです。
巡回セールスマン問題の近似アルゴリズムについて

私が paiza の問題に取り組んだときには、改善法を実装しない段階で Nearest Neighbour 法と Random Insertion 法を比較して、Random Insertion 法で良い結果が得られたので NN + 2-opt などは試しませんでした*3。paiza の問題は現在でも実行できるようだったので改めて試してみたところ、初期解の求め方を Random Insertion 法から Greedy 法に変更して 2-opt 法を用いたところ、たしかにスコアが向上することを確認できました*4

*1:Q1 は第一四分位数、Q3 は第三四分位数です。1.5 という数値は boxplot のオプションで指定できます。

*2:収束判定のために全ての候補を列挙しています。適当な回数で止めるというような方法であれば、その都度ランダムに選択すればよいので、候補を列挙する必要はありません。

*3:Insertion 法の方が良いという結果が私の直感に合っていたという理由もあり、その時点で Nearest Neighbout 法を完全に捨ててしまいました。

*4:ウェブサイトで公開されているスコアも現在でも更新されてしまうようで、今度は以前のスコアが分からなくなってしまいました。たしか 135 台だったように記憶しています。今回の方法で 132,612 に向上しました。