CHAC, the Military Ants in the press around the world

Last Friday, 6th of November some news related to the mini-simulator which we have developed for the implementation and test of the algorithms based in the ants’ behaviour to search for the best path (attending to the speed and safety) in a military battlefield, were published. :)

This new appeared firstly (in May some days after my PhD Tesis lecture) at the Press  site of the University of Granada.

But last Friday, the new was published by some other webs, as AlphaGalileo, EurekAlert and RedOrbit. Then it appeared in many other scientific news webs (AECC, SoftPedia, ScienceDaily, Physorg, LabSpaces, TMCnet, First Science or Science Centric).

In addition it has appeared in some general news online sites (mainly in Asia): Sindh Today, New Kerala, TopNews.in, South Asia News, CBNews and Breaking News among others.

Finally, the new has been also introduced in some blogs, forums and social nets (Blog.Taragana, BizFace, Defense Forum India, Twitter).

Thanks a lot for the interest in our work and let us know if you need some documentation or other stuff concerning to it. ;)

The application can be downloaded from our group’s project site in forja.rediris (is the project hCHAC), and it has been developed under a GPL license, so it is free to download, use and even modify, but following this license restrictions. :)

Best regards.

[IDC'09] Studying the Cache Size in a gossip-based evolutionary algorithm

Last week we were presenting the work Studying the Cache Size in a Gossip-Based Evolutionary Algorithm [BibTex] in the 3rd International Symposium on Intelligent Distributed Computing hold in Ayia Napa (Cyprus).

Gossiping is a self-organized and decentralized approach to distribute algorithms through Peer-to-Peer (P2P) networks.
Based on such an approach, the Evolvable Agent model is a P2P Evolutionary Algorithm (EA) whose
population structure is defined by the gossiping protocol newscast, a protocol that behaves asymptotically as a small-world graph. This paper explores the impact of different cache sizes on the algorithm performance given that cache size is the only tunable parameter in newscast. To this aim, the problem generator wP-PEAKS and the multimodal deceptive problem MMDP have been used as benchmarks.
Results show that the quality of the solutions and the run-time of the algorithm are not altered when changing the settings of the cache size. This fact points out that newscast is a robust gossiping protocol for tackling distributed evolutionary computation.

Descargar el Simulador de estrategias militares basado en el comportamiento de las hormigas

JJ ha subido hoy los fuentes y el ejecutable del simulador de estrategias militares basado en el comportamiento de las hormigas, como se ha denominado en la prensa (ver post Hormiguitas Militares en la prensa).

O mini-simulador SIMAUTAVA (mSS-HEXA, que lo llamamos nosotros). :-)

Éste se puede descargar en el sitio de geneura en la Forja de Rediris:

https://forja.rediris.es/projects/geneura/

(mini-simulador hCHAC)

El software ha sido implementado bajo una licencia GPL. ;)

Se ha incluido , aparte del ejecutable (para Windows) un manual de funcionamiento y varios mapas de ejemplo.

Además se han subido los fuentes del mismo, escritos en Borland Delphi 7.

Esperamos que sea útil para la gente interesada en el mismo.

Saludos a todos y gracias por el interés puesto en esta aplicación y los algoritmos.

Hormiguitas Militares en la prensa

Hoy (o más bien ayer) fue publicada una noticia sobre el simulador y los algoritmos implementados para el desarrollo de la Tesis Doctoral que leí hace dos semanas (ver post El fin del trabajo… la tesis!!!).

La noticia se incluyó inicialmente entre las notas de prensa de la UGR y posteriormente se hicieron eco de ella en Europa Press. A partir de ese momento, se incluyó un artículo o post al respecto en diversas publicaciones electrónicas.

Entre ellas se incluyen varios periódicos:

El Mundo, ABC, Ideal de Granada, La Opinión de Granada, 20 Minutos, El Periódico de Cataluña, e incluso El Economista. ;-)

Algunos portales:

Yahoo, Ya.com, Terra

Y también algunos blogs:

cienciaaldia, geeko, elsenderodelguerrero, thebluebulb

En general lo comentado en los artículos es bastante correcto desde el punto de vista ‘científico’, si bien en aquellos en los que se incluyen comentarios de lectores, se puede ver que la información no es todo lo completa o ‘estricta’ que quizá debiera ser.

Por ello quisiera hacer un par de apuntes sobre la noticia a fin de aclarar un poco más su contenido, al menos para aquellos que lean este post. ;)

- La primera anotación creo que es completamente necesaria y es que los algoritmos de optimización basada en colonias de hormigas fueron presentados en el año 1991 por Dorigo et al., si bien incluso sus estudios estaban basados por otros realizados varios años antes por Pierre-Paul Grassé y confirmados por Deneubourg sobre el comportamiento de las hormigas naturales.

- En segundo lugar y entrando en cuestiones ‘etico/políticas’, el software ha sido diseñado en colaboración con personal del ejército, pero no va a ser utilizado al menos a corto plazo. En cualquier caso su utilidad hasta el momento sería completamente ‘pacífica’, dado que la unidad solo se mueve, no dispara.

Del mismo modo su uso para aplicaciones ‘civiles’, como planificación de rutas de transporte, sería posible realizando una adaptación del simulador al nuevo problema.

- Es libre por ser un proyecto desarrollado como investigación dentro de la UGR, aunque bajo demanda en principio.

- Del mismo modo, el objetivo de la aplicación diseñada sería la automatización de avatares dentro de un simulador más complejo que el utilizado, los cuales deberían buscar y elegir el mejor camino de forma autónoma.

Si bien, también podría ser útil para que el capitán de una compañía planificase por adelantado la ruta a seguir en un campo de batalla conocido.

Me alegro de que esto haya trascendido, pero me gustaría que quedase todo lo más claro posible. ;)

Saludos.

El fin del trabajo… la tesis!!!

Bueno, bueno, este post es meramente informativo y me complace sobremanera escribirlo puesto que lo hago para comunicar a los lectores

¡¡¡ que ya he leido mi tesis!!! :D :D

La lectura fue el 5 de Mayo y he tardado tanto en escribir esto porque me prometí no tocar un teclado en dos semanas. ;) XD

El título de la misma es:

Resolución del Problema Militar de Búsqueda de Camino Óptimo Multiobjetivo mediante el uso de algoritmos de optimización Basados en Colonias de Hormigas.
(un poco largo si, pero como todos :D)

La presentación la podeis ver aquí mismo:

Y el PDF está disponible -> aquí <-

Espero que os interese. ;)

Saludos.

————————————————————————————–

English version:

I finished my PhD Thesis  last 5th of May… :D

(I have written this post today because I didn’t want to use a keyboard in two weeks XD).

It is titled Solving the Multiobjetive Military Pathfinding Problem Using Ant Colony Optimization Algorithms.

The presentation and the pdf of the Thesis are available (in spanish) at:

http://geneura.ugr.es/~amorag/tesis/

I wish it will be interesting for you. ;)

Bye bye. :D

P2P technology for computing tasks does not always mean P2P computing

What would you think of a Bugatti Veyron limited to a maximum speed of 20 Km/h?? mmmm… YES!! Give me back the money!!

… well, that’s roughly my feeling when I read a paper on P2P computing restricting the scalability analysis to some few nodes. Of course, the analogy is not completely fair since performing a real massively distributed (and decentralized) experiment presents some challenges that, in most of the cases so far, remain out of the scope of the state of the art research. That happens, for instance, to P2P environments applied to optimization, and more precisely to Evolutionary Computation.

Usually, you can find two different approches for P2P optimization testing, either using simulations or using a “GRID-like style” in real environments, each case presents its own advantanges and drawbacks:

• Using simulations implies a certain number of assumptions about the real environment, hence, assumption have to be correct in some sense (e.g. representing a pesimistic scenario or making clear what’s the scope of the work) and results have to be understood under such an umbrella.

• Using a real P2P environment ( we performed a study like that using a 8×2 cluster). The adventage here is that the design has to face real restrictions, as communication or evaluation times, message passing restrictions or fault tolerance. Nevertheless, there are extreme difficulties to set a real and proper environment to test a model.

When you face a real environment, you find that:

• Large number of resources are hard to grab

• Scalability is hard to study. In the case of having few nodes, no real P2P computing is going on since no conclusions about large scalability can be drawn. On the other hand, if there are some good dozens of peers, other questions such as fault tolerance arise.

In the last friday paper seminar our team was discussing the following paper that uses the “grid-like style” for testing:

• P-CAGE environment for Evolutionary Computation in P2P systems

in which the authors propose a hybrid model combining islands with cellular EAs. Every peer holds an island and every island a cellular EA. As previously commented for grid-like testing, the scalability analysis is quite poor (up to 10 peers), additionally, the algorithm yields the best performance in the five peers’ scenario, pointing to a really poor scalability of the model. Nevertheless, the fact is that P-CAGE outperforms canonical EAs making of it a valid solution based on P2P technology, just that, such a solution is not really scalable and therefore, can not be really understood as P2P computing.

To conclude, I do think that simulations can benefit the understanding of complex interactions in P2P EAs at this stage of research, preventing situations as the one shown above, afterwards, there will be time to validate the models in real environments, letting that theory meets practice.

So you want a summer internship in Granada, Spain

The GeNeura team is composed by an international team of doctors and graduate students, mainly focused in bioinspired algoritms such as ant colony optimization algorithms, also in multiobjective versions, distributed and sequential EAs applied to neural net training, along with other applications.
So, if you have knowledge of

• Evolutionary algorithms, or
• neural nets, or
• P2P or parallel or distributed computing and
• Java, Perl, Ruby, Javascript or Python, and
• your own source of funding, such as Erasmus, a Foreign Ministry scholarship, or anything like that

please send your resumé to JJ Merelo, specifying what you request from us, and the support you will have, and we’ll be back to you ASAP.

Pherographia in SIGEvolution

Our partner Carlos Fernandes has published an article on the latest number of SIG evolution, called A Camera Obscura for Ants. This article describes from the scientific point of view his Pherography method, that uses ant colony algorithms for creating curious and nice effects on photography. A bit like our Kohonants, but without the Kohonen part.

E. Coli and Open-Source Software

(…) It’s a bizarre coincidence that just as scientists were discovering the evolutionary importance of viruses, computer engineers were creating a good metaphor for their effect. In the late 1990s, group of American engineers became frustrated by the slow pace of software development. Corporations would develop new programs to make it impossible for anyone on the outside to look at the code. Improvements could come only from within – and they came slowly, if at all. In 1998, these breakaway engineers issued a manifesto for a different way of developing programs, which they called open-source software. They began to write programs with fully acessible code. Other programmers could tinker with the program, or merge parts of different programs to create new ones. The open-source software movement predicted that this uncontrolled code swapping would make better programs faster. Studies have also shown that software can be debugged faster if it is opwn source than if it is private. Open-source software has now gone from manifesto to reality. Even big corporations such as Microsoft are beginning to open some of their programs to the world’s inspection.

In 2005, Anne O. Summers, a microbiologist at the University of Georgia, and her colleagues coined a new term for evolution driven by horizontal gene transfer: open-source evolution. Vertical gene transfer and natural selection act like an in-house team of software developers, hiding the details of their innovations from the community. Horizontal gene transfer allows E. Coli. to grab chunks opf software and test them in its own operating system. In some cases, the combination is a disaster. Its software crashes, and it dies. But in other cases, the fin-tuning of natural selection allows the combination to work well. The improved patch may later end up in the genome of other organism, where it can be improved even more. If E. Coli is any guide, the open-source movement has a bright future.

(…)

Carl Zimmer, in Microcosm – E. Coli and the New Science of Life

Estimation of Distribution Algorithms

In the week before the discussion on microarrays, the seminar’s paper was From Recombination of Genes to the Estimation of Parameters I, Binary Parameters, by H. Mulhenbein and G. Paaβ. The seminar aimed at discussing the simple Univariate Marginal Distribution Algorithm (UMDA), its origins, advantages and disadvantages when compared to standard Genetic Algorithms, and the algorithms that were born out of this simple evolutionary method. There is a lot of work done on UMDA and Estimation of Distribution Algorithms (EDAs), so there is not much latitude for speculation.

One of the most interesting features of UMDA and following EDAs is their simplicity and the way research has been done by carefully analyzing and improving existing EDAs, from the “old” PBIL to the sophisticated and rather effective BOA and hBOA algorithms. Theoretical analysis of Evolutionary Computation, namely that concerned with scalability and convergence issues, experienced a consisted improvement since the burst on EDAs research. Moreover, it is when scalability is carefully analyzed and/or measured that some EDAs reveal all its full power when compared to traditional Genetic Algorithms. Some EDAs, by “learning” a problems’ structure (think of BOA, for instance) are able to deal with very large instances of that problem in practicable computational time. In addition, recent investigations have concluded that these kind of algorithms and Ant Colony Optimization share a sufficient number of traits to be seen as methods belonging to the same class of heuristics, a fact that may spoil all the “magic” behind Ant Algorithms (and it will sure discredit much of the jargon involved in some discussions on Ant Algorithms, self-organization, etc). On the other hand, this “unification” will shed some light on both algorithms’ characteristics.

(In this line of investigation, our group has recently published the paper UMDAs for Dynamic Optimization Problems, but further research is on way, on both static and dynamic environments.)