Swarm Intelligence – Chapter 6

Thinking is Social

The chapter begins by talking about the story of the blind men and the elephant. The point of the story here is to show the societies are able to benefit from the sharing of individuals partial knowledge, which results in a large body of knowledge that alloww the group to develop strategies no individual could formulate. They then begin talking about the three levels of adaptation, the point of these three levels are the development of optima processes in a group. The adaptive culture model is the next topic of interest. First they briefly review their earlier discussion of Axelrod, and his contribution to evolutionary computing. Then they begin talking about speculations that have been made regarding the development optimums through the use of cognitive optimization. Axelrod’s recent simulations are touched on before they address the next topic.

Axelrod’s culture model is the next topic of interest in the chapter. It begins by talking about how similarities between individuals can be used to spread culture. In the ACM model individuals adopt non-matching features from their neighbors stochastically. It then talks about how simulations are conducted by repeated iteration until regions of the matrix contain matching patterns. The following sections detail various experiments that were conducted using ACM.

The first experiment deals with Axelrods theory that similarity is a precondition for social interaction and subsequent exchange of cultural features. There is then discussion on about the “birds of a feather flock” idea where self-similar individuals group, another idea presented where by people are more interested in group with people that share the same ideas. In this experiment the effect of similarity as a casual influence was removed. The result of the experiment was unanimity. Thus, it appears that the effect of casual similarity in ACM results in polarization.

In the second experiment they substituted a simple arbitrary function for the similarity test previously used. The rule was “if (the neighbor’s sum is larger than the targeted individual’s sum) then interact.” In this experiment the population converged on the global optimum every time, though the number “9999” was never included in the initial population.

The task of the third experiment was to find a set of five numbers that represented the features of an individual, within which the sum of the first three numbers equaled the sum of the last two. They go into discussion about why this is interesting, and relevant. Then they explained the details of the experiment. The result of the experiment was that all the individuals solved the problem, and parts of the solution were distributed through definite regions of the matrix. They believe the point of this experiment is to show the spread of features throughout a culture.

The fourth experiment deals with “hard” problems, also known as NP problems. In this particular experiment, they looked at the traveling salesman problem. They talk about the details of setting up the TSP to work within the simulation, and then make some observations about the results they received across multiple tests. It seems that at best half of the population would find an optima path, but throughout the simulations they found five different paths that all yielded the shortest distance.

Parallel constraint satisfaction was the focus of the fifth experiment. It began by discussion how features of ACM can be used to represent constraint satisfaction networks. They then go into discussion about parallel constraint satisfaction networks. Discussion of the advances and disadvantages of various aspects of these networks followed. An example, and setup for the experiment was the next topic of discussion. They go into detailing how these networks were encoded for the sample, and then talk about their observations from the experiment.

The sixth experiment focuses on symbol processing. There is discussion about traditional AI and navigation through symbolic nodes. Then, there is a more detailed discussion of how a network of nodes is transformed into a hierarchical tree. From the hierarchical tree they example the properties that are used in this experiment. There is some discussion at the end about the relevance of the experiment.

The chapter ends with a discussion about the ACM, and important questions related to it. Then they begin to talk about the relative insignificance of the individual in the system. And, finish by trying to make a global comparison to human thinking, and cognition.

Swarm Intelligence – Chapter 5

Humans Actual, Imagined, and Implied

This chapter begins by taking a look at the study of minds. The work of Claude Shannon is first examined, as he proposed information could be conceptualized mathematically as a kind of inverse function of probability. It goes through some of his studies dealing with randomly selecting letters from a page based on their probable conjunction with other letters. Since he lived before computers, they expanded his work using a computer model to show how things began to make more and more sense the further out you branched.

The next area they address was the fall of the behaviorist paradigm. Here they talked about the traditional aspects of psychological study based on behavior. Through the section they try to explain the basis of the behaviorist perspective, and begin to look at the problems that plagued it. This was immediately followed by the cognitive revolution. Here they begin talking about the shift in paradigm where minds were beginning to be thought of in terms of cognition rather than behavioral. They also talk about the impact this had on the development of AI systems at the time. These discussions worked towards the Bandura Social Learning Paradigm. This is the system that provided the foundation for social psychology, or looking at the learning/abilities of individuals in terms of the group they were in.

Social psychology is the focus of the next section. They begin the section by talking about the history, and development of the disciplines proponents. Initially, they focus on discussion of the principles of Gestalt psychology brought over by Germans in the mid twenty century. The main point here was that they were trying to establish that the mind attempts to make sense of the object in a coherent manor regardless of their actual nature. The next discussion takes a look at the Lewin field theory. Here they discuss his proposed life space and how it was portrayed at the time. His work is considered the stage for modern complex systems theory in psychology. Social influence is examined as the first prime example of social psychology. Here they look into how and why humans establish norms, conform, and the impact of social influence. They review various studies that show how powerful the influence of others can impact an individual. The next area covered is sociocognition. They talk about examples by where people can share collective understanding where by each individual only knows a fragment of the whole picture.

Pulling this all together into a more useful form, the next section begins to talk about simulating social influence. Here they are examine what exactly the difference is between a simulated mind, and a real mind. Though there is no definitive point, they seem to put forth the idea that a simulated mind is an actual mind. They then begin talking about trying to figure out how various modes of thought are conducted in order to model them properly in simulation. The next area of discussion is the shift from traditional AI to evolution methods. They start by taking about the history of bad blood between the two. Then talk about the strengths and weaknesses of both. It boils down to the fact that tradition AI is not good at handling simple tasks that evolutionary methods excel at. From here they begin talking about the evolution of cooperation. Through a discussion of the prisoners dilemma they examine how cooperation between individuals can greatly influence the rewards each member receives. The next area of discussion was an attempted explanation for the need for coherence. From there they begin to talk about networks in groups. Here they began to look at how groups of people were able to communicate, and thus come to some kind of consensus. To do this they used constraint satisfaction networks (which were explained in chapter 2).

In the following section, there is discussion about culture in theory and practice. The section begins by trying to establish whether or not culture is a thing that actually exists, or an abstraction. Eventually, they decide it is something, and begin to pursue principles based on that conjecture. First they begin to illustrate how computer simulations can represent the behavior of individuals in a social context. To demonstrate this point they use the example of the prisoners dilemma. The El Farol problem was then examined (Irish drinking night), this showed simulated interaction between agents that developed sophisticated negotiation techniques in order to trick other agents. It is basically a situation were you think you know what the other knows, but they know what you know soSugarscape was then discussed, here they were trying to grow artificial societies. The most interesting note here was the emergence of sophisticated immune systems that developed in the agents. The next system was Tesfatsions ACE. This was a system that modeled complex economic systems based on a modified version of the prisoners dilemma. The following sample was Pickers competing-norms model, where he tried to show how some behaviors might remain dominant when better behaviors are available in the environment. Latens dynamic social impact theory. This talked about how more people yield less impact on the system, and also showed concepts such as minority attitudes in populations are achieved at steady state. The evolutionary culture model established by Boyd and Richerson was then talked about. It basically discusses the link between cultural, and biological evolution. To further this discussion they follow up by talking about memetic (first talked about in chapter 1), and their relevance. Memetic algorithms are then talked about. One good example is the one created by Burke and Smith. Advancing another step in the scale, they begin talking about cultural algorithms. They end the section by talking about the convergence between social scientists and computer simulations.

The chapter wraps up by taking a look at what life might be like without culture. In the section they take a look at multiple instances of feral children that are found in the wild, and they talk about their tendencies and inability to become civilized. The picture they paint is very dismal, as they try to say that advanced intelligence comes from culture, rather than the individual.

Swarm Intelligence – Chapter 4

Evolutionary Computation Theory and Paradigms

The chapter begins by exploring some of the history of evolutionary computation. They take a look at the four areas of evolutionary computation (genetic algorithms, evolutionary programming, evolution strategies, and genetic programming) in terms of people rather than technologies (during history). First they talk about genetic algorithms and contributions made by A.S. Frasier, and then work their way to John Holland who is the main focus. From Holland they start talking about his students, Bagley, K. A. De Jong, and David E. Goldberg. Additionally, there is discussion of Steve Smith, and John Grefenstette’s contributions (both students of De Jong). The next discussion is on evolutionary programming where they examine the work of Larry J. Fogel and his colleagues. They also mention work by Don Dearhold and his students. Ingo Rechenberg and Hans-Paul Schwefel are illustrated as the pioneers of evolution strategies, the section focuses only on their contributions. The genetic programming section highlights the work of Friedberg, Dunham, and North. John Koza did extensions of their work. The section ends by discussing emerging trends towards the unification of the four fields.

The following section provides and overview of evolutionary computing. They first discuss the primary three things that are present in all four types. After which they begin discussing the evolutionary computing paradigm attributes. Where they discuss issues in relation to other existing search paradigms. This discussion provides the foundation for implementation concepts, where they explore the five steps of implementation that are found in all the systems. From this point they begin looking at specific implementation of the four areas of evolutionary computing.

Genetic algorithms are the most practiced, and perhaps relevant to swarm intelligence so they are addressed at length. The section begins with a quick primer on the various terms used within GAs. This explanation is followed by an overview of GAs. Here they discuss the five steps of implementation tailored towards GAs. The main difference is that crossover is so important. A simple GA problem is then examined to illustrate the key points. This study is attempting to optimize a value of x based on a sine function. In this example they illustrate simple implementations of crossover and mutation. After the sample they give a review of GAs where they discuss the representation of variables, population sizes, population initialization, fitness calculations, roulette wheel selection, crossover, and mutation in detail. Having established the basics they begin to look at schemata and the schema theorem. First they discuss what exactly a schemata is and how to implement, and perform various procedures on them (such as crossover). Then, they provide the schema theorem that predicts the number of times a specific schema will appear in the next generation of a GA, given the fitness of the population members in the schema. The section is ended with the authors’ thoughts on GAs as a whole.

Evolutionary programming is examined in the next section. The section begins with a primer on evolutionary programming. They then go into an explanation of how the five-implementation steps are tailored for EP. Since EP is essentially a top down approach they describe it in terms of the evolution of a finite state machine. They give design level implementation concepts for dealing with problems such as the addition and removal of states. There is also discussion of the five types of mutation that can occur. Another type of problem that EPs are used for is, function optimization. From this they illustrate how one might use this to solve the prisoner’s “dilemma.” As in the previous section, this ends with their thoughts on EPs as a whole.

Evolution strategies—an expansion of evolutionary programming—are examined in the following section. Once again, the section begins with an explanation of what exactly, evolution strategies, is. Then, they jump into an explanation of mutation in terms of an entire population. From the biological explanation they begin to discuss the foundations of how this is implemented. The next issue they address is recombination. After establishing how alterations are made, they discuss how selection is performed. This section ends with an explanation of the implementation procedure, and a brief summary of ES.

The final section examines genetic programming, which is often thought of as a subset of genetic algorithms. The section begins by explaining that genetic programming focuses on tree structures. From this they explain the five preparatory steps of implementation. After those five steps have been completed the program continues on the “real” implementation steps. They talk about different methods that are used to make the tree “grow.” This section is ended with a summary of GP, and problems that you are most likely to encounter when trying to implement it.

Swarm Intelligence – Chapter 3

On Our Nonexistence as Entities: The Social Organism

This chapter begins by taking a look at various perspectives on evolution. First they address the conflict between creationism, and evolution in schools, and then began to discuss how evolution on Earth may have taken place. Then they begin talking about life on different scales. The first scale they examine is macro. This perspective is called Gaia, and focuses on the earth as a life form itself. They talk about how life forms on a planet primarily serve to keep the planet stable in someway. In a simulation called Daisyworld, they examine how different colors of daisies can help regulate the surface temperature of a planet.

They then examine differential selection by which it is believed that evolution selects against animals that reproduce too often to prevent over population (and thus eliminating a food source). Next they discuss attempts to understand behavior that seems to contradict the idea of self-preservation: the process of inclusive fitness whereby individuals try to protect others with similar genetics. Their underlying point throughout the section is that scientists need to stop looking for individual selectionism, and focus on group selection.

The smallest level of interest lies within cells. They look at organelles, and put for the suggestion that the only purpose of humans is to preserve the life, and facilitate these “tiny masters.” This entry only appears to have been entered in order to show the importance of finding the right scope. The book puts forth the belief that you should not look at individuals, but rather societies, or “super organisms.”

Self-organization and flocking behavior is the focus of the following section. Here they examine swarm (flocking) behavior as a certain form of optimization. They talk about how it becomes easier for the individuals to survive in a group, rather then alone, and the social supports that are established to facilitate basic functions, such a raising young, and finding food. The discussion begins with bacteria, examines insects, and finishes with animals. The first discussion of potential optimization was with ants, where they looked at the traveling salesman problem. With animals, they begin to look at the impact individual agents had on the group. Additionally, they tried to establish some fundamental rules for flocking behavior.

The culmination of the previous section provided the baseline of then next: robot societies. Here they first talk about the old paradigm established as MIT, “Gold Old-Fashioned Artificial Intelligence.” GOFAI is a symbol processing system, whereby the AI is intended to understand its surroundings, and then act accordingly. The new style of AI is based on subsumption architecture. These robots intelligences are built from the bottoms up. They have a simple set of rules that they follow that allows them to appear more purposeful than they really are. From this they began talking about the nature of the mind, and how it is separated from the brain. They also look into considering whether it is worthwhile to consider the mind as a society of agents (which the deem it is not). They talk about how swarms are more nearly a sum of the parts. There is then discussion about using small robots to complete various tasks such as cleaning the television screen to taking readings from a volcano. Virtual robots are considered to simulate actions that defy laws of physics. Kerstin Dautenhahn’s research is examined regarding social intelligence, and social robotics.

The following section talks about another aspect of AI: shallow understanding. There is discussion about deep processing, which is performed through operations on symbolic representations within the computer’s native mode. Things such a processing complex databases and proving theorems seem “deep.” However, programs that simply talk with the user, and don’t seem to do anything important are called “shallow.” But, they are ironically more difficult to code. They go into example using ELIZA, and they point out that a machine can make convincing chatter based on a dataset of pre-formulated responses by on key words, but they do not actually understand any of the content they are receiving.

The final section looks into what agency means. They examine various peoples research, such as Stan Franklin and Art Graeseer to determine what exactly an agent is. Essentially they determine that it is an entity that acts according to its environment, and the people often anthropomorphize the actions of agents as more meaningful things than they really are. Then, going full circle they return to evolutionary concepts, where by they think speech may have evolved from primate grooming behaviors.

Swarm Intelligence – Chapter 2

Symbols, Connections, and Optimizations by Trial and Error

This chapter begins by looking into symbols in trees and networks. The first example of the first philosophies regarding intelligence: symbol processing. This was the first approach that was used for artificial intelligence. This methodology relies on symbols to be clearly categorized. They discussed the grounding problem for tree structures as well. The second assumption they look into is fuzzy logic. Which means that connections are not either true or false. They are based on a degree of accuracy. Another method that was discussed was constraint-satisfaction models.

Commonly in traditional symbol processing, symbols are arranged in tree structures. With this structure, each step leads to another decision. However, since fuzzy logic does not rely on clear-cut decision making, it may look erratic, where it is strong in some places, and week in others. Trees cannot depict feedback. So, network matrices are used to depict feedback relationships. There is further discussion about representing networks using matrices (include mapping of trees on matrices). There is also discussion about graph patterns that cause feedback. Paul Smolensky has an equation to find the optimal state of such networks. There is discussion about maintaining harmony of a network. Particularly, there is discussion about a method of optimization formulated by John Hopfield.

The discussion of discovering patterns of connections among elements (learning) is covered. They begin by taking a look at what it means for two things to be correlated. They then begin to talk about how this is implemented using correlation matrices. The two types of organization they talk about are symmetrical and asymmetrical connections. They begin to talk about how you can use complex logical interactions to achieve different results. They focused on creating feed forward networks, and used them to create logical propositions. Interpretation is then talked about; the sigmoid function is used to manipulate information into a tolerable range.

Neural networks are then discussed. These networks are used to try to provide a theory of cognition referred to as connectionism. This method assumes that cognitive elements are made up as patterns distributed through a network of connections. This model more closely resembles human thinking, since it does not require elements to be separated for categorization.

The next section begins to take a look at problem solving, and optimization. They begin by trying to establish that characteristics of problems can be used to generate a degree of goodness by which an answer can be estimated. In this example they look at methodologies for selecting a solution to satisfy an algebra equation. Then they begin to look at the three spaces of optimization. The first is parameter space, which is the legal value of all elements. The function space contains the results of operations on the parameters. The fitness space contains the degrees of success by which patterns of parameters are used in function space. This is measured as a degree of goodness, or badness. They then begin to talk about evaluating solutions by establishing a fitness landscape. The idea is to reach the highest point on the graph (which can be multi-dimensional).

High dimensional cognitive space and word meanings are examined in the next section. This section begins by talking about computer algorithms used for word meaning recognition. The first approach is called semantic differential (Osgood, Suci, and Tannenbaum – 1950). They gave people words, and had extensive questionnaires about their feelings pertaining to the word (57). They linked words into groups by “halo effect,” which results in the categories: evaluation, potency, and activity. Another group created a database of word relations based on Usenet samplings in order to remove the factor of tester bias (Colorado 1990). They organized word associations into a matrix so they could establish more relationships, such ad Euclidean distance. They talk about how this closely relates to the way human’s process word definitions by understanding context rather than consulting a dictionary.

NK Landscapes, and factors of complexity are discussed in the following section. This section deals with interdependent variables and problem space. The foundations of complexity lie in N, the size of the problem, and K, the amount of interconnectedness of the variables (Stuart Kauffman). Increasing N results in combinational explosion, and increasing K results in epistasis. There are extensive examples using bit strings to illustrate various problem complexities.

Combinational optimization is the focal point of the next section. The idea here is to either minimize or maximize a result. First simple permutations are talked about. Then, they talk about breadth-first and depth-first search of simple permutation diagrams (trees). Heuristics are used as shortcuts to reduce the search space. The whole idea appears to boil down to trying to find the best way to guess where you are going to find the right answer.

The next section deals with developing binary optimizations. They first discuss how various things can be encoded in binary so they can be used for binary optimizations. Then there is discussion about how binary search space doubles for every additional element, and how you represent binary strings in various dimensions. There is also discussion about the meaning of hamming distance. Since binary strings can become intractable it becomes necessary to determine which bits are the most important in order to narrow the search space. They then go into discussion of various searches such as random and greedy, hill climbing, and simulated annealing. Additionally, they talk about various implementation concepts such as binary vs. gray coding, and examining step sizes and granularity.

The final section is a brief overview of optimization using real numbers. Essentially these problems appear to be similar to combination, and binary optimization methods. However, distance (include step size) is no longer determined in Hamming distance. Typically they are represented using Euclidean distance as calculated in n-dimensional space.