Tecnicas Heuristicas

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.