Optimizacion-binaria-con-redes-neuronales-de-Hopfield-asimetricas

Vista previa del material en texto

Universidad Nacional Autónoma de México
Facultad de Ciencias
Optimización Binaria con Redes Neuronales
de Hopfield Asimétricas
T E S I S
QUE PARA OBTENER EL TÍTULO DE:
FÍSICO
PRESENTA:
ALDO MORA SÁNCHEZ
DIRECTOR DE TESIS:
DR. PEDRO EDUARDO MIRAMONTES VIDAL
2011
 
UNAM – Dirección General de Bibliotecas 
Tesis Digitales 
Restricciones de uso 
 
DERECHOS RESERVADOS © 
PROHIBIDA SU REPRODUCCIÓN TOTAL O PARCIAL 
 
Todo el material contenido en esta tesis esta protegido por la Ley Federal 
del Derecho de Autor (LFDA) de los Estados Unidos Mexicanos (México). 
El uso de imágenes, fragmentos de videos, y demás material que sea 
objeto de protección de los derechos de autor, será exclusivamente para 
fines educativos e informativos y deberá citar la fuente donde la obtuvo 
mencionando el autor o autores. Cualquier uso distinto como el lucro, 
reproducción, edición o modificación, será perseguido y sancionado por el 
respectivo titular de los Derechos de Autor. 
 
 
 
2
Datos del alumno
Apellido paterno: Mora
Apellido materno: Sánchez
Nombre: Aldo
Teléfono: 57547423
Universidad: Universidad Nacional Autónoma de México
Facultad: Facultad de Ciencias
Carrera: F́ısica
Número de cuenta: 300133257
Datos del tutor
Grado: Dr
Nombres: Pedro Eduardo
Apellido paterno: Miramontes
Apellido materno: Vidal
Datos del sinodal 1
Grado: Dr
Nombre: Germinal
Apellido paterno: Cocho
Apellido materno: Gil
Datos del sinodal 2
Grado: Dr
Nombre: Pablo
Apellido paterno: Padilla
Apellido materno: Longoria
Datos del sinodal 3
Grado: Dr
Nombres: David Philipp
Apellido paterno: Sanders
Datos del sinodal 4
Grado: Dr
Nombre: Fernando
Apellido paterno: Ramı́rez
Apellido materno: Alatriste
Datos del trabajo escrito
T́ıtulo: Optimización binaria con redes
neuronales de Hopfield asimétricas
Número de páginas: 62
Año: 2011
3
A mi familia, amigos y maestros, porque sin ellos todo hubiera sido muy
complicado o completamente inútil.
Índice general
Índice general 5
1. Introducción 7
2. Optimización Combinatoria 9
2.1. Algoritmos: eficiencia y complejidad . . . . . . . . . . . . . . . . 11
2.1.1. Clases de Complejidad . . . . . . . . . . . . . . . . . . . . 12
2.2. Recocido Simulado . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3. Gráficas 17
3.1. Definiciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4. Redes Neuronales 21
4.1. Fundamentos Biológicos . . . . . . . . . . . . . . . . . . . . . . . 21
4.2. Redes neuronales artificiales . . . . . . . . . . . . . . . . . . . . . 23
4.2.1. Funciones de Activación . . . . . . . . . . . . . . . . . . . 27
4.2.2. Topoloǵıas de redes neuronales . . . . . . . . . . . . . . . 29
4.3. Redes de Hopfield . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.3.1. Enerǵıa . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.3.2. Forma de la función objetivo y condiciones de estabilidad 34
4.4. Consecuencias de quitar las restricciones de los pesos. . . . . . . 35
5. Ruta más corta en una gráfica 37
5.1. Implementación . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
6. Resultados 43
6.1. Resultados utilizando el algoritmo original . . . . . . . . . . . . . 43
6.2. Modificación al algoritmo original . . . . . . . . . . . . . . . . . . 49
6.3. Resultados de la aplicación de la modificación . . . . . . . . . . . 52
7. Conclusiones 59
Bibliograf́ıa 61
5
Caṕıtulo 1
Introducción
En este documento se abordará un problema de optimización binaria
proponiendo una modificación al algoritmo de Hopfield para redes neuronales
artificiales. Se expondrá, de forma razonablemente autocontenida, el problema
de la optimización binaria tomando como caso particular la búsqueda de la
ruta más corta en una gráfica. Se observará que bajo el algoritmo de Hopfield
el problema no se puede codificar de manera estable, se estudiará brevemente
la dinámica, aparentemente caótica, del sistema que representa al problema y
finalmente se hará una modificación a la regla de actualización, esto con el
fin de conseguir estabilidad en el sistema y con ello una solución. La solución
óptima en el esquema de Hopfiled es codificada como el mı́nimo global de una
función binaria, por lo que al algoritmo de Hopfield se le adecuará el del recocido
simulado, para evitar mı́nimos locales que podŕıan, como se mostrará, significar
estados que no cumplen con las caracteŕısticas de una solución, y claramente
tampoco con las de la solución optima.
Las redes neuronales son modelos de aprendizaje automático basados en la
forma en que se cree que funciona el sistema nervioso, están constituidas por
un conjunto de unidades interconectadas que reciben como entrada una suma
pesada de valores provenientes de las demás y producen una salida, que a su vez
puede ser tomada por ellas. Las redes neuronales de Hopfield [1] son utilizadas
para la optimización de funciones, en su forma original mediante una dinámica
análoga a un proceso f́ısico real toman como entrada un vector binario y lo van
transformando de forma que se minimice una función objetivo llamada enerǵıa.
La salida es entonces un vector con la propiedad de que al ser evaluado en la
función objetivo, el resultado es siempre menor al que daŕıa la evaluación del
vector original. Este algoritmo presenta tres limitantes:
1. Al actualizarse sólo admite cambios en el vector de entrada que minimicen
la función, por lo que si el estado inicial no es cercano al mı́nimo global,
el estado final será en el mejor de los casos un mı́nimo local.
2. Se basa en modelos de Ising, por lo que la enerǵıa debe poder escribirse
como una suma de términos constantes, lineales y a lo más cuadráticos.
3. Para garantizar un cambio negativo en la enerǵıa en cada actualización
del sistema, la matriz de coeficientes de términos cuadráticos debe ser
7
8 CAPÍTULO 1. INTRODUCCIÓN
simétrica y de elementos nulos en la diagonal.
En la literatura se encuentra, referente al primer punto, el algoritmo de
“recocido simulado”(simulated annealing) [2] basado a su vez en el algoritmo
de Metropolis. Dicho algoritmo agrega una pseudotemperatura al modelo, ésta
desciende gradualmente simulando el proceso de recocido de los metales. La
probabilidad de aceptar un cambio positivo en la enerǵıa está dada por una
distribución de Boltzmann, por lo que a muy altas temperaturas se tiene un
medio de probabilidad de aceptar un cambio positivo, y a temperatura cero el
algoritmo se reduce al original permitiendo sólo cambios negativos. Con esto es
posible explorar el espacio de soluciones escapando de mı́nimos locales a altas
temperaturas, y descendiendo en la enerǵıa al bajar la temperatura. En este
trabajo se combinan ambos algoritmos, el de Hopfield y el de recocido simulado.
Sobre el segundo punto, se sabe que toda función binaria se puede escribir de
forma tal que sea la suma de términos lineales, cuadráticos, cúbicos, etcétera. El
modelo de Hopfield incluye hasta términos cuadráticos, se comentará la forma
de extender dicho modelo, sin embargo no se tratará aqúı.
Finalmente sobre el tercer punto, en la literatura se discute la dinámica de
redes de Hopfield al violar el requerimiento de simetŕıa y elementos nulos en la
diagonal, se estudia por ejemplo el caos que se presenta bajo ciertos parámetros,
sin embargo en el presente texto se propondrá una modificación a la regla de
actualización que le da estabilidad al sistema, garantizando una disminución
de la enerǵıa independientemente de la forma de la matriz de coeficientes de
interacciones cuadráticas. Aśı, para controlar los saltos en la enerǵıa basta con
variar la temperatura, de no darse esta estabilidad incluso a bajas temperaturas
tendŕıamos un comportamiento caótico sin la posibilidad, en la mayoŕıa de los
casos, de encontrar un mı́nimo.
Este primer caṕıtulo es una breve introducción, en el segundo caṕıtulo
se escribirá sobre la optimización combinatoria, definiciones,algoritmos para
resolver problemas de este tipo y la complejidad de los mismos. Se describirá en
particular el algoritmo del recocido simulado, que es un método estocástico
y metaheuŕıstico utilizado en problemas de optimización combinatiora. El
tercer caṕıtulo es sobre gráficas, incluye un poco de historia, definiciones
y tipos de gráficas. En el cuarto caṕıtulo se describirán de forma general
las redes neuronales y de forma particular las de Hopfield. Se incluyen
fundamentos bioógicos de las mismas y caracteŕısticas como topoloǵıa, funciones
de activación, etcétera. En el quinto se planteará el problema de encontrar la
ruta más corta en una gráfica, y se describirá en términos de redes de Hopfield,
modificando el algoritmo original para adecuarlo a problemas más generales.
En el sexto caṕıtulo se presentarán los resultados, y finalmente en el séptimo
conclusiones y futuras ĺıneas de investigación.
Caṕıtulo 2
Optimización Combinatoria
Un problema discreto de optimización consiste en encontrar el valor óptimo
de una función real, llamada función objetivo, dentro de un conjunto finito
de soluciones factibles. A veces dado un conjunto base E, el conjunto de
soluciones factibles se puede expresar [3] de manera natural como 2E , el conjunto
de subconjuntos de E, en este caso se le llama problema de optimización
combinatoria.
Conociendo la función objetivo, dado que el conjunto de soluciones factibles
es finito, resulta muy sencillo elaborar un algoritmo que pruebe cada una
de las soluciones y encuentre la que optimice la función. Sin embargo en la
práctica, debido a la naturaleza del conjunto de soluciones, que puede crecer
exponencialmente al variar el tamaño del problema, un algoritmo de este estilo
usualmente requiere un tiempo de cómputo exponencial en función del tamaño
de la entrada. Estos conceptos se definirán formalmente más adelante.
La optimización matemática trata, en general, de resolver el siguiente
problema:
min(f(x))
con las restricciones:
gi(x) ≥ 0 i = 1, ...,m
hj(x) = 0 j = 1, ..., p
Con f , gi y hj funciones generales de la variable x ∈ Rn. El vector
x representa variables de decisión y la función f , llamada función objetivo,
evalúa la calidad de las decisiones. Las m restricciones del primer tipo y las
p restricciones del segundo tipo determinan el subconjunto del dominio de
donde se toman las soluciones posibles. A los problemas que involucran variables
discretas se les llama de optimización combinatoria.
A continuación se darán algunas definiciones formales sobre problemas de
optimización combinatoria:
Definición 1 (Instancia) Una instancia de un problema de optimización es
un par (C,f), donde C es el conjunto de soluciones factibles y f un mapeo
f : C → R
9
10 CAPÍTULO 2. OPTIMIZACIÓN COMBINATORIA
llamado función objetivo. El problema es encontrar
c ∈ C | f(c) ≤ f(y) ∀ y ∈ C
El punto c es llamado una solución global a la instancia.
Definición 2 Un problema de optimización es un conjunto I de instancias.
Informalmente podemos describir a una instancia como un problema par-
ticular con valores fijos de entrada, es decir con la información necesaria para
encontrar una solución. Un problema es la abstracción obtenida de los elementos
en común entre varias instancias.
Un problema clásico es el del agente viajero. Se tiene una colección de puntos,
y el problema es encontrar una ruta que empezando y terminando en el mismo
lugar pase sólo una vez por cada punto y los recorra todos. Una instancia del
problema seŕıa una matriz particular de distancias entre puntos.
Definición 3 (Vecindad) Dado un problema de optimización con instancias
(C, f), una vecindad es un mapeo:
N : C → 2C
Una vecindad es el conjunto N(c) de puntos cercanos a c, si C = Rn, la
distancia euclidiana proporciona una forma natural de definir una vecindad,
como el conjunto de puntos a menos de cierto valor fijo.
Definición 4 (Óptimo Local) Dada una instancia (C, f) y una vecindad N ,
una solución c es llamada óptimo local con respecto a N , o simplemente óptimo
local cuando no hay necesidad de especificar N , si:
f(c) ≤ f(g) ∀ g ∈ N(c)
Definición 5 (Óptimo Global) Si independientemente de N , c es un ópti-
mo local, entonces c es un óptimo global.
Para resolver sistemáticamente instancias de un problema, se definen
secuencias de operaciones llamadas algoritmos.
Como ya se mencionó, debido a que el conjunto de posibles soluciones es
finito, el procedimiento más intuitivo es realizar una búsqueda exhaustiva, sin
embargo como también ya se comentó esto es ineficiente. Otro método consiste
en hacer una búsqueda al azar, de esta forma si fuera totalmente impráctico
recorrer todo el espacio de soluciones al menos se aumenta la región del mismo en
la que se haŕıa la búsqueda, evitando en lo posible tomar una muestra demasiado
sesgada, sin embargo esto tampoco hace gran diferencia. Entre los métodos más
populares, se ha buscado en la naturaleza inspiración para resolver problemas de
optimización combinatoria. Puede ser en procesos f́ısicos, como la búsqueda de
la configuración de menor enerǵıa en un sistema de átomos, o procesos biológicos
2.1. ALGORITMOS: EFICIENCIA Y COMPLEJIDAD 11
como la evolución o la “inteligencia de enjambre”, estos algoritmos suelen ser
metaheuŕısticos. A pesar de que la naturaleza discreta de estos problemas impide
utilizar herramientas anaĺıticas y por lo tanto exactas, a veces puede hacerse
una versión continua del problema, pero esta involucra resolución de ecuaciones
simultáneas, algebraicas o diferenciales, que además de tener también algoritmos
poco eficientes al final es muy probable que se requiera una discretización de
las ecuaciones para su solución, regresando al problema de la imposibilidad de
utilizar métodos anaĺıticos exactos.
2.1. Algoritmos: eficiencia y complejidad
Un algoritmo es una técnica para resolver una instancia de un problema.
Según [5], un algoritmo debe ser:
1. Finito en su descripción.
2. Factible, en cada uno de sus pasos.
3. Terminable, después de un número finito de pasos.
4. Determinista, por ser una secuencia preestablecida de pasos definidos,
aunque puede tener una componente probabiĺıstica.
La complejidad se encarga de estudiar el tiempo y espacio en memoria que
requiere un algoritmo en función del tamaño de la entrada. Es deseable que el
algoritmo sea eficiente, teóricamente un algoritmo es eficiente si el tiempo de
cómputo requerido para resolver instancias del problema está acotado por un
polinomio en función del número de bits necesarios para codificar el problema.
Como se puede leer en [7], Alan Cobham y Jack Edmonds, comenzaron a llamar
eficientes a los algoritmos que corren en tiempo polinomial.
Como los factores constantes son irrelevantes no interesa la implementación
de un algoritmo en un modelo computacional particular, simplemente se cuenta
la cantidad de pasos elementales requeridos. Un paso elemental puede ser una
operación aritmética, la verificación de una condición, la asignación de una
variable, etcétera.
Un algoritmo tiene como entrada una lista de números, un número entero a se
puede almacenar en binario con una cantidad de bits del orden de O(log(|a|+2)).
El número de bits necesarios para almacenar un racional es la suma de los bits
necesarios para almacenar el numerador y el denominador. El tamaño de una
entrada x, tam(x), es el número total de bits necesarios para almacenarla. El
espacio requerido para almacenar un irracional no se tratará aqúı, ya que sólo
se desea esbozar el concepto de complejidad.
Definición 6 (Complejidad Computacional) Sea A un algoritmo que acep-
ta entradas de un conjunto X, y sea f : N → R+. Si existe una constante
α > 0 tal que A termina su cómputo después de al menos αf(tam(x)) pasos
elementales para cada x ∈ X, se dice que A corre en tiempo O(f), también se
dice que la complejidad de A es O(f)
12 CAPÍTULO 2. OPTIMIZACIÓNCOMBINATORIA
En [7] se comparan tiempos de ejecución hipotéticos para algoritmos con
un número de pasos 100nlog(n), 10n2, n3,5, nlog(n), y n!. El logaritmo es base
2 y se considera que un paso elemental toma un nanosegundo. En ese orden,
para n = 10 tenemos tiempos de 3µs, 1µs, 3µs, 2µs, 1µs y 4µs, sin embargo si
simplemente triplicamos n, obtenemos, en el mismo orden, un tiempo de 15µs,
9µs, 148µs, 20µs, 1s y 8 × 1015 años. Para una entrada 10 veces mayor a la
original, es decir de n = 100, si el tiempo es 2n, el algoritmo tardaŕıa bajo las
condiciones especificadas 4× 1013 años.
La eficiencia teórica presenta algunos problemas, por ejemplo es una teoŕıa
del peor escenario. Se considera f de tal forma que f(n) sea máximo para
una instancia de entrada n, esto puede ser una medida pesimista si el peor
escenario ocurre raramente, en la práctica las instancias pueden estar lejos de
este. Por otro lado el orden del polinomio puede ser muy alto, con lo que existe
la posibilidad de que en el rango del problema se presente un comportamiento
similar al exponencial.
Los problemas se separan en grupos llamados clases de complejidad, estas
categoŕıas reúnen problemas con eficiencia teórica similar. Para esta clasificación
se considera el peor escenario del mejor de los algoritmos, con lo que se consigue
un justo balance que permite transmitir lo que intuitivamente podŕıamos llamar
dificultad de un problema particular, incluso a quien no esté familiarizado con él.
Hablar de la complejidad de un problema y no de un algoritmo es probablemente
un abuso, sin embargo esto se justifica al tomar el mejor algoritmo conocido, de
todas formas es importante tener en mente que aunque se hable de la pertenencia
de un problema a una clase, esto es un atributo de su mejor algoritmo conocido
y no algo inherente al problema mismo, por lo que este puede considerarse
perteneciente a otra clase de encontrarse un algoritmo mejor.
2.1.1. Clases de Complejidad
En este contexto una clase es un conjunto de problemas que pueden ser
resueltos por una máquina abstracta M en un tiempo O(f(n)), donde n es el
tamaño de la entrada.
Un problema de decisión es uno que admite como respuesta śı o no, y cada
problema de optimización se puede reformular como un problema de decisión,
por lo que usualmente la clase de complejidad a la que pertenecen los problemas
de optimización se plantea en términos de problemas de decisión.
Como indica [6], a la clase de problemas de decisión que pueden ser resueltos
en tiempo polinomial se les llama P . Los problemas de decisión cuya respuesta
afirmativa puede ser verificada en tiempo polinomial se conocen como NP , de
non-deterministic polinomial. Los problemas para los que una respuesta negativa
puede ser verificada en tiempo polinomial se conocen como Co − NP , por ser
el conjunto complemento de NP .
P está contenido en la intersección de NP y Co−NP , ya que obviamente si
existe un algoritmo polinomial, este nos proporciona una respuesta afirmativa
2.2. RECOCIDO SIMULADO 13
o negativa en tiempo polinomial, sin embargo es importante hacer la distinción
entre NP y Co−NP ya que puede existir una forma de verificar una respuesta
positiva sin que tengamos forma de saber lo contrario, y viceversa. Mas aún, hay
que enfatizar que no es claro todav́ıa si un elemento de NP está necesariamente
en P o en Co − NP , como ejemplo está el hecho de que no se conoce ningún
algoritmo polinomial para el problema del agente viajero, aunque exista forma
de verificar una respuesta positiva en tiempo polinomial y no se conozca un
algoritmo polinomial para verificar una respuesta negativa. Debido a lo anterior
una pregunta importante sigue siendo la posible igualdad entre P y NP o NP
y Co − NP . Hasta ahora se cree que hay buenas razones para considerar que
P 6= NP y NP 6= Co−NP .
Los problemas de optimización en los que el espacio de soluciones vaŕıa
exponencialmente con el tamaño de la entrada están contenidos en NP . Dentro
de NP existe un subconjunto, llamado NP -completo, que contiene problemas
que de encontrarse un algoritmo polinomial se demostraŕıa que P = NP , ya que
estos problemas pueden ser transformados en tiempo polinomial en los demás
elementos de NP . El problema del agente viajero es un ejemplo de problema
NP -completo.
Un ejemplo de algoritmo a utilizar en un problema de optimización
combinatoria es el del recocido simulado, que será explicado en la siguiente
sección.
2.2. Recocido Simulado
En [2] se propone utilizar el algoritmo de Metropolis, esto es la utilización de
herramientas de f́ısica estad́ıstica, para problemas de optimización combinatoria.
La mecánica estad́ıstica es un conjunto de métodos para analizar las
propiedades de una colección grande de átomos, como en la mayoŕıa de los
materiales con los que interactuamos estos están presentes en cantidades del
orden de 1023 por cent́ımetro cúbico, sólo se observa experimentalmente a
una temperatura dada, la configuración más probable cuando el sistema se
encuentra en equilibrio térmico. Para esto Josiah Willard Gibbs introdujo como
herramienta teórica un ensamble de part́ıculas idénticas sobre el cual se calculan
valores promedio y fluctuaciones de ellos.
La configuración del sistema se especifica dando las posiciones {ri} de cada
una de las part́ıculas, y estas son pesadas por su factor de Boltzmann e
−E({ri})kBT
donde E es la enerǵıa, kB es la constante de Boltzmann y T es la temperatura.
En esta distribución, al bajar la temperatura el pico se va haciendo más angosto
y se recorre a la izquierda, lo que significa que a bajas temperaturas dominan
los estados base como se muestra en la figura 2.1 1.
1http://commons.wikimedia.org/wiki/File:Maxwell-Boltzmann distributionPDF.png
14 CAPÍTULO 2. OPTIMIZACIÓN COMBINATORIA
Figura 2.1: Una distribución de Boltzmann para tres temperaturas, el eje x
representa la enerǵıa y el eje y la fracción de elementos con dicha enerǵıa.
Como ejemplo se puede tomar una cadena de i átomos, con la posibilidad de
apuntar sólo en dos direcciones, a cuyos estados se les denotará µi = ±1. A altas
temperaturas cada átomo tiene la misma probabilidad de encontrarse en cada
estado, por lo que se tiene una distribución binomial, con valores para la enerǵıa
máximo y mı́nimo de ±NJ, y valor más probable de 0. Los valores máximo y
mı́nimo bajo esta distribución son altamente improbables, la enerǵıa cero tiene
un peso estad́ıstico eNJ mayor. Sin embargo al bajar la temperatura, como en el
sistema hay menos fluctuaciones el estado base se vuelve cada vez más probable.
En la práctica sin embargo se ha encontrado que las bajas temperaturas no
son suficientes para garantizar el estado base. Se ha observado por ejemplo en
el proceso de recocido en metales, que si los cambios no son cuasiestáticos y
se permite que el sistema esté fuera de equilibrio, el material tendrá muchas
imperfecciones y se encontrará en un estado metaestable, un optimo local. Por
ello la técnica utilizada consiste en fundir el metal, y luego ir descendiendo
gradualmente la temperatura, pasando mucho tiempo en temperaturas cercanas
al mı́nimo. El algoritmo de recocido simulado se basa en esta técnica, definiendo
una pseudotemperatura para el sistema que funcione de tal forma que el sistema
obedezca una distribución de Boltzmann.
Para asignar en el modelo esta temperatura efectiva hay que observar las
analoǵıas entre ambos sistemas. El proceso de mejora con las iteraciones en
la optimización combinatoria es similar al reordenamiento microscópico en los
materiales, teniendo claramente la función objetivo el papel de la enerǵıa. Sin
embargo si sólo admitimos cambios en la configuración que minimicen la enerǵıa
2.2. RECOCIDO SIMULADO 15
es equivalente a bajar rápidamente a temperatura cero, por lo que las soluciones
obtenidas son metaestables.
Desde el punto de vista geométrico, debemos recordar que la hipersuperficie
de la función objetivo de un problemade optimización tiene frecuentemente
gran cantidad de picos y valles, si estamos cerca de un mı́nimo local, cualquier
algoritmo que permita únicamente un descenso nos llevará irremediablemente a
él sin la posibilidad de salir.
Con el algoritmo de Metropolis se incorporan saltos controlados en la función
objetivo, disminuyendo en altura al descender la temperatura. El algoritmo es
el siguiente:
1. Se toma un elemento del sistema y se cambia ligeramente su configuración
de forma aleatoria
2. Se calcula el cambio en la enerǵıa y si este es negativo la configuración
nueva se acepta, si el cambio es positivo se acepta con probabilidad
P (∆E) = e
−∆E
kBT .
3. Se baja la temperatura, si esta sigue siendo mayor que cero, se repite desde
el primer paso
Aśı, el sistema adquiere una distribución de Boltzmann y la analoǵıa es útil.
El valor T no tiene nada que ver con una temperatura real de algún elemento
del problema, es sólo un parámetro que se hace disminuir gradualmente para
aprovechar las predicciones de la mecánica estad́ıstica.
En resumen, el recocido simulado es un método que permite saltos en la
función objetivo que van disminuyendo en magnitud al transcurrir el tiempo, a
efecto de tratar de evitar mı́nimos locales.
Algunos problemas de optimización combinatoria aparecen de forma natural
al tratar con gráficas, que serán definidas en la siguiente sección. Por un lado,
en ellas una de las caracteŕısticas más importantes es la conectividad, atributo
que se puede representar con un valor binario. Y por otro, se ha hablado ya
de problemas que presentan variación exponencial del tamaño del espacio de
solución en función del tamaño de la entrada, y es de esta forma también que
aumentan las posibilidades de conexión de una gráfica al aumentar los nodos.
Caṕıtulo 3
Gráficas
La teoŕıa de gráficas se remonta a 1736, año en que Euler resolvió el problema
de los siete puentes de Königsberg (ahora Kaliningrado, el enclave ruso en el
Báltico). La ciudad teńıa cuatro porciones de tierra conectadas por siete puentes
como se muestra en la figura 3.1 1.
Este problema, bastante conocido en la época, consist́ıa en encontrar una
ruta por las cuatro porciones de tierra cruzando una y sólo una vez cada puente.
Euler probó que no exist́ıa tal ruta con un método que sentó las bases de la teoŕıa
de gráficas. Este problema se diferenćıa del del Agente Viajero previamente
comentado en que en este caso lo que se debe visitar una sola vez es cada
puente y no cada porción de la ciudad.
Haciendo una abstracción de la ciudad, le asignó a cada porción de tierra
un nodo o vértice, y unió dos de ellas si exist́ıa un puente que las conectaba. El
objeto resultante, con 4 nodos y 7 aristas se muestra en la figura 3.2 2.
Euler dio las condiciones necesarias y suficientes para que una gráfica
cualquiera admita una ruta como la descrita.
3.1. Definiciones
Definición 7 (gráfica) Una gráfica es un par G = (N,A) que consiste en un
conjunto no vaćıo N y un conjunto A de subconjuntos de dos elementos de N. Los
elementos de N son llamados nodos. Sean b, c ∈ N , un elemento a = {b, c} ∈ A
es una arista con vértices b y c. Se dice que b y c son incidentes con a, y que
ambos son adyacentes o vecinos entre ellos, se escribe a=bc.
Una gráfica dirigida o digráfica es una en la que los pares {b, c} son pares
ordenados, es decir las aristas tienen una direccionalidad.
1http://mosaicos.50webs.com/puenteskonigsberg.html
2tomada de http://media.texample.net/tikz/examples/PNG/bridges-of-konigsberg.png
17
18 CAPÍTULO 3. GRÁFICAS
Figura 3.1: Los puentes de Königsberg
Figura 3.2: Gráfica resultante de la abstracción de los puentes y la ciudad.
3.1. DEFINICIONES 19
Figura 3.3: Gráfica totalmente conectada
Como ejemplo podemos describir dos tipos importantes, en primer lugar la
gráfica completa Kn con n vértices (|V | = n), y A compuesto por todos los
subconjuntos de dos elementos de V . Es decir una gráfica en la que cada nodo
está conectado con todos los demás, como se muestra en la figura 3.3 3.
Además tenemos la gráfica bipartita completa Km,n, que tiene por conjunto
de nodos la unión disjunta del conjunto V1 de m elementos y el conjunto V2 de
n elementos, y por aristas todos los conjuntos {a, b} con a ∈ V1 y b ∈ V2. En
otras palabras se tienen dos grupos de nodos, y cada nodo se une con los nodos
del otro grupo como se observa en la figura 3.4 4.
La teoŕıa de gráficas estudia casos en los que la conectividad es la
principal caracteŕıstica del problema, aśı que las aristas pueden ser dibujadas
de forma arbitraria, siendo irrelevantes sus tamaños, intersecciones o ubicación
geométrica, al igual que la de los nodos.
Ahora definiremos algunos conceptos: Sea (a1, a2, ..., an) una secuencia de
aristas en una gráfica, si existen nodos b1, ..., bn+1 tales que ai = bibi+1 para
i = 1, ..., n la secuencia es llamada un camino, si b1 = bn+1 es un camino
cerrado. Un camino para el que todas las aristas son diferentes es un camino
simple, y si además b1 = bn+1 es un camino simple cerrado. Una ruta es un
camino simple en el que además todos los vértices son distintos. Un camino
3tomada de http://altermundus.com/downloads/examples/graph/Complet-16.png
4tomada de http://www.sagenb.org/home/pub/670/cells/11/sage0.png
20 CAPÍTULO 3. GRÁFICAS
Figura 3.4: Gráfica bipartita
simple cerrado con n ≥ 3 para el que todos los nodos son diferentes exceptuando
el primero y el último se llama ciclo. En cualquiera de los casos b1 es el nodo
inicial, bn+1 es el nodo final y n es la longitud.
Definición 8 (Matriz de adyacencia) Si el conjunto N de nodos tiene n
elementos, la matriz de adyacencia asociada es la matriz cuadrada de n x n con
elementos nulos excepto en las entradas i, j tales que existe una arista entre el
nodo i y el nodo j de la gráfica, en este caso la entrada de la matriz será 1. Si
la arista es un bucle en una gráfica no dirigida, entonces la entrada de la matriz
será 2.
Las gráficas pueden ser utilizadas para representar redes neuronales, el
siguiente caṕıtulo trata de su descripción.
Caṕıtulo 4
Redes Neuronales
4.1. Fundamentos Biológicos
El sistema nervioso humano puede verse como una caja negra que funciona a
tres niveles, como una computadora convencional, recibe información del medio,
la procesa, y toma decisiones en función de esto, sin embargo además de lo
anterior existe retroalimentación, por lo que somos capaces de aprender.
Las neuronas son células con alta excitabilidad en la membrana, se espe-
cializan en recibir y conducir impulsos nerviosos. Respecto a su morfoloǵıa,
constan de un cuerpo principal llamado soma del que nacen pequeñas terminales
denominadas dendritas, responsables de recibir los est́ımulos; y una prolongación
llamada axón encargada de transmitir los impulsos, la figura 4.1 muestra un
esquema1.
Los receptores convierten est́ımulos en señales eléctricas que proporcionan
información a la red de neuronas, estas señales son procesadas por el cerebro
y convertidas por los efectores en respuestas o salidas. La retroalimentación
1tomada de http://campusvirtual.unex.es/cala/epistemowikia/images/b/b4/Neurona.PNG
Figura 4.1: Esquema de una neurona
21
22 CAPÍTULO 4. REDES NEURONALES
está presente al haber flujo de información de los efectores al cerebro y de este
a los receptores.
Se cree que hay aproximadamente 10 billones de neuronas en la corteza
cerebral y 60 trillones de conexiones entre ellas. Las interconexiones neuronales
se dan a través de la sinapsis, una neurona t́ıpicamente da lugar a varios miles
de sinapsis en las que generalmente se conecta el axón con las dendritas de
otra célula, aunque también puede hacerlo con el cuerpo celular, con otro axón
o dendrita con dendrita. La sinapsis puede ocurrir entre dos neuronas o entre
una neurona y una célula de otro tipo, la sinapsis más común es la qúımica, el
mecanismo t́ıpicamente es como sigue [11]:
1. El potencialde membrana es el voltaje entre el interior y el exterior
de la célula, la sinapsis qúımica comienza con un potencial de acción,
que es un pico en el potencial de membrana que sigue una trayectoria
predeterminada, este viaja por la membrana de la neurona presináptica
hasta llegar a la sinapsis, que es el lugar de unión entre las dos neuronas.
2. El potencial de membrana se hace más positivo o menos negativo
(depolarización), lo que causa que se abran los canales permeables a iones
de calcio.
3. Los iones de calcio fluyen por la membrana de la neurona presináptica, lo
que incrementa rápidamente la concentración de calcio en el interior.
4. La concentración de calcio activa un conjunto de protéınas sensibles al
calcio, unidas a veśıculas que contienen neurotransmisores
5. Estas protéınas cambian de configuración, haciendo que algunas veśıculas
se unan a la membrana presináptica, se abren las veśıculas y vierten los
neurotransmisores en el espacio entre las membranas de las dos células.
6. Algunos de estos neurotransmisores escapan, pero otros se unen a
receptores de la membrana de la célula postsináptica.
7. El neurotransmisor activa la célula receptora, hay varios mecanismos para
esto.
8. Debido a la agitación térmica el neurotransmisor se separa del receptor,
y puede ser destruido metabólicamente o reabsorbido por la neurona
presináptica para uso futuro.
El peso de una conexión está definido por el cambio en el potencial
postsináptico de membrana, que es el que resulta de la activación de los
receptores de los neurotransmisores postsinápticos. Los cambios en el peso
sináptico pueden ser a corto o largo plazo, los cambios a corto plazo duran
entre segundos y minutos, y no implican cambios celulares estructurales; los
cambios a largo plazo ocurren por la repetida activación sináptica, debido a la
cual mensajeros secundarios pueden iniciar la śıntesis de protéınas, resultando
en una alteración de la sinapsis misma. Se cree que estos mecanismos a largo
plazo son responsables del aprendizaje y la memoria.
En el proceso anterior se observa cómo una señal eléctrica se transforma
en una qúımica y esta a su vez en una eléctrica de nuevo. Las redes neuronales
4.2. REDES NEURONALES ARTIFICIALES 23
artificiales son un modelo de cómputo, producto de la abstracción de los procesos
neuronales, de los que podemos conservar lo siguiente:
Se tiene un número N de unidades sencillas de procesamiento conectadas
entre śı, a cada par está asociado un valor llamado peso sináptico.
Las unidades pueden o no recibir una entrada del exterior, es un valor
constante pero que puede variar para cada unidad y al que después se
asociará con un umbral.
Cada unidad recibe una entrada de las otras N − 1, y hace una suma
pesada de estos N − 1 términos mas el est́ımulo exterior si es que este
existe, el peso de cada término es el peso sináptico entre la unidad que
está haciendo la suma y la unidad de la que proviene dicho término. A la
suma pesada mas el factor externo se le llama a veces campo local inducido.
Una función de activación proporciona una salida a cada unidad, tomando
como entrada el valor del campo local inducido.
La salida de una unidad puede ser entrada para otras neuronas, siempre
que su peso sináptico respecto a ella no sea cero.
En la siguiente sección se explicará con más detalle esto, pero teniendo en
cuenta que cada unidad realiza una operación muy sencilla podemos notar que
se trata de un cómputo emergente, en el que las propiedades colectivas no se
pueden reducir a las propiedades de las partes individuales. Es justamente en las
interacciones (pesos) y umbrales donde se almacena información relevante, en las
redes de Hopfield que se discutirán más adelante, la información del problema
se codifica en los pesos y umbrales, y se deja al sistema evolucionar hasta llegar
a un estado de equilibrio, que representa una configuración óptima del sistema,
al menos localmente.
4.2. Redes neuronales artificiales
Cualquier computadora es capaz de realizar tareas como el cálculo de
millones de cifras por segundo, o almacenar en unos instantes datos que a un
humano le tomaŕıa mucho tiempo, sin embargo con los algoritmos convencionales
es realmente dif́ıcil programarla para que realice una tarea tan sencilla para
un ser humano como reconocer patrones o tratar con ruido. Para un programa
convencional, una silueta de una persona con la mano derecha arriba y otra de la
misma persona con la mano izquierda arriba seŕıa un objeto totalmente distinto.
La diferencia entre estos tipos de tareas parece ser la naturaleza intŕınsecamente
paralela y no lineal del segundo, un ser humano al analizar una imagen toma
información simultáneamente de una gran cantidad de segmentos pertenecientes
a la misma, y pone a trabajar un igualmente numeroso grupo de unidades.
El cerebro humano es capaz de reconocer patrones en un tiempo mucho
menor que el que le tomaŕıa a cualquier programa creado, a pesar de que la
24 CAPÍTULO 4. REDES NEURONALES
velocidad de los componentes de una computadora moderna es aproximada-
mente seis órdenes de magnitud mayor a la de las reacciones en el cerebro. Un
ser humano crea categoŕıas de la experiencia, mediante inferencia inductiva, y
después puede utilizarlas de manera deductiva, en una computadora serial este
proceso parece casi imposible. Según [10], el cerebro humano puede reconocer
un rostro familiar en un ambiente nuevo en un lapso de entre 100 y 200 ms, a
una computadora digital le tomaŕıa mucho más una tarea menos compleja.
Además del alto paralelismo y la no linealidad, el cerebro humano puede
aprender, ajustarse al medio, tratar con ruido, es compacto, disipa poca enerǵıa
y es tolerante a fallos.
Debido a la identificación de lo anterior como deseable para la resolución
de problemas, o simplemente a la tendencia a imitar a la naturaleza por
considerarla eficiente, se han desarrollado algoritmos que tratan de reproducir
algunas de estas caracteŕısticas, entre ellos se encuentran las redes neuronales.
Estas redes surgieron como modelos del funcionamiento del sistema nervioso,
aunque han evolucionado como herramientas de inteligencia artificial, alejándose
a veces del realismo a cambio de eficiencia. La naturaleza ha servido no
sólo como inspiración, sino también como herramienta directa para resolver
problemas donde se requiere un alto paralelismo. Leonard M. Adleman [9] en
1994 publicó un art́ıculo donde utilizaba ADN para resolver una instancia de
siete nodos del problema del camino Hamiltoniano, otro problema NP-completo,
en el que en una gráfica se define un nodo inicial y uno final, y hay que encontrar
un camino que empezando en el nodo inicial y terminando en el final pase sólo
una vez por cada nodo. La diferencia con el problema del agente viajero es que
dos nodos no son necesariamente adyacentes en el del camino hamiltoniano, si
la gráfica del problema del camino hamiltoniano es totalmente conectada este
problema se convierte en el del agente viajero. En términos prácticos resolver
una instancia de siete nodos es trivial, sin embargo fue la primera vez que se
utilizó de forma satisfactoria el ADN para realizar cómputo. El algoritmo es el
siguiente:
1. Generar caminos aleatorios en la gráfica.
2. Mantener los caminos que empiecen en el nodo inicial y terminen en el
final.
3. Si la gráfica tiene n nodos, mantener sólo los caminos que pasen
exactamente por n nodos.
4. Mantener sólo los caminos que contengan al menos una vez cada nodo.
5. Si quedó algún camino, devolver “śı”, de lo contrario, devolver “no”.
La implementación biológica consistió en codificar cada nodo i en una
secuencia aleatoria de ADN de 20 elementos, y cada arista ij en la unión de los
últimos 10 elementos de la secuencia correspondiente al nodo i con los primeros
10 elementos de la secuencia correspondiente al nodo j. Exceptuando los casos
en que i fuera el nodo inicial o j el nodo final, en losque se tomaŕıan los 20
4.2. REDES NEURONALES ARTIFICIALES 25
Figura 4.2: La cadena complementaria a un nodo j sirve para unir una arista ij
con una arista jk
elementos.
Aśı, por ejemplo si el nodo i se representa con la secuencia TATCG-
GATCGGTATATCCGA llamada Oi, el nodo j con la secuencia GCTATTC-
GAGCTTAAAGCTA denominada Oj , y el nodo k con la secuencia GGCTAGG-
TACCAGCATGCTT llamada Ok, entonces la arista ij quedará representada
por la secuencia Oij GTATATCCGACTTAAAGCTA y la arista jk por la
secuencia CTTAAAGCTAGGCTAGGTAC denominada Ojk.
La unión de dos aristas con un nodo en común, como ij con jk quedaŕıa
codificada aśı:
GTATATCCGACTTAAAGCTA - CTTAAAGCTAGGCTAGGTAC
Recordando que Oj es GCTATTCGAGCTTAAAGCTA, su cadena comple-
mentaria O∗j es CGATAAGCTCGAATTTCGAT, O
∗
j sirve para unir Oij con
Ojk por afinidad de pares como se muestra la figura 4.2.
A nivel laboratorio, para una gráfica de siete nodos, con nodo incial a y nodo
final b, los cinco pasos del algoritmo se implementaron de la siguiente forma:
1. Se mezclaron en una reacción de ligación 50 pmol de cada O∗i para cada
i (exceptuando la correspondiente al nodo incial y la correspondiente al
nodo final, ya que para estos nodos se necesita una sola arista que los
contenga), y 50 pmol de cada Oij para cada ij tales que existiera una arista
que uniera al nodo i con el nodo j. Con lo que se obtuvieron moléculas de
ADN que codificaban caminos aleatorios.
2. Se amplificó mediante la técnica reacción en cadena de la polimerasa
(PCR, por sus siglas en inglés) el producto del paso anterior, usando
iniciadores Oa y O
∗
b , con lo que se consiguió amplificar sólo los caminos
que empezaban en a y terminaban en b.
3. El resultado del paso anterior se corrió en un gel de agarosa y se
amplificó la banda correspondiente a 140 pares de bases, que representa
moléculas que codifican caminos que incluyen exactamente siete vértices.
26 CAPÍTULO 4. REDES NEURONALES
Figura 4.3: Neurona artificial simple
4. El producto del paso anterior fue purificado por afinidad con un sistema
magnético de biotina - avidina. Se generó una cadena sencilla de la doble
cadena del paso anterior, y para una i fija se utilizaron cadenas O∗i unidas
a esferas de hierro, se prepararon condiciones para el emparejamiento de
cadenas y se utilizó un imán para atraer a las moléculas que conteńıan O∗i
y por tanto representaban caminos que conteńıan al nodo i. Se repitió este
proceso para cada i.
5. El resultado del paso anterior se amplificó para saber si se generó una
molécula que codificara un camino hamiltoniano.
Volviendo al enfoque anterior, de utilizar a la naturaleza como modelo y no
como herramienta, regresamos a las redes neuronales artificiales. Se comentó en
la sección anterior que estos modelos de aprendizaje artificial basados en la forma
en que se cree que funciona el cerebro humano constan de unidades (neuronas)
interconectadas, con un peso sináptico asociado a cada par y una función que
transforma la entrada proveniente de las demás unidades en una salida utilizable
por las otras unidades, la figura 4.3 ejemplifica gráficamente una neurona de dos
entradas2.
En términos matemáticos, una neurona k está representada por dos ecua-
ciones:
uk =
m∑
j=1
wkjxj
yk = φ(uk + bk)
Donde uk es la suma pesada de las entradas provenientes de las demás
neuronas, wkj es el peso sináptico entre las neuronas k y j, xj es la salida
de la neurona j, bk es el est́ımulo externo constante aplicado a la neurona k, φ
2tomada de http://upload.wikimedia.org/wikipedia/commons/thumb/f/f0/Computer.Science.AI.Neuron.svg/250px-
Computer.Science.AI.Neuron.svg.png
4.2. REDES NEURONALES ARTIFICIALES 27
es la función de activación y yk es la salida de la neurona k.
El comportamiento de la red dependerá entre otras cosas de la forma de
la función de activación, para que la red se acerque a nuestros propósitos hay
que seleccionar una función adecuada, en seguida se describen algunos tipos de
función de activación.
4.2.1. Funciones de Activación
Usualmente encontramos tres tipos de funciones de activación, las funciones
de umbral, las funciones lineales a trozos y las funciones sigmoides.
Una función de umbral es una función escalón de Heaviside, este modelo
conocido como de Mc Culloch - Pitts, es un modelo de “todo o nada”, si el
campo local inducido, es decir la suma del est́ımulo externo de una neurona
con la suma pesada de las entradas de las demás es no negativa, entonces la
neurona se activa, de lo contrario permanece inactiva. Esta función representa
a una unidad que se activa cuando la entrada excede un umbral. El modelo de
Hopfield que se usará posteriormente incorpora esta función de activación, si
por ejemplo el est́ımulo externo es negativo, entonces el requerimiento de que la
suma pesada mas el est́ımulo sea no negativo es equivalente a pedir que la suma
pesada sea mayor al est́ımulo externo, aśı para cada unidad el est́ımulo externo
funciona como un umbral.
Con ecuaciones:
m∑
j=1
wkjxj + (−bk) ≥ 0 ⇒
m∑
j=1
wkjxj ≥ bk
Aśı, para cada unidad k el est́ımulo externo bk se puede ver también como
el umbral asociado a esa unidad.
La función escalón se muestra en la figura 4.4.
La función lineal a trozos se define por una ecuación del tipo:
φ(v) =
 0 si v ≤ −
1
2
v + 12 si −
1
2 < v <
1
2
1 si v ≥ 12
Y la podemos observar en la figura 4.5.
Finalmente, la función sigmoide es muy utilizada en la construcción de redes
neuronales ya que es no lineal, siempre creciente y diferenciable, un ejemplo es
la función loǵıstica:
φ(v) =
1
1 + e−av
El parámetro a indica la pendiente de la sigmoide, al aumentar este valor y
hacerlo tender a infinito recuperamos la función escalón. La figura 4.6 muestra
dos funciones loǵısticas, la de ĺınea continua tiene una pendiente de 1, la de ĺınea
28 CAPÍTULO 4. REDES NEURONALES
Figura 4.4: Función escalón de Heaviside
Figura 4.5: Función lineal a trozos
4.2. REDES NEURONALES ARTIFICIALES 29
Figura 4.6: Función sigmoide
discontinua tiene una pendiente de 0.5:
Lo importante de estas funciones es que más allá de cierto valor de saturación
la salida tenga dos posibilidades, los valores de las mismas son irrelevantes
aśı que de ser conveniente se puede usar por ejemplo el conjunto 0,1 o el -
1,1.
Otro aspecto importante a considerar al diseñar una red es la topoloǵıa, que
se refiere a las conexiones entre unidades y como consecuencia de ello al flujo
de la información.
4.2.2. Topoloǵıas de redes neuronales
Se distinguen dos tipos de arquitecturas:
Las redes proalimentadas, en las que el flujo de datos es estrictamente de
entrada a salida. Se tienen n capas de neuronas, y una neurona de la capa
i puede únicamente estar conectada a neuronas de la capa i+1. La primer
capa es la que recibe la entrada y la última da la salida. Como la capa de
entrada no realiza cómputo por convención no se le cuenta en el número de
capas, aśı, una red de una capa de entrada, una capa oculta o intermedia,
y una capa de salida se dice que tiene dos capas. En la imagen3 4.7 se
muestra una red proalimentada, con tres entradas y dos salidas.
Las redes retroalimentadas o recurrentes pueden admitir conexiones más
generales, y la noción de capa puede o no estar presente. En estas redes
debido a la posible presencia de ciclos hay dos esquemas, en uno el que
3upload.wikimedia.org/wikipedia/commons/thumb/e/e1/MultiLayerNeuralNetwork.png/400px-
MultiLayerNeuralNetwork.png
30 CAPÍTULO 4. REDES NEURONALES
Figura 4.7: Red proalimentada
Figura 4.8: Red recurrente de dos capas
el comportamiento dinámico es muy importante ya que la activación
puede continuar indefinidamente o hasta que el sistema se estabilice en
un atractor; y otro en el que se calcula la activación de cada unidad una
vez y trata las conexiones recurrentes como información extra, incorporada
por la propia red. La figura 4.8 es de una red recurrente con dos capas:
El número decapas en una red proalimentada es importante ya que
determina la capacidad de clasificación que tiene un sistema. Minsky y Papert
demostraron que una red de una sola capa no puede representar un simple XOR
(O exclusivo). La tabla de valores de XOR, para entradas binarias -1 y 1 es la
siguiente:
x0 x1 y
-1 -1 -1
-1 1 1
1 -1 1
1 1 -1
Que gráficamente se ilustra en la figura 4.9 4.
Las gráficas representan los operadores lógicos AND, OR y XOR. Cada una
de estas funciones tiene por entrada dos valores binarios, el caso concreto de
4tomada de [12]
4.2. REDES NEURONALES ARTIFICIALES 31
Figura 4.9: Representación de AND, OR y XOR
XOR se ejemplifica en la tabla anterior, XOR toma valor 1 si y sólo si las
entradas son distintas, aśı que las entradas (-1,1) y (1,-1) tienen valor de 1 (en
negro en la gráfica) y las demás de -1 (mostrado en blanco).
Podemos observar que AND devuelve 1 en un sólo punto, aśı que si trazamos
una ĺınea es posible separar las entradas que devuelven 1 y de las que devuelven
-1. OR tiene 3 valores de un tipo y uno de otro, por lo que de igual forma existen
ĺıneas que pueden separar el problema, sin embargo para XOR esto es imposible
ya que las dos entradas a separar están en la misma ĺınea. La relación entre lo
anterior y las redes neuronales es que una red de una sola capa tiene capacidad
de separar valores de la misma forma en que lo hace una ĺınea recta, ya que
para una capa y dos entradas, con una entrada externa constante θ, la entrada
total s es:
s = w1x1 + w2x2 + θ
Tomando por función de activación una función umbral, la salida es 1 si
s ≥ 0 y -1 si s ≤ 0, es decir los puntos del plano x1, x2 que cumplan
w1x1 + w2x2 ≥ −θ
Darán como salida 1 y los demás -1. El ĺımite es justamente la recta
w1x1 + w2x2 = −θ
Por lo que todos los puntos que estén de un lado activarán la unidad.
Este inconveniente se soluciona agregando una capa oculta, lo que geométri-
camente significa agregar una dimensión, siendo con ello los puntos separables
por un plano en el espacio ahora tridimensional. Lo anterior no se presentará a
detalle aqúı ya que las redes a utilizar son las de Hopfield, pero puede ser
consultado en [12]. Las redes de Hopfield son redes recurrentes en las que el
número de capas no está definido, pertenecen al grupo de redes que se estabilizan
en un atractor, en estas redes no hay restricciones sobre la conectividad de las
unidades.
32 CAPÍTULO 4. REDES NEURONALES
4.3. Redes de Hopfield
La idea de Hopfield para optimizar funciones fue hacer una analoǵıa con
un sistema dinámico que tiende al equilibrio. En su art́ıculo [1] la función a
optimizar era la similitud entre una cadena binaria y una cadena binaria patrón
porque buscaba justamente almacenar patrones en una red. Cada estado del
sistema (concretamente las salidas de las unidades) representaŕıa un patrón y
podŕıa verse como un punto en el espacio de configuración, con la enerǵıa se
codificaŕıan los patrones a almacenar en los pesos y umbrales de la red, de tal
forma que los puntos que representan los patrones a almacenar fueran mı́nimos
locales, aśı al empezar desde un lugar cercano a un patrón almacenado la
dinámica conduciŕıa el sistema hasta este. Por punto cercano se puede entender
un patrón parecido a alguno de los almacenados, pero con ruido. De esta forma
la red funcionaŕıa como una memoria asociativa. Si los patrones son imágenes
podemos recuperar o “recordar” una imagen con parte de ella, o con una versión
ligeramente distorsionada de la misma.
Una red de Hopfield es una red en la que se admiten todas las conexiones
posibles entre neuronas, con una función de activación tipo umbral. Se toman
unidades al azar y se les aplica la función de activación, si los pesos wij cumplen
ciertos requisitos, a saber, wij = wji y wii = 0 para todo (i, j) entonces la red
eventualmente converge a un estado de equilibrio. Para ejemplificar lo anterior y
su utilidad se describirá un problema sencillo pero ilustrativo, el de la memoria
asociativa, abordado por Hopfield en su art́ıculo [1].
El problema es el siguiente, se tiene un sistema de N unidades, la unidad
i puede estar en el estado ξi = 1 o ξi = −1. Se le llama patrón µ al conjunto
ξµ = {ξ1, ξ2, ..., ξN} Se deben almacenar p patrones, de tal forma que cuando
se presente una nueva cadena ζ, la red produzca el patrón almacenado más
parecido a ζ.
Tomaremos como función de activación para la unidad i una función escalón:
Si = sgn(
N∑
j
wijSj − θi) (4.1)
Donde de nuevo wij son los pesos y θi son los umbrales. La función sgn es:
sgn(x) =
{
1 si x ≥ 0
−1 si x < 0
Hasta ahora, no sabemos nada de los valores de los pesos y los umbrales,
aśı que en cierta forma son parámetros que podemos ajustar para obtener lo
que deseamos, que es estabilidad. Observemos ahora como se puede almacenar
un patrón. Si escribimos las siguientes N ecuaciones:
sgn(
N∑
j
wijξj − θi) = ξi ∀ i
4.3. REDES DE HOPFIELD 33
Podemos observar que de cumplirse, la regla de actualización no produciŕıa
cambios ya que justamente aśı se definió la regla de actualización. Cualesquiera
parámetros que permitan esta igualdad conseguiŕıan estabilidad para el patrón
a almacenar. En particular si tomamos
θi = 0
wij ∝ ξiξj
Obtendremos
sgn(
N∑
j
wijSj − θi) ∝ sgn(
N∑
j
ξiξ
2
j ) = sgn(
N∑
j
ξi) = sgn(Nξi) = Nξi
De esta forma, si tomamos
wij =
ξiξj
N
Tenemos la igualdad deseada. Más aún, si el estado inicial {Si} difiere
en menos de la mitad de los bits del patrón almacenado {ξi}, este error
será compensado por la suma
N∑
j
wijSj
Aśı, todos los estados que difieran en menos de la mitad de los bits del
patrón terminarán en el valor almacenado, por lo que el patrón ξ es un
atractor. Análogamente se puede probar que -ξ es otro atractor, de hecho si
el estado inicial difiere en más de la mitad de los bits del patrón el sistema
evolucionará hasta este estado reverso. Para un sólo patrón almacenado tenemos
estos dos atractores.
Si se desean almacenar p patrones, se encuentra de la misma forma que los
pesos deben calcularse mediante una superposición de los patrones
wij =
1
N
p∑
µ=1
ξµi ξ
µ
j
En [13] se discute la capacidad de almacenamiento para un sistema de N
unidades.
4.3.1. Enerǵıa
En la sección anterior se habló de estabilidad sin considerar la “enerǵıa”
asociada al estado de la red. El concepto de enerǵıa surgió de la analoǵıa entre
estos sistemas y el modelo de Ising, como el de espines descrito en la sección de
recocido simulado. El modelo de Ising es un modelo para el ferromagnetismo,
se tienen variables discretas (espines) que pueden tomar dos estados y que
34 CAPÍTULO 4. REDES NEURONALES
interactúan con los vecinos, la dinámica del sistema es tal que los espines se
acomodan minimizando la enerǵıa.
En la analoǵıa de Hopfield las neuronas corresponden a los espines, los pesos
a las interacciones entre ellos, los umbrales al campo inducido y la función a
optimizar a la enerǵıa, en este caso la función se minimiza pero si nuestra función
objetivo requiere ser maximizada basta un cambio de signo en la misma. En el
caso de la memoria asociativa la función a optimizar es la similitud entre el
estado inicial S y el patrón más cercano ξ. Al ajustar los pesos wij para que
almacenen los patrones, la dinámica es la que bajo este modelo tendŕıa un
sistema de N espines, con interacciones wij entre ellos.
La enerǵıa del sistema en ambos casos se define como:
H = −1
2
N∑
i
N∑
j
wijSiSj +
N∑
i
θiSi (4.2)
Más adelante se verá que la función objetivo tiene que ser de la forma de esta
enerǵıa, por lo que ella determina el tipo de problemas que se pueden solucionar
con una red de Hopfield.
4.3.2. Forma de la función objetivo y condiciones de
estabilidad
Al describir la memoria asociativa se encontró una condición suficiente para
que la regla de actualización nos condujese hasta un punto deseado, sin embargo
el problema de una función general a optimizar y sus condicionesde estabilidad
aún no se ha discutido.
Para ambos podemos usar el concepto de enerǵıa, recordando la analoǵıa de
Hopfield la función a optimizar corresponde a la enerǵıa, por lo que con este
modelo lo mejor que podemos conseguir es minimizar una función de la forma
(4.2), es decir con una suma de términos lineales y cuadráticos en las variables.
El procedimiento entonces para aplicar el algoritmo de Hopfield, es escribir
la función a optimizar en la forma (4.2) para encontrar los pesos y umbrales
que codifiquen nuestro problema. Al escribir la función a optimizar puede que
aparezcan términos cúbicos o de mayor orden, esto, como se verá más adelante
en el planteamiento particular del problema de la ruta más corta, puede a veces
resolverse reescribiendo la función en otros términos, si no es posible entonces
deberá buscarse algún otro algoritmo de optimización.
Para discutir la estabilidad de un sistema descrito por una función general
de la forma (4.2) bajo la regla de actualización (4.1), evaluemos el cambio en la
enerǵıa del sistema debido a un cambio en la unidad k, de Vk0 a Vkf .
4.4. CONSECUENCIAS DE QUITAR LAS RESTRICCIONES DE LOS PESOS.35
∆Hk = −
1
2
∑
i
wikViVkf −
1
2
∑
i
wkiVkfVi + bkVkf +
1
2
wkkVkfVkf
−(−1
2
∑
i
wikViVk0 −
1
2
∑
i
wkiVk0Vi + bkVk0 +
1
2
wkkVk0Vk0)
= −1
2
∑
i
wikVi∆Vk −
1
2
∑
i
wkiVi∆Vk + bk∆Vk +
1
2
wkk(V
2
kf − V 2k0)
Si
wij = wji y wii = 0 ∀i, j (4.3)
entonces se puede escribir:
∆Hk = −∆Vk(
∑
i
wkiVi − bk) (4.4)
Si la unidad k cambió de -1 a 1 entonces ∆Vk > 0, y de acuerdo a la regla
de actualización para que se haya dado este cambio∑
i
wkiVi − bk ≥ 0
Por lo tanto, de la ecuación (4.4) ∆Hk ≤ 0
Por otro lado, si el cambio fue de 1 a -1 ∆Vk < 0 y
∑
i wkiVi − bk < 0, en
cuyo caso ∆Hk < 0
Combinando ambos casos, siempre podemos decir que ∆Hk ≤ 0
Todo lo anterior significa que un sistema con una función de la forma
(4.2), bajo las restricciones (4.3) y con una regla de actualización como
(4.1) irá evolucionando hasta encontrarse al menos en un mı́nimo local. Las
condiciones (4.3) fueron llamadas por Gérard Toulouse un “inteligente salto
hacia atrás del realismo biológico”, ya que en la naturaleza no hay evidencia que
nos lleve a pensar en conexiones simétricas, pero como se mostró proporcionan
estabilidad al modelo. Más adelante se discutirá el efecto de ignorar estas
restricciones y una manera de evitarlas.
4.4. Consecuencias de quitar las restricciones de
los pesos.
Al respecto Hopfield [1] estudió el efecto de remover estas condiciones en
sistemas de 30 y 100 neuronas, en los que los wij son números aleatorios entre
-1 y 1. Encontró que para N = 30 el sistema no muestra un recorrido ergódico
por todo el espacio de configuración, y antes de cierto tiempo se establece en
una conducta ĺımite, siendo lo más común un punto estable. En 50 simulaciones
para cada matriz encontró que frecuentemente dos o tres estados capturaban la
36 CAPÍTULO 4. REDES NEURONALES
dinámica, existiendo a veces oscilaciones entre dos puntos, o un recorrido caótico
en una región del espacio de configuración de distancia de Hamming pequeña.
El caso de N = 100 mostró resultados cualitativamente similares. En [16] se
estudia el comportamiento caótico de una red de Hopfield con 3 neuronas y uno
de los pesos como parámetro, se encuentran atractores y ciclos ĺımite. Hertz
[13] propone una ligera asimetŕıa que funcione como ruido para escapar de los
mı́nimos locales menos estables, sin embargo no resulta muy conveniente en
la práctica ya que en primer lugar, el problema está codificado en los pesos
y umbrales, por lo que la asimetŕıa no es un parámetro a elegir, y en segundo
lugar no es algo sobre lo que se tenga control, variar la asimetŕıa seŕıa resolver un
problema distinto al planteado. En el presente texto se utiliza la temperatura
como parámetro variable a voluntad capaz de introducir ruido al sistema y
permitirnos escapar de los estados menos estables, se propone una regla de
actualización que implica cambios no positivos en la enerǵıa, de esta forma se
puede introducir ruido de forma controlada y retirarlo a voluntad. Antes de
ello se analizarán algunos resultados obtenidos de la simulación utilizando el
algoritmo original de Hopfield.
Como ejemplo de problema a resolver con una red de Hopfield se tratará el
de encontrar la ruta más corta entre dos nodos de una gráfica.
Caṕıtulo 5
Ruta más corta en una
gráfica
5.1. Implementación
El problema es, dados los vértices a y b de una gráfica, encontrar una ruta
de costo total mı́nimo que los conecte. El costo entre dos nodos es una constante
que puede representar el tiempo de tránsito, la distancia f́ısica o cualquier otro
valor que nos interese.
El primer paso para abordar el problema de la ruta más corta en una gráfica
utilizando una red neuronal de Hopfield es definir la estructura de la red. Si la
gráfica original tiene N nodos, una forma de construir la red es con N(N − 1)
neuronas, la neurona (i, j) tendrá como salida Vij = 1 si la arista que une el
nodo i con el j está en la ruta, y 0 de otra forma.
Habiendo dado una estructura a la red, necesitamos definir una función que
tenga por mı́nimo la configuración de la red que represente la ruta más corta
entre el nodo a y el nodo b.
La ruta entre a y b tiene que cumplir algunas condiciones:
1. Que la suma de los costos entre cada par de nodos que forman la ruta sea
mı́nima
2. No agregar aristas inexistentes.
3. Que la ruta sea continua
4. Que la ruta comience en a y termine en b.
Una ruta que cumpla simultáneamente las cuatro condiciones será la deseada.
Expresando matemáticamente el problema, tenemos un conjunto de N
nodos, una matriz A de adyacencia, como se describe en la definición 8 del
caṕıtulo sobre gráficas, y una matriz C de costos (en este caso la distancia
euclidiana entre nodos), en la que el elemento cij es el costo asociado a la arista
37
38 CAPÍTULO 5. RUTA MÁS CORTA EN UNA GRÁFICA
que une al nodo i con el j, si es que esta existe.
Con estos elementos podemos podemos construir la función de enerǵıa. Para
el primer requisito tenemos simplemente:
E1 = α1
N∑
i,j
CijVij (5.1)
El término anterior es mı́nimo si se escogen las aristas de menos costo. Al
final para la enerǵıa total se sumarán todos los términos de la enerǵıa, por lo
que la constante α1 es un parámetro a controlar para darle más o menos peso a
un término.
Sobre el segundo requisito podemos construir con la matriz de adyacencia
otra matriz M con elementos cero donde la matriz de adyacencia tiene algo
distinto de cero, y valores muy altos en las demás entradas, aśı, el término:
E2 = α2
N∑
i,j
MijVij (5.2)
Será mı́nimo si las aristas incluidas son las existentes en la gráfica, como la
red neuronal incluye neuronas para todas las unidades de alguna forma hay que
penalizar a las neuronas que representen aristas inexistentes. Podŕıa también
hacerse una red con neuronas sólo para aristas existentes, esto haŕıa innecesario
el término anterior y además reduciŕıa el tiempo de cómputo, pero en este caso
se tomó la red completa.
Sobre la continuidad podŕıamos por ejemplo escribir para cada par i, j un
término proporcional a
Vij(
N∑
k
Vjk − 1)2
Aśı si la arista ij no está en la ruta, el término será cero, y si está en la
ruta será mı́nimo cuando la suma sea 1, esto es cuando exista una y sólo una
arista que salga de j, teniendo aśı continuidad en el nodo j. El problema de este
término es que tendŕıamos una interacción cúbica entre las neuronas, situación
incompatible con la forma de la enerǵıa en (4.2). Si quitamos el cuadrado
pareceŕıa resolverse el problema porque la interacción seŕıa ahora cuadrática,
sin embargo al quitar el cuadrado la cantidad entre paréntesis podŕıa ser -1 si
la suma es cero, lo que nos daŕıa un mı́nimo si la ruta se interrumpe en j y esto
claramente no es lo que buscamos. También podŕıamos pensaren utilizar un
valor absoluto en vez de elevar el interior al cuadrado, pero el problema seŕıa
ahora que habŕıa que tratarlo por casos, cuando lo de adentro es negativo y
cuando es positivo, esto depende directamente del valor de Vjk, que es variable.
Lo anterior significaŕıa que los pesos dependen de la dinámica en lugar de ser
constantes y tampoco es lo que deseamos.
Como se comentó con anterioridad la forma de expresar la enerǵıa es crucial
para poder aplicar el algoritmo, a veces dificultades como la anterior se pueden
salvar reformulando la enerǵıa en otros términos. En este caso por ejemplo se
5.1. IMPLEMENTACIÓN 39
puede bajar el orden de la interacción si exigimos continuidad en cada nodo,
es decir, el número de aristas entrantes debe ser igual al número de aristas
salientes, con excepción del nodo a y el b, en el nodo inicial debe salir una arista
y no entrar nada y en el nodo final lo opuesto.
Lo anterior se puede expresar de la siguiente forma:
E3 = α3
N∑
i
(
N∑
k 6=i
Vki −
N∑
k 6=i
Vik + F (i))
2 (5.3)
con
F (i) =
{
1 si i = a
−1 si i = b
Para cada nodo i, si i 6= a, b la parte entre paréntesis se anula si la suma
de arsitas entrantes es igual a la suma de aristas salientes. Si i = a el interior
del paréntesis se anula sólo si la primer suma es 0 y la segunda es 1, lo que
implica que no hay aristas entrando al nodo a y hay una arista saliendo de él.
Si i = b entonces el término se anula si la primer suma es 1 y la segunda 0, lo
que significa que hay una arista que entra a b y ninguna sale de ah́ı.
El mı́nimo de la expresión (5.3) hasta ahora es aquella configuración en la que
sale una arista de a y no entra ninguna, entra una arista en b y no sale ninguna,
y para todos los demás nodos el número de aristas salientes es igual al número
de aristas entrantes. Si la configuración incluye la ruta más corta y además otras
aristas que mantengan la simetŕıa este término seguiŕıa siendo mı́nimo, aunque
al incluir el término (5.1) esta configuración seŕıa más energética que la de la
ruta más corta.
Sin embargo esto no es suficiente aún, como ya se mencionó el algoritmo de
Hopfield original encuentra mı́nimos locales, y puede ser que la solución trivial
{Vij} = 0 para todo i, j sea un mı́nimo local, ya que es mı́nima en todos los
términos hasta ahora incluidos exceptuando los dos que incluyen la función F,
que son pocos comparados con los 2N2 + 2(N − 1)2 + (N − 2) términos que no
incluyen F.
Para lo anterior podemos agregar un término más:
E4 = α4
∥∥∥∥∥∥
N∑
ij
Vijdij − dab
∥∥∥∥∥∥ (5.4)
Donde dij es el vector distancia entre los nodos ij.
Dentro del śımbolo de norma tenemos dos vectores, el primero es la suma
de todos los vectores incluidos en la ruta en un estado particular del sistema,
el segundo es el vector que va del inicio al final. La norma se hará cero cuando
estos dos vectores sean iguales, es decir cuando al unir todos los segmentos de la
ruta, el inicio y el fin estén a una distancia igual que a y b. Esto por śı sólo puede
en el peor de los casos tener un mı́nimo en cualquier configuración que cumpla
lo anterior, pudiendo ser incluso discontinua y no empezar en a ni terminar en b,
sin embargo penaliza la salida trivial y al ser combinado con los demás términos
40 CAPÍTULO 5. RUTA MÁS CORTA EN UNA GRÁFICA
ya tenemos cubiertas las cuatro condiciones requeridas.
Si unimos los términos anteriores tenemos:
E(a, b) = α1
N∑
i,j
CijVij + α2
N∑
i,j
MijVij (5.5)
+α3
N∑
i
(
N∑
k 6=i
Vki −
N∑
k 6=i
Vik + F (i))
2 + α4
∥∥∥∥∥∥
N∑
ij
Vijdij − dab
∥∥∥∥∥∥
Que es una función cuyo mı́nimo es la configuración que representa una ruta
continua de a a b del menor costo.
Ahora falta escribir (5.5) en términos de (4.2), es decir llevar a cabo todas
las operaciones y agrupar los términos cuadráticos y lineales, los términos
constantes se pueden ignorar porque al importarnos sólo las diferencias en la
enerǵıa estos términos son irrelevantes.
Para codificar el problema en la red neuronal, los coeficientes de los términos
cuadráticos corresponderán a los pesos, los de los términos lineales a los umbrales
y los constantes, como ya se mencionó, serán ignoradas.
Como cada neurona representa un par de nodos y por tanto tiene dos ı́ndices,
se necesitan 4 ı́ndices para especificar un peso w, por ejemplo wijkl será el peso
de la conexión entre la neurona ij que representa la arista ij y la neurona kl
que representa la arista kl.
Como ejemplo se simplificará el término E4 en sus componentes cuadráticas,
lineales y constantes.
E4 = α4
∥∥∥∥∥∥
N∑
ij
Vijdij − dab
∥∥∥∥∥∥ = (
∑
ij
Vij(xj − xi)− (xb − xa))2
+(
∑
ij
Vij(yj − yi)− (yb − ya))2 =
∑
ij
∑
kl
VijVkl(xj − xi)(xl − xk)
−2(xb − xa)
∑
ij
Vij(xj − xi) + (xb − xa)2
+
∑
ij
∑
kl
VijVkl(yj − yi)(yl − yk)
−2(yb − xa)
∑
ij
Vij(yj − yi) + (yb − ya)2
Por lo que:
E4 = −
1
2
∑
ijkl
w4ijklVijVkl +
∑
ij
U4ijVij
Donde
5.1. IMPLEMENTACIÓN 41
w4ijkl = −2(xj − xi)(xk − xl)− 2(yj − yi)(yl − yk) (5.6)
Es la parte de los pesos correspondientes a E4, y
U4ij = −2(xb − xa)(xj − xi)− 2(yb − ya)(yj − yi) (5.7)
Es la parte de los umbrales.
Para obtener los pesos, hay que hacer lo mismo con los demás términos de
la enerǵıa, los dos primeros no tienen términos cuadráticos aśı que sólo resta el
tercero, un cálculo como el anterior arroja:
w3ijkl =

-2 si j = l y i, k 6= j
4 si j = k y i, l 6= j
-2 si i = k y j, l 6= i
0 en cualquier otro caso
(5.8)
Por lo que el peso total es la suma de (5.6) y (5.8)
La parte del umbral asociada al tercer término de la enerǵıa, U3ij es la suma
de cuatro términos:
U3aij =
{
2 si j = a y i 6= a
0 de cualquier otra forma
U3bij =
{
-2 si i = a y j 6= a
0 de cualquier otra forma
U3cij =
{
-2 si j = b y i 6= b
0 de cualquier otra forma
U3dij =
{
2 si i = b y j 6= b
0 de cualquier otra forma
Ahora faltan sólo las contribuciones al umbral de los primeros dos términos,
U1ij = Cij
U2ij = Mij
De todo lo anterior ya podemos calcular los pesos y umbrales totales:
wijkl = w
3
ijkl + w
4
ijkl
Uij = U
1
ij + U
2
ij + U
3a
ij + U
3b
ij + U
3c
ij + U
3d
ij + U
4
ij
Hasta ahora se han tenido dos dificultades, la forma restrictiva de la ecuación
(4.2) a funciones a lo más cuadráticas y la convergencia a mı́nimos locales.
El primer punto se resolvió reformulando la enerǵıa y el segundo mejorará al
agregar a la simulación el algoritmo del recocido simulado. Sin embargo hay un
problema más, los pesos encontrados para este problema violan las condiciones
de Hopfield, que son simetŕıa (wij = wji) y elementos nulos en la diagonal
(wii = 0), en el siguiente caṕıtulo se observará qué sucede de violarse estas
condiciones, y se encontrará una forma de evitarlas.
42 CAPÍTULO 5. RUTA MÁS CORTA EN UNA GRÁFICA
Caṕıtulo 6
Resultados
6.1. Resultados utilizando el algoritmo original
Sabemos que nuestra ecuación de enerǵıa no cumple con las condiciones
de estabilidad, aśı que para ver las consecuencias de esto en nuestro problema
particular se utilizó una instancia simple, una gráfica de 9 nodos y 12 aristas en
forma de rectángulo de 2 aristas de lado con un costo unitario para cada arista.
Se eligió como nodo inicial la esquina inferior izquierda y como nodo final la
esquina superior derecha, como se esperaba que la enerǵıa no se estabilizara
necesariamente, se guardó la configuración de menor enerǵıa que el sistema
hubo adquirido, siendo ésta final o no.
Los resultados se pueden observar en la figura 6.1. La parte superior es la
gráfica en la que se buscará la ruta más corta, en rojo se muestran las conexiones
y en negro las aristas que el programa arrojó como solución. Los nodos negros
son el incial y el final. La parte inferior es la enerǵıa en función del tiempo.
Se puede observar que la salida es un camino discontinuo, y que ni siquiera
incluye el nodo inicial. Además podemos ver de la gráfica que la enerǵıa no
necesariamente desciende, y aunque no se incluyeaqúı ninguna imagen hubo
casos en los que la enerǵıa oscilaba o teńıa un comportamiento aparentemente
caótico.
Se escribió un programa en Python para ver los efectos individuales de las
restricciones en la forma de la matriz de pesos, el procedimiento fue el siguiente:
1. Construir una matriz de números aleatorios, pero que cumpla las condi-
ciones (4.3). Asociarle a esta matriz el número de variación cero.
2. Seleccionar como condiciones iniciales, valores al azar de encendido o
apagado para las neuronas. Guardar estos valores para tener siempre las
mismas condiciones iniciales para efectos de comparación.
3. Correr el algoritmo de Hopfield, y después de cierto periodo de tránsito,
guardar la enerǵıa del sistema para cada tiempo. El algoritmo de Hopfield
requiere de actualización al azar de las N unidades, para efectos de
comparación entre las variaciones se actualizaron las unidades en el mismo
orden, aunque este fue al azar.
43
44 CAPÍTULO 6. RESULTADOS
Figura 6.1: Resultado de aplicar el algoritmo original
4. Graficar en el eje x el número de variación y en el eje y los valores que
haya tenido la enerǵıa después del tiempo de tránsito para ese número de
variación.
5. Alejarse gradualmente de las condiciones de Hopfield (la forma de hacerlo
se detallará adelante). Aumentar en uno el número de variación.
6. Repetir desde el paso 3
Lo anterior para observar, al alejarnos gradualmente de las condiciones (4.3),
el efecto en la estabilidad del sistema. Lo que hace el algoritmo es simplemente
graficar en el eje x el grado de asimetŕıa y en el eje y los estados finales después
de un tiempo de tránsito, si se observa más de un punto en una ĺınea vertical
significa que hay más de un estado final, esto es se establece una conducta ĺımite
o se comporta caóticamente pero no se estabiliza. El algoritmo se repitió con
distintas matrices, todas al azar, sin embargo con algunas se desestabilizaba
el sistema mucho más rápido que con otras. Sin detenerse en el estudio de las
caracteŕısticas de las matrices que presentaban este compartamiento, se fijó una
de ellas para el estudio posterior, esta matriz teńıa por entrada enteros entre
-2 y 2, y umbrales entre -1 y 1. Para la condición de Hopfield de simetŕıa, se
consiguió un alejamiento gradual al sumar aleatoriamente números arriba de la
diagonal, debido a que lo importante no son los valores de los términos w(i, j) y
w(j, i) sino la diferencia entre ellos, agregar números al azar en ambos lados de
la diagonal podŕıa de hecho mantener ambos valores cercanos. El requerimiento
de los ceros de la diagonal también se trató sumando gradualmente números a
ella. Debido a que en ambos casos para tener estabilidad sólo nos interesa estar
cerca de w(i, i) = 0 y |w(i, j) − w(j, i)| = 0, se podŕıa esperar que el aumento
6.1. RESULTADOS UTILIZANDO EL ALGORITMO ORIGINAL 45
Figura 6.2: Resultado de sumar -0.2 a elementos sobre la diagonal
del número de estados finales sucediera de igual forma si se suman sólo números
negativos o sólo números positivos, sin embargo como muestran algunas de las
figuras siguientes, se observó en las simulaciones que esto no fue aśı .
Como primer gráfica se muestra en la figura 6.2 el efecto de sumar el número
-0.2 a elementos elegidos aleatoriamente sobre la diagonal
No se observa nada significativo, únicamente un desplazamiento del valor
final de la enerǵıa. Para la figura 6.3 se hizo lo mismo pero ahora agregando un
número positivo, 0.2
En este caso śı hay un aumento en el número de estados finales después de
cierta variación, y los valores además se van alejando entre śı, lo que implica una
mayor inestabilidad del sistema. Si ahora agregamos constantemente un número
negativo sólo a la diagonal, como por ejemplo -0.05, obtenemos lo que muestra
la figura 6.4. El valor a agregar en cada variación fue mucho más pequeño en el
caso de la diagonal ya que si hay N2 elementos en la matriz habŕıa sólo N en
la diagonal.
La figura 6.4 comparte algunas caracteŕısticas con los diagramas de bifurca-
ción, que no es de sorprender ya que se ha hablado del caos que puede presentar
este algoritmo si no se dan las condiciones de estabilidad. Se encuentran por
ejemplo zonas con menos estados finales en medio de zonas con una cantidad
mayor de los mismos.
Podemos observar ahora en la figura 6.5 y 6.6 que sumar a la diagonal
números positivos no tiene consecuencias significativas.
Y como es de esperarse, si se combinan las condiciones de los casos que
presentaron inestabilidad, es decir si se agregan números negativos a la diagonal
y positivos sobre ella se obtiene otro caso interesante, que se puede observar en la
46 CAPÍTULO 6. RESULTADOS
Figura 6.3: Resultado de sumar 0.2 a elementos sobre la diagonal
Figura 6.4: Resultado de sumar números negativos a la diagonal de la matriz
6.1. RESULTADOS UTILIZANDO EL ALGORITMO ORIGINAL 47
Figura 6.5: Resultado de sumar números positivos a la diagonal
Figura 6.6: Resultado de sumar números positivos a la diagonal y sobre ella
48 CAPÍTULO 6. RESULTADOS
Figura 6.7: Resultado de sumar números negativos a la diagonal y positivos
sobre ella
figura 6.7. Aunque a simple vista no se distingue, con la ayuda de un programa
se encontró que el número de estados finales se mantuvo constante a partir de
cierta variación, y hubo una región que no se ubicaba al final, para la que el
número de estados finales fue el mayor. Se guardó una matriz correspondiente
a esta región para analizar posteriormente el posible comportamiento caótico
resultante de utilizarla como matriz de pesos.
Con esta matriz se corrió el algoritmo de Hopfield y se generó una serie de
tiempo con los valores de la enerǵıa resultantes, a dicha serie se le aplicó una
transformada rápida de Fourier. La transformada de Fourier es una herramienta
matemática para mapear una función en el espacio de frecuencias. Se puede
considerar a una función como un elemento de un espacio vectorial de dimensión
infinita, el espacio de las funciones, que admite por base al conjunto de soluciones
de cualquier operador diferencial autoadjunto como se puede encontrar en
cualquier libro sobre funciones especiales como [14], estas bases son capaces de
generar cualquier función expresándola como combinación lineal de elementos de
la misma, los coeficientes de esta expansión representan la contribución de cada
elemento de la base a la función, son la proyección de la función en cada elemento
de ella. Si en particular se toma como base al conjunto {sen(nx), cos(nx)}, n ∈ N
tendremos para la expansión coeficientes que indican la amplitud, o importancia
de una frecuencia particular en una función. Una transformada rápida de Fourier
lleva esta idea a conjuntos discretos de datos, permitiéndonos tener una idea de
la periodicidad de los mismos al conocer las frecuencias involucradas.
Un sistema caótico tiene una regla determinista que genera salidas con
periodicidad infinita pero no es lo mismo que azar, la transformada rápida de
Fourier de una serie de tiempo totalmente aleatoria es una ĺınea horizontal
debido a la igual contribución de todas las frecuencias, una serie periódica con
una única frecuencia se mostraŕıa bajo la transformada como un único pico, y
un sistema caótico t́ıpico exhibiŕıa en escala logaŕıtmica una ĺınea inclinada al
6.2. MODIFICACIÓN AL ALGORITMO ORIGINAL 49
Figura 6.8: De arriba a abajo serie de tiempo, valor absoluto de la transformada
rápida de Fourier y transformada en escala logaŕıtmica con ajuste lineal
aplicársele la transformada.
En el caso tratado aqúı se consiguió un ajuste con valor de R2 =0.51,
pendiente de -0.66 y ordenada al origen de 12.34, en la imagen 6.8 se muestran
las gráficas de la serie de tiempo, la transformada y la transformada en escala
logaŕıtmica con su ajuste lineal.
Se puede observar en la parte superior de la figura 6.8 que poco abajo del
valor 50 de la enerǵıa, la salida