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

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

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

#1

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

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

ひっすー

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

#2

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

選択はそのまま上位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
登録日時: 9年前

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

#3

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

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

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

くっちゃべー

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

#4

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

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

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

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

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

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

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

#5

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

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


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

うまくいっていない

交叉を変更

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

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


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

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

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

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


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


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

くっちゃべー

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

#6

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

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

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

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

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

#7

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

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

都市の訪問順について、

ABCDE...

BACDE...

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

くっちゃべー

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

#8

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

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

ABCDE...

BACDE...

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

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

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

#9

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

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

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

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

くっちゃべー

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

#10

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

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

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

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

#11

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

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

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


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

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

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

くっちゃべー

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

#12

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

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

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

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

#13

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

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

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

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

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

くっちゃべー

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

#14

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

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

くっちゃべー

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

#15

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

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

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

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

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

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

#16

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

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

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

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

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

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

くっちゃべー

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

#17

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

・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
登録日時: 9年前

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

#18

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

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

> しかし、総距離の短い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 くっちゃべー » 3年前

> ここまでを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
登録日時: 9年前

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

#20

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

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

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

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


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

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


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

くっちゃべー

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

#21

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

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

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

くっちゃべー

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

#22

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

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

くっちゃべー

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

#23

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

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

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

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

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

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

#24

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

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

生物学の進化を考えると、一番優秀な個体がたまたま子孫を残せないことは当然あるので、
全遺伝子に突然変異が起こりうる方が「自然」です。
ですがアルゴリズム的には、折角得られた暫定的な最適解が失われてしまうのは避けたいところです。
もしかしたら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 くっちゃべー » 3年前

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

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 くっちゃべー » 3年前

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

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

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

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

#27

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

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

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


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


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

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


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

くっちゃべー

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

#28

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

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

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

【変数・関数の説明】
・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
登録日時: 9年前

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

#29

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

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

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


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

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

くっちゃべー

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

#30

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

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

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


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

閉鎖

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