遺伝的アルゴリズムの遺伝子の長さについて

質問

今、グラフ理論と遺伝的アルゴリズム（以下ＧＡ）の勉強をしています。
グラフ理論の最小全域木問題をＧＡを使って解こうと考えています。そこで、個体の遺伝子の長さをそのグラフの点の数Ｎにすればよいのではないかと考えました。
しかし、グラフが大きく、点の数Ｎが１００や１０００になった場合は、遺伝子の長さも非常に長くなってしまいます。これはＧＡとして問題があるかないかについて教えてください。
よろしくお願いします。

回答No.3

pori_boy · ベストアンサー

こんにちは．

遺伝子の長さが問題のサイズが大きくなるにつれて長くなってしまうのは，基本的にどうしようもないことなので問題はないといえます．
ただし，以下の点についても考える必要があると思います．

1. 遺伝子の長さをグラフの点の数Nとして，どのように最小全域木を表現できるでしょうか？
これは，難しい（考えるべき）課題です．他の回答者の方も言っているように，遺伝子の決め方はとても重要になります．

2. 最小全域木問題をGAを使って解くことが適当かどうか検討が必要です．
勉強のために，わざと，GAを用いて解くのであればよいですが，そうでないのであれば，GAを用いるのが適切な問題かどうかをまず考えて下さい．
最小全域木問題を解くことが目的なのであれば，単純かつ効率的なアルゴリズムが存在するので，GAを用いて近似解を得ることは推奨されません．

お礼

回答していだだきありがとうございます。
シュミレーションをしてみて、検討するのが良い方法ではないかと最近考えております。
お礼とあわせて、１と２について補足をさせていただきます。
１．木→遺伝子と遺伝子→木の符号化・復号化はできると思います。
　（複数の論文に書いてありました。正直プログラムができるかはわかりませんが・・・）
２．最小全域木問題の他の解き方（プリム法とクラスカル法）については勉強をしました。
　そこで、点の数Ｎが非常に多い場合はどうするか？と考えた次第です。

今後も勉強をしていこうと思います。ありがとうございました。

回答No.2

rabbit_cat

＞これはＧＡとして問題があるかないかについて教えてください。
これ自体が非常に難しい問題です。
一般論で言えば、ＧＡがうまく働くかどうかは、ほとんど、Ｇｅｎｅの決め方にかかっています。あんまり長いのは普通はよくないでしょうね。

お礼

回答していただきありがとうございます。
シュミレーションでいろいろとやってみるのが良いのかな、と考えています。

回答No.1

noname#194289

ずれているかもしれませんが、何かの理論（グラフ理論かどうかわかりませんが）に基づいて計算すると普通のたんぱく分子が最も安定な形を取るためにかかる時間が膨大なものになってしまうというような話を聞いたことがあります。現実にはどんなたんぱく分子でも簡単に安定した形におさまってしまうようです。見当はずれかもしれませんがもし少しでも参考になればと思い書きました。

お礼

回答していだだきありがとうございます。
たんぱく分子については全く知らないことでしたので、
今後勉強をしていきたいと思います。