yerarthinks

ejercicio número 55 de la revista antena de telecomunicación

2008-11-07T19:04:00.003+01:00

En esta ocasión,

las blancas juegan y dan mate en cinco jugadas

A ver lo que se me ocurre ... ;)

ejercicio número 54 de la revista antena de telecomunicación

2008-07-18T14:23:00.002+02:00

Juegan Blancas

y a pesar del peligro que tienen en b2, consiguen mate en cinco movimientos.

A falta de la solución en el próximo número, esta es mi propuesta:

1. Rh8+, Bxh8
2. Bh6+, Bg7
3. Bxg7+, Kg8
4. Bh6+, Kh8
5. Qg7#

Multiple-choice Knapsack Problem

2008-07-15T22:33:00.002+02:00

In my new job at University of Cantabria, where I work on a FP7 European research called MULTICUBE, whose objective is to build an innovative design space exploration (DSE) tool for MpSoCs, I've found out an unexpected application of genetic algorithms.

When you co-design a hardware/software application on a MpSoC architecture you must chose a suitable architecture (doing an architecture exploration by tuning parameters of the afore mentioned architecture in order to optimize power, performance, area, etc) and then you must map the functionality implemented by the application software optimally (run-time exploration) over the different hardware resources (e.g. microprocessor cores) in order to fully use all the resources available within the constraints imposed by the application.

The process of mapping optimally could be seen as a classical Knapsack Problem (see a Google Search on the subject), which is a problem in combinatorial optimization. The thing is, that instead of 0-1-knapsack problem, we've got a Multiple-choice Knapsack Problem (MMKP), that is one of the list of knapsack problems with n items (e.g. application tasks) and m knapsacks (e.g. hardware resources) with capacities Wi.

There are several approximations to the solution of the (NP-Complete) problem including greedy ones, dynamic programming ones, heuristic ones, etc. But the ones that I'm interested in are the evolutionary computation approaches. It's not easy to find open access to papers which present such solution approaches. I've found out a paper who explains a heuristic approach (convex hull) with the quality of service (QoS) management problem of the Multiple Resource Multiple Dimension (MRMD) systems example.

Solving the Multidimensional Multiple-choice Knapsack Problem by constructing convex hulls
Md Mostofa Akbar (a),(b), M. Sohel Rahman (b), M. Kaykobad (b), E.G. Manning (a), G.C. Shoja (a)

(a) Department of CSC, PANDA Lab, University of Victoria, Victoria, BC, Canada, USA
(b) Department of CSE, BUET, Dhaka, Bangladesh

In the paper the authors state that:

Various other techniques like tabu search [14], simulated annealing [15] and genetic algorithms [16] can also be applied to solve the variants of Knapsack Problem. The genetic algorithm has the exponential worst-case complexity—it can explore all the items. Tabu search and simulated annealing are based on looking at the neighbours. These are costlier than the greedy approach used in HEU (heuristic). HEU uses a two-way interchange approach and searches candidates in the neighbourhood which yield better revenue, and changes one selection to another. But in tabu search, simulated annealing and genetic algorithm approach, current solution is moved to another solution by upgrading some and downgrading some. This upgrade and downgrade at the same step requires more time because we have to search all neighbouring combinations of current solution. In the next section, we present our main contribution by presenting a new heuristic to solve MMKP by constructing convex hulls.

The references aforementioned are:

[14] Dammeyer F,Voss S. Dynamic tabu list management using the reverse elimination method.Annals of Operations Research 1991.

[15] Drexel A. A simulated annealing approach to the multiconstraint zero-one knapsack problem. Annals of Computing 1988;40:1–8.

[16] Khuri S, Back T, Heitkotter J. The zero/one multiple knapsack problem and genetic algorithms. ACM Symposium of applied computation; 1994.

So it seems this time genetic algorithms are not the best option at hand to solve the problem ... :)

ejercicio número 53 de la revista antena de telecomunicación

2008-06-10T22:06:00.003+02:00

En el rincón de ocio de la revista Antena de Telecomunicación del primer cuatrimestre del primer cuatrimestre de este año (número 1, abril 2008) del Colegio de Ingenieros Técnicos de Telecomunicación (COITT) tenemos la sección habitual dedicada a los problemas de ajedrez, con el siguiente ejercicio planteado:

Ejercicio n.º 53

Las negras están al completo y con amenaza inminente al Rey blanco; sin empbargo las blancas consiguen mate en cuatro movimientos.

Después de pensar un rato y ensayar los movimientos en el scid, he llegado a la siguiente propuesta de solución:

1. Qxe8+!, Kxe8
2. a8=Q+, Qd8
3. Ba4+, Kf8
4. Qxd8#

Hasta el siguiente cuatrimestre no podré saber si acerté con la solución ... :)

The Wombats - Kill The Director

2008-05-07T23:10:00.000+02:00

Almost my favourite band!!! :)

Lyrics

Kill the director

I've met someone that makes me feel seasick
Oh what a skill to have
Oh what a skill to have
So many skills that make her distinctive
But they're not mine to have
No they're not mine

Whenever she looks i read the nearest paper
No i don't care about the soaps
No i don't care about the soaps
Though i'm acting like i'm in an Eastenders episode

If this is a rom-com
Kill the director
If this is a rom-com
Kill the director please

Carrots help us see much better in the dark
Don't talk to girls; they'll break your heart
And this is my head and this is my spout
They work together; they can't figure anything out

So with the angst of a teenage band
Here's another song about a gender i'll never understand
Here's another song about a gender i'll never understand

If this is a rom-com
Kill the director
If this is a rom-com
Kill the director
If this is a rom-com
Kill the director please

This is no Bridget Jones
This is no Bridget Bridget
This is no Bridget Jones
This is no Bridget Bridget
This is no Bridget Jones
This is no Bridget Bridget
This is no Bridget Jones
This is no Bridget Bridget
This is no Bridget Jones
This is no Bridget Bridget
This is no Bridget Jones
This is no Bridget
Bridget Jones

czebe-sarosi, Hungary championship, 1993

2008-05-06T23:36:00.000+02:00

Blancas juegan y ganan

Con enérgica maniobra de ataque, las blancas explotaron la mala situación del rey enemigo, en la posición de la partida Czebe-Sarosi (Campeonato de Hungría por equipos, 1993) ¿Cuál es el plan ganador?

Solución:

1. Nxf7! Rxf7

(si 1. … Kxf7
2. Bxd5+)

2. Bxf6 Bxf6

(a 2. … Nxf6
3. Rxf6 Bxf6
4. Qxc8+)

3. Rxd5 Qc6

4. Rd6 Qe8

5. Rd7

y las negras abandonaron. Un fino juego con el tema de las piezas clavadas.

more biological inspiration for evolutionary algorithms

2008-05-05T17:55:00.001+02:00

The fact is that the bulk of EA techniques relies on a very simplified model of biological genetics, using haploid crossover and point mutation. While a few researchers have investigated diploid crossover:

- Smith, R. E. (1988) An investigation of diploid genetic algorithms for adaptive search of nonstationary functions. TCGA Report No. 88001, University of Alabama, The Clearinghouse for Genetic Algorithms, Tuscaloosa (Smith 1988),

there is still a minimal application of the current knowledge of biological genetic processes. In particular, the understanding fo how genes regulate each other's activity needs significant study (for example this?) with respect to artificial evolution.

Another fruitful area would be a comparative study of the transcription and translation mechanisms in an artificial evolution context. Similarly, the role that introns play in preserving useful schema is an active research domain (although this has been the subject of greater study in the genetic programming community, where junk genes lead to bloat of the tree representation genomes)

the diploid chromosome mechanism for Evolutionary Algorithms

2008-05-04T17:05:00.002+02:00

(from book Applied Evolutionary Algorithms in Java)

One interesting variance between biological evolution mechanisms and those used in most evolutionary algorithms is that organisms normally use a diploid chromosome structure, while EAs use a haploid design. First, however, we need a basic definition of the term "diploid":

Pertaining to homologous chromosomes, where each cromosome number has a pair of chromosomes, such as th 23 pairs in humans totaling our 46 chromosome compliment. (biology online)

A diploid chromosome structure is therefore composed of a pair of chromosomes. One advantage this offers is to allow memory to be incorporated into the individual's chromosome structure. In an EA context the choice between the two values requires some form of dominance function. Lewis et al. (1998) give a useful comparison of the relative merits of haploid and diploid designs:

- A Comparison of Dominance Mechanisms and Simple Mutation on Non-Stationary Problems. Jonathan Lewis, Emma Hart, Graeme Ritchie. Lecture Notes in Computer Science

Tha main proposed application area for a diploid EA is when the fitness function is time-varying. Hence the aditional information stored in the chromosome can provide a secondary source of diversity within the population. In addition, the diploid structure may enable the retention of long-term memory of past solutions, which will be useful if the fitness landscape is time-dependent. However, very little experimental work has yet been performed in this area.

To this last point, I've searched for extra info (papers) on time-varying (changing) optimization problems, being that this is a clear line of research in this field. These are my findings:

- Memory Enhanced Evolutionary Algorithms for Changing Optimization Problems. Jürgen Branke. Proceedings of the Congress on Evolutionary Computation (1999)

- Evolutionary Approaches to Dynamic Optimization Problems A Survey. Jürgen Branke. Evolutionary Algorithms for Dynamic Optimization Problems (1999)

- Evolutionary Approaches to Dynamic Optimization Problems Updated Survey. Jürgen Branke. Evolutionary Algorithms for Dynamic Optimization Problems (2001)

- Evolutionary Algorithms for Non-Stationary Environments. Krzysztof Trojanowski, Zbigniew Michalewicz. Proc. of 8th Workshop: Intelligent Information systems (1999)

- Non-stationary Function Optimization using Evolutionary Algorithms with a Case-based Memory. J. Eggermont, T. Lenaerts.

evolvable hardware, FPGAs and evolutionary algorithms

2008-05-03T15:53:00.006+02:00

(from the book Applied Evolutionary Algorithms in Java)

Evolvable Hardware

On of the most exciting developments in EA systems has been the development of hardware that directly supports evolution-based search algorithms. In particular, the availability of Field Programmable Gate Arrays (FPGA) chips allows real-time configuration of logic circuits that can evaluate a specified function (Thompson, 1996) Work at Sussex University by Adrian Thompson demonstrated that a FPGA device could be automatically configured using a genetic algorithm to solve a signal processing problem. This work open an entirely new domnain for tha application of evolutionar algorithms in two important ways: first by showing how reconfigurable hardware could allow improve processing of an EA problem; and second by showing that evolution could exploit the actual physics of a synthetic environment.

Thompson draws some fascinating conclusions regarding the power of such techniques:

A surprising hypothesis is suggested: Even within robust digital design, unsconstrained evolution can produce cirsuits beyond hte scope of conventional design rules. Previously it had been assumed that the domain of robust digital design was fully covered by conventional design rules. Given the undoubted utility of robust digitl designs, it is an exciting possibility that evolution could explore novel regions of design space, containing circuits that may be better for some applications

The main difficulty in utilising an EA technique, however, is the sensitivity of the evolved design to the exact environmental conditions under which it was evolved. For example, the resulting ciruit is normally sensitive to temperature. Further work from Thompson has aimed to enhance the robustness of this process by evolving circuits across a range of temperature values.

The emerging field of evolvable hardware, in FPGA devices, is particularly exciting as it enables the possibility of real-timne learning by EA systems. It also opens an entirely new domain of physical evolution in synthetic substrates, which take advantage of the actual ohysics of electronic systems. Providing such systems can achieve robust solutions, then it cpuld lead to entirely new classes of hardware, which fully exploit the capabilities of the silicon substrate; including their application to evolving analogue electronic devices. (NASA has been particularly interested in the possibilities offered by this technology and has arranged a series of workshops on Evolvable Hardware)

multiobjective optimisation as an advanced Evolutionary Algorithms technique

2008-05-02T15:13:00.004+02:00

(from book Applied Evolutionary Algorithms in Java)

It is a fact of life that we rarely, if ever, achieve all our current goals, since multiple goals of any agent are frequiently in conflict with each other (a robot to take the shortest route to the target and the need to safely avoid obstacles en route) Most real-world applications for EA methods contain conflicting sets of optimisation criteria; hence we require some means for achieving multiobjective optimisation.

Given some set of competing performance criteria such as resource efficiency, cost, and speed, when no further improvement can be made in one without degrading the quality of another, then the system is said to be Pareto-optimal.

The approaches to multimobjective optimisation can be divided into three categories:

(1) Plain aggregating approaches. Objectives are numerically combined into a single objective function to be optimised (i.e weighted sum approach)

(2) Population-based non-Pareto approaches. Different objectives affect the selection or deselection of different parts of the population in turn (sort of tabu search?)

(3) Pareto-based approaches. The population is ranked, making direct use of the definition of Pareto dominance.

This categorization is made by Carlos M. Fonseca (see publications) I've done a search in Google which has yielded the following interesting paper hits:

- Genetic Algorithms for Multiobjective Optimization: Formulation, Discussion and Generalization. Carlos M. Fonseca, Peter J. Fleming. Genetic Algorithms: Proceedings of the Fifth International Conference (1993)

- An Overview of Evolutionary Algorithms in Multiobjective Optimization Carlos M. Fonseca, Peter J. Fleming. Evolutionary Computation (1995)

Artificial intelligence, Telecom and robotic space exploration

2008-05-01T23:19:00.002+02:00

I have stumbled upon two news releases from the European Space Agency (ESA) about the use of AI techniques to help to improve the performance and quality acquisition of science data from the Mars Express Mission. The first news release is an interview with Dr Ari Kristinn Jónsson, Dean of the School of Computer Science at Reykjavik University, Iceland, and former research scientist at NASA's Ames Research Center, where he led various projects both in AI development and in AI applications for space missions.

Artificial intelligence for robotic exploration: Q&A with Ari Kristinn Jónsson

29 April 2008

Dr Ari Kristinn Jónsson says that artificial intelligence (AI) can open up new opportunities for the long-term exploration of the solar system, supporting missions that require minimal oversight from human controllers on Earth.

The second news release deals specifically with the problem in Mars Express that has been resolved with the help of MEXAR2 ('Mars Express AI Tool'), developed by AI researchers at Italy's Institute for Cognitive Science and Technology (ISTC-CNR) led by Dr Amedeo Cesta and mission planners and computer scientists at the European Space Operations Centre (ESOC) in Darmstadt, Germany.

Artificial intelligence boosts science from Mars

29 April 2008

Artificial intelligence (AI) being used at the European Space Operations Centre is giving a powerful boost to ESA's Mars Express as it searches for signs of past or present life on the Red Planet.

[...]

Traditionally, data downloading was managed using human-operated scheduling software to generate command sequences sent to Mars Express, telling it when to dump specific data packets. "This is tedious, time-consuming and never really eliminated the occasional loss - forever - of valuable science data," says Alessandro Donati, Head of the Advanced Mission Concepts and Technologies Office at ESA's Space Operations Centre (ESOC), Darmstadt, Germany.

[...]

But since 2005, AI researchers at Italy's Institute for Cognitive Science and Technology (ISTC-CNR) led by Dr Amedeo Cesta and mission planners and computer scientists at ESOC have been developing a solution to the complex Mars Express scheduling problem by applying artificial intelligence (AI) techniques to the problem. These are similar to those used to solve scheduling and optimisation problems faced by airlines, shipping companies and large construction projects.

ejercicio número 52 de la revista antena de telecomunicación

2008-04-13T21:04:00.003+02:00

Las blancas al completo y a punto de coronar Dama ... sin embargo juegan negras y consiguen mate en cinco movimientos!

Estos son los movimientos fatales para las blancas confiadas:

1. ..., Ce7+
2. Rb8, Axc7+
3. Ra8, o-o+
4. Tb8, Txb8+
5. Pxb8->D, Txb8#

The killers - When you were young

2008-04-06T20:15:00.004+02:00

Here's a video of one of my favourite bands, the killers:

And here are the lyrics:

You sit there in your heartache
waiting on some beautiful boy To..to save you from your old ways

You play forgivness watch it now here he comes
he doesn't look a thing like jesus but he talks like agentleman like you imagined when you were young

Can we climb this mountain i don't know higher now than ever before
I know we can make it if we take it slow
take it easy.. take it easy now watch it go

We're burning down the highway skyline on the back of a hurricane it started turning
when you were young
when you were young

And sometimes you close your eyes and see the place where you used to live
when you were young

They say the devils water it ain't so sweet you don't have to drink right now but you can dip your feet in every once and a little while

You sit there in your heartache
waiting on some beautiful boy To..to save you from your old ways

You play forgivness watch it now here he comes
he doesn't look a thing like jesus but he talks like a gentleman like you imagined when you were young

(talks like gentleman like you imagined) when you were young
when you were young
I said he doesn't look a thing like jesus
he doesn't look a thing like jesus
but more than you wil ever know

learning java by examples

2008-03-20T21:24:00.002+01:00

Being that I have to learn Java programming language in order to be able to make and understand evolutionary algorithms in Java, I've decided to search in Google looking for Java source code examples to start learning.

There are certainly plenty of hits (more than one and a half million of them!) If I had to select some first-cut starting point to explore Java source code, I'd choose Java Examples Organised by topic website (which also features examples of other popular and interesting languages like C/C++ or C#) Another good starting point is The Java Developers Almanac 1.4, which has, in my opinion, several very pedagogic examples.

A good free online electronic book, from Bruce Eckel, is Thinking in Java, 3rd Edition. All source code from examples developed in the book is available for downloading. There is a fourth edition of the book but it is only available for purchase. The author has other books on programming in other programming languages (e.g. C/C++) which could be interesting.

Arthur C. Clarke Obituary

2008-03-19T17:02:00.004+01:00

This morning I've heard in the radio news that yesterday Arthur C. Clarke has passed away. This man has been (it is) one of my favourite Science Fiction authors. We have lost one of the best ones. I like the weight Science has in all his novels and short stories. I'll miss him a lot.

I feel the mourn, the same mourn as I felt when Isaac Asimov or Carl Sagan passed away. I've found out that I'm not alone. I've searched on Google for obituary news about Arthur C. Clarke and there are thousands of hits. I think that is wonderful. So many people remembering this great human being. I've read some of them: the BBC News one and the Fantastic Fiction UK website one.

After reading the latter and skimming at the myriad of books he has written, I've been searching for his books, the ones I've read for years, in my own personal library at home. What have I found? Well, these ones:

Certainly not a big collection. I promise I'm going to read the rest of them, he has written.

Time for Open Source Software Vendors to Think Beyond Free

2008-03-16T16:51:00.001+01:00

SOA WORLD

Thinking that free is the only aspect of software that matters is "freetarded"

By: Christopher Keene

Mar. 15, 2008 09:00 PM

Time for Open Source Software Vendors to Think Beyond Free
— Of the many sins that Silicon Valley practices, none are more dangerous or prevalent than the sin of smugness. Savio Rodrigues has a good posting making the point that Microsoft is learning from and adapting to the open-source movement, while the open-source movement is so enamored with 'free' that they are not paying enough attention to the total cost of ownership from a customer's perspective.

Weizenbaum and Artificial Intelligence

2008-03-15T15:03:00.003+01:00

People dies everyday. Some of them because they're old and his/her life comes to an end. On March 5th, Joseph Weizenbaum, a German-American author and professor emeritus of computer science at MIT, passed away. I've just read it in a posted blog article while looking for AI news in Internet. He's the author of ELIZA a computer program which parodied a Rogerian therapist. This program raised some interesting questions about Turing Tests and human machine interaction.

Web Development: RIA + SOA

2008-03-12T18:06:00.002+01:00

SOA World Magazine Newletter

News Desk

Coming Next in Web Development: RIA + SOA

RIA represents the rich user interface and SOA represents the services that it consumes

By: Nolan Wright

Mar. 12, 2008 04:45 PM

Coming Next in Web Development: RIA + SOA
— The world of web development is moving away from MVC-based web architectures and towards a client/server model that is probably best described as RIA + SOA, where RIA represents the rich user interface and SOA represents the services that it consumes. There has been a lot of buzz around rich Web 2.0 applications, but they will not become mainstream until the next generation of web platforms emerge - fully integrated platforms that enable RIA + SOA.

Article URL:

http://soa.sys-con.com/read/513263.htm

Trackback URL:

http://soa.sys-con.com/read/513263_trackback.htm

Google Search and Business Intelligence

2008-03-06T17:45:00.001+01:00

SOA World Magazine Newsletter

Business Intelligence

Introducing "Generation S" - for Search

Generations X and Y are being followed by one that will rely on search to accomplish almost any task

By: Rado Kotorov; Jake Freivald

Mar. 6, 2008 04:45 AM

Introducing "Generation S" - for Search
— My seven-year-old daughter thinks that there is a knowledge genie that her teacher 'Googles' for answers. While cute, the anecdote also exemplifies how much Google's obsession with simplicity has helped build brand awareness, making their name literally synonymous with search. I can foresee generations X and Y being followed by generation S - one that will rely on search to accomplish almost any task.

Article URL:

http://soa.sys-con.com/read/507951.htm

Trackback URL:

http://soa.sys-con.com/read/507951_trackback.htm

game theory, competition and cooperation: the GNU GPL model?

2008-03-05T09:55:00.004+01:00

I've just read a draft paper from a redhat company person about economical justification of the GNU GPL model based on game theory concepts and the synergies between cooperation and competition.

A Beautiful Mind Meets Free Software: Game Theory, Competition and Cooperation by Alexandre Oliva.

Abstract

Russel Crowe, playing John Nash in Ron Howards’ motion picture “A Beautiful Mind”, claims that Adam Smith’s theory that “in competition, individual ambition serves the common good” is incomplete, and that “the best result will come from everybody in the group doing what’s best for himself, and the group”. Adam Smith’s motto synthe- sizes pretty well what happens in the competition-driven proprietary software development market, whereas John Nash’s adds the cooperation that is so common even among competitors in Free Software markets. Every commercial Free Software developer tries to obtain its edge by developing better software, thus contributing to the software pool that even its competitors will be able to build upon, i.e., every Free Software developer does what’s best for himself, and the group, so the best outcome is achieved. The paper shows how the GNU GPL licensing model can be economically favourable to developers over proprietary and even BSD-like licenses.

This draft paper reviews briefly John Nash contributions to Game Theory, especially the nash equilibrium concept. Then it introduces some basic concepts on Game Theory such as prisoner's dilemma and the tragedy of the commons. There is a relationship of these Game Theory concepts with those of software development and licensing models. Using that relationship the author tries to show that development under the GNU GPL can be more favourable than proprietary or BSD-like licenses.

I've been surprised to read that the credible commitment from commoners to avoid overuse in tragedy of the commons case has real world examples like the Kyoto Protocol as a self-imposed commitment.

The conclusions of the author are that choosing the GNU GPL can be the best choice not only for software users, but also for software developers and vendors, enabling them to share development costs and to achieve a better overall economic efficiency while still being fairly paid for their services

It is an interesting debate the trade-off between cooperation and competition, is it better to be selfish or cooperative?

Cooperation in Wireless Networks: Principles and Applications: Real Egoistic Behavior is to Cooperate! (Hardcover)

2008-03-04T21:49:00.000+01:00

Today I've started to read a technical book about cooperation and its application to wireless communications, a hot topic both in academy and in business:

Cooperation in Wireless Networks: Principles and Applications: Real Egoistic Behavior is to Cooperate! (Hardcover)
by Frank H.P. Fitzek (Editor), Marcos D. Katz (Editor)

Cooperation is known as an effective strategy in nature to achieve individual or common goals by forming cooperative groups. The authors look for applying the same cooperative strategies we can see in nature to the field of wireless communications at all levels. The cross over between nature and engineering has always been fruitful. Mimicking nature as a source of inspiration in engineering is a winner strategy. Thee book itself is written in a collaborative manner by several authors from Asia, America, and Europe :) Cooperation has already been studied by Social Sciences with well established theories and experiments. Now it's being studied as a hot topic in many sub fields of wireless communications. Every chapter of the book is written formally as a paper.

I've read the first chapter, which has the following table of contents:

1. Cooperation in Nature and Wireless Communications;
Frank H. P. Fitzek and Marcos Katz.

1. Basics of Cooperation.
2. The Prisoner’s Dilemma.
3. The Iterated Prisoner’s Dilemma.
4. N–person Prisoner’s Dilemma.
5. Stimulating Cooperative Behavior.
6. Cooperation in Wireless Communication Systems.
7. Cooperative Principles in Wireless Communications: The Future.
8. Conclusion.

References.

In this chapter, examples of nature are cited as successful models of cooperation: lichens, carnivore hunting groups, Tour de France peloton and vampire bats. We can model those interactions and apply then to the field of wireless communications. Objective: maximize the QoS of the network, minimizing the complexity of the terminals, air interface and power consumption.

In this chapter, the authors put as a basic example a game: the prisoner's dilemma, and two interesting derivatives: Iterated PD and N-person PD which are directly applicable to the wireless communication field. They cite Wilensky (2002) NetLogo PD N-Person Iterated Model for gathering further information and Robert Axelrod's tournaments. Here the participants are intelligent (embedded agent based) wireless terminals with long range cellular network and short range ad-hoc network capabilities. Among the strategies which use those terminals, we have Tit for Tat (TFT) and unforgiven Tit for Tat as the most rewarding (being pure cooperation, defecting and random the worst, respectively) These are game theory strategies. They give rules to be successful in an environment with multistrategy individuals.

Cooperation in Wireless Networks is first classified in communicational, operational and social. The communicational aspect is treated in the book. A further classification of this aspect is implicit (i.e ALOHA, TCP/IP flow control) or explicit. The explicit can be subdivided in macro (i.e relying in Wi-Fi networks) and micro (i.e lower link layers, Multiple Description Coding, Multicast, UMTS + WLAN, power saving)

I've found a connection between a set of cooperating agents trying to solve a problem (á la AI) and the set of terminals in an environment cooperating in order to communicate with each other. They both play a game, a prisoner's dilemma game in which they use a series of strategies in order to maximize each one gain. Should these agents use AI techniques (i.e evolutionary computation) to manage its goals? To cooperate, terminals need information about the environment (i.e air interface, channel, other terminals) and should be able to decide what to do based on that information (i.e cognitive radio/communication over software defined radio)

all tomorrow's parties

2008-03-01T07:51:00.006+01:00

I've just finished reading the William Gibson's Scifi novel All Tomorrow's Parties (Amazon, Wikipedia) I liked it but it has not been the best novel I've ever read. It is the third book in William Gibson's Bridge trilogy. I've only read this one.

It deals with emerging technologies. Emerging technologies and converging technologies are terms used interchangeably to cover the emergence and convergence of new and potentially disruptive technologies such as nanotechnology, biotechnology, cognitive science, robotics, and artificial intelligence (wikipedia dixit) Indeed, the author suggests the emergence of nanotechnology and teleportation as a driving force developing under the cover in the novel. Another strong presence is AI with Rei Toei, the Idoru, an enigmatic and sophisticated artificial human being, which has been the main character of other William Gibson's novel.

The author describes which some of the character's novel call an intersitial society developed within the partially damaged San Francisco's bridge after the Big One. This society is semi independent of all regulatory law and order of the rest of the city.

In the back cover of the book is the following text:

Laney, living on blue cough medicine in a cardboard city, is scaning for nodality, for the future. A future that depends on Rei Toei, the idoru -- beautiful girl, virtual icon, post-human being. Rydell -- ex-cop, ex-security for Lucky Dragon convenience stores -- is working for Laney, soft of, but he's looking for a future too, and for Chevette, who was once his gril (and is now on the run) And now Rydell's back in San Francisco, back on the Bridge, where it all began, and where it looks like it might all end, possibly with a number of big bangs.

But endings are also beginnings ...

This scanning for nodality Laney does, seems to me a sophisticated data mining process helped with the visual interface to the Net, now a sort of Second Life on steroids. These nodal points he's looking for remind me also of Free Scale Networks and Complex Systems.

ejercicio número 51 de la revista antena de telecomunicación

2008-02-26T22:13:00.003+01:00

En el Rincón del Ocio del boletín Antena de Telecomunicación, del Colegio Oficial de Ingenieros Técnicos de Telecomunicación (COITT) tenemos un problema de ajedrez para resolver.

Las negras juegan y ganan. Esta es mi solución:

1. ..., Qg3
2. Qf2, Qxf2

(si 2. Qe2, Qxg1#)

3. ..., Rxh2#

Virtualization, SaaS & SOA: Introducing Service Oriented Programming

2008-02-25T16:23:00.003+01:00

SOA World Magazine

Unifying Grid Virtualization, SaaS and SOA

By: Ash Massoudi
Feb. 25, 2008 10:15 AM

Virtualization, SaaS & SOA: Introducing Service Oriented Programming
— The advent of SOA and standard-base Web services together with Internet based delivery models has provided the essential base for facilitating new software platform innovations. One of these innovations is a breakthrough software componentization technique that we have coined Service Oriented Programming (SOP). While SOA focuses on communication between systems using 'service operations,' SOP provides a new technique to build agile application modules using in-process, native service operations as the 'units of assembly.'

Article URL:
http://soa.sys-con.com/read/467329.htm

Trackback URL:
http://soa.sys-con.com/read/467329_trackback.htm

Web 2.0 Mashups & SOA

2008-02-24T22:43:00.001+01:00

SOA World Magazine

The Convergence of Web 2.0 Mashups & SOA
A world of opportunities for enterprises

By: Rakesh Saha
Feb. 24, 2008 11:00 AM

The Convergence of Web 2.0 Mashups & SOA
— Enterprise mashups - the convergence of Web 2.0 mashups and service-oriented architecture (SOA) - can create a world of opportunities for enterprises to come up with internal and customer-facing self-service, composite and 'situational' applications. These applications can be created just-in-time by empowered enterprise business users and by simply combining SOA-enabled information sources and services or SOBAs (service-oriented business application) on the intranet and Internet.

Article URL:

http://soa.sys-con.com/read/497055.htm

Trackback URL:

http://soa.sys-con.com/read/497055_trackback.htm

The Wombats - Moving to New York

2008-02-17T12:05:00.003+01:00

This is the last vídeo I've seen today in YouTube:

And these are the lyrics:

The Wombats - Moving to New York Lyrics

I’ve just had the craziest week,
Like a party bag of lies, booze and then deceit.
And I don’t know why I want to voice this out loud,
It’s therapeutic somehow.

So I’m moving to New York cos I’ve got problems with my sleep,
And we’re not the same and I will wear that on my sleeve.
So I’m moving to New York cos I’ve got issues with my sleep,
Looks like Christmas came early, Christmas came early for me.

I put one foot forward and ended up thirty yards back.
And am I losing touch or am I just completely off the track?
And I don’t know why I want to voice this out loud,
It’s therapeutic somehow.

So I’m moving to New York cos I’ve got problems with my sleep,
And we’re not the same and I will wear that on my sleeve.
So I’m moving to New York cos I’ve got issues with my sleep,
Looks like Christmas came early, Christmas came early for me.

So I’m moving to New York cos I’ve got problems with my sleep,
And we’re not the same and I will wear that on my sleeve.
So I’m moving to New York cos I’ve got issues with my sleep,
Looks like Christmas came early, Christmas came early for me

basic genetic algorithm implemented in java

2008-02-12T18:14:00.003+01:00

The following java classes provide tha basis for a very simple genetic algorithm. The source code has been copied from Appendix B of the book Applied Evolutionary Algorithms in Java by Robert Ghanea-Hercock. I want to use it as a blueprint to achieve a more complex implementation by myself, incorporating all improvements suggested in Appendix B and Chapter 3 in that excellent book.

The first class called individual.java, acts as a generic object representation of each chromosome in a GA population. An individual contains all the data required to define a specific chromosome and stores the current fitness values associated with the individual. The actual chromosome is stored within a Java Vector object, so we have the choice of using any basic Java object as a gene representation (floats, integers, doubles, ...)

Here is the source code (I've used a nice online utility by Greg Houston, which alloes me to format the source code for blogging. If anyone knows a better form, with syntax colouring for example, let me know please)

/** A Genetic Algorithm Example in Java
    
    From Applied Ecolutionary Algorithms in Java by Robert Ghanea-Hercock.
    Appendix B.
    
    individual.java
    
    individual class, defines a single individual chromosome. Acts as a generic
    object representation of each chromosome in a GA population. An individual
    contains all the data required to define a specific chromosome and stores
    current fitness values associated with hte individual.
    
    The actual chromosome is stored within a Java vector object. By selecting
    this design we have the choice of using any basic Java object as a gene
    representation: floats, integers, doubles, etc. 
    
**/
    
import java.util.Observable;
import java.util.Hashtable;
import java.util.Vector;

public class individual implements Cloneable {

  /** constructor */

  public individual () {

    chromosome = new Vector(); // Dynamic resizable array for genes
    fitness = 0.0; // raw fitness value
    scaledFitness = 0.0; //relative fitness value
  }

  /** variable class members */

  public double fitness;
  public double scaledFitness;
  public Vector chromosome;

  /** Method for return full copy of this individual */

  public individual copy () {

    individual newInd = new individual ();
    newInd.chromosome = (Vector)this.chromosome.clone();
    newInd.fitness >= this.fitness;
    newInd.scaledFitness = this.scaledFitness;
    
    return newInd;

  }

} 

/** end class **/

The second class, genetic.java, tries to match the contents of a one-dimensional set of double values generated from a simple mathematical function (sin x) and prints the output to screen. This is the source code:

/**

    Main genetic algorithm class. This version tries to match the contents of a
    1-D array of double numeric values. A one-dimensional set of double values
    generated from a simple mathematical function (sin x) Then it prints the
    output to screen.
    
**/

import java.util.*;

public class genetic {

/** variables */

// fitness calculation

double sumFitness;
double bestFitness;
double averageFitness;

// individuals to evolve

individual population []; // array of current individuals
individual newpopulation []; // array of next generation of individuals
individual bestIndividual; // best individual

// GA parameters

int popSize; // number of individuals
double alleleSize; // range of the target numeric values
int maxLength; // (maximum) length of chromosome
int minLength; // (minimum) same as above for fixed length chromosomes
int generation = 0; // generation count

// Random

Random random;
static final int seed = 93404;


// array to match

public double testarray [];

/** constructor */

public genetic () 
{

  // Fist, we choose a suitable GA parameters (could be fetched from file?)
  
  popSize = 120;
  maxLength = 16;
  minlength = 16;
  alleleSize = 99.0;
  
  // Fitness and Random
  
  sumFitness = 0.0;
  random = new Random (seed);
  
  // Creation of population
  
  testarray = new double(maxlength);
  bestIndividual = new individual ();
  population = new individual[popSize];
  
  for (int i=0; i<popSize; i++)
  {
    population[i] = new individual();
  }
  
  // Initialise population
  
  population = initialisePopulaton (population);
}

/** method to initialise the population of individuals */

public individual[] initialisePopulation (individual pop[])
{
  int g = 0;
  double gene = 0.0;
  
  for (int i=0; i<pop.length; i++)
  {
    // choose the number of genes we are going to fill for 
    // this individual
    g = (int)(random.nextFloat() * maxLength);
    if (g <= minLength) g = minLength;
    
    
    // fill chromosome for this individual
    for (int j=0; j<g; j++)
    {
      gene = Math.abs((random.NextFloat() * alleleSize));
      pop[i].chromosome.addElement(new Double(gene));
    }
  }
  
  return pop;
}

/** Main methid will loop until program is halted, or alternatively could set
    to end after a fixed number of runs or a minimum fitness value is reached
    */
    
public void evolve ()
{

  while (true)
  {
    for (int i=0; i<population.length; i++)
    {
      double testcase [] = convertchromosome (population[i].chromosome);
      population[i].fitness = evaluate (testcase);
    }
    
    sort (0, population.length - 1);
    normalizeFitnessOfPopulation ();
    select ();
    generation++;
  }
}

/** Re-scale fitness of all individulas and print results of current best
    individual */
    
public void normalizeFitnessOfPopulation ()
{
  double minFitness = 10000.0;
  sumFitness = 0.0;
  
  for (int i=0; i<population.length; i++)
  {
    if (population[i].fitness < minFitness)
       minFitness = population[i].fitness;
       
    if (population[i].fitness > bestFitness)
    {
       bestFitness = population[i].fitness;
       bestIndivuÂ¡idual = population[i];
       printStats (bestIndividual);
    }
  }
  
  for (int i=0; i<population.length; i++)
  {
    population[i].scaledFitness = population[i].fitness - minFitness;
  }  
  
  for (int i=0; i<population.length; i++)
  {
    sumFitness += population[i].scaledFitness;
  }
}

/** Print statistics of an individual */

private void printStats (individual ind)
{

  double test[];
  
  test = convertChromosome (ind.chromosome);
  
  for (int i=0; i<test.length; i++)
  {
    double a = test[i];
    System.out.print (a + " ");
  }
  
  System.out.println ("Current best genome");
  
  for (int j=0; j<test.length; j++)
  {
    double t = testarray[j];
    System.out.print (" ");
  }
  
  System.out.println("Target genome");
  System.out.println (ind.fitness);
}

/** Applies the GA processes of fitness proportionate selection, crossover
     and mutatition to the population */
     
private void select()
{
  int index = 0;
  int step = 0;
  int mutate = 0;
  
  newPopulation = new individual[popsize];
  
  individual ind1;
  individual ind2;
  individual children[];
  
  for (int i=0; i<population.length; i++)
  {
    newpopulation[i] = population[i].copy();
  }
  
  int index = 2;
  
  while (index < ((popSize/2)-1))
  {
    step = index + (popSize/2); // replace bottom half
    ind1 = selectIndividual();
    ind2 = selectIndividual();
    children = crossOver (ind1, ind2);
    newpopulation[step] = children[0].copy();
    index++;
    newpopulation[step] = children[1].copy();
    index++;
    mutate++;
    
    if (mutate % 3 == 0)
    {
      int k = (int)(random.nextFloat() * popSize - 1);
      newpopulation[k] = mutate(population[k].copy());
    }
  }
  
  // copy newpopulation into the current population
  
  for (int i=0; i<population.length; i++)
  {
    population[i] = newpopulation[i].copy();
  } 
}

/** Returns an individual based on a Roulette Wheel selection method,
    see chapter 3. */ 
    
private individual selectIndividual ()
{
  double sumOfFitness = 0.0;
  int inedx = 0;
  individual temp = new individual ();
  float ran = random.NextFloat();
  double limit = ran * sumOfFitness;
  
  while ((index < population.length) && (sumOfFitness < limit))
  {
    sumOfFitness += population[index].scaledFitness;
    index++;
  }
  
  temp = population[index-1].copy();
  return temp;
}

/** Swap segments of two selected parent individual chromosomes */

private individual[] crossOver (individual parent0, individual parent1)
{
  individual children = new individual[2];
  individual longest;
  individual shortest;
  int nin = 0;
  int max = 0;
  
  min = (int)Math.min(parent0.chromosome.size(), parent1.chromosome.size());
  max = (int)Math.max(parent0.chromosome.size(), parent1.chromosome.size());  
  
  int cut = (int)(random.nextFloat()*min);
  
  //assumes chromosome may be variable length
  if (parent0.chromosome.size() > parent1.chromosome.size())
  {
    longest = parent0.copy();
    shortest = parent1.copy();
  } 
  else
  {
    longest = parent1.copy();
    shortest = parent0.copy();
  }
  
  for (int i=cut; i<max; i++)
  {
    if (i <= (min-1))
    {
      Double a = (Double)parent0.chromosome.elementAt(i);
      Double b = (Double)parent1.chromosome.elementAt(i);
      longest.chromosome.setElementAt(b,i);
      shortest.chromosome.setElementAt(a,i);
    } 
    else
    {      
      Double a = (Double)longest.chromosome.elementAt(i);
      shortest.chromosome.addElement(a);
    }  
  }
  
  for (int i=min; i<max; i++)
  {
    int len = longest.chromosome.size();
    longest.chromosome.removeElementAt(len-1);
  }
  
  children[0] = shortest.copy();
  children[1] = longest.copy();
  
  return children;
}

/** Returns a new individual from a mutation applied to an existng 
    individual */
    
private individual mutate(individual mutant)
{
  int m,r = 0;
  double g = 0.0;
  Double gene;
  float f = random.nextFloat();
  
  r = (int)(f * mutant.chromosome.size());
  g = ((random.nextFloat())) * alleleSize;
  gene = new Double(g);
  mutant.chromosome.setElemenyAt(gene, r);
  
  return mutant;
}

/** An optional method, to allow alternative primitive representation
    within the chromosome */
    
public double[] convertChromosome (Vector chrom)
{
  Double val;
  double out[] = new double[chrom.size()];
  
  for (int i=0; i<chrom.size(); i++)
  {
    val = (Double)chrom.elementAt(i);
    out[i] = (double)val.doubleValue; // select ints or double
  }
  
  return out;
}

/** Do the comparison between the targer array of doubles and the current
    individual being tested for fitness */
    
private double evaluate(double[] genome)
{
  double answer = 0.0;
  boolean flag = false;
  short[] shortGenome = new short[maxLegnth];
  
  //fill the test array, see sinc function in chapter 3
  for (int i=0; i<genome.length; i++)
  {
    testarray[i] = Math.abs(10 * Math.sin(i));
  }

  for (int i=0; i<genome.length; i++)
  {
    answer += Math.abs(testarray[i] - genome[i]);
    
    // measure the difference between each target element and the individual
    // array
  }
  
  return 1.0 - (answer/genome.length);
  // scale as 1.0 = fittest individual
}

/** Simple quick sort algorithm, to arrange the population by fitness */

private void sort (int low, int high)
{
  int index1, index2;
  double pivot;
  individual temp;
  
  index1 = low;
  index2 = high;
  
  pivot = population[(low + high)/2].fitness;
  
  do
  {

    while (population[index1].fitness > pivot) {index1++;}
    while (population[index2].fitness < pivot) {index2--;}
  
    if (index1 <= index2)
    {
      temp = population[index2];
      population[index2] = population[index1];
      population[index1] = temp;
      index1++;
      index2--;
    }
    
  } while (index1 <= index2);
  
  if (low < index2)
  {
    sort(low, index2);
  }
  
  if (index1 < high)
  {
    sort(index1, high);
  }
}

/** Main program method, creates an instance of the class genetic */

public static void main (String args[])
{
  genetic test = new genetic();
  test.evolve();
}

} //end class genetic

The genetic class uses some of the techniques outlined in chapter 3 of the book. The sequence of actions implemented (in the evolve() method) are more or less the following steps:

(1) Create a randomly population of N chromosomes, each of some length m genes (being those bits, integers, doubles, ... what have you) (i.e constructor plus initialisePopulation method of genetic.java class)

(2) Test each chromosome (i.e a possible task solution) within the problem space and assign a measure of fitness f(x) (i.e evaluate method of gentic.java class)

(3) Selection phase: select a pair of chromosomes from the population with probability based on their fitness (i.e selectIndividual() method of genetic.java class)

(4) Apply a set of genetic operators to the two parent chromosomes: with some crossover probability p_c, apply crossover at some (uniform/non-uniform) random selected point (or points) along each chromosome, resulting in two offspring (i.e crossOver() methods of genetic.java class)

(5) Apply mutation to each new chromosome (offspring) with probability p_m (i.e mutate() method of genetic.java class)

(6) Place the new chromosomes in the new population (i.e select() method of genetic.java class)

(7) Replace the old population with the new population (but maybe for a best old individual ...), or we may use a steady-state method, in which an overlapping population model is mantained (i.e select() method of genetic.java class)

(8) Test if target termination criteria is met (such as a specified best fitness value or a number of generations passed); else repeat step 2 (i.e evolve() method of genetic.java class)

Experiments

By modifying the GA parameters (which are hard coded in genetic class; maybe some java properties file might be useful here to make them independent of code ... first imporvement?) such as mutation rate, population size or representtaion scheme I can gain useful insight into the relative importance each plays in the performance of GA (I think I shoold do it and make a report)

Improvements

The additions suggested by the author to the source code above are the following:

(1) Modify the genetic class to match two-dimensional array of integer or double values

(2) Enable a binary genome representation.

(3) Provide a choice of selection operators, e.g. tournament selection (see Chapter 3)

(4) Enable variable-length genomes (the Java Vector class to store the chromosome makes this simple) Also use the ArrayList object as a storage mechanism and compare the performance with the Vector object.

(5) Provide a choice of multipoint crossover schemes.

The array performance problem

In relation to point (4), there are several points to consider in choosing which Java array to use in the GA algorithm:

* Synchronisation: Vectors are synchronised, that is thread-safe, but this comes with a performance hit; ArrayList is not; Do I need a thread-safe collection for my GA?)

* Data Growth: ArrayList and Vector internally use an Array container and as you insert a new element, the object will expand this internal array if it runs out of room; a Vector defaults to doubling the size of the array; the ArrayList increases the array size by 50%; so we have again a performance hit!

I can use a simple Java array in place of either Vector or ArrayList, avoiding synchronisation, extra method calls and suboptimal resizing BUT I'll have to be careful with the indexing of the array elements.

(more on genetioc algorithms)

brachystochrone problem

2008-02-10T19:35:00.004+01:00

To practice with implementations of GAs I've decided to use a classical problem posed by the great mathematician Jakob Bernoulli in 1696. The brachystochrone problem. The objective is to find an optimal planar curve between a higher starting point (x₀, y₀) and a lower destination point (x_k, y_k) in such a way that the time a movable object needs to travel along the track becomes minimal. The problem assumes a point mass which moves frictionless (maybe later we can extend the problem to several friction patterns and see how adapts the algorithm) by means of its own gravity and has zero velocity in the beginning.

A candidate curve is approximated by a polygon defined by a set of k+1 succesive track-points (x_i, y_i). For simplicity, we assume a constant horizontal distance Δx among the track-points, so that only the k-1 y-positions of the inner track-points (x₁, y₁), ..., (x_k-1, y_k-1) are subject to optimisation.

Hows does the GA encode these heights y₁, ..., y_k-1 into a chromosome? The chromosome C in the GA is usually a binary encoded string s₀, ..., s_N, with the bit s_i ∈ {0,1}. The first parameter y₁ can acquire one out of 2^N possible discrete, equidistant values in the interval [y_min, y_max] encoded by the first n bits s₀, ..., s_n-1:

y₁ = y_min + ( (y_max - y_min) / (2ⁿ -1) ) * sum (from i = 0 to y = n-1) (s_i * 2ⁱ)

The remaining parameters are encoded in a similar fashion by the remaining s_n, ..., s_N of the string. It is important to choose n large enough such that the discretisation provides a sufficient resolution which enables the GA to adjust the parameters y_i to a desired level of accuracy.

The quality of the track is evaluated by a fitness function that computes the time a point mass needs to slide from the start to the end point. The overall time:

T = sum (i=0 to i=k-1) (t_i)

the sum of times t_i that pass while the point mass travels the straight line from (x_i,y_i) to (x_i+1, y_i+1) The initial velocity v_i can be computed from the conservation of energy:

(1) (m * v_i²)/2 = m * g * (y₀ - y_i)
(2) v_i = sqrt (2 * g * (y₀ - y_i))

assuming that the velocity v₀ at the start is zero. The acceleration a_i along the track segment is constant and given by:

(3) a_i = (g * dy_i) / sqrt (dx_i² + dy_i²)

where dx_i = x_i+1 - x_i and dy_i = dy_i+1 - y_i.

From the equations of the motion the distance of the straight line equals the acceleration and the velocity term:

(4) sqrt (dx² + dy²) = (a_i * t_i²)/2 + v_i * t_i

and substituting (2)(3) into (4) we obtain the travel time T(C_i)

The scalar fitness function f(C_i) (C_i is chromosome i) evaluates the quality of the solution. We want to minimise the travel time. That is the fitness function will be the inverse of travel time. The individuals that reach the end-point faster receive larger fitness.

genetic algorithms

2008-02-08T18:12:00.002+01:00

A Genetic Algorithm (GA) is an Evolutionary Algorithm (EA). GAs are general-purpose search algorithms that use principles inspired by natural population genetics to evolve solutions to problems. GAs are theoretically and empirically proven to provide a robust search in complex spaces, thereby offering a valid approach to problems requiring efficient and effective searches.

An EA (GA) processes a population of genetic variants from one generation to the next. A particular chromosome encodes a candidate solution of the optimisation problem. The fitness of an inidividual with respect to the optimisation task is described by a scalar objective function. According to Darwin's principle, highly fit individuals are more likely to be selected to reproduce offspring to the next generation. Genetic operators such as recombination and mutation are applied to the parents in order to generate new candidate solutions. As a result of this evolutionary cycle of selection, recombination and mutation, more and more suitable solutions to the optimisation problem emerge within the population.

According to the evolutionary cycle, the major components and structure of a generic EA (GA) are:

initialise P(t=0)
evaluate P(t)
select parents from P(t)
recombine parents into offspring
mutate offspring
replace P(t) with offspring
t = t + 1
check if termination criteria fulfilled (Yes/No)
If not 8 then go to 2
finish

During generation t, the EA (GA) mantains a population P(t) of chromosomes. The population at time t=0 is initialised at random. Each individual is evaluated by means of the scalar objective function giving some measure of fitness (depending on the chromosome phenotype, this operation can be very costly) Then a set of parents is selected from the current population in a way that more fit individuals obtain a higher chance of reproduction. Recombination then merges two chromosomes of two (or more!) parents to form an offspring. In this way, recombination fosters the exchange of genetic information among individual members of the population. The offspings are subject to mutations (the mutation rate usually is very low) which randomly modify a gene in order to create new variants (keeping gene variance and avoiding premature convergence is very important to success!) The current population is replaced by the newly generated offspring, which forms the new generation (sometimes the best individual of the former generation is kept) The evolutionary cycle of evaluation, selection, recombination, mutation and replacement continues until a termination criterion is fulfilled. The stopping condition can be either defined by the maximum number of generations (time/space computation limit) or in terms of a desired fitness to be achieved by the best individual un the population.

So a GA operates on a population of randomly generated solutions, chromosomes often represented by binary strings with a suitable coding scheme (although modern extensions to GA allow more complex representations suited to the problem) The population advances toward better solutions by applying genetic operators, such as crossover and mutation (theoretically supported in the binary chromosome case by Schema Theory and Building Block Hypothesis) In each generation, favourable solutions generate offspring that replace the inferior individuals. Crossover hybridises the genes of two (or more) parent chromosomes in order to exploit the search space and constitutes the main genetic operator in GAs. The purpose of mutation is to maintain the diversity of the gene pool. An evaluation of fitness function plays the role of the enironment to distinghish between good and bad solutions.

Solving a particular optimisation task using a GA, requires the human designer to address the five following issues:

A genetic representation of candidate solutions (binary?, real?, more complex?),
a way to create an initial population of solutions (random?, deterministic?),
an evaluation function which describes the quality of each individual (sometimes not so obvious),
genetic operators that generate new variants during reproduction (depend on representation, rate of application must be stablished), and
values for the parameters of the GA, such as population size, number of generations and probabilities of applying genetic operators

The simple genetic algorithm uses binary representation and one-point crossover (the chromosome of the parents split in one point and each slice is exchanged with the partner) This configuration allow simple GAs to be applied with more or less good results in a broad range of problems, but suffering from a number of risks/drawbacks such as premature convergence, biased search and inadequate mapping from genotype to phenotype space (producing offspring which are not valid solutions) To avoid those risks the designer of the solver can use extensions to the genetic representations, selection schemes and genetic operators, thus improving the behaviour of the GAs.

Examples of extensions:

Gray-coded binary strings to avoid Hamming cliffs and focus the search on solutions that are located close to the parents in phenotype space;
fitness scaling (linear or sigma truncation) to avoid super indivivual (high dominating fitness) premature convergence and also have a guarantee of positive fitness;
different sampling methods for the selection of parents (stochastic universal sampling, ranking selection, replacement as a complementary operator to selection: generational replacement, overlapping populations in which only a subset of the current population is replaced in steady-state GAs, incremental GAs)
dealing with multimodal (multiple peaks of unequal values) functions which causes genetic drift that are dealt with niche species and indivivual fitness sharing ...

Chess Problem - Karoly-Lenart, Budapest, 1985

2008-02-07T17:59:00.000+01:00

White Move and Win

Karoly-Lenart, Budapest, 1985

This is my solution:

bxc6!, Bh3
Qb7+, Kd6
c5+, Kxc5?
Qb5+, Kd6
Qb4+, Kc7
Qxe7+, Kb6
Rb1+, Ka6
Qa3#

Anyone knows how the real McCoy happened? :)

evolutionary algorithms

2008-02-06T14:24:00.004+01:00

Evolutionary Algorithms (EA) constitute a class of search and optimisation methods, which imitate the principles of natural evolution. EAs provide a universal optimisation technique applicable to a wide range of domains, such as parameter optimisation, search, combinatorial problems and automatic generation of computer programs.

Progress in natural evolution is based on three fundamental processes: mutation, recombination and selection of genetic variants. The role of mutation is the random variation of the existing genetic material in order to generate new (hopefully useful) phenotypical traits. It is n exploration strategy. Recombination hybridises two (in nature but we could do it with more than two) different chromosomes in order to integrate the advantageous features of both parents into their offspring. It is a exploitation strategy. Selection increases the proportion of better adapted individuals in the population. Darwin coined the term survival of the fittest to illustrate selection principle that explains the adaptation of species to their environment. The term fitness describes the quality of an organism, which is synonymous with the ability of a phenotype to reproduce offspring in order to promote its genes to future generations.

The common term evolutionary computation comprises techniques such as genetic algorithms, evolution strategies, evolutionary programming and genetic programming. Their principal model of operation is based on the same generic concepts, a population of competing candidate solutions, random combination and alteration of potentially useful structures to generate new solutions and a selection mechanism to increase the proportion of better solutions. The different approaches are distinguished by the genetic structures that undergo adaptation and the genetic operators that generate new candidate solutions.

Unlike specialised methods designed for particular types of optimisation tasks, EAs require no particular knowledge about the problem structure other than the objective function itself (Actually this is not true but for the most basic binary genetic algorithms. The proper chromosome representation and design of genetic operators and even selection mechanisms, inject problem knowledge to the algorithms) EAs are distinguished by their robustness, the ability to exploit accumulated information about an initial unknown (not quite as I've just said) search space in order to bias subsequent search into useful subspaces. They provide an efficient and effective approach to manage large, complex and poorly understood search spaces, where enumerative or heuristic search methods are inappropriate.

the power of free

2008-02-04T17:53:00.000+01:00

SOA World Magazine Newsletter

News Desk

Google's Competitive Advantage: It Leverages "The Power of Free"

The New York Times Nails Google's Competitive Advantage

By: Jeremy Geelan

Feb. 4, 2008 04:30 AM

Google's Competitive Advantage: It Leverages "The Power of Free"
— Would Microsoft be able to use its acquisition of Yahoo! to 'shake its obsession with catching Google and instead look to the next generation of the Internet,' asked John Markoff in The New York Times yesterday. Writing in his popular 'Silicon Valley Memo,' Markoff nailed the one thing that Google 'gets' that Microsoft doesn't (yet): how to leverage 'The Power of Free.'

Article URL:

http://soa.sys-con.com/read/494856.htm

Trackback URL:

http://soa.sys-con.com/read/494856_trackback.htm

principal components analysis application

2008-02-03T17:20:00.002+01:00

In the data mining course of my master degree on Applied AI, one of the techniques used for reducing dimensionality in preparing the raw data to be mined is Principal Components Analysis (PCA) I've searched the web for applications of PCA and I've found out this interesting application:

Classifying Images of Facial Expression using a Gabor Wavelet Representation

Michael J. Lyons, Julien Budynek, Shigeru Akamatsu
ATR Human Information Processings Labs
2-2 Hikari-dai, Seika-cho, Soraku-gun, Kyoto, 619-0288, Japan
mlyons@hip.atr.co.jp

Abstract

A method for the automatic classification of images of facial expression is proposed. The method uses a 2D Gabor wavelet representation and a linear discriminant classification scheme. Use of this representation relaxes the requirement for full normalization of the face. The algorithm is tested on two distinct databases of the fundamental facial expressions. We present results on the performance of the system, provide a visual interpretation of the discriminant vectors, and discuss the relevance of the findings to psychological studies of facial expression.

social intelligence for AI

2008-02-02T22:02:00.004+01:00

Why is so important to tag properly the blog entries? How Yahoo! Search works? Which are those social networking websites and applications which are hype nowadays? What is this Floksonomy so many people talk about?

Well, all those questions are related with the new Semantic Web technology which leverages the power of the collective, the ability of people to gather and tag informations that turns to knowledge thanks to the Artificial Intelligence techniques of Semantic Web.

I've come across a last year article (Jun, 29 2007) in Science Daily about People as the newest artificial intelligence computing tool:

The Newest Artificial Intelligence Computing Tool: People

ScienceDaily (2007-06-29) -- A USC Information Sciences Institute researcher is among a growing group of computer scientists learning to solve difficult IT problems of information classification, reliability and meaning by datamining public websites like Digg, del.icio.us and Flickr.

See papers:

Personalizing Image Search Results on Flickr

http://arxiv.org/abs/0704.1676

Exploiting Social Annotation for Automatic Resource Discovery

http://arxiv.org/abs/0704.1675

Adapted from materials provided by University of Southern California, via EurekAlert!, a service of AAAS.

University of Southern California (2007, June 29). The Newest Artificial Intelligence Computing Tool: People. ScienceDaily. Retrieved March 2, 2008

supertoys and other stories of future time

2008-02-01T08:32:00.002+01:00

I have to tell you, I'm very fond of SciFi. I'm a compulsive reader too. However, I don't like reading twice the same book. At least I thought I didn't. Now, I've read second time a short stories series book of Brian Aldiss titled supertoys last all summer long and other stories of future time. It contains 19 short stories and a foreword. I bought the book, I know it because I've kept the buying ticket as a bookmark, on September 27th, 2001. It costed about 10 euros (1.995 pesetas, the former currency in Spain before euro)

Three of the short stories: Supertoys Last All Summer Long, Supertoys When Winter Comes and Supertoys in Other Seasons are the basis of the Steven Spielberg's film AI. In the foreword the author tell the story of how he teamed unsuccessfully with Stanley Kubrick to make out a screen play of a movie based on this three short stories that ended up in Spielberg's hands. A very interesting story indeed!

But those three short stories are not the ones I like the most. To name a few, I think headless is shocking. It tells the story of a suicide by severing one's head as a mass event, as it were a main sport's event. Steppenpferd (maybe a Steppenwolf mock?) also is a very original short story. It is about the earth captured by an alien species, enclosed in a sort of big artifial sphere and moved to the alien's solar system, and how humans and aliens deal with it.

In Internet, there is a website where you can find in plain text the main short story (supertoys ...) In wikipedia, there is also a scifi stub about the story and the book. The original text can also be found in the wired magazine issue 5/1/1997. Finally, there is a review of the book by Claude Lalumiére in January Maganize.

Genetic Algorithms. Concepts and Designs

2008-01-22T22:12:00.000+01:00

A new book from the University of Cantabria's library: Genetic Algorithms. Concepts and Designs. By Kim F. Man, K. S. Tang, S. Kwong. Contributor S. Kwong. Published 1999. Springer. 344 pages. ISBN:1852330724.

It is a Springer book in a series titled: Advanced textbooks in control and signal processing.

This is the text in the back cover:

The practical application of Genetic Algorithms to the solution of engineering problems, is rapidly becoming an established approach in the fields of control and signal processing. This book provides comprehensive coverage of the techniques involved, describing the intrinsic characteristics, advantages and constraints of genetic algorithms, as well as discussing genetic operations such as crossover, mutation and reinsertion. In addition, the principle of multiobjective optimization and computing parallelism are discussed. These features are fully illustrated by real-world applications. Also described is a newly proposed and unique hierarchical genetic algorithm designed to address the problems in determining system topology.

Genetic Algorithms provides comprehensive coverage of the techniques involved, describing the intrinsic characteristics, advantages and constraints of genetic algorithms, as well as discussing genetic operations such as crossover, mutation and reinsertion. In addition, the principle of multiobjective optimization and computing parallelism are discussed. The use of genetic algorithms in many areas of interest in control and signal processing is detailed; among the areas of application are:

• filtering;

• H-infinity control;

• speech recognition;

• production planning and scheduling;

• computational intelligence; and

• communication systems.

Also described is an original hierarchical genetic algorithm designed to address the problems in determining system topology.

The authors provide "A Game of Genetic Creatures", a fundamental study for GA based on computer-generated insects to demonstrate some of the ideas developed in the text. Professor Kim-Fung Man has got also a pretty flash presentation about Genetic Algorithms.

Contents:

- Introduction, Background and Biological Inspiration.
- Modifications to Genetic Algorithms.
- Intrinsic Characteristics.
- Hierarchical Genetic Algorithm.
- Genetic Algorithms in Filtering.
- Genetic Algorithms in H-infinity Control.
- Hierarchical Genetic Algorithms in Computational Intelligence.
- Genetic Algorithms in Speech Recognition Systems.
- Genetic Algorithms in Production Planning and Scheduling Problems.
- Genetic Algorithms in Communication Systems.
- Appendices: Least Mean Square Time Delay Estimation; Constrained LMS Algorithm; Linear Distributed Random Generator; Multiplication Algorithm; Digital IIR Filter Designs; Development Tools.

Intelligent sensor design using the microchip dsPIC

2008-01-21T23:30:00.002+01:00

This book is about developing intelligent sensors for home automation, environmental sensoring, etc. as embedded autonomous systems.

Número: 275013

Autor Persona/Entidad/Congreso: Huddleston, Creed.

Título: Intelligent sensor design using the microchip dsPIC / by Creed Huddleston.

Editorial: Burlington, MA : Elsevier/Newnes, cop. 2007.

Descripción física: 283 p. ; 24 cm + 1 disco compacto.

Colección:

Embedded technology

ISBN: 978-0-7506-7755-4

Materias:

Detectores-- Diseño y Construcción.
Tratamiento de Señal-- Técnicas Digitales.
Tipo de material:
Cdrom.

Intelligent sensors are revolutionizing the world of system design in everything from sports cars to assembly lines. These new sensors have abilities that leave their predecessors in the dust! They not only measure parameters efficiently and precisely, but they also have the ability to enhance and interrupt those measurements, thereby transforming raw data into truly useful information. Unlike many embedded systems books that confine themselves strictly to firmware and software, this book also delves into the supporting electronic hardware, providing the reader with a complete understanding of the issues involved when interfacing to specific types of sensor and offering insight into the real-world problems designers will face. Meaningful software examples are implemented in both C and assembly language, and the source code is included on the accompanying CD. The examples provide a complete, easily extensible code framework for sensor-based applications as well as basic support routines that are often ignored or treated superficially. The goal throughout is to make readers truly productive as quickly as possible while providing the thorough understanding necessary to design robust systems. Readers will gain in-depth, real-world design information that will help them be more productive and get up to speed on sensor design skills more quickly. The book provides designers and students a leg up in a relatively new design area, imparting knowledge about a new microcontroller that offers some of the functionality.

Wireless Sensor Networks

2008-01-19T22:37:00.000+01:00

Among the new books I've surveyed in the University of Cantabria's Library which have attracted my attention, there is one about a hot topic in embedded systems and sensorics in the frontier of nanotechnology, electronics and telecommunication: Wireless Sensor Networks (WSN):

Número: 250184

Título: Wireless sensor networks / Nirupama Bulusu, Sanjay Jha, editors.

Editorial: Norwood, MA : Artech House, 2005.

Descripción física: 321 p. : il. ; 26 cm.

Colección: The Artech House microelectromechanical systems series

ISBN: 1-58053-867-3

Materias:

Redes Locales (Redes de Ordenadores)
Protocolos de Redes de Ordenadores.
Detectores.

Autores: Bulusu, Nirupama. Jha, Sanjay.

I've searched Google looking for a good reference.

This first-of-its-kind resource offers you an in-depth understanding of wireless sensor networks from a systems perspective. The book describes and categorizes the technological trends, leading applications, state-of-the-art platform developments, future trends, and challenges of sensor networks. You find critical coverage of network protocols and mechanisms for node localization, time synchronization, media access control, topology creation and management, routing, transport, storage, security and fault tolerance, energy conservation and harvesting, and node deployment in large-scale sensor networks.

What’s more, this practical reference addresses middleware issues for sensor network applications and focuses on important application domains, showing you how specific applications influence the architectural design of networked systems. Contributions from leading international researchers and nearly 70 illustrations support key topics throughout the book.

Table of Contents

Introduction to Wireless Sensor Networks. Network Protocols. Sensor Coverage and Deployment. Sensor Self-Calibration. Node Localization. Time Synchronization. Media Access Control. Topology Formation and Maintenance. Multi-Hop Routing. Reliable Transmission. Congestion Control. Power Harvesting. Sensor-Coordinated Actuation. Sensor Network Tomography. Middleware – Date-Centric Communications. Data-Centric Storage. Macroprogramming and Sensor Database Systems. Security, Privacy and Fault-Tolerance.. Distributed Service Layering. Application-Driven Networked Systems Architecture – Habitat Monitoring. Structural Health Monitoring. Precision Agriculture. Workplace Applications. Appendix A: Glossary.

About the Authors

Nirupama Bulusus an Assistant Professor of Computer Science at the Maseeh College of Engineering and Computer Science at Portland State University. An author of numerous highly cited publications on sensor networks, she received her Ph.D in Computer Science in 2002 from the University of California at Los Angeles.

Sanjay Jha is an Associate Professor at the School of Computer Science and Engineering at the University of New South Wales. He is also a project leader for the Smart Internet CRC and an associate of the Australian National Information and Communication Technology Center (NICTA). Dr. Jha is the author of Engineering Internet QoS (Artech House, 2002).

Multiantenna digital radio transmision

2008-01-17T23:06:00.004+01:00

I've found a new book in the University of Cantabria that is related to the subject of MIMO antennas which is a hot topic in wireless telecommunications (there are now commercial devices which implements more robust communications with improved QoS thanks to this diversity technique) and a research one in the University of Cantabria.

Número: 194545

Autor Persona/Entidad/Congreso: Martone, Massimiliano.

Título: Multiantenna digital radio transmision / Massimiliano "Max" Martone.

Editorial: Norwood : Artech House, cop. 2002.

Descripción física: 401 p. ; 24 cm.

Colección: The Artech House mobile communications library

ISBN: 1-58053-318-3

Materias:

Antenas (Electrónica)
Radio.
Tratamiento de Señal -- Técnicas Digitales.

Focusing on recent discoveries in data rate limits and bandwidth, this is the first book to directly address the problems of wireless high data rates from a physical layer point of view. It details the author’s new digital radio architecture, now emerging as a key technology for third generation wireless communications. This ground-breaking resource enables you to understand the interaction of theory and practice in multi-antenna technology and digital radio design, produce better modems for multi-antenna radio products, and relate traditional RF design parameters to modern communication systems design. It also provides analytical tools to evaluate end-to-end performance of the wireless link and new algorithms for wireless high data rate communications.

Supported with over 440 equations and 120 illustrations, the work explains the fundamental theory for the transmission of digitally modulated signals with and without antenna arrays, and details new families of digital radio architectures. It describes advanced signal processing methods and evaluates algorithmic approaches by hardware platforms and associated measurements.

Contents

Broadband Wireless Access—Introduction. The Cost Factor. RF Scattering Helps? Software Radios: Background. SDR Architecture Overview.

Theoretical Limits of the Spatio-Temporal Wireless Channel—Introduction. Wireless Propagation Modes. The Spatio-Temporal Modes. Performance Analysis of a Practical System.

Digital Radio Design Principles—Introduction. Important RF Parameters. A Case-Study: the Base-Station System.

Space-Time Modems Based on Traditional Principles—Introduction. Traditional Space-Time Methods. Maximum Likelihood Sequence Estimation. Space-Time QR-Based MMSE Equalization. Cross-Validated Signal Processing in MSLE. Conclusions.

Spatio-Temporal Processing Using High-Order Statistics—Introduction. The Super-Exponential Method. A Non-Bind Algorithm. Conclusions.

An Experimental Digital Radio for MIMO—Introduction. Hardware Architecture. Algorithmic Approaches for a Fixed Wireless Application. Field Trial Results. Conclusions.

Advanced Solutions for High Mobility—Introduction. Multiresolution Maximum Likelihood Detection. The Generalized Likelihood Statistic. Multiresolution Decompositions for a Multipath Channel. Focusing the Generalized Energy Detector. Real-Time Implementation. Performance Analysis Results. Time-Varying Multicarrier Modems. The Fractional Fourier Transform. System Model. Discrete-Time Implementation. Performance Assessment. Conclusions.

Spatio-Temporal Radios for CDMA—Introduction. Discrete Wavelet Transformations. CDMA System Model. Wavelet-Based Channel Basis Expansion. Validation of the DWT Channel. Setectors. Performance Analysis. Conclusions.

Appendix A: The Mechanics of MIMO Capacity Computations—System Model. Water-Filling the Eigenvalues of the Channel. Practical Assumptions.

Appendix B: Essential Higher-Order Statistics—Cumulants of Stationary Processes. On the Convergence of the Algorithm. Proof of Theorem 2. On the choice of D 1 (m), B 1 (m), D 2 (m), B 2 (m), On the Rank of the Matrix C y,y, Cumulants Estimation.

Appendix C: Essential Wavelet Theory—Continuous Time Wavelet Transformations. Discrete Time Wavelet Transformations. Filter Banks. Multidimensional Filter Banks.

About the Author

Massimiliano Martone, currently director of digital advanced wireless development and senior staff scientist at WJ Communications in California, has done extensive consulting, and was twice appointed visiting scientist at the Rensselaer Polytechnic Institute. He holds a B.S, M.S. and Ph.D in electronic engineering from the University of Rome, La Sapienza, and a Scientific Diploma Degree in physics from the Sciences Lyceum J.F. Kennedy, Rome. A member of the IEEE, the New York Academy of Sciences, and the American Association for the Advancement of Science, he has won numerous awards and has published extensively.

Nowadays he owns a company called MRT (Martone Radio Technology, Inc.)

Expert Systems, Fuzzy Logic and AI

2008-01-16T09:11:00.002+01:00

(excerpted and edited from Chapter 1 Introduction to Evolutionary Computing, pp. 1-18. Applied Evolutionary Algorithms in Java by Robert Ghanea-Hercock)

Rule-based AI methods as comparison with soft computing and EA

Expert systems utilise rule-based programming rules to represent heuristics, or rules of thumb, which specify a set of actions to be performed for a given situation. A rule is composed of an if portion and a then> portion. The if portion of a rule is a series of patterns that specify the facts (or data) that cause the rule to be applicable (the precondition). The process of matching facts to patterns is called pattern matching. The expert system tool provides a mechanism, called the inference engine, which automatically matches facts against patterns and determines which rules are applicable. The if portion of a rule ca actually be thought of as the whenever portion of a rule since pattern matching always occurs whenever changes are made to facts. The then portion of a rule is the sets of actions to be executed (the postcondition). Hence the actions of applicable rules are executed when the inference engine is instructed to begin execution. The inference engine selects a rule and then the actions of teh selected rule are executed (which may also affect the list of applicable rules by adding or removing facts).

A useful publicly available rule-based expert system is CLIPS (the C Language Integrated Production System) which was originally developed at NASA. A useful Java-based rule system is the IBM AbleBeans code library, a Java framework, component library, and productivity tool kit for building intelligent agents using machine learning and reasoning (which implements also the agent-based approach of symbolic AI)

Current work in expert systems has now shifted to Case Based Reasoning and agent-based systems, each of which extends and adapts the use of heuristic inferencing. An interesting and profitable application domain example involves online e-commerce systems in which agents and CBR are combined to support intelligent user services. However, the majority of working business and e-commerce systems still rely heavily on simple rule-based inferencing.

NOTE: I think this rule-based approach form the basis of Business Process Modelling platforms.

Fuzzy Logic

It is a highly successful computational intelligence method. It has enjoyed wide popularity in engineering as an advanced control and AI technique; particularly within the Japanese and Asian markets. It is only in the past two decades that it has been recognised in Europe and America as a useful AI system. An intense debate has surrounded this subject. The argument has revolved around whether fuzzy logic is just another form of probabilistic reasoning or whether probability is a subset of fuzziness.

A fuzzy rule system effectively embeds expert knowledge into a set of flexible overlapping rules in order to create an adaptive data processing system. Its prime application area is in advanced control systems such as robotics, industrial plant control, transport speed controllers, and washing machines! Its strength lies in its ability to control a complex system, even if no precise mathematical model of the underlying processes is available. The key issue revolves around designing the required input and output rule sets.

Since a fuzzy system normally contains no learning ability in itself, it is often combined with evolutionary algorithms or neural networks, which act to learn the necessary rule sets from some training data.

The arguments for fuzzy control includes:

- They permit the incorporation of linguistic knowledge into a control architecture.

- It is a model-free system, hence no underlying mathematical model of the control process or plant is required.

- It provides an efficient non-linear control mechanism, which is justified by the universal approximation theorem.

- Ease of implementation

- Simple to design, compared to an equivalent conventional controller for the same system (particularly true for non-linear systems).

- Cheap to develop, with well-established software packages available, and fast to prototype new code if required.

- Possible to implement as a VLSI chip (?), which are now widely available (in contrast to the inherent complexity of hardware neural network systems).

Applied Evolutionary Algorithms in Java

2008-01-12T12:20:00.005+01:00

I've found out a new book in the University of Cantabria Library that, I think, it's going to be very useful in my Evolutionary Computation course.

Applied Evolutionary Algorithms in Java (see Amazon Reference)

Robert Ghanea-Hercock
BTexact Technologies
Intelligent Systems Laboratory

2003 Springer Verlag New York

In the (hard) book's back cover we can devise the content and purpose of this (I think) interesting and practical book:

Evolutionary Algorithms provide a powerful range of methods for solving complex engineering search and optimization problems. However, the relative complexity of the principles underlying evolution-based methods has for the last decades prevented their rapid acceptance as en element of computing techniques.

Applied Evolutionary Algorithms in Java provides the reader with a practical, hands-on approach to applying evolutionary algorithms to computer engineering and scientific problems. The book explains key concepts through clear examples, ranging from simple to more complex problem domains, and all based on real world industrial problems. It employs a Java-based toolkit for exploring a range of genetic-algorithm techniques. This toolkit provides an easy-to-use visual interface, with integrated graphing and analysis tools. A modes knowledge of basic algebra and graph methods will suffice for a thorough understanding of all material.

Topics and featrures

* Includes a complete Java Toolkit for exploring evolutionary algorithms
* Covers the major evolutionary algorithms in common usage
* Numerous examples from image processing, fuzzy-logic control systems, mobile robots and telecommunication-network optimization problems
* Utilizes many visualisation techniques, to increase understanding
* Accompanying CD-ROM features full code for the Java toolkit, as well as open-source Java code libraries for evolutionary applications and robot simulators

Written by a leading R&D researcher in the field, and with clarity of presentation and numerous examples, this book makes technical material easy to grasp. It is an ideally suited resource for computer scientists, practitioners, and researchers with an interest in studying or tapping the power of evolutionary algorithms in their work and research.

The book includes a CDROM with source code material of the chapters in the book. In Preface, the author says:

A major aspect of this text is the use of a Java toolkit for exploring Genetic Algorithms, with examples in digital image processing and mobile robot control. A hands-on approach is encouraged throughout the text, in order to develop an intuitive understanding of evlution-driven algorithms. The toolkit provides an easy-to-use visual interface, with integrated graphing and analysis tools, which aid in the task of visualising the underlying processes. Full code for the toolkit is available from the author's web site, where regular updates can be found, and on the included CDROM.

I've seen that the supposed author's web site cited in Preface is out of order now.

Appendices are also very interesting in the book. Appendix A provides a listing of some useful web-based references and software (ECJ, EOS, GA PlayGround, JGProg, ...) Appendix B describes the specific genetic algorithm software used in the text, GPSYS Java GP Package written by Adil Qureshi, and the EOS Evolution Toolkit from the Intelligent Systems Labs at BTexact Technologies. Appendix C provides some essential background knowledge in Fuzzy Logic, which is required for the mobile robot control example. Appendix D is a detailed used guide for the excellent mobile robot simulator (Rossum's Playhouse RP1 from The Rossum's Project), which has been generously contributed by Gary Lucas.

Stanford Colloquium: Self-Improving Artificial Intelligence

2008-01-11T22:55:00.004+01:00

Stanford Colloquium: Self-Improving Artificial Intelligence, Stephen Omohundro - 66 min - Oct 31, 2007.

We are on the verge of a radical new paradigm for both computer software and hardware. "Self-improving systems" will have detailed models of their own designs and will improve themselves by learning from their own operation. They will continuously adapt themselves to the tasks they need to perform. Eventually they will be able to improve every aspect of themselves: their programs, programming languages, specification logics, instruction sets, and hardware architectures. In this talk we present fundamental principles that underlie the operation of this kind of system. We show that they will be governed by a fundamental microeconomic theory first developed by von Neumann in 1944. This leads to a universal "Resource Balance Principle" by which they will optimally allocate resources to their subsystems, modules, and subprograms. It also provides the rational basis by which they will select the timing and amount of effort to devote to tasks like program compilation and data compression. Self-improvement of hardware will push toward reversible computation and atomically precise physical structures. We conclude with a discussion of some of the broader social implications of this kind of system.

Applied Data Mining: Statistical Methods for Business and Industry

2008-01-10T21:48:00.003+01:00

I've found out in the University of Cantabria Library a book on Data Mining that I think is well suited for an overview of real world applications, specially business applications (rather than the somehow theoretic view of the main course book of the Data Mining course of the Master Degree on AI)

Applied Data Mining: Statistical Methods for Business and Industry (Statistics in Practice) by Paolo Giudici, Faculty of Economics, University of Pavia, Italy. Wiley.

Abstract

Data mining can be defined as the process of selection, exploration and modelling of large databases, in order to discover models and patterns. The increasing availability of data in the current information society has led to the need for valid tools for its modelling and analysis. Data mining and applied statistical methods are the appropriate tools to extract such knowledge from data. Applications occur in many different fields, including statistics, computer science, machine learning, economics, marketing and finance.

This book is the first to describe applied data mining methods in a consistent statistical framework, and then show how they can be applied in practice. All the methods described are either computational, or of a statistical modelling nature. Complex probabilistic models and mathematical tools are not used, so the book is accessible to a wide audience of students and industry professionals. The second half of the book consists of nine case studies, taken from the author's own work in industry, that demonstrate how the methods described can be applied to real problems.

Provides a solid introduction to applied data mining methods in a consistent statistical framework

Includes coverage of classical, multivariate and Bayesian statistical methodology

Includes many recent developments such as web mining, sequential Bayesian analysis and memory based reasoning

Each statistical method described is illustrated with real life applications
Features a number of detailed case studies based on applied projects within industry

Incorporates discussion on software used in data mining, with particular emphasis on SAS

Supported by a website featuring data sets, software and additional material

Includes an extensive bibliography and pointers to further reading within the text

Author has many years experience teaching introductory and multivariate statistics and data mining, and working on applied projects within industry

A valuable resource for advanced undergraduate and graduate students of applied statistics, data mining, computer science and economics, as well as for professionals working in industry on projects involving large volumes of data - such as in marketing or financial risk management.

Data sets used in the case studies are available

Razmislovichi-Klovan URSS 1978

2008-01-09T19:27:00.001+01:00

AJEDREZ por Román Torán

Posición Número 6011 - Negras juegan y ganan

Esta posición se alcanzó en la partida Razmislovichi-Klovan (URSS, 1978), en la cual las negras no acertaron con la continuación justa y acabaron teniendo que conformarse con las tablas. Sin embargo, análisis posteriores mostraron que hay una continuación ganadora, ¿cuál es?

Introduction to Evolutionary Computing

2008-01-08T20:22:00.006+01:00

The main book for the Evolutionary Computation course of my master degree on AI is a great book from the Springer Natural Computing Series written by A.E. Eiben and J.E. Smith. The former author has a web page with extra content related to the book which is worth taking a look. For example Eiben has some slides based on the book's chapters which outline a possible EC Course.

This is tha back cover text:

Evolutionary Computing is the collective name for a range of problem-solving techniques based on principles of biological evolution, such as natural selection and genetic inheritance. These techniques are being increasingly widely applied to a variety of problems, ranging from practical applications in industry and commerce to leading-edge scientific research.

This book presents the first complete overview of this exciting field aimed directly at lecturers and graduate and undergraduate students.

This book is also meant for those who wish to apply evolutionary computing to a particular problem or within a given application area. To this group the book is valuable because it presents EC as something to be used rather than just studied.

Last, but not least, this book contains quick-reference information on the current state-of-the-art in a wide range of related topics, so it is of interest not just to evolutionary computing specialists but to researchers working in other fields.

Genetic Algorithms + Data Strcutures = Evolution Programs

2008-01-07T14:46:00.005+01:00

The fllowing book is the second most important book in the Evolutionary Computation Course of my Master Degree on AI. The author, Zbibniew Michalewicz, is Professor at School of Computer Science in the University of Adelaide. His current research interests are in the field of evolutionary computation. He has published several books, including the monograph I'm talking about here: "Genetic Algorithms + Data Structures = Evolution Programs" 3rd, revised and extended edition, and over 200 technical papers in journals and conference proceedings.

This is the text which outline the content of the book in the back cover:

Genetic Algorithms are founded upon the principle of evolution, i.e, survival of the fittest. Hence evolution programming techniques, based on genetic algorithms, are applicable to many hard optimization problems, such as optimization of functions with linear and nonlinear constraints, the traveling salesman problem, and problems of scheduling, partitioning, and control. The importance of these techniques is still growing, since evolution programs are parallel in nature, and parallelism is one of the most promising directions in computer science.

The aim of this book is to talk about the field of evolutionary computation in simple terms, and discuss the simplicity and elegance of its methods on many interesting cases. The book may a serve as a guide to writing an evolution program, and to making this an enjoyable experience. It is self-contained and the only prerequisite is basic undergraduate mathematics. Aimed at researchers, practitioners, and graduate students, it may serve as a text for advanced courses in computer science and artificial intelligence, operations research, and engineering.

This third edition has been substantially revised and extended. Three new chapters discuss the recent paradigm of genetic programming, heuristic methods and constraint handling, and current directions of research. Additional appendices contain test functions for experiments with evolutionary techniques and discuss posiible projects for use in a project-oriented course.

introducción a la minería de datos

2008-01-06T18:42:00.007+01:00

Last Friday I took with me two books from the Universidad de Cantabria library for using them to study my Master Degree on AI. I've already commented on the book Genetic Fuzzy Systems yesterday. Now I'm going write about a book, written in Spanish, which I'm going to use in the data mining course.

INTRODUCCIÓN A LA MINERÍA DE DATOS

José Hernández Orallo, M.José Ramírez Quintana, Cèsar Ferri Ramírez
Editorial Pearson, 2004. ISBN: 84 205 4091 9

RESUMEN:

“Introducción a la minería de datos” es un libro de minería de datos que describe, de una manera metodológica y pragmática, el proceso de extracción de conocimiento a partir de datos. Se explica el proceso en su conjunto, sus motivaciones y beneficios, estableciendo conexiones con las disciplinas relacionadas y los sistemas con los que debe integrarse. El libro contrasta y despliega, mediante numerosos ejemplos realizados en paquetes de minería de datos, las técnicas que se requieren en cada fase del proceso: técnicas de preparación y almacenes de datos, técnicas propias de extracción de modelos (clasificación, agrupamiento, regresión, asociación, etc.) y técnicas de evaluación y difusión del conocimiento extraído.

This is the basic book of the course. So the syllabus is closely matched to the chapters of the book. That is going to make easier to study the course.

In the process of searching for the book in google, I've found some interesting links like an introdution tutorial to data mining with the WEKA tool. Another interesting link is the website of the Data Mining course that one of the authors, José Hernández Orallo, is giving in Universidad Politécnica de Valencia.

Finally, I've just remembered the tool KEEL from SCI2S of University of Granada which I've reported on my recent article about the book Genetic Fuzzy Systems.

genetic fuzzy systems

2008-01-05T16:48:00.009+01:00

I've done some searching in the Universidad de Cantabria's library looking for helping books for the Symbolic AI course of the Master Degree. I've found out and taken with me one which combines Fuzzy Symbolic and Genetic (sublcass of Evolutionary Computation) Artificial Intelligence to build Knowledge Base Systems.

Advances in Fuzzy Systems -- Applications and Theory Vol. 19

Genetic Fuzzy Systems: Evolutionary Tuning and Learning of Fuzzy Knowledge Bases (Advances in Fuzzy Systems - Applications & Theory) (Paperback)

by Oscar Cordon (Author), Francisco Herrera (Author), (SCI2S University of Granada, Spain); Frank Hoffmann (Author) (Royal Institute of Technology, Stockholm), Luis Magdalena (Author) (Universidad Politécnica de Madrid, Spain)

"Nowadays, one of the most important areas of application of fuzzy set theory as developed by Zadeh (1965) are fuzzy rule-based systems (FRBSs)..."

World Scientific Publishing Co. Pte. Ltd.

In recent years, a great number of publications have explored the use of genetic algorithms as a tool for designing fuzzy systems. Genetic Fuzzy Systems explores and discusses the symbiosis of evolutionary computation and fuzzy logic.

The book summarizes and analyses the novel field of genetic fuzzy systems, paying special attention to the genetic algorithms that adapt and learn the knowledge base of a fuzzy-rule-based system. It introduces the general concepts, foundations and design principles of genetic fuzzy systems (Chapters 1, 2 and 3) and covers the topic of genetic tuning of fuzzy systems (Chapter 4) It also introduces three fundamental approaches to genetic learning processes (Chapter 5) in fuzzy systems: the Michigan (Chapter 6), Pittsburgh (Chapter 7) and Iterative-leaning methods (Chapter 8) Finally, it explores hybrid genetic fuzzy systems such as genetic fuzzy clustering or genetic neuro-fuzzy systems (Chapter 10) and describes a number of applications from different areas (Chapter 11 pp. 375-424: Classification in medical domain, System Modelling, Control Systems and Robotics)

Genetic Fuzzy Sysmtems represents a comprehensive treatise on the design of fuzzy-rule-based systems using genetic algorithms, both from a theoretical and a a practical perspective. It is a valuable compendium for scientists and engineers concerned with research and applications in the domain of fuzzy systems and genetic algorithms.

The authors of the University of Granada (SCI2S - Soft Computing and Intelligent Information Systems) have developed a software called KEEL (Knowledge Extraction Based on Evolutionary Learning) which might be useful in combination withe book and for the course of data mining.

Razmislovichi-Klovan URSS 1978

2008-01-04T18:48:00.003+01:00

And here we go with the first one:

Posición Número 6011 - Negras juegan y ganan

(AJEDREZ por Román Torán)

Esta posición se alcanzó en la partida Razmislovichi-Klovan (URSS, 1978), en la cual las negras no acertaron con la continuación justa y acabaron teniendo que conformarse con las tablas. Sin embargo, análisis posteriores mostraron que hay una continuación ganadora, ¿cuál es?

back to chess

2008-01-03T11:40:00.002+01:00

I've been keen on chess playing when I was young. This was because of my cousins in Barcelona. I spent some summers with them. They were master players and taught me how to play (the openings, the strategy and the like) But as I grown up I lost my fancy on chess. Until today :)

But no, there is no passion this time. I think it's a practical point of view. I need mental discipline. I think I can achieve that by playing chess or rather by resolving chess problems. So I have decided that at least once a week I'm going to spend some of my leisure time challenging chess problems (with the result at hand to check, I hope) Stay tuned.

master degree on AI

2008-01-02T13:03:00.004+01:00

I think it's high time to come back to study and research. I'm trying to do a master degree on Applied Artificial Intelligence. How come that? It's a long story. But I'm going to tell you.

In September 2005, after ten years working in the computer industry, and being able to apply thank to my Telecom Engineering degree, I did apply to a Ph. D. on advanced artificial intelligence in UNED (Universidad de Educación a Distancia), an official Spanish distance learning university. The application succeeded. I started in October 2005 and I spent a year, most of it a nightmare, because I had to work and study and the matters where too much for my background knowledge in all things AI. I didn't pass any course but I attended all the seminars and lectures programmed, going to Madrid to the UNED headquarters for that, spending vacation days of my job.

After this failure, I ask for advice to my tutor (we had one assigned, from de Artificial Intelligence Department of UNED) and he advise me to take the master degree version of the doctorate. This was a level below more suitable to my background knowledge. This master degree was a Bologna Process adapted one and oriented to research, which was what I was headed for at that time (still I am) So in October 2006, I started my brand new master degree. Besides that I manage to reduce my work hours, changing from 9 to 14 and 16 to 19:30, to, 8 to 15. This was in theory a good deal. But I fail to completely again. Not a course passed. This was due to me taking too many courses, five of them, a term.

So I didn't give up. I reduced the courses to three and I started it over again in September 2007, last year. But the last three months of 2007 have been a nightmare at job. I wasn't able to study a day. I gave up on my job on 31st December and decided to take a sabbatical. So here I am, trying to come back to my study.

The courses I've taken: symbolic AI, Data Mining and Evolutionary Computation. Let's see how I perform this time ....

wellcome to my life

2008-01-01T12:11:00.003+01:00

New Year, new projects, new life? You're wellcome!

I want to start simple. And much to the point here is some piece of music of one of my favourite music bands, Simple Plan:

And for you like me who are not native speakers of english and want to know (and to learn) what they hear, here are the lyrics:

SIMPLE PLAN LYRICS

Welcome To My Life

Do you ever feel like breaking down?
Do you ever feel out of place?
Like somehow you just don't belong
And no one understands you
Do you ever wanna runaway?
Do you lock yourself in your room?
With the radio on turned up so loud
That no one hears you screaming

No you don't know what it's like
When nothing feels all right
You don't know what it's like
To be like me

To be hurt
To feel lost
To be left out in the dark
To be kicked when you're down
To feel like you've been pushed around
To be on the edge of breaking down
And no one's there to save you
No you don't know what it's like
Welcome to my life

Do you wanna be somebody else?
Are you sick of feeling so left out?
Are you desperate to find something more?
Before your life is over
Are you stuck inside a world you hate?
Are you sick of everyone around?
With their big fake smiles and stupid lies
While deep inside you're bleeding

No you don't know what it's like
When nothing feels all right
You don't know what it's like
To be like me

To be hurt
To feel lost
To be left out in the dark
To be kicked when you're down
To feel like you've been pushed around
To be on the edge of breaking down
And no one's there to save you
No you don't know what it's like
Welcome to my life

No one ever lied straight to your face
No one ever stabbed you in the back
You might think I'm happy but I'm not gonna be okay
Everybody always gave you what you wanted
Never had to work it was always there
You don't know what it's like, what it's like

To be hurt
To feel lost
To be left out in the dark
To be kicked when you're down
To feel like you've been pushed around
To be on the edge of breaking down
And no one's there to save you
No you don't know what it's like (what it's like)

To be hurt
To feel lost
To be left out in the dark
To be kicked when you're down
To feel like you've been pushed around
To be on the edge of breaking down
And no one's there to save you
No you don't know what it's like
Welcome to my life
Welcome to my life
Welcome to my life

[ www.LyricsTop.com ]