inteligencia artificial

UNIVERSIDAD DE OVIEDO
Facultad de Ciencias
Licenciatura en Matem´ticas
a

Algoritmos Evolutivos
para la Resoluci´n de
o

Sistemas de “Word Equations”

´
Fatima Drubi Vega
Trabajo Acad´mico
e
Oviedo, julio de 2003

´
Indice general
1. Introducci´n
o

4

2. Los Algoritmos Gen´ticos
e

6

2.1. Introducci´n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . .
o

6

2.2. Conceptos B´sicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
a

7

2.3. Caracter´
ısticas de los Algoritmos Gen´ticos . . . . . . . . . . . . . . . . . .
e

9

2.4. El Algoritmo Gen´tico Simple . . . . . . . . . . . . . . . . . . . . . . . . . . 10
e
2.4.1. Codificaci´n de los Individuos . . . . . . . . . . . . . . . . . . . . . . 11
o2.4.2. Generaci´n de la Poblaci´n Inicial . . . . . . . . . . . . . . . . . . . 14
o
o
2.4.3. Evaluaci´n de los Individuos . . . . . . . . . . . . . . . . . . . . . . 14
o
2.4.4. Selecci´n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
o
2.4.5. Cruce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.4.6. Mutaci´n . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . 21
o
2.5. Seudoc´digo de un Algoritmo Gen´tico Simple . . . . . . . . . . . . . . . . 22
o
e
2.6. El Teorema de los Esquemas

. . . . . . . . . . . . . . . . . . . . . . . . . . 29

2.7. Otros Algoritmos Gen´ticos: los Algoritmos Evolutivos . . . . . . . . . . . . 34
e
3. El Problema de Satisfactibilidad

36

3.1. Introducci´n . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . 36
o
3.2. Conceptos B´sicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
a
3.3. Los Algoritmos Evolutivos para Resolver SAT . . . . . . . . . . . . . . . . . 39
4. Sistemas de “Word Equations”: el Algoritmo de Makanin

48

4.1. Introducci´n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
o4.2. Conceptos B´sicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
a

1

4.3. El Algoritmo de Makanin . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.3.1. Representaci´n Gr´fica
o
a

. . . . . . . . . . . . . . . . . . . . . . . . . 51

4.3.2. Las Ecuaciones Generalizadas . . . . . . . . . . . . . . . . . . . . . . 55
4.3.3. EL Algoritmo deTransformaci´n . . . . . . . . . . . . . . . . . . . . 60
o
4.4. Casos Particulares de Sistemas de “Word Equations” . . . . . . . . . . . . . 66
5. Un Algoritmo Gen´tico Simple para Resolver l SW ES
e

71

5.1. Introducci´n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
o
5.2. Codificaci´n de los Individuos . . . . . . . . . . . . . . . . . . . . . . . . . . 71
o5.3. Generaci´n de la Poblaci´n Inicial . . . . . . . . . . . . . . . . . . . . . . . 74
o
o
5.4. Evaluaci´n de los Individuos . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
o
5.5. Los Operadores Gen´ticos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
e
6. El Algoritmo Genero Problema

88

7. Primeros Resultados Experimentales

91

7.1. Introducci´n . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
o
7.2. Tama˜o de Poblaci´n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
n
o
7.3. Probabilidad de mutaci´n . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
o
8. Algoritmos Evolutivos para Resolver l SW ES

107

8.1. A.E. S´lo Mutaci´n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .107
o
o
8.2. A.E. B´squeda Local . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
u
8.3. Resultados experimentales . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
9. Experimento final

125

A. El Algoritmo Gen´tico Simple
e

128

B. El Algoritmo Genero Problema

145

C. Los problemas propuestos

157

C.1. El problema 10-15-3 . . . . . . . . . . ....