さきほど以下のように書き換えました。すると10都市もほぼ1分かからずでした。20都市のほうはまだまだでした。これだと交叉なしにはならないです。1.すべての個体を評価2.評価した結果に基づき、評価の高かった順に個体をソート3.すべての個体からルーレット方式にて2個体を親として選出。交叉なし・10都市なら1分ほどと言いますが、なぜそう言い切れるのかわかりません。1世代に1度でも確率として少なすぎるのでしょうか?遺伝的アルゴリズムに明確な終わりはありません。時間をかけても最適解が得られる保証はありません。都市数が増えると爆発的に探索空間が広がるので、10都市程度で最適解を得られないなら、20都市では役に立たないだろうという私の経験によるものです。以下の質問にも答えてもらっていません。その他については、現在の成績が気になります。数倍もかかるのかでは、状況が全く違います。これもスルーされています。今の知見で考察してみてはどうでしょうか。成績の悪いものが残らないようにするのが交叉ではないのでしょうか?くっちゃべーさんは「交叉」という操作の意味をまだ理解していないと思います。自分のプログラムがどうなっているのか、どうあるべきなのか、考察してみてほしいです。4年前>10都市程度で最適解を得られないなら、20都市では役に立たないだろうという私の経験によるものです。10都市ほどならすぐに得られるようになりました。1つ前のプログラムからの変更点のみ載せます。その他については、現在の成績が気になります。数倍もかかるのかでは、状況が全く違います。10都市は問題なく到達でき、20都市の場合ぱっと見うまくいっていますが、スタート地点から結ぶ最初の点の位置がおかしかったりと惜しいです。距離に関しても最初の点がうまくいっていないために長くなっています。今の知見で考察してみてはどうでしょうか。何と言っても突然変異の確率を大幅に改善したからだと思います。そのときのバージョンよりも突然変異しやすく、また突然変異するタイミングを交叉後から交叉の代わりに行うように変えたため現在のほうが好成績を残せています。>くっちゃべーさんは「交叉」という操作の意味をまだ理解していないと思います。自分のプログラムがどうなっているのか、どうあるべきなのか、考察してみてほしいです。思いつくままの質問していたと思います。現在のプログラムも基礎的な部分はうまく働いていると言えるのではないかと思います。良い記録が失われることや通らない都市がでてくる問題もなくなりました。何より10都市が1分かからず解くことができ嬉しく思っております。20都市もおそらく時間さえかければ解けると思いますが、それでは遺伝的アルゴリズムの意味がありませんので、20都市も1分ほどで解けるようにしたいです。上のコード、さきほどのコード(全体のプログラム)を元になにが問題なのかあるいはなにを追加すべき教えて欲しいです。それでは遺伝的アルゴリズムの意味がありませんので、20都市も1分ほどで解けるようにしたいです。なにが問題なのかあるいはなにを追加すべき教えて欲しいです。「解ける」とはどういうことを指していますか?既に次のように書いています。遺伝的アルゴリズムに明確な終わりはありません。時間をかけても最適解が得られる保証はありません。今の知見で考察してみてはどうでしょうか。何と言っても突然変異の確率を大幅に改善したからだと思います。交叉後から交叉の代わりに行うように変えたため現在のほうが好成績を残せています。質問と答えが噛み合っていませんね。4年前>「解ける」とはどういうことを指していますか?既に次のように書いています。何か誤解していませんか?解けるという言葉は間違いでした。私の言いたかったことは最短経路が得られるということです。>そもそも「交叉」とはどのような操作ですか?親2個体のデータを利用して子を生成する操作だと考えています。>この操作を行う目的は何ですか?最短経路を得るためにかかる時間・世代数を減らすこと考えています。>その目的は達成できていますか?以前よりも達成できていると思いますが、まだ不十分です。>できていることをどのように検証できますか?実際に実行してみて、最短経路を得られるのにかかる時間・世代数を比べることで検証できると考えています。4年前やはり根本的に誤解しています。遺伝的アルゴリズムで最短経路が得られる保証はありません。私が書いた「理論的最適解」と「準最適解」という言葉について考えてみてください。4年前>「理論的最適解」2点の距離の総和が一番短いものを指すのはないでしょうか。一定の時間における理論的最適解ということでしょうか。4年前やはり、自分が何をしているのか、よく判っていなかったのですね。「NP困難」と言われる難しさの問題です。都市数が5の場合、あり得る経路の数は5!=120通りしかなく、120通りを全て試して最短経路を見つけるプログラムは簡単に作れるでしょう。都市数5と同じ総当たりのプログラムで最短経路を見つけることができます。今どきのPCなら、殆ど瞬時に見つけられるでしょう。都市数が20になると、経路の数は20!=2432902008176640000通りであり、PCでは総当たりを試すことは不可能になります。都市数が100になったらどうなるでしょうか。「NP困難」な問題の特徴です。「遺伝的アルゴリズム」は、「NP困難」な問題を解けるわけではありません。現実的な時間内に、そこそこの解を求めるアルゴリズムです。ーさんのゴールはどこでしょうか。自分の勉強不足や伝える力が少ないことをこのスレで大変実感しました。以後気をつけて質問したいです。>「遺伝的アルゴリズム」は、「NP困難」な問題を解けるわけではありません。現実的な時間内に、そこそこの解を求めるアルゴリズムです。ーさんのゴールはどこでしょうか。5都市は1秒かからず、10都市ならば30秒〜1分ほどでそこそこの解を求めることができました。私のゴールとしては20都市をそこそこの時間でそこそこの解が得られるようにすることとしています。仮に、くっちゃべーさんの作ったプログラムを私が作ったら、倍の速さで動くとします。同じプログラムが5倍の速さで動くようになるかもしれません。「一般的に何分か?」という質問に意味がないことが判るでしょう。したらいいでしょうか。プログラムが完成しているとします。1分後、3分後、5分後、10分後、30分後、、、などの成績を見てください。何回も試して、傾向や平均を調べてください。4年前>「一般的に何分か?」という質問に意味がないことが判るでしょう。>もし100回試した結果、5分後と比較して10分後の成績がよくなるケースが10回だった場合、5分の時点で打ち切るべきでしょうか?100回中1回でも成績が良くなっていたなら、10分までは続けるべきでしょうか?これは誰が決めるべきですか?プログラムを書いている私が決めることだと思います。20都市で5万世代たっても最短経路が得られません。正直に言って、10、20回やってみても1度も得られていません。時間がかかりすぎだと思います。最短経路を求められるアルゴリズムではないと書きましたが。4年前>ちなみに最短経路を得られていないことは、どのように確認しているのですか?見た目です。怪しいものはのぞいたとしても、明らかに無駄な通り方をしているものが多いです。>最短経路を求められるアルゴリズムではないと書きましたが。何がご不満なのですか?(1番優秀なデータとして)無駄な通り方をしていないものになるまでにかかる時間を減らしたいのです。PCの性能など多くの条件があってどこまで減らせるかわかりません。1時間かけても無駄な通り方をしているものばかりです。かかる時間を減らす方法を教えて欲しいのです。怪しいものはのぞいたとしても、明らかに無駄な通り方をしているものが多いです。どのように「明らか」なのか、具体的に説明できますか?日本語で正確に説明できるなら、コーディングにすることも難しくないかもしれません。日本語で説明できないなら、コーディングなんて不可能です。コーディングできるなら、終了条件に使えますね。交叉についてですが、TSPには有効でない操作だと私は考えています。実際プログラムに取り入れても改良されませんでした。失礼ながら、杜撰な検証と理解による、誤った結論だと私は思います。改良の案としては、「反転」という操作はどうでしょうか。1本の遺伝子からランダムに2点を選び、2点に挟まれた部分を逆転させます。以下のような操作です。ABEDCFGパス表現ならば簡単に実装できるし、交叉より、よほどお勧めです。4年前>改良の案としては、「反転」という操作はどうでしょうか。1本の遺伝子からランダムに2点を選び、2点に挟まれた部分を逆転させます。実際に「反転」を実装してみました。すると、目に見てわかるくらい変化がありました。自分の納得のいくレベルに辿り着けたと思っております。このスレを解決に持って行けるレベルです。正直になんの不満もないレベルです。このまま終わりにしたくない理由が1つあります。それはなぜこの「反転」を実装することでここまで変化したのかということです。自分で考えろと言われてしまえばそれまでですし、それでも構いません。教えていただけるようでしたら教えていただきたいです。改善されたとのことで何よりです。問題の性質やアルゴリズムの特徴を全く理解していないのだと思います。交叉が何故役に立たない(と私が思っている)のかも、判らないのでしょう。次は自分が何を作ったのか、考えてみてください。出し惜しみしたいわけではないですが、回答は数日待ってください。私としては自明なことなので、どのように説明したら判りやすいか、(酔って帰った今は)思いつきません。読んでもらえたとしても、くっちゃべーさんにどれほど理解していただけるか判りませんが、やり残した気がするので一応書きます。最適解を見つけられない事です。存在しないと思います。成績の良い解を少々変更しても、成績が下がるだけで、すぐに淘汰されてしまいます。普通の突然変異がうまく重なって、元の解よりも成績の良い解が得られる確率は非常に小さいでしょう。TSPを日本の都道府県の県庁所在地巡りで説明すると、そこそこ成績の良い解は、局所的には最適化されています。...と試しているようなものです。ように変更するようなイメージです。反転によって、この最適化は損なわれません。同様に、(...→近畿)の部分と九州についても、局所最適化は損なわれません。全体的な最適化に繋がりうる程度に大きな変更を行えるのが反転という操作です。このような操作が可能なので、NP困難な問題の中ではTSPは比較的簡単とも言えるでしょう。ミクプラは自由にリンクできます。