次に、GAの最大のキモである、「染色体」を設計します ――といっても、本当に遺伝子操作を行うのではありません。GAでいうところの染色体は、コンピュータで扱うことのできる、単なる1列の文字列または数列に過ぎません。
今回の問題では、クリスマススケジュールの日程そのものを「染色体」とすることができるのですが、今回の場合、染色体の設計にちょっとした工夫が必要になります。ここでは「順序表現」という手法を用いています。
この図は、23日にEさん、24日にBさん、25日にAさん、26日にHさんとデートをする、というスケジュールを示す染色体を示しています。この"E・B・A・H"を、そのまま染色体として使うことも可能ですが、この表現方式では、簡単に致死染色体が発生してしまうのです。
例えば、"E・B・A・B" のように、Bさんと2日もデートするようなことになった場合、スケジュールとしては採用できませんので、全く評価されない「即死する」染色体(致死染色体)になってしまうからです。
これを回避するためには、例えば、上図のような手順の順序表現を用いて染色体を作ります。順序表現を使えば、同じ人物が2回以上選ばれることがないので、致死染色体が発生する恐れがありません。
その後は、適当な乱数を使って、デタラメなデートスケジュールの染色体を、大量に作ります。
染色体を大量に作れば作るほど、集団が大きくなって、良い解が見つかる可能性が高くなりますが、計算時間がかかるという問題もでてきますので、作りながら染色体の数を調整することが多いです。
Copyright © ITmedia, Inc. All Rights Reserved.