Open afdez opened 8 years ago
mariosky
commented
8 years ago Por mi parte puedo implementarlo y ejecutar algunos experimentos para ver como va. El código de su propuesta está disponible?
También en la página de OGR, se incluye un link a una propuesta utilizando GAs http://www.soliday.com/stephen/papers/download.html#ICGA95
¿Que nos recomiendas para la implementación?
vrivas
commented
8 years ago Me parece muy interesante. He encontrado otro trabajo de GA aplicados a este problema: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=5586955 Supongo que habrá más :/
afdez
commented
8 years ago Hola de nuevo. Siento ser tan intermitente en las interacciones pero es que estaba en un pico de trabajo del cual todavía estoy intentando salir ;-(
Mario, tengo código disponible pero es antiguo (lo tendría que buscar en copias de seguridad pues estaban en otro ordenador). La mejor solución que encontramos en nuestro paper (que sigue siendo el estado-del-arte para aplicaciones de metaheurísticas, según lo que sé) era un Scatter Search. Yo creo que es mejor coger cualquiera de las soluciones existentes, o implementar un algorito genético con la codificación de marcas estándar y usar ese. La idea para la investigación es distribuir ese algoritmo, o incluso diferentes algoritmos distintos en un conjunto de nodos diferentes y luego analizar diferentes temas como habéis hecho vosotros en el artículo de origen.
Lo mejor de este problema es es muy sencillo de comprender (se explica en tres minutos), atraería voluntarios y, además, tenemos "adversarios" (poderosos por cierto) contra los cuales medirnos ya que hay una propuesta (tipo SETI), casi por por fuerza bruta, en http://www.distributed.net/OGR. Hay también mucha documentación en Internet sobre propuestas realizadas sobre el problema.
¿Cómo lo veis? Si queréis podemos intentar implementar cada uno una versión de un alfgoritmo para abordar este problema y luego vemos cómo usarlas. Yo por ejemplo podría intentar la codificación basada en distancias ente marcas, y alguno de vosotros la de la codifiación basada en marcas.
Luego habría que pensar en un modelo distribuido de computación voluntaria.
Ya me decís, Saludos, Antonio
mariosky
commented
8 years ago OK,
Hemos estado ocupados con otros experimentos. Queda en la lista de trabajo futuro, pero lo estaré revisando entrando el año, ¿Haz visto alguna representación visual del resultado de los experimentos? Creo que sería interesante para el usuario ver las marcas, por lo menos se imagina uno una regla minimalista para los casos básicos en los que tiene solución continua.
Hola a todos (escribo en Castellano pues todos los que por ahora contribuimos somos hispanoparlantes ;-),
He leído con interés y, cierto detalle, el artículo “Volunteers in the Cloud…” que habéis enviado el Special issue y ahora os indico mis impresiones y posibles sugerencias para que las abordemos si queréis en rabajo futuro (tengo más pero voy a ir propocionándolas gradualmente ;-):
Os propongo pues un problema muy bonito, que tiene mucha practicidad en campos tales como las telecomunicaciones (en este sentido es muy defendible), y que abordé en el pasado con cierto éxito. Se trata del GOLOMB RULER PROBLEM. Es un problema duro, pero a la vez de muy fácil comprensión, que se explica en 5 minutos (escribiendo y en 2 hablando) poniendo un par de ejemplos. Es un problema combinatorio además, lo cual hace que sea más comprensible para el usuario. La ventaja es que (1) por una parte puede atraer a más voluntarios y (2) en el futuro podemos involucrar al usuario en la propia resolución del problema (en forma de aportar información por ejemplo), lo cual es otra de mis propuestas para el futuro.
Otras ventajas de este problema: es escalable, y la mejor solución devuelta por una metaheurísitica tiene tamaño n = 16 (es una propuesta conjunta de Carlos y mía). Se conocen soluciones hasta al menos un tamaño de n = 150, pero sólo se ha probado la optimilidad de ellas (por fuerza bruta en muchos casos y mediante un sistema de cientos de ordenadores distribuidos trabajando en paralelo) hasta un valor de n = 23 o 24. Actualmente existe además un proyecto(8similar al SETI) de computación voluntaria en la cual se añaden ordenadores y el esfuerzo se realiza para probar la optimalidad de las soluciones a partir de n>23, todo por FUERZA BRUTA: mirad en http://www.distributed.net/OGR, donde encontraréis mucha información y la definición sencilla del problema.
Podríamos pues variar el problema, abordar lo que ya se ha hecho (repetir algo de los mismos experimentos) , ver hasta qué tamaño podemos manejar. Lo bueno además es que, al ser escalable, pues si resolvemos – o sea, encontramos el óptimo de - una instancia de tamaño n (los óptimos son conocidos o hay una solución conocida que puede ser mejorable) pues AUTOMÁTICAMENTE podemos pasar a resolver la instancia de valor n+1.
¿Cómo lo véis? El problema es fácil de codificar (de forma natural es una secuencia creciente de números distintos, aunque se podría codificar como la distancia entre cada dos numero empezando en 0) y la evaluación de individuos es relativamente sencilla (se verifica si la distancia entre cada dos números en la secuencia es única con respecto a las distancia entre entre otros dos números en la secuencia). El valor de la solución es el último número de la serie y se trata de minimizar este valor. Por ejemplo, para n=4, tenemos por ejemplo las siguientes dos soluciones:
La de abajo es óptima. Esas dos soluciones se pueden representar también como la distancia entre cada dos números de la secuencia (se sume el 0 como primer número). Serían: 1 2 4 1 3 2
¿Cómo lo véis? Es una propuesta concreta, tenemos además con quién comparar (hay propuestas de compuatción voluntaria pero creo que la nuestra, al usar EAs, es totalmente distinta).