Por favor, use este identificador para citar o enlazar este ítem:
http://cimat.repositorioinstitucional.mx/jspui/handle/1008/1025| UN ALGORITMO DE ESTIMACIÓN DE DISTRIBUCIÓN BASADO EN T-CHERRY JUNCTION TREE | |
| JUAN BOSCO ROBLEDO MUÑOZ | |
| Acceso Abierto | |
| Atribución-NoComercial | |
| MATEMÁTICAS INDUSTRIALES COMPUTACIÓN | |
| Existe una familia de Algoritmos Evolutivos que ajustan un modelo de la distribución de probabilidad de los mejores individuos de la población con el fin de utilizar la información del espacio de búsqueda contenida en ellos de manera explı́cita para guiar el proceso de optimización. Son los llamados Algoritmos Evolutivos Basados en Modelos. Entre éstos destacan los Algoritmos de Estimación de Distribución, los cuales hacen simulaciones des- de el modelo para generar nuevos individuos. Una buena parte de estos algoritmos usan Modelos Gráficos Probabilı́sticos, que consisten en una estructura dada por un grafo y sus parámetros; donde los vértices del grafo son las variables del problema y una arista indica que hay dependencia entre las variables que conecta. El costo computacional de manejar este tipo de modelos está en función de la densidad del grafo. Se suelen usar grafos dis- persos ya que es necesario construir el modelo varias veces durante el proceso evolutivo. En este trabajo buscamos hacer uso de manera eficiente de un modelo más denso, lo cual nos permitirá tomar en cuenta más dependencias entre las variables del problema. Se propone para esto la construcción de un t-Cherry Junction Tree de orden k (donde k indica la densidad del modelo) usando el algoritmo propuesto por Proulx y Zhang, con una mejora en cuestión de eficiencia en la métrica de calidad del ajuste a la distribución de probabilidad de los individuos. Se aplica este modelo en un Algoritmo de Estimación de Distribución, que llamamos t-Cherry EDA, y se hace un análisis experimental de su rendimiento en funciones de benchmark comúnmente usadas en la literatura para distintas densidades del grafo. Los resultados muestran que un valor de k adecuado respecto a las propiedades de dependencia de las variables obtiene buenos resultados. Al usar una densidad menor o mayor a la adecuada el rendimiento del algoritmo baja, por lo que una estrategia de adaptación de este valor surge como trabajo futuro. El modelo muestra ser robusto, pues además de las propiedades usadas en este trabajo podemos mencionar que su entropı́a es un buen indicador de convergencia; y los individuos simulados desde él pueden ser usados como vectores de mutación correlacionados. Es por esto que sus posibles aplicaciones se extienden a otras familias de Algoritmos Evolutivos Basados en Modelos. | |
| 09-08-2019 | |
| Tesis de maestría | |
| OTRAS | |
| Versión aceptada | |
| acceptedVersion - Versión aceptada | |
| Aparece en las colecciones: | Tesis del CIMAT |
Cargar archivos:
| Fichero | Descripción | Tamaño | Formato | |
|---|---|---|---|---|
| TE 750.pdf | 9.55 MB | Adobe PDF | Visualizar/Abrir |