Algoritmos evolutivos con estimación de distribuciones

Algoritmos evolutivos de estimación Parte de la familia Algoritmos Evolutivos

Algoritmos Evolutivos de Estimación. Son algoritmos basados en poblaciones que realizan su búsqueda en el carácter estocástico de la generación. No utilizan los operadores de cruce y mutación.

=== Esta plantilla tiene como objetivo ser una metaplantilla, es decir, una plantilla usada para ser la base de otras plantillas, no para ser usada directamente en el artículo.

Uso

Todos los parámetros son opcionales.

Cada fila de la tabla puede ser o una sección, o estar compuesta por un conjunto etiqueta/campo de datos, o por solo un campo de datos. Estos son estados mutuamente exclusivos, por lo tanto si se define una fila para ser tanto una sección como un conjunto etiqueta/campo de datos, este último no será tenido en cuenta.

Nótese que si se quiere insertar una imagen en cualquier lugar que no sea la parte superior de la ficha, o si se quieren insertar otros datos alternativos, usar una fila con un solo campo de datos sería una solución viable.

Parámetros

Nota: Los parámetros que incluyan la letra "n" entre paréntesis [o sea (n)], indican que se debe escribir al final del parámetro un número del 1 al 75. Por ejemplo, el código "|estilosección65 = font-style: italic;" establecería el estilo de fuente de la sección 65 en itálica.

Título y subtítulo

Título de la ficha
Subtítulo de la ficha
(el resto de la ficha)

Se recomienda siempre establecer título a la ficha. También se pueden establecer 2 subtítulos a la ficha.

titulo

Texto a mostrar como título.

colorfondotitulo o colorfondo

Establece el color de fondo del título.

subtitulo

Subtítulo de la ficha.

subtitulo2

Segundo subtítulo.

Contenido adicional

Todas las imágenes son centradas de manera predeterminada. Solo debe especificarse el nombre de las imágenes. Por ejemplo: "example.png".

imagen, imagen2

Imágenes ubicadas justo encima de los datos principales de la ficha (es decir, secciones, etiquetas y campos de datos).

tamañoimagen, tamañoimagen2

Tamaño de las imágenes 1 y 2 (predeterminado: 240px).

imagenizquierda, imagenderecha

Imágenes pequeñas ubicadas inmediatamente debajo de los subtítulos, una a la izquierda y otra a la derecha, respectivamente.

tamañoimagenizquierda, tamañoimagenderecha

Tamaño de las imágenes pequeñas (predeterminado: 100px).

imageninferior

Imagen ubicada en la parte inferior de la ficha.

tamañoimageninferior

Tamaño de la imagen inferior (predeterminado: 240px).

pie, pie2, pieizquierdo, piederecho, pieinferior

Pies de imagen.

seccion(n)

Contenido usado como sección.

etiqueta(n)

Contenido usado como etiqueta.

datos(n)

Contenido usado como campo de datos.

piedetabla

Texto del pie de la tabla. Se usa para notas al pie, véase también, etc.

Estilos CSS

Estos parámetros son usados para agregar código CSS en el atributo "style" de los elementos de la plantilla; son los que permiten cambiar la apariencia de estos elementos. Por lo tanto, deberán ser usados con sutileza para mantener un aspecto general estético y atractivo.

estilo

Se aplica a toda la tabla.

estilotitulo

Se aplica al título.

estilosubtitulo

Se aplica a los subtítulos.

estilosubtitulo1

Se aplica al primer subtítulo. Tiene precedencia sobre "estilosubtitulo".

estilosubtitulo2

Se aplica al segundo subtítulo. Tiene precedencia sobre "estilosubtitulo".

estiloimagen

Se aplica a todas las imágenes.

estilopie

Se aplica a todos los pies de imagen.

estiloseccion

Se aplica a las secciones en general.

estilosección(n)

Se aplica a la sección especificada con el número. Tiene precedencia sobre "estiloseccion".

estiloetiqueta

Se aplica a las etiquetas en general.

estiloetiqueta(n)

Se aplica a la etiqueta especificada con el número. Tiene precedencia sobre "estiloetiqueta".

estilodatos

Se aplica a los campos de datos en general.

estilodatos(n)

Se aplica al campo de datos especificado con el número. Tiene precedencia sobre "estilodatos".

estilopiedetabla

Se aplica al pie de tabla.

Clases CSS

clase

Este parámetro es insertado en el atributo "class" de la tabla, y afecta a toda la ficha.

clasetitulo

Este parámetro es insertado en el atributo "class" del título.

claseimagen

Este parámetro es insertado en el atributo "class" de las imágenes.

clase(n)

Este parámetro es insertado únicamente en el atributo "class" del campo de datos que se especifique con el número. Si no hay datos no tiene efecto.

clasefila(n)

Este parámetro es insertado en el atributo "class" de tanto la etiqueta como el campo de datos que correspondan al número especificado (es decir, toda la fila). Si no se inserta una etiqueta, equivale a usar el parámetro "clase(n)" con el mismo número. Este parámetro no tiene efecto en secciones.

clasesubtitulo

Este parámetro es insertado en el atributo "class" de los subtítulos.

clasepiedetabla

Este parámetro es insertado en el atributo "class" del pie de tabla.

Esta plantilla soporta la adición de información de microformatos. Esto se hace añadiendo el atributo "class" a una determinada celda de datos, indicando que clase de información contiene. Por ejemplo, para marcar una ficha como una "vCard", se agrega el siguiente parámetro:

|clase = vcard

Y para cada campo de datos, el parámetro correspondiente:

|clase1 = fn
|clase2 = org
|clase3 = tel

...y así para todos los parámetros "clase" de la plantilla.

Véase microformats.org para más información sobre microformatos en general.

Cabeceras

Ver también Especial:Preferencias y activar el accesorio «Muestra imágenes en las cabeceras de las fichas versión 2.»

Al ser una metaplantilla basada en el diseño de Ficha v2, esta usa cabeceras específicas de acuerdo a la temática de la plantilla. Para usar las cabeceras se pueden usar dos parámetros:

tipocabecera

Establece el tipo de cabecera. Este parámetro es un alias del parámetro "clasetitulo", y, si bien su objetivo es otro, tienen el mismo efecto en el resultado final de la ficha (salvo en caso de que se use la clase "media"). Sin embargo, para establecer clases que no sean del tipo "cabecera", se debe usar siempre "clasetitulo".

media

Si este parámetro se establece en "sí" entonces se establece al título la clase "media" en vez de la clase "cabecera". Esto permite títulos más compactos.

Enlaces ver/discusión/editar

nombre

El nombre de la página de la plantilla a la que los enlaces "ver/discusión/editar" deberían apuntar (sin el espacio de nombres "Plantilla:"). Puede usarse {{subst:PAGENAME}}. Si este parámetro es omitido los enlaces no se mostrarán.

Campos opcionales

Una fila con una etiqueta pero sin un campo de datos no se muestra. Esto facilita la creación de filas opcionales. Para hacer una fila opcional se tiene que incluir un parámetro que predetermine el contenido de esta a una cadena vacía:

|etiqueta5 = Población
|datos5  = {{{población|}}}

De esta forma si en el artículo no se define el parámetro de población, la fila no se muestra.

Para campos más complejos con contenidos con un formato predefinido que seguirían estando presentes incluso si el parámetro no se estableciera, se puede incluir el contenido en una instrucción #if (en español: "si") para hacer que desaparezca todo cuando el parámetro no se use. Por ejemplo, la instrucción #if en el siguiente ejemplo se lee como:

"si:el parámetro masa ha sido proporcionado|entonces mostrarlo, seguido de kg"

|etiqueta6 = Masa
|datos6  = {{#if:{{{masa|}}}|{{{masa}}} [[kg]]}}

Para más información sobre el uso de #if, véase este artículo.

También es posible hacer secciones opcionales de manera similar. Si se quiere que una sección aparezca solo si uno o más campos de datos que la acompañan son proporcionados, se podría usar el siguiente modelo como un ejemplo de como hacerlo:

{{Ficha
|título       = Ejemplo de una sección opcional
|seccion1     = {{#if:{{{elemento1}}}{{{elemento2}}}{{{elemento3}}}|Sección opcional}}
|etiqueta2    = Elemento1
|datos2       = {{{elemento1}}}
|etiqueta3    = Elemento2
|datos3       = {{{elemento2}}}
|etiqueta4    = Elemento3
|datos4       = {{{elemento3}}}
}}

seccion1 se mostrará si se definen cualquiera de los parámetros elemento1, elemento2 o elemento3. Si no se define ningúno de éstos parámetros entonces no se mostrará la sección.

La instrucción #if devolverá false (falso) únicamente cuando no haya nada en la condición (lo que sigue después de los dos puntos y finaliza con la primera barra vertical que no pertenezca a un parámetro), por lo tanto la instrucción fallará solo si no se define ningún parámetro.

Ejemplos de uso

Título de prueba
Subtítulo de prueba
Subtítulo de prueba 2
Pie izquierdo Pie derecho
Pie
Pie2
Sección
Datos
Todos definidos (sección)
Etiqueta y datos (etiqueta)	Etiqueta y datos (datos)
Pie inferior
Pie de tabla

{{Ficha
|titulo          = Título de prueba
|tipocabecera    = humano
|subtitulo       = Subtítulo de prueba
|subtitulo2      = Subtítulo de prueba 2
|imagenizquierda = example.png
|tamañoimagenizquierda = 75px
|pieizquierdo    = Pie izquierdo
|imagenderecha   =  example.png
|tamañoimagenderecha = 75px
|piederecho      = Pie derecho
|imagen          = example.png
|tamañoimagen    = 150px
|pie             = Pie
|imagen2         = example.png
|tamañoimagen2   = 90px
|pie2            = Pie2

|estiloseccion  = background:#ccf;
|estiloetiqueta = background:#ddf;

|seccion1  = Sección
|etiqueta1 = 
|datos1    = 
|seccion2  = 
|etiqueta2 = Etiqueta
|datos2    = 
|seccion3  =
|etiqueta3 = 
|datos3    = Datos
|seccion4  = Todos definidos (sección)
|etiqueta4 = Todos definidos (etiqueta)
|datos4    = Todos definidos (datos)
|seccion5  =
|etiqueta5 = Etiqueta y datos (etiqueta)
|datos5    = Etiqueta y datos (datos)

|imageninferior  = example.png
|tamañoimageninferior = 110px
|pieinferior     = Pie inferior

|piedetabla       = Pie de tabla
|estilopiedetabla = background:#ddf;
}}

Título de prueba
Etiqueta 1	Datos 1
Etiqueta 2	Datos 2
Etiqueta 3	Datos 3
Sección 4
Etiqueta 5	Datos 5: Lorem ipsum dolor sit amet, consectetur adipisicing elit.
Pie de tabla

Sintaxis completa

(Nota: La plantilla soporta hasta 75 filas; pero aquí solo se incluyen 20 ya que fichas más grandes son raras. Para usar más de 20 solo extiende la numeración como se requiera. Los parámetros "clase" también son omitidos ya que no son usados comúnmente.)

{{Ficha
|estilo = 

|titulo = 
|estilotitulo = 
|colorfondotitulo = 

|subtitulo = 
|subtitulo2 = 
|estilosubtitulo = 

|estiloimagen = 
|estilopie = 

|imagen = 
|tamañoimagen = 
|pie = 

|imagen2 = 
|tamañoimagen2 = 
|pie2 = 

|imagenizquierda = 
|tamañoimagenizquierda = 
|pieizquierdo = 

|imagenderecha = 
|tamañoimagenderecha = 
|piederecho = 

|estiloseccion = 
|estiloetiqueta = 
|estilodatos = 

|seccion1   = 
|etiqueta1  = 
|datos1     = 
|seccion2   = 
|etiqueta2  = 
|datos2     = 
|seccion3   = 
|etiqueta3  = 
|datos3     = 
|seccion4   = 
|etiqueta4  = 
|datos4     = 
|seccion5   = 
|etiqueta5  = 
|datos5     = 
|seccion6   = 
|etiqueta6  = 
|datos6     = 
|seccion7   = 
|etiqueta7  = 
|datos7     = 
|seccion8   = 
|etiqueta8  = 
|datos8     = 
|seccion9   = 
|etiqueta9  = 
|datos9     = 
|seccion10  = 
|etiqueta10 = 
|datos10    = 
|seccion11  = 
|etiqueta11 = 
|datos11    = 
|seccion12  = 
|etiqueta12 = 
|datos12    = 
|seccion13  = 
|etiqueta13 = 
|datos13    = 
|seccion14  = 
|etiqueta14 = 
|datos14    =
|seccion15  = 
|etiqueta15 = 
|datos15    = 
|seccion16  = 
|etiqueta16 = 
|datos16    = 
|seccion17  = 
|etiqueta17 = 
|datos17    = 
|seccion18  = 
|etiqueta18 = 
|datos18    = 
|seccion19  = 
|etiqueta19 = 
|datos19    = 
|seccion20  = 
|etiqueta20 = 
|datos20    = 

|imageninferior = 
|tamañoimageninferior = 
|pieinferior = 

|estilopiedetabla = 
|piedetabla = 

|nombre = {{subst:PAGENAME}}
}}

Algoritmos Evolutivos de Estimación ===

El comportamiento de los Algoritmos Genéticos dependen en gran parte de los operadores de cruce y mutación , las probabilidades de cruce y mutación, el tamaño de la población , la tasa de reproducción generacional, el número de generaciones, etc.

La determinación de valores adecuados para dichos parámetros constituye por sí mismo un verdadero problema de optimización. Por otra parte una mala elección de los valores de los parámetros puede llevar a que el algoritmo obtenga soluciones alejadas del óptimo.

Este es uno de los motivos por los que desde hace varios años se han venido estudiando alternativas a los métodos heurísticos estocásticos existentes que no necesitasen el ajustar un número alto de parámetros. Otro motivo básico por el que se ha desarrollado la búsqueda de nuevos métodos heurísticos de optimización es por la necesidad de identificar las interrelaciones entre las variables utilizadas para representar a los individuos con la codificación utilizada.

Nueva familia

Todo ello ha motivado al nacimiento de una nueva familia de algoritmos evolutivos llamados Algoritmos Evolutivos con estimación de distribuciones (EDAs). Estos son algoritmos basados en poblaciones al igual que los algoritmos genéticos en los que la transición de una generación a otra ha sido modificada, y basan su búsqueda en el carácter estocástico de la misma, sin embrago a diferencia de los AGs, en los EDAs no existen los operadores de cruce y mutación.

En su lugar la población de individuos se regenera mediante una distribución de probabilidad, que se estima a partir de una base de datos formada por individuos de generaciones anteriores, es decir se sustituyen los operadores de cruce y mutación, por operadores que estiman o “aprenden” la distribución de probabilidad de los puntos seleccionados en la generación anterior. Se utilizan para resolver problemas de optimización en los cuales las variables de decisión son reales (xi€R), en una generación la población se construye realizando un muestreo probabilístico de la población anterior y escogiendo los mejores individuos.

Mientras que en los algoritmos genéticos las interrelaciones entre las variables representando a los individuos se tienen en cuenta de manera implícita, en los EDAs dichas interrelaciones se expresan de manera explícita a través de la distribución de probabilidad asociada con los individuos seleccionados en cada generación.

Pasos que siguen los algoritmos evolutivos

1. En primer lugar, se genera la población inicial formada por N puntos, que frecuentemente se realiza asumiendo una distribución uniforme de cada variable. Tras generar los puntos, estos se evalúan mediante la aplicación de la función de adaptabilidad o de costo (función objetivo).
2. Segundo, en cada generación se seleccionan M puntos (M ≤N) siguiendo un criterio de selección.
3. Tercero, se induce el modelo probabilístico n-dimensional que mejor representa las interdependencias entre las n variables. Este paso es conocido como el de aprendizaje, y es el más crucial en los EDAs debido a la importancia de tener en cuenta todas las dependencias entre las variables para asegurar mejoras sucesivas de los puntos.
4. Finalmente, la nueva población se conforma con N nuevos puntos obtenidos tras simular o muestrear la distribución de probabilidad aprendida en el paso previo. Es frecuente en este paso utilizar una aproximación elitista, que mantiene el mejor o los mejores puntos de la población t–1 en la nueva población. En este caso, se crean en cada generación un total de N – E puntos, donde E representa el número de puntos élites.

Los pasos 2, 3 y 4 se repiten mientras no se cumple una condición de parada en concreto. Ejemplos de criterios de parada son: llegar a un número máximo de generaciones, uniformidad de la población generada, no mejora con respecto al mejor de los puntos obtenido en las generaciones previas, etc. A continuación se muestra el pseudocódigo de un EDAs.

Pseudocódigo.JPG

Estructura general de un Algoritmo de Estimación de distribuciones

Estructura.JPG

Como se puede observar al igual que en la mayoría de los algoritmos generacionales, se parte de una población inicial con m individuos, generada (en la mayoría de los casos) aleatoriamente. En el segundo paso se selecciona un número n (n<=m) de individuos, se selecciona normalmente aquellos con los mejores valores en la función de evaluación) como base de datos para la estimación del modelo . A continuación se introduce el modelo probabilístico n-dimensional que mejor refleja las interdependencias entre las n variables. A partir del modelo inducido se genera una población auxiliar mediante muestreo. Por último la nueva población D_k se obtiene a partir de la población anterior D_ {k-1} y de la población auxiliar. Normalmente esta selección se realiza de forma elitista. A continuación se muestra como proceden los EDAs para arrojar las nuevas generaciones.

Fig # 3. Diagrama ejemplificando la operativa de un EDA.

Como se puede observar, partimos de una población inicial de individuos a la cual aplicamos un proceso de selección, en este paso decantamos aquellos individuos menos prometedores a mejorar nuestra función objetivo, posteriormente utilizando los individuos seleccionados determinamos el modelo que caracteriza las relaciones existentes entre las variables, este modelo permite luego aplicando un muestreo estocástico seleccionar la nueva generación.
El principal problema que se presenta es la estimación del modelo M, ya que cuanto más complejo sea el modelo mejor recogerá las dependencias entre las variables, pero más compleja/costosa será su estimación, puesto que en cada generación un nuevo modelo puede ser construido.

Formas fundamentales de realizar el modelado

• Análisis univariado: este es el modelo más simple, no considera relaciones entre las variables y las probabilidades conjuntas se factorizan como producto de distribuciones (marginales) univariadas e independientes.
• Análisis bivariados: permite la dependencia entre las variables, sin embargo la dependencia se restringe a dos variables, ej: xj depende de xi y solo de xi. En este caso es necesario realizar dos tareas: hallar el grafo de dependencia y calcular las probabilidades condicionales P (xj|xi). Se puede decir que existen heurísticas específicas para determinar el grafo de dependencia.
• Análisis multivariado: es el enfoque más completo, pero también el más complejo de implementar, los modelos estadísticos utilizados son de orden n, típicamente se modelan mediante redes bayesianas. Para obtener la población en t+1 se realiza el muestreo de M, habitualmente mediante la utilización de modelos lógicos probabilísticos.
  Las diferencias consisten en el tipo de relaciones que son consideradas para la construcción del modelo.

Fuente

---

Tesis de Isabel María Higuera Igarza.