You are currently browsing the monthly archive for June 2011.

Video – A 1964 film based on the novel *Zorba the Greek* by Nikos Kazantzakis. The film was directed by Michael Cacoyannis and the title character was played by Anthony Quinn. The supporting cast included Alan Bates as a visiting Englishman as well as Irene Papas. The theme, “Sirtaki” by Mikis Theodorakis, has become famous and popular as a song and as a dance. The movie was shot on location on the Greek island of Crete. Specific places featured include the town of Chania, the Apokoronas region and the Akrotiri peninsula. The famous scene, in which Quinn’s character dances the Sirtaki, was shot on the beach of the village of Stavros. (from YouTube)

*Basil* (Alan Bates), a young English writer, meets a free-spirited Greek peasant named *Zorba* (Anthony Quinn) while waiting to travel to the island of Crete. While Zorba pursues a relationship with aging French courtesan *Madame Hortense*, *Basil* attempts to court a young widow. Along the way, he learns valuable life lessons from the earthy *Zorba*, who has an unquenchable* joie de vivre* (link):

[…] **Basil**: I don’t want any trouble. **Alexis Zorba**: Life is trouble. Only death is not. To be alive is to undo your belt and look for trouble. […] **Zorba**: Damn it boss, I like you too much not to say it. You’ve got everthing except one thing: madness! A man needs a little madness, or else… **Basil**: Or else? **Zorba**: …he never dares cut the rope and be free. […] **Basil**: Teach me to dance, will you? **Zorba**: Dance? Did you say… dance?! … Come on my boy… together… Let’s go… hop … Again… hop … […] **Zorba**: Boss, I have so much to tell you, … I never had loved a man like you … […] **Zorba**: Hey boss, did you ever see a more splendiferous crash?! … Oh, … You can laugh too!… hmmm… Hey!… You laugh! […]

Drawing (page 5) – Riccardo Manzotti – *A Process View of Reality* – April 2008.

“** To destroy variety at a scale, we need variety at another scale**“,

*Yavni Bar-Yam*, ICCS’11 – Int. Conference on Complex Systems, Boston, June 2011.

In “*a process oriented externalist solution to the hard problem”* (*A Process View of Reality, *2008), an 8 page comic series (pdf link) about the *Mind-Body problem*, or * David Chalmers* *Hard Problem*, Riccardo Manzotti asks: […] *How can the conscious mind emerge out of physical stuff like the brain?* *Apparently, Science faces an unsolvable problem: The hard problem states that there is an unbridgeable gap between our conscious experience and the scientific description of the world. The modern version of the mind-body problem arose when the scholars of the XVII century suggested that reality is divided in the mental domain and in the physical domain* […]. In the next 7 pages, *Manzotti* comes up with a possible solution, not far from what Science nowadays is doing, starting in the 1950’s: avoiding reductionism.

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, *David Rodrigues* (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*(*n*^{2}2^{n}).

In our present case (*N*=1084) we have had to deal with 1083 factorial possible paths, leading to the astronomical number of 1.19×10^{2818 }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.

p.s. – This is a joint twin post with *David Rodrigues*.

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.

Figure – Poker final hand rankings. Poker is a typical example of *bounded rationality* in our daily lives. Without having all the information available, you still have to make a decision. In one of his works, *Herbert Simon* states: “*boundedly rational agents experience limits in formulating and solving complex problems and in processing (receiving, storing, retrieving, transmitting) information*“.

[…] *Bounded rationality* is the idea that in decision making, rationality of individuals is limited by the information they have, the cognitive limitations of their minds, and the finite amount of time they have to make decisions. It was proposed by *Herbert Simon* as an alternative basis for the mathematical modelling of decision making, as used in economics and related disciplines; it complements rationality as optimization, which views decision making as a fully rational process of finding an optimal choice given the information available. Another way to look at bounded rationality is that, because decision-makers lack the ability and resources to arrive at the optimal solution, they instead apply their rationality only after having greatly simplified the choices available. Thus the decision-maker is a satisfier, one seeking a satisfactory solution rather than the optimal one. *Simon* used the analogy of a pair of scissors, where one blade is the “cognitive limitations” of actual humans and the other the “structures of the environment”; minds with limited cognitive resources can thus be successful by exploiting pre-existing structure and regularity in the environment. Some models of human behaviour in the social sciences assume that humans can be reasonably approximated or described as “*rational*” entities (see for example rational choice theory). Many economics models assume that people are on average rational, and can in large enough quantities be approximated to act according to their preferences. The concept of bounded rationality revises this assumption to account for the fact that perfectly rational decisions are often not feasible in practice due to the finite computational resources available for making them. […] In Wikipedia, (link).

Book cover – *Herbert A. Simon*. *Models of Bounded Rationality*, Volume 1, Economic Analysis and Public Policy, *MIT Press 1984*. The Nobel Prize in Economics was awarded to Herbert Simon in 1978. At Carnegie-Mellon University he holds the title of Professor of Computer Science and Psychology. These two facts together delineate the range and uniqueness of his contributions in creating meaningful interactions among fields that developed in isolation but that are all concerned with human decision-making and problem-solving processes. In particular, Simon has brought the insights of decision theory, organization theory (especially as it applies to the business firm), behavior modeling, cognitive psychology, and the study of artificial intelligence to bear on economic questions. This has led not only to new conceptual dimensions for theoretical constructions, but also to a new humanizing realism in economics, a way of taking into account and dealing with human behavior and interactions that lie at the root of all economic activity. The sixty papers and essays contained in these two volumes are grouped under eight sections, each with a brief introductory essay. These are: Some Questions of Public Policy, Dynamic Programming Under Uncertainty; Technological Change; The Structure of Economic Systems; The Business Firm as an Organization; The Economics of Information Processing; Economics and Psychology; and Substantive and Procedural Reality. Most of Simon’s papers on classical and neoclassical economic theory are contained in volume one. The second volume collects his papers on behavioral theory, with some overlap between the two volumes. (from MIT).

Video – “*Be the one*” track on *Moby*‘s Destroyed album. *Destroyed* is the tenth studio album by the American electronic artist *Moby*. It was released on 2011 by Mute Records. Network video animation by *Taras Gesh*.

From time to time some colleagues, students and friends do ask me what is a good introductory paper into *Complex Networks*. Indeed there are several, including some general books, but over the years I tend to point into “*The Shortest Path to Complex Networks*” by J.F.F. *Mendes* (thorough my life I met him several times now) and S.N. *Dorogovtsev*, released in 2004. For those who are beginners on the field, and do want to play or indeed program several concepts in the area, like *clustering*, *small-worlds*, *edge condensation, cliques and communities* as well as the *preferential attachment* (point 20.) among others, this is a rather simple and quick (besides is 25 pages) straightforward paper, well organized around 51 different entries, topics and concepts. Not all of them are here of course, like, among others, the *age node* issue which for several reasons tends to interest me. Point 1 starts with the birth of network science and it’s simple as : […] I*n 1735, in St Petersburg, Leonhard Euler solved the so-called Konigsberg bridge problem – walks on a simple small graph. This solution (actually, a proof) is usually considered as a starting point of the science of networks* […]. The full paper is available through *arXiv.org*. Here is the link. Do enjoy. Like *Moby* says… *be the one*. The full reference list is also a must.

## Recent Comments