Despite the intuition that the same population size is not needed throughout the run of an Evolutionary Algorithm (EA), most EAs use a fixed population size.
This paper presents an empirical study on the possible benefits of a Simple Variable Population Sizing (SVPS) scheme on the performance of Genetic Algorithms (GAs). It consists in decreasing the population for a GA run following a predetermined schedule, configured by a speed and a severity parameter. The method uses as initial population size an estimation of the minimum size needed to supply enough building blocks, using a fixed-size selectorecombinative GA converging within some confidence interval toward good solutions for a particular problem. Following this methodology, a scalability analysis is conducted on deceptive, quasi-deceptive, and non-deceptive trap functions in order to assess whether SVPS-GA improves performances compared to a fixed-size GA under different problem instances and difficulty levels. Results show several combinations of speed-severity where SVPS-GA preserves the solution quality while improving performances, by reducing the number of evaluations needed for success.
Last week I received the paper aceptance notification for the DCAI conference in Salamanca. This time we are going to present a distributed algorithm framework for mobile devices using Bluetooth. Ok, today I am quite lazy (today, and all the days, actually), so I think the best idea is to copy the abstract.
Abstract. This work presents a Java framework which allows to implement easily connectivity applications via Bluetooth. Nowadays it is difficult to program Bluetooth devices, so it is necessary to use a high-level Application Programming Interface (API) to make easy the creation of applications in Java ME and Java SE platforms, the most extended ones. As a solution we show the development of a distributed computing environment using a layered, client-server, and event-based with asynchronous communication architecture. In addition we solve two well-known evolutionary computation problems (the Traveler Salesman Problem and the Wave Function Problem), as an example of use.
The most interesting thing is that we have used real mobiles in order to execute the experiments, with all associated problems. It is difficult to find a compatible mobile phone with a Bluetooth stack that works properly. Even is not easy communicate two phones of the same fabricant but different model! But finally we managed to start the experiment, as you can see in the next photo.
Two Nokias executing our distributed algorithm. Photo by DraXus.
In this paper we analyse the robustness of a Peer-to-Peer (P2P) Evolutionary Algorithm (EA) subject to the following dynamics: peers leave the system independently from each other causing a collective effect known as churn. The algorithm has been designed to tackle large instances of computationally expensive problems and, in this paper, we will assess its behavior under churn. To that end, we have performed a scalability analysis in five different scenarios using the Massively Multimodal Deceptive Problem as a
benchmark. In all cases, the P2P EA reaches the success criterion without a penalty on the response time. The key to the algorithm robustness is to ensure enough peers at the beginning of the experiment. Some of them leave but those that remain are enough to guarantee a reliable convergence.
I returned from Brussels a couple of days ago, where I went to present KANTS: Artificial Ant System for Classification (the model was already described here) at the 6th International Conference on Ant Colony Optimization and Swarm Intelligence. ANTS 2008 is similar to PPSN, with most of the papers being presented at poster sessions (only a few are chosen for oral presentation). This procedure works well when the poster sessions are not just a minor event of the congress, thrown to a distant room in the hotel/university where nobody even bothers to go, or scheduled to the end of a long day. ANTS sessions were well organized and every poster had an assigned space. My presentation was scheduled to the last day of the congress, when most of people had already packed for their trip back home, but nonetheless the session went well, with lots of people wandering around the room, clearly interested in the works. KANTS got the attention of some audience, and I think they were quite impressed by the simplicity (and efficiency) of the idea. The inevitable question arouse (are you planning to test KANTS on a real-world problem?) and this time we can answer yes, we are not only planning to do it, but we are already working on it (later we will report on those experiments). In the same section, another swarm-clustering was presented. I saw the poster, and the results on clustering appear to be quite good (but the system does not perform classification). I haven’t read the paper (as a matter of fact, it is published as an extended abstract), but I was able to realize that the algorithm is little bit complex, simulating the behavior of three different species: ants, birds and spiders.
A week before I was in Barcelona, at the 8th International Conference on Hybrid Intelligent Systems (HIS 2008), presenting the paper Tracking Extrema in Dynamic Fitness Functions with Dissortative Mating Genetic Algorithms. It is quite a different work, and more related to my thesis’ subject, bio-inspired computation on dynamic environments. It describes the experiments performed with an adaptive dissortative mating GA (ADMGA) on Dynamic Optimization Problems. Dissortative mating appears frequently in nature and refers to the occurrence of mating between dissimilar individuals more often than expected by chance. It maintains genetic diversity at a higher level, thus increasing the exploration stage of the algorithm. Dynamic fitness functions are more sensible to genetic diversity than static ones, and so dissortative mating is a good candidate to deal with that kind of problems. The paper describes mainly the experiments performed with trap functions and show that ADMGA may improve GAs on some dynamic optimization scenarios. Robustness is also addressed and results show that ADMGA maintains a more stable performance over the wide range of dynamic scenarios. The congress HIS is mainly dedicated to hybrid models and real-world applications, so ADMGA was somewhat “lost” among other works. But good news came after the congress, and this line of research will probably make its way through other media.
P.S. In Brussels, avoid Hotel Continental, near Midi Station, unless you need inspiration for another insects’ heuristics.
Last friday I returned from the First Ferguson World Tour Of Science. I was traveling around Europe in order to present some things about my research.
First we arrived at Dortmund, Germany, where the Parallel Problem Solving from Nature (PPSN 2008) was celebrated. There I presented my paper “Evolving XSLT Stylesheets for Document Transformation” that you can download from here.
You can see me in this photo that JJ took explaining my poster to a great audience:
I hadn’t any problem explaining it. Nobody came to complain about colours, XML future, or typos in the word “Conclusions”. Oh, wait, I could remember… no, nobody came.
Here you can see me doing some magical science. Mmmh, who will be these guys sitting in that table?
After that I went to Castellón (Valencia, Spain) to present my paper “Algoritmos evolutivos distribuidos sobre dispositivos Bluetooth” (in Spanish, as you can see, but you also can download from here).
Just to say that it has been an awesome travel around the world! I met a lot of interesting people and learnt a lot. Yeah, I really love the researcher’s life.
The title of this post is due to today I received my MSc degree (I presented this paper in Granada, where I am a grad student).
Next week, Carlos Fernandes will present in the ANTS 2008 conference our paper KANTS: Artificial Ant System for Classification (hope the typo is not in the proceedings, but I’m afraid it will be). The algorithm was already presented by Antonio in ALIFE XI, with the paper KohonAnts: a self-organizing ant algorithm for clustering and pattern classification (which is also available from arxiv). Antonio was questioned about what was good about this algorithm, and I guess this is as good a place as any other to tell about it.
The basic idea of Kohonants is to use stigmergy for clustering and classification. Usual ant clustering algorithm place data as objects in the grid ants move around, and then, via some natural inspiration and a great deal of heuristics, they manage to cluster them according to proximity.
Kohonants, on the other hand, makes each data item an ant (or several, if needed). Pheromones are also vectorial in nature, in the same dimension as data, and what ants do when they move about is first take into account what’s the pheromone levels they have around in their neighborhood, and second modify it making them closer to the vector they represent.
That is why they are called Kohonen’s Ants: Kohonen’s algorithm behaves in the same way. Takes a training data vector, compares it to all the vectors in a two-dimensional array, and whoever wins is made closer to the data vector. Ants in Kohonants take the place of data vector in Kohonen’s algorithm, and the two-dimensional vector array that is trained is substituted by the two-dimensional (vectorial) pheromone field in Kohonants.
Results so far have been quite good, but we’ll continue with it to see what are their limits, and how well it fares against other ant and non-ant clustering algorithms. Meanwhile, as we mentioned in our previous post, you can download full code from the GeNeura code repository
The realization of a control unit can be done using a complex circuitry or microprogramming. The latter may be considered as an alternative method of implementation of machine instructions that can reduce the complexity and increase the flexibility of the control unit. The microcode efficiency and speed are of vital importance for the computer to execute machine instructions fast. This is a difficult task and it requires expert knowledge. It would be interesting and very helpful to have automated tools that, given a machine instruction description, could generate an efficient and correct microprogram. A good option is to use evolutionary computation techniques, which have proved been effective in the evolution of computer programs. In this paper, we intend to show how evolutionary computing techniques could be used to face this problem of generating efficient microprograms. We have developed a microarchitecture simulator of a real machine in order to evaluate an individual and to assign it the fitness value (to determine whether this candidate solution correctly implements the instruction machine). The proposed method is successful in generating correct solutions, not only for the machine code instruction set, but for new machine instructions not included in such set. We have shown that our approach can generate microprogramms to execute (to schedule microinstructions) the machine level instructions for a real machine. Moreover, this evolutive method could be applied to any microarchitecture just by changing the microinstruction set and pre-conditions of each machine instruction to guide evolution.
The poster, the source code of the proposed method and the full-length paper are available for download at http://atc.ugr.es/pedro/ev-micropr
Finally I’m going to be present in the Mankind History after my first publication in an international conference! It just a poster, but it’s still quite cool. It was presented in the GECCO’08 Conference, in Atlanta, where some intrepid GeNeura members drank a lot of Coca-Cola, even the (suspicious) beer flavoured Coca-Cola.
Here is 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.
You can download the draft from here, or the poster from here. The poster is orange, perfect for these summer days ;)
Now I am preparing my suitcase in order to go to the PPSN conference in Dortmund, where I will present an improvement of this algorithm.
Algorithms for decision support in the battlefield have to take into account separately all factors with an impact of success: speed, visibility, and consumption of material and human resources. It is usual to combine several objectives, since military commanders give more importance to some factors than others, but it is interesting to also explore and optimize all objectives at the same time, to have a wider range of possible solutions to choose from, and explore more efficiently the space of all possible paths. In this paper we introduce hCHAC-4, the four-objective version of the hCHAC bi-objective ant colony optimization algorithm, and compare results obtained with them and also with some other approaches (extreme and mono-objective ones). It is concluded that this new version of the algorithm is more robust, and covers more efficiently the Pareto front of all possible solutions, so it can be consider as a better tool for military decision support.
