What is Emergence?
Generative Murals as Experiments in the Philosophy of Complexity
Philip Galanter, BA, MFA
Arts Technology Group, New York University, New York, USA.
The Traveling Salesman s a series of site specific wall paintings based on a canonical optimization problem. Well known among computer scientists, the Traveling Salesman Problem (TSP) is a search for the shortest path visiting a number of locations exactly once. For this piece software is used to solve the problem for sets of random points, and then each optimized path is transformed into an image. The resulting images exhibit a consistent style that is simultaneously random yet visually coherent. Some would call this emergent form.
The Traveling Salesman explores the ontological and epistemological aspects of the question "what is emergence"?
One day while developing my "Foundations of Generative Art Systems"  class I was looking for a good example to illustrate the use of genetic algorithms. I came acoss an article by Larry Fogel  documenting his early use of genetic algorithms to solve The Traveling Salesman Problem.
The Traveling Salesman Problem, or TSP, is well-known among computer scientists, mathematicians, engineers and others. The problem is easy to state. A salesman has to visit a number of cities exactly once, and the goal is to find the tour that minimizes the total distance traveled. (There are other variations as well). 
The TSP is of interest in part because it represents a broad range of applications including all manner of transportation logistics, but it also maps into less obvious applications such as genome sequencing, integrated circuit design, computer network design, and power grid design.
The TSP is also of interest because it is a combinatorial problem thought to be NP-Complete. Informally NP-Complete problems are those which become exponentially more difficult to solve as their complexity is increased linearly. For example, if a 200 city problem takes 1 second for a computer to solve, a 400 city problem might take 4 seconds to solve, and an 800 city problem might take 16 seconds to solve. Interestingly if a TSP algorithm could be found that only requires a linear increase in computation time, it would generalize to a linear solution for all NP-Complete combinatorial problems. It is thought, however, that such a solution is an impossibility.
In practice the most efficient algorithms for the TSP are not genetically based. But because the problem is easy to understand it can nevertheless be useful in a teaching context. In a typical implementation each genotype is in fact a proposed solution to the problem, i.e. a tour. At each step the phenotype, the total distance traveled, is evaluated. Very long tours are eliminated from the gene pool, and the genes for short tours are allowed to continue breeding. Because viable genes must be a cycle that includes each city once and only once, typical simple mutation and crossover operations are usually avoided. Instead similar operations that ensure legal tours are used. After a number of generations the solutions in the gene pool improve and perhaps ultimately yield an optimal tour, i.e. the shortest possible path.
Here is the graph Fogel originally published in his groundbreaking work. He first generated a set of random points (i.e. “cities”) and then used genetically inspired software to generate this TSP solution.
As I viewed this graph something strange happened. I stopped thinking about the lesson I was preparing and the various technical aspects of genetic algorithms. I was lost in the appreciation of the esthetics of what could be viewed as a line drawing. The formal aspects of this would-be machine drawing seemed to exhibit an intelligence and coherence that had nothing to do with combinatorial analysis and optimization. A set of random points had been transformed into a compelling image with a definite style. I wondered if an artist, if asked to connect the dots, could come up with an equally satisfying line drawing.
It seemed as if formal beauty was an emergent property arising out of the complexity of genetic competition. With the aid of a scanner and Photoshop I appropriated the graph and added some color to help emphasize the overall contours of the “drawing” resulting in the following image.
Those studying complex systems are not unanimous as to how to define complexity, but virtually all would agree that evolutionary systems fit the bill. The local interactions of large numbers of small components (i.e. genes) and feedback mechanisms (i.e. reproduction and competition) result in structures at a higher level (i.e. the phenotype) that would be difficult to explain via reductionism.
For many emergence is the hallmark of complexity, and natural evolution is the highest and best example of emergence. Exquisite forms such as butterfly wings, leopards spots, the branching structures of trees, and spiral structures in seed pods and flower petals, and indeed the entire realm of living things, seem to offer “order for free”  as provisional end points in the long process of evolution.
Philosophers and theologians have argued that just as the complex design of a watch implies the existence of an intelligent watchmaker, the infinitely more complex design of the ecosystem and the plants and animals it contains implies the existence of an infinite creator, which is to say God. Emergence is offered by complexity science as a less mysterious, purely mechanistic, explanation of creation.
But even as such, emergent properties are often defined as “unexpected” or “surprising” features that defy prediction or even understanding via dissection into parts, and can only be appreciated in a holistic manner.
And so it seemed with the solutions to the Traveling Salesman Problem. Upon completing the graphic shown above (figure 1.1) I immediately decided to embark on a series of wall drawings or murals. Each mural is site specific in that a set of random points are generated to fit the specific shape of the given wall. Then those points are solved as a TSP problem and the resulting lines are painted and filled with color.
I expected that some would respond to these works in a way consistent with the ironic social/political postmodern tone that remains dominant in the American art world. After all, the traveling salesman has an iconic status in American culture. Willie Loman in Arthur Miller’s play “Death of a Salesman” epitomizes the hard working capitalist who ultimately fails because he views the American dream as a purely material pursuit. And there is a tradition of bawdy “traveling salesman” jokes where the eponymous anti-hero engages a sequence of farmer’s daughters or bored housewives, often to no happy end. And indeed one could observe that the same computing technology that allows us to now solve large TSP’s has also, ironically enough, made traveling salesmen increasingly irrelevant through the advent of web based marketing, video conferencing, and so on.
But such things were not my interest. Artists often invent private languages, and just as felt and fat became symbols for Joseph Beuys of his (possibly fictional) wartime experiences, for me the Traveling Salesman Problem became a symbol of my experience with emergence.
I made more TSP based designs and confirmed that they shared a consistent aesthetic style. I continued to wonder how it was that a genetic algorithm which solves the TSP, an exercise in optimizing a tour of random points with no aesthetic agenda, and no feedback based on artistic judgment, could generate murals with a consistent visual
style that seemed anything but random.
2. TSP Solutions Considered Aesthetically and Mathematically
To better understand the emergent form TSP solutions seem to exhibit I created 25 problems, each using 1000 points (cities) randomly distributed within a circle. I distributed the points within a circle to avoid any bias an aspect ratio or straight edges or corners might introduce.
Figure 2.0 Figure 2.1
I noted the following aesthetic factors that seemed to contribute to the style these designs exhibit.
I then embarked upon a modest mathematical investigation of the apparently emergent form TSP solutions exhibit considering each factor in turn.
2.1 Each design creates an enclosed area
It seems almost trivially obvious that any TSP solution is going to create an enclosed area. Imagine each city is a fence post and each city-to-city path taken is a barrier. If at a given point along the fence 2 persons would like to meet they may be tempted to walk to the next fence post. But at that post they will find another fence span blocking their meeting. And so they move on to the next fence post and find another span blocking their meeting. And so it goes until, by definition, the fence returns to the first fence post. Since the two people can never meet one of them must be trapped in an enclosed area.
It’s of course possible that the fence will cross itself, and when this happens it creates two or more enclosed areas. But this doesn’t seem to happen in TSP solutions. Why might this be?
2.2 Each design creates only one enclosed area, i.e. the border never crosses itself
We now want to show that the total length of the two crossed line segments is always greater than the total length of the uncrossed line segments in both possible cases. We will call the four cities in question A, B, C, and D. An additional point X is added at the point of intersection.
Since the shortest distance between two points is a straight line, we can show:
AC < AX + XC
BD < BX + XD
AC + BD < (AX + XC) + (BX + XD)
AC + BD < (AX + XD) + (BX + XC)
AC + BD < AD + BC
In the same way we can show that:
AB + CD < AD + BC
Having shown that the total length of the two crossed line segments is always greater than the total length of the uncrossed line segments in both possible cases, we can infer that any suggested solution that includes a pair of crossed line segments can be improved by uncrossing those line segments. Thus an optimal solution will have no crossed line segments at all. (Note though that it is quite possible that a solution with no crossed line segments is still sub-optimal).
2.3 The angles which make up the borders seem evenly divided between convex and concave. There is a relative lack of extreme angles.
Figure 2.6 Figure 2.7
Figure 2.8 Figure 2.9
Aggregating the angle statistics within each of the 25 test cases further confirms a relative balance of convex versus concave edges.
Figure 2.11 Figure 2.12
It makes perfect sense that there is a balance of convex and concave contours. While some angles may be more likely than others, complementary angles (as the distribution in figures 2.8 and 2.9 shows) are equally likely. Assume a tour is being constructed and that points A and B have been connected. The inside of the soon-to-be enclosed space is to the left and the outside is to the right. As a local phenomenon (figure 2.13) a third random point C to be added to the tour is as likely to be on the left as the right. Thus adding a third point is as likely to create a concave contour as a convex one.
2.4 The area seems to be equally divided into figure and ground
Figure 2.14 Figure 2.15
Similar to the argument in the previous section, as a local phenomenon adding a third point C as the tour is connected is as likely to add a lot as a little area in the enclosed figure.
3. Emergence as a Philosophical Problem
Somehow improved understanding had evaporated the sense of emergence.
One has to wonder whether emergence is in the eye of the beholder. Could it be that Marvin Minsky is correct when he refers to emergence as a “suitcase concept’ we use to deceive ourselves by filling it with “things we don’t understand yet”?  Might it be that extraterrestrial beings endowed with an advanced intelligence wouldn’t consider the evolution of earthly plants and animals as emergence, but would simply view it on a par with other non-emergent phenomena?
But further, if emergence is merely an experience without any specific basis in the physical world, does that mean it isn’t real? Following John Searle’s thoughts on consciousness , perhaps emergence like other qualia is real but partitioned into the realm of what he calls “first person ontology”.
Emergence as a philosophical problem remains an open question. But this actually increases my enthusiasm for this series of murals. Often an artists role, and the private language he or she may develop, is more about asking important questions than providing pat answers. In addition I hope the Traveling Salesman series can serve as an example of how the exploration of systems through generative art can act as a sort of experimental philosophy. I remain convinced that even in these postmodern times philosophy can be pursued via artistic experimentation.
 Galanter, P. Foundations of generative art systems – a hybrid survey and studio class for graduate students. Generative Art 2001: Proceedings of the 4th International Conference. Generative Design Lab, Milan Polytechnic, Milan 2001
 Fogel, L. J. (1999). Intelligence through simulated evolution : forty years of evolutionary programming. New York, Wiley.
 Kauffman, S. A. (1995). At home in the universe : the search for laws of self-organization and complexity. New York, Oxford University Press.
 In a talk presented at the 2003 International Conference on Complexity Science, Nashua New NH
 Searle, J. R. (1997). The Mystery of Consciousness, New York, New York Review of Books