ニューラルネット Report2

top > ニューラルネット Report2

課題：NNで巡回セールスマン問題（Travelling Salesmen Problem ; TSP）を解く．
その際，ソースファイルtsp.cにて都市配置を指定してあるが，
その都市配置を各自任意に指定して動かしてみること．

1.デフォルトの設定で動作させてみる

struct { double x, y; } cityxy[CityNo] =
{ { 3.0, 4.0 }, { 2.0, 7.0 }, { 4.0, 7.0 }, { 5.0, 5.0 },
    { 5.0, 3.0 }, { 4.0, 1.0 }, { 2.0, 1.0 }, { 1.0, 3.0 },
    { 1.0, 5.0 } };

結果

    ###   Sequence     Cycle :   49   ###
City     1      2      3      4      5      6      7      8      9
   1   0.03   0.03   0.03   0.06   0.98   0.06   0.03   0.03   0.03
   2   0.06   0.99   0.08   0.03   0.01   0.01   0.00   0.00   0.01
   3   0.02   0.07   0.99   0.08   0.02   0.01   0.00   0.00   0.01
   4   0.01   0.02   0.06   0.99   0.10   0.02   0.01   0.01   0.01
   5   0.01   0.01   0.01   0.02   0.10   0.99   0.06   0.02   0.01
   6   0.01   0.00   0.00   0.01   0.02   0.08   0.99   0.07   0.02
   7   0.01   0.00   0.00   0.01   0.01   0.03   0.08   0.99   0.06
   8   0.06   0.02   0.01   0.01   0.01   0.02   0.02   0.07   0.99
   9   0.99   0.07   0.02   0.02   0.01   0.01   0.01   0.02   0.06
 Energy = 6.627321

2.都市の座標を変更してみるその1

struct { double x, y; } cityxy[CityNo] =
{ { 1.0, 4.0 }, { 3.0, 2.0 }, { 5.0, 2.0 }, { 1.0, 1.0 },
    { 2.0, 1.0 }, { 2.0, 5.0 }, { 1.0, 8.0 }, { 2.0, 6.0 },
    { 1.0, 7.0 } };

結果

    ###   Sequence     Cycle :   49   ###
City     1      2      3      4      5      6      7      8      9
   1   0.03   0.02   0.01   0.07   0.99   0.05   0.02   0.02   0.04
   2   0.99   0.12   0.05   0.04   0.02   0.01   0.00   0.00   0.04
   3   0.07   0.98   0.06   0.02   0.01   0.00   0.00   0.00   0.02
   4   0.02   0.05   0.07   0.99   0.03   0.01   0.00   0.00   0.02
   5   0.02   0.12   0.99   0.07   0.02   0.00   0.00   0.00   0.02
   6   0.04   0.01   0.01   0.02   0.03   0.04   0.04   0.07   0.99
   7   0.00   0.00   0.00   0.00   0.02   0.07   0.99   0.08   0.01
   8   0.02   0.00   0.00   0.01   0.02   0.04   0.11   0.99   0.05
   9   0.01   0.00   0.00   0.01   0.03   0.99   0.14   0.06   0.02
 Energy = 6.801940

3.都市の位置を変更してみるその2

struct { double x, y; } cityxy[CityNo] =
{ { 1.0, 1.0 }, { 2.0, 2.0 }, { 3.0, 3.0 }, { 4.0, 4.0 },
    { 1.0, 1.0 }, { 2.0, 2.0 }, { 3.0, 3.0 }, { 4.0, 4.0 },
    { 1.0, 1.0 } };

結果

    ###   Sequence     Cycle :   49   ###
City     1      2      3      4      5      6      7      8      9
   1   0.01   0.98   0.02   0.00   0.00   0.00   0.02   0.02   0.10
   2   0.85   0.07   0.03   0.02   0.01   0.02   0.03   0.12   0.03
   3   0.00   0.02   0.97   0.10   0.05   0.10   0.02   0.03   0.00
   4   0.00   0.00   0.01   0.11   1.00   0.11   0.01   0.00   0.00
   5   0.93   0.03   0.02   0.00   0.00   0.00   0.02   0.02   0.12
   6   0.01   0.06   0.02   0.02   0.01   0.02   0.03   0.08   0.98
   7   0.00   0.02   0.02   0.10   0.05   0.10   0.97   0.03   0.00
   8   0.00   0.00   0.00   0.87   0.02   0.87   0.00   0.00   0.00
   9   0.01   0.03   0.02   0.00   0.00   0.00   0.02   0.97   0.10
 Energy = 8.233629

4.値を20に増やしてみる

struct { double x, y; } cityxy[CityNo] =
{ { 1.0, 1.0 }, { 1.0, 2.0 }, { 1.0, 3.0 }, { 1.0, 4.0 },
  { 2.0, 1.0 }, { 2.0, 2.0 }, { 2.0, 3.0 }, { 2.0, 4.0 },
  { 3.0, 1.0 }, { 3.0, 2.0 }, { 3.0, 3.0 }, { 3.0, 4.0 },
  { 4.0, 1.0 }, { 4.0, 2.0 }, { 4.0, 3.0 }, { 4.0, 4.0 },
  { 5.0, 1.0 }, { 5.0, 2.0 }, { 5.0, 3.0 }, { 5.0, 4.0 } };

結果

    ###   Sequence     Cycle :   49   ###
City     1      2      3      4      5      6      7      8      9     10     11     12     13     14     15     16     17     18     19     20
   1   0.06   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.07   0.06   0.03   0.02   0.02   0.02
   2   0.06   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.06   0.02   0.02   0.02   0.02
   3   0.06   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.06   0.02   0.02   0.02   0.02
   4   0.06   0.07   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.06   0.02   0.02   0.02   0.03
   5   0.07   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.06   0.03   0.02   0.03   0.03
   6   0.07   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.07   0.03   0.02   0.02   0.03
   7   0.07   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.07   0.03   0.02   0.02   0.03
   8   0.06   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.07   0.03   0.03   0.02   0.03
   9   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.07   0.03   0.03   0.03   0.03
  10   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.03   0.03   0.03   0.03
  11   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.03   0.03   0.03   0.03
  12   0.07   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.08   0.03   0.03   0.03   0.03
  13   0.09   0.07   0.07   0.07   0.07   0.07   0.07   0.07   0.07   0.07   0.07   0.07   0.07   0.07   0.07   0.08   0.04   0.03   0.04   0.03
  14   0.10   0.08   0.07   0.07   0.07   0.07   0.07   0.07   0.07   0.07   0.07   0.07   0.07   0.07   0.08   0.09   0.03   0.03   0.04   0.03
  15   0.09   0.07   0.07   0.07   0.07   0.07   0.07   0.07   0.07   0.07   0.07   0.07   0.07   0.07   0.08   0.10   0.03   0.04   0.03   0.03
  16   0.08   0.07   0.07   0.07   0.07   0.07   0.07   0.07   0.07   0.07   0.07   0.07   0.07   0.07   0.08   0.09   0.03   0.04   0.03   0.04
  17   0.03   0.03   0.03   0.03   0.03   0.03   0.03   0.03   0.03   0.03   0.03   0.03   0.03   0.03   0.03   0.03   0.02   0.97   0.02   0.01
  18   0.04   0.03   0.03   0.03   0.03   0.03   0.03   0.03   0.03   0.03   0.03   0.03   0.03   0.03   0.03   0.03   0.02   0.02   0.02   0.97
  19   0.03   0.03   0.03   0.03   0.03   0.03   0.03   0.03   0.03   0.03   0.03   0.03   0.03   0.03   0.03   0.04   0.97   0.02   0.02   0.02
  20   0.03   0.03   0.03   0.03   0.03   0.03   0.03   0.03   0.03   0.03   0.03   0.03   0.03   0.03   0.03   0.03   0.01   0.02   0.97   0.02
 Energy = 33.141362

5.考察

都市の位置を変更しても収束していることが今回の結果で分かった。
このことから、都市の相対位置は演算にあまり影響を及ぼさないことが推測できる。
しかし、都市の数を増やしてみると収束しなくなった。
グラフを見ると、繰り返し回数を増やしても意味がないことがわかる。
これより、都市数が多い巡回セールスマン問題を
Hopfieldで解くのはあまり効率的ではないことが考えられる。