(1)まず、交叉をやめましょう。それ以外の部分が完成してから挑戦してください。(2)世代ごとに最も評価が高かった個体の総距離を比較してください。世代が進むにしたがって、総距離は減っていくはずです。絶対に親世代より悪化することがないようにしてください。(※)(1)に従い、交叉を完全に切り離しました。(2)に従いましたが、質問です。このとき交叉は完全に切り離しているので総距離が変わる。都市の通る順番が変わるためには突然変異しかありませんよね?これだと総距離が減っていくとは言えないと思うのですが、減っていくような突然変異ってあるのでしょうか?というよりそれは突然変異なのか?って思ってしまって質問しました。私の解釈がおかしいのだと思います。(2)に従いましたが、質問です。いうよりそれは突然変異なのか?って思ってしまって質問しました。私の解釈がおかしいのだと思います。都市の訪問順について、ABCDE...↓BACDE...のように変わることを突然変異と言っています。私が勝手に言っているのではなく、一般的な表現と思ってください。このときに、総距離が増えるときもあれば減るときもあるでしょう。都市の訪問順について、ABCDE...↓BACDE...のように変わることを突然変異と言っていますこのように変わる突然変異をしております。都市数が10程度で見つけられないなら、存在意義に疑問を感じます。このように変わる突然変異をしております。10都市に変えて何をすべきなのでしょうか?交叉はまだ切り離していますよね?交叉なしで解決してないのですよね?それならば原因を突き止めて解決するだけですが。何を困っているのか状況が判りません。説明をしてもらえないと、アドバイスのしようがありません。交叉なしで解決していないというより交叉なしだとデータを変化させる要因は突然変異しかありませんよね?でも、今は突然変異の確率は1%であり、1データの中身を(先ほどのように)入れ替えるようになっています。するととてつもない時間がかかりますし、何より総距離はなかなか減っていかないと思います。するととてつもない時間がかかりますし、何より総距離はなかなか減っていかないと思います。それでも実行して放っていけばよいのでしょうか?突然変異の発生率を上げてもよいのですが、10都市でとてつもない時間がかかるならば、プログラムが正しく作れていない可能性もあります。5都市でプログラムを作ってみてはいかがですか。終了条件としてはすべてのデータで都市の回り方が同じになったらとなっていますがこれでいいですか?これはナンセンス。遺伝子の多様性を放棄しています。最終的な解はトップだけ取り出せばいいのです。一般的に終了条件の決定方法は難しいものです。ある程度の世代数が経っても最適解が更新されないようなら終了でよいでしょう。4年前3都市,5都市において交叉なしで解が収束しました。3都市,5都市において交叉なしで解が収束しました。次のステップとしては何をすべきでしょうか?「解が収束」が何を指しているのか判りません。机上での予想通りの最短経路が得られたということですか?そうであれば最低限の部分はできていることになります。ないならデバッグしてください。毎回乱数で都市の座標を決めているなら、デバッグをやりやすくするために、毎回同じ座標の組を使ってください。その10都市について、本当の最短経路を総当たりで計算してください。総当たりの結果が遺伝的アルゴリズムで得られたら次の段階に進めます。今どきの一般的なスペックのPCで10都市だと、1分以上かかるようならバグがあると思っていいでしょう。4年前10都市(スタート入れると11都市)、突然変異確率10%、交叉なしで1分間一番良いもののルートだけ表示してみましたが、最短経路を得られませんでした。試しに、10都市(スタート入れると11都市)、突然変異確率10%、交叉「あり」でテストしてみたところ、最短経路を得られました。10都市(スタート入れると11都市)、突然変異確率「1%」、交叉「あり」の場合も最短経路を得られました。かかった時間は1分とはいきませんが、素早い時間で得られました。目標の20都市になるととてつもなく時間がかかるようです。これは遺伝的アルゴリズムがうまくいっていると言えるのでしょうか?言えないでしょう。前も書きましたが、交叉がなくても機能するはずです。交叉なしでの性能が悪すぎるという事は、交叉以外の部分にバグがあるのでしょう。都市数が増えると爆発的に探索空間が広がるので、ごまかしが効かなくなっているのではないでしょうか。自分の能力以上のプログラムに取り組んでいる人には難しい作業です。推奨される方法ではないですが、一番簡単な方法は、プログラムとテストデータをここに載せて、デバッグを依頼することです。それでも解決するとは限りませんし、解決するとしても日数がかかるかもしれません。(掲示板とはそういうものです。有償のサービスを探してください。)ソースコードを見せたくない場合、アドバイスが必要ならば、もっと定量的な情報がほしいです。瞬時に解決しているでしょうか?その時の時間や世代数は?5都市で1秒以上かかるなら、やはりバグがあるものと思います。その他の定量的な情報の例としては、3都市以降の最短経路が得られるまでの時間と世代数とかです。・5都市(スタート地点を含むと6都市)・一度に10ルート・交叉なし・突然変異確率1%という条件でテストしてみると1~5分ほどかかってしまいました。(1~5分というのは何度かテストしたからです。)そこでいくつか疑問や気になったことがあったので質問します。確率で行うようになっています。稀に一世代前にはあった一番総距離の短い値が消えていたりします。200しかし、総距離の短い2ルートは突然変異しないようになっています。答えやすい方から書きます。総距離の短い2ルートは突然変異しないようになっています。それとも私のプログラムのバグでしょうか?当然バグです。確率で行うようになっていますその説明ではまだ曖昧ですので、確認させてください。以下のどれをさしているのでしょうか。平均すると、100世代に一回突然変異が起こる。平均すると、10世代に一回突然変異が起こる。平均すると、12.5世代に一回突然変異が起こる。(8遺伝子×12.5世代に一回)A)~C)までのいずれにも当てはまらないなら、どのような操作を行っているのか想像できません。説明を補足してください。いずれにしても、これでは殆ど新しい遺伝子は発生しません。A)~C)までの方針ならば、各世代で4~5回程度の突然変異でもよいのではないかと思います。Wikipediaには、『突然変異の確率は0.1%~1%、高くても数%である。遺伝子が長いほど、その確率も高くなります。ちなみに、現在のプログラムは「パス表現」と言われる表記で書かれていると想像していますが、これを「順序表現」に変えることで、遺伝子座単位の操作が楽になります。「順序表現」というものを理解して書き換えるのが手間ですが、交叉とも相性がよくなります。これは必須ではないですが、本格的にやるなら、いずれ手を出すことになると思います。http://homepage3.nifty.com/ono-t/GA/GA-tspcov-j.pdfさて、今後の方針についての提案です。1.最短経路がなくなる不具合を修正する。2.突然変異の確率を上げて色々試す。やるべきなのは、この2つでしょう。1.→2.の順番です。その上で、次のステップを検討したらよいと思います。3-1.交叉を実装する。3-2.順序表現に変更する。3-3.性能を向上させる。確率で行うようになっています実際には「平均すると100世代に1回、1つの遺伝子に突然変異が起こる」となっております。1%では低すぎますか?>これを「順序表現」に変えることで、遺伝子座単位の操作が楽になります。「順序表現」というものを理解して書き換えるのが手間ですが、交叉とも相性がよくなります。これは必須ではないですが、本格的にやるなら、いずれ手を出すことになると思います。最近まで順序表現にしていました。このやり方だと交叉によって良いデータが継がれていくとは思えないのです。D:12435となりますが、この場合、つながって受け継いでいるところがほぼありませんよね?これでは交叉の意味がないと思います。大前提として、今は交叉なしの実装の話です。順序表現の説明のため、将来実装する交叉を引き合いに出してしまった私の落ち度です。混乱させて申し訳ありません。実際には「平均すると100世代に1回、1つの遺伝子に突然変異が起こる」となっております。1%では低すぎますか?99世代の間は選択しか行わないことになります。無駄なだけではなく、その間に遺伝子群の多様性が失われてしまいます。ちなみに、生物学的な遺伝の知識が乏しいならば、これを機に軽く勉強することをお勧めします。多様性が失われることがアルゴリズム的にどういう意味を持つのか理解できると思います。私の理解が悪いのですか?交叉以前の部分がちゃんと動いていないのが現在の問題です。最短経路が消えてしまう不具合をまず修正してください。順序表現だろうとパス表現だろうと(一様交叉だろうとN点交叉だろうと)、それに比べたら大した問題ではありません。初心者は足元をおろそかにして色々試したくなるものです。交叉や表現を色々試してみても無駄ではないでしょうか。交叉以前の部分がちゃんと動いていないのが現在の問題です。最短経路が消えてしまう不具合をまず修正してください。変異の確率としてはどのくらいが適切でしょうか?交叉なし、あり両方教えて欲しいです。4年前やはり選択がおかしかったようです。修正すると最短経路が消えるということはなくなりました。この時点での質問をいくつかさせていただきます。・突然変異の確率はいくつが適切か。・親となったデータには突然変異が起こらないようになっているがこの処理は適切か。・交叉ありにすると、すぐにすべての遺伝子が同じになってしまいます。これは間違いなのでしょうか。みても間違いだと思いますが、のちのち、1つの解にたどり着き、そのときの遺伝子は皆同じなわけですよね?そう考えると間違いでもないのかと考えたりもするのですが・・・。・・・10)1000→これがしばらく続く。→また突然変異が起こるまでこのまま。ここで900が最短経路の総距離であればよいのですが・・・明らかにそうとは言えません。・親となったデータには突然変異が起こらないようになっているがこの処理は適切か。全遺伝子に突然変異が起こりうる方が「自然」です。アルゴリズム的には、折角得られた暫定的な最適解が失われてしまうのは避けたいところです。したら2度と見つからないかもしれませんので。文章だけでは伝わってこないので判断できません。10個体だとして、、、1.全個体(親世代)を評価する。2.上位2個体をコピーして子1と子2とする。3.適当な確率で親10個体に突然変異を発生させる。4.変異後の10個体からランダムに8個体選び、子3~子10とする。5.世代交代して1に戻る。以上は非常に単純な考えですが、最適解は失われないしちゃんと機能します。のちのち、1つの解にたどり着き、そのときの遺伝子は皆同じなわけですよね?これが大きな間違いです。最終的にほしいのは、優秀な遺伝子1つです。その時、他の遺伝子がどうなっていても構わないし、むしろ、ばらけていた方が望ましいです。暫定1位が進化の袋小路かもしれません。そこに収束してしまうと、それ以上の進化は望めません。TSPの例で説明します。数字は適当ですが、以下のような評価値だとします。BACDE現時点で得られた最適解は、BACEDの130点です。変異の発生率が低く、選択ばっかりしているとBACEDに収束してしまいます。BACEDからABCDEに変異するためには、AとBを入れ替える突然変異と、DとEを入れ替える突然変異の両方が発生しないといけません。数世代のうちに淘汰されてしまい、BACEDだけの集団になるでしょう。これが現在起こっていることだと思います。更なる突然変異が発生しないと理論的最適解は得られません。・突然変異の確率はいくつが適切か。常に適切だと言える数値はありません。遺伝子長にもよるし、選択がどれくらいシビア(弱者に厳しい)なのかにもよります。選択がうまく機能し始めたのならば、色々試してみてください。書きましたが、遺伝子座単位で『突然変異の確率は0.1%~1%、高くても数%である。1%とすると、10都市で10遺伝子ならば、平均して1世代に1回、突然変異が発生します。4年前>くっちゃべーさんがどのような処理をしているのか、上のように説明できますか?1.すべての個体を評価2.評価した結果に基づき、評価の高かった順に個体をソート3.すべての個体からルーレット方式にて2個体を親として選出。そのまま残して子1と子2とする(4.部分写像交叉にて親2個体から8個体を生成)5.子1と2を除いた8個体から100世代に1度10個体のうちの1個体に対して「ランダムの2箇所を入れ替える」という突然変異を行う6.1へ戻るといった具合です。>数世代のうちに淘汰されてしまい、BACEDだけの集団になるでしょう。これが現在起こっていることだと思います。更なる突然変異が発生しないと理論的最適解は得られません。その通りでしたので、突然変異の行う確率を大幅に変更しました。先ほどまでは上記の通り、「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へ戻るただ、突然変異のタイミングが気になります。その点について指摘お願いします。その他の気になる点についてご指摘ください。4年前1分は言いすぎました。1分から〜10分ほど。中には途中で実行を停止するぐらい長いものもありました。試しにと思って5都市でやってみると1秒かかりませんでした。変異のタイミングが気になります。その点について指摘お願いします。その他の気になる点についてご指摘ください。何が気になるのか具体的に書いてください。指摘のしようがありません。その他については、現在の成績が気になります。数倍もかかるのかでは、状況が全く違います。3.すべての個体からルーレット方式にて2個体を親として選出。目立った問題点はありません。手順通りにプログラムが作れているかは私には判りませんし、そろそろソースコードを見ないと、性能についてのアドバイスは難しそうです。今の知見で考察してみてはどうでしょうか。4年前>手順通りにプログラムが作れているかは私には判りませんし、そろそろソースコードを見ないと、性能についてのアドバイスは難しそうです。自分がきちんと説明できているか不安になってきました。説明通りにコードが書けているとは思えなくなってきました。ソースコードを載せます。A〜(B-1)の値を返すそのほかにも不明な点がありましたら質問ください。明確な終了時は決めていません。(50000世代を越えると終了するようにはなっていますが)また、setTotalDistanceとshowRouteの中身についてはライブラリ?の関数を大量に使っていましたのでコメント通り問題なく処理できているものだとしてください。問題ばかりだとは思いますが、ご指摘よろしくお願いします。自分がきちんと説明できているか不安になってきました。説明通りにコードが書けているとは思えなくなってきました。ソースコードを載せます。これらの関数をどのように呼び出しているかが欠けています。コメント通り問題なく処理できているものだとしてください。している部分程、バグがあるものです。この辺りも省略せずに、動かせるソースを載せてください。4年前>ごちゃごちゃしている部分程、バグがあるものです。この辺りも省略せずに、動かせるソースを載せてください。動かすためにゲームエンジンUnityを使用しますが、いかがいたしましょう?setTotalDistanceとshowRouteの中身についてもUnityの機能を大量に使っています。質問です(以前質問したかもしれませんが)交叉なし・10都市なら1分ほどと言いますが、なぜそう言い切れるのかわかりません。いかがいたしましょう?そのためにC#になったのですね。Unityの機能を大量に使っています。showRouteはともかく、setTotalDistanceにはこのライブラリの機能は不要と思いますが。遺伝的アルゴリズムの部分と、その結果を表示する部分がうまく分かれていないのでしょうか。ゲームエンジンUnityは、私は触ったことはありません。興味もなく、今後も触る予定はありません。No.28について言えることは、メソッド名と実際の処理が一致していないことです。showRoute()の中でSelection()を呼んでいたり、Selection()の中でmutation()を呼んでいたりするのが問題です。プログラムの見通しが悪くなり、バグの元でしょう。Update()からこれらのメソッドを呼び出すようにするのが、よいと思います。可読性を高めることによって、間違いに気づきやすくなったり、デバッグしやすくなったり、色々試しやすくなるものです。修正することをお勧めします。肝心の処理の方は、No.28のソースを元にして、動かせるようにしてみます。期待せずにお待ちください。4年前>肝心の処理の方は、No.28のソースを元にして、動かせるようにしてみます。期待せずにお待ちください。ご迷惑をおかして本当に申し訳ありません。なんとか十分な性能(20都市も1分くらい)のものを作りたいんです。