evidencia
empírica
de
que
se
encuentran
soluciones
de
un
nivel
aceptable,
en
un
tiempo competitivo con el resto de algoritmos de optimización combinatoria.
En
el
caso
de
que
existan
técnicas
especializadas
para
resolver
un
determinado
problema, lo
mas
probable es que superen al AG, tanto en rapidez como en efica-
cia.
El
gran
campo
de
aplicación
de
los
AG
se
relaciona
con
aquellos
problemas
para
los
cuales
no
existen
técnicas
especializadas.
Incluso
en
el
caso
en
que
di-
chas técnicas existan, y funcionen bien,
pueden efectuarse
mejoras
de las
mismas
hibridandolas con los AG.
1.1.3.
¿Por qué utilizar Algoritmos Genéticos en la Optimización?
La
razón
del
creciente
interés
por
los
AG
es
que
estos
son
un
método
global
y
robusto de búsqueda de las soluciones de problemas. La principal ventaja de estas
características es el equilibrio alcanzado entre la eficiencia y eficacia para resolver
diferentes y
muy complejos problemas de grandes dimensiones.
Lo
que
aventaja
a
los
AG
frente
a
otros
algoritmos
tradicionales
de
búsqueda
es
que se diferencian de estos en los siguientes aspectos:
Trabajan
con
una
codificación
de
un
conjunto
de
parámetros,
no
con
los
parámetros
mismos.
Trabajan con un conjunto de puntos, no con un único punto y su entorno (su
técnica
de
búsqueda
es
global.)
Utilizan
un
subconjunto
del
espacio
total,
para obtener información sobre el universo de búsqueda, a través de las eva-
luaciones de la función a optimizar. Esas evaluaciones se emplean de forma
eficiente para clasificar los subconjuntos de acuerdo con su idoneidad.
No necesitan conocimientos específicos sobre el problema a resolver; es
decir, no están sujetos a restricciones. Por ejemplo, se pueden aplicar a fun-
ciones
no continuas, lo cual les abre
un amplio campo de aplicaciones que
no podrían ser tratadas por los métodos tradicionales.
Utilizan operadores probabilísticos, en vez
de los tipicos
operadores
deter-
minísticos de las técnicas tradicionales.
Resulta sumamente fácil ejecutarlos en las modernas arquitecturas masivas
en paralelo.
Cuando se usan para problemas de optimización, resultan
menos afectados
por
los
máximos
locales
que
las
técnicas
tradicionales
(i.e.,
son
métodos
robustos).
Ahora bien; un esquema del funcionamiento general de un algoritmo genético
podría ser el siguiente:
Algoritmo
Genetico :
-
Generar una población inicial.
-
Iterar hasta un criterio de parada.
-
Evaluar cada individuo de la población.
-
Seleccionar los progenitores.
-
Aplicar el operador de cruce y mutación a estos progenitores.
-
Incluir la nueva descendencia para formar una nueva generación.
1.1.4.
Ventajas
El primer y más importante punto es que los AG son intrínsecamente parale-
los. La
mayoría de los otros algoritmos son en serie y sólo pueden explorar
el espacio de soluciones hacia una solución en una dirección al
mismo tiem-
po, y si la solución que descubren resulta subóptima, no se puede hacer otra
cosa
que
abandonar
todo
el
trabajo
hecho
y
empezar
de
nuevo.
Sin
embar-
go, ya que los
AG tienen descendencia
múltiple, pueden explorar el espacio
de
soluciones
en
múltiples
direcciones
a
la
vez.
Si
un
camino
resulta
ser
un
callejón
sin
salida,
pueden
eliminarlo
fácilmente
y
continuar
el
trabajo
en
avenidas
más
prometedoras,
dándoles
una
mayor
probabilidad
en
cada
ejecución de encontrar la solución.
Sin
embargo,
la
ventaja
del
paralelismo
va
más
allá
de
esto.
Considere
lo
siguiente:
todas
las
cadenas
binarias
(cadenas
de
ceros
y
unos)
de
8
dígitos
forman
un
espacio
de
búsqueda,
que
puede
representarse
como
********
(donde
*
significa
“o
0
o
1”).
La
cadena
01101010
es
un
miembro
de
este
espacio. Sin embargo, también es un
miembro del espacio 0*******, del es-
pacio
01******, del espacio 0******0,
del espacio 0*1*1*1*, del espacio
10*01**0, etc. Evaluando la aptitud de esta cadena particular, un
AG esta-
ría
sondeando
cada
uno
de
los
espacios
a
los
que
pertenece.
Tras
muchas
evaluaciones,
iría
obteniendo
un
valor
cada
vez
más
preciso
de
la
aptitud
media
de
cada
uno
de
estos
espacios,
cada
uno
de
los
cuales
contiene
mu-
chos miembros. Por tanto, un
AG
que evalúe explícitamente un número pe-
queño
de
individuos
está evaluando
implícitamente
un
grupo
de
individuos
mucho
más
grande
-de
la
misma
manera
que
un
encuestador
que
le
hace
preguntas a un cierto
miembro de un
grupo étnico, religioso
o
social espera
aprender algo acerca de las opiniones de todos los
miembros de ese grupo, y
por tanto puede
predecir con fiabilidad la opinión nacional sondeando sólo
un pequeño porcentaje
de la población. De la
misma
manera, el
AG
puede
dirigirse hacia el espacio con los individuos más aptos y encontrar el mejor
de
ese
grupo.
En
el
contexto
de
los
algoritmos
evolutivos,
esto
se
conoce
como
teorema
del
esquema,
y
es
la
ventaja
principal
de
los
AG
sobre
otros
métodos de resolución de problemas.
Debido
al
paralelismo
que
les
permite
evaluar
implícitamente
muchos
es-
quemas a la vez, los
AG funcionan particularmente bien resolviendo proble-
mas cuyo espacio de soluciones potenciales es realmente grande -demasiado
vasto
para
hacer
una
búsqueda
exhaustiva
en
un
tiempo
razonable.
La
ma-
yoría
de
los
problemas
que
caen
en
esta
categoría
se
conocen
como
“no
lineales”.
En
un
problema
lineal,
la
aptitud
de
cada
componente
es
inde-
pendiente, por lo
que cualquier mejora en alguna parte
dará como resultado
una
mejora
en
el
sistema
completo.
No
es
necesario
decir
que
hay
pocos
problemas
como
éste
en
la
vida
real.
La
no
linealidad
es
la
norma,
donde
cambiar un componente puede tener efectos en cadena en todo el sistema, y
donde
cambios
múltiples
que,
individualmente,
son
perjudiciales,
en
com-
binación
pueden
conducir
hacia
mejoras
en
la
aptitud
mucho
mayores.
La
no
linealidad
produce
una
explosión
combinatoria:
el
espacio
de
cadenas
binarias de 1.000 dígitos
puede examinarse exhaustivamente evaluando só-
lo
2.000
posibilidades
si
el
problema
es
lineal,
mientras
que
si
no
es
lineal,
una
búsqueda
exhaustiva
requiere evaluar
21.000
posibilidades
-un
número
que, escrito, ocuparía
más de 300 dígitos.
Afortunadamente, el paralelismo implícito de los
AG les permite superar in-
cluso este enorme número de posibilidades, y encontrar con éxito resultados
óptimos o
muy buenos en un corto periodo de tiempo, tras muestrear
direc-
tamente
sólo
regiones
pequeñas
del
vasto
paisaje
adaptativo.
Por
ejemplo,
un
AG desarrollado en común
por ingenieros de General Electric y el Rens-
selaer
Polytechnic
Institute
produjo
el
diseño
de
la
turbina
de
un
motor
a
reacción de altas prestaciones que era tres veces
mejor que la configuración
diseñada
por
humanos,
y
un
50 %
mejor
que
una
configuración
diseñada
por un sistema experto que recorrió con éxito
un espacio de soluciones
que
contenía más de 10.387 posibilidades. Los métodos convencionales para di-
señar
estas
turbinas
son
una
parte
fundamental
de
proyectos
de
ingeniería
que
pueden
durar
hasta
cinco
años
y
costar
más
de
2.000
millones
de
dóla-
res;
el
AG
descubrió
esta
solución
en
dos
días,
en
una
estación
de
trabajo
de escritorio típica en ingeniería.
Otra
ventaja
notable
de
los
AG
es
que
se
desenvuelven
bien
en
problemas
con
un
paisaje
adaptativo
complejo
-aquéllos
en
los
que
la
función
objeti-
vo
es
discontinua,
ruidosa,
cambia
con
el
tiempo,
o
tiene
muchos
óptimos
locales.
La
mayoría
de
los
problemas
prácticos
tienen
un
espacio
de
solu-
ciones
enorme,
imposible
de
explorar
exhaustivamente;
el
reto
se convierte
entonces
en
cómo
evitar
los
óptimos
locales
-soluciones
que
son
mejores
que
todas
las
que
son
similares
a
ella,
pero
que
no
son
mejores
que
otras
soluciones
distintas
situadas
en
algún
otro
lugar
del
espacio
de
soluciones.
Muchos
algoritmos
de
búsqueda
pueden
quedar
atrapados
en
los
óptimos
locales:
si
llegan
a
lo
alto
de
una
colina
del
paisaje
adaptativo,
descubrirán
que
no
existen
soluciones
mejores
en
las
cercanías
y
concluirán
que
han
alcanzado
la
mejor
de
todas,
aunque
existan
picos
más
altos
en
algún
otro
lugar del mapa.
Los
algoritmos evolutivos,
por
otro
lado,
han
demostrado
su
efectividad
al
escapar
de
los
óptimos
locales
y
descubrir
el
óptimo
global
incluso
en
pai-
sajes adaptativos muy escabrosos y complejos. (Debe decirse que, en la
realidad,
a
menudo
no
hay
manera
de
decir
si
una
cierta
solución
a
un
pro-
blema
es
el
óptimo
global
o
sólo
un
óptimo
local
muy
alto.
Sin
embargo,
aunque
un
AG
no
devuelva
siempre
una
solución
perfecta
y
demostrable
a
un
problema,
casi
siempre
puede
devolver
al
menos
una
muy
buena
solu-
ción).
Todos
los
cuatro
componentes
principales
de
los
AG
-paralelismo,
selección,
mutación
y
cruzamiento-
trabajan
juntos
para
conseguir
esto.
Al
principio,
el
AG
genera
una
población
inicial
diversa,
lanzando
una
“red”
sobre
el
paisaje
adaptativo.
(Koza
2003[42],
p.
506)
compara
esto
con
un
ejército
de
paracaidistas
cayendo
sobre
el
paisaje
del
espacio
de
búsqueda
de
un
problema,
cada
uno
de
ellos
con
órdenes
de
buscar
el
pico
más
alto).
Pequeñas mutaciones permiten a cada individuo explorar sus proximidades,
mientras que la selección enfoca el progreso, guiando a la descendencia del
algoritmo
cuesta
arriba
hacia
zonas
más
prometedoras
del
espacio
de
solu-
ciones.
Sin
embargo,
el
cruzamiento
es
el
elemento
clave
que
distingue
a
los
AG
de
los
otros
métodos
como
los
trepacolinas
y
el
recocido
simulado.
Sin
el
cruzamiento,
cada
solución
individual
va
por
su
cuenta,
explorando
el
es-
pacio de búsqueda en sus inmediaciones sin referencia de lo
que el resto
de
individuos
puedan
haber
descubierto.
Sin
embargo,
con
el
cruzamiento
en
juego, hay una transferencia de información entre los candidatos prósperos
-los individuos pueden beneficiarse de lo que otros han aprendido, y los es-
quemas
pueden
mezclarse
y
combinarse,
con
el
potencial
de
producir
una
descendencia que tenga las virtudes de sus dos padres y ninguna de sus debi-
lidades. Este punto está ilustrado en
Koza et al. 1999[41], p. 486, donde los
autores
analizan
el
problema
de
sintetizar
un
filtro
de
paso
bajo
utilizando
programación
genética.
En
una
generación
se
seleccionaron
dos
circuitos
progenitores
para
llevar
a
cabo
el
cruzamiento;
un
padre
tenía
una
buena
topología
(componentes
como
inductores
y
condensadores
colocados
en
el
sitio correcto) pero malos tamaños (valores demasiado bajos de inductancia
y
capacidad
para los componentes). El otro padre tenía
mala topología pero
buenos
tamaños.
El
resultado
de
aparearlos
mediante
cruzamiento
fue
una
descendencia
con
la
buena
topología
de
un
padre
y
los
buenos
tamaños
del
otro,
dando
como
resultado
una
mejora
sustancial
de
la
aptitud
sobre
sus
dos padres.
El
problema
de
encontrar
el
óptimo
global
en
un
espacio
con
muchos
óp-
timos
locales
también
se
conoce
como
el
dilema
de
la
exploración
versus
explotación,
“un
problema
clásico
de
todos
los
sistemas
que
pueden
adap-
tarse
y
aprender”.
Una
vez
que
un
algoritmo
(o
un
diseñador
humano)
ha
encontrado
una estrategia
para resolver
problemas que parece funcionar sa-
tisfactoriamente, ¿debería centrarse en hacer el
mejor uso de esa estrategia,
o
buscar
otras?
Abandonar
una
estrategia
de
probada
solvencia
para
bus-
car otras nuevas casi
garantiza que supondrá una pérdida y
degradación del
rendimiento,
al
menos
a
corto
plazo.
Pero
si
uno
se
queda
con
una
estrate-
gia
particular excluyendo a todas las demás, corre el riesgo de no
descubrir
estrategias
mejores
que
existen
pero
no
se
han
encontrado.
De
nuevo,
los
AG
han
demostrado
ser
muy
buenos
en
dar
con
este
equilibrio
y
descubrir
buenas soluciones en un tiempo y esfuerzo computacional razonables.
Otra área en el que destacan los
AG es su habilidad para manipular muchos
parámetros
simultáneamente.
Muchos
problemas
de
la
vida
real
no
pueden
definirse en términos de un único valor que hay que minimizar o maximizar,
sino que
deben expresarse en términos de múltiples objetivos, a menudo in-
volucrando
contrapartidas:
uno
sólo
puede
mejorar
a
expensas
de
otro.
Los
AG son muy buenos resolviendo estos problemas: en particular, su uso
del
paralelismo
les
permite
producir
múltiples
soluciones,
igualmente
buenas,
al
mismo
problema,
donde
posiblemente
una
solución
candidata
optimiza
un
parámetro
y
otra
candidata
optimiza
uno
distinto
y
luego
un
supervisor
humano puede seleccionar una de esas candidatas para su utilización. Si una
solución
particular
a
un
problema
con
múltiples
objetivos
optimiza
un
pa-
rámetro
hasta el punto en el que ese parámetro
no puede
mejorarse
más sin
causar
una correspondiente
pérdida de calidad en algún otro
parámetro, esa
solución se llama óptimo paretiano o no dominada.
Finalmente, una de las cualidades de los AG que, a primera vista, puede pa-
recer
un
desastre,
resulta
ser
una
de
sus
ventajas:
a
saber,
los
AG
no
saben
nada
de
los
problemas
que
deben
resolver.
En
lugar
de
utilizar
información
específica conocida a priori para
guiar cada paso
y
realizar cambios con
un
ojo
puesto
en
el
mejoramiento,
como
hacen
los
diseñadores
humanos,
son
“relojeros ciegos”; realizan cambios aleatorios en sus soluciones candidatas
y
luego utilizan la función objetivo para determinar si esos cambios produ-
cen una mejora.
La
virtud
de
esta
técnica
es
que
permite
a
los
AG
comenzar
con
una
mente
abierta,
por
así
decirlo.
Como
sus
decisiones
están
basadas
en
la
aleatorie-
dad,
todos
los
caminos
de
búsqueda
posibles
están
abiertos
teóricamente
a
un
AG;
en
contraste,
cualquier
estrategia
de
resolución
de
problemas
que
dependa
de
un
conocimiento
previo,
debe
inevitablemente
comenzar
des-
cartando
muchos
caminos
a
priori,
perdiendo
así
cualquier
solución
nove-
dosa
que
pueda
existir.
Los
AG,
al
carecer
de
ideas
preconcebidas
basadas
en creencias establecidas sobre “cómo deben hacerse las cosas” o sobre
lo
que
“de
ninguna
manera
podría
funcionar”,
los
AG
no
tienen
este
pro-
blema.
De
manera
similar,
cualquier
técnica
que
dependa
de
conocimiento
previo
fracasará
cuando
no
esté
disponible
tal
conocimiento,
pero,
de
nue-
vo,
los
AG
no
se
ven
afectados
negativamente
por
la
ignorancia.
Mediante
sus componentes de paralelismo, cruzamiento y mutación, pueden viajar
extensamente por el paisaje adaptativo, explorando regiones que algoritmos
producidos
con
inteligencia
podrían
no
haber
tenido
en
cuenta,
y
revelan-
do
potencialmente
soluciones
de
asombrosa
e
inesperada
creatividad
que
podrían no
habérseles ocurrido
nunca a los
diseñadores
humanos. Un ejem-
plo
muy
gráfico
de
esto
es
el
redescubrimiento,
mediante
la
programación
genética,
del
concepto
de
retroalimentación
negativa
-un
principio
crucial
para
muchos
componentes
electrónicos
importantes
de
hoy
en
día,
pero
un
concepto
que,
cuando
fue
descubierto
en
primera
instancia,
se
le
denegó
Mister Wong
Portal para Investigadores y Profesionales
