遺伝的アルゴリズムについて

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
ひっすー

遺伝的アルゴリズムについて

#1

投稿記事 by ひっすー » 8年前

初投稿です。遺伝的アルゴリズムのプログラムについて困ったので質問です。
【今やっていること】
遺伝的アルゴリズムを用いた巡回セールスマン問題を解くプログラム制作
【困っていること】
・エリート選択
・交叉
【具体的にいうと】
・エリート選択
 今は、純粋に一周するのにかかった総距離の短いもの上位2つを選んでいます。
 しかし、他の例にならってルーレット方式にしようと考えています。
 10このデータからルーレット方式で2こ選ぶとして
 どのように重みをつけ、偏ったルーレットを作れば良いのでしょうか?
 1つずつswitchで書くわけにもいかないと思います。具体的なコードで教えていただきたいです。
・交叉
 2このデータ(親)から10このデータ(子)を作ろうとしていますが、どの方式をとると良いのでしょうか?
 また、親のデータをそのまま受け継ぐ子データがあってもいいと思いますか?
 2こから4こはなんとなくわかりますが、5こ以上作るやり方がわかりません。

ひっすー

Re: 遺伝的アルゴリズムについて

#2

投稿記事 by ひっすー » 8年前

選択はそのまま上位2つを選び、交叉は下のようにしました。
ですが、最適化ができていません。
最初の方こそそれらしく(1周の総距離が)短くなっていきましたが、
よくみる、外側を1周するようにはなりません。何がいけないのでしょうか?
改善すべきところを教えてください。

【交叉】

コード:

int VolumeElite  = 2,VolumeRoute = 10,VolumeData = 20

for (int num = VolumeElite; num < VolumeRoute; num++) {
	if (rand (0, 5) % 5 != 0) {//80%の確率で交叉する
		for (int i = 0; i < VolumeData + 1; i++) {//+1は気にしないでください
			if (rand (0, 1) == 0) {//50%の確率で親1のデータ
				Gene [num][i] = Gene [0][i];			
	                } else {
				Gene [num][i] = Gene [1][i];//50%の確率で親2のデータ
				}
			}
		}
	}
}

たいちう
記事: 418
登録日時: 13年前

Re: 遺伝的アルゴリズムについて

#3

投稿記事 by たいちう » 8年前

交叉についてまずい所もありますが、それ以前の問題のような気がします。
遺伝的アルゴリズムは、突然変異と評価と選択さえ機能すれば、解が収束するはずです。
一旦、これらの機能のみを正しく作り、完成後に交叉を実装してはどうでしょうか。

おそらく交叉なしでも、うまく動いてないのだと思いますが、
適当な指摘のためには、ソース全体を載せてください。必要ならば都市のデータも。

くっちゃべー

Re: 遺伝的アルゴリズムについて

#4

投稿記事 by くっちゃべー » 8年前

しばらく返信できず、すみません。

順序表現・一様交叉からパス表現・順序交叉に変えてみました。
ですが、以前として解が収束しません。

やっぱり交叉以外の部分が問題のようですね。
現在、突然変異は確率1%で1データの通る都市2つを交換するようになっています。
また、評価は総距離に依存しています。
そして選択はルーレット方式になっています。

以下のように回答されましたが、どうすればこのことが確認できるのでしょうか?
突然変異の確率を上げてデータすべての通る都市の順番が同じになるまで待つとかでしょうか?
たいちう さんが書きました:
遺伝的アルゴリズムは、突然変異と評価と選択さえ機能すれば、解が収束するはずです。

たいちう
記事: 418
登録日時: 13年前

Re: 遺伝的アルゴリズムについて

#5

投稿記事 by たいちう » 8年前

「ひっすー」さん == 「くっちゃべー」さんでしょうか。
名前を統一してください。フォーラムルールも確認してください。


> やっぱり交叉以外の部分が問題のようですね。

うまくいっていない

交叉を変更

やはりうまくいっていない

この状況のみから言えることは、あまりありません。
交叉の変更前と変更後のそれぞれに問題があるかもしれないし、
交叉以外の部分に問題があるかもしれないし、
交叉と交叉以外の両方に問題があるかもしれません。


> 以下のように回答されましたが、どうすればこのことが確認できるのでしょうか?
> 突然変異の確率を上げてデータすべての通る都市の順番が同じになるまで待つとかでしょうか?

(1)まず、交叉をやめましょう。
それ以外の部分が完成してから挑戦してください。

(2)世代ごとに最も評価が高かった個体の総距離を比較してください。
世代が進むにしたがって、総距離は減っていくはずです。
絶対に親世代より悪化することがないようにしてください。(※)

(3)TSPは問題の性質上、必ず最適解を見つけられるわけではないですが、
都市数が10程度で見つけられないなら、存在意義に疑問を感じます。
10!は総当たりで調べられる数ですから。


上記の(2)を試し、問題の切り分けを行ってください。
(3)についてはその後の課題です。(交叉は更に後)


(※)
親世代より悪化することもありえる、という仕様も、ありだとは思います。
プログラム全体の難易度が若干上がるので、これも後回しがよいでしょう。

くっちゃべー

Re: 遺伝的アルゴリズムについて

#6

投稿記事 by くっちゃべー » 8年前

名前の統一。当然ですね。すみませんでした。以後気をつけます。
たいちう さんが書きました: (1)まず、交叉をやめましょう。
それ以外の部分が完成してから挑戦してください。

(2)世代ごとに最も評価が高かった個体の総距離を比較してください。
世代が進むにしたがって、総距離は減っていくはずです。
絶対に親世代より悪化することがないようにしてください。(※)
(1)に従い、交叉を完全に切り離しました。
(2)に従いましたが、質問です。このとき交叉は完全に切り離しているので
総距離が変わる。すなわち都市の通る順番が変わるためには突然変異しかありませんよね?
これだと総距離が減っていくとは言えないと思うのですが、減っていくような突然変異ってあるのでしょうか?
というよりそれは突然変異なのか?って思ってしまって質問しました。
おそらく、私の解釈がおかしいのだと思います。

たいちう
記事: 418
登録日時: 13年前

Re: 遺伝的アルゴリズムについて

#7

投稿記事 by たいちう » 8年前

> (2)に従いましたが、質問です。このとき交叉は完全に切り離しているので
> 総距離が変わる。すなわち都市の通る順番が変わるためには突然変異しかありませんよね?
> これだと総距離が減っていくとは言えないと思うのですが、減っていくような突然変異ってあるのでしょうか?
> というよりそれは突然変異なのか?って思ってしまって質問しました。
> おそらく、私の解釈がおかしいのだと思います。

都市の訪問順について、

ABCDE...

BACDE...

のように変わることを突然変異と言っています。
私が勝手に言っているのではなく、一般的な表現と思ってください。
このときに、総距離が増えるときもあれば減るときもあるでしょう。

くっちゃべー

Re: 遺伝的アルゴリズムについて

#8

投稿記事 by くっちゃべー » 8年前

たいちう さんが書きました: 都市の訪問順について、

ABCDE...

BACDE...

のように変わることを突然変異と言っています
このように変わる突然変異をしております。
確認が取れたところで以下の(3)ですが、
10都市に変えて何をすべきなのでしょうか?交叉はまだ切り離していますよね?
たいちう さんが書きました: (3)TSPは問題の性質上、必ず最適解を見つけられるわけではないですが、
都市数が10程度で見つけられないなら、存在意義に疑問を感じます。

たいちう
記事: 418
登録日時: 13年前

Re: 遺伝的アルゴリズムについて

#9

投稿記事 by たいちう » 8年前

> このように変わる突然変異をしております。
> 確認が取れたところで以下の(3)ですが、
> 10都市に変えて何をすべきなのでしょうか?交叉はまだ切り離していますよね?

交叉なしで解決してないのですよね?
それならば原因を突き止めて解決するだけですが。

何を困っているのか状況が判りません。
もう少し説明をしてもらえないと、アドバイスのしようがありません。

くっちゃべー

Re: 遺伝的アルゴリズムについて

#10

投稿記事 by くっちゃべー » 8年前

交叉なしで解決していないというより
交叉なしだとデータを変化させる要因は突然変異しかありませんよね?
でも、今は突然変異の確率は1%であり、1データの中身を(先ほどのように)入れ替えるようになっています。
とするととてつもない時間がかかりますし、何より総距離はなかなか減っていかないと思います。
それでも実行して放っていけばよいのでしょうか?
また、終了条件としてはすべてのデータで都市の回り方が同じになったらとなっていますがこれでいいですか?

たいちう
記事: 418
登録日時: 13年前

Re: 遺伝的アルゴリズムについて

#11

投稿記事 by たいちう » 8年前

> とするととてつもない時間がかかりますし、何より総距離はなかなか減っていかないと思います。
> それでも実行して放っていけばよいのでしょうか?

突然変異の発生率を上げてもよいのですが、
10都市でとてつもない時間がかかるならば、
プログラムが正しく作れていない可能性もあります。
例えば、5都市でプログラムを作ってみてはいかがですか。
あるいは3都市とか。必ず最短経路が得られますか?


> また、終了条件としてはすべてのデータで都市の回り方が同じになったらとなっていますがこれでいいですか?

これはナンセンス。遺伝子の多様性を放棄しています。
最終的な解はトップだけ取り出せばいいのです。

ただ、一般的に終了条件の決定方法は難しいものです。
ある程度の世代数が経っても最適解が更新されないようなら終了でよいでしょう。

くっちゃべー

Re: 遺伝的アルゴリズムについて

#12

投稿記事 by くっちゃべー » 8年前

3都市,5都市において交叉なしで解が収束しました。
ただ、すべてのデータで都市の回り方が同じではなく
1番良いデータにおいて解が収束しましたが、これでいいわけでよね?
次のステップとしては何をすべきでしょうか?

たいちう
記事: 418
登録日時: 13年前

Re: 遺伝的アルゴリズムについて

#13

投稿記事 by たいちう » 8年前

> 3都市,5都市において交叉なしで解が収束しました。
> ただ、すべてのデータで都市の回り方が同じではなく
> 1番良いデータにおいて解が収束しましたが、これでいいわけでよね?
> 次のステップとしては何をすべきでしょうか?

「解が収束」が何を指しているのか判りません。
机上での予想通りの最短経路が得られたということですか?
そうであれば最低限の部分はできていることになります。
そうでないならデバッグしてください。

次は都市数10です。
もし毎回乱数で都市の座標を決めているなら、
デバッグをやりやすくするために、毎回同じ座標の組を使ってください。
その10都市について、本当の最短経路を総当たりで計算してください。
総当たりの結果が遺伝的アルゴリズムで得られたら次の段階に進めます。

今どきの一般的なスペックのPCで10都市だと、
1分以上かかるようならバグがあると思っていいでしょう。

くっちゃべー

Re: 遺伝的アルゴリズムについて

#14

投稿記事 by くっちゃべー » 8年前

10都市(スタート入れると11都市)、突然変異確率10%、交叉なしで
1分間一番良いもののルートだけ表示してみましたが、最短経路を得られませんでした。

くっちゃべー

Re: 遺伝的アルゴリズムについて

#15

投稿記事 by くっちゃべー » 8年前

試しに、10都市(スタート入れると11都市)、突然変異確率10%、交叉「あり」
でテストしてみたところ、最短経路を得られました。
また、10都市(スタート入れると11都市)、突然変異確率「1%」、交叉「あり」
の場合も最短経路を得られました。
かかった時間は1分とはいきませんが、素早い時間で得られました。

しかし、目標の20都市になるととてつもなく時間がかかるようです。
(時間がかかりすぎて最短経路が得られるのか得られないのかはわからない)

これは遺伝的アルゴリズムがうまくいっていると言えるのでしょうか?

たいちう
記事: 418
登録日時: 13年前

Re: 遺伝的アルゴリズムについて

#16

投稿記事 by たいちう » 8年前

> これは遺伝的アルゴリズムがうまくいっていると言えるのでしょうか?

言えないでしょう。
前も書きましたが、交叉がなくても機能するはずです。
交叉で性能が改善されることはありますが、
交叉なしでの性能が悪すぎるという事は、交叉以外の部分にバグがあるのでしょう。
都市数が少ないときはPCのスペックでごまかせても、
都市数が増えると爆発的に探索空間が広がるので、
ごまかしが効かなくなっているのではないでしょうか。

私の予想では深刻なバグがあるので、これから先はバグを潰す作業が最優先ですが、
自分の能力以上のプログラムに取り組んでいる人には難しい作業です。
必ずしも推奨される方法ではないですが、一番簡単な方法は、
プログラムとテストデータをここに載せて、デバッグを依頼することです。
それでも解決するとは限りませんし、解決するとしても日数がかかるかもしれません。
(掲示板とはそういうものです。短時間で確実に解決してほしいなら、
有償のサービスを探してください。)

ソースコードを見せたくない場合、アドバイスが必要ならば、もっと定量的な情報がほしいです。
3都市や5都市の場合、最短経路が得られたものと認識していますが
(私は確認したいのですが、くっちゃべーさんの回答は頂けていません)、
瞬時に解決しているでしょうか?その時の時間や世代数は?
5都市で1秒以上かかるなら、やはりバグがあるものと思います。

その他の定量的な情報の例としては、3都市以降の最短経路が得られるまでの時間と世代数とかです。

くっちゃべー

Re: 遺伝的アルゴリズムについて

#17

投稿記事 by くっちゃべー » 8年前

・5都市(スタート地点を含むと6都市)
・一度に10ルート
・交叉なし
・突然変異確率1%
という条件でテストしてみると1~5分ほどかかってしまいました。
(1~5分というのは何度かテストしたからです。)
そこでいくつか疑問や気になったことがあったので質問します。

・突然変異について
 確率1%というのは突然変異という動作が起こる確率が1%だということですが、私の場合、
「10ルートのうちどれか1ルートを総距離の短い2ルートは選ばれない条件の中、ランダムで」選び、
 その選ばれた「1ルートのうち2箇所を完全にランダムで選び、その2箇所の値を交換する」ようになっており、
 ここまでを1% の確率で行うようになっています。確率として低すぎるでしょうか?
 「10ルートすべてに突然変異を行う」を1%の確率で行うべきでしょうか?
 このやり方は突然変異として正しいでしょうか?
 たいちうさんの想像している突然変異と一致している(あるいは想定内)でしょうか?
 また、全ルートで総距離が同じになっても突然変異を行わず、確率に従うようになっていますがこれも一致しているでしょうか?

・10ルートすべての総距離を世代ごとに表示していますが、
 稀に一世代前にはあった一番総距離の短い値が消えていたりします。
 例)一世代:100 150 200  二世代:130 150 200
 しかし、総距離の短い2ルートは突然変異しないようになっています。
 最短の記録消えるなどということは(上の条件で)起こりうることなのでしょうか?
 それとも私のプログラムのバグでしょうか?
 

たいちう
記事: 418
登録日時: 13年前

Re: 遺伝的アルゴリズムについて

#18

投稿記事 by たいちう » 8年前

答えやすい方から書きます。

> しかし、総距離の短い2ルートは突然変異しないようになっています。
> 最短の記録消えるなどということは(上の条件で)起こりうることなのでしょうか?
> それとも私のプログラムのバグでしょうか?

当然バグです。
デバッグしましょう。


> ここまでを1% の確率で行うようになっています

その説明ではまだ曖昧ですので、確認させてください。
以下のどれをさしているのでしょうか。

A) 平均すると、100世代に一回突然変異が起こる。
B) 平均すると、10世代に一回突然変異が起こる。(10遺伝子×10世代に一回)
C) 平均すると、12.5世代に一回突然変異が起こる。(8遺伝子×12.5世代に一回)

A)~C)までのいずれにも当てはまらないなら、どのような操作を行っているのか想像できません。
説明を補足してください。

いずれにしても、これでは殆ど新しい遺伝子は発生しません。
A)~C)までの方針ならば、各世代で4~5回程度の突然変異でもよいのではないかと思います。


Wikipediaには、『突然変異の確率は0.1%~1%、高くても数%である。』と書かれています。
くっちゃべーさんも、同様な資料を読んだのかもしれませんが、
これは1つの遺伝子座が突然変異する確率なので、
1つの遺伝子全体では突然変異する確率はもっと高く、
遺伝子が長いほど、その確率も高くなります。


ちなみに、現在のプログラムは「パス表現」と言われる表記で書かれていると想像していますが、
これを「順序表現」に変えることで、遺伝子座単位の操作が楽になります。
「順序表現」というものを理解して書き換えるのが手間ですが、交叉とも相性がよくなります。
これは必須ではないですが、本格的にやるなら、いずれ手を出すことになると思います。

cf. http://homepage3.nifty.com/ono-t/GA/GA-tspcov-j.pdf



さて、今後の方針についての提案です。

1.最短経路がなくなる不具合を修正する。
2.突然変異の確率を上げて色々試す。

まずやるべきなのは、この2つでしょう。必ず1.→2.の順番です。
その上で、次のステップを検討したらよいと思います。

3-1.交叉を実装する。
3-2.順序表現に変更する。
3-3.性能を向上させる。

くっちゃべー

Re: 遺伝的アルゴリズムについて

#19

投稿記事 by くっちゃべー » 8年前

> ここまでを1% の確率で行うようになっています

実際には「平均すると100世代に1回、1つの遺伝子に突然変異が起こる」となっております。
1%では低すぎますか?

>これを「順序表現」に変えることで、遺伝子座単位の操作が楽になります。
「順序表現」というものを理解して書き換えるのが手間ですが、交叉とも相性がよくなります。
これは必須ではないですが、本格的にやるなら、いずれ手を出すことになると思います。

つい最近まで順序表現にしていました。
ですが、このやり方だと交叉によって良いデータが継がれていくとは思えないのです。
例)5都市の場合
 ルートA:12345 順序表現A:00000
 ルートB:13425 順序表現B:01100
このように表現しているのですが間違っていますか?

これを交叉すると
例)一様交叉の場合
 一様交叉のマスクが01010の場合
 ルートCの場合:0が親A,1が親B D:0が親B,1が親Aを受け継ぐ
 ルートC:01000 ルートD:00100

パス表現に戻すと
 C:13245 D:12435
となりますが、

この場合、つながって受け継いでいるところがほぼありませんよね?
これでは交叉の意味がないと思います。
これは一様交叉であることが悪いのですか?順序表現が悪いのですか?
私の理解が悪いのですか?

たいちう
記事: 418
登録日時: 13年前

Re: 遺伝的アルゴリズムについて

#20

投稿記事 by たいちう » 8年前

大前提として、今は交叉なしの実装の話です。
順序表現の説明のため、将来実装する交叉を引き合いに出してしまった私の落ち度です。
混乱させて申し訳ありません。

> 実際には「平均すると100世代に1回、1つの遺伝子に突然変異が起こる」となっております。
> 1%では低すぎますか?

99世代の間は選択しか行わないことになります。
無駄なだけではなく、その間に遺伝子群の多様性が失われてしまいます。
ちなみに、生物学的な遺伝の知識が乏しいならば、
これを機に軽く勉強することをお勧めします。
多様性が失われることがアルゴリズム的にどういう意味を持つのか理解できると思います。


> これは一様交叉であることが悪いのですか?順序表現が悪いのですか?
> 私の理解が悪いのですか?

交叉以前の部分がちゃんと動いていないのが現在の問題です。
交叉について評価できる段階ではありませんので、
最短経路が消えてしまう不具合をまず修正してください。
順序表現だろうとパス表現だろうと(一様交叉だろうとN点交叉だろうと)、
それに比べたら大した問題ではありません。


# 老婆心ながら、、、
# 初心者は足元をおろそかにして色々試したくなるものです。
# 評価や選択の部分が完成していないのに、
# 交叉や表現を色々試してみても無駄ではないでしょうか。

くっちゃべー

Re: 遺伝的アルゴリズムについて

#21

投稿記事 by くっちゃべー » 8年前

交叉以前の部分がちゃんと動いていないのが現在の問題です。
交叉について評価できる段階ではありませんので、
最短経路が消えてしまう不具合をまず修正してください。

突然変異を行うのならば、最短経路が消えてもおかしくはないと思いますが
最短経路が消えないような突然変異をしろということでしょうか?

くっちゃべー

Re: 遺伝的アルゴリズムについて

#22

投稿記事 by くっちゃべー » 8年前

突然変異の確率としてはどのくらいが適切でしょうか?
交叉なし、あり両方教えて欲しいです。

くっちゃべー

Re: 遺伝的アルゴリズムについて

#23

投稿記事 by くっちゃべー » 8年前

やはり選択がおかしかったようです。
データを昇順に並び替える点がおかしかったようで、
修正すると最短経路が消えるということはなくなりました。

この時点での質問をいくつかさせていただきます。

・突然変異の確率はいくつが適切か。
・親となったデータには突然変異が起こらないようになっているがこの処理は適切か。
・交叉ありにすると、すぐにすべての遺伝子が同じになってしまいます。
 これは間違いなのでしょうか。一見どうみても間違いだと思いますが、
 のちのち、1つの解にたどり着き、そのときの遺伝子は皆同じなわけですよね?
 そう考えると間違いでもないのかと考えたりもするのですが・・・。
 【実際には】
 総距離:1)1000 2)1000 3)1000 ・・・10)1000
 →これがしばらく続く。
 突然変異が3に起こり、900(1000よりも小さくなった)のとき
 →総距離: 1)900 2)900 3)900 ・・・ 10)900 
 →また突然変異が起こるまでこのまま。
 ここで900が最短経路の総距離であればよいのですが・・・明らかにそうとは言えません。

たいちう
記事: 418
登録日時: 13年前

Re: 遺伝的アルゴリズムについて

#24

投稿記事 by たいちう » 8年前

> ・親となったデータには突然変異が起こらないようになっているがこの処理は適切か。

生物学の進化を考えると、一番優秀な個体がたまたま子孫を残せないことは当然あるので、
全遺伝子に突然変異が起こりうる方が「自然」です。
ですがアルゴリズム的には、折角得られた暫定的な最適解が失われてしまうのは避けたいところです。
もしかしたら2度と見つからないかもしれませんので。

処理が適切かどうかは、くっちゃべーさんがどのような処理をしているか、
文章だけでは伝わってこないので判断できません。

例えば10個体だとして、、、

1.全個体(親世代)を評価する。
2.上位2個体をコピーして子1と子2とする。
3.適当な確率で親10個体に突然変異を発生させる。
4.変異後の10個体からランダムに8個体選び、子3~子10とする。
5.世代交代して1に戻る。

以上は非常に単純な考えですが、最適解は失われないしちゃんと機能します。
くっちゃべーさんがどのような処理をしているのか、上のように説明できますか?


>  のちのち、1つの解にたどり着き、そのときの遺伝子は皆同じなわけですよね?

これが大きな間違いです。
最終的にほしいのは、優秀な遺伝子1つです。
その時、他の遺伝子がどうなっていても構わないし、
むしろ、ばらけていた方が望ましいです。

暫定1位が進化の袋小路かもしれません。
そこに収束してしまうと、それ以上の進化は望めません。

TSPの例で説明します。
数字は適当ですが、以下のような評価値だとします。

100 : ABCDE(理論的最適解)
130 : BACED(暫定一位)
150 : ABCED
160 : BACDE

現時点で得られた最適解は、BACEDの130点です。
アルゴリズムの目標はABCDEの100点を求める事ですが、
突然変異の発生率が低く、選択ばっかりしているとBACEDに収束してしまいます。

BACEDからABCDEに変異するためには、AとBを入れ替える突然変異と、
DとEを入れ替える突然変異の両方が発生しないといけません。
突然変異の発生率が低ければ、途中段階のABCEDが生まれたとしても、
数世代のうちに淘汰されてしまい、BACEDだけの集団になるでしょう。


これが現在起こっていることだと思います。
比較的成績の悪いABCEDやBACDEが生き残っているうちに、
更なる突然変異が発生しないと理論的最適解は得られません。


> ・突然変異の確率はいくつが適切か。

常に適切だと言える数値はありません。
遺伝子長にもよるし、選択がどれくらいシビア(弱者に厳しい)なのかにもよります。
選択がうまく機能し始めたのならば、色々試してみてください。

既に書きましたが、遺伝子座単位で『突然変異の確率は0.1%~1%、高くても数%である。』だそうです。
1%とすると、10都市で10遺伝子ならば、平均して1世代に1回、突然変異が発生します。

くっちゃべー

Re: 遺伝的アルゴリズムについて

#25

投稿記事 by くっちゃべー » 8年前

>くっちゃべーさんがどのような処理をしているのか、上のように説明できますか?

1.すべての個体を評価
2.評価した結果に基づき、評価の高かった順に個体をソート
3.すべての個体からルーレット方式にて2個体を親として選出。そのまま残して子1と子2とする
(4.部分写像交叉にて親2個体から8個体を生成)
5.子1と2を除いた8個体から100世代に1度10個体のうちの1個体に対して
 「ランダムの2箇所を入れ替える」という突然変異を行う
6.1へ戻る

といった具合です。

>数世代のうちに淘汰されてしまい、BACEDだけの集団になるでしょう。
これが現在起こっていることだと思います。
比較的成績の悪いABCEDやBACDEが生き残っているうちに、
更なる突然変異が発生しないと理論的最適解は得られません。

まさにその通りでしたので、突然変異の行う確率を大幅に変更しました。
先ほどまでは上記の通り、「8個体から100世代に1度10個体のうちの1個体に対して」でしたが
「8個体から2世代に1度10個体のうちの1個体に対して」と変更しました。
すると、同じ個体の集団となって解が発見できないという問題が大幅に改善されました。
10都市の場合ですと、交叉なしでありながら1分ほどで発見できました。
なので改めると、以下のようになります。

1.すべての個体を評価
2.評価した結果に基づき、評価の高かった順に個体をソート
3.すべての個体からルーレット方式にて2個体を親として選出。そのまま残して子1と子2とする
(4.部分写像交叉にて親2個体から8個体を生成)
5.子1と2を除いた8個体から2世代に1度10個体のうちの1個体に対して
 「ランダムの2箇所を入れ替える」という突然変異を行う
6.1へ戻る

ただ、突然変異のタイミングが気になります。
その点について指摘お願いします。また、その他の気になる点についてご指摘ください。

くっちゃべー

Re: 遺伝的アルゴリズムについて

#26

投稿記事 by くっちゃべー » 8年前

1分は言いすぎました。偶然だったようです。
1分から〜10分ほど。バラバラです。
中には途中で実行を停止するぐらい長いものもありました。

ただ、試しにと思って5都市でやってみると1秒かかりませんでした。

たいちう
記事: 418
登録日時: 13年前

Re: 遺伝的アルゴリズムについて

#27

投稿記事 by たいちう » 8年前

> ただ、突然変異のタイミングが気になります。
> その点について指摘お願いします。また、その他の気になる点についてご指摘ください。

何が気になるのか具体的に書いてください。
指摘のしようがありません。


その他については、現在の成績が気になります。
例えば5分かかって、理論的最適解に到達できていないとしても、
その時の距離が、理論的最適解と比較して数%長いだけなのか、
数倍もかかるのかでは、状況が全く違います。


> 1.すべての個体を評価
> 2.評価した結果に基づき、評価の高かった順に個体をソート
> 3.すべての個体からルーレット方式にて2個体を親として選出。そのまま残して子1と子2とする
> (4.部分写像交叉にて親2個体から8個体を生成)
> 5.子1と2を除いた8個体から2世代に1度10個体のうちの1個体に対して
>  「ランダムの2箇所を入れ替える」という突然変異を行う
> 6.1へ戻る

この手順の説明も、曖昧な部分が残っていると思いますが、
特に目立った問題点はありません。
手順通りにプログラムが作れているかは私には判りませんし、
そろそろソースコードを見ないと、性能についてのアドバイスは難しそうです。


ちなみに、以前のバージョンで交叉ありの方が成績が良かったようですが、
何故そうだったのか、今の知見で考察してみてはどうでしょうか。

くっちゃべー

Re: 遺伝的アルゴリズムについて

#28

投稿記事 by くっちゃべー » 8年前

>手順通りにプログラムが作れているかは私には判りませんし、
そろそろソースコードを見ないと、性能についてのアドバイスは難しそうです。

自分がきちんと説明できているか不安になってきました。
また、説明通りにコードが書けているとは思えなくなってきました。
なのでソースコードを載せます。

【変数・関数の説明】
・VolumeRoute 遺伝子の数 
・VolumeData 都市数
・VolumeElite 親の数
・Updateはフレーム毎で実行
・Random.Range(A,B) A〜(B-1)の値を返す
そのほかにも不明な点がありましたら質問ください。

なお、明確な終了時は決めていません。(50000世代を越えると終了するようにはなっていますが)
また、setTotalDistanceとshowRouteの中身についてはライブラリ?の関数を大量に使っていましたので
コメント通り問題なく処理できているものだとしてください。

問題ばかりだとは思いますが、ご指摘よろしくお願いします。

コード:

public class RouteSCR : MonoBehaviour
{
    public int VolumeRoute = 10, VolumeData = 10, VolumeElite = 2, LoopCount = 0;
    public float Interval = 0.2f;
    public bool IsNext = false;
    //総距離
    public float[] TotalDistance = new float[10];
    //パス(ルート)データ
    private int[,] Route = new int[10, 20];
    //エリートデータ
    private int[,] EliteRoute = new int[2, 20];
    //ルーレットデータ
    private int[] Rate = new int[5]{ 80, 50, 30, 10, 5 };
    private float time = 0.0f;
   
    void Update()//毎フレーム行う処理
    {
        time += Time.deltaTime;
        if (IsNext && time > Interval && LoopCount < 50000)//50000を超えたら強制終了
        {
            LoopCount++;
            IsNext = false;
            time = 0.0f;
            SecondgGeneration();
        }
    }

    //第一世代
    void buildFirstRoute()//一番最初に実行されるようになっている
    {
        for (int i = 0; i < VolumeRoute; i++)
        {
            for (int j = 0; j < VolumeData; j++)
            {
                Route[i, j] = j + 1;
            }
            for (int k = 0; k < Random.Range(VolumeData / 2, VolumeData); k++)
            {
                int num = Random.Range(0, VolumeData);
                int temp = Route[i, num];
                Route[i, num] = Route[i, 0];
                Route[i, 0] = temp;
            }
        }
        showRoute();
    }

    //第二世代以降
    void SecondgGeneration()
    {
        showRoute();
    }

    //ルート表示
    void showRoute()
    {
       //ルートを画面に表示する処理
        Selection();
    }

    //ルートごとに総距離を計算
    void setTotalDistance()
    {
        //Route変数から
        //総距離を計算してTotalDistanceに格納する処理
    }

    void Sort(){
        //Route配列をソート
        for (int i = 0; i < VolumeRoute; i++)
        {
            int index = i;
            for (int j = i + 1; j < VolumeRoute; j++)
            {
                if (TotalDistance[j] < TotalDistance[index])
                {
                    index = j;
                }
            }

            float DistanceTemp = TotalDistance[i];
            TotalDistance[i] = TotalDistance[index];
            TotalDistance[index] = DistanceTemp;

            if (index != i)
            {
                for (int k = 0; k < VolumeData; k++)
                {
                    int temp = Route[i, k];
                    Route[i, k] = Route[index, k];
                    Route[index, k] = temp;
                }
            }
        }
    }

    //エリート選択
    void Selection()
    {

        setTotalDistance();
        Sort();

        //選択(ルーレット方式)
        bool IsDecide = true;
        int[] num = new int[VolumeElite];
        for (int i = 0; i < VolumeElite; i++)
        {
            do
            {
                IsDecide = true;
                num[i] = roulette();
                for (int k = 0; k < i; k++)
                {
                    if (i != k && (num[i] == num[k]))
                    {
                        IsDecide = false;
                    }
                }
            } while (IsDecide == false);
            if (IsDecide)
            {
                for (int j = 0; j < VolumeData; j++)
                {
                    EliteRoute[i, j] = Route[num[i], j];
                }
            }
        }
        //Crossover();
        mutation();
    }

    int roulette()
    {
        int max = 0;
        for (int i = 0; i < Rate.Length; i++)
        {
            max += Rate[i];
        }
        int temp = Random.Range(0, max);
        for (int j = 0; j < Rate.Length; j++)
        {
            temp -= Rate[j];
            if (temp <= 0)
            {
                return j;
            }
        }
        Debug.LogError("Error/roulette");
        return -1;
    }

    void Crossover()
    {
        int[,] path = new int[VolumeRoute - VolumeElite, VolumeData];
        for (int i = VolumeElite; i < VolumeRoute; i += 2)
        {
            int index = 0, num = 0;
            //切断2点を選ぶ
            int formerPos = Random.Range(0, VolumeData / 2);
            int latterPos = Random.Range(formerPos + 2, VolumeData);

            for (int j = 0; j < VolumeData; j++)
            {
                Route[i, j] = 0;
                Route[i + 1, j] = 0;
            }

            //2点間をそのままコピー
            for (int j = formerPos; j < latterPos; j++)
            {
                Route[i, j] = EliteRoute[0, j];
                Route[i + 1, j] = EliteRoute[1, j];
            }
           
            int m = i - VolumeElite;
            //もう一方の親を右回りでpathにコピー
            index = latterPos;
            num = 0;
            do
            {
                path[m, num] = EliteRoute[1, index];
                path[m + 1, num] = EliteRoute[0, index];
                index++;
                num++;
                if (index >= VolumeData)
                {
                    index = 0;
                }
            } while(num < VolumeData);
           
            //重複を調べる
            for (int k = formerPos; k < latterPos; k++)
            {
                for (int l = 0; l < VolumeData; l++)
                {
                    if (Route[i, k] == path[m, l])
                    {
                        path = LeftJustification(path, m, l);
                    }
                    if (Route[i + 1, k] == path[m + 1, l])
                    {
                        path = LeftJustification(path, m + 1, l);
                    }
                }
            }
           
            //もう一方の親(重複を除外したpath)をlatterPosから挿入
            index = latterPos;
            num = 0;
            do
            {
                Route[i, index] = path[m, num];
                Route[i + 1, index] = path[m + 1, num];
                index++;
                num++;
                if (index >= VolumeData)
                {
                    index = 0;
                }
            } while(num <= VolumeData - (latterPos - formerPos + 1));
           
        }
        setTotalDistance();
        Sort();
        mutation();
    }

    int[,] LeftJustification(int[,] path_c, int num, int index)
    {
        for (int i = index; i < VolumeData - 1; i++)
        {
            path_c[num, i] = path_c[num, i + 1];
        }
        return path_c;
    }
        
    //突然変異
    void mutation()
    {
        if (Random.Range(0,100) % 2 == 0)//2世代に一度突然変異
        {
            int num = Random.Range(VolumeElite, VolumeRoute);//優秀なデータは変異しない
            //入れ替える2点を選ぶ
            int pos1 = Random.Range(0, VolumeData), pos2 = 0;
            do
            {
                pos2 = Random.Range(0, VolumeData);
            } while (pos1 == pos2);
            //実際に入れ替える
            int temp = Route[num, pos1];
            Route[num, pos1] = Route[num, pos2];
            Route[num, pos2] = temp;
        }
        IsNext = true;
    }
}  

たいちう
記事: 418
登録日時: 13年前

Re: 遺伝的アルゴリズムについて

#29

投稿記事 by たいちう » 8年前

> 自分がきちんと説明できているか不安になってきました。
> また、説明通りにコードが書けているとは思えなくなってきました。
> なのでソースコードを載せます。

不十分です。
これらの関数をどのように呼び出しているかが欠けています。


> また、setTotalDistanceとshowRouteの中身についてはライブラリ?の関数を大量に使っていましたので
> コメント通り問題なく処理できているものだとしてください。

ごちゃごちゃしている部分程、バグがあるものです。
この辺りも省略せずに、動かせるソースを載せてください。
必要ならばデータも。

くっちゃべー

Re: 遺伝的アルゴリズムについて

#30

投稿記事 by くっちゃべー » 8年前

>ごちゃごちゃしている部分程、バグがあるものです。
この辺りも省略せずに、動かせるソースを載せてください。
必要ならばデータも。

動かすためにゲームエンジンUnityを使用しますが、
いかがいたしましょう?


setTotalDistanceとshowRouteの中身についても
Unityの機能を大量に使っています。

くっちゃべー

Re: 遺伝的アルゴリズムについて

#31

投稿記事 by くっちゃべー » 8年前

今更ながら質問です(以前質問したかもしれませんが)

交叉なし・10都市なら1分ほどと言いますが、なぜそう言い切れるのかわかりません。
「突然変異しか遺伝子の中身を変化させることはできず、
突然変異ではどれを変化させるかはランダムになっている」
これだと何分かかるかはそのときの運によりませんか?
1分終わるときもあれば数分、数十分もしかすると数時間かかってもおかしくないと思うのですが・・・
1世代に1度でも確率として少なすぎるのでしょうか?

成績の悪いものに突然変異を起こすことが大切だと言いますが
成績の悪いものが残らないようにするのが交叉ではないのでしょうか?

たいちう
記事: 418
登録日時: 13年前

Re: 遺伝的アルゴリズムについて

#32

投稿記事 by たいちう » 8年前

> 動かすためにゲームエンジンUnityを使用しますが、
> いかがいたしましょう?

そのためにC#になったのですね。


> setTotalDistanceとshowRouteの中身についても
> Unityの機能を大量に使っています。

showRouteはともかく、setTotalDistanceにはこのライブラリの機能は不要と思いますが。
遺伝的アルゴリズムの部分と、その結果を表示する部分がうまく分かれていないのでしょうか。


ゲームエンジンUnityは、私は触ったことはありません。
特に興味もなく、今後も触る予定はありません。

No.28について言えることは、メソッド名と実際の処理が一致していないことです。
showRoute()の中でSelection()を呼んでいたり、
Selection()の中でmutation()を呼んでいたりするのが問題です。
プログラムの見通しが悪くなり、バグの元でしょう。
例えば、Update()からこれらのメソッドを呼び出すようにするのが、よいと思います。

まあ、上の指摘は直接性能に関係するところではありませんが、
可読性を高めることによって、間違いに気づきやすくなったり、
デバッグしやすくなったり、色々試しやすくなるものです。
最初に書いた、遺伝的アルゴリズムと、表示の切り分けと同様に、
修正することをお勧めします。


肝心の処理の方は、No.28のソースを元にして、動かせるようにしてみます。
あまり期待せずにお待ちください。

くっちゃべー

Re: 遺伝的アルゴリズムについて

#33

投稿記事 by くっちゃべー » 8年前

>肝心の処理の方は、No.28のソースを元にして、動かせるようにしてみます。
あまり期待せずにお待ちください。

ご迷惑をおかして本当に申し訳ありません。
でも、なんとか十分な性能(20都市も1分くらい)のものを作りたいんです。
お願いします。

ここからは報告です。
さきほど以下のように書き換えました。すると10都市もほぼ1分かからずでした。
しかし、20都市のほうはまだまだでした。ただ、これだと交叉なしにはならないです。

1.すべての個体を評価
2.評価した結果に基づき、評価の高かった順に個体をソート
3.すべての個体からルーレット方式にて2個体を親として選出。そのまま残して子1と子2とする
4.子1と2を除いた8個体に対して
 以下のどちらかを2個体ずつ行う(8個体なので4回行う)
 ・部分写像交叉にて親2個体から2個体を生成
 ・現世代のものに「ランダムの2箇所を入れ替える」という突然変異を行い、2個体を生成
5.1へ戻る

たいちう
記事: 418
登録日時: 13年前

Re: 遺伝的アルゴリズムについて

#34

投稿記事 by たいちう » 8年前

> 交叉なし・10都市なら1分ほどと言いますが、なぜそう言い切れるのかわかりません。
> 「突然変異しか遺伝子の中身を変化させることはできず、
> 突然変異ではどれを変化させるかはランダムになっている」
> これだと何分かかるかはそのときの運によりませんか?
> 1分終わるときもあれば数分、数十分もしかすると数時間かかってもおかしくないと思うのですが・・・
> 1世代に1度でも確率として少なすぎるのでしょうか?

遺伝的アルゴリズムに明確な終わりはありません。
準最適解を得るためのアルゴリズムなので、
時間をかけても最適解が得られる保証はありません。

都市数が増えると爆発的に探索空間が広がるので、
10都市程度で最適解を得られないなら、
20都市では役に立たないだろうという私の経験によるものです。
以下の質問にも答えてもらっていません。

> その他については、現在の成績が気になります。
> 例えば5分かかって、理論的最適解に到達できていないとしても、
> その時の距離が、理論的最適解と比較して数%長いだけなのか、
> 数倍もかかるのかでは、状況が全く違います。


これもスルーされています。

> ちなみに、以前のバージョンで交叉ありの方が成績が良かったようですが、
> 何故そうだったのか、今の知見で考察してみてはどうでしょうか。


> 成績の悪いものに突然変異を起こすことが大切だと言いますが
> 成績の悪いものが残らないようにするのが交叉ではないのでしょうか?

くっちゃべーさんは「交叉」という操作の意味をまだ理解していないと思います。
思いつくまま質問をするのではなく、このスレ全体をじっくり読み返し、
自分のプログラムがどうなっているのか、どうあるべきなのか、考察してみてほしいです。

くっちゃべー

Re: 遺伝的アルゴリズムについて

#35

投稿記事 by くっちゃべー » 8年前

>10都市程度で最適解を得られないなら、
20都市では役に立たないだろうという私の経験によるものです。

10都市ほどならすぐに得られるようになりました。1つ前のプログラムからの変更点のみ載せます。

コード:

void Crossover()
    {
        int[,] path = new int[VolumeRoute - VolumeElite, VolumeData];
        for (int i = VolumeElite; i < VolumeRoute; i += 2)
        {
            switch (Random.Range(0, 2))
            {
                case 0:
                    int index = 0, num = 0;
                    //切断2点を選ぶ
                    int formerPos = Random.Range(1, VolumeData / 2);//最初と最後は除く
                    int latterPos = Random.Range(formerPos + 2, VolumeData);

                    for (int j = 0; j < VolumeData; j++)
                    {
                        Route[i, j] = 0;
                        Route[i + 1, j] = 0;
                    }

                    //2点間をそのままコピー
                    for (int j = formerPos; j < latterPos; j++)
                    {
                        Route[i, j] = EliteRoute[0, j];
                        Route[i + 1, j] = EliteRoute[1, j];
                    }
                    
                    int m = i - VolumeElite;
                    //もう一方の親を右回りでpathにコピー
                    index = latterPos;
                    num = 0;
                    do
                    {
                        path[m, num] = EliteRoute[1, index];
                        path[m + 1, num] = EliteRoute[0, index];
                        index++;
                        num++;
                        if (index >= VolumeData)
                        {
                            index = 0;
                        }
                    } while(num < VolumeData);
                   
                    //重複を調べる
                    for (int k = formerPos; k < latterPos; k++)
                    {
                        for (int l = 0; l < VolumeData; l++)
                        {
                            if (Route[i, k] == path[m, l])
                            {
                                path = LeftJustification(path, m, l);
                            }
                            if (Route[i + 1, k] == path[m + 1, l])
                            {
                                path = LeftJustification(path, m + 1, l);
                            }
                        }
                    }
                    //もう一方の親(重複を除外したpath)をlatterPosから挿入
                    index = latterPos;
                    num = 0;
                    do
                    {
                        Route[i, index] = path[m, num];
                        Route[i + 1, index] = path[m + 1, num];
                        index++;
                        num++;
                        if (index >= VolumeData)
                        {
                            index = 0;
                        }
                    } while(num <= VolumeData - (latterPos - formerPos + 1));
                    break;
                case 1://高確率すぎますか?
                    Mutation(i);
                    Mutation(i + 1);
                    break;
                //case 2やcase 3として交叉や突然変異を増やすべきでしょうか?
                default:
                    Debug.LogError("RouteSCR/Crossover");
                    break;
            }
        }
        IsNext = true;//ここでtrueにしておく
        //mutation();呼ばない
    }

    void Mutation(int num)
    {
        //入れ替える2点を選ぶ
        int pos1 = Random.Range(0, VolumeData), pos2 = 0;
        do
        {
            pos2 = Random.Range(0, VolumeData);
        } while (pos1 == pos2);
        //実際に入れ替える
        int temp = Route[num, pos1];
        Route[num, pos1] = Route[num, pos2];
        Route[num, pos2] = temp;
        //checkGeneration();
    }
>> その他については、現在の成績が気になります。
> 例えば5分かかって、理論的最適解に到達できていないとしても、
> その時の距離が、理論的最適解と比較して数%長いだけなのか、
> 数倍もかかるのかでは、状況が全く違います。

10都市は問題なく到達でき、20都市の場合ぱっと見うまくいっていますが、
スタート地点から結ぶ最初の点の位置がおかしかったりと惜しいです。
距離に関しても最初の点がうまくいっていないために長くなっています。

>> ちなみに、以前のバージョンで交叉ありの方が成績が良かったようですが、
> 何故そうだったのか、今の知見で考察してみてはどうでしょうか。

何と言っても突然変異の確率を大幅に改善したからだと思います。
そしてそのときのバージョンよりも突然変異しやすく、また突然変異するタイミングを
交叉後から交叉の代わりに行うように変えたため現在のほうが好成績を残せています。

>くっちゃべーさんは「交叉」という操作の意味をまだ理解していないと思います。
思いつくまま質問をするのではなく、このスレ全体をじっくり読み返し、
自分のプログラムがどうなっているのか、どうあるべきなのか、考察してみてほしいです。

思いつくままの質問していたと思います。すみませんでした。
現在のプログラムも基礎的な部分はうまく働いていると言えるのではないかと思います。
一番良い記録が失われることや通らない都市がでてくる問題もなくなりました。
何より10都市が1分かからず解くことができ嬉しく思っております。

20都市もおそらく時間さえかければ解けると思いますが、
それでは遺伝的アルゴリズムの意味がありませんので、20都市も1分ほどで解けるようにしたいです。
上のコード、さきほどのコード(全体のプログラム)を元に
なにが問題なのかあるいはなにを追加すべき教えて欲しいです。

たいちう
記事: 418
登録日時: 13年前

Re: 遺伝的アルゴリズムについて

#36

投稿記事 by たいちう » 8年前

> 20都市もおそらく時間さえかければ解けると思いますが、
> それでは遺伝的アルゴリズムの意味がありませんので、20都市も1分ほどで解けるようにしたいです。
> 上のコード、さきほどのコード(全体のプログラム)を元に
> なにが問題なのかあるいはなにを追加すべき教えて欲しいです。

「解ける」とはどういうことを指していますか?
既に次のように書いています。何か誤解していませんか?

> 遺伝的アルゴリズムに明確な終わりはありません。
> 準最適解を得るためのアルゴリズムなので、
> 時間をかけても最適解が得られる保証はありません。



> >> ちなみに、以前のバージョンで交叉ありの方が成績が良かったようですが、
> > 何故そうだったのか、今の知見で考察してみてはどうでしょうか。
>
> 何と言っても突然変異の確率を大幅に改善したからだと思います。
> そしてそのときのバージョンよりも突然変異しやすく、また突然変異するタイミングを
> 交叉後から交叉の代わりに行うように変えたため現在のほうが好成績を残せています。

質問と答えが噛み合っていませんね。

そもそも「交叉」とはどのような操作ですか?
この操作を行う目的は何ですか?
その目的は達成できていますか?
できていることをどのように検証できますか?

くっちゃべー

Re: 遺伝的アルゴリズムについて

#37

投稿記事 by くっちゃべー » 8年前

>「解ける」とはどういうことを指していますか?
既に次のように書いています。何か誤解していませんか?

解けるという言葉は間違いでした。
私の言いたかったことは最短経路が得られるということです。

>そもそも「交叉」とはどのような操作ですか?

親2個体のデータを利用して子を生成する操作だと考えています。

>この操作を行う目的は何ですか?

最短経路を得るためにかかる時間・世代数を減らすこと考えています。

>その目的は達成できていますか?

以前よりも達成できていると思いますが、まだ不十分です。

>できていることをどのように検証できますか?

実際に実行してみて、最短経路を得られるのにかかる時間・世代数を
比べることで検証できると考えています。

たいちう
記事: 418
登録日時: 13年前

Re: 遺伝的アルゴリズムについて

#38

投稿記事 by たいちう » 8年前

やはり根本的に誤解しています。
遺伝的アルゴリズムで最短経路が得られる保証はありません。

私が書いた「理論的最適解」と「準最適解」という言葉について考えてみてください。

くっちゃべー

Re: 遺伝的アルゴリズムについて

#39

投稿記事 by くっちゃべー » 8年前

>「理論的最適解」

2点の距離の総和が一番短いものを指すのはないでしょうか。

>「準最適解」

正直、よくわかりません。
一定の時間における理論的最適解ということでしょうか。

たいちう
記事: 418
登録日時: 13年前

Re: 遺伝的アルゴリズムについて

#40

投稿記事 by たいちう » 8年前

やはり、自分が何をしているのか、よく判っていなかったのですね。

くっちゃべーさんの取り組んでいる問題、「巡回セールスマン問題」は、
「NP困難」と言われる難しさの問題です。

都市数が5の場合、あり得る経路の数は5!=120通りしかなく、
120通りを全て試して最短経路を見つけるプログラムは簡単に作れるでしょう。

都市数が10の場合でも、経路の数は10!=3628800通りであり、
都市数5と同じ総当たりのプログラムで最短経路を見つけることができます。
今どきのPCなら、殆ど瞬時に見つけられるでしょう。

都市数が20になると、経路の数は20!=2432902008176640000通りであり、
PCでは総当たりを試すことは不可能になります。
スーパーコンピューターやクラウドコンピューティングなら可能かもしれませんが、
都市数が100になったらどうなるでしょうか。

このように、問題のサイズが小さい場合は簡単に解けるけど、
サイズが大きくなっただけで計算量的に不可能になってしまうのが、
「NP困難」な問題の特徴です。


「遺伝的アルゴリズム」は、「NP困難」な問題を解けるわけではありません。
現実的な時間内に、そこそこの解を求めるアルゴリズムです。

くっちゃべーさんのゴールはどこでしょうか。


巡回セールスマン問題
https://ja.wikipedia.org/wiki/%E5%B7%A1 ... F%E9%A1%8C

NP困難
https://ja.wikipedia.org/wiki/NP%E5%9B%B0%E9%9B%A3

遺伝的アルゴリズム
https://ja.wikipedia.org/wiki/%E9%81%BA ... A%E3%83%A0

くっちゃべー

Re: 遺伝的アルゴリズムについて

#41

投稿記事 by くっちゃべー » 8年前

自分の勉強不足や伝える力が少ないことをこのスレで大変実感しました。
以後気をつけて質問したいです。

>「遺伝的アルゴリズム」は、「NP困難」な問題を解けるわけではありません。
現実的な時間内に、そこそこの解を求めるアルゴリズムです。
くっちゃべーさんのゴールはどこでしょうか。

5都市は1秒かからず、10都市ならば30秒〜1分ほどでそこそこの解を求めることができました。
私のゴールとしては20都市をそこそこの時間でそこそこの解が得られるようにすることとしています。
そこそこの時間としては正直、一般的に(遺伝的アルゴリズムを使って)どれほどかかるのかがわからないのですが、
3分〜5分ほどでしょうか?早すぎるでしょうか?逆に遅すぎますか?

たいちう
記事: 418
登録日時: 13年前

Re: 遺伝的アルゴリズムについて

#42

投稿記事 by たいちう » 8年前

仮に、くっちゃべーさんの作ったプログラムを私が作ったら、倍の速さで動くとします。
あるいは、くっちゃべーさんがPCを買い替えたら、
同じプログラムが5倍の速さで動くようになるかもしれません。
「一般的に何分か?」という質問に意味がないことが判るでしょう。


では、どうしたらいいでしょうか。

既にプログラムが完成しているとします。
1分後、3分後、5分後、10分後、30分後、、、などの成績を見てください。
何回も試して、傾向や平均を調べてください。

もし100回試した結果、5分後と比較して10分後の成績がよくなるケースが10回だった場合、
5分の時点で打ち切るべきでしょうか?
100回中1回でも成績が良くなっていたなら、10分までは続けるべきでしょうか?
これは誰が決めるべきですか?

くっちゃべー

Re: 遺伝的アルゴリズムについて

#43

投稿記事 by くっちゃべー » 8年前

>「一般的に何分か?」という質問に意味がないことが判るでしょう。
>もし100回試した結果、5分後と比較して10分後の成績がよくなるケースが10回だった場合、
5分の時点で打ち切るべきでしょうか?
100回中1回でも成績が良くなっていたなら、10分までは続けるべきでしょうか?
これは誰が決めるべきですか?


プログラムを書いている私が決めることだと思います。
ですが、20都市で5万世代たっても最短経路が得られません。
正直に言って、10、20回やってみても1度も得られていません。
さすがに、時間がかかりすぎだと思います。
交叉のやり方を変更すべきでしょうか?(現在は部分写像交叉)
変更ではなく、追加すべきでしょうか?2箇所を入れ替える以外の突然変異を追加すべきでしょうか?

たいちう
記事: 418
登録日時: 13年前

Re: 遺伝的アルゴリズムについて

#44

投稿記事 by たいちう » 8年前

最短経路を求められるアルゴリズムではないと書きましたが。
何がご不満なのですか?

ちなみに最短経路を得られていないことは、どのように確認しているのですか?

くっちゃべー

Re: 遺伝的アルゴリズムについて

#45

投稿記事 by くっちゃべー » 8年前

>ちなみに最短経路を得られていないことは、どのように確認しているのですか?

見た目です。怪しいものはのぞいたとしても、明らかに無駄な通り方をしているものが多いです。

>最短経路を求められるアルゴリズムではないと書きましたが。
何がご不満なのですか?

(1番優秀なデータとして)無駄な通り方をしていないものになるまでにかかる時間を減らしたいのです。
もちろん、PCの性能など多くの条件があってどこまで減らせるかわかりません。
ただ、1時間かけても無駄な通り方をしているものばかりです。
かかる時間を減らす方法を教えて欲しいのです。

たいちう
記事: 418
登録日時: 13年前

Re: 遺伝的アルゴリズムについて

#46

投稿記事 by たいちう » 8年前

> 見た目です。怪しいものはのぞいたとしても、明らかに無駄な通り方をしているものが多いです。

どのように「明らか」なのか、具体的に説明できますか?
日本語で正確に説明できるなら、コーディングにすることも難しくないかもしれません。
日本語で説明できないなら、コーディングなんて不可能です。
コーディングできるなら、終了条件に使えますね。


交叉についてですが、TSPには有効でない操作だと私は考えています。
TSPの性質上役に立つはずがないと考えていますし、
実際プログラムに取り入れても改良されませんでした。

この点については、くっちゃべーさんは今回逆の結論を持っているかもしれませんが、
失礼ながら、杜撰な検証と理解による、誤った結論だと私は思います。


改良の案としては、「反転」という操作はどうでしょうか。
1本の遺伝子からランダムに2点を選び、2点に挟まれた部分を逆転させます。
以下のような操作です。

ABCDEFG → AB CDE FG → AB EDC FG → ABEDCFG


パス表現ならば簡単に実装できるし、交叉より、よほどお勧めです。

くっちゃべー

Re: 遺伝的アルゴリズムについて

#47

投稿記事 by くっちゃべー » 8年前

>改良の案としては、「反転」という操作はどうでしょうか。
1本の遺伝子からランダムに2点を選び、2点に挟まれた部分を逆転させます。

実際に「反転」を実装してみました。
すると、目に見てわかるくらい変化がありました。
自分の納得のいくレベルに辿り着けたと思っております。
このスレを解決に持って行けるレベルです。正直になんの不満もないレベルです。

ただ、このまま終わりにしたくない理由が1つあります。
それはなぜこの「反転」を実装することでここまで変化したのかということです。
自分で考えろと言われてしまえばそれまでですし、それでも構いません。
ただ、教えていただけるようでしたら教えていただきたいです。

たいちう
記事: 418
登録日時: 13年前

Re: 遺伝的アルゴリズムについて

#48

投稿記事 by たいちう » 8年前

改善されたとのことで何よりです。

何故、反転が有効なのか全くわからないのならば、
問題の性質やアルゴリズムの特徴を全く理解していないのだと思います。
交叉が何故役に立たない(と私が思っている)のかも、判らないのでしょう。

質問掲示板なので質問は歓迎なのですが、自分で考えることを放棄していませんか?
プログラムが完成したのならば、当然ある程度は考えているとは思いますが、
次は自分が何を作ったのか、考えてみてください。

出し惜しみしたいわけではないですが、回答は数日待ってください。
私としては自明なことなので、どのように説明したら判りやすいか、
(酔って帰った今は)思いつきません。

たいちう
記事: 418
登録日時: 13年前

Re: 遺伝的アルゴリズムについて

#49

投稿記事 by たいちう » 8年前

忙しく日が経ってしまい、読んでもらえないかもしれませんし、
読んでもらえたとしても、くっちゃべーさんにどれほど理解していただけるか判りませんが、
やり残した気がするので一応書きます。


遺伝的アルゴリズムでよくある失敗は、そこそこ成績の良い解に収束してしまい、
最適解を見つけられない事です。
この種のアルゴリズムの宿命のようなもので、決定的な解決方法を私は知りませんし、
多分存在しないと思います。

そこそこ成績の良い解を少々変更しても、成績が下がるだけで、すぐに淘汰されてしまいます。
普通の突然変異がうまく重なって、元の解よりも成績の良い解が得られる確率は非常に小さいでしょう。

TSPを日本の都道府県の県庁所在地巡りで説明すると、
そこそこ成績の良い解は、局所的には最適化されています。
突然変異の操作は、局所最適化されている、東京→神奈川→静岡→...という経路に対して、
手当たり次第に、東京→青森→静岡→...と試しているようなものです。

反転の操作は、...→近畿→四国→山陽山陰→九州というルートを、
...→近畿→山陽山陰→四国→九州のように変更するようなイメージです。
四国→山陽山陰の部分は局所的に最適化されていた場合、
反転によって、この最適化は損なわれません。
同様に、(...→近畿)の部分と九州についても、局所最適化は損なわれません。

局所的に最適化されたルートに対して、局所最適化をできるだけ壊さず、
全体的な最適化に繋がりうる程度に大きな変更を行えるのが反転という操作です。
このような操作が可能なので、NP困難な問題の中ではTSPは比較的簡単とも言えるでしょう。

閉鎖

“C言語何でも質問掲示板” へ戻る