next up previous contents
Next: Analizando la regla Up: Aplicando la teoría del Previous: Aplicando la teoría del   Contenido

Analizando la regla $ Life$ $ R(2,3,3,3)$

La teoría del campo promedio ha sido empleada en [16], [22], [24], [30], [44] y [50], para tratar de explicar el comportamiento de los estados de las reglas de evolución, la mayoría de estos estudios describen el comportamiento de las células a través de su densidad en el espacio de evoluciones en el tiempo. El análisis propone un enfoque sencillo y práctico de como obtener dichas densidades e interpretar fácilmente los resultados, tal como lo plantean McIntosh en [44] y Chaté-Manneville en [16], graficando su curva de probabilidad en el tiempo inicial y calculando sus curvas de probabilidad a través del tiempo, sustituyendo iterativamente el polinomio de la Equación 2.5.1.

Se construye el polinomio de la teoría del campo promedio paso a paso para ver con claridad la relación que existe entre las Ecuaciones 2.5.12.5.7, y las variables definidas por $ S_{min}$, $ S_{max}$, $ N_{min}$ y $ N_{max}$. La regla Life es la regla semiltotalística $ R(2,3,3,3)$ entonces $ S_{min}=2$, $ S_{max}=3$, $ N_{min}=3$ y $ N_{max}=3$, el número de configuraciones que se pueden generar en la vecindad de Moore cuando $ S_{min}=2$ es igual a 28, como se ilustra en la Figura 3.9.

Figura 3.9: Configuraciones que determinan la sobrevivencia cuando $ S_{min}=2$
\includegraphics[width= 2.5in]{imagenes/capitulo2/config_life.eps}

La transformación local cuando $ S_{min}=2$ determina 28 vecindades que se transforman a 1 en la siguiente generación, donde la célula central en este caso es igual a 1, la Figura 3.9 ilustra todas las combinaciones que se pueden generar en la vecindad de Moore, cuando la célula central está viva y se tienen dos vecinos vivos para que en la siguiente generación la célula central siga viva. Empleando notación de las Ecuaciones 2.5.12.5.7 se representa el polinomio del campo promedio de la siguiente manera:


$\displaystyle p_{t+1} = \sum_{v=S_{min}}^{S_{max}} \left (\begin{array}{c} n-1 ...
...\left (\begin{array}{c} n-1 \ v \end{array} \right ) p_{t}^{v} (1-p_{t})^{n-v}$ (3.4.1)

donde $ n$ representa el número de células que tiene una vecindad, $ n-1$ son las combinaciones sin tomar en cuenta la célula central, $ v$ indica el número de veces que aparece el estado 1 en la vecindad de Moore, $ n-v$ indica el número de veces que aparece el estado 0 en la vecindad de Moore, $ p_{t}$ es la probabilidad de tener 1's en la siguiente generación, $ 1-p_{t}$ es la probabilidad de tener 0's en la siguiente generación, la combinatoria $ \left (\begin{array}{c}
n-1 \\
v
\end{array} \right )$ dará las constantes para cada uno de los términos del polinomio. La primera sumatoria calculará todas las combinaciones que se derivan del intervalo que definen $ S_{min}$ y $ S_{max}$ en el caso de la sobrevivencia. La segunda sumatoria calculará todas las combinaciones que se derivan del intervalo que definen $ N_{min}$ y $ N_{max}$ en el caso de los nacimientos. En el caso de la sobrevivencia al exponente $ v$ se le suma un elemento, porque al momento de definir la cantidad de 1's en la vecindad la célula central está viva. En el caso de los nacimientos $ v$ representa el número de veces que aparece el estado 1 en la vecindad y no se le suma ningún elemento porque la célula central está muerta.

La probabilidad de que se obtengan 1's es igual a $ p$, para garantizar su complemento $ q$ es la probabilidad de que se obtengan 0's, por lo tanto $ p+q=1$ y $ q=1-p$. Simplificando la Ecuación 3.4.1 empleando la variable $ q$ se tiene finalmente:


$\displaystyle p_{t+1} = \sum_{v=S_{min}}^{S_{max}} \left (\begin{array}{c} n-1 ...
...x}} \left (\begin{array}{c} n-1 \ v \end{array} \right ) p_{t}^{v} q_{t}^{n-v}$ (3.4.2)

El exponente $ v$ para la variable $ p_{t}$ se calcula sumando el número de células ocupadas por el estado 1 dentro de la vecindad de Moore, el exponente $ n-v$ para la variable $ q$ se calcula sumando el número de células ocupadas por el estado 0 dentro de la vecindad de Moore, entonces se tiene que $ v=3$ y $ n-v=9-3=6$, cuando $ S_{min}=2$. Nótese que las combinaciones se realizan en la vecindad isotrópica $ \mathcal V$ (en los vecinos), donde la célula central $ \mathbf{x}_{0}$ es ocupada por el estado 1, en realidad al momento de calcular las configuraciones no importa si $ \mathbf{x}_{0}$ es ocupada por el estado 1 o el estado 0, sin embargo $ \mathbf{x}_{0}$ es importante al momento de definir los exponentes del polinomio.

Ahora se realiza el cálculo cuando $ S_{max}=3$ como se ilustra en la Figura 3.10.

Figura 3.10: Configuraciones que determinan la sobrevivencia cuando $ S_{max}=3$
\includegraphics[width= 5.7in]{imagenes/capitulo2/config_life2.eps}

Cuando $ S_{max}=3$ se generan 56 vecindades que se transforman al estado 1 en la siguiente generación dentro de la vecindad de Moore, éstas son combinaciones sin repetición. Por lo tanto se calcula el número de combinaciones empleando el coeficiente binomial:


$\displaystyle \left (\begin{array}{c} n-1 \ v \end{array} \right ) = \frac{(n-1)!}{v!((n-1)-v)!}$ (3.4.3)

donde $ n=2r+1=\mathcal V$ y $ v$ tomará valores de $ v=\{0,1,\ldots,n-1\}$. Por ejemplo para el caso de la Figura 3.9 se tiene que $ v=S_{min}=2$ y $ n-1= \mathcal V=8$, entonces se tiene que:


$\displaystyle \left (\begin{array}{c} 8 \ 2 \end{array} \right ) = \frac{(9-1)!}{2!((9-1)-2)!} = 28$    

donde este número representa las combinaciones sin repetición que se generan cuando $ S_{min}=2$ en la vecindad isotrópica $ \mathcal V=8$ o los vecinos de la vecindad de Moore. En el caso de la Figura 3.10 se tiene que $ S_{max}=3$, entonces se tiene que:


$\displaystyle \left (\begin{array}{c} 8 \ 3 \end{array} \right ) = \frac{(9-1)!}{3!((9-1)-3)!} = 56$    

donde este número representa las combinaciones sin repetición que se generan cuando $ S_{max}=3$ en la vecindad isotrópica $ \mathcal V=8$ o los vecinos de la vecindad de Moore. Nótese que para el caso cuando $ N_{min}=3$ y $ N_{max}=3$, se tienen 56 combinaciones igual que cuando $ S_{max}=3$, ésto se debe porque las combinaciones se realizan en las células de $ \mathcal V$, es decir, los vecinos de la vecindad sin tomar en cuenta la célula central $ \mathbf{x}_{0}$, por lo que las combinaciones de $ S_{max}=3$ son iguales a las combinaciones de $ N_{min}=3$ y $ N_{max}=3$, estos valores van a determinar las constantes del polinomio.

El grado del polinomio se determina por el número de células vivas $ v$ y por el número de células muertas $ n-v$, que existen en los vecinos $ \mathcal V$ de las Figuras 3.93.10, cuando $ S_{min}=2$ se tiene que $ v=3$ y $ n-v=6$, cuando $ S_{max}=3$ se tiene que $ v=4$ y $ n-v=5$, cuando $ N_{min}=3$ se tiene que $ v=3$ y $ n-v=6$ y cuando $ N_{max}=3$ se tiene que $ v=4$ y $ n-v=5$, finalmente el polinomio para la regla de Life es:


$\displaystyle p_{t+1}=28p_{t}^{3}q_{t}^{6}+56p_{t}^{4}q_{t}^{5}+56p_{t}^{3}q_{t}^{6}$ (3.4.4)

simplificando se tiene el polinomio de la teoría del campo promedio para Life:


$\displaystyle p_{t+1}=84p_{t}^{3}q_{t}^{6}+56p_{t}^{4}q_{t}^{5}$ (3.4.5)

la probabilidad que se genera cuando $ S_{max}=3$ es la misma probabilidad cuando $ N_{min}=3$, porque el número de 1's en la vecindad de Moore es igual en los dos casos, por eso se tienen tres términos en el polinomio en lugar de cuatro como pudiera pensarse.

La curva de probabilidad se obtiene poniendo el polinomio de la Ecuación 3.4.5 en términos de $ p$:


$\displaystyle p_{t+1}=84p_{t}^{3}(1-p_{t})^{6}+56p_{t}^{4}(1-p_{t})^{5}$ (3.4.6)

donde $ p$ tomará valores de 0 a 1. La curva de probabilidad del campo promedio muestra directamente la información de como se comporta la densidad de los estados en el espacio de evoluciones. La densidad es interpretada a través de la existencia de puntos fijos en la curva de probabilidad que genera el polinomio. A continuación se da la definición de punto fijo.

Definición 3.4.1   Un punto $ x$ es periódico para una función $ f$ si $ f^{n}(x)=x$ para algún $ n \geq 1$ donde $ n \in \mathbb{Z}^{+}$ y se dice que $ x$ tiene periódo $ n$ bajo $ f$. Si $ f(x)=x$, entonces $ x$ es llamado un punto fijo en $ f$.
height 0.2 cm cm height 0.2 cm

Los puntos fijos pueden ser estables o inestables. Sea $ f$ una función diferenciable, si el valor absoluto de la primera derivada $ \vert f'(x)\vert<1$, entonces $ x$ es un punto fijo estable. Si el valor absoluto de la primera derivada $ \vert f'(x)\vert>1$ entonces $ x$ es un punto fijo inestable. Si el valor de la primera derivada $ f'(x)=0$, entonces $ x$ es llamado un punto crítico, es decir, su tangente es horizontal al eje $ x$ en el plano cartesiano.

La gráfica de la Figura 3.11 muestra la curva de probabilidad que produce el polinomio de la regla de evolución Life, el eje horizontal $ q$ indicará la probabilidad de obtener 0's, el eje vertical $ p$ indica la probabilidad de obtener 1's, $ p$ y $ q$ podrán ser evaluados en el intervalo cerrado $ [0,1]$, por esta razón la diagonal mostrará los punto fijos de la curva al momento de intersectar algún punto de la curva con la diagonal, porque eso significa que $ f(x)=x$ en ese punto.

El punto fijo estable que se encuentra en 0 sobre el eje $ x$ de la Figura 3.11 indica que en el espacio de evoluciones no hay células vivas, entonces la probabilidad de que se obtengan células vivas en la siguiente generación es 0, ésto es por la condición de que $ S_{min} < 2$; por otra parte si el espacio de evoluciones se encuentra lleno de células vivas, entonces la probabilidad de que se obtengan células vivas en la siguiente generación es 0, esto se debe por la condición de que $ S_{max} > 3$ y los valores de la curva son igual a 0 conforme nos acerquemos mas a 1 en el eje $ q$.

Figura 3.11: Curva de probabilidad de la regla Life
\includegraphics[width= 4.0in]{imagenes/capitulo2/curva_life.eps}

Nótese la existencia de otros dos puntos fijos, un punto fijo inestable aproximadamente en 0.2 que indica la existencia de comportamientos inpredecibles dentro de ciertas regiones locales, es decir, la densidad que tiene el autómata en ese momento puede mantenerse igual, crecer rápidamente o desaparecer por completo en unos cuantos pasos. El otro punto fijo es un punto crítico y se encuentra aproximadamente en 0.37 que indica la densidad promedio de células vivas que se pueden conservar en el espacio de evoluciones a través del tiempo. Para obtener el comportamiento en la siguiente generación se sustituye el polinomio $ p_{t}$ de la Ecuación 3.4.6, en él mismo para obtener la curva de probabilidad en $ p_{t+2}$ de la siguente manera:


\begin{displaymath}
\begin{array}{lll}
p_{t+2} & = & 84(84p_{t+1}^{3}(1-p_{t+1})...
...1-p_{t+1})^{6}+56p_{t+1}^{4}(1-p_{t+1})^{5}))^{5}
\end{array}
\end{displaymath}

este polinomio mostrará el comportamiento de la curva en la siguiente generación. Nótese que conforme se desee calcular mas generaciones el polinomio crece exponencialmente, los polinomios para la tercera y cuarta generación ocuparían tres páginas completas. En la Figura 3.12 se grafican las curvas de probabilidad para la segunda, tercera y cuarta generación de la regla de evolución Life.

Figura 3.12: Curva de probabilidad de la regla Life, segunda, tercera y cuarta generación
\includegraphics[width= 6.5in]{imagenes/capitulo2/curva_life2.eps}

El comportamiento de las células en cada generación delimita cada vez mas su densidad en el espacio de evoluciones, en promedio éste es el comportamiento que debe seguir cualquier configuración inicial aleatoria, se puede apreciar en la Figura 3.12 que el intervalo de la curva sobre el eje $ q$ se hace cada vez mas estrecho, ésto indica que la población de células vivas es cada vez menor, en efecto así ocurre en Life.

En la fase de experimentación las curvas de probabilidad se calcularon sustituyendo el polinomio $ p_{0}$ en $ p_{1}$, el polinomio $ p_{0}$ en $ p_{2}$ y así sucesivamente. Para tratar de acelerar el proceso en las curvas de probabilidad se sustituyo el polinomio $ p_{0}$ en $ p_{1}$, el polinomio $ p_{1}$ en $ p_{2}$ y así sucesivamente, pero los resultados al momento de generar la gráfica fueron idénticos, además de que para el segundo caso existe el problema de que el polinomio a calcular es mucho mas grande que para el primer caso.

La densidad promedio de 0.37 calculada para la regla de evolución Life coincide con otros resultados obtenidos en [50] y [24]. Todos los demás casos se estudian de la misma manera, para posteriormente establecer una caracterización a través de sus curvas de probabilidad.


next up previous contents
Next: Analizando la regla Up: Aplicando la teoría del Previous: Aplicando la teoría del   Contenido
ice 2001-08-30