Algoritmos Genéticos

 

 

 

Qué son los Algoritmos Genéticos (GA) ?


Los Algoritmos Genéticos son un método de optimización matemática que esta basado en la evolución natural...


...Y si la evolución natural permitió que una pequeña e insignificante cadena núcleo proteínica, con el paso del tiempo hiciera que sus descendientes llegaran a ser hombres, podría hacer que la solución de un modelo matemático converja a la solución óptima.


El principio de la selección natural es bastante sencillo de entender, y es supremamente lógico. Si tenemos organismos (soluciones) que pueden cruzarse combinando en su descendencia sus características y eventualmente que aparezcan rasgos aleatorios (mutación), algunos serán más aptos que otros. Los más aptos tendrán más   oportunidades de reproducirse, y sus características se perpetuarán, los menos irán desapareciendo con el transcurso del tiempo. Al final las características que representan una ventaja se van sumando, complementando para lograr los organismos tan espectaculares que encontramos en la naturaleza. Nosotros mismos en la cúspide de esta.

 

A esto es lo que solemos llamar "Selección Natural" y con los Algoritmos Genéticos hemos copiado esta magnifica idea de la naturaleza. Una idea que ha demostrado su eficacia, pues ha demostrado tener un éxito arrollador, pero tal vez no ha demostrado su eficiencia, pues se ha necesitado de quince mil millones de años, para que la vida se desarrolle hasta el punto dónde se encuentra hoy. Y entonces? Demoraremos quince mil millones de años para resolver un programa matemático con este método? Pues dependiendo del problema y si lo hacemos a mano... pues tal vez si.... y por eso es que viene una terrible advertencia. Si no tiene ni forro de idea sobre Programación de Computadores o un muy buen manejo de hojas de cálculo, y además de eso, no tiene la más misérrima intención de aprender a hacerlo... lo mejor es que presione el botón de back... a menos que tenga curiosidad sobre el método, en ese caso: bienvenido. 


Hablando de eficiencia, los Algoritmos Genéticos, tal vez se parezcan más a la "Selección Artificial" que a la natural. La selección artificial es aquella que es causada por el hombre. Por ejemplo: las vacas lecheras. En un principio las vacas lecheras Sólo producían una cantidad pequeña de leche, pero con el pasar de los años, los seres humanos han ido prefiriendo a las vacas que dan más leche. Las razas con estas características han sido preferidas, han sido alimentadas cuidadas, se ha incentivado su reproducción su población ha crecido, sus características se han perpetuado, y las que no, se han ido descartando, su población fue disminuyendo y eventualmente esas razas desaparecieron. Una vaca de hoy da 100 veces más leche que las de hace cien años. En este sentido, la Selección Artificial ha sido más eficiente pues ha producido los resultados en mucho menos tiempo.

 

 


 
Terminología de los Algoritmos Genéticos:

 

 

 


Gen:

 

 Representa el valor de una variable de decisión (También se podrían usar un grupo de genes, para representar una solución  una variable un poco más compleja ), de manera análoga a como nuestros genes nos indican el color de ojos, de piel, la altura, etc; en modelación matemática nos podría indicar niveles de mano de mano de obra, de inventarios, etc. Si el gen es dominante, perdurará en la herencia que se haga dependiendo del filtro de selección artificial, si no si el gen es recesivo, irá difuminándose a lo largo de las generaciones según la presión del medio ambiente.

 

Cromosoma:

Un cromosoma esta formado por un grupo de genes. Es el conjunto de la solución en si.


Longitud de la Cadena

 

Es el número de genes que componen el cromosoma. O sea el número de variables que tiene el modelo matemático.


Función de Aptitud

 

La función de aptitud le da una calificación sobre que tan bueno es un conjunto de genes para obtener un objetivo dado, y con ello se realiza un filtro de las características que se propagan entre generaciones, y cuales no.  Normalmente esta función de aptitud será la misma función objetivo del modelo matemático que se tiene a la mano.


 Metodología:


Establezca cuáles son las variables de decisión en su problema matemático, defínalas claramente desde que valores hasta que valores pueden tomar sus soluciones, si son enteras, continuas, no negativas etc. Estas serán los genes del problema que en su conjunto formarán el cromosoma.
Defina cuál es el objetivo que quiere hallar, y formalícelo como  una expresión matemática, que obviamente va a estar en función de las variables de decisión. A esta función objetivo, le vamos a llamar función de aptitud.


Concrete cuales son las restricciones del sistema modelado, para conseguir el objetivo. Puede involucrarlas en la función objetivo a manera de penalización, para que en caso que los valores de las variables de decisión, es decir de los genes, no cumplan con la restricción se vea reflejado directamente en la función objetivo o de aptitud, llevándola proporcionalmente (o cuadráticamente, o exponencialmente, etc) al opuesto de su valor deseado. Cómo así? Lo enrede?  A ver... por ejemplo si tenemos una función de aptitud de minimización de costos de producción, y se tiene como restricción una cantidad x de cierto insumo, podríamos penalizar sumándole al costo de la función objetivo x cantidad multiplicada por cada unidad que se pase de la restricción.  Y así de esta manera para cada una de las restricciones que se tengan.


En este momento se puede definir la población inicial del sistema. Es decir se dan varios grupos de valores de las variables de decisión de una forma aleatorio o si es más experto utilizando alguna regla heurística que mejore la elección de la población inicial. Recordemos que a los grupos de valores los llamamos cromosomas.


Crear una nueva población: al crear una nueva población, se cruzan soluciones y los hijos heredan una parte de su información genética de u madre y otro parte de su  información del padre. Además eventualmente se pueden producir mutaciones aleatorias, que introducen nueva información en los hijos, que no estaba dentro del código de los padres. Esta nueva característica puede ser transmitida a los nietos, y si por azar del destino, resulta benéfica le dará una ventaja competitiva sobre sus compañeros, podrá tener mayor probabilidad de reproducirse y por lo tanta de perpetuarse.  Para la selección de los individuos que se procrearán se puede utilizar el método de la ruleta, donde a los individuos de la población se le asigna una porción del intervalo [0-1], que es proporcional a su función de aptitud, luego un número aleatorio se ubicará en la porción del intervalo que le corresponde eligiendo así a quién se puede cruzar. Otro método es el de la competencia: se ordenan de mayor a menor los individuos según su función de aptitud, y se elige el número de individuos igual al de la población mínima a tener.


Luego: Iterar N veces o hasta que los cromosomas converjan (algo bastante difícil de lograr)
Cuando haya llegado a N veces o haya convergido, se habrá llegado a la respuesta pseudo-óptima, o con suerte a la óptima
 

Contenido :

Social