Download Métodos heurísticos de optimización.

M ¶etodos heur¶³sticos de optimizaci¶on
a
a
R o s a Ir m a H e r n ¶a n d e z D u r a¶ n y S e r g io G. d e lo s Co b o s S ilva .
E s t u d ia n t e d e L ic e n c ia t u r a e n Co m p u t a c i¶o n , D e p t o . In g e n ie r ¶ ³a E l¶ e c t r ic a , U A M{ I
se busca primordialmente es minimizar costos para el uso e¯ciente de recursos cada vez m¶as escasos, o para maximizar utilidades o bene¯cios. Sin embargo, muchos de estos problemas son muy complejos y no existen m¶etodos e¯cientes y r¶
apidos para encontrar una soluci¶
on ¶
optima. Debido a esto han surgido procedimientos o t¶ecnicas heur¶³sticas1 que han
demostrado ser lo su¯cientemente e¯cientes y capaces de entregar una \buena soluci¶
on"como se ver¶a
m¶
as adelante.
Re s u me n
H o y e n d¶ ³a e x iste n una g ra n v a rie da d de pro ble ma s de o ptimiz a c i¶o n c o mbina to ria q ue so n de a lta c o mple jida d, e sto de bido a q ue e nc o ntra r su so luc i¶o n ¶o ptima o c e rc a na a e lla e s dif¶ ³c il, so bre to do to ma ndo e n c ue nta q ue
lo q ue se busc a e s una r¶a pida so luc i¶o n utiliz a ndo una
c a ntida d a de c ua da de re c urso s c o mputa c io na le s. En e ste tra ba jo se mue stra n a lg uno s de lo s m¶e to do s de pro g ra ma c i¶o n e sto c ¶a stic a e n o ptimiz a c i¶o n, q ue se c a ra c te riz a n po r da r una \ bue na so luc i¶o nante dic ho s pro ble ma s. A lg uno s de lo s m¶e to do s q ue se pre se nta n e n e ste tra ba jo so n: la B¶usq ue da T a b¶u, A lg o ritmo s Ge n¶e tic o s
y la s Re de s N e uro na le s, q ue ha n de mo stra do su e ¯c ie nc ia y q ue so n de lo s m¶a s utiliz a do s e n e l Esta do de l A rte .
En este trabajo se tiene como uno de los objetivos el presentar algunas de las bases y caracter¶³sticas
de algunos m¶etodos heur¶³sticos (m¶etodos de programaci¶
on estoc¶
astica en optimizaci¶
on), los cuales han
mostrado ser actualmente una gran herramienta para cumplir con el punto m¶
as importante de la Investigaci¶
on de Operaciones, la optimizaci¶
on de recursos cada vez m¶
as escasos. El presente trabajo se estructura de la siguiente manera: en la Secci¶on 1
se explica en general la e¯ciencia de los m¶etodos
heur¶³sticos, as¶³ como el por qu¶e se dice que proporcionan una \buena soluci¶
on"; en la Secci¶
on 2 se plantean de manera general los problemas de optimizaci¶
on combinatoria; en la Secci¶
on 3 se proporciona una introducci¶
on a la B¶
usqueda Tab¶
u; en la Secci¶
on 4 se da una descripci¶
on de los elementos principales sobre los Algoritmos Gen¶eticos, y ¯nalmente en la Secci¶
on 5 se habla sobre el tema de Redes Neuronales.
P a la b ra s cla ve s : Optimiz a c i¶o n C o mbina to ria , B¶usq ue da T a b¶u, A lg o ritmo s Ge n¶e tic o s, Re de s N e uro na le s.
A b s t ra ct
T he re e x ists a g re a t v a rie ty o f hig hly c o mple x pro ble ms
in c o mbina to ria l o ptimiz a tio n, fo r w hic h c lo se d a na ly tic a l so lutio ns a re di±c ult o r impo sible to o bta in. H o w e re r he uristic s pro g ra mming me tho ds suc h a s: T a bu
Se a rc h, Ge ne tic A lg o rithms o r N e ura l N e tw o rk s, ha v e
pro v e n to be v e ry use ful in ¯nding fa st a nd e c o no mic a l fa irly \ g o o d so lutio ns" , a nd a re a c o mmo n c o mpo ne nt o f the sta te o f the a rt me tho ds fo r so lv ing suc h
k ind o f pro ble ms. In this a rtic le , a re v ie w a nd a de sc riptio n o f suc h me tho ds is pre se nte d.
Ke ys
w ord s :
C o mbina to ria l Optimiz a tio n, T a bu Se a rc h, Ge ne tic A lg o rithms a nd N e ura l N e tw o rk s.
Introducci¶
on
Cuando escucha el t¶ermino de Investigaci¶
on de Operaciones, >qu¶e le viene a la mente? ... >s¶
olo modelos matem¶
aticos?, >ecuaciones y c¶alculos? Sin embargo, no son s¶olo matem¶aticas. Quiz¶a pase por alto uno de sus objetivos generales: la optimizaci¶
on,
s¶³ la optimizaci¶on de recursos.
1. M¶
etodos e¯cientes y soluciones ¶
optimas
Los m¶etodos heur¶³sticos son e¯cientes pero,
>respecto a qu¶e recursos?, existen recursos tales como tiempo de ejecuci¶
on y espacio de almacenamiento. Esto es un punto a favor de los
m¶etodos heur¶³sticos, debido a que algunos problemas complejos de optimizaci¶
on combinatoria no pueden resolverse de manera exacta usando tiempo y espacio de computadora razonables como se podr¶
a ver m¶
as adelante. A¶
un a pesar de que actualmente se cuenta con supercomputadoras de alta velocidad capaces de realizar
La optimizaci¶on es importante, ya que actualmente
se presenta una gran variedad de problemas de optimizaci¶
on. Muchos de estos problemas implican situaciones reales y pr¶acticas, como son los problemas de
localizaci¶
on de plantas, de rutas, de inversi¶
on de portafolios, de transporte, dise~
no de chips, y mantenimiento de sistemas entre algunos. En donde lo que
1 H eu r ¶
³stica p r ov ien e d e la p alab r a gr iega eu r istik en
sign i¯ ca en con tr ar .
5
q u e
6
ContactoS 31, 5{16 (1999)
millones o hasta billones de instrucciones por segundo, ante problemas de optimizaci¶on el querer generar todas las alternativas posibles por
medio de este tipo de computadora no ser¶³a factible ni e¯ciente (si no lo cree, contin¶
ue leyendo). Para entender mejor esto, suponga el problema de la \mochila", el cual parte del hecho de que cuando se sale de excursi¶on, la cantidad de utensilios que se puede empacar en
la mochila, queda determinado por la capacidad de la mochila, el volumen de los utensilios (objetos) y el valor intr¶³nseco que ¶estos tienen para el excursionista; por lo tanto, el problema consiste en llenar la mochila con el conjunto de objetos m¶as valiosos que maximicen la
utilidad de ¶estos durante la excursi¶on, sin exceder los l¶³mites f¶³sicos de la mochila. En t¶erminos
matem¶
aticos el problema en cuesti¶on se formula como:
Max Z =
X
vi xi < KT ;
i
donde:
vi
=
es el valor del objeto i,
i= 1,2,. . . ,n;
xi
= es la capacidad o volumen
del objeto i, i= 1,2,. . . ,n;
KT = es la capacidad o volumen
de la mochila en general
Ahora bien, suponga que se cuenta con n = 50
objetos, esto implicar¶³a que la computadora
tendr¶³a que analizar m¶as de 800 billones (bill¶
on
= 1012 ) de combinaciones, examinar todas estas
posibles combinaciones le llevar¶³a mucho tiempo a la computadora, ahora bien si aumentamos s¶
olo en dos la cantidad de los objetos, es decir, 52 objetos la computadora tendr¶³a que analizar m¶
as de 4503 billones de combinaciones. O
sea, con s¶
olo un peque~
no aumento en la cantidad de los objetos, la diferencia en el n¶
umero
de combinaciones aumenta de manera notable,
en este caso aumentar¶³a en m¶as 3600 billones
de combinaciones. <Imagin¶ese! Esto s¶³ que implicar¶³a poca e¯ciencia, ya que aparte de analizar todas las posibles combinaciones y ver cu¶
ales
son las que no rebasan el espacio de la mochila KT , todav¶³a se tendr¶³a que analizar cu¶ales son
las que contienen los objetos de m¶as valor para el excursionista, esto l¶ogicamente aumentar¶³a
el tiempo de ejecuci¶on, y ¶³todav¶³a faltar¶³a ver
qu¶e hay en cuanto al espacio de c¶omputo! Por
lo tanto, se puede decir que uno de los problemas a los que se enfrentan los algoritmos exactos, por ejemplo, los de enumeraci¶on son el tiempo y espacio (ante conjuntos no tan grandes
de elementos) ya que se tendr¶³an que generar
en forma secuencial todas las posibles combinaciones, y aparte analizar todas estas combinaciones generadas. Es por esto, que la alternativa ante desventajas como ¶estas son los m¶etodos
heur¶³sticos, que tienen la ventaja de optimizar
el tiempo y espacio de c¶
omputo.
Tambi¶en se mencion¶
o que los m¶etodos heur¶³sticos producen o entregan una \buena soluci¶
onante problemas complejos de optimizaci¶on
combinatoria. Por \buena soluci¶
on", se entender¶
a en adelante que la soluci¶
on obtenida est¶a
relativamente cercana a la ¶
optima, sino es que
se trata de la soluci¶
on ¶
optima propiamente dicho.
La pregunta ahora es: >c¶
omo se puede a¯rmar que los m¶
etodos heur¶³sticos en realidad producen una \buena soluci¶
on", si
no se conoce la soluci¶
on ¶
optima? Claro, si
se conociera la soluci¶
on ¶
optima, utilizando recursos de manera razonable (tiempo y espacio)
no habr¶³a por qu¶e usar m¶etodos heur¶³sticos.
La respuesta a la anterior pregunta es la siguiente: hay problemas de optimizaci¶
on ya conocidos para los cuales existen algoritmos r¶
apidos
y e¯cientes que permiten conocer las soluciones
optimas de dichos problemas. Pues bien, con ba¶
se en algunos de estos problemas para los cuales ya se conoce su soluci¶
on ¶
optima o la mejor reportada en la literatura, se les aplican los
m¶etodos heur¶³sticos, dando como resultado una
soluci¶
on muy cercana a la ¶
optima en la mayor¶³a de los casos si no es que en muchas ocasiones se igualan. Y todo esto se logra con s¶olo
analizar un peque~
no subconjunto del conjunto total de combinaciones posibles de soluciones factibles. Esto indica que los problemas son
resueltos de manera \inteligente"mediante los
m¶etodos heur¶³sticos.
2. Planteamiento general de un problema de optimizaci¶
on combinatoria
Se ha hecho menci¶
on que los m¶etodos
heur¶³sticos dan soluci¶
on a los problemas de optimizaci¶
on combinatoria pero, >cu¶
al es la forma de ¶estos?
Los problemas de optimizaci¶
on se dividen en
problemas de optimizaci¶
on con variables continuas y problemas de optimizaci¶
on con variables discretas, llamados problemas de optimizaci¶
on combinatoria. En estos u
¶ltimos, la soluci¶on
se busca sobre un conjunto ¯nito o in¯nito numerable.
El problema de optimizaci¶
on combinatoria se
puede representar de la siguiente forma:
M¶etodos heur¶³sticos de optimizaci¶on. Rosa Irma Hern¶
andez D. y Sergio G. de los Cobos S.
P = Minimizar C(x)
tal que x 2 X µ Rn
donde:
X denota el conjunto ¯nito
(o a lo m¶as numerable) de
todas las soluciones factibles.
C es la funci¶on objetivo, o costo.
Como se nota la formulaci¶on para estos problemas es sencilla, sin embargo resolverlos y encontrar la soluci¶on ¶optima puede que no lo sea,
tal como lo apunta Guti¶errez Andrade (1991),
\Una caracter¶³stica recurrente en los problemas
de optimizaci¶on combinatoria es el hecho de que
son muy \f¶aciles"de entender y de enunciar, pero generalmente son \dif¶³ciles"de resolver".
En el caso de minimizaci¶on, el problema consiste
en encontrar xop t tal que cumpla con:
C(xop t ) · C(x); 8x 2 X
A la soluci¶on xopt se le llama una soluci¶
on globalmente ¶optima, en donde la funci¶
on objetivo (costo ¶optimo) es Cop t = C(xop t ), adem¶
as
Xop t denota el conjunto de soluciones ¶
optimas
que son totalmente \cercanasa la soluci¶
on globalmente ¶optima xop t .
Ahora bien, los m¶etodos heur¶³sticos pueden resolver problemas del tipo P , que buscan encontrar una soluci¶on x 2 Xop t . Dichos m¶etodos se
caracterizan a trav¶es de movimientos que permiten pasar de una soluci¶on factible a otra soluci¶
on factible, tal que los movimientos pertenezcan a X (conjunto de soluciones factibles).
3. Una introducci¶
on a la b¶
usqueda Tab¶
u
Haciendo un poco de historia, se puede mencionar que las ideas b¶asicas de la B¶
usqueda Tab¶
u
fueron hechas por Fred Glover (1986) y por Pierre Hansen (1986).
Pero, >qu¶e es la B¶
usqueda Tab¶
u? La B¶
usqueda
Tab¶
u es un m¶etodo heur¶³stico de \alto nivel",
que se usa para resolver problemas de optimizaci¶
on de gran escala. Se dice que de \alto nivel",
ya que esta dise~
nado para guiar a otros m¶etodos
a que \escapen"de la optimalidad local, y as¶³ poder continuar con la b¶
usqueda para mejorar ese
optimo local encontrado. La B¶
¶
usqueda Tab¶
u ha
demostrado ser un m¶etodo \inteligente", al obtener las mejores soluciones en una gran variedad de problemas pr¶acticos.
Es importante hacer notar que ya en la d¶ecada
de los a~
nos ochenta, el Committee on Next Decade of Operations Research (Condor (1988))
7
cali¯caba a la B¶
usqueda Tab¶
u, junto con la
t¶ecnica del Recocido Simulado y los Algoritmos Gen¶eticos como \extremadamente promisorios"para el tratamiento futuro de aplicaciones pr¶
acticas. Actualmente, se ha demostrado
que dichos m¶etodos en realidad han cumplido
con su papel en aplicaciones reales y pr¶
acticas.
Figura 1. Regi¶
on Factible y soluci¶
on inicial.
El algoritmo de la b¶
usqueda tab¶
u consiste b¶asicamente en: A partir de una soluci¶
on factible inicial (ver Figura 1) de un problema de optimizaci¶
on combinatoria, hay que moverse paso a paso hacia una soluci¶
on que proporcione el
valor m¶³nimo de la funci¶
on objetivo C(x). Cada soluci¶
on factible se puede representar como
un punto p en alguna regi¶
on espacial, adem¶as
se de¯ne una vecindad N (p) (ver Figura 2) para cada punto p, que consta de soluciones factibles que son \cercanasa p en alg¶
un sentido.
Figura 2. Conjunto vecindad del punto p.
El paso b¶
asico del algoritmo de la b¶
usqueda
tab¶
u es que una vez que se tiene la soluci¶on inicial factible, y se gener¶
o el conjunto de soluciones N (p), entonces se escoge al mejor vecino generado de p que viene a ser p¤ , el cual es
8
ContactoS 31, 5{16 (1999)
el nuevo punto a partir, ya sea que C(p¤ ) tenga o no una mejor soluci¶on que C(p). Y as¶³ sucesivamente.
Ahora bien, uno de los objetivos de la b¶
usqueda
tab¶
u consiste en inducir la exploraci¶on hacia
nuevas regiones, para encontrar nuevas soluciones de alta calidad. Otro de sus objetivos, es el
de evitar casos de ciclado, impidiendo as¶³ que los
movimientos hacia nuevas soluciones nos regresen al mismo ¶optimo local del cual se pudo haber partido o a un punto de alguna iteraci¶
on anterior. Esto se logra gracias a una de las caracter¶³sticas m¶
as notables de la b¶
usqueda tab¶
u, que
es la construcci¶on de una lista tab¶
u T de movimientos. Dicha lista consiste en aquellos movimientos que no son permitidos (movimientos
tab¶
ues) en la presente iteraci¶on. (Ver Figura 3).
Todo esto es precisamente con el ¯n de evitar
ciclos.
Figura 3. Movimiento Tab¶
u
Algo que se debe mencionar es que la prevenci¶
on de ciclos no es la u
¶ltima meta del proceso
de b¶
usqueda, ya que se pueden presentar casos,
en donde una buena trayectoria de b¶
usqueda resultar¶
a al revisitar una soluci¶on encontrada antes, esto lleva a que la clasi¯caci¶on de tab¶
u de un
movimiento pueda eliminarse, por lo tanto, un
movimiento tab¶
u permanece como tal, s¶
olo durante un cierto n¶
umero de iteraciones, de forma tal que esto implica que T es una lista c¶³clica
donde para cada movimiento s ¡! s¤ el movimiento opuesto s¤ ¡! s ser¶a un movimiento no permitido que se adiciona al ¯nal de la lista T , donde el movimiento m¶as viejo en T se
elimina.
Como se nota, la b¶
usqueda tab¶
u cuenta con elementos para poder encontrar una \buena soluci¶
on", la de restringir la b¶
usqueda a ciertos puntos, mediante la clasi¯caci¶on de tab¶
u (prohibidos) y la de quitar la etiqueta de tab¶
u a movimientos que mejoren la soluci¶on previamente encontrada. El criterio que permite dicha eliminaci¶
on es denominado criterio de aspiraci¶
on.
Es as¶³ como las restricciones tab¶
ues y el criterio de aspiraci¶
on de la b¶
usqueda tab¶
u, juegan
un papel dual en la restrici¶
on y gu¶³a del proceso de b¶
usqueda.
Con base en lo anterior es importante enfatizar
los siguientes puntos:
² La lista T de los movimientos tab¶
u, es la
que proporciona una b¶
usqueda restringida,
esto lleva a que las soluciones generadas
dependan cr¶³ticamente de la composici¶on
y la manera en que se actualiza la lista T .
² La b¶
usqueda tab¶
u no hace referencia a la
condici¶
on de optimalidad local, a excepci¶
on de aquellos casos cuando el ¶
optimo
local es mejor que la soluci¶
on previamente encontrada.
² Un mejor movimiento se elige en cada
paso.
Un punto importante de la b¶
usqueda tab¶
u es la
construcci¶
on de una lista tab¶
u T de movimientos que no son permitidos en cada iteraci¶
on (movimiento tab¶
u). El principal objetivo de esta lista es excluir los movimientos a los puntos de iteraciones anteriores. Ahora bien, >cu¶
al debe ser
el tama~
no ideal de esta lista? Lo que se debe tener en cuenta de este par¶
ametro es que si la longitud es demasiada peque~
na, seguro ocurrir¶a el
ciclado, es decir, se regresar¶
a a movimientos anteriores, sin embargo, si es demasiado grande,
restringir¶
a la b¶
usqueda para poder salir de soluciones locales. Por tanto, una faceta importante de la b¶
usqueda tab¶
u es la habilidad para localizar un rango robusto de longitudes de
la lista tab¶
u mediante pruebas emp¶³ricas preliminares para identi¯car, para una clase de problemas, los tipos de atributos y de restricciones tab¶
u que son realizados de manera efectiva.
Otro elemento importante en la b¶
usqueda tab¶
u
es el criterio de nivel de aspiraci¶
on, cuya ¯nalidad es la de permitir que la condici¶
on de
tab¶
u de un movimiento se elimine y se seleccione como mejor movimiento, esto si se puede obtener una mejor soluci¶
on que la alcanzada hasta el momento, o sea este criterio de aspiraci¶
on da una oportunidad para eliminar la
clasi¯caci¶
on de tab¶
u y permiten que el m¶etodo
de la b¶
usqueda tab¶
u alcance sus mejores niveles de realizaci¶
on.
Seg¶
un apunta Laguna et al. (1990), algunos de
los criterios de aspiraci¶
on son: \(a) Aspiraci¶on
por default: si todos los movimientos posibles
son clasi¯cados como tab¶
u, entonces el movimiento \menos tab¶
u"es seleccionado. (b) Aspi-
M¶etodos heur¶³sticos de optimizaci¶on. Rosa Irma Hern¶
andez D. y Sergio G. de los Cobos S.
raci¶
on por objetivo: una aspiraci¶on de movimiento es satisfecha, permitiendo que un movimiento x sea un candidato para seleccionarse, si C(x) < mejor costo. (c) Aspiraci¶
on por direcci¶
on de b¶
usqueda: un atributo de aspiraci¶
on
es satisfecho, si la direcci¶on proporciona un mejoramiento y el actual movimiento es un movimiento de mejora".
Intensi¯caci¶on y diversi¯caci¶on
Si en alguna iteraci¶on ya no existieran puntos
admisibles, se tendr¶³an que utilizar las fases de
intensi¯caci¶on y la diversi¯caci¶on. La fase intensi¯caci¶on proporciona una forma simple para dirigir la b¶
usqueda alrededor de la mejor soluci¶
on o conjunto de mejores soluciones. Existe en la b¶
usqueda una matriz de frecuencias que
es la que registra la \historia"del procedimiento y que da informaci¶on en cuanto a las regiones
que no se han visitado, y es utilizada para formar la funci¶on de memoria de t¶ermino largo, la
cual permite la diversi¯caci¶on de la b¶
usqueda;
es decir, es posible dirigir la b¶
usqueda \m¶
as cercana"¶
o \m¶as alejada"en las regiones exploradas.
Para aplicaciones reales, tales como un problema de calendarizaci¶on y una aplicaci¶on en cuanto a selecci¶on de rutas, puede consultar a De los
Cobos (1997) y P¶erez S. et al. (1996), respectivamente.
4. Una introducci¶
on
a los Algoritmos Gen¶
eticos
Por el siglo XIX, se introdujo una teor¶³a que revolucion¶o al mundo: la teor¶³a de la evoluci¶
on
del brit¶
anico Charles Darwin. En ¶esta, Darwin
a¯rmaba que las especies naturales van evolucionando para adaptarse a su medio ambiente, con el criterio de que los individuos que mejor se adapten a los cambios de su entorno son
los que tendr¶an mayor probabilidad de sobrevivir hasta la edad adulta y procrear, haciendo que sus genes pasen a la siguiente generaci¶
on cuando se reproduzcan.
Pero, >qu¶e tiene que ver est¶a teor¶³a con los
m¶etodos heur¶³sticos? Si la naturaleza es capaz de ir optimizando las caracter¶³sticas de un
individuo perfeccionando sus genes para adaptarse mejor a su medio, >por qu¶e no se puede crear una poblaci¶on digital que se optimice para adaptarse mejor a la funci¶on objetivo
que se plantee y a la cual se le quiera dar soluci¶
on? Es aqu¶³ donde entran los Algoritmos
Gen¶eticos.
Or¶³genes
La idea de los algoritmos gen¶eticos, surgi¶
o de
modo independiente en dos frentes, uno de ¶estos
9
fue en los Estados Unidos, donde en los a~
nos sesenta el profesor John Holland de la Universidad de Michigan, sabiendo de la importancia de
la selecci¶
on natural, desarroll¶
o una t¶ecnica que
permiti¶
o incorporarla en un programa de computadora; en donde su objetivo era lograr que
las computadoras aprendieran por s¶³ mismas.
Su t¶ecnica se llam¶
o \planes reproductivos"pero,
tras una de sus publicaciones por 1975, dicha
t¶ecnica se hizo popular bajo el nombre de algoritmos gen¶eticos.
De modo independiente, el alem¶
an Rechenberg
introdujo la idea de la Estrategias Evolutivas.
Fue precisamente en 1964, cuando Rechenberg
empez¶
o con su primer experimento para imitar
el m¶etodo de la evoluci¶
on biol¶
ogica.
Claro est¶
a que desde aquellos a~
nos sesenta hasta
la fecha, muchas otras personas han contribuido
de modo notable al desarrollo de estas ideas.
Actualmente la comunidad cient¶³¯ca est¶a mostrando gran inter¶es en esta t¶ecnica en b¶
usqueda
basada en la teor¶³a de la evoluci¶
on de Darwin,
y que se conoce como algoritmos gen¶eticos. Esta t¶ecnica tiene como base los criterios de selecci¶
on que utiliza la naturaleza, ¶estos hacen que
los individuos que mejor se adapten a los cambios de su entorno sean los que sobrevivan, actualmente los cient¶³¯cos saben que estos cambios se efect¶
uan en los genes del individuo (unidad b¶
asica de codi¯caci¶
on de cada uno de los
atributos de un ser vivo), y que sus atributos
m¶
as deseables, es decir aquellos que le permiten adaptarse mejor a su entorno, son los que
se transmiten a sus descendientes.
Entonces c¶
omo se de¯ne lo que es un algoritmo gen¶etico: \Es un algoritmo matem¶
atico altamente paralelo que transforma un conjunto
de objetos matem¶
aticos individuales con respecto al tiempo usando operaciones modeladas de
acuerdo al principio darwiniano de reproducci¶
on y supervivencia del m¶
as apto, y tras haberse presentado de forma natural una serie de
operaciones gen¶eticas de entre las que se destaca la recombinaci¶
on sexual. Cada uno de estos objetos matem¶
aticos suele ser una cadena de
caracteres (letras o n¶
umeros) de longitud f¶³sica
que se ajusta al modelo de las cadenas de cromosomas, y se les asocia con una cierta funci¶
on matem¶
atica que re°eja su aptitud."(John
Koza 1992).
En t¶erminos generales se puede decir que los
algoritmos gen¶eticos son t¶ecnicas de b¶
usqueda
aleatoria que imitan los procesos observados en
la evoluci¶
on natural. Tienen como base que a
partir de soluciones iniciales (padres) se gene-
10
ContactoS 31, 5{16 (1999)
ran nuevas soluciones (hijos), empleando mecanismos que se aplican en la gen¶etica. La mejor
descendencia de las soluciones padres se retienen para una nueva generaci¶on, por lo que se fomenta la supervivencia de los m¶as aptos, la mejor de todas las descendencias se registra y es el
candidato propuesto por el m¶etodo para una soluci¶
on ¶
optima.
Componentes b¶asicos
Un algoritmo gen¶etico b¶asico tiene tres operadores: reproducci¶on, cruzamiento y mutaci¶on. La
reproducci¶
on consiste en el apareamiento aleatorio de dos individuos tomados de un conjunto de soluciones, para crear una o m¶as descendencias. El cruzamiento consiste en el cambio de
genes (tipo de informaci¶on y sus atributos) siguiendo el modelo de reproducci¶on biol¶ogica, toman en cuenta que la descendencia tenga un mejoramiento en relaci¶on con sus padres. La mutaci¶
on consiste en introducir un elemento aleatorio, muchas veces con la ¯nalidad de que al cambiar un gene no se den los resultados esperados, adem¶
as la mutaci¶on diversi¯ca el espacio
de b¶
usqueda aleatoria y protege de la p¶erdida
de material gen¶etico que pueda darse en la reproducci¶
on y el cruzamiento.
Aplicaciones
La aplicaci¶on m¶as com¶
un de los algoritmos
gen¶eticos, y donde han mostrado ser muy e¯cientes y con¯ables, es en la soluci¶on de problemas de optimizaci¶on combinatoria, y en par¶
ticular en los problemas de secuenciaci¶on. Estos
aparecen frecuentemente en muchas ciencias
aplicadas. Por ejemplo, el problema del agente viajero, los problemas de rutas, el problema
de la mochila, el problema del coloreo de grafos, el problema de plani¯caci¶on de tareas, entre otros.
Sin embargo, es importante hacer notar que antes de usar el m¶etodo de los algoritmos gen¶eticos
para alg¶
un problema en particular, se deben tomar en cuenta las siguientes caracter¶³sticas del
mismo:
² Lo recomendable es que el problema cuente con un espacio de b¶
usqueda discreto, es
decir debe de estar delimitado dentro de
un cierto rango, no importando si este espacio de posibles soluciones es muy grande. Aunque, tambi¶en funciona para espacios de b¶
usqueda continuos, pero preferentemente cuando exista un rango de soluciones relativamente peque~
nos.
² Debe poderse de¯nir una funci¶
on de aptitud (funci¶on objetivo del problema de
optimizaci¶
on a resolver) que indique qu¶e
tan buena o mala es una cierta soluci¶on,
de tal forma que permita que las \buenas"soluciones se propaguen con mayor rapidez.
² Las soluciones del problema deben codi¯carse de una forma que resulte relativamente f¶
acil de implementar en la computadora. Dentro de las codi¯caciones, la m¶as
com¶
un y m¶
as sencilla de implementar es
la de cadenas binarias que es la que propuso John Holland, aunque se han utilizado tambi¶en n¶
umeros reales y letras.
Funcionamiento
El funcionamiento de un algoritmo gen¶etico se
puede mostrar con el siguiente fragmento de
pseudoc¶
odigo:
inic ia
i:=0 ;
g e ne ra po bla c i¶o n inic ia l(Pi);
se le c c io na indiv iduo s de Pi;
c ruz a indiv iduo s se le c c io na do s de Pi;
muta indiv iduo s de Pi;
Re pite
i:=i+1 ;
g e ne ra po bla c i¶o n (Pi) usa ndo Pi{ 1 ;
se le c c io na indiv iduo s de Pi;
c ruz a indiv iduo s se le c c io na do s de Pi;
muta indiv iduo s de Pi;
H a sta
q ue
e nc ue ntre s una
\ bue na
c i¶o n"
te rmina
so lu-
Primero, se genera aleatoriamente una poblaci¶
on inicial, que estar¶
a formada por un conjunto de cromosomas (com¶
unmente es una cadena de bits de longitud ¯ja). Como segundo paso se hace una selecci¶
on de individuos de esta poblaci¶
on, un m¶etodo simple para hacer dicha selecci¶
on, es el usado por Goldberg, D.E.
(1989). Este m¶etodo es el de la ruleta, y consiste en crear una ruleta en la que cada cromosoma tiene asignado un valor proporcional a su aptitud. Por ejemplo, suponga que se tiene una poblaci¶
on de 5 cromosomas cuyas aptitudes est¶an
dadas por los valores y porcentajes que se muestran en la Tabla 1.
Con los porcentajes de la tabla se puede elaborar una ruleta como se muestra en la Figura 4.
Esta ruleta se gira n veces para determinar qu¶e
individuos se seleccionar¶
an. L¶
ogicamente, como
a los individuos m¶
as aptos se les asign¶
o un ¶
area
mayor de la ruleta, se espera que se les seleccione m¶
as veces que los menos aptos.
M¶etodos heur¶³sticos de optimizaci¶on. Rosa Irma Hern¶
andez D. y Sergio G. de los Cobos S.
11
No. de cromosoma Cadena de bits Aptitud % del total
1
11010110
70
5
2
10000111
154
11
3
00110100
448
32
4
01110010
518
37
5
11110110
210
15
Total
1400
100.0
Tabla 1. Aptitudes de los cromosomas.
Figura 4. Ruleta de aptitudes.
Una vez realizada la selecci¶on, el siguiente paso es la reproducci¶
on o cruza de los individuos seleccionados. En este paso, los seleccionados (sobrevivientes) intercambian material cromos¶
omico (bits) y sus descendientes formar¶
an
la poblaci¶on de la siguiente generaci¶on.
Existen formas comunes de reproducci¶
on como
son las siguientes: uso de un punto u
¶nico de
cruza y uso de dos puntos de cruza.
Con el uso de un solo punto de cruza entre dos
individuos, cada pareja de cromosomas da origen a dos descendientes para la siguiente generaci¶
on, el punto de cruza puede ser cualquiera de los dos extremos de la cadena, en cuyo caso no se realiza la cruza.
Con el uso de dos puntos de cruza entre dos individuos, en este caso se mantienen los genes de
los extremos, y se intercambian los del centro,
aqu¶³ tambi¶en existe la posibilidad de que uno o
ambos puntos de cruza se encuentren los de la
cadena, en cuyo caso se har¶a una cruza usando un solo punto, o ninguna cruza seg¶
un corresponda.
El siguiente paso, es el operador llamado mutaci¶
on, el cual realiza un cambio uno de los genes (un bit) de un cromosoma elegido aleatoriamente, en este caso un bit se sustituye por
su complemento (un uno cambia en cero y vice-
versa). La mutaci¶
on permite la introducci¶on de
nuevo material cromos¶
omico en la poblaci¶on generada con la cruza.
Generalmente la cruza y la mutaci¶
on se maneja dentro de la implementaci¶
on del algoritmo
gen¶etico como un porcentaje que indica con qu¶e
frecuencia se efectuar¶
a, en el caso de la cruza esto signi¯ca que no todas las parejas de cromosomas se cruzar¶
an, que habr¶
a algunas de ellas que
pasar¶
an intactas a la siguiente generaci¶on, hasta que una pareja mejor la desplace. Cabe hacer
notar que la frecuencia con que se efect¶
ua la cruza es mucho mayor que la mutaci¶
on, ya que ¶esta
s¶
olo se realiza de manera espor¶
adica.
>Cu¶
ando se debe detener el algoritmo gen¶etico?
Generalmente, se ejecuta el algoritmo durante un n¶
umero m¶
aximo de generaciones o cuando la poblaci¶
on se haya hecho estable, es decir, cuando la mayor¶³a de los individuos tengan una aptitud similar.
Para un problema de optimizaci¶
on a solucionar con un algoritmo gen¶etico, se puede consultar la p¶
agina de internet de Coello, en donde
se muestran resultados interesantes, dado que
se logra encontrar la soluci¶
on ¶
optima con un
\buen"tiempo.
5. Redes Neuronales
>Reconocimiento de patrones y optimizaci¶on?
S¶³, ¶estas tan s¶
olo son dos de las aplicaciones de
las redes neuronales arti¯ciales. Por ejemplo, >se
imagina las consecuencias que habr¶³a si le hicieran un diagn¶
ostico m¶edico, en el que le digan que tiene un tipo de c¶
ancer benigno cuando la realidad lo que tiene es un c¶
ancer maligno? >O se imagina lo que pasar¶³a en el campo de batalla, si en un combate a¶ereo se quisiera destruir a las naves enemigas, y al identi¯carlas (reconocerlas) y apuntar a ellas no se tratara del enemigo si no de una nave aliada? Pues
bien, he aqu¶³ la importancia del reconocimiento
de patrones, claro junto con la optimizaci¶on, para as¶³ poder obtener los mejores resultados. Pero, veamos de d¶
onde surgieron y en qu¶e consisten las redes neuronales arti¯ciales.
12
ContactoS 31, 5{16 (1999)
En 1936, Alan Turing fue el primero en estudiar el modelo humano como una forma de ver
el mundo de la computaci¶on. Ahora bien, quienes establecieron los fundamentos de la computaci¶
on Neuronal fueron el neuro¯si¶ologo Warren McCulloch, y el matem¶atico Walter Pitts,
¶estos proporcionaron en 1943 una teor¶³a acerca
de c¶
omo trabajaban las neuronas y adem¶as modelaron una red neuronal simple mediante circuitos el¶ectricos. En 1957, Frank Rossenblant
desarroll¶
o el modelo de una red neuronal, llamada el Perceptr¶on que es la m¶as antigua red
neuronal, y que se usa hoy en d¶³a como reconocedor de patrones. En 1959, Widrow y Marofal Ho®, desarrollaron la primera red neuronal, llamada ADALINE que se aplic¶o a un problema real que consist¶³a en eliminar ecos en las
l¶³neas telef¶
onicas.
Hoy en d¶³a, se siguen realizando muchos trabajos e investigaciones acerca de las redes neuronales, as¶³ como el hecho de que hay y surgen productos nuevos tanto hardware como software sobre todo para la simulaci¶on.
Bases de las redes Neuronales.
Uno de los ¶organos m¶as poderosos conocidos por
el hombre es el cerebro humano, por ejemplo
un peque~
no ni~
no es capaz de realizar de manera f¶
acil acciones que superan por mucho a la capacidad de la computadora m¶as so¯sticada: reconocimiento de docenas de caras y objetos desde diferentes ¶angulos y en diferentes condiciones
(luz, etc.). Pues bien, las redes neuronales arti¯ciales en cuanto al aspecto te¶orico y modelado est¶
an inspiradas en la estructura y funcionamiento del cerebro, donde la neurona es el elemento fundamental. El cerebro humano consiste de un gran n¶
umero de neuronas, interconectadas masivamente, se calcula que como promedio hay del orden de diez billones de neuronas
en el cerebro humano con un promedio de miles de conexiones por cada una. La neurona es
una c¶elula viva y en general, consta de un cuerpo celular, del que salen ramas, una que es la
rama principal llamada ax¶on, y otras m¶as cortas, llamadas dendritas. Ver Figura 5.
Se puede mencionar que una neurona est¶
a formada por tres partes: su cuerpo celular, sus estructuras de entradas (las dendritas) y su estructura de salida (el ax¶on). Algo importante de
las neuronas es que tienen la capacidad de comunicarse, esto se puede describir en t¶erminos
generales de la siguiente manera: el cuerpo
celular y las dendritas reciben se~
nales de entrada, estas se~
nales son combinadas e integradas por el cuerpo celular que da como resul-
Figura 5. Estructura de una neuronas.
tado que se emitan se~
nales (el¶ectricas) de salida. El ax¶
on es el encargado de transportar
las se~
nales (el¶ectricas) de salida a los terminales ax¶
onicos, que se encargan a su vez de distribuir las se~
nales recibidas a un nuevo conjunto de
neuronas; la se~
nal que se transmite entre los terminales ax¶
onicos de una neurona y las dendritas de las neuronas siguientes es de tipo qu¶³mico.
Cabe mencionar tambi¶en a los puntos de conexi¶
on con otras neuronas, llamados sinapsis, que
tienen la funci¶
on de receptor y est¶
an localizados entre los terminales ax¶
onicos y las dendritas de la neurona siguiente, por lo tanto se puede decir que las se~
nales electro{qu¶³micas se propagan por las neuronas desde sus sinapsis hacia otras neuronas. Algo que se debe hacer notar es el hecho de que una neurona recibe informaci¶
on de otras miles de neuronas, y a su vez
env¶³a informaci¶
on a miles de neuronas m¶
as.
Existen dos tipos de sinapsis: las sinapsis excitadoras y las sinapsis inhibidoras. Casi todas las
neuronas reciben entradas procedentes de ambas sinapsis, es decir, en cada instante algunas
neuronas estar¶
an activas y otras se hallar¶
an en
reposo; la suma de los efectos excitadores e inhibidores determinar¶
an si la neurona ser¶
a o no estimulada; es decir, si emitir¶
a o no impulsos y a
qu¶e velocidad.
De¯nici¶
on
Las redes neuronales arti¯ciales son modelos
computarizados que intentan reproducir el comportamiento del cerebro, dichos modelos funcio-
M¶etodos heur¶³sticos de optimizaci¶on. Rosa Irma Hern¶
andez D. y Sergio G. de los Cobos S.
nan bajo procesamiento paralelo y adaptativo.
Por lo tanto, se podr¶³an de¯nir a las redes neuronales arti¯ciales como un sistema de computaci¶
on formado por un gran n¶
umero de elementos
simples, elementos de proceso muy interconectados, los cuales procesan informaci¶on por medio de su estado din¶amico como respuesta a entradas externas [Hecht{Niesen 1988a].
Cabe mencionar que en las redes neuronales
biol¶
ogicas, las neuronas corresponden a los elementos simples de proceso mencionados en la
de¯nici¶
on anterior.
En cuanto a la construcci¶on de redes neuronales arti¯ciales, ¶estas pueden ser construidas con
hardware especial (sobre todo con base en procesamiento paralelo) o simuladas en computadoras normales. Sin embargo, actualmente el
hardware especial no es lo que m¶as se usa, sino m¶
as bien lo m¶as com¶
un es hacer simulaci¶
on
de redes neuronales, por medio de computadoras digitales.
Aplicaciones
Las redes neuronales pueden utilizarse en un
gran n¶
umero y variedad de aplicaciones, tanto comerciales como militares. Entre las principales aplicaciones son para el reconocimiento de patrones y para el procesado de se~
nales.
Sin embargo han encontrado gran ¶exito en aplicaciones como la visi¶on arti¯cial, en el procesado de se~
nales e im¶agenes, reconocimiento del habla y de caracteres, sistemas expertos, an¶
alisis
de im¶
agenes m¶edicas, control remoto, control
de robots, inspecci¶on industrial, y exploraci¶
on
cient¶³¯ca. En general, las aplicaciones de las
redes neuronales se pueden clasi¯car en: asociaci¶
on y clasi¯caci¶on, regeneraci¶on de patrones, regresi¶on y generalizaci¶on, y optimizaci¶
on.
A continuaci¶on se mencionan de manera breve dos de estas clasi¯caciones que se consideran importantes.
Asociaci¶
on y clasi¯caci¶
on: Aqu¶³ la idea es que
los patrones de entrada est¶aticos deben ser clasi¯cados, este trabajo lo har¶a una red neuronal, la cual debe ser entrenada para que cuando se le presente una versi¶on distorsionada ligeramente del patr¶on base, pueda reconocerla
correctamente sin problemas, por ejemplo, debe ser capaz de recuperar una se~
nal \limpia"de
ambientes o canales ruidosos. En muchos problemas de clasi¯caci¶on, la cuesti¶on a solucionar
es la recuperaci¶on de informaci¶on, esto es, recuperar el patr¶on original, dada una informaci¶
on parcial del patr¶on deseado.
Optimizaci¶
on:
Las redes neuronales son
una herramienta tambi¶en para la optimi-
13
zaci¶
on de aplicaciones, que normalmente implican la b¶
usqueda del m¶³nimo absoluto de una funci¶
on de energ¶³a.
Hablando en t¶erminos de disciplinas espec¶³¯cas,
por ejemplo, en una empresa las aplicaciones
consisten en la optimizaci¶
on de plazas y horarios en l¶³neas de vuelo, en la explotaci¶
on de una
base de datos, reconocimiento de caracteres escritos, etc. En ¯nanzas, las aplicaciones consisten en la identi¯caci¶
on de falsi¯caciones, interpretaci¶
on de ¯rmas, etc. En el medio ambiente, analizar tendencias y patrones, previsi¶on de
tiempo, etc. En medicina, predicci¶
on de reacciones adversas a los medicamentos, diagn¶osticos
de tratamiento a partir de s¶³ntomas y/o de datos anal¶³ticos, monitorizaci¶
on en cirug¶³a, etc. En
el aspecto militar, clasi¯caci¶
on de las se~
nales de
radar, creaci¶
on de armas inteligentes, optimizaci¶
on del uso de recursos escasos, reconocimiento y seguimiento en el tiro al blanco.
Las redes neuronales se usan como ¯ltros para
la eliminaci¶
on de ruidos , des¶
ordenes en se~
nales,
por ejemplo, la red backpropagation (propagaci¶
on hac¶³a atr¶
as) se usa a menudo para obtener una versi¶
on de ruido{ reducido a partir de
una se~
nal de entrada, y la red MADALINE se
ha usado por d¶ecadas para mejorar la transmisi¶
on telef¶
onica comercial.
Otra aplicaci¶
on interesante es la segmentaci¶on
de datos, que es una tarea muy solicitada, sobre todo en im¶
agenes, se~
nales de variaci¶
on temporal, por ejemplo, datos s¶³smicos. Actualmente existen numerosas aproximaciones de redes
neuronales habilitadas para segmentaci¶on de
im¶
agenes, la mayor¶³a de los cuales presentan
una capacidad superior en comparaci¶
on con alguno de los m¶
as complejos algoritmos de segmentaci¶
on.
Como se puede notar las redes neuronales arti¯ciales tienen in¯nidad de aplicaciones, por ultimo se comenta una de ellas a la que ya se
le han aplicado diferentes tipos de redes neuronales con prometedores resultados: la compresi¶
on de datos. Esta aplicaci¶
on es importante en
areas donde se producen, se transmiten y al¶
macenan enormes cantidades de datos, tales como la medicina. Por tal raz¶
on, se busca aplicar y
desarrollar la metodolog¶³a de compresi¶
on de datos, ya que el costo de los dispositivos de almacenamiento masivo es elevado.
De todas las aplicaciones mencionadas se puede
ver que tienen hechos en com¶
un; la mayor¶³a consisten en realizar un reconocimiento de patrones: buscar un patr¶
on en una serie de patrones,
clasi¯car patrones, completar una se~
nal a par-
14
ContactoS 31, 5{16 (1999)
tir de valores parciales o reconstruir el patr¶
on
correcto partiendo de uno distorsionado.
Componentes de una red neuronal arti¯cial.
Hilera y Mart¶³nez, (1995) apuntan que los componentes b¶
asicos generales de toda red neuronal arti¯cial son los siguientes:
² \Unidades de procesamiento (neurona arti¯cial)
² Estado de activaci¶on de cada neurona.
² Patr¶
on de conectividad entre neuronas.
² Regla de propagaci¶on.
² Funci¶
on de salida o transferencia.
² Regla de activaci¶on.
² Regla de aprendizaje"
A continuaci¶on se describir¶a de manera breve en
qu¶e consisten estos componentes. Unidades de
procesamiento.- Cualquier modelo de red neuronal consta de unidades elementales de proceso: las neuronas. El trabajo de una neurona consiste en recibir las entradas de las neuronas vecinas y calcular un valor de salida, el
cual es enviado a todas las neuronas restantes. Generalmente, se pueden encontrar tres tipos de neuronas. Neuronas de entrada: aquellas que reciben est¶³mulos externos, relacionadas con el aparato sensorial u otros sectores del
sistema, que tomar¶an la informaci¶on de entrada. Neuronas ocultas: la informaci¶on de entrada se transmite a estas unidades ocultas que se
ocupan de su procesado. Es en la sinapsis y neuronas ocultas donde se genera cualquier tipo de
representaci¶on interna de la informaci¶on recibida. El nombre de neurona oculta se debe a que
no tienen ninguna relaci¶on directa con la informaci¶
on de entrada ni con la de salida. Neuronas de salida: estas unidades reciben la informaci¶
on una vez que ha sido procesada, su misi¶
on principal es enviar la se~
nal (respuesta) fuera del sistema.
El estado de activaci¶
on.- Todas las neuronas que
componen la red se hallan en cierto estado en
un tiempo t, se puede decir que hay dos posibles estados de activaci¶on: reposo y excitado, y
a cada uno de los cuales se les designa un valor (continuo o discreto). Los estados de activaci¶
on que tendr¶an cada una de las neuronas
depender¶
a en parte de la se~
nal que env¶³a cada una de las neuronas vecinas. Tambi¶en se pude decir que la se~
nal que env¶³a cada neurona a
sus neuronas vecinas depende de su propio estado de activaci¶on
Funci¶
on de salida o de transferencia.- Entre las
neuronas que forman una red neuronal arti¯cial existe un conjunto de conexiones que unen
unas neuronas con otras. Cada neurona env¶³a
su se~
nal a las neuronas con las que se encuentra conectada. Por lo tanto, la funci¶
on de salida lo que hace es transformar el estado actual de
activaci¶
on (de una neurona) en una se~
nal de salida. En algunas redes esta se~
nal de salida es igual
al estado de activaci¶
on de la neurona, en cuyo caso la funci¶
on de salida, es la funci¶
on identidad. Existen otros tipos de funciones de salida, como lo son: la funci¶
on lineal, sigmoidal,
etc. Para m¶
as detalle acerca de ¶estas ver (Hilera y Mart¶³nez, 1995).
Regla de propagaci¶
on.- Esta regla tiene que ver
con la manera en que se combinan todos los valores de entrada (los valores de salida de sus
neuronas vecinas) a una neurona con los pesos de las conexiones que llegan a esa neurona. En t¶erminos m¶
as claros se puede decir: que
todas las conexiones que unen a las neuronas
en una red neuronal tienen asociado un peso,
que es el que ¯nalmente hace que la red adquiera conocimiento. Ahora bien, si se considera como yi el valor de salida de la neurona i en un
tiempo ti dado; y como wij el peso de la conexi¶
on (sinapsis) entre la neurona i y j, entonces se puede decir que la entrada neta En que recibe la neurona j en el tiempo tj es la suma
del producto de cada se~
nal individual por el valor de la sinapsis que conecta a ambas neuronas
EN =
X
i
wij ¤ yi :
Regla de activaci¶
on.- Esta regla consiste en combinar el valor total de las entradas con el estado actual de la neurona, para que se produzca un nuevo estado de activaci¶
on de la neurona. Dado el estado actual de activaci¶
on de una
neurona ai (t) de la neurona i y la entrada total que llega a ella, el estado de activaci¶
on siguiente ai (t+1) de la neurona i, se obtiene aplicando la regla de activaci¶
on.
Regla de aprendizaje.- (Hilera y Mart¶³nez, 1995)
dice \Biol¶
ogicamente, se suele aceptar que la informaci¶
on memorizada en el cerebro est¶
a m¶as
relacionada con los valores sin¶
apticos de las conexiones entre las neuronas que con ellas mismas; es decir, el conocimiento se encuentra en
las sinapsis". Pues bien, en el caso de las redes neuronales arti¯ciales se puede decir lo mismo, ya que como se mencion¶
o anteriormente, los
pesos que tienen asociados las conexiones son
M¶etodos heur¶³sticos de optimizaci¶on. Rosa Irma Hern¶
andez D. y Sergio G. de los Cobos S.
los que hacen que la red adquiera conocimiento. En s¶³, se puede decir que la red aprende modi¯cando los valores de los pesos de las conexiones de la red misma.
Formas de aprendizaje
El proceso de aprendizaje de una red neuronal
consiste en modi¯car los pesos de las conexiones en respuesta a una informaci¶on de entrada. Estas modi¯caciones que se producen consisten en la destrucci¶on, modi¯caci¶
on y creaci¶
on de conexiones entre las neuronas, por ejemplo la creaci¶on de una nueva conexi¶
on implica que el peso de la misma pasa a tener un valor distinto de cero, de la misma forma la destrucci¶
on de una conexi¶on sucede cuando el peso pasa a ser cero.
Algo importante que se puede decir es que la red
ha aprendido cuando los pesos de las conexiones
permanecen estables.
Los criterios que se siguen para modi¯car los pesos se conoce como regla de aprendizaje de la
red. Por lo general, se manejan dos tipos de reglas: con aprendizaje supervisado y aprendizaje no supervisado. La diferencia principal entre las redes que manejan aprendizaje supervisado y las que no lo manejan, consiste en la
existencia o no de un agente externo, un supervisor que controle el proceso de aprendizaje a la red.
El proceso de aprendizaje supervisado, se caracteriza porque se realiza mediante un entrenamiento controlado por un supervisor, que es
el que determina la respuesta que deber¶³a generar la red a partir de una entrada de informaci¶
on, el supervisor veri¯ca la respuesta (salida) de la red y en caso de que no coincida
con lo deseado, se proceden a modi¯car los pesos de las conexiones.
Las redes con aprendizaje no supervisado no requieren la in°uencia externa de un supervisor
para ajustar los pesos de las conexiones, por lo
tanto, la red no recibe ninguna informaci¶
on externa que le indique si la respuesta que gener¶
o es
o no correcta. Lo que deben de hacer estas redes es autoorganizarse, es decir, deben encontrar las caracter¶³sticas, regularidades, correlaciones o categor¶³as que se puedan establecer entre los datos de entrada. En algunos casos la
salida representa el grado de familiaridad entre la informaci¶on de entrada y las entradas que
se han mostrado antes.
Por u
¶ltimo, se puede comentar de manera breve acerca de este proceso de aprendizaje: primero la red empieza a trabajar con un conjun-
15
to de muestras, en donde dichas muestras deben re°ejar todas las condiciones de entrada
que est¶
an asociadas con la salida deseada. Posteriormente, \se le adiestra", y una vez adiestrada se le pone a trabajar para reconocer, clasi¯car, etc., nueva informaci¶
on.
Bibliograf¶³a
1. CONDOR (Committee on the Next Decade
of Operation Research), Operations Research:
The Next Decade. Operations Research, 36,
1988.
2. De los Cobos Silva Sergio, La t¶ecnica de la
b¶
usqueda Tab¶
u y sus aplicaciones, Ingenier¶³a,
LV11[ 4 ], 247{256,1997.
3. De los Cobos Silva S., Gonz¶
alez S.F. y Aceves G.
R., Formas Inteligentes de Resolver Problemas
Dif¶³ciles, Universidad Michoacana, [ 12 ], 49{64,
1994.
4. Glover F. Future Paths for Integer Programming and Links to Arti¯cial Intelligence, Computers and Operations Research, 533{549,1986.
5. Goldberg,D.E., Genetic Algorithms in Search,
Optimization and Machine Learning, Addison
Wesley Publishing Company, 1989, p.412.
6. Guti¶errez Andrade M. A., La t¶ecnica del recocido simulado y sus aplicaciones, Tesis de Doctorado, DEPFI{Universidad Nacional Aut¶onoma
de M¶exico. Ciudad Universitaria, M¶exico,1991.
7. Hansen P., The steepest Ascent Mildest Descendent Heuristic for Combinatorial Programming. Congress on Numerical Methods in Combinatorial Optimization, Capri, Italia, 1986.
8. Hilera Jos¶e y Mart¶³nez V¶³ctor. Redes Neuronales Arti¯ciales. Fundamentos, modelos y aplicaciones. Addison{Wesley Iberoamericana, Espa~
na, 1995, p.9,45{68.
9. http://www.fciencias.unam.mx/
revista/soluciones/N17/Coello2.html
10. Koza, J,R., Genetic Programming of Computers
by Means of Natural Seletion. The MIT Press,
1992, p. 819
11. Laguna M., Barnes J. W. and Glover F., Tabu Search for a Single Machine Scheduling Problem. Technical report (july), Advanced Knowledge Systems Group of U. S., West Advanced
Technologies, 1991.
16
ContactoS 31, 5{16 (1999)
12. P¶erez S., De los Cobos S., Ordorica M. y Guti¶errez A., M¶etodos heur¶³sticos de optimizaci¶
on
en la gran industria nacional. Reporte de investigaci¶
on, de CBI, UAM{Iztapalapa, 1996.
13. Ponce de Le¶on Sent¶³, E., Algoritmos Gen¶eticos
y su aplicaci¶
on a problemas de secuenciaci¶
on.
Tesis Doctoral, Instituto de Cibern¶etica Matem¶
atica y F¶³sica, Centro de Inteligencia Arti¯cial, La Habana Cuba, 1997.
cs