Friday Paper Seminar: BEA (Bacterial Evolutionary Algorithm)

Today in our Friday Thursday Paper Seminar we’ve been discussing the paper “Fuzzy System Parameters Discovery by Bacterial Evolutionary Algorithm” of Norberto Eiji Nawa and Takeshi Furuhashi.

It’s a very interesting paper because introduces a bioinspired algorithm based in bacteria (as the title says, obviously), and its application to fuzzy system. The main improvement from the previous algorithm of the authors the Pseudo-Bacterial Evolutionary Algorithm is the fact of using the transduction, the way that the bacterias interchanges information between themselves. But let’s begin from the beginning.

Every individual of the population is a bacteria whose chromosome is the parameters of a fuzzy system. This chromosome has low epistasis, that is, the chromosoma have weak interrelationships between parts so it is possible to perform optimization in parts. So in each generation every bacteria have a local improvement called bacterial mutation, cloning the bacteria and improving every part but taking care of the global fitness, so the best clone is chosen.

The second operator presented is the Gene Transfer Operation. Instead crossover, the best bacterias sends information to the worst bacterias adding or overwriting parts of the chromosome.

After explain the algorithm the authors performs several experiments to compare other algorithms and this one. I’m not expert in Fuzzy Systems, so probably I’ll be wrong, but I can see that the while the BEA has lower error rates evaluating train set, it also has higher error rates in test set, and the fuzzy system obtained has more (and not used) fuzzy rules. I think this is not a good improvement, but the idea of bacterial mutation and gene transfer is quite interesting in other problems, as we can see in more papers that refers this one.

So, that’s all! Until next week!

Pablo (aka Fergu)

See ya in PPSN

Today is the last, final and defintive day for submitting papers to the PPSN (Parallel Problem Solving from Nature) conference, and I think we’ve beaten some record here, since our research group (the extended GeNeura, with visiting researchers, other partners in research groups, and so no) is submitting 10 papers. Taking into account the usual PPSN acceptance rate, we’ll probably only manage to get 3 accepted, so anything more than that will really be a success.
There are several evolutionary computation conferences out there, some of them good, some not as good, but for us PPSN is the absolute best. This would be the seudo-20th anniversary (actually, 10th edition, 18th anniversary), and for us it would be our personal 12th anniversary, since the first time we had something admitted in that conference was in 1996, and we haven’t failed a single one (even organized one of them). So even if this year we’re attending all EC conferences there are (CEC, GECCO -yes, GECCO-, Evostar), we really can’t miss this one.
So if you are submitting to PPSN (more than 220, for the time being), good luck, and see you there!

Introducing KohonAnts, a new stigmergic clustering and classification algorithm

We have submitted, and at the same time uploaded to ArXiV, a paper on this new algorithm the masterminds of GeNeura + Carlos Fernandes and Vitorino Ramos (who are practically now full-privileges GeNeura members). You can download it from ArXiV; the title is KohonAnts: A Self-Organizing Ant Algorithm for Clustering and Pattern Classification:

In this paper we introduce a new ant-based method that takes advantage of the cooperative self-organization of Ant Colony Systems to create a naturally inspired clustering and pattern recognition method. The approach considers each data item as an ant, which moves inside a grid changing the cells it goes through, in a fashion similar to Kohonen’s Self-Organizing Maps. The resulting algorithm is conceptually more simple, takes less free parameters than other ant-based clustering algorithms, and, after some parameter tuning, yields very good results on some benchmark problems.

We’ll be very soon doing the rounds with this algorithm with the usual conferences. It is new, it works surprisingly well, and, as usual, source code is available from your friendly Forja subversion repository (not updated, though).

New paper on evolution of XSLT stylesheets uploaded to ArXiV

A new paper, Improved evolutionary generation of XSLT stylesheets, has been uploaded to ArXiV. It’s been accepted, as poster, to the GECCO 2008 conference, so we conveniently publish the full paper here as a reference. Here’s the abstract:

This paper introduces a procedure based on genetic programming to evolve XSLT programs (usually called stylesheets or logicsheets). XSLT is a general purpose, document-oriented functional language, generally used to transform XML documents (or, in general, solve any problem that can be coded as an XML document). The proposed solution uses a tree representation for the stylesheets as well as diverse specific operators in order to obtain, in the studied cases and a reasonable time, a XSLT stylesheet that performs the transformation. Several types of representation have been compared, resulting in different performance and degree of success.

As the paper says, full source is available from our SubVersion repository

SOTEA: Population structure, coevolution and diversity maintenance

Last Friday’s talk was about the work of Whitacre and coathors presented in:

• The Self-Organization of Interaction Networks for Nature-Inspired Optimization (Quite related with our research line on population structures (i.e. [1,2]), keeping some similarities with this paper)

The authors propose an EA (called SOTEA) for the sake of diversity maintenance. To this aim, they focus on a self-organized population structure with the shape of a complex network. The network co-evolves with the EA by following two rules (from which emerge a power law population structure):

1. Reproduction rule:

When a new offspring is created, SOTEA add a new node, this node is linked to its parent (asexual reproduction). The parent’s connections are inherited by the offspring with certain probability Padd. Besides, all inherited connections are lost by the parent with probability Premove.

2. Competition rule

A random selected individual competes with its less fit neighbour. From such a competition, the loser results killed and the winner inherits all its connections.

Within the paper, the results are compared versus a Cellular GA and a Panmictic GA. They show that SOTEA keeps better the population diversity than its competitors and converges reasonably to a solution.

Quite a nice work, although I missed a larger and more stressing test suit case (Authors just use the NK landscape test function).

Pasándonos a git

Una parte posiblemente poco considerada de la investigación científica consiste en compartir código y fuentes de trabajos científicos. Hay miles de formas de hacerlo mal, y varias de hacerlo bien; una de estas últimas es usar repositorios. Nosotros lo venimos usando desde hace cierto tiempo, sobre todo con código, y hemos llegado a estar bastante hartos de las limitaciones de CVS. Subversion está algo mejor, pero desde que ha surgido Git, estamos tratando de pasar todos los repositorios, y de crear los nuevos, usándolos. Así que el viernes pasado dedicamos el seminario a una mini-introducción a git.

The NFL Theorems in a nutshell

Last Friday I tried to explain the other members the famous Wolpert & Macready paper “No Free Lunch Theorems for Optimization”. I said “I tried” because I was beaten by a lot of bravely formulas with their invincible Sigma Squadron. I get obfuscated with such all mathematical things and I decided to face up to the problem with sense: searching a summary in the Internet. It looks like that anybody has read the article, because I haven’t found any useful (and understable for my person) information. But I’ll try to explain what I’ve learned:

The NFL Theorems says that for each pair of algorithms, A and B, without human behaviour, the half of problems in the world, the universe and all, will be more efficient in the algorithm A than the B.

Well, not bad.

But, imagine you have programmed the “Super Wonderful Algorithm To Do All With The Powers of the Cristal Skull”, the best algorithm ever made, and you are proud of it, working since you started your MsC, using it for your PhD and now you are an ancient professor you are finally writing the greatest paper of Universe. So you take all problems of the world, the universe and all, and compare with another algorithm. For example, the random search.

Damm! Your algorithm is worse in the half of problems.

So this paper is a pessimist way to those than are searching that “super wonderful algorithm to do all”.

The most interesting part is the philosophical sense. I’ve asked in the last GeNeura weekly meeting if we are part of a super-evolutionary algorithm and we can adapt the algorithms A or B to increase the performance over the other then the super-evolutionary algorithm that have created us breaks with the theorems. But JJ said that the universe is not computable, even at microatomic scale. So we all talked about metaphysics the rest of the meeting.

After that I suggested the Craig Evan’s book “Permutation City”. It’s about human virtual copies, meta-universes and a lot of cyberpunk cliches. And it’s quite cool.

That’s all, I guess. All comments about NFL theorems and/or computable universes are welcome!

New paper on multiobjective ant colony optimization available online

This is the paper we presented at the ECAL 2007 conference. Its title is Comparing ACO Algorithms for Solving the Bi-criteria Military Path-Finding Problem, and it deals with one of our lines of work, using ant-colony algorithms to show the way to a (peaceful and unarmed) military unit.

Be XMPP

Long time before coming back here. This Friday has been devoted to talking about XMPP and its research possibilities. It’s already a distributed infrastructure, so it wouldn’t be too difficult to turn it into a distributed computing infrastructure, which we are about to do.
We also got kind of lucky in our latest paper submissions, and got 5 papers accepted for CEC (within WCCI), plus two papers in EvoStar. We’ll be in Napoli to present them come late March.

[ECAL’07] CHAC Presentation

Hi!

These are the slides of the presentation of CHAC algorithm in ECAL’07 conference.

Enjoy it.