From Standard to Second Order Swarm Intelligence Phase-Space Maps

ECCS11 From Standard to Second Order Swarm Intelligence Phase-Space Maps David Rodrigues Jorge Louçã Vitorino Ramos

David M.S. Rodrigues, Jorge Louçã, Vitorino Ramos, “From Standard to Second Order Swarm Intelligence Phase-space maps“, in European Conference on Complex Systems, ECCS’11, Vienna, Austria, Sept. 12-16 2011.

Abstract: Standard Stigmergic approaches to Swarm Intelligence encompasses the use of a set of stochastic cooperating ant-like agents to find optimal solutions, using self-organized Stigmergy as an indirect form of communication mediated by a singular artificial pheromone. Agents deposit pheromone-signs on the edges of the problem-related graph to give rise to a family of successful algorithmic approaches entitled Ant Systems (AS), Ant Colony Systems (ACS), among others. These mainly rely on positive feedbacks, to search for an optimal solution in a large combinatorial space. The present work shows how, using two different sets of pheromones, a second-order coevolved compromise between positive and negative feedbacks achieves better results that single positive feedback systems. This follows the route of very recent biological findings showing that forager ants, while laying attractive trail pheromones to guide nest mates to food, also gained foraging effectiveness by the use of pheromones that repelled foragers from unrewarding routes. The algorithm presented here takes inspiration from this biological observation.

The new algorithm was exhaustively tested on a series of well-known benchmarks over hard NP-complete Combinatorial Optimization Problems (COP’s), running on symmetrical Traveling Salesman Problems (TSP). Different network topologies and stress tests were conducted over low-size TSP’s (eil51.tsp; eil78.tsp; kroA100.tsp), medium-size (d198.tsp; lin318.tsp; pcb442.tsp; att532.tsp; rat783.tsp) as well as large sized ones (fl1577.tsp; d2103.tsp) [numbers here referring to the number of nodes in the network]. We show that the new co-evolved stigmergic algorithm compared favorably against the benchmark. The algorithm was able to equal or majorly improve every instance of those standard algorithms, not only in the realm of the Swarm Intelligent AS, ACS approach, as in other computational paradigms like Genetic Algorithms (GA), Evolutionary Programming (EP), as well as SOM (Self-Organizing Maps) and SA (Simulated Annealing). In order to deeply understand how a second co-evolved pheromone was useful to track the collective system into such results, a refined phase-space map was produced mapping the pheromones ratio between a pure Ant Colony System (where no negative feedback besides pheromone evaporation is present) and the present second-order approach. The evaporation rate between different pheromones was also studied and its influence in the outcomes of the algorithm is shown. A final discussion on the phase-map is included. This work has implications in the way large combinatorial problems are addressed as the double feedback mechanism shows improvements over the single-positive feedback mechanisms in terms of convergence speed and of major results.

Keywords: Stigmergy, Co-Evolution, Self-Organization, Swarm Intelligence, Foraging, Cooperative Learning, Combinatorial Optimization problems, Symmetrical Traveling Salesman Problems (TSP), phase-space.

Information-Theoretic Measures for Objective Evaluation of Classifications

This work presents a systematic study of objective evaluations of abstaining classifications using Information-Theoretic Measures (ITMs). First, we define objective measures for which they do not depend on any free parameter. This definition provides technical simplicity for examining “objectivity” or “subjectivity” directly to classification evaluations. Second, we propose twenty four normalized ITMs, derived from either mutual information, divergence, or cross-entropy, for investigation. Contrary to conventional performance measures that apply empirical formulas based on users’ intuitions or preferences, the ITMs are theoretically more sound for realizing objective evaluations of classifications. We apply them to distinguish “error types” and “reject types” in binary classifications without the need for input data of cost terms. Third, to better understand and select the ITMs, we suggest three desirable features for classification assessment measures, which appear more crucial and appealing from the viewpoint of classification applications. Using these features as “meta-measures”, we can reveal the advantages and limitations of ITMs from a higher level of evaluation knowledge. Numerical examples are given to corroborate our claims and compare the differences among the proposed measures. The best measure is selected in terms of the meta-measures, and its specific properties regarding error types and reject types are analytically derived.

[1107.1837] Information-Theoretic Measures for Objective Evaluation of Classifications. by Bao-Gang Hu, Ran He, XiaoTong Yuan

very interesting for future reference, if I’m back to ITMs for my data…

Shortest Path Sardine

Fig.1 – (click to enlarge) The optimal shortest path among N=1084 points depicting a Portuguese sardine as a result of one of our latest Swarm-Intelligence based algorithms. The problem of finding the shortest path among N different points in space is NP-hard, known as the Travelling Salesmen Problem (TSP), being one of the major and hardest benchmarks in Combinatorial Optimization (link) and Artificial Intelligence. (D. Rodrigues, V. Ramos, 2011)

Almost summer time in Portugal, great weather as usual, and the perfect moment to eat sardines along with friends in open air esplanades; in fact, a lot of grilled sardines. We usually eat grilled sardines with a tomato-onion salad along with barbecued cherry peppers in salt and olive oil. That’s tasty, believe me. But not tasty enough however for me and one of my colleagues, Vitorino Ramos (blog link/twitter link). We decided to take this experience a little further on, creating the first shortest path sardine.

Fig. 2 – (click to enlarge) Our 1084 initial points depicting a TSP Portuguese sardine. Could you already envision a minimal tour between all these points?

As usual in Travelling Salesmen problems (TSP) we start it with a set of points, in our case 1084 points or cities (fig. 2). Given a list of cities and their pairwise distances, the task is now to find the shortest possible tour that visits each city exactly once. The problem was first formulated as a mathematical problem in 1930 and is one of the most intensively studied problems in optimization. It is used as a benchmark for many optimization methods. TSP has several applications even in its purest formulation, such as planning, logistics, and the manufacture of microchips. Slightly modified, it appears as a sub-problem in many areas, such as DNA sequencing. In these applications, the concept city represents, for example, customers, soldering points, or DNA fragments, and the concept distance represents travelling times or cost, or a similarity measure between DNA fragments. In many applications, additional constraints such as limited resources or time windows make the problem considerably harder. (link)

Fig. 3 – (click to enlarge) A well done and quite grilled shortest path sardine, where the optimal contour path (in blue: first fig. above) with 1084 points was filled in black colour. Nice T-shirt!

Even for toy-problems like the present 1084 TSP sardine, the amount of possible paths are incredible huge. And only one of those possible paths is the optimal (minimal) one. Consider for example a TSP with N=4 cities, A, B, C, and D. Starting in city A, the number of possible paths is 6: that is 1) A to B, B to C, C to D, and D to A, 2) A-B, B-D, D-C, C-A, 3) A-C, C-B, B-D and D-A, 4) A-C, C-D, D-B, and B-A, 5) A-D, D-C, C-B, and B-A, and finally 6) A-D, D-B, B-C, and C-A. I.e. there are (N–1)! [i.e., N–1 factorial] possible paths. For N=3 cities, 2×1=2 possible paths, for N=4 cities, 3x2x1=6 possible paths, for N=5 cities, 4x3x2x1=24 possible paths, … for N=20 cities, 121.645.100.408.832.000 possible paths, and so on.

The most direct solution would be to try all permutations (ordered combinations) and see which one is cheapest (using computational brute force search). The running time for this approach however, lies within a polynomial factor of O(n!), the factorial of the number of cities, so this solution becomes impractical even for only 20 cities. One of the earliest and oldest applications of dynamic programming is the Held–Karp algorithm which only solves the problem in time O(n22n).

In our present case (N=1084) we have had to deal with 1083 factorial possible paths, leading to the astronomical number of 1.19×102818 possible solutions. That’s roughly 1 followed by 2818 zeroes! – better now to check this Wikipedia entry on very large numbers. Our new Swarm-Intelligent based algorithm, running on a normal PC was however, able to formulate a minimal solution (fig.1) within just several minutes. We will soon post more about our novel self-organized stigmergic-based algorithmic approach, but meanwhile, if you enjoyed these drawings, do not hesitate in asking us for a grilled cherry pepper as well. We will be pleased to deliver you one by email.

Fig. 4 – (click to enlarge) Zoom at the end sardine tail optimal contour path (in blue: first fig. above) filled in black, from a total set of 1084 initial points.

(this is a joint twin post with Vitorino Ramos)

David Hales: why computer people need to think about political economy and other issues

Today at ISCTE-IUL we’ll have a seminar by David Hales. David Hales is a researcher at the Open University in the United Kingdom. His research is at the overlap between computer science and social science. He has a background is Computer Science and Artificial Intelligence but he has spent a lot of time with Sociologists, Philosophers and even lapsed Economists doing simulations.

He has been doing a lot of interesting research and his talk today is about “The socio-economics of distributed systems (why computer people need to think about political economy and other issues)“.

The seminar is Friday, 3rd June 2011, 18h00 at ISCTE-IUL, building 2, room C402

Later this year, he will also be the Keynote speaker of the PhD in Progress Workshop that I’m organising in Vienna during ECCS’11, so if you can’t see him talk today, you can always joins us in the European Conference on Complex Systems and have a good time!

Springer crap paperback books are expensive – Rant!

<book rant>

I Love books. I buy lots of books. Just today I received a package with two books that costed me over 150€. Two paperback books. That’s a lot! But this is not a problem. I need them. I love them. I pay the price.

What pissed me off, was that this book, The Geometry of Biological Time, published by Springer, the most expensive of the two, is such a lazy print from Springer. It seems that they just used a Xerox machine and glued 800 pages to make the binding. What a crap work this is, springer? This would be acceptable for a small shop around the corner, but not from you, and not at these prices!

</book rant>

Day 4 at ETH – The Food

Zürich IV

After 4 days, I miss my diet… Here, everything is based on cheese… and cheese, and cheese… With all the options the quality is really high and we can really enjoy these plates, but I want some grilled fresh fish please…

Today we had dinner in one “picturesque” house that appears in all Zürich guides: The Rheinfelder Bierhalle !Depicted is their internationally famous Jumbo-Jumbo-Cordon Bleu (It’s longer than a 15″ laptop) eaten with the help of a Schneider-Weisse beer (Yes, that’s 1/2L and we had more than we can remember). Now I have to digest all this… Tomorrow night I’ll go back to my diet… if I can eat anything by then.

Day 3 at ETH – Lot’s of things happenning…

Some notes:

  1. Zurich today has a beautiful sun spying on us. It was fun to get its warmth during lunch…

  2. Don’t understand what is going on with my bank. Can’t get more than 100 Swiss Francs (~80€) each time I try to withdraw some money. It has to be something with the Swiss banks as I used this card in other countries and I managed to withdraw higher values… So… Swiss banks don’t really want me spending money here, and 100 CHF isn’t any REAL Money… for Swiss terms…

  3. We had today a kind of team building social game that was very interesting and went then with the team to drink some beers in a tapas bar. We then moved on to a (I presume) typical folk music bar from Switzerland (you can see a short video above). They told me that this was the first time that they had this type of event inside the team, and I think that by the success of it they will repeat it again.

  4. Finally … It’s still cold… Argh… but worse than the cold is the wall you hit when you move from 1 room at 22ºC to the outside at 2ºC. It’s something I won’t get used, ever…

  5. Science/geek stuff… yesterday I was here (If you know what this is, I’ll give you a Swiss cheese), and today I was briefed a bit about Brutus! LOL, Fun times…