TIM Labs

2018年12月アーカイブ

遺伝といえばメンデルである。

あのエンドウ豆のシワの有無による研究により、遺伝学が始まったと言われている。

とくに、隔世遺伝というのがあり、子供には親の性質が現れないのに、孫には祖父母の性質が現れるという性質である。

さて、問題は、

一般的な遺伝的アルゴリズムの実装において、隔世遺伝は成り立っているのであろうか?

もう年末も近いので、問題の提起だけしておこうと思う。

正月休みに、ちょっと考えて見て欲しい。

では、良いお年を。

2人での巡回セールスマン問題は、以下のように考えると、できる。

TPS2-exp1.png

上は、両端がない循環しない紐状のルートの場合である。
これの両端の2つの街の間の距離も加え、全体でリング状になるとしたのが一般的な巡回セールスマン問題である。

ここでは、その下側のように、両端にベース(基地)を加えたものを考え、それらの間の距離も考えることにする。
すると、①がセールスマン1の巡回路になり、②がセールスマン②の巡回路になる。

これで、二人のセールスマンの巡回路が決まるので、その長さを求め、最小化すべきものを計算することで、いままでと同様に遺伝的アルゴリズムにより、二人巡回セールスマン問題が解ける。

これが分かれば、次のように考えると3人巡回セールスマン問題も解ける。

TPS2-exp2.png

3人の場合には、両端のない経路を考える時点で、既にベース(基地)が2つ入っている。

この場合、単にベースを2つ、その他の街を1つずつの並べ替えを考えれば良いだけである。

適当に並べたときに、ベースが連続する場合があり、その場合、全くなにもしない移動距離ゼロのセールスマンが発生する訳だが、その場合にはサラリーマン間の移動距離の差が大きくなるので、そのようなケースは自動的に排除されるので、何も問題ない。

このようにして、複数人で手分けをして回る場合の巡回セールスマン問題で、公平で合理的なルートを求めることができるのである。

この他にも、さまざまな条件の巡回セールスマン問題があるので、詳しくは各自で調べてみよう。

いや、自分で勝手にさまざまな条件をでっち上げて、考えてみるのも良いだろう。

一般的な巡回セールスマン問題は、一人のセールスマンが多数の街を巡回することになっているが、これでは過重労働になり、過労死するかも知れない。

ということで、セールスマンを増員してみよう。

2人のセールスマンは、いずれもセンター(基地、本社、本部、、、、何と呼んでも良いのだが)から出発して、全ての街をいずれかのセールスマンが立ち寄り、二人とも出発点のセンターに戻ってくるとする。

2人の負荷はできるだけ差が少ないことが望ましい。それで、各人の経路長の差を少なくしたい。かつ、各人の経路長も短くしたい。

それで、平均経路長+経路長の差 をできるだけ小さく(短く)することにしてみた。

すると、こんな結果が得られた。

100-2-2-2202-s.png    100-2-2-2120-s.png

左は赤と青の巡路が分かれているが、右は巡路が交叉している。

点の位置は同じになっているのだが、どちらが 平均経路長+経路長の差 が小さくなっている、つまり望ましいプランであろうか?

このアーカイブについて

このページには、2018年12月に書かれたブログ記事が新しい順に公開されています。

前のアーカイブは2018年11月です。

次のアーカイブは2019年1月です。

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。

月別 アーカイブ