VOLVER.
En este apartado se tratarán algunas cuestiones relacionadas con el porque "funcionan" los algoritmos genéticos. El significado de la palabra "funciona" se refieren al hecho de ser capaces de encontrar el óptimo de la función durante el proceso de búsqueda.
En lo que sigue se presentará el denominado teorema de los esquemas para el caso del algoritmo genético canónico, utilizando ademas un alfabeto binario. Dicho teorema utiliza el consepto del esquema que introducimos a continuación.
Supongamos un alfabeto binario S={0,1} para construir un esquema necesitamos anpliar el alfabeto anterior por medio del simbolo *. Un esqueme sera cualquier ristra de caracteres formada a partir de elementos del alfabeto ampliado S`, siendo S`= (0,1*}. Si la longitud de la ristra es L el numero de esquemas existentes es 3`, ya que cada posición puede ocuparse por cualquiera de los tres elementos del alfabeto extendido S`. Un esqueme representa por tanto todas aquellas riatras que se asocian con él, en todas las posiciones distintas ocupadas por e.
Rudolph [33] demuestra la no convergencia el optimo global del algoritmo genetico canonico, asi como la garantia de convergencia expresadaen terminos probabilisticos,del algoritmo genetico que mantiene a la mejor solucion en la poblacion.
Davis y Principe [12] extrapolan los fundamentos teóricos del algoritmo a un modelo de algoritmo genetico basado en cadenas de Markov. Se efectúa un estudio de las matrices de transición de estados teniendo en cuenta el primer lugar tan solo la reproducción, a continuacion la reproducción y la, mutación y finalmente la reproducción, la mutación y el cruce.
Suzuki [39] efectúa un estudio dela convergencia del algoritmo geneticos por medio de cadenas de markov. los algortmos geneticos estudiados presentan un criteriode reduccion elitista modificado, segun el cual se genera una poblacion de A individuos, incluyendo en ella al mejor individuo de la poblacion en la generación anterior, obteniéndose los A - 1 individuos restantes por medio de las operaciones geneticas normales.
Liepeins [28] demuestra a la convergencia del algoritmo genético hacia poblaciones que contiene al óptimo, en el caso de algoritmo genéticos sin operador de mutación, pero en los cuales el reemplazamiento de individuos es elitista - el mejor individuo no se pierde nunca - y ademas se efectúa de tal manera que en cada paso cualquier punto del espacio sea potencialmente aolcanzable por medio de la operación de cruce.
Chakraborty y Dastidar [8] presentan un modelo de fiabilidad estocástica de un esquema para el algoritmo genetico binario con logitud de representacion fija, y obtiene una estimación para el número de generaciones necesarias hasta obtener una convergencia.
Eiben y Col [14] modelan la evolución del algorutmo genetico por medio de una cadena de Markov, obteniendo condiciones suficientes para la convergencia en probabilidad del proceso evolutivo hacia el óptimi global.
VOLVER.