~ubuntu-branches/ubuntu/oneiric/postgresql-9.1/oneiric-security : contents of doc/src/sgml/html/geqo-intro2.html at revision 15

~ubuntu-branches/ubuntu/oneiric/postgresql-9.1/oneiric-security : (revision 15)

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<HTML
><HEAD
><TITLE
>Genetic Algorithms</TITLE
><META
NAME="GENERATOR"
CONTENT="Modular DocBook HTML Stylesheet Version 1.79"><LINK
REV="MADE"
HREF="mailto:pgsql-docs@postgresql.org"><LINK
REL="HOME"
TITLE="PostgreSQL 9.1.9 Documentation"
HREF="index.html"><LINK
REL="UP"
TITLE="Genetic Query Optimizer"
HREF="geqo.html"><LINK
REL="PREVIOUS"
TITLE="Query Handling as a Complex Optimization Problem"
HREF="geqo-intro.html"><LINK
REL="NEXT"
TITLE="Genetic Query Optimization (GEQO) in PostgreSQL"
HREF="geqo-pg-intro.html"><LINK
REL="STYLESHEET"
TYPE="text/css"
HREF="stylesheet.css"><META
HTTP-EQUIV="Content-Type"
CONTENT="text/html; charset=ISO-8859-1"><META
NAME="creation"
CONTENT="2013-04-01T18:35:08"></HEAD
><BODY
CLASS="SECT1"
><DIV
CLASS="NAVHEADER"
><TABLE
SUMMARY="Header navigation table"
WIDTH="100%"
BORDER="0"
CELLPADDING="0"
CELLSPACING="0"
><TR
><TH
COLSPAN="5"
ALIGN="center"
VALIGN="bottom"
><A
HREF="index.html"
>PostgreSQL 9.1.9 Documentation</A
></TH
></TR
><TR
><TD
WIDTH="10%"
ALIGN="left"
VALIGN="top"
><A
TITLE="Query Handling as a Complex Optimization Problem"
HREF="geqo-intro.html"
ACCESSKEY="P"
>Prev</A
></TD
><TD
WIDTH="10%"
ALIGN="left"
VALIGN="top"
><A
HREF="geqo.html"
ACCESSKEY="U"
>Up</A
></TD
><TD
WIDTH="60%"
ALIGN="center"
VALIGN="bottom"
>Chapter 51. Genetic Query Optimizer</TD
><TD
WIDTH="20%"
ALIGN="right"
VALIGN="top"
><A
TITLE="Genetic Query Optimization (GEQO) in PostgreSQL"
HREF="geqo-pg-intro.html"
ACCESSKEY="N"
>Next</A
></TD
></TR
></TABLE
><HR
ALIGN="LEFT"
WIDTH="100%"></DIV
><DIV
CLASS="SECT1"
><H1
CLASS="SECT1"
><A
NAME="GEQO-INTRO2"
>51.2. Genetic Algorithms</A
></H1
><P
>    The genetic algorithm (<ACRONYM
CLASS="ACRONYM"
>GA</ACRONYM
>) is a heuristic optimization method which
    operates through randomized search. The set of possible solutions for the
    optimization problem is considered as a
    <I
CLASS="FIRSTTERM"
>population</I
> of <I
CLASS="FIRSTTERM"
>individuals</I
>.
    The degree of adaptation of an individual to its environment is specified
    by its <I
CLASS="FIRSTTERM"
>fitness</I
>.
   </P
><P
>    The coordinates of an individual in the search space are represented
    by <I
CLASS="FIRSTTERM"
>chromosomes</I
>, in essence a set of character
    strings. A <I
CLASS="FIRSTTERM"
>gene</I
> is a
    subsection of a chromosome which encodes the value of a single parameter
    being optimized. Typical encodings for a gene could be <I
CLASS="FIRSTTERM"
>binary</I
> or
    <I
CLASS="FIRSTTERM"
>integer</I
>.
   </P
><P
>    Through simulation of the evolutionary operations <I
CLASS="FIRSTTERM"
>recombination</I
>,
    <I
CLASS="FIRSTTERM"
>mutation</I
>, and
    <I
CLASS="FIRSTTERM"
>selection</I
> 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
><B
>Figure 51-1. Structured Diagram of a Genetic Algorithm</B
></P
><DIV
CLASS="INFORMALTABLE"
><P
></P
><A
NAME="AEN93857"
></A
><TABLE
BORDER="0"
FRAME="void"
CLASS="CALSTABLE"
><COL><COL><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
><P
></P
></DIV
><PRE
CLASS="LITERALLAYOUT"
>+=========================================+
|&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;  Algorithm GA  &lt;&lt;&lt;&lt;&lt;&lt;&lt;&lt;&lt;&lt;&lt;&lt;&lt;&lt;|
+=========================================+
| 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
><DIV
CLASS="NAVFOOTER"
><HR
ALIGN="LEFT"
WIDTH="100%"><TABLE
SUMMARY="Footer navigation table"
WIDTH="100%"
BORDER="0"
CELLPADDING="0"
CELLSPACING="0"
><TR
><TD
WIDTH="33%"
ALIGN="left"
VALIGN="top"
><A
HREF="geqo-intro.html"
ACCESSKEY="P"
>Prev</A
></TD
><TD
WIDTH="34%"
ALIGN="center"
VALIGN="top"
><A
HREF="index.html"
ACCESSKEY="H"
>Home</A
></TD
><TD
WIDTH="33%"
ALIGN="right"
VALIGN="top"
><A
HREF="geqo-pg-intro.html"
ACCESSKEY="N"
>Next</A
></TD
></TR
><TR
><TD
WIDTH="33%"
ALIGN="left"
VALIGN="top"
>Query Handling as a Complex Optimization Problem</TD
><TD
WIDTH="34%"
ALIGN="center"
VALIGN="top"
><A
HREF="geqo.html"
ACCESSKEY="U"
>Up</A
></TD
><TD
WIDTH="33%"
ALIGN="right"
VALIGN="top"
>Genetic Query Optimization (<ACRONYM
CLASS="ACRONYM"
>GEQO</ACRONYM
>) in PostgreSQL</TD
></TR
></TABLE
></DIV
></BODY
></HTML
>

1 by Martin Pitt Import upstream version 9.1~beta1	1	<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
	2	<HTML
	3	><HEAD
	4	><TITLE
	5	>Genetic Algorithms</TITLE
	6	><META
	7	NAME="GENERATOR"
	8	CONTENT="Modular DocBook HTML Stylesheet Version 1.79"><LINK
	9	REV="MADE"
	10	HREF="mailto:pgsql-docs@postgresql.org"><LINK
	11	REL="HOME"
1.1.11 by Martin Pitt Import upstream version 9.1.9	12	TITLE="PostgreSQL 9.1.9 Documentation"
1 by Martin Pitt Import upstream version 9.1~beta1	13	HREF="index.html"><LINK
	14	REL="UP"
	15	TITLE="Genetic Query Optimizer"
	16	HREF="geqo.html"><LINK
	17	REL="PREVIOUS"
	18	TITLE="Query Handling as a Complex Optimization Problem"
	19	HREF="geqo-intro.html"><LINK
	20	REL="NEXT"
	21	TITLE="Genetic Query Optimization (GEQO) in PostgreSQL"
	22	HREF="geqo-pg-intro.html"><LINK
	23	REL="STYLESHEET"
	24	TYPE="text/css"
	25	HREF="stylesheet.css"><META
	26	HTTP-EQUIV="Content-Type"
	27	CONTENT="text/html; charset=ISO-8859-1"><META
	28	NAME="creation"
1.1.11 by Martin Pitt Import upstream version 9.1.9	29	CONTENT="2013-04-01T18:35:08"></HEAD
1 by Martin Pitt Import upstream version 9.1~beta1	30	><BODY
	31	CLASS="SECT1"
	32	><DIV
	33	CLASS="NAVHEADER"
	34	><TABLE
	35	SUMMARY="Header navigation table"
	36	WIDTH="100%"
	37	BORDER="0"
	38	CELLPADDING="0"
	39	CELLSPACING="0"
	40	><TR
	41	><TH
	42	COLSPAN="5"
	43	ALIGN="center"
	44	VALIGN="bottom"
	45	><A
	46	HREF="index.html"
1.1.11 by Martin Pitt Import upstream version 9.1.9	47	>PostgreSQL 9.1.9 Documentation</A
1 by Martin Pitt Import upstream version 9.1~beta1	48	></TH
	49	></TR
	50	><TR
	51	><TD
	52	WIDTH="10%"
	53	ALIGN="left"
	54	VALIGN="top"
	55	><A
	56	TITLE="Query Handling as a Complex Optimization Problem"
	57	HREF="geqo-intro.html"
	58	ACCESSKEY="P"
	59	>Prev</A
	60	></TD
	61	><TD
	62	WIDTH="10%"
	63	ALIGN="left"
	64	VALIGN="top"
	65	><A
	66	HREF="geqo.html"
1.1.6 by Martin Pitt Import upstream version 9.1.2	67	ACCESSKEY="U"
1.1.6 by Martin Pitt Import upstream version 9.1.2	68	>Up</A
1 by Martin Pitt Import upstream version 9.1~beta1	69	></TD
	70	><TD
	71	WIDTH="60%"
	72	ALIGN="center"
	73	VALIGN="bottom"
	74	>Chapter 51. Genetic Query Optimizer</TD
	75	><TD
1.1.6 by Martin Pitt Import upstream version 9.1.2	76	WIDTH="20%"
1 by Martin Pitt Import upstream version 9.1~beta1	77	ALIGN="right"
	78	VALIGN="top"
	79	><A
	80	TITLE="Genetic Query Optimization (GEQO) in PostgreSQL"
	81	HREF="geqo-pg-intro.html"
	82	ACCESSKEY="N"
	83	>Next</A
	84	></TD
	85	></TR
	86	></TABLE
	87	><HR
	88	ALIGN="LEFT"
	89	WIDTH="100%"></DIV
	90	><DIV
	91	CLASS="SECT1"
	92	><H1
	93	CLASS="SECT1"
	94	><A
	95	NAME="GEQO-INTRO2"
	96	>51.2. Genetic Algorithms</A
	97	></H1
	98	><P
	99	> The genetic algorithm (<ACRONYM
	100	CLASS="ACRONYM"
	101	>GA</ACRONYM
	102	>) is a heuristic optimization method which
	103	operates through randomized search. The set of possible solutions for the
	104	optimization problem is considered as a
	105	<I
	106	CLASS="FIRSTTERM"
	107	>population</I
	108	> of <I
	109	CLASS="FIRSTTERM"
	110	>individuals</I
	111	>.
	112	The degree of adaptation of an individual to its environment is specified
	113	by its <I
	114	CLASS="FIRSTTERM"
	115	>fitness</I
	116	>.
	117	</P
	118	><P
	119	> The coordinates of an individual in the search space are represented
	120	by <I
	121	CLASS="FIRSTTERM"
	122	>chromosomes</I
	123	>, in essence a set of character
	124	strings. A <I
	125	CLASS="FIRSTTERM"
	126	>gene</I
	127	> is a
	128	subsection of a chromosome which encodes the value of a single parameter
	129	being optimized. Typical encodings for a gene could be <I
	130	CLASS="FIRSTTERM"
	131	>binary</I
	132	> or
	133	<I
	134	CLASS="FIRSTTERM"
	135	>integer</I
	136	>.
	137	</P
	138	><P
	139	> Through simulation of the evolutionary operations <I
	140	CLASS="FIRSTTERM"
141	>recombination</I
142	>,
143	<I
144	CLASS="FIRSTTERM"
145	>mutation</I
146	>, and
147	<I
148	CLASS="FIRSTTERM"
149	>selection</I
150	> new generations of search points are found
151	that show a higher average fitness than their ancestors.
152	</P
153	><P
154	> According to the <SPAN
155	CLASS="SYSTEMITEM"
156	>comp.ai.genetic</SPAN
157	> <ACRONYM
158	CLASS="ACRONYM"
159	>FAQ</ACRONYM
160	> it cannot be stressed too
161	strongly that a <ACRONYM
162	CLASS="ACRONYM"
163	>GA</ACRONYM
164	> is not a pure random search for a solution to a
165	problem. A <ACRONYM
166	CLASS="ACRONYM"
167	>GA</ACRONYM
168	> uses stochastic processes, but the result is distinctly
169	non-random (better than random).
170	</P
171	><DIV
172	CLASS="FIGURE"
173	><A
174	NAME="GEQO-DIAGRAM"
175	></A
176	><P
177	><B
178	>Figure 51-1. Structured Diagram of a Genetic Algorithm</B
179	></P
180	><DIV
181	CLASS="INFORMALTABLE"
182	><P
183	></P
184	><A
1.1.11 by Martin Pitt Import upstream version 9.1.9	185	NAME="AEN93857"
1 by Martin Pitt Import upstream version 9.1~beta1	186	></A
	187	><TABLE
	188	BORDER="0"
	189	FRAME="void"
	190	CLASS="CALSTABLE"
	191	><COL><COL><TBODY
	192	><TR
	193	><TD
	194	>P(t)</TD
	195	><TD
	196	>generation of ancestors at a time t</TD
	197	></TR
	198	><TR
	199	><TD
	200	>P''(t)</TD
	201	><TD
	202	>generation of descendants at a time t</TD
	203	></TR
	204	></TBODY
	205	></TABLE
	206	><P
	207	></P
	208	></DIV
	209	><PRE
	210	CLASS="LITERALLAYOUT"
	211	>+=========================================+
	212	\|>>>>>>>>>>> Algorithm GA <<<<<<<<<<<<<<\|
	213	+=========================================+
	214	\| INITIALIZE t := 0 \|
	215	+=========================================+
	216	\| INITIALIZE P(t) \|
	217	+=========================================+
	218	\| evaluate FITNESS of P(t) \|
	219	+=========================================+
	220	\| while not STOPPING CRITERION do \|
	221	\| +-------------------------------------+
	222	\| \| P'(t) := RECOMBINATION{P(t)} \|
	223	\| +-------------------------------------+
	224	\| \| P''(t) := MUTATION{P'(t)} \|
	225	\| +-------------------------------------+
	226	\| \| P(t+1) := SELECTION{P''(t) + P(t)} \|
	227	\| +-------------------------------------+
	228	\| \| evaluate FITNESS of P''(t) \|
	229	\| +-------------------------------------+
	230	\| \| t := t + 1 \|
	231	+===+=====================================+</PRE
	232	></DIV
	233	></DIV
	234	><DIV
	235	CLASS="NAVFOOTER"
	236	><HR
	237	ALIGN="LEFT"
	238	WIDTH="100%"><TABLE
	239	SUMMARY="Footer navigation table"
	240	WIDTH="100%"
	241	BORDER="0"
	242	CELLPADDING="0"
	243	CELLSPACING="0"
	244	><TR
	245	><TD
	246	WIDTH="33%"
	247	ALIGN="left"
	248	VALIGN="top"
	249	><A
250	HREF="geqo-intro.html"
251	ACCESSKEY="P"
252	>Prev</A
253	></TD
254	><TD
255	WIDTH="34%"
256	ALIGN="center"
257	VALIGN="top"
258	><A
259	HREF="index.html"
260	ACCESSKEY="H"
261	>Home</A
262	></TD
263	><TD
264	WIDTH="33%"
265	ALIGN="right"
266	VALIGN="top"
267	><A
268	HREF="geqo-pg-intro.html"
269	ACCESSKEY="N"
270	>Next</A
271	></TD
272	></TR
273	><TR
274	><TD
275	WIDTH="33%"
276	ALIGN="left"
277	VALIGN="top"
278	>Query Handling as a Complex Optimization Problem</TD
279	><TD
280	WIDTH="34%"
281	ALIGN="center"
282	VALIGN="top"
283	><A
284	HREF="geqo.html"
285	ACCESSKEY="U"
286	>Up</A
287	></TD
288	><TD
289	WIDTH="33%"
290	ALIGN="right"
291	VALIGN="top"
292	>Genetic Query Optimization (<ACRONYM
293	CLASS="ACRONYM"
294	>GEQO</ACRONYM
295	>) in PostgreSQL</TD
296	></TR
297	></TABLE
298	></DIV
299	></BODY
300	></HTML
301	>