Conferencias en el Máster en Tecnologías Informáticas Avanzadas de la UHU

El pasado viernes asistí a tres charlas que impartó el profesor Francisco Herrera del departamento de CCIA de la Universidad de Granada. En la primera de ellas, “Data Mining: From the Top 10 Algorithms to the New Challenges”, el profesor Herrera habló de los 10 mejores algorimos que se aplican a la minería de datos según (ICDM ‘06), así como de los 10 mayores retos de la minería de datos actual. La siguente charla, titulada “Data Complexity” estaba dedicada a los intentos de dar fundamento teórico a la minería de datos. Se habló de los modos de caracterizar los conjuntos de datos con el fin de recomendar que algoritmo funciona mejor con un determinado conjunto de datos. La última de las tres conferencias “How must I do my Experimental Study?” trataba los test estadísticos que deben aplicarse a los experimentos en un trabajo de investigación con el fin de justificar, por ejemplo, la calidad de un nuevo algoritmo. Se trató el uso de métodos estadísticos no-paramétricos que funcionan bien en conjuntos de datos que no siguen una distribución normal, cosa que sucede en la mayoría de los problemas reales. Este tipo de test, en palabras del profesor Herrera, empiezan a ser indispensables cuando se quiere publicar en revistas científicas de primer nivel. A continuación aportaré alguna información adicional sobre estas conferencias.

“Data Mining: From the Top 10 Algorithms to the New Challenges”

Lo candidatos al Top 10 debían cumplir algunos requisitos, como por ejemplo que tuviesen como mínimo 50 citas recientes.  De los inicialmente propuestos quedaron sólo 18 algoritmos finalistas. Los resultados del estudio fueron publicados en el artículo “Top 10 algorithm in data mining” y posteriormente en un libro con el mismo título. La siguiente tabla muestra a los finalistas clasificados en categorías.

Categoría	Finalistas
Classification	1. C4.5, 2. CART, 3. K Nearest Neighbours (kNN), 4. Naive Bayes
Statistical Learning	5. SVM,  6. EM
Association Analysis	7. Apriori,  8. FP-Tree
Link Mining	9. PageRank, 10. HITS
Clustering	11. K-Means,  12. BIRCH
Bagging and Boosting	13.  AdaBoost
Sequential Patterns	14. GSP,  15. PrefixSpan
Integrated Mining	16. CBA
Rough Sets	17. Finding reduct
Graph Mining	18. gSpan

En la segunda parte de esta primera charla, se presentaron los 10 grandes retos en minería de datos según (ICDM 2005). No he conseguido más información sobre la fuente del estudio. Ampliaré esta información cuando consiga las transparencias utilizadas en la charla. Los principales desafíos se engloban en las siguientes áreas:

1. Teoría. Definición de una teoría unificada ¿por qué funcionan los algoritmos? ¿cuales son los fundamentos del Data Mining?
2. Escalabilidad. Algoritmos que manejen gran cantidad de datos a gran velocidad.
3. Secuencialidad y series temporales. Técnicas para predecir acontecimientos a partir de datos históricos.
4. Datos complejos. Obtención conocimiento complejo a partir de datos complejos.
5. Minería de datos en redes sociales.
6. Minería de datos en bases de datos distribuidas.
7. Minería de datos para problemas biológicos y ambientales
8. Procesos de la minería de datos. Automatización, caracterización de los problemas, etc.
9. Seguridad, privacidad e integridad.
10. Minería de datos sobre datos no estáticos y datos cuya observación sea costosa.

Buscando más información sobre estos desafíos futuros he encontrado un artículo reciente sobre este tema titulado “Future tends in data mining“.

“Data Complexity”

Pretende dar respuesta a la pregunta “dado un problema de clasificación, ¿qué clasificador es mejor para el?”.  El libro de referencia es Data Complexity in Pattern Recognition. Para poder responder a esa pregunta se necesitan medidas de complejidad de los conjuntos de datos. Podemos encontrar diferentes medida de la complejidad de los datos en el trabajo de Tin Kam Ho, titulado “Measures of Geometrical Complexity in Classification Problems“.  Os dejo un enlace a las transparencias de la charla.

“How must I do my Experimental Study?”

Cuando nuestro trabajo de investigación consiste en el desarrollo de un nuevo algoritmo, es muy importante compararlo con con algoritmos de calidad. Muchos artículos son rechazados en revistas de prestigio, cuando se compara un nuevo algoritmo con versiones antiguas de nuestros competidores y no se incluyen comparativas con las últimas versiones más eficientes y precisas.  Justificar convenientemente la bondad del nuevo algoritmo utilizando  conjuntos de datos conocidos y métodos estadísticos es igualmente importante. En la dirección del grupo de investigación “Soft Computing and Intelligent Information Systems” que dirige el profesor Herrera, podemos encontrar información sobre estos métodos estadísticos y un software desarrollado por el profesor Salvador García, que genera los gráficos para incluir en documentos Latex utilizando a la entrada un fichero en formato CVS.

Data Mining: From the Top 10 Algorithms to the New Challenges

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

Using Dissortative Mating Genetic Algorithms to Track the Extrema of Dynamic Deceptive Functions

Traditional Genetic Algorithms (GAs) mating schemes select individuals for crossover independently of their genotypic or phenotypic similarities. In Nature, this behaviour is known as random mating. However, non-random schemes − in which individuals mate according to their kinship or likeness − are more common in natural systems. Previous studies indicate that, when applied to GAs, negative assortative mating (a specific type of non-random mating, also known as dissortative mating) may improve their performance (on both speed and reliability) in a wide range of problems. Dissortative mating maintains the genetic diversity at a higher level during the run, and that fact is frequently observed as an explanation for dissortative GAs ability to escape local optima traps. Dynamic problems, due to their specificities, demand special care when tuning a GA, because diversity plays an even more crucial role than it does when tackling static ones. This paper investigates the behaviour of dissortative mating GAs, namely the recently proposed Adaptive Dissortative Mating GA (ADMGA), on dynamic trap functions. ADMGA selects parents according to their Hamming distance, via a self-adjustable threshold value. The method, by keeping population diversity during the run, provides an effective means to deal with dynamic problems. Tests conducted with deceptive and nearly deceptive trap functions indicate that ADMGA is able to outperform other GAs, some specifically designed for tracking moving extrema, on a wide range of tests, being particularly effective when speed of change is not very fast. When comparing the algorithm to a previously proposed dissortative GA, results show that performance is equivalent on the majority of the experiments, but ADMGA performs better when solving the hardest instances of the test set.

Full paper here.

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.

Pervasive evolutionary algorithms on mobile devices

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.

You can download the draft from here.

Immigrants do all the work

Genetic Agorithms with Memory- and Elitism-based Immigrants in Dynamic Environments was the paper selected for presentation and discussion in last Friday’s seminar. The article, authored by Shengxiang Yang, was published in the last Fall edition of Evolutionary Computation and addresses evolutionary optimization in dynamic environments.

Yang proposes two Genetic Algorithms (GAs) for dynamic optimization based on Grefenstette’s classical Random Immigrants GA (RIGA). RIGA tackles (or tries to) changing optima by inserting, in each and every generation, a certain number of randomly generated individuals that replace the worst individuals in the population (or randomly selected individuals, in another version). This way, genetic novelty is constantly being introduced and the population is expected to have enough diversity to react to changes in the environments. However, RIGA suffers from a major “weakness”: the raw building-blocks introduced by the randomly generated individuals are quickly removed from the population because their fitness is usually below average. RIGA is frequently chosen as a peer-algorithm for comparison purposes in evolutionary dynamic optimization studies, but, due to this “weak spot”, it may be questioned if a Standard GA is not better suited to assess the efficiency of a new method (in fact, studies currently being developed in our lab reinforce this hypothesis). In order to improve RIGA’s performance, several alternative RIGA-based methods have been proposed in the past few years.

The two GAs described in Yang’s paper try to overcome the problem with random immigrants by inserting in the population mutated copies of the elite — Elitism-based Immigrants Genetic Algorithm (EIGA) — or mutated copies of the chromosomes kept in a memory — Memory-based Immigrants Genetic Algorithm (MIGA). Memory-based approaches for dynamic optimization use a memory to store good solutions, which are retrieved later, periodically, or when the environments changes. Memory GAs are known to improve traditional GAs performance when the dynamics of changes are cyclic, that is, the fitness function returns to previous “shapes” from time to time; on the other hand, memory schemes are not that effective when the changes are not periodic. Therefore, and as expected, MIGA outperforms other GAs when the changes are cyclic. EIGA is better when the changes in the environment are not severe. This behaviour is explained by the fact that introducing mutated copies of the best individual in the population provides the GA with means to tackle small changes because the algorithm is maintaining a kind of sub-population around the optimal solution, and small shifts in the environment are easily traceable by those near-optimal individuals.

Summarizing, the study shows that MIGA and EIGA are able to outperform other GAs under the conditions of the test set. However, there is one question that remains unanswered: what happens when changing the parameter values? For instance, diversity maintenance schemes for dynamic optimization deal with non-stationary environments by maintaining the diversity at a higher level. This means that maybe the optimal mutation probability of these algorithms is different from those of Standard GAs. Shouldn’t a proper comparison between the algorithms consider a range of possible mutation probabilities (Yang’s studies used the traditional pm = 1/l, where l is the chromosome length)? And what about population size? Isn’t population size the major bottleneck for GAs’ performance in stationary environments? Is it possible that a variation in the population size of the GA for dynamic optimization conduces the research to different conclusions? Studies currently under way will try to answer to some of these questions.

Genetic algorithm with rough set theory

Last Friday we discussed the paper “The generic genetic algorithm incorporates with rough-set theory – An application of the web services composition” of Liang and Huang.  This is the standard mixture paper: a kind of algorithm + another soft computing technique + an application of the real world = a complete paper. I am not kidding, I think that combining several techniques, and more important, using them in real applications, should be a basis of research.

Rought set theory provides a way to create a set of decission rules that can be selected in every problem with functional requirements. For example in the extensive area of web services composition. We can provide this information to a genetic algorithm to compose services avoiding constrained solutions and initial population using that decission rules. The authors also use non-functional requirements, such QoS, cost or avilability in the fitness function. They conclude that the usage of rough set in a GA could increase the convergence (but it is necessary to keep some unfeasible solutions during the process, just in case).

It is a easy-to-read paper, so probably you would like to read it instead my summary ;) Moreover, they present some ideas in the web service composition area.

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.