La adaptación gaussiana (GA) , también llamada adaptación normal o natural (NA) es un algoritmo evolutivo diseñado para maximizar el rendimiento de fabricación debido a la desviación estadística de los valores de los componentes de los sistemas de procesamiento de señales . En resumen, GA es un proceso adaptativo estocástico en el que una serie de muestras de un vector n- dimensional x [ x T = ( x 1 , x 2 , ..., x n )] se toman de una distribución gaussiana multivariante , N ( m , M), Que tiene media m y momento matriz M . Las muestras se analizan en busca de errores o aprobados. Los momentos de primer y segundo orden del gaussiano restringido a las muestras pasadas son m * y M * .
El resultado de x como muestra aprobada se determina mediante una función s ( x ), 0 < s ( x ) < q ≤ 1, de modo que s ( x ) es la probabilidad de que x se seleccione como muestra aprobada. La probabilidad media de encontrar muestras aprobadas (rendimiento) es
Entonces el teorema de GA establece:
Para cualquier s ( x ) y para cualquier valor de P < q , siempre existe un pdf gaussiano [ función de densidad de probabilidad ] que se adapta para la máxima dispersión. Las condiciones necesarias para un óptimo local son m = m * y M proporcional a M *. El problema dual también está resuelto: P se maximiza mientras se mantiene constante la dispersión (Kjellström, 1991).
Las pruebas del teorema se pueden encontrar en los artículos de Kjellström, 1970, y Kjellström & Taxén, 1981.
Dado que la dispersión se define como el exponencial de la entropía / desorden / información promedio, se deduce inmediatamente que el teorema es válido también para esos conceptos. En conjunto, esto significa que la adaptación gaussiana puede llevar a cabo una maximización simultánea del rendimiento y la información promedio (sin necesidad de que el rendimiento o la información promedio se definan como funciones de criterio).
El teorema es válido para todas las regiones de aceptabilidad y todas las distribuciones gaussianas . Puede ser utilizado por repetición cíclica de variación y selección aleatorias (como la evolución natural). En cada ciclo, se muestrea un número suficientemente grande de puntos distribuidos gaussianos y se prueba su pertenencia a la región de aceptabilidad. El centro de gravedad del gaussiano, m , se mueve luego al centro de gravedad de los puntos aprobados (seleccionados), m *. Así, el proceso converge a un estado de equilibrio cumpliendo el teorema. Una solución siempre es aproximada porque el centro de gravedad siempre se determina para un número limitado de puntos.
Se utilizó por primera vez en 1969 como un algoritmo de optimización puro que hace que las regiones de aceptabilidad sean cada vez más pequeñas (en analogía con el recocido simulado , Kirkpatrick 1983). Desde 1970 se ha utilizado tanto para la optimización ordinaria como para la maximización del rendimiento.
Evolución natural y adaptación gaussiana
También se ha comparado con la evolución natural de poblaciones de organismos vivos. En este caso, s ( x ) es la probabilidad de que el individuo que tiene una matriz x de fenotipos sobreviva dando descendencia a la siguiente generación; una definición de aptitud individual dada por Hartl 1981. El rendimiento, P , se reemplaza por la aptitud media determinada como una media sobre el conjunto de individuos en una gran población.
Los fenotipos suelen estar distribuidos gaussianos en una gran población y una condición necesaria para que la evolución natural pueda cumplir el teorema de la adaptación gaussiana, con respecto a todos los caracteres cuantitativos gaussianos, es que pueda empujar el centro de gravedad del gaussiano a la centro de gravedad de los individuos seleccionados. Esto puede lograrse mediante la ley de Hardy-Weinberg . Esto es posible porque el teorema de la adaptación gaussiana es válido para cualquier región de aceptabilidad independiente de la estructura (Kjellström, 1996).
En este caso, las reglas de la variación genética, como el cruce, la inversión, la transposición, etcétera, pueden verse como generadores de números aleatorios para los fenotipos. Entonces, en este sentido, la adaptación gaussiana puede verse como un algoritmo genético.
Cómo escalar una montaña
La aptitud media puede calcularse siempre que se conozca la distribución de los parámetros y la estructura del paisaje. No se conoce el paisaje real, pero la figura siguiente muestra un perfil ficticio (azul) de un paisaje a lo largo de una línea (x) en una habitación abarcada por dichos parámetros. La curva roja es la media basada en la curva de campana roja en la parte inferior de la figura. Se obtiene dejando que la curva de campana se deslice a lo largo del eje x , calculando la media en cada ubicación. Como puede verse, los pequeños picos y hoyos se suavizan. Por lo tanto, si la evolución se inicia en A con una variación relativamente pequeña (la curva de campana roja), entonces la escalada tendrá lugar en la curva roja. El proceso puede atascarse durante millones de años en B o C, siempre que permanezcan los huecos a la derecha de estos puntos y la tasa de mutación sea demasiado pequeña.
Si la tasa de mutación es lo suficientemente alta, el trastorno o la varianza pueden aumentar y los parámetros pueden distribuirse como la curva de campana verde. Luego, la escalada tendrá lugar en la curva verde, que está aún más suavizada. Debido a que los huecos a la derecha de B y C ahora han desaparecido, el proceso puede continuar hasta los picos en D. Pero, por supuesto, el paisaje pone un límite al desorden o variabilidad. Además, dependiendo del paisaje, el proceso puede volverse muy entrecortado, y si la relación entre el tiempo que pasa el proceso en un pico local y el tiempo de transición al siguiente pico es muy alta, también puede parecer un punto puntuado. equilibrio sugerido por Gould (ver Ridley).
Simulación por computadora de la adaptación gaussiana
Hasta ahora, la teoría solo considera valores medios de distribuciones continuas correspondientes a un número infinito de individuos. En realidad, sin embargo, el número de individuos es siempre limitado, lo que da lugar a una incertidumbre en la estimación de m y M (la matriz momento de la gaussiana). Y esto también puede afectar la eficiencia del proceso. Desafortunadamente, se sabe muy poco sobre esto, al menos en teoría.
La implementación de la adaptación normal en una computadora es una tarea bastante simple. La adaptación de m puede ser realizada por una muestra (individuo) a la vez, por ejemplo
- m ( i + 1) = (1 - a ) m ( i ) + ax
donde x es una muestra aprobada y a <1 una constante adecuada para que la inversa de a represente el número de individuos en la población.
En principio, M puede actualizarse después de cada paso y lo que lleva a un punto factible
- x = m + y según:
- M ( i + 1) = ( 1-2 b ) M ( i ) + 2 byy T ,
donde y T es la transpuesta de y y b << 1 es otra constante adecuada. Para garantizar un aumento adecuado de la información promedio , y debe distribuirse normalmente con matriz de momentos μ 2 M , donde el escalar μ > 1 se utiliza para aumentar la información promedio ( entropía de información , desorden, diversidad) a una tasa adecuada. Pero M nunca se utilizará en los cálculos. En lugar de ello utilizamos la matriz W definido por WW T = M .
Por tanto, tenemos y = Wg , donde g se distribuye normalmente con la matriz de momentos μU y U es la matriz unitaria. W y W T pueden actualizarse mediante las fórmulas
- W = (1 - b ) W + byg T y W T = (1 - b ) W T + bgy T
porque la multiplicación da
- M = ( 1-2 b ) M + 2 byy T ,
donde se han descuidado términos que incluyen b 2 . Por tanto, M se adaptará indirectamente con una buena aproximación. En la práctica, será suficiente actualizar solo W
- W ( i + 1) = (1 - b ) W ( i ) + BYG T .
Ésta es la fórmula utilizada en un modelo bidimensional simple de un cerebro que satisface la regla hebbiana del aprendizaje asociativo; ver la siguiente sección (Kjellström, 1996 y 1999).
La siguiente figura ilustra el efecto del aumento de la información promedio en un pdf gaussiano utilizado para escalar la cresta de una montaña (las dos líneas representan la línea de contorno). Tanto el grupo rojo como el verde tienen la misma aptitud media, alrededor del 65%, pero el grupo verde tiene una información promedio mucho más alta, lo que hace que el proceso verde sea mucho más eficiente. El efecto de esta adaptación no es muy destacado en un caso bidimensional, pero en un caso de alta dimensión, la eficiencia del proceso de búsqueda puede aumentar en muchos órdenes de magnitud.
La evolución en el cerebro
En el cerebro, se supone que la evolución de los mensajes de ADN es reemplazada por una evolución de patrones de señales y el paisaje fenotípico es reemplazado por un paisaje mental, cuya complejidad difícilmente será superada por el primero. La metáfora con el paisaje mental se basa en el supuesto de que determinados patrones de señales dan lugar a un mejor bienestar o rendimiento. Por ejemplo, el control de un grupo de músculos conduce a una mejor pronunciación de una palabra o interpretación de una pieza musical.
En este modelo simple, se supone que el cerebro consta de componentes interconectados que pueden sumar, multiplicar y retrasar los valores de la señal.
- Un núcleo de células nerviosas puede agregar valores de señal,
- una sinapsis puede multiplicarse con una constante y
- Un axón puede retrasar los valores.
Ésta es la base de la teoría de los filtros digitales y las redes neuronales que consisten en componentes que pueden sumar, multiplicar y retrasar los valores de las señales y también de muchos modelos cerebrales, Levine 1991.
En la siguiente figura, se supone que el tronco encefálico proporciona patrones de señal distribuidos gaussianos. Esto puede ser posible debido a que ciertas neuronas se activan al azar (Kandel et al.). El tallo también constituye una estructura desordenada rodeada de capas más ordenadas (Bergström, 1969) y, según el teorema del límite central, la suma de señales de muchas neuronas puede tener una distribución gaussiana. Los cuadros triangulares representan sinapsis y los cuadros con el signo + son núcleos de células.
En la corteza se supone que las señales deben probarse para determinar su viabilidad. Cuando se acepta una señal, las áreas de contacto en las sinapsis se actualizan de acuerdo con las fórmulas siguientes de acuerdo con la teoría de Hebb. La figura muestra una simulación bidimensional por computadora de la adaptación gaussiana de acuerdo con la última fórmula de la sección anterior.
m y W se actualizan de acuerdo con:
- m 1 = 0,9 m 1 + 0,1 x 1; m 2 = 0,9 m 2 + 0,1 x 2 ;
- w 11 = 0,9 w 11 + 0,1 y 1 g 1 ; w 12 = 0,9 w 12 + 0,1 y 1 g 2 ;
- w 21 = 0,9 w 21 + 0,1 y 2 g 1 ; w 22 = 0,9 w 22 + 0,1 y 2 g 2 ;
Como puede verse, esto se parece mucho a un pequeño cerebro regido por la teoría del aprendizaje hebbiano (Kjellström, 1996, 1999 y 2002).
Adaptación gaussiana y libre albedrío
La adaptación gaussiana como modelo evolutivo del cerebro que obedece a la teoría hebbiana del aprendizaje asociativo ofrece una visión alternativa del libre albedrío debido a la capacidad del proceso de maximizar la aptitud media de los patrones de señales en el cerebro escalando un paisaje mental en analogía con los patrones fenotípicos. evolución.
Un proceso tan aleatorio nos da mucha libertad de elección, pero casi ninguna voluntad. Sin embargo, una ilusión de voluntad puede emanar de la capacidad del proceso para maximizar la adecuación media, haciendo que el proceso busque la meta. Es decir, prefiere picos más altos en el paisaje antes que más bajos, o mejores alternativas antes que peores. De esta forma puede aparecer una voluntad ilusoria. Zohar 1990 ha dado una opinión similar. Véase también Kjellström 1999.
Un teorema de eficiencia para la búsqueda aleatoria
La eficiencia de la adaptación gaussiana se basa en la teoría de la información de Claude E. Shannon (ver contenido de la información ). Cuando ocurre un evento con probabilidad P , entonces se puede lograr el registro de información ( P ). Por ejemplo, si la media de fitness es P , la información obtenida para cada individuo seleccionado para la supervivencia será log ( P ) - en promedio - y el trabajo / tiempo necesario para obtener la información es proporcional a 1 / P . Así, si la eficiencia, E, se define como la información dividida por el trabajo / tiempo necesario para obtenerla, tenemos:
- E = - P log ( P ).
Esta función alcanza su máximo cuando P = 1 / e = 0.37. Gaines ha obtenido el mismo resultado con un método diferente.
E = 0 si P = 0, para un proceso con tasa de mutación infinita, y si P = 1, para un proceso con tasa de mutación = 0 (siempre que el proceso esté vivo). Esta medida de eficiencia es válida para una gran clase de procesos de búsqueda aleatoria siempre que se den ciertas condiciones.
1 La búsqueda debe ser estadísticamente independiente e igualmente eficiente en diferentes direcciones de parámetros. Esta condición puede cumplirse aproximadamente cuando la matriz de momentos del gaussiano se ha adaptado para obtener información promedio máxima a alguna región de aceptabilidad, porque las transformaciones lineales de todo el proceso no afectan la eficiencia.
2 Todos los individuos tienen el mismo costo y la derivada en P = 1 es <0.
Entonces, se puede demostrar el siguiente teorema:
Todas las medidas de eficiencia, que satisfacen las condiciones anteriores, son asintóticamente proporcionales a - P log ( P / q ) cuando aumenta el número de dimensiones, y se maximizan por P = q exp (-1) (Kjellström, 1996 y 1999).
La figura anterior muestra una posible función de eficiencia para un proceso de búsqueda aleatorio como la adaptación gaussiana. A la izquierda, el proceso es más caótico cuando P = 0, mientras que hay un orden perfecto a la derecha donde P = 1.
En un ejemplo de Rechenberg, 1971, 1973, se empuja una caminata aleatoria a través de un corredor maximizando el parámetro x 1 . En este caso, la región de aceptabilidad se define como un intervalo ( n - 1) dimensional en los parámetros x 2 , x 3 , ..., x n , pero nunca se aceptará un valor x 1 por debajo del último aceptado. Dado que P nunca puede exceder 0.5 en este caso, la velocidad máxima hacia valores x 1 más altos se alcanza para P = 0.5 / e = 0.18, de acuerdo con los hallazgos de Rechenberg.
Un punto de vista que también puede ser de interés en este contexto es que no se necesita ninguna definición de información (aparte de que los puntos muestreados dentro de alguna región de aceptabilidad brinden información sobre la extensión de la región) para demostrar el teorema. Entonces, debido a que la fórmula puede interpretarse como información dividida por el trabajo necesario para obtener la información, esto también es una indicación de que −log ( P ) es un buen candidato para ser una medida de información.
El algoritmo de Stauffer y Grimson
La adaptación gaussiana también se ha utilizado para otros fines como, por ejemplo, la eliminación de sombras mediante el "algoritmo de Stauffer-Grimson", que es equivalente a la adaptación gaussiana como se utiliza en la sección "Simulación por ordenador de la adaptación gaussiana" anterior. En ambos casos, el método de máxima verosimilitud se utiliza para la estimación de valores medios por adaptación en una muestra a la vez.
Pero existen diferencias. En el caso de Stauffer-Grimson, la información no se utiliza para el control de un generador de números aleatorios para el centrado, la maximización de la aptitud media , la información media o el rendimiento de fabricación. La adaptación de la matriz de momentos también difiere mucho en comparación con "la evolución en el cerebro" anterior.
Ver también
- Entropía en termodinámica y teoría de la información
- Teorema fundamental de Fisher de la selección natural
- Libre albedrío
- Algoritmo genético
- Aprendizaje hebbiano
- Contenido de informacion
- Recocido simulado
- Optimización estocástica
- Estrategia de evolución de la adaptación de la matriz de covarianza (CMA-ES)
- Unidad de seleccion
Referencias
- Bergström, RM Un modelo de entropía del cerebro en desarrollo. Psicobiología del desarrollo , 2 (3): 139-152, 1969.
- Brooks, DR & Wiley, EO Evolution as Entropía, Hacia una teoría unificada de la biología . Prensa de la Universidad de Chicago, 1986.
- Brooks, RD Evolución en la era de la información: redescubrimiento de la naturaleza del organismo. Semiosis, Evolución, Energía, Desarrollo, Volumen 1, Número 1, marzo de 2001
- Gaines, Brian R. Gestión del conocimiento en sociedades de agentes adaptativos inteligentes. Revista de sistemas de información inteligentes 9, 277-298 (1997).
- Hartl, DL A Primer of Population Genetics . Sinauer, Sunderland, Massachusetts, 1981.
- Hamilton, WD. 1963. La evolución del comportamiento altruista. Naturalista estadounidense 97: 354–356
- Kandel, ER, Schwartz, JH, Jessel, TM Essentials of Neural Science and Behavior . Prentice Hall International, Londres, 1995.
- S. Kirkpatrick y CD Gelatt y MP Vecchi, Optimización por recocido simulado, Science, Vol 220, Número 4598, páginas 671–680, 1983.
- Kjellström, G. Optimización de la red por variación aleatoria de los valores de los componentes. Ericsson Technics , vol. 25, no. 3, págs. 133-151, 1969.
- Kjellström, G. Optimización de redes eléctricas con respecto a los costes de tolerancia. Ericsson Technics , no. 3, págs. 157-175, 1970.
- Kjellström, G. & Taxén, L. Optimización estocástica en el diseño de sistemas. IEEE Trans. en la Circ. y Syst., vol. CAS-28, no. 7, julio de 1981.
- Kjellström, G., Taxén, L. y Lindberg, PO Optimización discreta de filtros digitales mediante adaptación gaussiana y minimización de funciones cuadráticas. IEEE Trans. en la Circ. y Syst., vol. CAS-34, no 10, octubre de 1987.
- Kjellström, G. Sobre la eficiencia de la adaptación gaussiana. Revista de teoría y aplicaciones de la optimización , vol. 71, no. 3, diciembre de 1991.
- Kjellström, G. & Taxén, L. Gaussian Adaptation, un optimizador global eficiente basado en la evolución; Matemáticas computacionales y aplicadas, In, C. Brezinski & U. Kulish (Editores), Elsevier Science Publishers BV, págs. 267–276, 1992.
- Kjellström, G. La evolución como algoritmo de optimización estadística. Evolutionary Theory 11: 105-117 (enero de 1996).
- Kjellström, G. La evolución en el cerebro. Matemáticas y Computación Aplicadas , 98 (2–3): 293–300, febrero de 1999.
- Kjellström, G. Evolución en pocas palabras y algunas consecuencias en las valoraciones. EVOLVE, ISBN 91-972936-1-X , Estocolmo, 2002.
- Levine, DS Introducción al modelado neuronal y cognitivo. Laurence Erlbaum Associates, Inc., Editores, 1991.
- MacLean, PD Un concepto trino de cerebro y comportamiento . Toronto, Univ. Prensa de Toronto, 1973.
- Maynard Smith, J. 1964. Selección de grupo y selección de parentesco, Nature 201: 1145-1147.
- Maynard Smith, J. Genética evolutiva . Prensa de la Universidad de Oxford, 1998.
- Mayr, E. Qué es la evolución . Basic Books, Nueva York, 2001.
- Müller, Christian L. y Sbalzarini Ivo F. Revisión de la adaptación gaussiana: una visión entrópica de la adaptación de la matriz de covarianza. Instituto de Informática Teórica e Instituto Suizo de Bioinformática , ETH Zurich , CH-8092 Zurich, Suiza.
- Pinel, JF y Singhal, K. Centrado y tolerancia del diseño estadístico mediante muestreo paramétrico. Transacciones IEEE sobre circuitos y sistemas, vol. Das-28, No. 7, julio de 1981.
- Rechenberg, I. (1971): Evolutionsstrategie - Optimierung technischer Systeme nach Prinzipien der biologischen Evolution (tesis doctoral). Reimpreso por Fromman-Holzboog (1973).
- Ridley, M. Evolución . Blackwell Science, 1996.
- Stauffer, C. & Grimson, Patrones de actividad de aprendizaje de WEL mediante seguimiento en tiempo real, IEEE Trans. sobre PAMI, 22 (8), 2000.
- Stehr, G. Sobre la exploración espacial de rendimiento de circuitos integrados analógicos. Technischen Universität Munchen, Disertación 2005.
- Taxén, L. Un marco para la coordinación del desarrollo de sistemas complejos. Instituto de Tecnología, Universidad de Linköping, Disertación, 2003.
- Zohar, D. El yo cuántico: una visión revolucionaria de la naturaleza humana y la conciencia arraigada en la nueva física . Londres, Bloomsbury, 1990.