Using the Incidence Matrix in an Evolutionary Algorithm for Computing Minimal Siphons in Petri Net Models

During last October we presented a paper at the 18th International Conference on System Theory, Control and Computing (ICSTCC 2014). It was at Sinaia, Romania and the paper was a further development of the work presented at PNSE (see Evolutionary computing and Petri Nets). We realized that we could use the incidence matrix of the Petri Net in order to look for siphons.

Title: Using the Incidence Matrix in an Evolutionary Algorithm for Computing Minimal Siphons in Petri Net Models.

Authors: F. Tricas, JM Colom, JJ Merelo

Abstract:

Petri nets are graph based tools to model and study concurrent systems and their properties; one of them is liveness, which is related to the possibility of every part of the system to be activated eventually. Siphons are sets of places that are related to liveness properties. When we need to deal with realistic problems its computation is hard or even impossible and this is why in this paper we are approaching it using evolutionary computation, a meta-heuristic that has proved it can successfully find solutions when the search space is big. In a previous work a formulation of the siphon property based on linear constraints and a genetic algorithm was proposed for general Petri Nets. Here we propose to adapt an algebraic method based on the selection of rows of the matrix that cancel in an adequate way input and output transitions so the resulting selection is a siphon. We will also present an evaluation for a family of resource allocation systems (RAS). The proposed solution is based on a genetic algorithm (GA); we can see how siphons can be computed using this genetic algorithm, with experiments showing that in some cases they are able to find a few solutions in less time than previous deterministic algorithms.

The paper can be downloaded at the IEEE Xplore site (link above) and the accepted version is available at [pdf] Using the Incidence Matrix in an Evolutionary Algorithm for Computing Minimal Siphons in Petri Net Models.

The slides used at the conference are:

Our plan is to continue exploring theses kind of methods to see if we can improve the results obtained.

Advertisements
Tagged with: , , , , , , ,
Posted in conferences, Congresos, Presentaciones

Evolutionary computing and Petri Nets

Last month we presented at PNSE 2014 (International Workshop on Petri Nets and Software Engineering, Tunis, Tunisia, June 23-24, 2014) a paper trying to use evolutionary algorithms to compute some structural components of Petri net models that can be related to liveness problems.

PNSE is a satellite event of Petri Nets 2014 35th International Conference on Application and Theory of Petri Nets and Concurrency and ACSD 2014 14th International Conference on Application of Concurrency to System Design.

Title: Computing Minimal Siphons in Petri Net Models of Resource Allocation Systems: An Evolutionary Approach
Authors: F. Tricas, JM Colom, JJ Merelo

Abstract:

Petri Nets are graph based tools to model and study concurrent systems and their properties; one of them is liveness, which is related to the possibility of every part of the system to be activated eventually. Siphons are sets of places that have been related to liveness properties. When we need to deal with realistic problems its computation is hard or even impossible and this is why in this paper we are approaching it using evolutionary computation, a meta-heuristic that has proved it can successfully find solutions when the search space is big. In this work a formulation of the siphon property using linear constraints is presented for general Petri Nets. We will also present an evaluation for a family of resource allocation systems (RAS). The proposed solution is based on a genetic algorithm (GA); we will show how siphons can be computed using it, with experiments showing that in some cases they are able to find a few solutions in less time than previous deterministic algorithms.

The paper can be downloaded at [PDF] Computing Minimal Siphons in Petri Net Models of Resource Allocation Systems: An Evolutionary Approach.

The presentation used at the conference was:

We feel that this can be the starting point for further work so stay tunned for more research on Petri nets and evolutionary algorithms.

Tagged with: , , , , , , ,
Posted in conferences, Congresos

Hackathon in Videogames at EVO* 2014

We are organizing a hackathon with our favorite topics: games, evolutionary algorithms, and open source. Join us next April 22nd!

The EvoGAMES blog

Imagen

Hi to all,

Finally, the EVOHackathon will be held in the Oficina de Software Libre on Tuesday 22 April (one day before EVOGames conference).

There are 5 projects confirmed right now,namely:

  • Creating autonomous agents for Super Mario Bros. game
  • Creating an AI engine for the game Wetland (Greyman Studios)
  • Creating bots for 1 vs 1 combats in the RTS Planet Wars
  • Procedural generation of stages for a new game (Greyman Studios)
  • Progamer: Code visualization tool based in Super Mario Bros. levels

As you can see, two of them are proposed and will be directed by a videogames company.

The inscription form is here.

We invite you to join us. It is free! 😀

View original post

Posted in Uncategorized

Amor por la Ciencia o “Prostitución Académica”?

En un número especial de Nature publicado en 2010 se afirmaba que la investigación se está convirtiendo en una especie de” prostitución académica ” en la que el trabajo se hace para complacer a los editores y árbitros en lugar de para profundizar en el conocimiento. Comentando esta frase, junto con otros temas relacionados, con personal de la ERC durante unas evaluaciones, me sugirieron hablar del tema en uno de sus seminarios. Este parecía un lugar más que adecuado para ello. Provocar debate al respecto en un lugar donde se toman tal número de decisiones sobre inversiones ecónomicas en ciencia me pareció una ocasión que no podía dejar pasar, por lo que unos meses después me encontré allí mismo hablando de “Love for science or academic prostitution?”. El titulo fue resultado de aquella frase de Nature, unido al comentario de este colega de la ERC que, al oirla, exclamó algo así como “oh, verdadero amor por la ciencia, eso lo que debemos tener, en contraposición a prostitución!”.

Este tema parecía encajar bastante bien en el Document Freedom Day, puesto que la ciencia vive una especie de secuestro en que, entre editoriales que cobran varias veces al propio autor por publicar (que no es lo mismo que hacer público, que cosas!) sus resultados, y científicos compitiendo por los recursos económicos, es hurtada a su verdadero destinatario, el ciudadano que espera beneficiarse de ella, ya sea mediante conocimiento aplicado, o conociendo los resultados de la investigación básica (en qué Universo vivimos, de qué estamos hechos…). Por ello estuve hablando de nuevo de amor y prostitución en ciencia durante la sesión organizada por la Oficina de Software Libre de la Universidad de Granada.

Como allí conté, mi propósito con esta charla fue provocar algo de pensamiento crítico adicional entre los comités que seleccionan a los evaluadores, y entre los propios evaluadores, que a su vez piden a los candidatos pensamiento crítico como signo de excelencia científica. El mensaje de alerta a los organismos financiadores es que pueden caer en la trampa del propio sistema que han establecido. Al perpetuar esta “prostitución” corren el riesgo de no financiar la mejor investigación, sino la mejor vendida. En la época actual de crisis económica, en que los investigadores en busca de fondos se ven a menudo obligados a entrar en un juego competitivo de complacer a los evaluadores, parece un buen momento para parar y realizar una reflexión profunda sobre el sistema científico.
La poca fiabilidad de muchas de las métricas de la investigación comunmente aceptadas, el círculo vicioso en que hemos entrado de publicar en revistas de impacto para que nuestro CV pese más, haciendo que estas revistas siguen elevando su impacto (y beneficios…) y aumentando la discriminación hacia la ciencia que se hace en países en desarrollo, pero también la llegada de métricas alternativas que intentan solventar el hecho de que las citas representan menos del 1% del uso que se hace un artículo, y de nuevos métodos de publicación (no sólo de la retórica de los resultados, sino de los datos y métodos) son algunos de los temas tratados en esta charla, donde se pueden encontrar las referencias correspondientes. Dar un mayor peso a la metodología (es reproducible?) frente a premiar los resultados debería ser garantía de una mejor ciencia, es decir de …Ciencia.

 

 

Tagged with: , , , , , ,
Posted in Uncategorized

Papers ejecutables en el DFD2014

El 26 de Marzo de 2014 se celebró el Document Freedom Day en todo el mundo, y la Oficina de Software Libre de la Universidad de Granada organizó una sesión de conferencias en las que tuve la oportunidad de participar como ponente con una exposición sobre Ciencia Abierta y Publicaciones Ejecutables. En esta charla pude presentar algunos temas de discusión sobre ciencia abierta que han surgido a lo largo de mi participación en los proyectos Canube y EU FP7 Wf4Ever, ambos con una clara vocación de difundir la ciencia abierta y reproducibilidad en la ciencia. Y es que el acceso libre a los datos no implica ciencia reproducible, y en realidad la ciencia no necesita este adjetivo, pero en los tiempos que corren la crisis de la reproducibilidad en ciencia es un hecho. Esto conlleva muchas veces un desprestigio de la ciencia, donde gran parte de las publicaciones que se realizan no admiten adjetivos como “repetible”, “reproducible” o “re-utilizable”. Esto es aún más sangrante cuando se trata de publicaciones científicas en las que todos y cada uno de los recursos que intervienen forman parte del mundo digital, y el mayor obstáculo para conseguir el status de reproducible debería ser en teoría puramente técnico.

La mayor parte de la ciencia que se realiza ahora tiene una fuerte componente colaborativa, y además es altamente especializada. Promover el intercambio, el descubrimiento, la visibilidad y el acceso a los recursos digitales que intervienen en la producción científica debería mitigar la reinvención, acortando el tiempo de aprendizaje y desarrollo, algo necesario cuando se tienen en cuenta las costosas inversiones tecnológicas en infraestructuras científicas. Tuve la ocasión de poder presentar algunas de las iniciativas lideradas por grupos de científicos y editores, que complementan las publicaciones tradicionales en papel con otras publicadas en formatos digitales más interactivos. Entre los principales objetivos de estos esfuerzos están la mejora de la reproducibilidad y la claridad de los resultados científicos, que van más allá del archivo PDF estático, fomentando la re-utilización y una explotación más eficiente de los recursos digitales disponibles.

Posted in Uncategorized

Biocomputación y herramientas online

Los campos de Ciencias y Computación han evolucionado conjuntamente en los últimos 30 años, hasta el punto, que ha llegado a surgir la disciplina de la Biocomputación. En ella se usa la capacidad de procesamiento de los ordenadores para diseñar algoritmos que permitan a los científicos modelar, comprender y, en última instancia, simular, procesos biológicos. La Biocomputación abarca numerosas disciplinas, desde la Biología Molecular hasta la Astrofísica, pasando por Microbiología, Química o Física de Sistemas Complejos. Gracias al uso de estos algortitmos los científicos podemos modelar o predecir el comportamiento de un determinado experimento antes de entrar al laboratorio, ahorrando así tiempo y número de intentos para conseguir las condiciones óptimas necesarias para cumplir el objetivo marcado. En Biología Molecular, el uso de los algoritmos permite la comparación de secuencias de ADN o estructura de proteínas, la consulta de éstas en bases de datos para localizar un determinado gen, enzima, etc., e incluso modificar o alterar secuencias y predecir el resultado antes de hacerlo en el laboratorio.

Los algoritmos utilizados se basan en tablas de dispersión Hash, donde a cada símbolo (letra) de una secuencia dada se le asignan números que corresponden con su posición en la cadena. Con estas tablas se obtienen matrices que nos van a permitir alinear y comparar dos o varias secuencias. Los métodos de comparación más usados en la actualidad están basados en el algoritmo BLAST.

El pasado 9 de Enero de 2014, integrantes de CANUBE nos reunimos en la Facultad de Ciencias en un seminario sobre los distintos aspectos de la Biocomputación y la existencia de diversas herramientas online basadas en ella que hacen nuestro trabajo un poco más sencillo. Os animamos a ver la presentación y acceder a las distintas plataformas cuyos enlaces se facilitan en la misma.

Posted in Uncategorized

AstroTaverna mira al cielo

Los nuevos desarrollos para el plugin AstroTaverna por parte de Fidesol en la Tarea 3.3 de Astrofísica comienza a dar resultados. Bajo la supervisión del grupo AMIGA del Instituto de Astrofísica de Andalucía – CSIC,  la integración de servicios web TAP (Tabular Access Protocol) en el diseño de workflows y un acceso directo al AstroTaverna Starter Pack avanza a buen ritmo ! Como prueba de ello aquí os dejamos dos videos que muestran el funcionamiento de estas dos tareas.

AstroTaverna – StarterPack Access

AstroTaverna – VO TAP Services

Podéis seguir el desarrollo de AstroTaverna en el GitHub de Canube.

 

Posted in Uncategorized