Algoritmo genérico

Introducción

Supongamos que tenemos una función de la cual no conocemos su derivada y hasta es posible que no sea derivable, ni siquiera continua, o que sea muy difícil de derivar, o… y queremos calcular su mínimo o su máximo en un intervalo dado. (Aquí vamos a suponer que queremos calcular el mínimo).

Fig. 1: Función difícil de derivar.

Funcion(y)=-(Integrate(Sen(x)/x,{x,1,y}))*(Log(Cos(y)+2)).

 

Fig. 2: Función no continua.

f(x)=x-IntegerPart(x).

funcion(x)=Sen(6*f(Cos(2*x)))*Cos(f(x)+2).

Pues una forma de hacerlo es utilizando el algoritmo genético que se basa en la adaptación de los individuos al medio en el que viven, podemos hacer una analogía de este algoritmo con la evolución de una especie en un ecosistema.

Damos algunas definiciones:

– Individuo es un punto dentro de ese intervalo.

– Genotipo, las características de cada individuo, es un punto en el intervalo en el que queremos calcular el mínimo.

– Adaptación de un individuo al medio es la proximidad de la imagen de ese punto por la función al extremo mínimo.

– Población inicial es el conjunto de puntos en el momento en el que se inicia el algoritmo.

– Hijo de dos individuos es un punto que está entre ambos puntos padres (de aquí el nombre de genético, se toman los individuos mejor adaptados, con menores valores imagen, y se crean nuevos puntos que estén entre esos dos puntos, se puede decir que el hijo hereda el código genético de los dos padre y por tanto sus propiedades de adaptación al medio.) Para crear nuevos hijos se toman los individuos mejor adaptados.

– Número máximo de la población es el número de individuos que soporta ese medio, el punto fijo de la ecuación logística para ese ecosistema.

– Muerte, desaparecen del conjunto de puntos algunos puntos escogidos al azar, dando preferencia a los que están menos adaptados. Se quitan tantos puntos como hagan falta hasta llegar al punto fijo de la población.

– Mutación, cada cierto número de nacimientos se producen unas mutaciones, que son individuos nuevos que se añaden a la población con código genético cambiado, sirven para que la especie no se estanquen en un mínimo local.

Se utilizan probabilidades para que se mueran los individuos menos adaptados y se reproduzcan los más adaptados, probabilidades que favorecen la reproducción de los individuos mejor adaptados al medio y la muerte de los peores adaptados.

Después de algunas iteraciones se ve como la población tiende a un mínimo, podemos decir que la especie se especializa en ese ecosistema pero puede que esa adaptación esa en un mínimo local de la función y que la especie se estanque en él y no sea capaz de tomar valores más bajos, por eso se incorporan mutaciones para que la población salte a otro mínimo (quizás de menor valor) y que se produzcan individuos mejor adaptados, este proceso termina cuando la población alcanza el mínimo global en el intervalo dado pues por muchas mutaciones que produzcan después morirán al no estar tan bien adaptadas como la población general que ya se ha adaptado muy bien al medio (aprovecha todos los recursos disponibles en el medio).

Estudiando el algoritmo se van muchas similitudes con especies de la vida real, aparte de las ya explicadas podemos ver.

Si el número de la población inicial es muy grande la especie llega antes al óptimo de su adaptación al medio, al igual que pasa en la vida real cuando hay mucha biodiversidad siempre aparecen especies muy bien adaptadas al medio. Si hay pocos individuos inicialmente es muy probable que se metan en un mínimo local (los individuos de esa especie serán muy parecidos entre sí y no aprovecharán otros recursos disponibles en el medio) y si no hay suficientes mutaciones le cuesta salir de él. Si hay suficientes mutaciones, con el tiempo, se creará una nueva especie que aprovechará más recursos del medio y dominará el ecosistema haciendo que la especie menos adaptada se extinga.

Hay otros factores que influyen en gran medida, como es el número de hijos por cada dos individuos, las veces que se reproducen, el número de la población, todos ellos tienen la propiedad de que cuanto mayor sean más probable es que se alcance el óptimo, claro que también es más pesado calcular una iteración pues hay más individuos que tratar. Otro factor importante es la muerte que es lo que produce que desaparezcan las especies peor adaptadas.

Bondad del algoritmo

El algoritmo se muestra especialmente útil cuando la función no es «suave» desde el punto de vista analítico, es decir, que no es derivable o es complicada de derivar, incluso puede no ser continua. En está situación las técnicas del análisis no se pueden aplicar y se necesita otro método para calcular los óptimos, es en este caso cuando el algoritmo genético entra en juego, aunque está claro que también se puede usar en los otros casos.

Fig. 3: Función no continua.

f(x)=x-IntegerPart(x)

funcion(x)=Sen(6*f(Cos(2*x)))*Cos(f(x)+2).

Después de experimentar durante un tiempo con este algoritmo se ven algunas propiedades como por ejemplo las siguientes:

Cuantos menos mínimos locales tenga la función más rápido alcanza el mínimo global. Ésto está claro, pues los individuos tienden a tomar un valor mínimo si hay pocos mínimos es más probable que tomen el valor mínimo global.

El algoritmo tiene problemas cuando se trabaja con una función que tenga muchos mínimos locales pues suele aproximarse a cada mínimo local antes de cambiar a otro entorno de un mínimo de valor menor y si hay muchos mínimos tarda más en encontrar el mínimo global.

Fig. 4: Función con muchos mínimos.

F(x)=Exp(-1/x^4)-Cos(x);

También tiene problemas cuando hay dos mínimos, uno global y otro local, pero que la diferencia entre sus valores es pequeña. Esto sucede porque los individuos tienen que adaptarse muy bien al medio antes de cambiar de genotipo, es decir, tienden a tomar valor muy próximos a ese mínimo antes de que alguna mutación o la descendencia de unos individuos cambien de entorno de mínimo, la especie mute.

El algoritmo también presenta problemas cuando el entorno del mínimo, que toma valores menores que el valor medio de la función en el intervalo de definición, es pequeño; por ejemplo, cuando la función oscila muy rápidamente, ya que es poco probable que un individuo caiga en ese entorno y que tenga descendencia que se adapte en este entorno.

Fig. 5: Función que presenta mínimos muy próximos.

funcion(x)=Sen(x^3)*Sen(x+3).

Cuanto menor sea el intervalo que consideramos o mayor sea la población inicial y el punto fijo de la población antes se llega al óptimo. Esto es así pues hay más probabilidad de que algún individuo entre en un entorno del mínimo global.

En el peor de los casos la probabilidad de encontrar el mínimo global utilizando el algoritmo genético es la misma que la probabilidad de que un punto tomado al azar en el intervalo de definición esté en un entorno pequeño del mínimo global.

El algoritmo está diseñado para que tienda a valores menores, por lo que después de un tiempo ejecutándose el valor que da es un valor mínimo, probablemente un mínimo local, y no hay garantías de que sea un mínimo global.

Por otra parte, en funciones discontinuas en el mínimo global, por ejemplo: una función que por la derecha tienda a un valor muy alto y por la izquierda tienda al mínimo global, es decir, una función que presente una discontinuidad con salto en el mínimo global, como en las funciones diente de sierra; el algoritmo no es capaz de llegar al mínimo global, tiende a él pero no lo alcanza nunca.

Más artículos relacionados con este tema:

Deja una respuesta

Tu e-mail no será publicado. Los campos requeridos están marcados con *