PostgreSQL Programmer's Guide
PrevChapter 22. データベースシステムにおける,遺伝的問い合わせの最適化Next

遺伝的アルゴリズム(Genetic Algorithms(GA))

GAは,確定ランダムサーチを利用して動作する 試行錯誤的な最適化手法です.最適化の難問に対して可能性のある 解決策のセットは,個体の母集団として考えられます.

検索空間における個体の関係は染色体により 表現されますが,その実体は文字列のセットです. 遺伝子は,最適化される単一のパラメータの 値をエンコードする染色体の一部です.代表的な遺伝子の エンコーディングはバイナリかまたは 整数です.

進化的手術である 遺伝子組み替え突然変異 および 淘汰の シミュレーションを通して,その先祖より高い平均適合性を示す,新しい 検索ポイントの子孫が見つかります.

"comp.ai.genetic" FAQ によると,GAが問題点を解決するための純粋なランダム検索ではないという ことは,そう大したストレスにはなり得ないとのことです. GA は推計学的なプロセスを使用しますが,その結果は 明確に非ランダム(ランダムよりもよい)になります.

GAの構造化ダイアグラムです.
---------------------------

P(t)    時間 t における子孫
P''(t)  時間 t において継承した子孫

+=========================================+
|>>>>>>>>>  アルゴリズム GA  <<<<<<<<<<<<<|
+=========================================+
| t := 0 で初期化                         |
+=========================================+
| P(t) を初期化                           |
+=========================================+
| P(t) の適合性を評価する                 |
+=========================================+
| 判断基準になるまで実行                  |
|   +-------------------------------------+
|   | P'(t)  := 再結合{P(t)}              |
|   +-------------------------------------+
|   | P''(t) := 突然変異{P'(t)}           |
|   +-------------------------------------+
|   | P(t+1) := 淘汰{P''(t) + P(t)}       |
|   +-------------------------------------+
|   | P''(t)の適合性を評価                |
|   +-------------------------------------+
|   | t := t + 1                          |
+===+=====================================+


PrevHomeNext
データベースシステムにおける,遺伝的問い合わせの最適化UpPostgres における,遺伝的問い合わせの最適化 (GEQO)