この記事の目的
本記事では、数理最適化問題でよく出てくる巡回セールスマン問題の簡単な例題について、遺伝的アルゴリズム(Genetic Algorithm, GA)を応用したソルバーであるPythonライブラリの「vcopt」を使用し、解を探ってみます。また、vcoptについて「巡回セールスマン問題に代表される順序の大域最適化」の解き方及び使い方を見てみます。
vcoptって何?
ビネット＆クラリティ合同会社( https://vigne-cla.com/ )により開発された、遺伝的アルゴリズム(Genetic Algorithm, GA)を使用した組合せ最適化ソルバーです。Python言語で書かれています。同ソルバーには様々な機能が実装されていますが、今回は順序(並び替え)の大域最適化を求める機能[vcopt().tspGA()関数]で解を求めてみます。
例題
さっそく巡回セールスマン問題の例題を見てみましょう。
問題
5都市を訪問するとし、都市間の移動距離が表5.1で与えられている巡回セールスマン問題を考える。
例えば、A-B-C-D-E-Aと訪問すると移動総距離は 30 + 30 + 25 + 30 + 10 = 125 となる。
もっとも移動距離が少なく済むような巡回経路を考えよ。
表5.1
| B | C | D | E | |
|---|---|---|---|---|
| A | 30 | 30 | 25 | 10 |
| B | 30 | 45 | 20 | |
| C | 25 | 20 | ||
| D | 30 |
問題設定により、各都市間の距離が定義されていますので、各経路ごとにこの距離を計算すれば解が得られます。
vcoptにはこれに関して「順序の大域最適化」を計算する関数[tspGA()]というものが標準で用意されていますので、これを利用します。(tspGA()の詳細は、vcoptのチュートリアル等をご参照下さい)
お手軽最適化パッケージ「vcopt」チュートリアル
https://vigne-cla.com/vcopt-tutorial/
ただし、上記関数[tspGA()]を利用する際に、パラメータの一つに評価関数の設定が必要になります。
この評価関数は経路ごとの総距離を算出する関数として独自実装が必要となります。
また、問題文には明記されていませんが、この問題では都市Aを出発して再び都市Aに帰着する前提とします。一周回って帰ってくる経路を図で表すと線がつながった、丸に近い図形(いびつな円形)になることが想像されます。線が途中で切れていたり、同じ経路で重なることはありません。これを閉路と呼びます。
この閉路を求める際にもvcoptにその解法の説明がありますので、これを応用します。
8-6. vcoptで巡回セールスマン問題を解く（閉路はどうやるの？編）
https://vigne-cla.com/8-6/
解答
プログラムを検討します。
まず、必要なライブラリを読み込みます。
from vcopt import vcopt
import numpy as np
以下で評価関数の定義をします。上述しました通り、関数[tspGA()]を実行するときに必要な引数(パラメータ)の一つです。
#都市間の距離を計算する関数
def tsp_score(para):
para_full = np.hstack((0, para, 0)) ... (1)
上記、vcoptが組み合わせ最適化問題を解く際にこの評価関数の値を計算し、最大化または最小化あるいは目標値に近づくように計算するためのものです。
今回は巡回セールスマン問題において総距離をなるべく少なくすることが目的なので、各都市を巡回した際の総距離を計算する内容の関数を定義します。関数名はtsp_scoreとします。引数として、各都市を表すインデックス番号の配列(para)とします。ここで気を付けることは、都市Aだけ含まない点です。このインデックス番号配列の内容は後述します。
上記の(1)について、「vcoptで巡回セールスマン問題を解く（閉路はどうやるの？編）」に詳細な説明がありますが、都市Aを出発し他の都市を巡回した後、再び都市Aに戻る条件を設定するための一文です。
数字の0は都市Aのインデックス番号とします。以下に都市を表すインデックス番号を定義します。
※「...(1)」はプログラムに書かないで下さい。
次に、都市間の距離を定数として定義します。
dis = [[0 for i in range(5)] for j in range(5)]
dis[0][0] = 50
dis[0][1] = 30
dis[0][2] = 30
...
上記について、定数名をdisとした2次元配列としました。
例えば都市A(インデックス番号：0)から都市B(インデックス番号：1)へ移動した場合は、dis[0][1]で値を設定します。設定値は30です。
上記のソースは一部だけ掲載しました。実際のソースでは全都市間を設定します。本記事の最後にソース全体を掲載しますので、そちらをご参照下さい。
同じ都市を続けて巡回することはできないので、同じインデックス番号が続く場合は距離の値を50としています。同じ都市を巡回しないようにあえて大きな値を設定することで、評価関数の値を大きくし、最適化の解として選ばれないようにします。
評価関数の残りの定義を以下に示します。
distance = 0
for step in range(5):
distance += dis[para_full[step]][para_full[step + 1]]
return distance
上記は都市間を移動した際の総距離(変数名：distance)を算出し、関数の呼び出し元に返却する処理です。
stepは都市を巡回するとき何番目に訪れるか?を表す数字です。
for文でstepを0～4としてループさせ、step番目の都市とstep+1番目の都市間の移動距離を合計します。
評価関数の定義は以上です。
プログラムの主処理に入ります。
para = [1,2,3,4]
上記は、関数[tspGA()]に与えるパラメータで、組み合わせを考える対象の要素です。今回の問題では巡回する都市を並べ替えて(組み合わせて)解を求めるため、要素となるものは都市番号です。
ただし、上述しましたが、巡回始点と終点の都市はAとしますので、都市Aは既に決定しており並べ替え(組み合わせ)の対象とはなりません。対象となるのは都市B～Eで、インデックス番号は1～4です。
先ほど定義した評価関数[tsp_score()]にも引数paraが設定されていますが、これは同じ変数を指します。
tsp_score関数はvcoptがtsp_score()を実行する際に内部的に呼び出され、パラメータparaも自動的に設定されます。
次に、最適化の解の算出を行う関数[tspGA()]を実行します。
para, score = vcopt().tspGA(para, # 並び替え対象要素
tsp_score, # 評価関数
0.0) # 目標値
上記でtspGA()を呼び出す際の引数(パラメータ)を3つ設定します。
引数一つ目は「並び替え対象要素」です。今回は都市Aを除く全ての都市のインデックス番号です。
引数二つ目は「評価関数」です。評価関数の内容は、この関数の定義部分で説明しました。
引数三つめは「目標値」です。目標値は0としています。実際に移動距離が0になることはありませんが、移動距離が最も小さい巡回経路が問題の解となるため、小さくなる方向を定めるために0とします。
なお、引数(パラメータ)の詳細は、vcoptのチュートリアルをご参照下さい。
関数の返却値は2つあり、paraは並べ替えた後の配列、scoreは最適化後の解として算出された総距離(最小距離)です。
以下、プログラムの最後にparaとscoreを画面表示させます。
print('para=',para)
print('score=',score)
以上でプログラミングは終了です。
実際の実行結果は以下となりました。
___________________ info ___________________
para_range : n=4
score_func :
aim : 0.0
show_pool_func : 'bar'
seed : None
pool_num : 40
max_gen : None
core_num : 1 (*vcopt, vc-grendel)
___________________ start __________________
Scoring first gen 40/40
Mini 2-opting first gen 40/40
| +<| gen=80, best_score=110.0
__________________ results _________________
para : [3 2 1 4]
score : 110.0
____________________ end ___________________
para= [3 2 1 4]
score= 110.0
最適化の結果、解は以下となりました。
para = [3 2 1 4]
これは都市の巡回経路が都市D,C,B,Eを表します。
今回は都市Aが始点かつ終点なので、最終的に巡回経路は以下とすれば良いことがわかりました。
巡回経路 A → D → C → B → E → A
また、総距離は 110 となります。
以下、プログラム全体を示します。
from vcopt import vcopt
import numpy as np
#巡回セールスマン問題
#都市間の距離を計算する関数
def tsp_score(para):
para_full = np.hstack((0, para, 0))
dis = [[0 for i in range(5)] for j in range(5)]
dis[0][0] = 50
dis[0][1] = 30
dis[0][2] = 30
dis[0][3] = 25
dis[0][4] = 10
dis[1][0] = 30
dis[1][1] = 50
dis[1][2] = 30
dis[1][3] = 45
dis[1][4] = 20
dis[2][0] = 30
dis[2][1] = 30
dis[2][2] = 50
dis[2][3] = 25
dis[2][4] = 20
dis[3][0] = 25
dis[3][1] = 45
dis[3][2] = 25
dis[3][3] = 50
dis[3][4] = 30
dis[4][0] = 10
dis[4][1] = 20
dis[4][2] = 20
dis[4][3] = 30
dis[4][4] = 50
distance = 0
for step in range(5):
distance += dis[para_full[step]][para_full[step + 1]]
return distance
para = [1,2,3,4]
para, score = vcopt().tspGA(para, # 並び替え対象要素
tsp_score, # 評価関数
0.0) # 目標値
print('para=',para)
print('score=',score)
出展
本記事は、数理最適化について以下の参考テキストに記載の練習問題を参考にさせて頂いております。
■参考テキスト
「ITText 数理最適化」
久野誉人・他[著]
情報処理学会[編集]
ご意見など
ご意見、間違い訂正などございましたらお寄せ下さい。