Embedding a social fabric component into cultural algorithms toolkit for an enhanced knowledge-driven engineering optimization
The Authors
Robert Reynolds, Department of Computer Science, Wayne State University, Detroit, Michigan, USA
Mostafa Ali, Department of Computer Science, Jordan University of Science and Technology, Irbid, Jordan
Acknowledgements
This research was supported by National Science Foundation (NSF) Integrative Graduate Education and Research Training grant No. 0654014 and by IEEE Walter J. Karplus Summer Research Grant awarded to Mostafa Z. Ali.
Abstract
Purpose – The purpose of this paper is to introduce the notion of a social fabric (SF) in which the expression of knowledge sources (KS) in cultural algorithms (CA) can be distributed through the population. The SF influence function is applied to the solution of selected complex engineering problems and it is shown that different parameter combinations for the SF influence function can affect the rate of solution. This enhanced approach is compared with previous approaches.
Design/methodology/approach – KS are allowed to influence individuals through a network. From a theoretical perspective, individuals in the real world are viewed as participating in a variety of different networks. Several layers of such networks can be supported within a population. The interplay of these various network computations is designated as the “social fabric.” Using this new influence function, when an individual is to be modified, one KS is selected to perform the modification at each generation. The selection process is done via weaving the SF, hence changing the number of individuals that follow a certain KS.
Findings – Simulation experiments show that the choice of influence function has a great impact on the problem-solving phase. For some problems, a social network is not necessary to produce frequent convergence to an optimum. On the other hand, it is observed that the social network can help to focus search by allowing a KS to influence groups of individuals within a network rather than single unrelated individuals. The new approach shows a more focused convergence to optimal values in complex engineering problems with numerous constraints. Also, it is suggested that a SF configuration can be robust in the sense that a configuration that works well for one problem can also perform well in a more complex but unrelated problem. This suggests that a configuration can be evolved to solve suites of problems.
Originality/value – The introduced approach is interesting for the optimization of problems of a non-linear complex nature.
Article Type:
Research paper
Keyword(s):
Social networks; Problem solving; Business process re-engineering; Process efficiency; Optimization techniques.
Journal:
International Journal of Intelligent Computing and Cybernetics
Volume:
1
Number:
4
Year:
2008
pp:
563-597
Copyright ©
Emerald Group Publishing Limited
ISSN:
1756-378X
1 Introduction
Recently, a number of socially motivated algorithms have been used to solve optimization problems. Some of the example algorithms are the particle swarm algorithm (Kennedy and Eberhart, 1995), the ant colony algorithm (Dorigo et al., 1996; Duan, 2005), and the cultural algorithm (CA) (Reynolds, 1978, 1994). These three algorithms all use a population-based model as the backbone of the algorithm and solve problems by sharing information via social interaction among agents in the population.
Figure 1 shows each of these approaches in terms of both a space and time continuum over which the social interactions take place. Notice that both the ant and particle swarm approaches can be found near the lower left end of this continuum, with the social interaction between individuals taking place within limited temporal and spatial dimensions. For example, in particle swarm, agents can exchange their direction of movement and velocity locally with other agents. In the ant algorithm, agents locally exchange information in terms of the density and gradient of a “pheromone” substance that marks their trial. The pheromone is deposited by an ant as it moves along a trail. The frequency of use of a trail is indicated by the amount of pheromone that is deposited relative to its degradation in the environment over time.
CA on the other hand allow agents to interact in many different ways using various forms of symbolic information reflective of complex cultural systems. The basic CA allows individuals to communicate via a shared belief space. The shared space stores five basic types of information that can be shared cognitively or symbolically.
CA (Reynolds, 1978, 1994) can provide a flexible framework in which to study the emergence of complexity in a multi-agent system. Here, we have embedded the CA framework within the recursive porous agent simulation tool (Repast) (North et al., 2006), producing a toolkit that called cultural algorithms simulation toolkit (CAT) (Reynolds and Ali, 2008).
In previous versions of CAT each individual was associated with a single knowledge source (KS) that influenced it. In this paper, we expand the ability of a KS to influence a population through the notion of a SF. The SF represents the extent to which the influence of a KS can spread through a population.
Several authors have used different types of algorithms for solving engineering problems. A quick overview is as follows.
Coello and Mezura-Montes (2002) implemented a version of the Niched-Pareto genetic algorithm (NPGA) (Horn et al., 1994) to handle the constraints for single-objective optimization problems. The NPGA is a multi-objective optimization approach in which individuals are selected through a tournament based on Pareto dominance. However, unlike the first NPGA, Coello and Mezura's approach does not require niches (or fitness sharing (Deb and Goldberg, 1989)) to maintain diversity in the population. The NPGA is a more efficient technique than traditional multi-objective optimization algorithms, because it only uses a sample of the population to estimate Pareto dominance.
Deb and Goyal (1996) proposed a genetic adaptive search to solve engineering optimization problems. He proposed to use a both, binary and real encoding for each solution. This approach was tested on three engineering problems (Kennedy and Eberhart, 1995), making emphasis in problems that have discrete and continuous variables. The obvious drawback of the approach is the need of implementing combined operators for the special encoding adopted.
Mezura-Montes (Goldberg, 1989) presented an enhanced evolutionary algorithm that does not require the definition of extra parameters other than those used by the evolutionary strategy. The implemented mechanism allows the algorithm to maintain diversity during the process.
Hu et al. (2003) applied the particle swarm optimization approach (PSO) to a variety of benchmark engineering problems with considerable success. In this approach individuals communicated current positions and results to their neighbors. Here, individuals interact through their joint control by a common KS. This allows us to integrate design constraints seamlessly into the problem solving process.
Reynolds and Peng (2005) implemented an algorithm that uses the marginal value theorem (MVT) based upon basic predator prey relationships in population biology to influence the individuals in the population and drive the process of obtaining better solutions. The algorithm was comparable in performance with the one presented in Goldberg (1989).
In this paper, we begin by describing the CA approach in Section II. In Section III, we introduce the social fabric (SF) mechanism as an extension of the CA influence function. We then apply it to the solution of two engineering problems: a tension/compression spring design problem and Golinski's speed reducer design problem as examples of complex engineering problems. Section V presents our conclusions and future work.
2 The cultural algorithms configuration
In this section, we discuss the different CA components, communication protocols, and the CAT system.
2.1 Cultural algorithms
The CA is a class of computational models derived from observing the cultural evolution process in nature (Reynolds, 1978, 1994). CA has three major components: a population space, a belief space, and a protocol that describes how knowledge is exchanged between the first two components. The population space can support any population-based computational model, such as genetic algorithms, and evolutionary programming. The basic framework is shown in Figure 2.
A CA is a dual inheritance system that characterizes evolution in human culture at both the macro-evolutionary level, which takes place within the belief space, and at the micro-evolutionary level, which occurs in the population space. Knowledge produced in the population space at the micro-evolutionary level is selectively accepted or passed to the belief space and used to adjust the knowledge structures there. This knowledge can then be used to influence the changes made by the population in the next generation.
The basic pseudo code of CA is shown in Figure 3.
Where, P t represents the Population component at time t, and B t for the belief space at time t. The algorithm begins by initializing both the population and the belief space. Then it enters the evolution loop until the termination condition is satisfied.
At the end of each generation, individuals in the population space are first evaluated with a performance function, obj(). An acceptance function, accept() is then used to determine which individuals will be allowed to update the belief space. Experiences of those chosen elite individuals are then added to the contents of the belief space via function update(). Next, knowledge from the belief space is allowed to influence the selection of individuals for the next generation of the population through the influence() function. The two feedback paths of information, one through the accept() and influence() functions, and the other through individual experience and the obj() function create a system of dual inheritance of both the population and the belief spaces.
The CA repeats this process for each generation until the pre-specified termination condition is met. In this way, the population component and the belief space interact with, and support each other, in a manner analogous to the evolution of human culture.
2.2 Knowledge sources
Five basic categories of cultural knowledge have been identified: normative knowledge, situational knowledge, domain knowledge, history knowledge, and topographical knowledge. Each will be discussed briefly. Throughout the description, we will use the following mathematical symbols:
- n – number of parameters of the optimization problem. It is often referred to as dimensions of an optimization problem.
- Parent individual – X<x 1, x 2, x n>.
- Offspring individual – Y<y 1, y 2, … , y n >.
Also, two functions are used:
- random (v 1, v 2): uniform-randomly generate a number from range (v 1, v 2); and
- mutate (v): Gaussian-randomly generate a number with mean v.
Normative knowledge is a set of promising variable ranges that provide standards for individual behaviors and guidelines within which individual adjustments can be made (Chung and Reynolds, 1998). normative knowledge leads individuals to “jump into the good range” if they are not already there. The normative Knowledge data structure for n variables is shown as in Figure 4.
Situational knowledge provides a set of exemplary cases that are useful for the interpretation of specific individual experience. Situational knowledge leads individuals to “move toward the exemplars.” The global best individual found so far is represented as <gb 1,gb 2, … ,gb n >. The rule for generating an offspring Y<y 1,y 2, … ,y n > from parent X<x 1,x 2, … ,x n > under situational knowledge's influence is expressed by the pseudocode below:
for dimension i=1 to n
if x i <gbi
y i = random (x i , gb i )
else if x i >gb i
y i = random (gb i , x i )
else
y i = mutate (x i )
//generate a value around x i
endif
endfor
The data structure of the situational knowledge is represented as a list of exemplar individuals, as shown in Figure 5.
Topographical knowledge was originally proposed to reason about region-based functional landscape patterns (Jin and Reynolds, 1999). The whole landscape is divided into cells according to spatial characteristics and each cell keeps track of the best individual in its region. Topographical knowledge guides individuals to emulate the cell-best (similar to local optima). The granularity of the grid can be adjusted recursively over time in response to exploration of individuals in the population. The data structure representation is an array of size n where n is the number of cells in the mesh. Each cell in the data structure contains a lower and an upper bound for the n variables ((l, u)1, … , (l, u) n ) indicating the ranges associated with the best solutions found in that cell so far, and a pointer to its children, as shown in Figure 6.
Domain knowledge uses knowledge about the problem domain to guide search. For example, in a functional landscape composed of cones, knowledge about cone shape and the related parameters will be useful in reasoning about them during the search process. The implementation of domain knowledge is detailed as follows:
We define gradients and directions relative to the parent individual X<x 1,x 2, … ,x n >. A direction ΔX is defined as<d 1,d 2, … ,d n >, where d i could be −1, 0, or 1 that represents decreasing, being the same, or increasing x i . The gradient ▽(ΔX) then is defined as: Equation 1 For each individual we calculate and keep its direction with steepest gradient max▽, that is, the direction leads to the fastest improvement in fitness:
if max▽ of parent X>0
//mutate X in its steepest direction
Y = mutate_in_direction (X)
else
//mutate global best in global best's steepest direction
Y = mutate_in_direction (gb)
Endif
Historical or temporal knowledge monitors the search process and records important events in the search process. These important events may be either a significant move in the search space or a detection of landscape change. Individuals guided by the history knowledge can consult those recorded events for guidance in selecting a move direction. Here, we represents the number of change events stored as, (ds 1, … , ds n ), and (dr 1, … , dr n ) are the average environmental changes in distance and direction, respectively, for each one of the n parameters. e 1 through e w are change events. The history knowledge is updated after every change event by updating the history list and the moving averages for each parameter.
History knowledge is implemented as a list of up to m temporal events/points on the search path {P 1, P 2, … , P m }. m is the size limit of the history list, and each P j =<p j,1,p j ,2, … ,p j,n > represents a significant point on the search path. The pseudocode is shown below:
Randomly pick a point P j =<p j,1, p j,2… p j,n >from the list
If parent X is less fit than P j
for dimension i=1 to n
y i = random (x i , p j,i )
//move X toward P j
endfor
else
for dimension i=1 to n
y i = mutate (x i )
endfor
endif
The five categories of knowledge that have been identified in CA systems were added at different times to achieve different problem-solving capabilities (Chung and Reynolds, 1998; Jin and Reynolds, 1999; Reynolds and Saleem, 2003). Reynolds has suggested that this set of KS is complete in that any cultural knowledge can be expressed as some combination of the five. When woven together, they show interesting collective behaviors regarding different roles in the search process, we call these interactions knowledge swarms.
2.3 Interaction of knowledge sources in belief space
So far, we have introduced the five categories of knowledge that have been used in CA systems. When used together, they showed interesting collective behaviors regarding different roles in the search process. Figure 7 shows the internal structure of the belief space in terms of how the different KS influence each other internally. The key issue here is how they are integrated together in guiding the population of problem solvers.
Each KS in the belief space holds a different type of knowledge, and each extracts experience from different groups of individuals. Figure 8 shows the connected knowledge update in the belief space. Normative and topographical knowledge is updated using information about all accepted individual experiences in the current generation, which is indicated by orange in the graph. The other three KS base their updates only on the best performer, which is labeled with magenta in the graph below.
Secondly, although each individual KS bases its updates on new knowledge from the current generation of agents, and its own accumulation of knowledge, there is a difference in that some KS will also use other KS as part of the update process while others do not. From Figure 8, we can see that domain and history knowledge use situational knowledge when they are updated.
The last difference between the KS is that updating is evoked in different situations. Except for history knowledge, all other four KS are frequently updated when no environmental dynamics occur. But when the environment changes, only history, situational and topographical knowledge are updated.
2.4 Communication protocols
The acceptance function selects the individual experiences that will be used to update the belief space at each generation. Here, the acceptance function will take the experiences of the top individuals in the population, and use that information to update all of the knowledge structures.
Individuals are updated using the same framework as in Rychtyckyj et al. (2003). The key here is that the KS communicate with each other through the update process. That is, if one KS produces a new high-performing individual, that individual can be used to potentially adjust each of the other KS. This allows other sources to exploit this new knowledge.
The influence function determines how the KS can influence the population. Here, when an individual is to be modified, one KS is selected to perform the modification at each generation. The selection process is done via weaving the SF, hence changing the number of individuals that follow a certain KS. Thus, as the population moves through the search landscape some KS may become more successful and others less successful. The SF approach is discussed in the Section IV.
3 The social fabric influence function
A wide range of systems in nature and society can be described in terms of complex networks. Examples include the internet, a network of interconnected routers, or human social systems. Civilizations are complex social systems with evident network characteristics (Wilkinson, 2003). Toynbee proposed to treat civilizations as networks of relations. Society in this sense is the total network of relations between the individuals affected by the received signals of knowledge as we imagine it in this work. With recent advances in the modeling of such complex systems it is increasingly recognized that the topology and evolution of real networks are governed by robust organizing principles (Albert and Barabasi, 2002). Consequently, various topologies have been studied as the field gains roots with firm mathematical frameworks and graph theory.
In order to accommodate network models and agent interaction within our CA system (CAT), a new influence function family based upon a SF metaphor was introduced. That will be described in the following sections.
3.1 Concept: the social fabric influence function
The SF can be viewed metaphorically as a living skin created out of the engineered emergence of agents. The tissue fibers are formed by the connectivity of each agent and the generator that determines the topology type of interaction and controls the newly created kinetic sculpture. The purpose is to describe group behaviors and how their interaction can produce emergent phenomena in the engineering design. Behaviors can be mixed and in this network, individual and community-oriented behaviors are expressed and combined. Figure 9 shows a simple example of how the collaborative agents might form a social network that is woven by the knowledge generators or KS.
Here, KS are allowed to influence individuals through a social network. From a theoretical perspective we view individuals in the real world as participating in a variety of different networks. Several layers of such networks can be supported within a population. The interplay of these various network computations is designated as the “social fabric.” This notion of SF has appeared metaphorically in various ways within computer science. For example, IBM among others developed tools to reinforce the “social fabric” whereby designers and programmers interact to solve complex problems (Cheng et al., 2005).
Let the elements of a set ζ represent individuals. Social interactions among individuals ζ are denoted by an undirected graph G(V; E), where: V is the set of vertices, V={v 1;v 2 … ,v I }; an one-to-one mapping of the set of individuals ζ onto itself, and I=|V| is the number of vertices (nodes), (known as the order of the graph, representing its topology); E is a subset of the collection of pairs of vertices and q=|E| is the number of edges, (known as the size of the graph). We say that agent i interacts with agent j if there is an edge in G(V;E) between nodes i and j: let v(i) denote the local neighborhood of agent i:v(i)={ j∈ζ|j≠i, {i,j}∈E}: the number of i's neighbors is the degree of node i:d i =|v(i)|. Graph G(V; E) may be represented equivalently by its adjacency matrix, ?, an I × I matrix whose element (i; j) is equal to 1, if there exists an edge from agent i and to j; and is equal to 0, otherwise.
Although currently agents in the model do not learn, we model them in a framework that will allow them to perform unsupervised reinforcement-based learning in the future. One way to express the reinforcement learning problem is as a Markov decision problem (Sutton and Barto, 1998). A Markov decision problem can be specified in terms of the following variables:
- S, the set of environment states: here the environment of the individual is the KS that is trying to directly influence each of its neighbors, along with the KS that is trying to influence the individual. Thus, for a square topology it is a five-tuple, the nodes direct influence and that of its four neighbors.
- s, is the current state: the specific KS that is trying to directly influence the individual as well as that for each of its neighbors.
- s˙, the new state produced by the agents' action.
-
A, is the set of agent actions. Here, it corresponds to the set of conflict resolution mechanisms that are currently used to decide between the KS s that are trying to directly influence the individual as well as its neighbors. The current conflict resolution actions are given below:
- Most frequently, used resolution (MFU). The resultant KS from all the ones affecting the individual in his neighborhood is the most used one since the beginning of the run (The one with the most hit rate, recorded in the belief space).
- Random resolution. The resultant KS here is a randomly chosen one in the range [1-5].
- Direct resolution. The resultant KS from all the ones affecting the individual in his neighborhood is the direct KS (direct link) from the belief space.
- Least frequently, used resolution (LFU). The resultant KS from all the ones affecting the individual in his neighborhood is the least used one since the beginning of the run (The one with the least hit rate, recorded in the belief space).
- a, is the current action chosen by the agent. Here, the conflict resolution action is fixed for all agents during a run. For example, all agents use the direct influence conflict resolution action. However, in future work reinforcement learning can be used to identify a policy (p i ) decision that determines which conflict resolution scheme is most suited for a given environment.
- R, the reward given to the agent as a result of its action. Here, the result of the action is to select a KS that will then determine the agents' location in the performance landscape. The value of the performance function at that location will be in the individuals reward. Potentially the reward can be determined as a function of previous rewards. Given any current state and action, s and a, together with any next state, the expected value of the next reward is: Equation 2
- Pr(s˙|,sa) is the transition probability of moving into another state s˙ given an action a in state s. The reinforcement learning activity for an agent will then be to find an action a given a state s that produces a new state that is highly valued.
In order to learn these probabilities we will need to add a state value function and action value function that will allow us to evaluate the result of being in one state or another. The agent can then learn to select states that maximize i. However, they are not needed at this time since the policy is selected in advance for all agents. So, while no actual learning is taking place here at the individual agent level the model framework that we are using will support policy evolution in the future when we allow agents to make their own individual decisions. In our current set of experiments we are interested in demonstrating the impact that the SF can make on problem solving even if agents are not learning on their own.
The SF is viewed as a computational tool that influences the action and interaction of the various KS in the belief space with the agents described above in the population space. Informally, we have N sub-networks and M individuals. An individual can be associated with one or more sub-networks. For a given network only certain information is allowed to flow along that network between nodes. Each sub-network can be viewed as being produced by a single thread that links up the participating nodes. Information, matter, and energy can flow along the thread. There is a set of connector threads that are used to weave the threads together to produce the SF. They do that by associating a node in one sub-network with a node in another sub-network such that flow in one network can constrain flows in the other and vice versa. The tightness of the weave is reflected in the number of connections between the networks. If the weave is too tight then there is less flexibility when the system is placed under stress.
3.2 Weaving the social fabric into the CAT system
The networks that comprise the SF can emanate from either the belief space or the population space. In terms of the population, the network could reflect a kinship network or an economic network for example. In terms of the belief space, the network could be the internet, or a local area network, or some other network directly accessible to the KS.
It may be that the KS know something about the networks that they can access but are not sure how those networks are linked up to the low-level social networks of the population. In other words, they may be aware of the outer layer of the SF, but can only infer about what is in the interior lining.
Figure 10 shows an overview of how the influence of a given KS can be spread through the population in the CAT system. The figure shows the initialization step, where each individual first will be affected by one KS (as a special case) that will represent the initial signal to be passed to other individuals. The individual is represented as a node in the landscape, where the number of connections or hops over which it can transmit this information to its neighbors will correspond to its influence, and will be limited by a maximum hop distance. The number of hops can be either 0 or d meaning either no connections or d connections at a time. The result of the influence of a KS on an agent is to position them at a particular point in solution space.
As a simple configuration in the CAT system we can simply specify just one network, one that is accessible to the KS in the belief space. What, we wish to investigate is whether just having access to the SF is sufficient for the KS to improve the performance of the influence function in optimization problem solving as opposed to not having a network to distribute their influence at all.
The process starts where each individual first is affected by one KS (as a special case) that will represent the initial signal to be passed to other individuals. The signal is passed to adjacent individuals in the topology based on the network connectivity. The number of connections or hops over which it can transmit this information to its neighbors corresponds to its influence. The maximum number of hops can be either 0 or d meaning either no connections or d connections at a time.
If networks are important in the problem solving process, even the simplest of network structure can have an impact on the problem solving process. In order to examine the impact of simple networks, we will assume that each individual is connected to a fixed number of other individuals using a constant topology. The topologies that we used here were taken from work in PSO where the impact of various topologies on the communication of local information among particles has been studied.
Several frequently used topologies taken from the PSO literature are supported in CAT. For example, the lbest model is the simplest form of a local topology is known as the ring the ring model. The lbest ring model connects each individual to only two other individuals in the landscape and is shown in Figure 11(a). Another frequently used topology is the gbest topology. In this topology each individual in the network is connected to all the individuals in the network as shown in Figure 11(b). The advantage of the lbest model may lie in its lower convergence rate relative to the gbest model that may reduce the change of premature convergence to a false optimal value (peak). Another topology supported in CAT is the square topology in which each individual has four connections in addition to other individuals in the population.
At each time step, every individual is influenced by one of the KS. In this simplest version, KS do not know anything about the network and the selected individuals' position in it.
The individual then transmits the name of the influencing KS to its neighbors through as many hops as specified. Next, each node counts up the number of KS bids that it collects. It will have the direct influence from the KS that selected it plus the names of the KS transmitted to it by its neighbors. in the current version the KS that has the most votes is the winner and will direct the individual for that time step. In case of a tie, there are several tie breaking rules implemented in CAT. They include, select the “most frequently used KS”, “the least frequently used Knowledge Source,” and “the KS that selected the individual this time,” among others. In later sections, we will compare the performance of the lbest and square topologies when solving an example Engineering problem, used a benchmark.
4 Solving benchmark engineering problems using the social fabric
In this section, we produce two different problems in engineering design. Both are physical mechanism design problems that involve constraints. Within this context we wish to address three different but related questions. The first question is, does the addition of social relations into a CA produce a more efficient or accurate solution for this type of problem over influence functions that support more limited or no relationships between individuals? Secondly, for a given problem is the solution sensitive to the particular parameters of the SF function that are used? Thirdly, can a social configuration that performs well in one constrained design problem perform well in a more constrained and more complex one?
4.1 Benchmark problem 1: tension/compression spring weight minimization
Our first problem is the tension/compression spring weight minimization problem (Figure 12) from Hu et al. (2003) is used to demonstrate the applicability of the SF influence function used by the CA system and implemented in (CAT) on solving real world engineering problems. The design variables are the mean coil diameter D, the wire diameter d and the number of active coils N. The problem is expressed as follows:
Minimize: Equation 3 Subject to: Equation 4 Equation 5 Equation 6 Equation 7 The variables take the following ranges: Equation 8
4.1.1 Constraint handling
In the presence of constraints, not all generated solutions may satisfy those constraints. A generated individual that does not satisfy these constraints is called infeasible. Infeasible solutions can come from the initial population, where individuals are randomly generated from the search space; or they can also from offspring generations, either generated by a feasible parent or an unfeasible parent. It is possible that an individual generated from a feasible parent can violate the given constraints. There are many different methods for handling infeasible solutions and the typical approaches are as follows (Michalewicz, 1996). Here, we use the penalty function method as given below:
if (individual satisfies all constrains)
fitness = obj(individual)
else
fitness = UN-FEASIBLE-VALUE
endif
This method penalizes infeasible solutions by imposing penalties on individuals that violate constraints. This method is simple to implement and widely used, but should be cautious about the time in evaluating illegal individuals. The reason for this choice is that we feel the culture should quickly learn what is required to survive in this environment; otherwise it is not a viable approach.
4.1.2 Experimental framework
The parameters used for running the simulation are presented in Table I. A total of 20 runs per parameter configuration were performed. The number of individuals is fixed to 100, and the total number of generations is 1,000. If a tie is found when the SF is woven then the resolution approach used is the KS that directly affected the individual at that step.
When plotting the population swarms, individuals are plotted in different iconic shapes in order to indicate which KS is in control of the individual location at that point in space. The scheme used to discriminate KS is showed in Table I.
4.1.3 Analysis of results
The algorithm used by Reynolds and Peng (2005) is an earlier version of the influence function. They used the MVT as the influence function that used a basic relationship associated with animal populations, predator-prey. That algorithm found results comparable to those presented in Coello and Mezura-Montes (2002). Algorithms presented in Coello and Mezura-Montes (2002) were based on 100 individuals and 36,000 evaluations for the objective function as can be seen in Table II. We will compare our algorithm's results to the results for that approach (Reynolds and Peng, 2005).
The MVT approach used by Reynolds and Peng (2005) did not assume that there any kind of connection between the individuals in the population space. KS will pass their signals to the individuals at each time step. The SF approach uses different topologies to pass abstract information obtained from the KS and then weaves together the SF to allow the individuals to pass the received information through the assumed used topology. The amount of interaction appears to affect the way the system solves the presented problem of a certain complexity. The results shown in Table III present a statistical comparison between our new approach and the one presented in Reynolds and Peng (2005). Using the t-test, the p-values found from comparing the MVT approach presented in Reynolds and Peng (2005) and ours are shown in Table IV. Statistical results show a statistical significant difference between both approaches.
The population swarm shown in Figures 13-15 show the population (individuals) moving within the whole space for both strategies used by our SF approach.
Each individual is shape coded to reflect the KS that has influences it in that generation. The best individual of a generation is stressed using a big cross X. Since the results of d and N, and d and D are similar we discuss only d and D. Figure 13(a) and (b) show a sample of the constructed SF-lbest, and SF-square topologies, respectively.
Figures 14(a) and 15(a) show the initial generation when running the system using the SF-lbest and the SF-square, respectively. The topographic knowledge followers draw the situational, normative, and most of the domain knowledge followers. By the last generation most of the individuals are swarming around the best. Topographic knowledge individuals are still exploring the space as shown in Figures 14(b) and 15(b).
When we did the best trace plots, the search path formed by the best individuals from each generation/year is plotted in a 2D style.
In the plot, the search space is projected onto two of the three total dimensions and the best individual so-far is displayed as a white “+” with its other dimension value(s) labeled out at the top of the plot, thus it looks like the best is in a “two dimensional space.” For a search space with n dimensions, there are n*(n−1) such kinds of projection. The fitness contour map is plotted as colored areas where all points in the “two dimensional space” have the same value(s) as the current best individual on the other dimension(s). In this contour map, color (darkness/lightness) is used to indicate the fitness of the points in the search space and the lighter ones have lower fitness thus are better individuals since the problem is one of minimization. At the same time, the infeasible solutions are represented with the lightest color level 0 thus forming the large background area for the enclosed feasible solutions. Notice that in Figure 16(a) and (b), the best trace plot for the SF-lbest shows how wire diameter d converges as late as the generation 819 and exhibits the most potential for exploration, where the best obtained by that time was 0.012892.
We will focus the rest of our discussion on these 2D. The best trace plot for the SF-square converges as early as the generation 385 to the value 0.01269 as in Figure 17(a) and (b).
The power behind the algorithm lies in using the bounding boxes that the system calculates at each time step for each of the KS. A dimensions of the bounding box represents the standard deviation along each dimension of the box for all of the individuals, “dots,” produced during that generation by the KS for the mutation process. It is considered to be the focus of the generation process by each KS. The main idea is to observe how these bounding boxes of the KS interact (overlap area), and how focused these bounding boxes are within the landscape at each time step. The branching phase of the algorithmic process is shown in Figures 18(a) and 19(a), where initially the bounding boxes associated with the topographic and domain KS cover most of the space. Over time the bounding boxes for the fine-grained search process have separated from those for the coarse-grained phase (focused search vs wider search) and surrounded the optimal value for this pair of dimensions.
These bounding boxes are effectively channeling new individuals into this area. This is viewed in Figures 18(b) and 19(b) for the SF-lbest and SF-square, respectively. Notice that the distances between the centers of the bounding boxes for the square topology is now much less than the distances between the centers of the bounding boxes in the lbest case.
The amount of interaction between the KS is viewed as the degree of overlap between their bounding boxes As shown in Figures 18(b) and 19(b), this overlap is higher in Figure 19(b) than in Figure 18(b) with respect to the overall area of each of the bounding boxes. For these reasons, the square topology produces a more focused and guided search in the landscape here than the lbest approach.
4.2 Benchmark problem 2: Golinski's speed reducer design
Golinski's speed reducer problem (Golinski, 1970; Ray, 2003) is one of the most well-studied problems of the NASA Langley multidisciplinary design optimization test suite. This problem represents the design of a simple gearbox such as might be used in a light airplane between the engine and propeller to allow each to rotate at its most efficient speed. The gearbox is shown in Figure 20 and its seven design variables are labeled below. The design is shown in Figure 21.
Golinski modeled the speed reducer so as to minimize its weight subject to constraints on bending stress of the gear teeth, traverse deflections of the shafts and stresses in the shaft. About seven variables are used for describing the problem, these are:
- x 1, face width.
- x 2, module of teeth.
- x 3, number of teeth in the pinion.
- x 4, length of the first shaft between bearings.
- x 5, length of the second shaft between bearings.
- x 6, diameter of the first shaft.
- x 7, diameter of the second shaft.
The third variable is an integer, while the rest of the variables are continuous. The goal is:
Minimize: Equation 9 Subject to: Equation 10 where 2.6≤x 1≤3.6,0.7≤x 2≤0.8,17≤x 3≤28,7.3≤x 4≤8.3,7.8≤x 5≤8.3, 2.9≤x 6≤3.9,5.0≤x 7≤5.5
4.2.1 Experimental frame work
The minimization of the weight of a speed reducer is the most complex problem among the benchmark problems we have available in the CAT system in terms of number of dimensions, problem constraints, domain constraints, and complexity of the environment surface. The configured parameters are shown in Table V. The topology that worked best for the tension spring problem is now employed on this more complex problem. The question is whether the SF configuration that worked well for the previous problem is still effective for a more complex problem? In other words, can a well-chosen social network be applied to support multiple problems simultaneously? The more omnivorous a configuration is, the more robust it will be in environments with changing problem structures.
4.2.2 Analysis of results
In terms of dimensions (x 2, x 3), Topographic knowledge produces a result that is near the optimum during the coarse-grained or exploratory search phase. This attracts the Situational, Domain, Normative, and History KS in the fine-grained or exploitation phase, as shown in Figures 22-25.
The meta-level bounding boxes that generate individuals in the population from generation 1 through 8 when the optimum has been found are shown in Figures 26-29. The bounding boxes for topographic and domain KS encompass most of the problem space in this dimension in Figure 26. Notice that by generation 7, the bounding box for Situational knowledge has now focused the search around the optimal value and is channeling new individuals into that area primarily. By generation 8, the other bounding boxes have very small areas which show how focused and specialized they are now.
Table VI describes the parameters in our experimental configuration and the template for our experiments. Each combination of the frequency, configuration, number of hops, and conflict resolution parameter was run 30 times for 1,000 generations for a population with 100 individuals.
The averaged “current best” over 1000 generations for each of the 30 runs for our controller, square-direct-3, versus a selected subset of other manually derived configurations is shown in Figure 30. Included in the subset are two other configurations that are close to ours in terms of variable values, lbest-direct-3 and gbest-direct-3, along with two earlier versions of the cultural algorithm influence function without the SF, MVT, and Saleems' (random function). In the latter case, individuals are randomly assigned to KS at each time step.
Notice that our configuration converges faster to a slightly better solution on average. Table VII compares the different topology-configurations of the social fabric influence function (SFI) using direct resolution, applied every three time steps to the social network. The table shows that the best average weight is obtained using our “Square-direct-3” compared with the other used topologies.
The next question is why does it do better? The answer can be inferred from Table VIII where we give the performance of our configuration, SFI (SQUARE), against the two earlier versions of the Cultural Algorithm Influence Function, Random selection (Saleem), and the MVT. Notice that by using the parameterized SF, the search has been focused substantially as indicated by the reduced standard deviation in the SF approach. This more focused search produced better statistics across the board with an improved “best,” “average,” and “median” score. And, the worst score is not as bad as the other two as well. Using the derived configuration, the best weight was 2,996.974 Kg, the mean weight when we repeated the runs 30 times, 1,000 generations each, was 3,000.278. The worst value obtained was 3,007.301. The gBest approach ranked second with a mean weight of 3,011.062 Kg. The lBest approach ranked third with mean weight of 3,015.026 Kg. The MVT did not perform as well as either of these approaches but is still better than Saleem's random influence function.
The good configuration for the previous problem when applied to a different and more complex problem still outperformed influence functions that did not use social relations, as well as other social configurations. This suggests that social configuration can be robust, and a configuration that emerges to solve one problem can be applied to other more complicated problems.
4.2.3 Discussion of results for the SpeedRreducer
From the previously presented results, it is clear that the generated configuration for the optimization of Golinski's speed reducer problem that “applies” the square topology communication to “spread” the influence of the agents in the social network every three generations and “resolves” conflicts between agents using the direct approach outperforms various other parameter combinations of the MVT-SF Influence Function along with earlier versions of the influence function without the SF. A comparison with other approaches from the literature shows that applying our SFI function compares well with the other used approaches and converges to a feasible solution in every single run. The (1 + λ) evolutionary strategy (Coello and Mezura-Montes, 2002) produces a mean weight of 3,088.778 for the speed reducer problem. The remaining techniques failed to consistently reach the feasible region. So, while our results are not strictly comparable to theirs since the run parameters are different, the results based upon an incentive-based approach are clearly competitive with them.
5 Conclusions
We have described an influence function for CA that uses social relationships to spread the influence of KS through a network. This approach, in general, out performs CA influence functions based on a more limited set of relationships such as those found in biological populations (predator prey) and pure random assignment. This SF function here allows the KS to distribute their influence through a social network and its' accuracy and efficiency carries over across problems suggesting that the SF is not only a powerful but potentially robust tool.
However, within a given social configuration there is certainly room for improvement. For example, when we apply the SFI to two different engineering optimization problems, it was clear that within each problem different social networks performed at different levels. Thus, even though a social network can improve performance with a problem, fine-tuning of its parameters can improve performance for a given problem.
Also, both of the problems presented are physical design problems that are highly constrained. Thus, the SF can be useful in exploiting those constraints. On the other hand, it may be the case that for completely random or chaotic performance landscapes the presence of a SF is not necessary in terms of improving performance. A conjecture then is that as physical design problems become more patterned and constrained, the more knowledge is available to be exploited by the social network. A related question for future work is, if the system starts with no social relations and is presented with an escalating sequence of complex problems, is there a “tipping point” at which a phase shift occurs in the sense that any social network configuration will outperform a system that has no network configuration. In other words, at what level of complexity is there a problem for which even the simplest social network will always outperform a network without one? An answer to this question begins to associate that complexity of civilization with the problems that it can solve.
Equation 1
Equation 2
Equation 3
Equation 4
Equation 5
Equation 6
Equation 7
Equation 8
Equation 9
Equation 10
Fixed graphic 1
Fixed graphic 2
Figure 1Scale of social interaction: the emergent properties depend upon the scale at which the interaction takes place
Figure 2The framework of cultural algorithm
Figure 3Basic pseudo-code for cultural algorithm
Figure 4The structure of normative knowledge
Figure 5The structure of situational knowledge
Figure 6The structure of topographical knowledge
Figure 7Structure of the belief space
Figure 8Knowledge update in belief space
Figure 9Social network formed by agents taken as a prototype for the target system via the CAT system
Figure 10Embedded social fabric component in CAT
Figure 11Topologies used in the social fabric model for connection between individuals: (a) lbest ring topology; (b) gbest topology
Figure 12Tension/compression string
Figure 13A sample social fabric swarm plot for the spring design problem: (a) using lbest; (b) using square topology
Figure 14Population swarm of dimension d+D using the lbest topology: (a) plotted at generation 1; (b) plotted at generation 1,000
Figure 15Population swarm of dimension d+D using the square topology: (a) plotted at generation 1; (b) plotted at generation 1,000
Figure 16Best trace plot of dimension d+D using the lbest topology
Figure 17Best trace plot of dimension d+D using the square topology: (a) plotted at generation 1; (b) plotted at generation 819
Figure 18Best trace plot of dimension d+D using the square topology: (a) plotted at generation 1; (b) plotted at generation 819
Figure 19Best trace plot of dimension d+D using the square topology: (a) plotted at generation 1; (b) plotted at generation 819
Figure 20The gearbox used in Golinski's speed reducer problem
Figure 21Speed reducer (gear design)
Figure 22Population swarm plot of dimension (x
2, x
3) at generation 1
Figure 23Population swarm plot of dimension (x
2, x
3) at generation 3
Figure 24Population swarm plot of dimension (x
2, x
3) at generation 5
Figure 25Population swarm plot of dimension (x
2, x
3) at generation 8
Figure 26Knowledge swarm plot of dimension (x
2, x
3) at generation 1
Figure 27Knowledge swarm plot of dimension (x
2, x
3) at generation 3
Figure 28Knowledge swarm plot of dimension (x
2, x
3) at generation 5
Figure 29Knowledge swarm plot of dimension (x
2, x
3) at generation 8
Figure 30“Average-curves” comparison for configuration five with the MVT, and Saleem's influence function of Golinski's speed reducer design
Table IShape scheme for KS
Table IIStatistical values from different approaches for the tension/compression spring design (eight Mezura)
Table IIIStatistical values from the MVT approach and our approach (the social fabric) for the tension/compression spring design
Table IV
P-values from comparing the Mvt approach with our new approach
Table VParameters used for problem P6 using square top
Table VIParameters used for Golinski's problem using square topology
Table VIIStatistical comparison of the different topology-configurations of the SFI using direct resolution, applied every three years to the social network
Table VIIIStatistical comparison of the performance of the SFI-best configuration with other techniques from literature
References
Albert, R., Barabasi, A. (2002), "Statistical mechanics of complex networks", Review of Modern Physics, Vol. 74 No.47, pp.48-94.
Cheng, L., Patterson, J., Rohall, S., Hupfer, S., Ross, S. (2005), "Weaving a social fabric into existing software", paper presented at AOSD 2005 – Fourth International Conference on Aspect-Oriented Software Development, Chicago, IL, March, .
Chung, C., Reynolds, G.R. (1998), "CAEP: an evolution-based tool for real-valued function optimization using cultural algorithms", International Journal on Artificial Intelligence Tools, Vol. 7 No.3, pp.239-91.
Coello, C.A., Mezura-Montes, E. (2002), "Handling constraints in genetic algorithms using dominance-based tournaments", in Parmee, I. (Eds),Proceedings of the Fifth International Conference on Adaptive Computing Design and Manufacture (ACDM 2002), University of Exeter, Exeter, Vol. 5 pp.273-84.
Deb, K., Goldberg, D.E. (1989), "An investigation of Niche and species formation in genetic function optimization", in Schaffer, J.D. (Eds),Proceedings of the Third International Conference on Genetic Algorithms, George Mason University, Morgan Kaufmann Publishers, San Mateo, CA, pp.42-50.
Deb, K., Goyal, M. (1996), "A combined genetic adaptive search GeneAS for engineering design", Computer Science and Informatics, Vol. 26 No.4, pp.30-45.
Dorigo, M., Maniezzo, V., Colorni, A. (1996), "Ant system: optimization by a colony of cooperating agents", IEEE Transactions on Systems, Man, and Cybernetics-Part B, Vol. 26 No.1, pp.29-41.
Duan, H.B. (2005), Ant Colony Algorithms: Theory and Applications, 1st ed., Science Press, Beijing, .
Goldberg, D.E. (1989), Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley, Reading, MA, .
Golinski, J. (1970), "Optimal synthesis problems solved by means of nonlinear programming and random methods", Journal of Mechanisms, Vol. 5 pp.287-309.
Horn, J., Nafpliotis, N., Goldberg, D.E. (1994), "A Niched Pareto genetic algorithm for multiobjective optimization", Proceedings of the First IEEE Conference on Evolutionary Computation, IEEE World Congress on Computational Intelligence, IEEE Service Center, Piscataway, NJ, Vol. 1 pp.82-7.
Hu, X., Eberhart, C.R., Shi, Y. (2003), "Engineering optimization with particle swarm", Proceedings of the 2003 IEEE Swarm Intelligence Symposium, IEEE Press, Indianapolis, IN, pp.53-7.
Jin, X., Reynolds, G.R. (1999), "Using knowledge-based evolutionary computation to solve nonlinear constraint optimization problems: a cultural algorithm approach", Proceedings of the 1999 Congress on Evolutionary Computation, IEEE Press, Washington DC, pp.1672-8.
Kennedy, J., Eberhart, R.C. (1995), "Particle swarm optimization", Proceeding of the IEEE International Conference on Neural Networks, IEEE Service Center, Perth, pp.12-13.
Michalewicz, Z. (1996), Genetic Algorithm + Data Structures = Evolution Program, 3rd ed., Springer, New York, NY, .
North, M.J., Collier, N.T., Vos, J.R. (2006), "Experiences creating three implementations of the repast agent modelling toolkit", ACM Transactions on Modelling and Computer Simulation, Vol. 16 No.1, pp.1-25.
Ray, T. (2003), "Golinski's speed reducer problem revisited", AIAA Journal, Vol. 41 No.3, pp.556-8.
Reynolds, G.R. (1994), "An introduction to cultural algorithms", Proceedings of the 3rd Annual Conference on Evolutionary Programming, World Scientific Publishing, London, pp.131-9.
Reynolds, G.R., Saleem, S. (2003), "The impact of environmental dynamics on cultural emergence", Festschrift, in Honor of John Holland, Oxford University Press, New York, NY, Vol. 1-10.
Reynolds, R.G. (1978), "On modeling the evolution of hunter-gatherer decision-making systems", Geographical Analysis, Vol. 10 No.1, pp.31-46.
Reynolds, R.G., Ali, M. (2008), "Computing the social fabric: the evolution of social intelligence with a computational framework", IEEE Computational Intelligence Magazine, Vol. 3 No.1, pp.18-30.
Reynolds, R.G., Peng, B. (2005), "Cultural algorithms: computational modeling of how cultures learn to solve problems: an engineering example", Cybernetics and Systems, Vol. 36 No.8, pp.753-71.
Rychtyckyj, N., Ostrowski, D., Schleis, G., Reynolds, G.R. (2003), "Using cultural algorithms in industry", Proceedings of IEEE Swarm Intelligence Symposium, IEEE Press, Indianapolis, IN, .
Sutton, R.S., Barto, A.G. (1998), Reinforcement Learning: An Introduction, MIT Press, Cambridge, MA, .
Wilkinson, D. (2003), "Civilizations as networks: trade, war, diplomacy, and command-control", Journal of Complexity, Vol. 8 pp.82-5.
About the authors
Fixed graphic 1Robert Reynolds received the Bachelor Degree in Computer Science at the University of Michign-Dearborn, Michigan, USA, in 1970. He finished his Master’s in Computer Science at the University of Michigan-Ann Arbor, Michigan, USA in 1978. He finished his PhD in computer science at the University of Michigan-Ann Arbor, Michigan, USA in 1979. Reynolds is a Professor of Computer Science at Wayne State University and an Associate Research Scientist in the Museum of Anthropology at the University of Michigan-Ann Arbor. His research interests include artificial intelligence, evolutionary computation, and cultural algorithms. He is a member of the IEEE, the IEEE computer society, the ACM, the American Association of Artificial Intelligence, the Evolutionary Programming Society, the American Association for the Advancement of Science, and the Society for American Archaeology. His personal homepage is: www.ai.cs.wayne.edu. Robert Reynolds is the corresponding author and can be contacted at: reynolds@cs.wayne.edu
Fixed graphic 2Mostafa Ali received the Bachelor Degree in Applied Mathematics at Jordan University of Science and, Irbid, Jordan, in 2000. He finished his Master’s in Computer Science at the University of Michigan-Dearborn, Michigan, USA in 2003. He finished his PhD in computer science at Wayne State University, Michigan, USA in 2008. He is a professor of computer science at Jordan University of Science and Technology. His research interests include artificial intelligence, evolutionary computation, cultural algorithms, data mining, and image processing. He is a member of the IEEE, the IEEE computer society, and the ACM, the American. His personal homepage is: www.cs.just.edu.jo/people/faculty/mostafa
