PostgreSQL
PrevChapter 50. データベースシステムにおける,遺伝的問い合わせの最適化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)