3
<meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
4
<title>46.2.�Genetic Algorithms</title>
5
<link rel="stylesheet" href="stylesheet.css" type="text/css">
6
<link rev="made" href="pgsql-docs@postgresql.org">
7
<meta name="generator" content="DocBook XSL Stylesheets V1.64.1">
8
<link rel="home" href="index.html" title="PostgreSQL 8.0.0beta5 Documentation">
9
<link rel="up" href="geqo.html" title="Chapter�46.�Genetic Query Optimizer">
10
<link rel="previous" href="geqo.html" title="Chapter�46.�Genetic Query Optimizer">
11
<link rel="next" href="geqo-pg-intro.html" title="46.3.�Genetic Query Optimization (GEQO) in PostgreSQL">
13
<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"><div class="sect1" lang="en">
14
<div class="titlepage">
15
<div><div><h2 class="title" style="clear: both">
16
<a name="geqo-intro2"></a>46.2.�Genetic Algorithms</h2></div></div>
19
<p> The genetic algorithm (<span class="acronym">GA</span>) is a heuristic optimization method which
21
determined, randomized search. The set of possible solutions for the
22
optimization problem is considered as a
23
<i class="firstterm">population</i> of <i class="firstterm">individuals</i>.
24
The degree of adaptation of an individual to its environment is specified
25
by its <i class="firstterm">fitness</i>.
27
<p> The coordinates of an individual in the search space are represented
28
by <i class="firstterm">chromosomes</i>, in essence a set of character
29
strings. A <i class="firstterm">gene</i> is a
30
subsection of a chromosome which encodes the value of a single parameter
31
being optimized. Typical encodings for a gene could be <i class="firstterm">binary</i> or
32
<i class="firstterm">integer</i>.
34
<p> Through simulation of the evolutionary operations <i class="firstterm">recombination</i>,
35
<i class="firstterm">mutation</i>, and
36
<i class="firstterm">selection</i> new generations of search points are found
37
that show a higher average fitness than their ancestors.
39
<p> According to the <span class="systemitem">comp.ai.genetic</span> <span class="acronym">FAQ</span> it cannot be stressed too
40
strongly that a <span class="acronym">GA</span> is not a pure random search for a solution to a
41
problem. A <span class="acronym">GA</span> uses stochastic processes, but the result is distinctly
42
non-random (better than random).
45
<a name="geqo-diagram"></a><p class="title"><b>Figure�46.1.�Structured Diagram of a Genetic Algorithm</b></p>
46
<div class="informaltable"><table border="0">
54
<td>generation of ancestors at a time t</td>
58
<td>generation of descendants at a time t</td>
62
<pre class="literallayout">+=========================================+
63
|>>>>>>>>>>> Algorithm GA <<<<<<<<<<<<<<|
64
+=========================================+
66
+=========================================+
68
+=========================================+
69
| evaluate FITNESS of P(t) |
70
+=========================================+
71
| while not STOPPING CRITERION do |
72
| +-------------------------------------+
73
| | P'(t) := RECOMBINATION{P(t)} |
74
| +-------------------------------------+
75
| | P''(t) := MUTATION{P'(t)} |
76
| +-------------------------------------+
77
| | P(t+1) := SELECTION{P''(t) + P(t)} |
78
| +-------------------------------------+
79
| | evaluate FITNESS of P''(t) |
80
| +-------------------------------------+
82
+===+=====================================+</pre>
added
removed
docs/en_US/pg/geqo-intro2.html
