2-opt
組合せ最適化において、2-opt は巡回セールスマン問題を解く局所探索法の1つである。
2-optは、Croesによって1958年に初めて提案されたが[1]、基本的な動作は既にFloodによって提案されていた[2]。背景にある基本的なアイディアは、交わる経路はそうならないように順路を変更できるということである。完全な2-optは、交換可能なすべての組合せを比較する。この手法は、巡回セールスマン問題だけでなく、関連する多くの問題にも適用できる。例えば、配送計画問題（Vehicle Routing Problem; VRP）やその容量付き版などが挙げられるが、これらの問題に適用するためにはアルゴリズムを少し修正する必要がある。
擬似コード
[編集]図で表すと、交換は次のように行う。
- A B - - A - B -
× ==>
- C D - - C - D -
擬似コードでは、経路を更新するルーチンは次のようになる。
'''procedure''' 2optSwap(route, v1, v2) {
1. route[0]からroute[v1]までを順番にnew_routeに追加する。
2. route[v1+1]から、route[v2]までを、逆順にnew_routeに追加する。
3. route[v2+1]から末尾までを順番にnew_routeに追加する。
'''return''' new_route;
}
以下は、2optSwapの動作例である。
- 経路(変数 route): A → B → E → D → C → F → G → H → A
- v1=1, v2=4 (開始インデックスを0とする)
- ステップ毎のnew_routeの内容:
- (A → B)
- A → B → (C → D → E)
- A → B → C → D → E → (F → G → H → A)
2optSwapをサブモジュールとして、完全な2-optは次のように書ける。
'''repeat until''' 改善が見られない {
best_distance = calculateTotalDistance(existing_route)
start_again:
'''for''' (i = 0; i <= 交換可能なノード数 - 1; i++) {
'''for''' (j = i + 1; j <= 交換可能なノード数; j++) {
new_route = 2optSwap(existing_route, i, j)
new_distance = calculateTotalDistance(new_route)
'''if''' (new_distance < best_distance) {
existing_route = new_route
best_distance = new_distance
goto start_again
}
}
}
}
始点や終点にある特定のノードは、順番を逆にすると無効な経路になるため、交換の候補から外すべきである。例えば、Aに戻る経路を次のように表しているとする。
A → B → C → D → A
route[0]とroute[2]を交換すると、new_routeは次のようになり、正しい経路情報ではなくなる。
C → B → A → D → A
効率的な実装
[編集]新しい経路を構築しその距離を計算するのは、非常に高価な処理で、ふつうnを頂点数としてかかる。ただし、交換によって経路長が減少するかはで分かる。
lengthDelta = - dist(route[v1], route[v1+1]) - dist(route[v2], route[v2+1]) + dist(route[v1+1], route[v2+1]) + dist(route[v1], route[v2])
もしlengthDeltaが負であれば、交換後の新しい距離が短くなることを意味するので、そのときのみ2-optの交換を行うことで、計算コストを大幅に抑えられる。
C++ コード
[編集]#include <random>
#include <stdio.h>
#include <vector>
using namespace std;
class Point {
public:
float x, y;
Point(float x, float y) {
this->x = x;
this->y = y;
}
Point() {
this->x = 0.0;
this->y = 0.0;
}
// 二点間の距離を計算
inline float dist(const Point &other) const {
float diffx = x - other.x;
float diffy = y - other.y;
return sqrt(diffx * diffx + diffy * diffy);
}
};
// 経路全体の距離を計算
int pathLength(vector<Point> &path) {
int n = path.size();
float length = path[n - 1].dist(path[0]);
for (int i = 0; i < n - 1; i++) {
length += path[i].dist(path[i + 1]);
}
return length;
}
// path[i]->path[i+1] と path[j]->path[j+1] の二辺を
// それぞれ path[i]->path[j] と path[i+1]->path[j+1] で置き換える。
void swap_edges(vector<Point> &path, int i, int j) {
i += 1;
while (i < j) {
Point temp = path[i];
path[i] = path[j];
path[j] = temp;
i++;
j--;
}
}
// 経路を出力
void printPath(string pathName, vector<Point> &path) {
printf("%s = [", pathName.c_str());
for (int i = 0; i < path.size(); i++) {
if (i % 10 == 0) {
printf("\n ");
}
if (i < path.size() - 1) {
printf("[%.1f, %.1f], ", path[i].x, path[i].y);
} else {
printf("[%.1f, %.1f]", path[i].x, path[i].y);
}
}
printf("\n];\n");
}
// ノード数nのランダムな経路を作る。各ノードの座標はx,yともに0以上1000以下。
vector<Point> createRandomPath(int n) {
vector<Point> path;
for (int i = 0; i < n; i++) {
float x = (float)rand() / (float)(RAND_MAX / 1000);
float y = (float)rand() / (float)(RAND_MAX / 1000);
path.push_back(Point(x, y));
}
return path;
}
int main() {
vector<Point> path = createRandomPath(100);
printPath("path1", path);
float curLength = pathLength(path);
printf("path1len = %.1f;\n\n", curLength);
int n = path.size();
bool foundImprovement = true;
while (foundImprovement) {
foundImprovement = false;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 2; j < n; j++) {
float lengthDelta =
-path[i].dist(path[i + 1]) - path[j].dist(path[(j + 1) % n]) +
path[i].dist(path[j]) + path[i + 1].dist(path[(j + 1) % n]);
// もし経路の長さが短くなったのならば、実際に2-optを行い辺を交換する
if (lengthDelta < 0) {
swap_edges(path, i, j);
curLength += lengthDelta;
foundImprovement = true;
}
}
}
}
printPath("path2", path);
printf("path2len = %.1f;\n", curLength);
return 0;
}
出力
[編集]path1 = [
[0.0, 131.5], [755.6, 458.7], [532.8, 219.0], [47.0, 678.9], [679.3, 934.7], [383.5, 519.4], [831.0, 34.6], [53.5, 529.7], [671.1, 7.7], [383.4, 66.8],
[417.5, 686.8], [589.0, 930.4], [846.2, 526.9], [92.0, 653.9], [416.0, 701.2], [910.3, 762.2], [262.5, 47.5], [736.1, 328.2], [632.6, 756.4], [991.0, 365.3],
[247.0, 982.6], [722.7, 753.4], [651.5, 72.7], [631.6, 884.7], [272.7, 436.4], [766.5, 477.7], [237.8, 274.9], [359.3, 166.5], [486.5, 897.7], [909.2, 60.6],
[904.7, 504.5], [516.3, 319.0], [986.6, 494.0], [266.1, 90.7], [947.8, 73.7], [500.7, 384.1], [277.1, 913.8], [529.7, 464.4], [941.0, 50.1], [761.5, 770.2],
[827.8, 125.4], [15.9, 688.5], [868.2, 629.5], [736.2, 725.4], [999.5, 888.6], [233.2, 306.3], [351.0, 513.3], [591.1, 846.0], [412.1, 841.5], [269.3, 415.4],
[537.3, 467.9], [287.2, 178.3], [153.7, 571.7], [802.4, 33.1], [534.4, 498.5], [955.4, 748.3], [554.6, 890.7], [624.8, 842.0], [159.8, 212.8], [714.7, 130.4],
[91.0, 274.6], [3.0, 414.3], [26.9, 709.8], [937.9, 239.9], [180.9, 317.5], [887.0, 652.1], [150.3, 681.3], [385.8, 387.7], [499.7, 147.5], [587.2, 845.6],
[590.1, 955.4], [556.1, 148.2], [983.3, 408.8], [141.8, 564.9], [252.1, 488.5], [464.0, 961.1], [126.0, 199.8], [319.2, 629.3], [126.7, 651.3], [621.6, 803.1],
[247.8, 476.4], [389.3, 203.3], [28.4, 901.7], [426.5, 142.0], [947.5, 410.3], [131.2, 885.6], [92.2, 162.2], [71.1, 365.3], [253.1, 135.1], [783.2, 455.3],
[349.5, 452.3], [808.9, 931.7], [651.6, 215.2], [679.6, 908.9], [250.1, 860.9], [471.3, 506.0], [600.4, 817.6], [755.8, 462.2], [951.4, 632.7], [439.3, 824.7]
];
path1len = 55723.0;
path2 = [
[0.0, 131.5], [91.0, 274.6], [71.1, 365.3], [3.0, 414.3], [53.5, 529.7], [92.0, 653.9], [47.0, 678.9], [15.9, 688.5], [26.9, 709.8], [28.4, 901.7],
[131.2, 885.6], [247.0, 982.6], [277.1, 913.8], [464.0, 961.1], [486.5, 897.7], [439.3, 824.7], [412.1, 841.5], [250.1, 860.9], [150.3, 681.3], [126.7, 651.3],
[141.8, 564.9], [153.7, 571.7], [247.8, 476.4], [252.1, 488.5], [319.2, 629.3], [416.0, 701.2], [417.5, 686.8], [534.4, 498.5], [537.3, 467.9], [529.7, 464.4],
[516.3, 319.0], [500.7, 384.1], [471.3, 506.0], [383.5, 519.4], [351.0, 513.3], [349.5, 452.3], [385.8, 387.7], [272.7, 436.4], [269.3, 415.4], [180.9, 317.5],
[233.2, 306.3], [237.8, 274.9], [287.2, 178.3], [389.3, 203.3], [532.8, 219.0], [736.1, 328.2], [783.2, 455.3], [755.6, 458.7], [755.8, 462.2], [766.5, 477.7],
[846.2, 526.9], [904.7, 504.5], [868.2, 629.5], [736.2, 725.4], [761.5, 770.2], [722.7, 753.4], [632.6, 756.4], [621.6, 803.1], [600.4, 817.6], [624.8, 842.0],
[631.6, 884.7], [591.1, 846.0], [587.2, 845.6], [554.6, 890.7], [589.0, 930.4], [590.1, 955.4], [679.3, 934.7], [679.6, 908.9], [808.9, 931.7], [999.5, 888.6],
[955.4, 748.3], [910.3, 762.2], [887.0, 652.1], [951.4, 632.7], [986.6, 494.0], [947.5, 410.3], [983.3, 408.8], [991.0, 365.3], [937.9, 239.9], [827.8, 125.4],
[947.8, 73.7], [941.0, 50.1], [909.2, 60.6], [831.0, 34.6], [802.4, 33.1], [671.1, 7.7], [651.5, 72.7], [714.7, 130.4], [651.6, 215.2], [556.1, 148.2],
[499.7, 147.5], [426.5, 142.0], [359.3, 166.5], [383.4, 66.8], [262.5, 47.5], [266.1, 90.7], [253.1, 135.1], [159.8, 212.8], [126.0, 199.8], [92.2, 162.2]
];
path2len = 8586.2;
出力の可視化
[編集]
脚注
[編集]- ^ G. A. Croes (1958). “A Method for Solving Traveling-Salesman Problems”. Operations Research 6 (6): 791-812. doi:10.1287/opre.6.6.791.
- ^ Merrill M. Flood (1956). “The Traveling-Salesman Problem”. Operations Research 4 (1): 61-75. doi:10.1287/opre.4.1.61.