METODOS NUMERICOS
Páginas: 177 (44111 palabras)
Publicado: 17 de marzo de 2014
ALGORITMOS HEUR´
’ISTICOS
EN
´
BIOINFORMATICA
TESIS DOCTORAL
David Alejandro Pelta
dpelta@ugr.es
DIRECTORES: Jos´ L. Verdegay - Armando Blanco
e
Depto. de Ciencias de la Computaci´n e
o
Inteligencia Artificial.
Universidad de Granada, 18071 Granada
2
´
Indice General
Agradecimientos
7
Introducci´n
o
11
1 Optimizaci´n Combinatoria y Metaheur´
o
ısticas17
1.1
Definiciones Preliminares . . . . . . . . . . . . . . . . . . . . .
18
1.2
Propiedades de las Metaheur´
ısticas . . . . . . . . . . . . . . . .
20
1.3
Ejemplos de Metaheur´
ısticas
22
. . . . . . . . . . . . . . . . . . .
2 FANS: una Heur´
ıstica para Problemas de Optimizaci´n
o
2.1
33
35
2.1.1
El Operador de Modificaci´n . . . . . . . . . . .. . . .
o
36
2.1.2
La Valoraci´n Difusa . . . . . . . . . . . . . . . . . . . .
o
37
2.1.3
El Administrador de Operaci´n . . . . . . . . . . . . . .
o
37
2.1.4
El Administrador de Vecindario . . . . . . . . . . . . . .
38
2.1.5
Par´metros Globales . . . . . . . . . . . . . . . . . . . .
a
39
2.1.6
Manejo de optimos locales . . . . . . . . . . . . .. . . .
39
2.1.7
2.2
Presentaci´n de FANS . . . . . . . . . . . . . . . . . . . . . . .
o
El Algoritmo . . . . . . . . . . . . . . . . . . . . . . . .
41
La Valoraci´n Difusa como Mecanismo de
o
Variaci´n del Comportamiento de FANS . . . . . . . . . . . . .
o
42
2.3
Comentarios Sobre la Implementaci´n . . . . . . . . . . . . . .
o
46
2.4
Utilizaci´n deM´ltiples Operadores
o
u
en el Proceso de B´squeda . . . . . . . . . . . . . . . . . . . . .
u
48
2.4.1
48
“Un Operador, un Landscape” . . . . . . . . . . . . . .
3
´ndice General
I
4
2.4.2
2.5
Justificaci´n Experimental . . . . . . . . . . . . . . . . .
o
52
Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . .
56
3 Verificaci´n Experimentalde FANS
o
3.1
59
61
Implementaci´n de FANS . . . . . . . . . . . . . . . . .
o
62
3.1.3
Descripci´n del Algoritmo Gen´tico . . . . . . . . . . .
o
e
66
Problemas de Mochila Estandard . . . . . . . . . . . . . . . . .
67
3.2.1
Instancias de Prueba
. . . . . . . . . . . . . . . . . . .
67
3.2.2
Experimentos y Resultados . . . . . . . . . . . . . . . .68
Mochila con M´ltiples restricciones . . . . . . . . . . . . . . . .
u
75
3.3.1
Instancias de Prueba . . . . . . . . . . . . . . . . . . . .
75
3.3.2
3.4
Formulaci´n de los Problemas de Mochila . . . . . . . .
o
3.1.2
3.3
60
3.1.1
3.2
FANS vs AG en Problemas de Mochila . . . . . . . . . . . . . .
Experimentos y Resultados . . . . . . . . . . . . . .. .
75
80
Funciones de Prueba . . . . . . . . . . . . . . . . . . . .
80
3.4.2
Implementaci´n de FANS . . . . . . . . . . . . . . . . .
o
81
3.4.3
Experimentos y Resultados . . . . . . . . . . . . . . . .
84
An´lisis Complementarios de FANS . . . . . . . . . . . . . . . .
a
89
3.5.1
An´lisis de la Calidad de las Soluciones Investigadas . .
a
893.5.2
3.6
. . . . . . . . . . . . . .
3.4.1
3.5
Experimentos sobre Funciones Reales
Evaluaci´n de Administradores de Vecindarios . . . . .
o
93
Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . .
99
4 Aplicaci´n de FANS a Problemas de Bioinform´tica
o
a
101
4.1
Conceptos B´sicos . . . . . . . . . . . . . . . . . . . . . . . . . 103
a
4.2El Problema de Predicci´n de Estructura . . . . . . . . . . . . 108
o
4.2.1
4.2.2
4.3
Problemas en la determinaci´n de la estructura . . . . . 110
o
Modelizaciones del Problema . . . . . . . . . . . . . . . 112
El Problema de Comparaci´n de Estructuras . . . . . . . . . . 117
o
4.3.1
Consideraciones Generales . . . . . . . . . . . . . . . . . 118
4.3.2
Comparaci´n de...
’ISTICOS
EN
´
BIOINFORMATICA
TESIS DOCTORAL
David Alejandro Pelta
dpelta@ugr.es
DIRECTORES: Jos´ L. Verdegay - Armando Blanco
e
Depto. de Ciencias de la Computaci´n e
o
Inteligencia Artificial.
Universidad de Granada, 18071 Granada
2
´
Indice General
Agradecimientos
7
Introducci´n
o
11
1 Optimizaci´n Combinatoria y Metaheur´
o
ısticas17
1.1
Definiciones Preliminares . . . . . . . . . . . . . . . . . . . . .
18
1.2
Propiedades de las Metaheur´
ısticas . . . . . . . . . . . . . . . .
20
1.3
Ejemplos de Metaheur´
ısticas
22
. . . . . . . . . . . . . . . . . . .
2 FANS: una Heur´
ıstica para Problemas de Optimizaci´n
o
2.1
33
35
2.1.1
El Operador de Modificaci´n . . . . . . . . . . .. . . .
o
36
2.1.2
La Valoraci´n Difusa . . . . . . . . . . . . . . . . . . . .
o
37
2.1.3
El Administrador de Operaci´n . . . . . . . . . . . . . .
o
37
2.1.4
El Administrador de Vecindario . . . . . . . . . . . . . .
38
2.1.5
Par´metros Globales . . . . . . . . . . . . . . . . . . . .
a
39
2.1.6
Manejo de optimos locales . . . . . . . . . . . . .. . . .
39
2.1.7
2.2
Presentaci´n de FANS . . . . . . . . . . . . . . . . . . . . . . .
o
El Algoritmo . . . . . . . . . . . . . . . . . . . . . . . .
41
La Valoraci´n Difusa como Mecanismo de
o
Variaci´n del Comportamiento de FANS . . . . . . . . . . . . .
o
42
2.3
Comentarios Sobre la Implementaci´n . . . . . . . . . . . . . .
o
46
2.4
Utilizaci´n deM´ltiples Operadores
o
u
en el Proceso de B´squeda . . . . . . . . . . . . . . . . . . . . .
u
48
2.4.1
48
“Un Operador, un Landscape” . . . . . . . . . . . . . .
3
´ndice General
I
4
2.4.2
2.5
Justificaci´n Experimental . . . . . . . . . . . . . . . . .
o
52
Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . .
56
3 Verificaci´n Experimentalde FANS
o
3.1
59
61
Implementaci´n de FANS . . . . . . . . . . . . . . . . .
o
62
3.1.3
Descripci´n del Algoritmo Gen´tico . . . . . . . . . . .
o
e
66
Problemas de Mochila Estandard . . . . . . . . . . . . . . . . .
67
3.2.1
Instancias de Prueba
. . . . . . . . . . . . . . . . . . .
67
3.2.2
Experimentos y Resultados . . . . . . . . . . . . . . . .68
Mochila con M´ltiples restricciones . . . . . . . . . . . . . . . .
u
75
3.3.1
Instancias de Prueba . . . . . . . . . . . . . . . . . . . .
75
3.3.2
3.4
Formulaci´n de los Problemas de Mochila . . . . . . . .
o
3.1.2
3.3
60
3.1.1
3.2
FANS vs AG en Problemas de Mochila . . . . . . . . . . . . . .
Experimentos y Resultados . . . . . . . . . . . . . .. .
75
80
Funciones de Prueba . . . . . . . . . . . . . . . . . . . .
80
3.4.2
Implementaci´n de FANS . . . . . . . . . . . . . . . . .
o
81
3.4.3
Experimentos y Resultados . . . . . . . . . . . . . . . .
84
An´lisis Complementarios de FANS . . . . . . . . . . . . . . . .
a
89
3.5.1
An´lisis de la Calidad de las Soluciones Investigadas . .
a
893.5.2
3.6
. . . . . . . . . . . . . .
3.4.1
3.5
Experimentos sobre Funciones Reales
Evaluaci´n de Administradores de Vecindarios . . . . .
o
93
Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . .
99
4 Aplicaci´n de FANS a Problemas de Bioinform´tica
o
a
101
4.1
Conceptos B´sicos . . . . . . . . . . . . . . . . . . . . . . . . . 103
a
4.2El Problema de Predicci´n de Estructura . . . . . . . . . . . . 108
o
4.2.1
4.2.2
4.3
Problemas en la determinaci´n de la estructura . . . . . 110
o
Modelizaciones del Problema . . . . . . . . . . . . . . . 112
El Problema de Comparaci´n de Estructuras . . . . . . . . . . 117
o
4.3.1
Consideraciones Generales . . . . . . . . . . . . . . . . . 118
4.3.2
Comparaci´n de...
Leer documento completo
Regístrate para leer el documento completo.