Se puede definir Heurística
como un arte, técnica o procedimiento práctico o informal, para resolver
problemas. Alternativamente, se puede definir como un conjunto de reglas
metodológicas no necesariamente formalizadas, positivas y negativas, que
sugieren o establecen cómo proceder y problemas a evitar a la hora de generar
soluciones y elaborar hipótesis.
Es generalmente considerado que
la capacidad heurística es un rasgo característico de los humanos desde cuyo
punto de vista puede describirse como el arte y la ciencia del descubrimiento y
de la invención o de resolver problemas mediante la creatividad y el pensamiento
lateral o pensamiento divergente. Según el matemático George Pólya la base de
la heurística está en la experiencia de resolver problemas y en ver cómo otros
lo hacen. Consecuentemente se dice que hay búsquedas ciegas, búsquedas
heurísticas (basadas en la experiencia) y búsquedas racionales.
La palabra heurística procede del
término griego εὑρίσκειν, que significa «hallar, inventar» (etimología que
comparte con Eureka). La palabra «heurística» aparece en más de una categoría
gramatical. Cuando se usa como sustantivo, identifica el arte o la ciencia del
descubrimiento, una disciplina susceptible de ser investigada formalmente.
Cuando aparece como adjetivo, se refiere a cosas más concretas, como
estrategias heurísticas, reglas heurísticas o silogismos y conclusiones
heurísticas. Claro está que estos dos usos están íntimamente relacionados ya
que la heurística usualmente propone estrategias heurísticas que guían el
descubrimiento.
La robótica trata de cubrir todos
los temas necesarios para programar un robot con inteligencia artificial en
aplicaciones de sensado y planificación de rutas para dar solución a un
problema. A través del tiempo, el campo de la robótica se ha transformado, al
pasar de máquinas rústicas hasta la construcción de humanoides, que permiten
resolver tareas sencillas o complicadas.
Algunos de estos robots, se han
construido basándose en el comportamiento de seres vivos dándole un toque sutil
del raciocinio. No sólo la parte física y de comportamiento se ha basado en la
vida, sino también los algoritmos que controlan dichos robots, los cuales nos
dan una mayor posibilidad de encontrar soluciones a problemas difíciles de
resolver para el ser humano.
Algunas de las técnicas que
involucran procedimientos de búsqueda en el espacio de soluciones factibles.
Búsqueda local.
Los algoritmos de búsqueda local
parten de una solución inicial y
aplicándole operadores de variación, la van alterando; si la solución alterada
es mejor que la original, se acepta, si no lo es, se vuelve a la inicial. El
procedimiento se repite hasta que no se consigue mejora en la solución. Los
procedimientos de búsqueda local más usados son los basados en el gradiente: en
este caso, el operador de variación selecciona una nueva solución teniendo en
cuenta la derivada de la función que se quiere optimizar en el punto, tratando
de ascender o descender usando el gradiente hasta llegar a un punto de
inflexión donde no se puede obtener ninguna mejora adicional.
Métodos que usan soluciones parciales.
Estos métodos van construyendo soluciones
variables a variable, no obteniendo una solución completa al problema hasta que
todas las variables han sido asignadas. Uno de los métodos más conocidos son
los algoritmos voraces o greedy, que funcionan de la forma siguiente: para cada
variable, se asigna aquél valor que maximice alguna función de utilidad.
En el caso del TSP, un algoritmo
voraz comenzaría con una ciudad elegida aleatoriamente, y elegiría la ciudad
más cercana a ésta. Para esta segunda ciudad, elegiría la más cercana, y así
sucesivamente.
En este caso, el problema estaría
simplemente parametrizado con la ciudad inicial elegida. Los algoritmos voraces
sustituyen un criterio de optimalidad global por un criterio en cada paso; no
siempre los dos se corresponden, y por tanto, no tienen porqué hallar el máximo
global del problema.
Otros métodos consisten en
dividir el problema general en problemas más simples, y hallar la solución a
estos problemas más simples; el método se denomina divide y vencerás; en
algunos casos, la solución a un problema de orden n puede venir resolver a otro
problema de orden n-1, tal como sucede, por ejemplo en el conocido problema de
las torres de Hanói. Ejemplo branch and bound. Algunos métodos consisten en ir
descartando partes del espacio de búsqueda, con el objeto de acotar cada vez
más la solución al problema.
El branch and bound. Este método
imagina el espacio de búsqueda como un árbol de decisión; en cada paso del
algoritmo, se toma la decisión de podar las ramas del árbol que parezcan menos
prometedoras.
Este método procede de la forma
siguiente: se establece una cota inferior a la posible solución (o superior, si
se trata de minimizar). Se va siguiendo una rama del árbol, hasta que se
encuentra que la solución parcial es menor que esa cuota; en ese caso, se
descarta la rama completa.
En el caso del recorrido del
viajante, supongamos que hemos establecido que la cota superior es 200 Km. Se
establece un árbol de la forma siguiente: tomando una ruta entre dos ciudades,
pongamos AB, se establecen dos ramas para una posible solución con y sin esa
ruta; a partir de ahí, se hace lo mismo con el resto de las rutas.
Se van recorriendo las ramas, y
si se encuentra que la suma parcial de las rutas supera los 200 Km, se elimina
esa rama y ya no se sigue recorriendo. Si se ha organizado el espacio de
búsqueda en forma de árbol, puede resultar importante la ordenación de las
ramas, porque si se consigue colocar las ramas "mejores" antes, el
algoritmo será capaz de encontrar la solución con más rapidez. Algoritmos como él
A* toman este tipo de enfoque. En este algoritmo, se usa un método
mejor-primero para recorrer las ramas, y un método heurístico para estimar el
coste de las ramas que quedan por recorrer. La principal diferencia con el
método anterior es que se usan heurísticas para estimar valores de las ramas
restantes, en vez de valores exactos.
Estos métodos se pueden extender
también a problemas de optimización numérica, en cuyo caso
darían cotas entre las cuales se
moverían las soluciones. Pero si el espacio de búsqueda no se puede enumerar
bien, o si existe un número de variables excesivo, este tipo de algoritmos no
suelen funcionar bien.
Hillclimbing
Estos procedimientos se suelen
llamar de hillclimbing, o de escalado de colinas; el mayor truco en ellos consiste
en escoger correctamente el tamaño de paso para ascender y el punto de inicio.
Pero se trata de algoritmos de búsqueda locales, y, como tales, sólo van a
encontrar el máximo local más cercano al punto de inicio. Esto se puede resolver usando una estrategia
de multicomienzo, pero, en todo caso, no te garantizan que se encuentre, o
incluso de acerque uno, al máximo global. En todo caso, tiene la ventaja de
que, en cada iteración del algoritmo, se tiene una solución válida, aunque no
tiene porqué ser la mejor. En el caso del TSP, un procedimiento de búsqueda
local se denomina 2-opt. Consiste en escoger una permutación inicial aleatoria,
e ir probando con todas las posibles soluciones en la vecindad de esta,
entendiendo como vecindad el conjunto de todos los recorridos que pueden ser
alcanzados intercambiando dos caminos no adyacentes en el recorrido original.
Un recorrido reemplaza al original si es mejor; una vez que no se puede mejorar
un recorrido, se considera óptimo y se da como solución.
El mejor algoritmo de búsqueda
local conocido para el recorrido del viajante es el llamado Lin-Kernighan. Es
una variación del anterior, permitiendo el número de caminos a intercambiar en
cada iteración variar; además, en vez de tomar cualquier mejora, prueba varias y
se queda con la mejora de más valor.
Recocido Simulado
El recocido simulado o algoritmo
de los Dioses (es un escalador estocástico). Se basa en el proceso de recocido,
en la cual los metales se funden y se forjan a la par que se enfrían, hasta
conseguir una estructura cristalina, dura y resistente.
Éste método realiza una búsqueda
global que requiere de una “temperatura” inicial, una final y una función de
variación de la temperatura. Consiste en un ascenso de gradiente comenzando en
un punto aleatorio; dependiendo de la temperatura es como se mueve por el
espacio de búsqueda. La probabilidad de escoger una solución peor que la
actual, desciende con el tiempo; la solución (se aproxima a la solución óptima)
se escoge de manera determinista evitando los mínimos locales.
Iteración básica
En cada iteración, el método de
recocido simulado evalúa algunos vecinos del estado actual s y
probabilísticamente decide entre efectuar una transición a un nuevo estado s' o
quedarse en el estados. En el ejemplo de recocido de metales descrito arriba,
el estado s se podría definir en función de la posición de todos los átomos del
material en el momento actual; el desplazamiento de un átomo se consideraría
como un estado vecino del primero en este ejemplo. Típicamente la comparación
entre estados vecinos se repite hasta que se encuentre un estado óptimo que
minimice la energía del sistema o hasta que se cumpla cierto tiempo
computacional u otras condiciones.
Vecindario de un estado
El vecindario de un estados está
compuesto por todos los estados a los que se pueda llegar a partir de s
mediante un cambio en la conformación del sistema. Los estados vecinos son
generados mediante métodos de Montecarlo.
El método de evaluación de
estados vecinos es fundamental para encontrar una solución óptima global al
problema dado. Los algoritmos heurísticos, basados en buscar siempre un estado
vecino mejor (con energía más baja) que el actual se detienen en el momento que
encuentran un mínimo local de energía. El problema con este método es que no
puede asegurar que la solución encontrada sea un óptimo global, pues el espacio
de búsqueda explorado no abarca todas las posibles variaciones del sistema.
Búsqueda Tabú
La búsqueda tabú fue propuesta
por Glover, Taillard y de Werra. El método es utilizado para resolver problemas
complejos de optimización. Esta técnica, en realidad es una meta-heurística,
que guiará a otras técnicas para
que no se quede en óptimos locales. También ayuda a la resolución de problemas
combinatorios.
La búsqueda Tabú, explora el
espacio de búsqueda de todas las soluciones por medio de movimientos que se
harán sólo si la solución siguiente es mejor que la anterior. Para que esta
técnica no quede atrapada en un óptimo local o se generen movimientos cíclicos
la búsqueda tabú utiliza una “memoria” (lista taboo) en donde se almacenan las
soluciones examinadas recientemente, volviéndose prohibidas para el siguiente
movimiento que se realizará. También, registra los atributos más comunes de un
conjunto de soluciones para buscar en la zona que le corresponde y a largo
plazo se extiende sobre regiones no exploradas.
Conceptos Básicos de Búsqueda Tabú
Los orígenes de la búsqueda tabú
se ubican a fines de los 60s y principios de los 70s, y se atribuye a Fred
Glover, quien desarrolló esta heurística para tratar de resolver problemas de
cubierta no lineal (nonlinear covering), aunque varios de sus principios
también fueron delineados independientemente por P. Hansen. La búsqueda tabú
surgió como un dispositivo que permitiría implementar una estrategia para
resolver problemas de programación entera con restricciones sustitutas
(surro-gate constraints), y aunque su
planteamiento original ha sufrido varios cambios a través de los años, la idea
básica propuesta por Glover ha permanecido intacta desde sus orígenes.
La búsqueda tabú puede verse como
una meta-heurística que se superpone a una técnica de búsqueda y que se encarga
de evitar que dicha técnica caiga en óptimos locales prohibiendo (o, en un
sentido más general, penalizando) ciertos movimientos. El propósito de
clasificar ciertos movimientos como prohibidos (o "tabú") es para
evitar que se caiga en ciclos durante la búsqueda.
Debido a esto, Glover
sugiere como nombre alternativo para su método el de búsqueda con
"inhibición débil", ya que los movimientos que se consideran
prohibidos constituyen generalmente una pequeña fracción del total de
movimientos disponibles, y un movimiento pierde su status de prohibido después
de un período de tiempo relativamente corto, volviéndose después nuevamente
accesible. A este respecto, este método puede contrastarse con la técnica de
ramificación y límites (branch and bound) que también prohíbe ciertos
movimientos para evitar ciclos, pero lo hace de una manera
La búsqueda tabú se encuentra fundamentada en 3 cosas principales:
1. El uso de estructuras
flexibles de memoria basadas en atributos, diseñadas para permitir una mejor
explotación de los criterios de evaluación y la información histórica de la
búsqueda que lo que se conseguiría con estructuras rígidas de memoria (como las
que se usan en la búsqueda de ramificación y límites y el algoritmo A*) o con
sistemas carentes de memoria (como la técnica de "enfriamiento
simulado" simulated annealing y otras técnicas aleatorias similares).
2. Un mecanismo asociado de
control (para emplear las estructuras de memoria) basado en la interacción
entre las condiciones que limitan y hacen más flexible el proceso de búsqueda.
Este mecanismo se encuentra inmerso en la técnica en la forma de restricciones
y criterios de aspiración (un criterio de aspiración es aquél que permite que
un movimiento pierda su status de "tabú" debido a que proporciona una
mejor solución que la actual).
3. La incorporación de memorias
de diferente duración (de corto a largo plazo), para implementar estrategias
que intensifiquen y diversifiquen la búsqueda. Las estrategias de
intensificación refuerzan las propiedades de las combinaciones de movimientos
que han demostrado (históricamente) ser buenas, mientras que las estrategias de
diversificación dirigen la búsqueda hacia nuevas regiones del espacio de
soluciones factibles. Note que estos dos mecanismos son muy similares a la
cruza y la mutación en los algoritmos genéticos, ya que la primera nos permite
delimitar una cierta región del espacio de búsqueda, mientras que la segunda
nos permite saltar a nuevas regiones del mismo, evitando que quedemos atrapados
en un óptimo local.
La parte medular de la búsqueda
tabú se localiza en el proceso de memoria de corto plazo, y muchas de las
consideraciones estratégicas en que se fundamenta este proceso reaparecen,
amplifica-das pero sin mayores modificaciones, en los procesos de memoria de
largo plazo.
Ejemplo de Uso
Para ilustrar el funcionamiento
de esta técnica, utilizaremos un ejemplo clásico de estructuras de datos e
Inteligencia Artificial: el problema de las N reinas. La idea básica es colocar
N reinas en un tablero de ajedrez de N×N casillas, de tal manera que ninguna de
ellas pueda capturar a otra.
Este problema puede verse como
uno de optimización en el que el objetivo es minimizar el número de colisiones
(una colisión se presenta cuando una reina puede capturar a otra). Si asumimos
que cada reina se colocará siempre en una fila determinada de acuerdo a un cierto
orden pre-establecido, podemos representar cualquier estado del tablero usando
una permutación de la forma (p1, p2,..., pn), donde el valor de p1 representa
la columna donde se colocará a la reina
que está en la fila 1, y así sucesivamente.
Una de las operaciones básicas
que el algoritmo utilizará es el intercambio de 2 elementos cualquiera de una
permutación en la que haya colisiones. A fin de evitar la repetición de
intercambios realizados recientemente, consideraremos tabú cualquier
intercambio de este tipo. Debido a condiciones de simetría (intercambiar las
reinas 1 y 4 es lo mismo que intercambiar las reinas 4 y 1), una estructura
puede usarse para almacenar el número de iteraciones que faltan para permitir
que 2 reinas intercambien posiciones nuevamente.
La restricción de los
intercambios de 2 reinas puede ser ignorada si un cierto movimiento (prohibido)
conduce a una mejor solución (este es el criterio de aspiración).
Escalando la colina
Esta técnica se basa en
optimización local, sigue la dirección de ascenso o descenso a partir de su
posición y requiere muy poco costo computacional. Su comportamiento es
irrevocable porque no permite regresarnos a otra alterativa.
La técnica de escalando la
colina, evalúa la función en varios puntos, pasando de un punto a otro donde el
valor de la evaluación es mayor. La búsqueda termina cuando se ha encontrado el
punto con un valor máximo, por lo que no se obtendría la mejor solución.
Algoritmos Bio-inspirados
Son propuestas inspiradas en
modelos biológicos, tales como Algoritmos de Optimización basada en Colonias de
Hormigas, Algoritmos basados en Enjambres (de abejas, termitas) y Computación
Evolutiva. Basan su operación en los principios de la teoría Neo-Darwiniana de
la evolución natural. Los problemas combinatoriales pueden ser divididos en dos
grandes grupos considerando la existencia de algoritmos polinomiales para
resolver cada tipo de problema. El primero es el problema tipo P (polinomial)
para el cual existen algoritmos con esfuerzos computacionales de tipo
polinomial para encontrar la solución óptima; y el segundo es el problema tipo
NP (no polinomial) para el cual no se conocen algoritmos con esfuerzos
computacionales de tipo polinomial para encontrar la solución óptima. Las
técnicas heurísticas son algoritmos que encuentran soluciones de buena calidad
para problemas combinatoriales complejos; o sea, para problemas tipo NP. Los
algoritmos heurísticos son más fáciles de implementar y encuentran buenas
soluciones con esfuerzos computacionales relativamente pequeños; sin embargo, renuncian (desde el punto de
vista teórico) a encontrar la solución óptima global de un problema.
En problemas de gran tamaño rara
vez un algoritmo heurístico encuentra la solución óptima global. Los algoritmos
heurísticos se clasifican en algoritmos constructivos (golosos), algoritmos de
descomposición y división, algoritmos de reducción, algoritmos de manipulación
del modelo y algoritmos de búsqueda usando vecindad. En esta última categoría
pueden ser agrupados los Algoritmos Genéticos (AG),
Simulated Annealing (SA),
Búsqueda Tabú (TS), Colonia de
Hormigas (ACO) y GRASP, [4, 5].
Algoritmos Genéticos (AG)
Son herramientas matemáticas que
imitan a la naturaleza e intentan resolver problemas complejos empleando el
concepto de la evolución. El algoritmo ejecuta una búsqueda simultánea en
diferentes regiones del espacio factible, realiza una intensificación sobre
algunas de ellas y explora otros subespacios a través de un intercambio de
información entre configuraciones. Emplea tres mecanismos básicos que son: La
selección, el crossover y la mutación, [4, 5]:
Algoritmos Genéticos:
En forma aleatoria se conformó
una población inicial, en la que cada cromosoma representa una posible ruta a
seguir y cada gen indica el número de la ciudad.
Los datos utilizados por el
algoritmo son:
Población inicial: 14 cromosomas
(aleatoria)
Número de genes por cromosoma: 8
Proceso de selección: Esquema de
la ruleta
Tipo de crossover: Punto simple
Tasa de crossover: ρc = 0.9
Tasa de mutación: ρm = 0.02
Máximo número de generaciones:
400
Criterio de parada: 20
generaciones consecutivas sin que mejore la función objetivo o máximo número de
generaciones.
Los resultados encontrados por
el algoritmo de AG son:
Ruta óptima: 1 4 8 7 6 5 3 2
Función objetivo: 1490
Total de generaciones: 125
Crossover
Consiste en el intercambio de
material genético entre dos cromosomas (a veces más, como el operador orgía
propuesto por Eiben et al.). El crossover es el principal operador genético,
hasta el punto que se puede decir que no es un algoritmo genético si no tiene
crossover, y, sin embargo, puede serlo perfectamente sin mutación, según
descubrió Holland. El teorema de los esquemas confía en él para hallar la mejor
solución a un problema, combinando soluciones parciales.
Para aplicar el crossover,
entrecruzamiento o recombinación, se escogen aleatoriamente dos miembros de la
población. No pasa nada si se emparejan dos descendientes de los mismos padres;
ello garantiza la perpetuación de un individuo con buena puntuación (y, además,
algo parecido ocurre en la realidad; es una práctica utilizada, por ejemplo, en
la cría de ganado, llamada inbreeding, y destinada a potenciar ciertas
características frente a otras). Sin embargo, si esto sucede demasiado a
menudo, puede crear problemas: toda la población puede aparecer dominada por
los descendientes de algún gen, que, además, puede tener caracteres no
deseados. Esto se suele denominar en otros métodos de optimización atranque en
un mínimo local, y es uno de los principales problemas con los que se enfrentan
los que aplican algoritmos genéticos.
En cuanto al teorema de los
esquemas, se basa en la noción de bloques de construcción. Una buena solución a
un problema está constituido por unos buenos bloques, igual que una buena máquina
está hecha por buenas piezas. El crossover es el encargado de mezclar bloques
buenos que se encuentren en los diversos progenitores, y que serán los que den
a los mismos una buena puntuación. La presión selectiva se encarga de que sólo
los buenos bloques se perpetúen, y poco a poco vayan formando una buena
solución. El teorema de los esquemas viene a decir que la cantidad de buenos
bloques se va incrementando con el tiempo de ejecución de un algoritmo
genético, y es el resultado teórico más importante en algoritmos genéticos.
El intercambio genético se puede
llevar a cabo de muchas formas, pero hay dos grupos principales Crossover
n-puntos: Los dos cromosomas se cortan por n puntos, y el material genético
situado entre ellos se intercambia. Lo más habitual es un crossover de un punto
o de dos puntos.
Crossover uniforme: Se
genera un patrón aleatorio de 1s y 0s, y se intercambian los bits de los dos
cromosomas que coincidan donde hay un 1 en el patrón. O bien se genera un
número aleatorio para cada bit, y si supera una determinada probabilidad se
intercambia ese bit entre los dos cromosomas.
Crossover especializados:
En algunos problemas, aplicar aleatoriamente el crossover da lugar a cromosomas
que codifican soluciones inválidas; en
este caso hay que aplicar el crossover de forma que genere siempre soluciones
válidas. Un ejemplo de estos son los operadores de crossover usados en el
problema del viajante.
Algoritmo genético simple.
John Holland desde pequeño, se
preguntaba cómo logra la naturaleza, crear seres cada vez más perfectos
(aunque, como se ha visto, esto no es totalmente cierto, o en todo caso depende
de qué entienda uno por perfecto). Lo curioso era que todo se lleva a cabo a
base de interacciones locales entre individuos, y entre estos y lo que les
rodea. No sabía la respuesta, pero tenía una cierta idea de cómo hallarla:
tratando de hacer pequeños modelos de la naturaleza, que tuvieran alguna de sus
características, y ver cómo funcionaban, para luego extrapolar sus conclusiones
a la totalidad. De hecho, ya de pequeño hacía simulaciones de batallas célebres
con todos sus elementos: copiaba mapas y los cubría luego de pequeños ejércitos
que se enfrentaban entre sí.
En los años 50 entró en contacto
con los primeros ordenadores, donde pudo llevar a cabo algunas de sus ideas,
aunque no se encontró con un ambiente intelectual fértil para propagarlas. Fue
a principios de los 60, en la Universidad de Michigan en Ann Arbor, donde, dentro
del grupo Logis of
Computes, sus ideas comenzaron a
desarrollarse y a dar frutos. Y fue, además, leyendo un libro escrito por un
biólogo evolucionista, R. A. Fisher, titulado La teoría genética de la
selección natural, como comenzó a descubrir los medios de llevar a cabo sus
propósitos de comprensión de la naturaleza. De ese libro aprendió que la
evolución era una forma de adaptación más potente que el simple aprendizaje, y
tomó la decisión de aplicar estas ideas para desarrollar programas bien adaptados
para un fin determinado. En esa universidad, Holland impartía un curso titulado
Teoría de sistemas adaptativos. Dentro de este curso, y con una participación
activa por parte de sus estudiantes, fue donde se crearon las ideas que más
tarde se convertirían en los algoritmos genéticos. Por tanto, cuando Holland se
enfrentó a los algoritmos genéticos, los objetivos de su investigación fueron
dos: imitar los procesos adaptativos de los sistemas naturales, diseñar
sistemas artificiales (normalmente programas) que retengan los mecanismos
importantes de los sistemas naturales.
Unos 15 años más adelante, David
Goldberg, actual delfín de los algoritmos genéticos, conoció a Holland, y se
convirtió en su estudiante. Golberg era un ingeniero industrial trabajando en
diseño de pipelines, y fue uno de los primeros que trató de aplicar los
algoritmos genéticos a problemas industriales. Aunque Holland trató de
disuadirle, porque pensaba que el problema era excesivamente complicado como
para aplicarle algoritmos genéticos, Goldberg consiguió lo que quería,
escribiendo un algoritmo genético en un ordenador personal Apple II. Estas y
otras aplicaciones creadas por estudiantes de Holland convirtieron a los
algoritmos genéticos en un campo con base suficiente aceptado para celebrar la
primera conferencia en 1985, ICGA´85. Tal conferencia se sigue celebrando
bianualmente.
Anatomía de un algoritmo genético simple
Los algoritmos genéticos son
métodos sistemáticos para la resolución de problemas de búsqueda y optimización
que aplican a estos los mismos métodos de la evolución biológica: selección
basada en la población, reproducción sexual y mutación.
Los algoritmos genéticos son
métodos de optimización, que tratan de resolver el mismo conjunto de problemas
que se ha contemplado anteriormente, es decir, hallar (xi,..., xn) tales que F
(xi,..., xn) sea máximo. En un algoritmo genético, tras parametrizar el
problema en una serie de variables, (xi,..., xn) se codifican en un cromosoma.
Todas los operadores utilizados por un algoritmo genético se aplicarán sobre
estos cromosomas, o sobre poblaciones de ellos. En el algoritmo genético va
implícito el método para resolver el problema; son solo parámetros de tal
método los que están codificados, a diferencia de otros algoritmos evolutivos
como la programación genética. Hay que tener en cuenta que un algoritmo
genético es independiente del problema, lo cual lo hace un algoritmo robusto,
por ser útil para cualquier problema, pero a la vez débil, pues no está
especializado en ninguno.
Las soluciones codificadas en un
cromosoma compiten para ver cuál constituye la mejor solución (aunque no
necesariamente la mejor de todas las soluciones posibles). El ambiente,
constituido por las otras camaradas soluciones, ejercerá una presión selectiva
sobre la población, de forma que sólo los mejor adaptados (aquellos que
resuelvan mejor el problema) sobrevivan o leguen su material genético a las
siguientes generaciones, igual que en la evolución de las especies. La
diversidad genética se introduce mediante mutaciones y reproducción sexual.
En la Naturaleza lo único que hay
que optimizar es la supervivencia, y eso significa a su vez maximizar diversos
factores y minimizar otros. Un algoritmo genético, sin embargo, se usará para
optimizar habitualmente para optimizar sólo una función, no diversas funciones
relacionadas entre sí simultáneamente. Este tipo de optimización, denominada
optimización multimodal, también se suele abordar con un algoritmo genético
especializado.
Por lo tanto, un algoritmo
genético consiste en lo siguiente: hallar de qué parámetros depende el
problema, codificarlos en un cromosoma, y se aplican los métodos de la
evolución: selección y reproducción sexual con intercambio de información y
alteraciones que generan diversidad. En las
siguientes secciones se verán
cada uno de los aspectos de un algoritmo genético.
