進化計算

進化計算は、生物の進化になぞらえた最適化のメタヒューリスティックである。1990年代の遺伝的アルゴリズムを発端に、遺伝的プログラミング、群知能最適化、遺伝的プログラミングなどが発展した。原理としては多点確率的探索であり、解空間および問題空間での、各々の候補点を生物や遺伝子としてとらえそれらの交配や突然変異を探索手続きとして最適解を探す。

問題の詳細な分析をせずにも、ランダム探索に比べて効率よく良い解を得ることができる。その一方でノーフリーランチ定理により、探索能力の上界が示されるとともに、探索パラメータや構造設定は問題に特異的であり平均的には破壊的な効率を出せるわけではないことが示されている。

実用上は、解空間の表現と評価関数さえ与えられれば簡便に最適解探索ができるため、広く利用されている。

遺伝的アルゴリズムは、最適化問題で問題空間のパラメータの組みとその遺伝子表現との対応関数を構成し、遺伝子表現での交配、突然変異を行い、目的関数による評価でよいパフォーマンスをあげたものを選択淘汰することで、よりよい解を探索する。

たとえば、荷物詰め込み問題であれば、詰め込む荷物の組の候補 (A, B, C)や(D, E, F) などを遺伝子とみる（遺伝子コーディング）。その交配によって(A, B, F) や(D, B, F)などの子孫遺伝子を作り、その中から評価のよいものを残して繰り返す（世代交代）この操作を何度か繰り返し最適な組み合わせを発見する。一般には、同じ回数の評価を、ランダムに作った解候補に対して行うよりもよい結果が得られやすい。

遺伝的プログラミングは、プログラム片を遺伝子とし、その進化によって対象問題を解くプログラムを探す。

2000年ころには、サブサンプションアーキテクチャとあいまって進化的ロボティクスも流行した。ロボットの制御アルゴリズムを、多数の行動規則の群で構成し、その規則を進化的に取捨選択する。これによって所与の環境に適応したロボット制御アルゴリズムを得る。複雑な条件や複雑な構造をもち、設計則が明らかでないロボットの設計に用いられた。

群知能最適化、スウォームオプティマイゼーションは、昆虫や鳥などの群の行動を模して、多点探索により最適解を求める手法である。