« Algoritmos de hormiga… « || Inicio || » Redes Neuronales: una… »

Ejercicios de PSO y ACO

Última modificación: 10 de Septiembre de 2016, y ha tenido 268 vistas

  1. Teniendo en cuenta que los algoritmos de hormigas y PSO son para optimizar funciones, repite los ejercicios de la relación de Búsquedas Locales y Algoritmos Genéticos, pero haciendo uso de PSO, Colonias de Hormigas.

Algoritmos de Hormigas

  1. Implementa una solución al Problema del Viajante haciendo uso de Colonias de Hormigas pero en casos en los que el grafo subyacente a las ciudades no sea el grafo completo (es decir, no estén todas las posibles conexiones entre ciudades).
  2. Busca posibles mejoras sobre el algoritmo de hormigas para resolver el problema de viajante.
  3. Haz uso de algoritmos de hormigas para calcular caminos mínimos en grafos. Introduce variantes en los que no se base en la distancia de la arista, sino en pesos que puedan tener.
  4. Implementa el algoritmo de hormigas elitista, en el que de forma adicional se incrementa la feromona de la mejor solución encontrada hasta el momento.
  5. Implementa el algoritmo de hormigas con ranking, en el que únicamente se añade feromona a las \(k\) mejores soluciones de cada vuelta, junto con la mejor solución encontrada hasta el momento.
  6. Resolver el problema de asignación de tareas haciendo uso de algoritmos de hormigas. Este problema se puede plantear como sigue: Hay un número de agentes (\(\{a_i: 1\leq i\leq n\}\)) y un número de tareas a realizar (\(\{t_j: 1\leq j \leq m\}\)). Cualquier agente puede ser asignado para desarrollar cualquier tarea, contrayendo algún coste  (\(c_{ij}\)) que puede variar dependiendo del agente, \(i\), y la tarea, \(j\), asignados. Es necesario para desarrollar todas las tareas asignar un solo agente a cada tarea para que el coste total del asignación sea minimizado, aunque un mismo agente podría realizar más de una tarea, pero ha de tenerse en cuenta que la realización de la tarea \(t_j\) por el agente \(a_i\) conlleva el uso de una serie de recursos (\(r_{ij}\)) del agente, y éstos están acotados por una cantidad fija, \(b_i\), para cada agente. 

PSO

  1. El algoritmo PSO visto en clase usa una discretización de la función que se está optimizando por medio de los patches. Haz los cambios necesarios para que se pueda usar con funciones no discretizadas sin considerar los patches (esto es, si tenemos una función f(x,y), cada partícula no mira el valor que hay en el patch que tiene debajo, sino que directamente evalúa el valor de f en su posición).
  2. Implementa un PSO en el que haya familias de partículas, de forma que no se guían por al mejor obtenido del total, sino únicamente de la familia a la que pertenecen.
  3. Implementa un PSO en el que la comunicación entre partículas venga determinada por la posición que ocupan, es decir, que cada partícula solo puede saber los valores alcanzados por partículas que están dentro de un determinado radio.
  4. Hacer una implementación de PSO en el que la vecindad de cada partícula (es decir, el conjunto de partículas de las que puede obtener información) viene dado por un grafo prefijado a priori. Haz pruebas de cómo funciona el algoritmo para distintos tipos de grafos con el mismo número de nodos (por ejemplo, con grafos aleatorios en los que el número de aristas varía, o para grafos generados siguiendo el algoritmo de enlace preferencial).
  5. Al igual que hemos optimizado el problema del tráfico 1D por medio de PSO, haz uso de otros modelos de NetLogo que puedas optimizar haciendo uso del mismo algoritmo.
  6. Utiliza PSO para optimizar los parámetros de los que depende el algoritmo de Colonias de Hormigas para un caso concreto (por ejemplo, una instancia concreta del problema del viajante).

« Algoritmos de hormiga… « || Inicio || » Redes Neuronales: una… »