カーナビの目的地ルート検索は「最適化」の例

多くの選択肢の中から最も良いものを選ぶ「最適化手法」とは？

私たちの身の回りには多くの工学的問題が存在します。回路設計、プラントの制御、スケジューリング、マネジメントやプランニング、建物の構造設計など。これらの多くは限られた資源、制約のもとで最善の“解”を決定することが望まれ、最適化問題として定式化されます。最適化とは、ある制約条件のもと、目的関数の最小値、あるいは最大値を与える設計変数を求めることをいいます。
　身近な例を挙げると、カーナビの目的地ルート検索でも最適化が行われています。目的地を入力すると最小走行距離のルートや最小料金ルートなどが表示されます。ここでは、ルートが設計変数で走行距離や料金が目的関数です。一方で、通過地点の指定などユーザが与える制約や工事中で利用できない経路などがあった場合には、それが制約条件になります。
　目的関数および設計変数を設定しモデルが決定すれば、次に“最適解”を得るための解法が必要となります。遺伝的アルゴリズムもその一つです。

選択・交叉・突然変異を繰り返して“解”を探索

遺伝的アルゴリズムとは？

遺伝的アルゴリズムは、自然界における生物の適応進化のメカニズムを工学的にモデル化したアルゴリズムです。自然界では、生活環境に適応できない個体は死滅し、環境に適応した個体は生き残り子孫を増やしていきます（図：適応進化のメカニズムのイメージ）。このメカニズムをモデル化し、問題に対して最もよく適応する個体、すなわち“最適解”をコンピュータ上で生成しようというのが遺伝的アルゴリズムの考え方です。
　遺伝的アルゴリズムによる解探索は、個体(individual)と呼ばれる解の集合である母集団に対して、選択(selection)・交叉(crossover)・突然変異(mutation)と呼ばれる遺伝的オペレータを繰り返し適用することによって行われます。
　ある世代を形成している個体間で交叉を行い新しい個体を生成する。また、一定の確率で遺伝子を反転させて、突然変異という操作を加える。こうして生成された個体を評価し、その中で環境への適合度が高い個体ほど高い確率で生き残り、次の世代を形成する。このような世代の更新を繰り返すことで、次第により良い個体が生成され、最適解に近づいていくというのが遺伝的アルゴリズムの基本的な概念です。
　自然界においては、環境に対して適応する度合いの高い個体が生き残り繁殖します。逆に適応力が低い個体は死滅します。遺伝的アルゴリズムにおいてもそれは同様であり、求める解に近い個体ほど、次世代へ残る確率が高くなるわけです。

生産計画、製品在庫の安定に寄与

遺伝的アルゴリズムの応用例を挙げてください。

都市の集合が与えられたとき、すべての都市を1回ずつ訪問して、出発点の都市に戻って来るなかで最短の経路長を有するものを求める「巡回セールスマン問題(Traveling SalesmanProblem)」は、代表的な組み合わせ最適化問題の一つです。X線結晶解析のアプリケーションや回路設計、タンパク質の構造解析などの基礎となるモデルです。

具体的に花田先生がかかわった工場の生産計画（スケジューリング）の例を挙げて説明してください。

東大阪市にある部品工場で、在庫のコントロールを目的としたスケジューリングの数理モデル化と解法の開発に当たりました。多くの製品を複数の機械で製造するのですが、1台の機械は製造する製品の切り替え時にセットアップ時間を要します。2000種の製品と30台の機械の間に依存関係があり、セットアップ回数を最小化、つまり機械をフルに回転しつつ、どの機械にどの製品を処理すると製品在庫が安定するかということが課題でした。
　遺伝的アルゴリズムにより1年間の各製品の生産スケジュールを自動生成したところ、最終的に総セットアップ回数を最小化しつつ、人手によるスケジュールに比べて在庫の変異幅（空き倉庫容量）を半分にすることができました。

実用性向上で強力な最適化手法に

これからの研究課題は？

実問題へ遺伝的アルゴリズムを適用するにあたって望まれることは、その探索性能、汎用性、実用性の向上です。高性能化を図るカギは、遺伝的アルゴリズムの主探索オペレータである交叉の設計にあります。交叉において、親個体が持つ良好な形質（部分解）が結合され、より優れた子個体が生成される操作を設計できたなら、遺伝的アルゴリズムは強力な最適化手法となりえます。
　また、並列処理との親和性は遺伝的アルゴリズムの高い実用性を保証する大きな特徴の一つであり、負荷の高い実問題に遺伝的アルゴリズムを適用する際には、並列処理することで高速化が図られてきました。最近では、広域ネットワークの通信速度、計算機性能の向上により大規模な計算環境が整いつつあり、遺伝的アルゴリズムの実アプリケーションへの期待が高まっています。