2014

Multi-objetive evolutionary algorithms for unstructured P2P topologies reconfiguration

 Descargar versión PDF

Profesores: Dra. Elizabeth Pérez Cortés y Dr. Hiroyuki Sato (University of Tokyo, Japón)

Resumen: Nowadays one of the main usages of the Internet is content generation, sharing and access. One of the approaches used to support these activities is the P2P model. In content distribution systems using this model, instead of having servers to distribute the contents, nodes are self organized to do it. Each node is a potential server and a client and this characteristic makes those systems naturally scalable and fault tolerant. In order to coordinate their actions, the nodes of a P2P system establish logical connections between them and those connections define an overlay network (called P2P network). There are two main classes of P2P networks: structured and unstructured. We are interesting on the second class, where there are no specific rules to define the neighborhood of a newcomer.

The reconfiguration of a P2P network is generally performed through a protocol to integrate new peers and a protocol to deal with those that leave the system. The goal of these protocols is to preserve the connectivity. A reconfiguration can also address the change in the interests of users, by example, by adjusting the amount of links of a peer to the popularity of its shared resources or by allowing a peer to change its neighborhood when this one is not interesting for it anymore. The reconfiguration of an unstructured P2P network can be seen as the problem of selecting, among all the possible connected undirected labeled graphs, the optimal one for the current participant peers and their interests. The prohibitive computational costs of an exhaustive approach provide an opportunity to use evolutionary computation to adaptively optimize the topology. In this project we are interested in the exploration of distributed control, local information multi-objective evolutionary algorithms as a strategy to perform periodic reconfiguration of unstructured P2P topologies.

Objetivo general

• The design and implementation of an effective an efficient multi-objetive evolutionary algorithm to perform the reconfiguration of an unstructured P2P topology.

Objetivos específicos

• Identify and understand the different distributed control, local information multi-objetive evolutionary algorithms proposed to perform the reconfiguration of an unstructured P2P topology.
• Design in a distributed control, local information multi-objetive evolutionary algorithm to perform reconfiguration in unstructured P2P topologies.
• Evaluate the proposed algorithm.
• Assess the relative importance of the different objetives used in the reconfiguration of an unstructured topology.

Soporte para el elitismo en algoritmos evolutivos multiobjetivo paralelos

 Descargar versión PDF

Profesores: Dr. Antonio López Jaimes (UAM Cuajimalpa) y Dra. Elizabeth Pérez Cortés

Resumen: La mayoría de los problemas de optimización del mundo real involucran dos o más objetivos que se tienen que optimizar simultáneamente y que se encuentran en conflicto. Como resultado, a diferencia de la optimización de un solo objetivo, en la optimización multiobjetivo no hay una solución óptima sino un conjunto de soluciones compromiso óptimas (llamadas frente de Pareto). Estas soluciones son óptimas en el sentido que no es posible mejorar un objetivo sin deteriorar otro. Los algoritmos evolutivos (AEs) fueron diseñados para resolver problemas de optimización del mundo real en los que las técnicas clásicas de programación matemática tienen un desempeño pobre o incluso no pueden aplicarse. Los algoritmos evolutivos son particularmente adecuados para resolver problemas multiobjetivo ya que mantienen simultáneamente un conjunto de soluciones para obtener  una  muestra  del  frente  de  Pareto.

El elitismo es el mecanismo para evitar perder las mejores soluciones encontradas durante la ejecución de un AE debido a efectos estocásticos. Este concepto juega un papel  importante  en AE modernos  ya  que  junto  con  la mutación, garantiza convergencia global. Existen dos enfoques principales para implementar el elitismo. Uno de ellos combina la población anterior y la nueva, y posteriormente utiliza una selección determinista para mantener a las mejores soluciones en la siguiente generación. En el otro enfoque se mantiene un conjunto externo de soluciones llamado “archivo” que mantiene las mejores soluciones encontradas durante la búsqueda. Existen múltiples esfuerzos para encontrar una estructura de datos que permita el mantenimiento eficiente del archivo en un entorno centralizado y, en este proyecto, estamos interesados en hacer lo propio par a un entorno paralelo. En otras palabras, estamos interesados en diseñar un algoritmo de archivado paralelo de manera que pueda contener un gran número de soluciones (> 5× 10⁵).

Objetivo general

• Diseñar un algoritmo paralelo de archivado capaz de mantener de manera eficiente un gran número de soluciones (> 5 x 10⁵).

Objetivos específicos

• Identificar los algoritmos de archivado propuestos actualmente que puedan implementarse en paralelo directamente.
• Conocer la eficiencia relativa de los algoritmos de archivado identificados.
• Proponer un algoritmo de archivado paralelo (posiblemente basado en una versión secuencial existente) para ejecutarse en un multiprocesador débilmente acoplado (e.g., un cluster).
• Poner el algoritmo implementado a disposición de la comunidad de computación evolutiva.

Soporte para el elitismo en algoritmos evolutivos multiobjetivo

 Descargar versión PDF

Profesores: Dra. Elizabeth Pérez Cortés y Dr. Antonio López Jaimes (UAM Cuajimalpa)

Resumen: La mayoría de los problemas de optimización del mundo real involucran dos o más objetivos que se tienen que optimizar simultáneamente y que se encuentran en conflicto. Como resultado, a diferencia de la optimización de un solo objetivo, en la optimización multiobjetivo no hay una solución óptima sino un conjunto de soluciones compromiso óptimas (llamadas frente de Pareto). Estas soluciones son óptimas en el sentido que no es posible mejorar un objetivo sin deteriorar otro. Los algoritmos evolutivos (AEs) fueron diseñados  para  resolver  problemas  de optimización del mundo real en los que las técnicas clásicas de programación matemática tienen un desempeño pobre o incluso no pueden aplicarse. Los algoritmos evolutivos son particularmente adecuados para resolver problemas multiobjetivo ya que mantienen simultáneamente un conjunto de soluciones para obtener una muestra del frente de Pareto.

El elitismo es el mecanismo para evitar perder las mejores soluciones encontradas durante la ejecución de un AE debido a efectos estocásticos. Existen dos enfoques principales para implementar el elitismo. Uno de ellos combina la población anterior y la nueva, y posteriormente utiliza una selección determinista para mantener a las mejores soluciones en la siguiente generación. En el otro enfoque se mantiene un conjunto externo de soluciones llamado “archivo” que mantiene las mejores soluciones encontradas durante la búsqueda. Existen múltiples esfuerzos para encontrar una estructura de datos que permita el mantenimiento eficiente del archivo en un entorno centralizado. En este proyecto estamos interesados en compilar y analizar el rendimiento relativo de las estructuras de datos existentes para la implementación del elitismo mediante un archivo.

Objetivo general

• Contar con una estructura de datos eficiente para implementar el elitismo mediante un archivo en los AEs.

Objetivos específicos

• Identificar las estructuras de datos existentes para implementar el archivo en AEs.
• Conocer el rendimiento relativo de las estructuras de datos existentes para implementar el archivo.
• Proponer una estructura de datos eficiente para almacenar el archivo (posiblemente basado en alguna de las existentes).
• Poner la estructura de datos implementada a disposición de la comunidad de computación evolutiva.

Construcción de índices semánticos para el intercambio abierto de recursos basado en contenidos

 Descargar versión PDF

Profesora: Dra. Reyna Carolina Medina Ramírez

Resumen: La  información  en  la  web  es  vasta  y  heterogénea  tanto  en  contenido  como en  formato, metodologías de representación y almacenamiento de la información gestionada, así como algoritmos y sistemas de búsqueda, han sido propuestos e implementados con éxito. Sin embargo, el enfoque utilizado todavía no ha explotado la naturaleza de los recursos existentes (significado en función de un contexto, vínculos entre los datos existentes en los documentos). Una memoria organizacional comparte varias características y problemas similares con la Web en general, la única diferencia es el volumen de documentos a ser gestionados e interrogados. Una memoria corporativa, es la representación explícita de los conocimientos de una organización materializados en lo que se conoce como recursos. Los recursos pueden ser personas y/o documentos heterogéneos, tanto en contenido como en formato. Entre los diversos enfoques para gestionar estos recursos, se encuentra el enfoque de la Web semántica.

La identificación de tareas y paradigmas de los sistemas de búsqueda semántica (vinculada), algoritmos para evitar la ambigüedad de términos, marcos de referencia para   la generación automática de descripciones semánticas, paradigmas de consulta para sistemas de búsqueda semántica, aplicaciones del aprendizaje maquinal, el procesamiento del lenguaje natural y técnicas de extracción de información en el contexto de búsqueda semántica, son sólo algunas de las áreas en las que se sigue investigando respecto a la búsqueda de información “vinculada”. Por lo anterior, se desea proponer un marco de referencia para la construcción de índices semánticos que permitan el intercambio abierto (Linked Open Data) de recursos basado en contenidos. En particular, se trata de generar por un lado, índices semánticos que permitan guiar el  almacenamiento y la recuperación de recursos de información al interior de una memoria corporativa, apegándose al enfoque de datos abiertos enlazados. Por el otro lado, diseñar y construir un prototipo que permita evaluar la propuesta.

Objetivo general

• Proponer un marco de referencia para la construcción de índices semánticos que permitan el intercambio abierto (Linked Open Data) de recursos basado en contenidos.

Objetivos específicos

• Caracterizar la naturaleza de la información al interior de la memoria de estudio (educativa).
• Proponer un método para la generación de índices semánticos, apoyado en el contenido de los recursos almacenados en la memoria educativa.
• Establecer un marco general apegado a estándares para la vinculación entre documentos orientados por el uso de sus contenidos (índices semánticos).
• Diseñar y construir un prototipo que permita caracterizar la naturaleza de la información al interior de una memoria educativa y su vinculación con otros recursos de información.

Difusión en fractales y aplicaciones

 Descargar versión PDF

Profesores: Dra. Cristi Darley Guevara (Universidad Estatal de Arizona) y Dr. Miguel Alfonso Castro García

Resumen: Intuitivamente, un fractal es una estructura matemática (conjunto) que posee patrones de autorreferencia y de autosimilitud o autosemejanza, es decir, el conjunto se construye de manera recursiva y presenta la mism apariencia a diferentes escalas. Este tipo de conjuntos se caracterizan por poseer una dimensión no entera. Las primeras herramientas para su estudio fueron los procesos de Levy y movimientos Brownianos, los cuales describen procesos de difusión como un límite escalado de caminatas aleatorias en movimientos geométricos sugiriendo la existencia de un generador que actuaría como el Laplaciano y dando algunas propiedades. En medios porosos, los modelos matemáticos que se han propuesto hasta la fecha para pruebas de pozos (yacimientos) y acuíferos, ya sea que cuenten con una estructura subterránea fractal o no, se pueden   clasificar, en forma general, de dos maneras distintas: modelos locales o diferenciales, y modelos no locales o integrodiferenciales.

Nuestra idea inicial es tomar la teoría desarrollada por Kigami, la cual por su “complejidad matemática” no ha sido aplicada en problemas físicos y reproducir el modelo de Chang-Yortsos sobre un triángulo, un tetraedro y una carpeta de Sierpinski y observar el comportamiento del caudal de flujo sobre estos fractales.

Objetivo general

• Comparación de la difusión evolutiva sobre conjuntos autosimilares poscríticos ramificados finitos con modelos de caudal de flujo para pozos y/o contaminantes acuíferos.

Objetivos específicos

• Paralelar algoritmos existentes implementando elemento finito (Python-C).
• Comprender los modelos de derivadas fraccionarias mencionados.
• Comparar los datos entre los modelos mencionados (en derivadas fraccionarias) y comparación con resultados de la simulación de la difusión en conjuntos autosimilares poscríticos ramificados finitos.
• Elaboración de una herramienta computacional (prototipo) que permita la estimación de parámetros de los modelos.

Diseño e implementación de un serializador/deserializador de objetos a XML

 Descargar versión PDF

Profesor: Dr. Carlos Roberto Jaimez González (UAM Cuajimalpa)

Resumen: La serialización es el proceso de transformar un objeto a un estado en el que pueda ser almacenado permanentemente. La serialización de objetos a XML proporciona una representación que es entendible por el ser humano y por una computadora, además de que promueve la interoperabilidad entre diferentes lenguajes de programación. La interoperabilidad es una característica importante en los sistemas distribuidos basados en objetos, ya que permite la comunicación de programas (clientes y servidores), escritos en diferentes lenguajes de programación orientados a objetos. Existen algunos problemas fundamentales que tienen que ser resueltos por los diferentes lenguajes para alcanzar la interoperabilidad. Algunos de estos problemas están relacionados con el mapeo de tipos de datos, la representación de los objetos, los mensajes, y la serialización y la deserialización. La problemática de este proyecto es lograr la interoperabilidad del serializador propuesto, con los serializadores WOX existentes, los cuales están escritos en Java, C#, Python y PHP. Dentro de los problemas a resolver se encuentran los siguientes: el mapeo de tipos de datos entre lenguajes de programación, la representación de los objetos, y los procesos de serialización y deserialización.

Objetivo general

• Diseñar e implementar un serializador/deserializador de objetos a XML.

Objetivos específicos

• Implementar un serializador de objetos a XML en el lenguaje de programación orientado a objetos elegido.
• Implementar un deserializador de XML a objetos en el lenguaje de programación orientado a objetos elegido.
• Implementar un módulo para generación automática de clases en el lenguaje de programación orientada a objetos elegido, a partir de la presentación XML de un objeto.
• Desarrollar un sitio Web con documentación y ejemplos para el serializador/deserializador.

Diseño de un algoritmo multiobjetivo bioinspirado para generar zonas electorales

 Descargar versión PDF

Profesores: Dr. Miguel Ángel Gutiérrez Andrade y Dr. Eric Alfredo Rincón García (UAM Azcapotzalco)

Resumen: El diseño de zonas es un problema que consiste en agrupar unidades geográficas en un número predeterminado de zonas que minimizan una función objetivo, al tiempo que se satisfacen ciertas restricciones, principalmente relacionadas con su topografía. Dentro de sus aplicaciones más frecuentes se encuentran el diseño de distritos electorales, diseño de zonas de ventas, diseño de zonas escolares y el uso de tierras. Con este planteamiento, el diseño de zonas puede presentar objetivos  múltiples, posiblemente en competencia entre sí, lo cual hace necesario llegar a una solución en la que todos los objetivos sean satisfechos en un grado aceptable. Para simplificar su solución, muchos de estos problemas tienden a modelarse como mono – objetivo usando sólo una de las funciones originales y manejando las adicionales como restricciones, o bien con una función objetivo obtenida como la suma ponderada de los objetivos originales.

En esta propuesta de trabajo de investigación se diseñará un algoritmo multiobjetivo basado en una técnica bioinspirada como colonia de abejas artificiales, optimización por colonia de hormigas, optimización por enjambre de partículas, entre otras, para el diseño de zonas electorales con dos objetivos, equilibrio poblacional y compacidad geométrica. El algoritmo será aplicado en instancias reales obtenidas en el Instituto Federal Electoral, y los resultados obtenidos se compararán con los reportados en la literatura existente.

Objetivo general

• Diseñar un algoritmo para construir zonas que promuevan el equilibrio poblacional y la compacidad geométrica.

Objetivos específicos

• Realizar el estado del arte de las diferentes técnicas multiobjetivo bioinspiradas.
• Diseñar un algoritmo multiobjetivo basado en técnicas bioinspiradas para construir zonas que promuevan el equilibrio poblacional y la compacidad geométrica.
• Aplicar el algoritmo diseñado en instancias reales.
• Comparar los resultados obtenidos con los reportados en la literatura especializada.

Un sistema clasificador no supervisado utilizando coloración de gráficas suaves

 Descargar versión PDF

Profesores: Dr. Pedro Lara Velázquez y Dr. Miguel Ángel Gutiérrez Andrade

Resumen: Un sistema clasificador no supervisado es un tipo especial de reconocimiento de patrones, significa poner una etiqueta a un objeto de acuerdo con sus características. Por ejemplo, cuando alguien observa una foto de un grupo de personas, se puede reconocer si alguno de ellos es alguien conocido, o si se está clasificando la ropa sucia, se puede hacer una pila de “ropa blanca” y una de “ropa oscura”. Los seres humanos hacemos reconocimiento de patrones cotidianamente, aunque lo hacemos de forma inconsciente. El reto de un modelo de reconocimiento de patrones es enseñarle a una computadora a hacer esta actividad de una forma eficiente.

Dado un conjunto de objetos no clasificados, podemos crear una medida de la distancia entre ellos, por ejemplo, si ponemos una medida de la cantidad de luz que refleja un paño podemos decidir si pertenece a la pila de “blancos” u “obscuros”. Si la luz que reflejan dos piezas de ropa es similar, es muy probablemente estarán en la misma pila, o si difieren mucho en luminosidad, van a estar en pilas diferentes. En este caso, la distancia entre objetos se está dando por una sola variable, que es la luminosidad, pero en general, la clasificación se realiza considerando métricas más complejas. El problema de coloración de gráficas suaves busca encontrar una coloración que minimiza la “tensión” en la gráfica, es decir, minimizar la suma de distancias entre vértices con colores idénticos. Este modelo se utiliza en la programación de eventos susceptibles de cambios, asignación estable de frecuencias del espectro electromagnético entre otros. Se ha demostrado que es un problema NP-duro aunque para instancias pequeñas, máximo de 20 vértices, se utilizan algoritmos exactos que resuelven el problema. Para instancias más grandes el uso de técnicas heurísticas es necesario y se cuenta con varios algoritmos genéricos que resuelven el problema de forma aproximada.

Objetivo general

• Construir un algoritmo para un sistema clasificador de uso general con el modelo de coloración de gráficas suaves.

Objetivos específicos

• Diseñar e implementar un algoritmo de reconocimiento de patrones, ya sea en lenguaje C o FreeBasic bajo el esquema de coloración de gráficas suaves.
• Aplicar el algoritmo para la clasificación de varias instancias benchmark.

Modelo filológico para lenguas romances y germánicas utilizando coloración de gráficas suaves

 Descargar versión PDF

Profesores: Dr. Pedro Lara Velázquez y Dr. Sergio Gerardo de los Cobos Silva

Resumen: El concepto de protolenguaje indoeuropeo fue creado a finales del siglo XIX en Alemania por Franz Bopp, quien notó la gran similaridad entre el alemán y el sánscrito en su libro Gramática comparativa. Bajo este modelo se reconocen 8 subgrupos, de los cuales en esta propuesta se utilizarán dos tipos: instancias en lenguas germánicas y romances. Estos modelos fueron del tipo empírico durante casi 200 años, hasta donde se propone un modelo filológico donde se consideran gráficas y se propone una métrica entre lenguajes basada en sus características. Esta métrica se puede utilizar como base para la generación de las distancias en un modelo de coloración de gráficas suaves.

El problema de coloración de gráficas suaves busca encontrar una coloración que minimice la “tensión” en la gráfica, es decir, minimizar la suma de distancias entre vértices con colores idénticos. Este modelo se utiliza en la programación de eventos susceptibles de cambios, asignación estable de frecuencias del espectro electromagnético, entre otros. Se ha demostrado que es un problema NP-difícil, aunque para instancias pequeñas, máximo de 20 vértices, se utiliza un modelo de programación lineal entera mixto. Para instancias con más de 20 vértices es necesario el uso de técnicas heurísticas que resuelven el problema de forma aproximada.

Objetivo general

• Crear un modelo filológico para lenguajes romances y germánicos utilizando coloración de gráficas suaves.

Objetivos específicos

• Construcción formal del modelo filológico utilizando coloración de gráficas suaves.
• Seleccionar la mejor métrica al modelo.
• Validar el modelo en un conjunto representativo de lenguas romances.
• Validar el modelo en un conjunto representativo de las lenguas germánicas.

Uso de herramienta borrosa para el estudio de índices económicos

 Descargar versión PDF

Profesores: Dr. Sergio Gerardo de los Cobos Silva y Dr. Eric Alfredo Rincón García (UAM Azcapotzalco)

Resumen: Esta forma de modelación con instrumentos borrosos, ofrece ciertas ventajas sobre la tradicional técnica de regresión. En primer lugar, porque las estimaciones que obtengamos después de ajustar los coeficientes borrosos, no serán variables aleatorias, y por tanto, en muchas ocasiones de difícil tratamiento numérico, sino números borrosos, cuyo tratamiento es más sencillo. Por otra parte, si el fenómeno de estudio es de carácter económico o social, las observaciones que del mismo se obtienen son consecuencia de la interacción entre las creencias, expectativas, etc. de los agentes que participan en dicho fenómeno, y por tanto, ya hemos señalado que en nuestra opinión, no es del todo adecuado modelar dicho fenómeno utilizando la teoría de la probabilidad. Por ejemplo, el precio de los activos que se negocian en los mercados financieros es la consecuencia de las expectativas que tienen los participantes sobre el devenir de la economía, la confianza que a los operadores les generan los emisores de dichos activos etc. Posiblemente en este caso sea excesivamente simplificadora la existencia de linealidad entre la variable explicada y las variables explicativas lo cual se asume utilizando tanto la regresión convencional como la regresión borrosa, pero creemos que es más realista modelar el sesgo que puede darse entre las realizaciones de la variable dependiente y el valor que teóricamente éstas pueden tomar asumiendo que la relación entre variable dependiente y variables explicativas es borrosa, que si damos una naturaleza aleatoria a dicho sesgo.

Objetivo general

• Proponer y diseñar diferentes algoritmos de tipo borroso.
• Aplicar los algoritmos diseñados en instancias reales.

Objetivos específicos

• Realizar el estado del arte de diferentes técnicas borrosas.
• Proponer y diseñar diferentes algoritmos de tipo borroso.
• Aplicar el algoritmo diseñado en instancias reales.
• Comparar los resultados obtenidos con los reportados en la literatura especializada.