PDF de programación - Tesis: Maria Margarita Goire - INGENIERÍA ELÉCTRICA CON OPCIÓN DE COMPUTACIÓN

C tK T M DE IMVESTIGACI8N Y I I

ESTUDIOS AVANZADOS BEL

I. P. N.

« I B L I O T E C A
I N G E N IE R IA ELEC TR IC A

CENTRO DE INVESTIGACION Y DE ESTUDIOS AVANZADOS DEL IPN

DEPARTAMENTO DE INGENIERIA ELECTRICA

SECCION DE COMPUTACION

MODELOS CONEXIONISTAS DE DEDUCION Y

APRENDIZAJE AUTOMATICO

TESIS QUE PRESENTA LA LIC. MARIA MARGARITA GOIRE CASTILLA

PARA OBTENER EL GRADO DE

MAESTRA EN CIENCIAS

EN LA ESPECIALIDAD DE:

INGENIERIA ELECTRICA CON OPCION EN COMPUTACION

TESIS DIRIGIDA POR EL DR. GUILLERMO B. MORALES LUNA

CtJ(TII> DE INVESTISACIBN Y I t

ESTUDIOS A VA NZ A DO S SE L

I. P. N.

■ I B L I O T E 1 C A
MEXICO, D. F. NOVIEMBRE DE 1991 ,N G E N |£ R|A E LEC TRICA

"hay. cq&cui, bien &e. &aAe que penaiaten,
que detienen ¿a mueníe cama un muría,
nadie cuibe pon que beben ¿a empuña,
beben ía amanqa, beben </ neAÍ&tenu

Minia dquinne

a u r r ir t de in v e s t ig a c ió n y »i

ESTUDIOS AVANZADOS DEL

I. P. N.

B I B L I O T E C A
'N G E M E R IA E LEC TR IC A

A mis padres Clara y Suitberto
por amarme siempre y dejarme
volar libremente.
A mi tío Daniel, aunque ya no esté
A mis hermanos Suitberto y Andrés
por su inmenso amor.

cwrrw Df WVESTISACUN y lt

Estudios a v a n z a " u n

i- P. N.

B i h L i o t e o a
rN G E N IE R lA E L E C T R IC A

AGRADECIMIENTOS

C O ITR # d e IN VESTISACI»N Y S i

ESTUDIOS A V A N Z A B e s e¡£¡_

I. p. N.

“
' b l i o t e i o a
'N^PNIERIA E L ECTRI CA

Deseo dejar constancia de mi agradecimiento a la Organi­
zación de las Naciones Unidas para la Educación, la Ciencia y
la Cultura (U.N.E.S.C.O.) y al Centro de Investigación y de
Estudios Avanzados del I.P.N., por la posibilidad que me brin­
daron para realizar los estudios de maestría y todo el apoyo
recibido durante el desarrollo de los mismos.

Así mismo quiero agradecer a todo el personal de la
Sección de Computación del Departamento de Ingienería
Eléctrica del C .I.N.V.E.S.T .A.V., su colaboración y su solida­
ridad manifiesta.

En particular, mi más profunda gratitud al Dr. Guillermo
Morales Luna por sus orientaciones, sus valiosos consejos, su
paciencia y la confianza que depositó en mi.

Gratitud infinita a mis compañeros y amigos mexicanos por

su estímulo, su apoyo, su cariño y su solidaridad constantes.

Muchas gracias a mi compañera Patricia Duran y a su

esposo Héctor Teherán, por su ayuda desinteresada.

Especialmente quiero manifestar mi agradecimiento a dos
amigas incondicionales, Isabel Negrete y Eréndira Correa, y a
sus familias, por su apoyo y ayuda, por sus consejos y su
constante estímulo, por todo el cariño demostrado y por creer
en mí.

Un agradecimiento a las instituciones cubanas que hicie­
ron posible mi estancia en México, al Ministerio de Enseñanza
Superior de Cuba (M.E.S), al Instituto Superior Politécnico
Julio Antonio Mella de Santiago de Cuba (I.S .P.J.A.M.) y a la
Comisión Cubana de la U.N.E.S.C.O. Muy especialmente, al
antiguo Departamento de Matemática y Computación del
I.S.P.J.A.M. y al actual Departamento de Informática del mismo
instituto.

Sencillamente gracias, a mis verdaderos compañeros y

amigos cubanos.

INDICE

INTRODUCCION

C t t T M I E INVESTI« HCIIN Y I I

ESTUBIOS AVANZADOS O i l

I. P. N.

B I B L I O T E C A
W G ENIE'R JA E LE C TR IC A

1. INTRODUCCION AL MODELO CONEXIONISTA

1.1. Conexionismo y Redes Neuronales
1.2. Desarrollo Histórico
1.3. Bases del Modelo Conexionista

2. MAQUINAS DE BOLTZMANN

2.1. Formulación Matemática
2.2. Semántica de la Máquina de Boltzmann
2.3. Estrategia para la localización de mínimos
2.4. Reconocimiento de Patrones

3. APRENDIZAJE EN UNA MAQUINA DE BOLTZMANN

3.1. Estrategia de Aprendizaje
3.2. Implementación del Aprendizaje

4. IMPLEMENTACION DEL ALGORITMO DE 'RECOCIDO SIMULADO’

4.1. Introducción al algoritmo
4.2. Algoritmo simulated annealing
4.3. Simulated Annealing en una Máquina de

Boltzmann

4.4. Presentación Técnica de la Implementación
4.5. Pruebas realizadas

5. OPTIMIZACION

5.1 El Problema del Agente Viajero
5.2 Annealing espcífico para el Problema del

del Agente Viajero

5.3. Implementación y Pruebas

CONCLUSIONES

REFERENCIAS

i

4
6
11

17
28
29
32

34
45

54
56

65
68
70

73

77
79

88

INTRODUCCION

C fN TH # DE INVESTIGACION Y I k

ESTUDIOS AYANZADOS B U

I. P. N.

l

i

b

b
INGENIERIA ELECTRICA

i o

c

t

e

a

Los modelos conexionistas de Máquinas de Boltzmann están
siendo estudiados por sus capacidades de procesamiento en
paralelo, por las propiedades interesantes de su algoritmo de
aprendizaje y por constituir una herramienta de optimización.

Nuestro trabajo de tesis está enmarcado precisamente en
este estudio, con el objetivo central de realizar un análisis
del modelo y proponer una implementación del mismo y de su
algoritmo de aprendizaje.

La implementación del algoritmo de optimización recocido
simulado (simulated annealing), integrado a la máquina de
Boltzmann para encontrar los mínimos globales de energía, y
también aplicado a un problema de optimización combinatoria,
es el otro objetivo de este trabajo.

La tesis se desarrolla en dos de las vertientes de estu­
dio de la máquina de Boltzmann, su algoritmo de aprendizaje y
su potencialidad como técnica de optimización combinatoria,
cuyos puntos a destacar son los siguientes:

- Análisis de las habilidades de aprendizaje de la máquina de

Boltzamnn.

- Análisis del algoritmo simulated annealing integrado a la
máquina, y de sus parámetros de control, como algoritmo de
minimización de energía.

- Análisis de la máquina de Boltzmann como máquina de minimi­
zación de energía, y en general como herramienta de optimi­
zación.

1

El trabajo está estructurado en cinco capítulos que abor­
dan los aspectos planteados anteriormente, y cuyas temáticas
expondremos a continuación.

El primer capítulo, "Introducción al Modelo Conexionis-
ta", introductorio sirve para ubicar a la tesis desde el punto
de vista histórico y temático.

El segundo capítulo, "Máquinas de Boltzmann", presenta la
formulación matemática del modelo con nuestra propuesta para
realizar las transiciones de estados en la máquina, que define
la estrategia a seguir para la localización de mínimos; aspec­
to de particular importancia para lograr soluciones cercanas
al óptimo. El capitulo finaliza con la explicación de como se
realizará el reconocimiento de patrones en nuestra implemen-
tación de la máquina de Boltzmann.

El tercer capítulo, "Aprendizaje en una Máquina de Boltz­
mann", trata el tema del aprendizaje del modelo y proponemos
nuestra variante para que la red aprenda. También se exponen
los detalles de nuestra implementación del algoritmo de apren­
dizaje y las pruebas realizadas para resolver el problema del
XOR, es decir, el entrenamiento a que fue sometida la red para
que aprenda el problema planteado.

Nuestra implementación del annealing para la máquina de
Boltzamnn, utilizando como función de aceptación la función
estandar del simulated annealing constituye un aspecto rele­
vante del capítulo cuatro, "Instrumentación del algoritmo de
recocido simulado"- Se incluyen además, el análisis y la se­
lección de los parámetros de la programación del recocido
(annealing schedule) para el algoritmo de optimización.

El capítulo cinco "Optimización", está dedicado a la
resolución del Problema del Agente Viajero, que es un conocido

2

problema de Optimización Combinatoria, aplicando el algoritmo
simulated annealing. Aparecen las pruebas realizadas y una
comparación de los resultados alcanzados con la solución exac­
ta para un ejemplo de 42 ciudades y para un ejemplo de 12
ciudades.

Los alcances de este trabajo de tesis pueden ser resumi­
dos en tres aspectos fundamentales que se enumeran a
continuación :

1 ANNEALING PARA LA MAQUINA DE BOLTZMANN
Para lograr esta implementación, enfatizamos los siguien­

tes puntos, por considearlos importantes:

1.1.- Estrategia de búsqueda para visitar las confi­

1.2.- Localización de los mínimos

locales

por

guraciones vecinas.

configuraciones vecinas.

1.3.- Generación de configuraciones aleatorias para

1.4.- Realización de pruebas sobre las modifica­

pasar a otro mínimo.

ciones planteadas.

2 ALGORITMO DE APRENDIZAJE DE LA MAQUINA DE BOLTZMANN

2.1.- Aplicación del annealing definido anterior­

mente .

2.2.- Reconocimiento patrones por completamiento.

3 OPTIMIZACION

3.1.- Annealing y el problema del Agente Viajero.
3.2.- Annealing schedule para el Agente Viajero.

Todas las implementaciones y programas fueron desarrolla
dos en el lenguaje de programación C, con el compilador Turbo
C, versión 2.0 de Borland y en C standard de la ANSI.

3

CAPITULO 1
INTRODUCCION AL MODELO CQNEXIONISTA

1.1 CONEXIONISMO Y REDES NEURONALES

La integración de los procesos de percepción e inducción
con el conocimiento, es una de las principales dificultades
para los diseñadores de sistemas inteligentes. Los esquemas de
procesamiento de información parecen ajenos a las operaciones
que se realizan a bajo nivel para traducir entradas sensoria­
les a descripciones simbólicas, o a las características de
flexibilidad y repetición de la adquisición de conocimiento.
Los métodos del Conexionismo constituyen un enfoque para mode­
lar el conocimiento que brinda una prometedora alternativa