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

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

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

#31

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

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

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

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

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

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

#32

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

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

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


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

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


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

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

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


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

くっちゃべー

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

#33

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

>肝心の処理の方は、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
登録日時: 9年前

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

#34

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

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

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

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

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


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

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


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

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

くっちゃべー

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

#35

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

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

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

#36

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

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

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

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



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

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

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

くっちゃべー

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

#37

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

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

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

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

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

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

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

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

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

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

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

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

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

#38

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

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

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

くっちゃべー

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

#39

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

>「理論的最適解」

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

>「準最適解」

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

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

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

#40

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

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

くっちゃべーさんの取り組んでいる問題、「巡回セールスマン問題」は、
「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 くっちゃべー » 3年前

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

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

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

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

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

#42

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

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


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

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

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

くっちゃべー

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

#43

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

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


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

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

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

#44

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

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

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

くっちゃべー

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

#45

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

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

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

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

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

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

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

#46

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

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

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


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

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


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

ABCDEFG → AB CDE FG → AB EDC FG → ABEDCFG


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

くっちゃべー

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

#47

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

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

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

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

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

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

#48

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

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

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

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

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

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

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

#49

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

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


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

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

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

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

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

閉鎖

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