1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
|
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<title>47.2.Genetic Algorithms</title>
<link rel="stylesheet" href="stylesheet.css" type="text/css">
<link rev="made" href="pgsql-docs@postgresql.org">
<meta name="generator" content="DocBook XSL Stylesheets V1.70.0">
<link rel="start" href="index.html" title="PostgreSQL 8.1.4 Documentation">
<link rel="up" href="geqo.html" title="Chapter47.Genetic Query Optimizer">
<link rel="prev" href="geqo.html" title="Chapter47.Genetic Query Optimizer">
<link rel="next" href="geqo-pg-intro.html" title="47.3.Genetic Query Optimization (GEQO) in PostgreSQL">
<link rel="copyright" href="ln-legalnotice.html" title="Legal Notice">
</head>
<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"><div class="sect1" lang="en">
<div class="titlepage"><div><div><h2 class="title" style="clear: both">
<a name="geqo-intro2"></a>47.2.Genetic Algorithms</h2></div></div></div>
<p> The genetic algorithm (<acronym class="acronym">GA</acronym>) is a heuristic optimization method which
operates through
nondeterministic, randomized search. The set of possible solutions for the
optimization problem is considered as a
<em class="firstterm">population</em> of <em class="firstterm">individuals</em>.
The degree of adaptation of an individual to its environment is specified
by its <em class="firstterm">fitness</em>.
</p>
<p> The coordinates of an individual in the search space are represented
by <em class="firstterm">chromosomes</em>, in essence a set of character
strings. A <em class="firstterm">gene</em> is a
subsection of a chromosome which encodes the value of a single parameter
being optimized. Typical encodings for a gene could be <em class="firstterm">binary</em> or
<em class="firstterm">integer</em>.
</p>
<p> Through simulation of the evolutionary operations <em class="firstterm">recombination</em>,
<em class="firstterm">mutation</em>, and
<em class="firstterm">selection</em> new generations of search points are found
that show a higher average fitness than their ancestors.
</p>
<p> According to the <span class="systemitem">comp.ai.genetic</span> <acronym class="acronym">FAQ</acronym> it cannot be stressed too
strongly that a <acronym class="acronym">GA</acronym> is not a pure random search for a solution to a
problem. A <acronym class="acronym">GA</acronym> uses stochastic processes, but the result is distinctly
non-random (better than random).
</p>
<div class="figure">
<a name="geqo-diagram"></a><p class="title"><b>Figure47.1.Structured Diagram of a Genetic Algorithm</b></p>
<div class="figure-contents">
<div class="informaltable"><table border="0">
<colgroup>
<col>
<col>
</colgroup>
<tbody>
<tr>
<td>P(t)</td>
<td>generation of ancestors at a time t</td>
</tr>
<tr>
<td>P''(t)</td>
<td>generation of descendants at a time t</td>
</tr>
</tbody>
</table></div>
<pre class="literallayout">+=========================================+
|>>>>>>>>>>> Algorithm GA <<<<<<<<<<<<<<|
+=========================================+
| INITIALIZE t := 0 |
+=========================================+
| INITIALIZE P(t) |
+=========================================+
| evaluate FITNESS of P(t) |
+=========================================+
| while not STOPPING CRITERION do |
| +-------------------------------------+
| | P'(t) := RECOMBINATION{P(t)} |
| +-------------------------------------+
| | P''(t) := MUTATION{P'(t)} |
| +-------------------------------------+
| | P(t+1) := SELECTION{P''(t) + P(t)} |
| +-------------------------------------+
| | evaluate FITNESS of P''(t) |
| +-------------------------------------+
| | t := t + 1 |
+===+=====================================+</pre>
</div>
</div>
<br class="figure-break">
</div></body>
</html>
|
