組み合わせ最適化問題にも“やわらかい”計算が有効

　変数が多く，さまざまに考えられる組み合わせの中から最適な解を求めるような問題を，組み合わせ最適化問題という。

　組み合わせ最適化問題には，著名な例題がいくつかある。複数の都市を巡回するのに，どの順番で回れば最短距離で回れるか（もしくは旅費を最小にできるか）を求める「巡回セールスマン問題」や，異なる重量と価格の商品をどう収納すれば，ナップサックに詰める商品の総価格を最大にできるかを求める「ナップサック問題」などである。

　変数が少なければすべての組み合わせを算出して最適解を導けるが，変数が増えるに従い，組み合わせの数が膨大になる。こうなると，計算量が爆発的に増加し，現実的な時間では解が求められない。

　こうした問題を解くのにも，非劣解を求める計算手法が有効だ。最適解ではないにしても，準最適解を求めることで，最適解の近似値を得る。近似に止まる代わりに，短時間で受け入れられる解を導き出せる。ニューラル・ネットワークや遺伝的アルゴリズムは，神経細胞の動作や遺伝子の働きといった従来とは異なるアルゴリズムを利用することで，有効に組み合わせ最適化問題を解く。

図●最適化問題の解決を妨げるローカル・ミニマム
評価関数が最小となる点を最適解とする場合。評価関数が複数の谷を持つとき，最適解を持たない谷に落ち込んだまま抜け出せないと，誤った最適解を求めてしまう。これをローカル・ミニマム（局所最小点）という。最適化問題を解決しようとすると，数学的手法であれ，ニューラル・ネットワークや遺伝的アルゴリズムであれ，ローカル・ミニマムの回避が課題となる。

　組み合わせ最適化問題は古くからあり，このような問題を解く方法は，生物のふるまいを模したもの以外にも考案されている。例えば，「シミュレーテッド・アニーリング」である。これは，ある1点の状態を基準とし，わずかに遷移した地点の状態との間で評価値を比較する。より適切な方を新たな基準として，同様の比較を繰り返す。これにより，近似的に最適解を得る。この際，単純に比較するのではなく，ある確率で適切ではない方を選ぶようにしておくと，ローカル・ミニマム（局所最小点）と呼ばれる誤った解を算出することを防げる（図[拡大表示]）。

　シミュレーテッド・アニーリングは，「疑似冷却法」「焼きなまし法」とも呼ばれる。物質が液体から固体に変わる際，ゆっくり温度が下がれば整然とした結晶構造になりエネルギーが極小になるが，急激に冷やすとアモルファス状態になりエネルギーが最小にならない現象を基に考案された。初めのうちは温度が高い。これを熱ゆらぎが大きいと考え，2点間の比較をするとき，適切ではない地点を選ぶ確率を高くすることで表す。これにより局所的な谷を抜け出して，最適解を持つ谷に進むことができる。最適解に近づくにつれて確率を低くする。シミュレーテッド・アニーリングでは，この確率変動の制御（温度制御という）が重要になる。