InTech uses cookies to offer you the best online experience. By continuing to use our site, you agree to our Privacy Policy.

Computer and Information Science » Numerical Analysis and Scientific Computing » "New Achievements in Evolutionary Computation", book edited by Peter Korosec, ISBN 978-953-307-053-7, Published: February 1, 2010 under CC BY-NC-SA 3.0 license. © The Author(s).

Chapter 13

Artificial Societies and Social Simulation Using Ant Colony, Particle Swarm Optimization and Cultural Algorithms

By Alberto Ochoa, Arturo Hernández, Laura Cruz, Julio Ponce, Fernando Montes, Liang Li and Lenka Janacek
DOI: 10.5772/8058

Article top

Overview

Social Simulation using agents in an environment related with a wedding.
Figure 1. Social Simulation using agents in an environment related with a wedding.
The ACS algorithm.
Figure 2. The ACS algorithm.
Neighborhood structures for PSO
Figure 3. Neighborhood structures for PSO
Conceptual Diagram of Cultural Algorithms.
Figure 4. Conceptual Diagram of Cultural Algorithms.
Routing-Scheduling-Loading Problem (RoSLoP)
Figure 5. Routing-Scheduling-Loading Problem (RoSLoP)
ACS-DiPro: a solution Methodology of RoSLoP
Figure 6. ACS-DiPro: a solution Methodology of RoSLoP
The ACS algorithm for RoSLoP
Figure 7. The ACS algorithm for RoSLoP
VRPTW example
Figure 8. VRPTW example
Pareto Front
Figure 9. Pareto Front
Pareto front for problem C101 with 25 customers
Figure 10. Pareto front for problem C101 with 25 customers
Pseudocode for a standard cultural algorithm.
Figure 11. Pseudocode for a standard cultural algorithm.
Results using the Simplex Method.
Table 5. Results using the Simplex Method.
Representation of the Dimension in a game board
Figure 12. Representation of the Dimension in a game board
Evaluation of a optimization problem using Baharastar
Figure 13. Evaluation of a optimization problem using Baharastar
Developed tool called Baharastar.
Figure 14. Developed tool called Baharastar.
Different ways of representation for a directed and unweighted graph. Left: Adjacency matrix (A). Centre: Drawn graph. Right: List of pairs (edge list). The triangle motif (in dashed box) is indicated for the three representations. The friendship couple concept is represented in the vertex 5 with 1. Some examples of k, C and b values: for v3, k3=5, C3=0, b3=0.69; v8, k8=3, C8=0.33, b8=0.36; v10, k10=2, C10=1,b10=0. Whit all this fundaments is possible determine that exists the concept of Six degrees of separation in a Social Networking.
Figure 15. Different ways of representation for a directed and unweighted graph. Left: Adjacency matrix (A). Centre: Drawn graph. Right: List of pairs (edge list). The triangle motif (in dashed box) is indicated for the three representations. The friendship couple concept is represented in the vertex 5 with 1. Some examples of k, C and b values: for v3, k3=5, C3=0, b3=0.69; v8, k8=3, C8=0.33, b8=0.36; v10, k10=2, C10=1,b10=0. Whit all this fundaments is possible determine that exists the concept of Six degrees of separation in a Social Networking.
Individual features of an element and classification of friendship preferences of a sample of societies (127 societies) obtained with Cultural Algorithms.
Figure 16. Individual features of an element and classification of friendship preferences of a sample of societies (127 societies) obtained with Cultural Algorithms.
Diorama obtained with Cultural Algorithms which show the clusters of preferences to become friendships, and an example of six degrees of separation.
Figure 17. Diorama obtained with Cultural Algorithms which show the clusters of preferences to become friendships, and an example of six degrees of separation.

Artificial Societies and Social Simulation using Ant Colony, Particle Swarm Optimization and Cultural Algorithms

Alberto Ochoa1, 2, Arturo Hernández3, Laura Cruz4, Julio Ponce5, Fernando Montes6, 2, Liang Li7 and Lenka Janacek8

1. Introduction

The proposal of this chapter is to explain the implementation of collective intelligent techniques to improve results in artificial societies and social simulation using diverse concepts such as argumentation, negotiation and reputation models to improve social simulation of artificial societies implementing dioramas, and multivariable analysis in different application domains for example Logistics. These techniques will be useful for answering diverse queries after gathering general information about a given topic. This kind of collective intelligence will be characterized by: ant colony, particle swarm optimization, and cultural algorithms, each one of these implementing diverse models or agents for simulate a social behaviour. Intelligent agents are used to obtain information to take decisions that try to improve the heuristic optimization needed in different application and fields of knowledge.

First, in section 1 of this paper, we approach different concepts related with Artificial Societies and Social Simulation using different strategies to analyze and model the necessary information to support the correct decisions of the evolving models. In other sections we explain the way to generate a specific behaviour with collective-intelligence techniques –ant colony (section 2), particle swarm optimization (section 3), and cultural algorithms (section 4). In section 5 we apply this knowledge in diverse fields and application domains that needs a heuristic optimization and the more innovative perspectives of each technique. In section 6 we analyse three cases of study: Logistics using a point of view of each one of these techniques (Ant Colony, Particle Swarm Optimization and Cultural Algorithms); Stratagems in an intelligent game board (Cultural Algorithms), and a Friendship Algorithm to demostrate the concept of Six Degrees of Separation in Societies of Memory-Alpha (Cultural Algorithms). Finally, in section 7 we provide our conclusions and our main future research in each technique.

2. Social simulation: basic concepts.

Social simulation is the modeling or simulation, usually with a computer, of social phenomena (e.g., cooperation, competition, markets, social networks dynamics, among others). A subset within social simulations are Agent Based Social Simulations (ABSS) which are an amalgam of computer simulations, agent-based modeling, and the social sciences.

History and Development

The birth of agent based model as a model for social systems was primarily brought by computer scientist (Reynolds, 1994). (Epstein and Axtell, 1996) developed the first large-scale agent model, the Sugarscape, to simulate and explore the role of social phenomena such as seasonal migrations, pollution, sexual reproduction, combat, transmission of diseases, and even culture, more recently.

Types of Simulation and Modeling

Social simulation can refer to a general class of strategies for understanding social dynamics using computers to simulate social systems. Social simulation allows for a more systematic way of viewing the possibilities of outcomes. There are four major types of social simulation:

  1. system level simulation.

  2. agent based simulation.

  3. system level modeling.

  4. agent based modeling.

A social simulation may fall within the rubric of computational sociology which is a recently developed branch of sociology that uses computation to analyze social phenomena. The basic premise of computational sociology is to take advantage of computer simulations in the construction of social theories. It involves the understanding of social agents, the interaction among these agents, and the effect of these interactions on the social aggregate. Although the subject matter and methodologies in social science differ from those in natural science or computer science, several of the approaches used in contemporary social simulation originated from fields such as physics and artificial intelligence.

System Level Simulation

System Level Simulation (SLS) is the oldest level of social simulation. System level simulation looks at the situation as a whole. This theoretical outlook on social situations uses a wide range of information to determine what should happen to society and its members if certain variables are present. Therefore, with specific variables presented, society and its members should have a certain response to the situation. Navigating through this theoretical simulation will allow researchers to develop educated ideas of what will happen under some specific variables (Chira et al, 2008).

Agent Based Modeling

Agent based modeling (ABM) is a system in which a collection of agents independently interact on networks. Each individual agent is responsible for different behaviors that result in collective behaviors. These behaviors as a whole help to define the workings of the network. ABM focuses on human social interactions and how people work together and communicate with one another without having one, single "group mind". This essentially means that it tends to focus on the consequences of interactions between people (the agents) in a population. Researchers are better able to understand this type of modeling by modeling these dynamics on a smaller, more localized level. Essentially, ABM helps to better understand interactions between people (agents) who, in turn, influence one another (in response to these influences). Simple individual rules or actions can result in coherent group behavior. Changes in these individual acts can affect the collective group in any given population.

Agent-based modeling is simply just an experimental tool for theoretical research. It enables one to deal with more complex individual behaviors, such as adaptation. Overall, through this type of modeling, the creator, or researcher, aims to model behavior of agents and the communication between them in order to better understand how these individual interactions impact an entire population. In essence, ABM is a way of modeling and understanding different global patterns.

Current Research

There are two current research projects that relate directly to modeling and agent-based simulation the following are listed below with a brief overview.

  • Agent based simulations of Market and Consumer Behavior, is another research group that is funded by the Unilever Corporate Research. The current research that is being conducted is investigating the usefulness of agent based simulations for modeling consumer behavior and to show the potential value and insights it can add to long-established marketing methods.

  • Agent based modeling is most useful in providing a bridge between micro and macro levels, which is part of what sociology studies. Agent based models are most appropriate for studying processes that lack central coordination, including the emergence of institutions that, once established, impose order from the top down. The models focus on how simple and predictable local interactions generate familiar but highly detailed global patterns, such as emergence of norms and participation of collective action. (Macy & Willer, 2002) researched a recent survey of applications and found that there were two main problems with agent based modeling the self-organization of social structure and the emergence of social order. Below is a brief description of each problem Macy and Willer believe there to be;

  1. "Emergent structure. In these models, agents change location or behavior in response to social influences or selection pressures. Agents may start out undifferentiated and then change location or behavior so as to avoid becoming different or isolated (or in some cases, overcrowded). Rather than producing homogeneity, however, these conformist decisions aggregate to produce global patterns of cultural differentiation, stratification, and hemophilic clustering in local networks. Other studies reverse the process, starting with a heterogeneous population and ending in convergence: the coordination, diffusion, and sudden collapse of norms, conventions, innovations, and technological standards."

  2. "Emergent social order. These studies show how egoistic adaptation can lead to successful collective action without either altruism or global (top down) imposition of control. A key finding across numerous studies is that the viability of trust, cooperation, and collective action depends decisively on the embeddedness of interaction."

These examples simply show the complexity of our environment and that agent based models are designed to explore the minimal conditions, the simplest set of assumptions about human behavior, required for a given social phenomenon to emerge at a higher level of organization (see Figure 1).

media/image1.jpg

Figure 1.

Social Simulation using agents in an environment related with a wedding.

Researchers working in social simulation might respond that the competing theories from the social sciences are far simpler than those achieved through simulation and therefore suffer the aforementioned drawbacks much more strongly. Theories in social science tend to be linear models that are not dynamic and which are inferred from small laboratory experiments. The behavior of populations of agents under these models is rarely tested or verified against empirical observation.

3. Behaviour in group intelligent techniques – ant colony.

This section describes the principles of any Ant System (AS), a meta-heuristic algorithm based on the ant food-search metaphor. The description starts with the ant metaphor, which is a model of real ants. Then, it follows a discussion of how AS has evolved. The section ends with the explanation of ACS, the most common AS version. ACS Algorithm is the base of the logistic application explained in a later section.

3.1. A metaphor of real ants

The AS was inspired by collective behavior of certain real ants (forager ants). While they are traveling in search of food, they deposit a chemical substance on the traversed path. This substance, called pheromone, is detected with their antennae. The Pheromone communication is an effective way of coordinating the activities of these insects. For this reason, pheromone rapidly influences the behavior of the ants: they will tend to take those paths where there is a larger amount of pheromone.

The behavior followed by real ants is modeled as a probabilistic process. Without any amount of pheromone, the ant explores the neighboring area in a totally random way. In presence of an amount of pheromone, the ant follows a path in a controlled random way. With crossed paths, the ant will follow the trail with the largest amount of pheromone with a higher probability. All ants deposit additional pheromone during the traveling, then the food-search process evolves with positive feedback. Since the pheromone evaporates, the non-used trails tend to disappear slowly, increasing the positive feedback effect. In this stochastic process, the best ant receives reward with the highest amount of pheromone, while the worst ant is punished with the lowest amount of pheromone.

3.2. Artificial ant colony

The AS is inspired in the natural optimization process followed by real ants. The algorithm is a general frame than can be applied to the solution of many combinatorial optimization problems. The artificial society, formed by ants, repeats the food-search process. Each ant builds a solution to the optimization problem. The ants share a pheromone structure, which is a common memory (global information) that can be accessed and updated simultaneously.

The AS is a multi-agent system where low level interactions between single ant-agents result in a complex behavior of the whole ant colony. Each ant-agent has incomplete information or insufficient skill to solve a problem. They need the whole colony to get the final objective. To optimize this kind of collaboration, there is not global control, data is decentralized, and the computation is asynchronous. Besides, the ant colonies exhibit an emergent behavior. This emergent conduct happens because they build their result in an incremental manner. As a consequence, the ant colonies are adaptive, complex and distributed multi-agent systems. The AS was originally proposed to solve the Traveling Salesman Problem (TSP), and the Quadratic Assignment Problem (QAP). Now exist a lot of applications like scheduling, machine learning, data mining (Ponce et al., 2009), and others. There are several variants of AS designed to solve specific problems or to extend the characteristics of the basic algorithm. The next paragraph describes the most important variants in order of appearance. Ant Colony Optimization (ACO) was introduced initially by Dorigo (Dorigo, 1991). ACO use two main characteristics: rs and rs. The heuristic information rs is used to measure the predilection to travel between a pair of nodes (r,s). The trails of artificial pheromone rs is used to compute the learned reference of traveling in a determined arc (r,s). It is formed by three algorithms: Ant-density, Ant-quantity and Ant-Cycle. Ant-density and Ant-quantity use the update of pheromone trails in every step of the ants, while Ant-Cycle makes updates after a complete cycle of the ant. A study of the correct configuration of AS for solving TSP concludes that the main parameter is β, the relative importance of the heuristic information. The study establishes that the optimal number of ants is equivalent to the number of nodes of the problem.

Gambardela and Dorigo (Gambardela, 1995) designed the Ant-Q algorithm, which is based on the principles of Q-learning. It was applied for solving the TSP and Asymmetric TSP (ATSP). Ant-Q uses a table of values Q to indicate how good a determined movement from node r to s is. It applies a rule to choose the next node to be visited and uses reinforcement learning to update Q with the best tour of the ants. Max-Min Ant System algorithm (MMAS) was developed by Stützle and Hoose (Stützle, 1996). It uses the elements of AS. However, it modifies three aspects: updating rule, pheromone values, and the next movement. The updating rule was modified to choose the best tour in every cycle, increasing the probability of early stagnation. Maximum and minimum limits for the pheromone trails were established. These limits avoid repeated movements: bounding the influence of the trail intensity, and leading to a higher degree of exploration.

Other variant of AS, named ASrank, was developed by Bullnheimer, Hartl and Strauss. (Bullnheimer et al., 1997). All solutions are ranked according to their fitness. The amount of deposited pheromone is weighted for each solution, such that the best result deposits more pheromone than bad solutions. This algorithm was tested with TSP and VRP instances. The developed technique is based on the Distributed Q-Leaning algorithm (DQL).

3.3. Ant Colony System (ACS)

Dorigo and Gambardela (Dorigo & Gambardela, 1996) improved AS with an algorithm named Ant Colony System (ACS). It presents three main differences with regard to AS: transition rule, global updating and local updating. The transition-state rule is modified to establish a balance between the exploration of new arcs and the priority exploitation of a problem. The global updating rule is applied only to the arcs of the best ant tour. A local updating of the pheromone is done while ants build a solution. ACS was applied to TSP and ATSP with the addition of a local search based on a 3-opt scheme. Figure 2 shows a general scheme of the ACS algorithm.

media/image2.jpeg

Figure 2.

The ACS algorithm.

It is well known that ACS is one of the best ant algorithms. ACS has the best performances and the majority of references (Asmar, 2005). This algorithm was adapted to solve the logistic problem approached in a section 6.1.

4. Behaviour in group intelligent techniques – particle swarm optimization.

The Particle Swarm Optimization (PSO) algorithm is a population-based optimization technique inspired by the motion of a bird flock (Kennedy, J. & Eberhart R., 1995). In the PSO model, every particle flies over a real valued n-dimensional space of decision variables X . Each particle keeps track of its position x , velocity v , and remembers the best position ever visited, PBest. The particle with the best PBest value is called the leader, and its position is called global best, GBest. The next particle's position is computed by adding a velocity term to its current position, as follows:

xt+1=x+vt+1
(1)

The velocity term combines the local information of the particle with global information of the flock, in the following way.

vt+1=w*vt+ϕ1*(PBestxt)+ϕ2*(GBestxt)
(2)

The equation above reflects the socially exchanged information. It resumes PSO three main features: distributed control, collective behavior, and local interaction with the environment (Eberhart et al., 1996). The second term is called the cognitive component, while the last term is called the social component. w is the inertia weight, and ϕ1 and ϕ2 are called acceleration coefficients. The inertia weight indicates how much of the previous motion we want to include in the new one. When the flock is split into several neighborhoods the particle's velocity is computed with respect to its neighbors. The best PBest value in the neighborhood is called the local best, LBest.

vt+1=w*vt+ϕ1*(PBestxt)+ϕ2*(LBestxt)
(3)

Neighborhoods can be interconnected in many diferent ways, some of the most popular are shown in Fig. 3. The star topology is, in fact, one big neighborhood where every particle is connected to each other, thus enabling the computation of a global best. The ring topology allows neighborhoods therefore it is commonly used by the PSO with local best.

PSO is a fast algorithm whose natural behavior is to converge to the best explored local optima. However, attainting flock's convergence to the global optimum with high probability implies certain adaptations (Garro, 2009). The approaches range from modifications to the main PSO equation, to the incorporation of reproduction operators. PSO algorithm has been extended in several directions; in a latter section we show a multiobjective optimization approach to solve a logistic problem, the vehicle routing problem with time windows.

media/image11.jpg

Figure 3.

Neighborhood structures for PSO

5. Behaviour in group intelligent techniques – cultural algorithms.

Cultural algorithms were developed by Robert G. Reynolds in 1994 as a complement to the evolutionary algorithms, this algorithms are bio-inspired in the Cultural Evolution of the Societies, and were focused mainly on genetic and natural selection concepts (Reynolds, 1994). Cultural algorithms operate at two forms: (1) a micro-evolutionary form, which consists of the genetic material that an offspring inherits from its parents (children, grandsons, greats-grandchild, etc), and (2) a macro-evolutionary level, which consists of the knowledge acquired by the individuals through generations (Culture). This knowledge is used to guide the behavior of the individuals that belong to a certain population. Figure 4 illustrates the basic framework of a cultural algorithm. A cultural algorithm operate in two spaces: Population Space and Belief Space. The most of computational problems found at real World, do not have a definitive (final) solution (Desmond & Moore, 1995). Cultural Algorithms uses the culture like a vehicle to store accessible relevant information to the population's members during many generations, and were developed to model the evolution of the cultural component over time and to demonstrate how this learns and acquires knowledge.

media/image12.jpg

Figure 4.

Conceptual Diagram of Cultural Algorithms.

The Population Space are evaluated with a performance function obj(), and an acceptance function accept() can help to determine which individuals are introduce in the Belief Space. Experiences of those chosen elites will be used to update the knowledge / beliefs of the Belief Space via function update(), this function represents the evolution of beliefs in the population. Next, the beliefs are used to influence the evolution of the population. New individuals are generated under the influence of beliefs in the time that were crates. 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 population and belief. The population component and the belief space interact with and support each other, in a manner analogous to the evolution of human culture (Wu & Hsiao, 2008).

List of belief space categories

Normative knowledge A collection of desirable value ranges for the individuals in the population eg. acceptable behavior for the agents in population.

Domain specific knowledge Information about the problem domain where cultural algorithms are applied.

Situational knowledge Specific examples of important events - eg. succesful/unsuccesful solutions

Temporal knowledge History of the search space - eg. the temporal patterns of the searching process

Spatial knowledge Information about the topography of the search space

6. Use of collective intelligence techniques in diverse heuristics optimization.

The use of collective intelligence is found in different areas ranging from biology, sociology, and business to computer science. However, a common definition looks for the identification of certain “intelligence” derived from the efforts of joined entities. The aforementioned entities range from bacteria, animals, human to computer processes. Furthermore, the same definition can be applied, in a broad sense, to action selection and evolutionary robotics.

Evolutionary Robotics employs a quasi-optimal approach to develop autonomous controllers for different kinds of robots. The use of genetic algorithms and neural networks are natural candidates, as the preferred methodology, for developing single evolved neural controllers. These controllers are the result of testing populations of adapted individuals during a refinement process through series of computer-program iterations. Next, pairs or groups of individuals can be evolved together. Following this approach a change in the evolution of one individual can be affected by the change of other related individuals in the group. The latter approach has been identified, as its biological counterpart, as co-evolution that can be cooperative or competitive. A cooperative strategy can be developed to achieve a common task (e.g. pushing objects, solving a common task), whereas in a competitive strategy individuals have to struggle to assimilate some scarce resources (e.g. prey and predator, securing of food stashes). In biology diffuse co-evolution has been referred to species evolving in response to a number of other species, which in turn are also evolving in response to a set of species. Consequently, the identification of collective intelligence is more evident when coevolving cooperative groups.

The development of collective behavior in simulation can be achieved by simple scalable control systems as a form of decentralized control. Therefore, the work of (Kube, 1993) exhibited group behavior without the use of explicit communication. A more recent approach by (Marroco & Nolfi, 2007) set a collective task where a group of four robots developed the ability to reach two different target areas and to group in pairs at each different location. Elementary communication skills were evolved alongside the abilities to reach target areas. In this way, coordination is achieved through stigmergy; nevertheless more elaborated communication can be implemented (Mitri, 2006). On the whole, the individual ability to communicate may be one of the requirements for the development of collective intelligence.

The evolutionary approach has been sufficient to solve problems were cooperation and communication skills are necessary for solving a particular task; in contrast communication arises as a deceptive feature within a competitive scenario. In this scenario a common setting is that of the prey and the predator where both individuals are competing for scoring points either for escaping or capturing each other. The experiment can be expanded to add more preys and predators. It is important to notice that the prey/predator sees the other as a source that needs to be secured/avoided making this an instance of the ‘action selection’ problem (Ochoa et al., 2008).

The action selection problem is related, to the behavior-based approach, and particularly to decision-making when a module takes control of the available actuators until is completed or proves ineffective. In the vertebrate brain, at specific loci, specialized centers of selection can be identified. One of them are the basal ganglia, and recent works support the idea of these nuclei playing an important role in action selection (Prescott et al., 2006). The basal ganglia act as a relay station in the planning and the execution of movements (behavior); hence gathering information from the cortex and motor cortex. The basal ganglia are able to mediate cognitive and muscular processes. Not only the basal ganglia serves as an important center of action selection; in cooperation with the cerebellum and the sensory cerebrum, all them are able to veto muscular contraction by denying the motor areas sufficient activation. In turn, these individual motor elements form more complex patterns, which can be thought as essential elements in the development of intelligence. The development of intrinsic basal ganglia circuitry with evolvable behavioral modules has already been implemented (Montes et al., 2007). Cooperative individuals not only require a society interaction, but the existence of an internal mechanism (e.g. the basal ganglia) that is able to mediate amongst various sensory processes. Nonetheless, these sensory processes need to be augmented when possible. Therefore, individuals need to build up unified internal perceptions based on their available sensory capabilities in order to produce specialized behavior. The work of (Montes et al., 2008) shows how non-standard avoidance can be achieved by extending sensory information through an evolutionary refinement.

The emergence of collective intelligence based on the behavior-based approach requires stepping out from the modeling of selfish solitary individuals to social organisms. Therefore, we need to group our robots and expose them to numerous interactions to assure complex performances at the level of the group. Here, we have identified some common elements in collective robotics: cooperation, intelligence, communication skills, and the integration of sensory information with action selection. All of those accomplished with the use of the evolutionary robotics approach. As a consequence, we believe that we may contribute to the development of robotic collective intelligence by way of social experiments using the artificial evolutionary method.

7. Cases of studies related to cultural algorithms

Many applications inspired in evolving compute have a great value in Logistics. In this section, we present five in special to compare their contributions, the first is related with Ant Colony in Logistic (6.1 Subsection), another is the use of Particle Swarm Optimization in Logistics (6.2 Subsection), the last three are related with Cultural Algorithms (6.3 Subsection) whih is used to improve Bin Packing Algorithm in a problem of Logistics, another is focused in an interactive game board using the problem of negotiation for obtaining a best situation in the game; in the other way is showed the anlysis of a social networking represented with a Dyoram to determine Six degree of separation in a graph.

7.1. Ant colony in logistic

Many manufacturing companies need merchandise delivered with the minimum quantity of resources and in due time. An optimal solution to this logistic problem could save between 5 to 20 % of the total cost of the products (Toth, 2002). However, this is a high-level complex problem. This type of word problem, named recently rich problem, includes several NP-hard sub-problems with multiple interrelated variants. To contribute to this area we approach the bottled-products distribution in a Mexican company. Our proposal includes an innovative ACS solution.

The Routing-Scheduling-Loading Problem (RoSLoP)

RoSLoP involves three tasks: routing, scheduling and loading. They are formulated with two well-known classical problems: Vehicle Routing Problem (VRP) and Bin Packing Problem (BPP). The routing and scheduling tasks are defined through VRP, while the loading task is stated through BPP. Fig. 5 shows this formulation.

media/image13.jpeg

Figure 5.

Routing-Scheduling-Loading Problem (RoSLoP)

RoSLoP includes constrains not considered in VRP and BPP. Previous work approached separately at the most, three variants of BPP (Chan et al., 2005), and five variant of VRP (Pisinger, 2005). Commercial applications have incorporated up to eight variants of VRP without available scientific documentation (OR/MS, 2006). To overcome these limitations, our research tries simultaneously with eleven variants of VRP (Cruz et al., 2008) and five variants of BPP (Cruz et al., 2007).

In order to generalize this problem, RoSLoP is formulated as follows: Given a set of customers with a demand to be satisfied, a set of depots that are able to supply them, and a set of BPP and VRP variants that restrict them, the routes, schedules and loads for vehicles needs to be designed. The Customer demands must be completely satisfied, so the total cost is minimized and the constraints are satisfied.

Methodology of Solution

The assignment of routes and schedules is solved by an ACS algorithm. Three elements complement this algorithm: an auto-adaptive constrained list; an initial search, implemented with the Nearest Neighborhood; and a local search, implemented with 3-opt and Cross-Exchange. The loads are assigned by DiPro algorithm (Cruz et al., 2007). Fig. 6 shows the interaction between the components of ACS and DiPro.

The ACS algorithm in Fig. 7 begins creating an initial solution (line 1). After, it creates an ant colony to minimize the number of vehicles used (lines 3 to 17). In this process, each ant builds a local solution sailing through the adjacent states of the problem. The election of the nodes is done through a pseudo-random selection rule (line 6 to 13). The local solution is compared with respect to the best global solution (line 18) and the updates are done (line 19-20). The stop conditions of lines 17 and 21 are specified with respect to the number of iterations and time of execution respectively. A description of equation and techniques used by ACS are given below.

media/image14.jpeg

Figure 6.

ACS-DiPro: a solution Methodology of RoSLoP

media/image15.jpeg

Figure 7.

The ACS algorithm for RoSLoP

Pheromone Update: Global update of the pheromone trail for customers is done over the best solution. Eq. 4 evaporates the pheromone in all the edges used for the best ant; the evaporation rate is [0,1]. It also adds a reward using the increment rs, which is the inverse of the length of the best global solution. Local update (Eq. 5) is applied every time that one ant travels from node r to node s. It uses0, which is the inverse of the product of the length of the shortest global solution, and the number of visited nodes. Similar equations are used for the vehicle pheromone trail.

τrs(1ρ)τrs+ρΔτrs
(4)
τrs(1ρ)τrs+ρτ0
(5)

Heuristic Information for Customers: The Eq. 6 determines the heuristic information rs used in the customer selection. In this equation, Δtrs is the difference between the current time of node r and the arrival time to the node s, wss is the remaining size of the time window in s, sts is the service time in s, and tcrs is the travel cost from r to s.

ηrs=(Δtrs(wss+sts)tcrs)1
(6)

Heuristic Information for Vehicles: The Eq. 7 calculates the heuristic information ηv used in the selection of the vehicles. In this equation, nvv is the quantity of trips required by the vehicle v to supply all the demands, TMv¯ is the average of the service time of a vehicle v, TRv¯ is the average travel time of a vehicle v, trv is the available service time of the vehicle v, ttv is the total service time of the vehicle v, and idprefv is the predilection-of-use grade of a vehicle v.

ηv=(nvv(TMv¯+TRv¯)trvttvidprefv)1
(7)

Pseudo-random selection rule: An ant k located in node r selects the next node s to move. The selection is made using the pseudo-random selection rule defined in Eq. 8. When a balancing condition is satisfied, the ant selects the best node exploiting the heuristic information and the trails of pheromone. Otherwise, a proportional random exploration is applied. In this equation, q0 is a parameter of balancing between exploitation and exploration, q is a random value in [0,1], is the relative importance of the heuristic information, Nk(r) is the set of available nodes for r.

if qq0s=argmaxsΝk(r){τrsηrsβ}     Si sΝk(r)else           prsx={τrsηrsβsΝk(r)τrsηrsβSi sΝk(r)0otherwise
(8)

Auto-adaptive Constrained List (ACL): The ACL characterizes the instance graph into subsets that have similar conditions. First, a Minimum Spanning Tree (MST) is generated. When the variability of the cost associated to each path in MST is small, all the nodes form a single conglomerate. Otherwise, it forms conglomerates through a hierarchical grouping. The value of the heuristic information rs is modified with a factor, which is a ratio of the cardinality of the groups of r and s.

Experimentation

A sample of three real instances and its solution is shown in Table 1. The database contains 312 instances classified by date order, and 356 products. The algorithm was coded in c# and set with 10 ants, 5 colonies, 40 generations, q0 = 0.9; β = 1; ρ = 0.1. The results show that ACS_DiPro uses an average of 5.66 vehicles. According with our industrial partner, it represents approximately an average saving of 11% in comparison with the manual solution. Besides, the algorithm execution takes 55.27 s. In contrast, a human expert is dedicated on doing this activity all working day.

InstanceORDERSACS_DiPro
Distance TraveledVehicles UsedTime
(s)
13/02/20062081980555.57
06/03/20062241960532.16
09/03/20062692570676.18
Average238.832245.165.6655.27

Table 1.

Solution of real instances of RoSLoP

7.2. Logistic application: solving the vehicle routing problem with time window using PSO.

In transportation management, there is a requirement to provide goods and/or services from a supply point to various geographically dispersed points with significant economic implications. The vehicle routing problem (VRP), which was first introduced by (Dantzig & Ramser, 1959), is a well-known combinatorial optimization problem in the field of service operations management and logistics.

The Vehicle Routing Problem concerns the transport of items between de-pots and customers by means of a fleet of vehicles. In the VRP, the decisions to be made define the order of the sequence of visits to the customers; they are a set of routes. A route departs from the depot and it is an ordered sequence of visits to be made by a vehicle to the customers, fulfiing their orders. A solution must be verified to be feasible, checking that it does not violate any constraint, such as the one stating that the sum of the demands of the visited vertices shall not exceed the vehicle capacity.

media/image29.jpg

Figure 8.

VRPTW example

The Vehicle Routing Problem (see Figure 8) with Time Windows (VRPTW), is a variant of the VRP which considers the available time window in which either customer has to be supplied. The VRPTW is commonly found in real world applications and is more realistic than the VRP that assumes the complete availability over time of the customers.

Each customer requests a given amount of goods, which must be delivered or collected at the customer location. Time intervals during which the customer is served can be specific. These time windows can be single or multiple. A vehicle can not arrive later than a given time, but it can wait if arriving early. In such a case, the goal of the objective function is to minimize the distance travelled and the waiting time. (Salvelsberg, 1985) proved that even finding a feasible solution to the VRPTW when the number of vehicles is fid is itself a NP-complete problem. An overview on the VRPTW formulation and approaches can be found in (Cordeau et al., 2002).

VRPTW Formulation

The VRPTW is represented by a set of identical vehicles denoted by K, and a directed graph G, which consist of a set of customers and a depot. The nodes 0 represents the depot. The set of n vertices denoting customers is denoted N. The arc set A denotes all possible connections between the nodes (including the node denoting depot). All routes start at node 0 and end at node 0. We associate a cost cij and a time tij with each arc (I,j)  A of the routing network. The travel time tij includes service time at customer i. Each vehicle has a capacity limit qk and each customer i, a demand di, i  N. Each customer i has a time window, [ai, bi], where ai and bi are the respective opening time and closing times of i.

No vehicle may arrive past the closure of a given time window, bi. Although a vehicle may arrive early, it must wait until the start of service time ai is possible. It generates a waiting time wk for the route. Vehicles must also leave the depot within the depot time window [a0, b0] and must return before or, at time b0. For eliminating any unnecessary waiting time (Russell, 1995), we assume that all routes start just-in-time wk = 0, that is, we adjust the depot departure time of each vehicle tk = max(0, ai - t0i), i  N.

Multi-Objective Optimization

In Multi-Objective Optimization (MOO), two or more conflicting objectives contribute to the overall result. These objectives often affect one another in complex, nonlinear ways. The challenge is to find a set of values for them which yields an optimization of the overall problem at hand.

A MOO problem is defined as follows:

minxf(x)=[f1(x),f2(x),....,fn(x)]subjectto
(9)
gi(x)0i=1,2,...m
(10)
hj(x)=0j=1,2,....pwherex=[x1,x2,....xd]isthevectorofdecisionvariables.
(11)

The notion of “optimum" in MOO problems difers from that of a single function in global optimization. Having several objective functions the aim is to find good compromises, rather than a single solution.

In 1896, Vilfredo Pareto, an Italian economist, introduced the concept of Pareto dominance (Pareto, 1896). A vector x is preferred to (dominates) a vector if each parameter of x is no greater than the corresponding parameter of y and at least one parameter is less.

Definition1Avectorxissaidtodominatevectory,xy
(12)
ifandonlyifxispartiallylessthany.i{1.2,....n},xiyii{1.2,....n}:xiyi
(13)

Figure 9 shows an example of the Pareto dominance concept between solution vectors B and C; BC due because B is less than C in the two objective functions f1 and f2.

A useful concept in MOO, related with Pareto dominance, is the Pareto front. The Pareto front is composed by a set of non-dominated vectors. Figure 9 shows a comparison between two individuals of the Pareto Front, where A is less than B in objective function f1, but B is less than A in objective function f2; therefore both solution vectors are non-dominated.

The Pareto front is particularly useful in engineering: by restricting attention to the set of solutions that are non-dominated, a designer can make tradfs within this set, rather than considering the full range of every parameter.

media/image38.jpg

Figure 9.

Pareto Front

Multiobjective approaches to VRPTW

The three objectives of the VRPTW were presented: total distance travelled, number of vehicles, and total waiting time. Many existing VRPTW techniques, however, are single objective-based heuristic methods that incorporate penalty functions, or combine the different criteria via a weighting function (Hasnah, 2002; Li & Lim, 2003). However, in the last five years, some hybrid algorithms have been proposed to solve the VRPTW as a MOO problem. (Tan, 2006), and (Ombuki, 2006), employed the travel distance and the number of vehicles to be minimized. (Chitty & Hernandez, 2004), tried to minimize the total mean transit time and the total variance in transit time. (Murata & Itai, 2005) consider to minimize the number of vehicles and the maximum routing time among the vehicles in order to minimize the active duration of the central depot. (Saadah et al., 2004), minimize the number of vehicles and the total distance travelled. This work proposes a hybrid particle swarm MOO algorithm that incorporates perturbation operators for keeping diversity in the evolutionary search and the concept of Pareto optimality for solving the VRPTW as a MOO problem with 3 objectives: minimize total travel distance, minimize number of vehicles and minimize total waiting time.

Tackling Solomon's logistic problem with MO-PSO

Our Multiobjective PSO (MO-PSO) uses a flock size of 100 members,applies a PSO with parameters c1 = 1 and c2 = 1, and w = U(0.5, 1). Total number of function evaluations is 1,000,000. A PC computer with Windows XP and C++ Builder Compiler, Pentium-4 processor at 3.00GHz, 1.00 GB of RAM was used for all experiments. A well-know problem set proposed by (Solomon, 1987) is used to test our model. In these problems, the travel times are equal to the corresponding Euclidean distances. One problems is chosen for the experiment: problem C101 in dimensions 25.

media/image39.jpg

Figure 10.

Pareto front for problem C101 with 25 customers

Figure 10 shows the Pareto front obtained by 10 runs of MO-PSO for the problem C101 with 25 customers. The optimal route obtained by single objective approaches is marked with *SO in the figure. The Pareto front obtained by MO-PSO evidenced the huge waiting time accumulated by the optimal solution reported in the literature with single objective (total distance) approaches. The vector reports a total distance of 191.813620 units attained with only 3 cars, and a total waiting time of 2133.144826 units. As we mentioned above, in this problem, the travel times are equal to the corresponding Euclidean distances. Then, the total waiting time is at least 10 times greater than the total travel time performed for all routes. The total waiting time represents the 57.53% of the total available time (3708 units) of the 3 vehicles, if the depot's window time [0; 1236] is taken as reference. Before, we explained that for eliminating any unnecessary waiting time, we assume that all routes start just-in-time wk = 0, that is, we adjust the depot departure time of each vehicle tk = max(0, ai - t0i), i  N. Therefore, there is no waiting times at the beginning of the route.

Table 2 presents some solutions of the Pareto front found by MO-PSO for the problem C101 with 25 costumers. For example, the solution vector (215.703725, 1584.387467, 4) presents a significant reduction in the total waiting time, but, the total distance and number of vehicles increased respect the solution vector (191.813620, 2133.144826, 3). The solution vector (359.85828, 963.12288, 3) has a waiting time of only 25.9% of the total available time (3708 units) of the three vehicles. Finally, the last solution vector (748.901755, 100.252129,10) presents a reduction of 20 times the waiting time of the solution vector (191.813620, 2133.144826, 3), and it represents the 2.7% of the total available time. Although this solution vector increase at least 3 times the total distance and the number of vehicles of the solution vector (191.813620, 2133.144826, 3).

DistanceWaiting TimeVehicles
191.8136202133.1448263
197.2565862077.7018613
215.7037251584.3874674
276.1835811293.7658003
359.858288963.1228813
443.570466744.9831313
511.430115478.3600004
526.659555466.4301553
589.610396276.0007504
609.975206199.1246295
673.520691172.0036496
748.901755100.25212910

Table 2.

Points in the Pareto front of problem C101 with 25 customers

The empirical results show that reducing the total distance often results in an increment of the total waiting time and vice versa. This happens when two customers that are geographically close may not necessarily be close from the temporal point of view. For the 3 dimensions of the problem C101, the total waiting time is over 50% of the available time of all vehicles occupied in each solution. In real-world problems, this levels of waiting times are not conforming to standard usage. Thereby, placing more emphasis on the distance travelled will often result in unnecessary waiting time.

7.3. Cultural algorithms to improve problems of logistics and combinatorial optimization.

Different problems related with Combinatorial problem son explained in this section, the first is related with Logistics in special with the Bin Packing Problem, the second with the concept of Negotiation in many societies and finally the analysis of six degree of separation in a Social Networking each one implement different strategies to improve the problem and using from different point of view Culturaal Algorithms (CAs).

In the fist problem CAs relies on a communication protocol that makes possible to gain access to the belief space. In relation with the evolutionary component of the cultural algorithm, either a Genetic or an Evolutionary Programming algorithm can be indistinctively used. The cultural algorithm operates at two different levels by means of inheritance: at the belief space at a macro-evolutive manner, whereas at a micro-evolutive sense at the very own population space. Once certain beliefs are acknowledged, this ‘new knowledge’ are assimilated by the population and passed to the belief space (Ochoa, 2008). As a consequence, having an impact on the development of generation of new individuals through posterior epochs.

The use of five particular kinds of knowledge is employed by the cultural algorithm to find, in the search space, a possible solution for a specific problem. This knowledge can be identified as: normative knowledge (acceptable behavior), circumstantial knowledge (successful and disastrous experiences), domain knowledge (objects and their relation in a given domain), historical knowledge (timed behavioral patterns), and topographically knowledge (spatial behavioral patterns) (Reynolds et al., 2005). The implementation of the cultural algorithm was carried out in a standard manner as shown in figure 11.

media/image40.jpg

Figure 11.

Pseudocode for a standard cultural algorithm.

The main contribution of the cultural algorithm to the evolutionary methods is the use of a belief space, and its cultural influence in the population for finding adequate solutions for problems that employ this knowledge space.

Implementation

The prototype is a hybrid intelligent system developed in Matlab 7.6.0, using cultural algorithms. We started by measuring available free space in a standard distribution vehicle. Also we measured the various presentations in cubic centimeters and their volume in liters. We also took into account the demand of the different available presentations, in order to determine the income utility.

PRODUCTCAPACITYDEMAND PERCENTAGEVOLUMEUTILITY
120 liters45 %36500cm3$ 10.00 MXP
21.5 liters15 %26731cm3$ 26.50 MXP
31 liter15 %18435cm3$ 21.60 MXP
40.500 liters25 %18177cm3$ 38.50 MXP

Table 3.

Description of the product.

Once the measurements were made, it was necessary to create an algorithm capable of finding the right selection, in terms of the freight, to optimize income utility and reduce costs of transportation (equation 14). Then the population and the belief space were initialized. The demand of the product is calculated based on their volume and income utility (Table 3). Next, the initial population is evaluated based on the restrictions shown in the same table.

Max r2m2= r1m1+ + + rnmn ...V2m2subject to v1m1+ + + ... vnmn= Vm1, m2.. mn = 0 and integer= 1138425cm3
(14)

where: r: Value per unit.

v: Volume of each unit.

m: are the units of each product type.

V: Maximum capacity in volume.

Any violation of the restrictions will be penalized in such a way that only the best combinations will be obtained. As a result, an average result is obtained and the best individuals are able to influence the next generation based on average individuals. The resultant epoch is a proposed solution for the problem, the halt condition is reached when seven consecutive epochs reach the same result. The result (Time) is the proposed solution, the condition of unemployment is from the recurrence of 7 times without change, ie = or> to the previous ones.

Results

Our initial results are based in a cultural algorithm with an initial population of one hundred individuals. Also, a belief space was created with the same number of individuals. The system was initialized with this population and belief space, and then Variation Operators were applied. The system was iterated until the halt condition was reached producing a nearly optimal solution. The program was used to determine a proper combination of the truckload to maximize profits. The selection of the truckload was based on the volumes of the various water containers and the freight capacity of the truck. In table 4 we observe that after the epoch fifteen the algorithm found a steady solution after eight epochs without improvement.

CAPACITY20 ltrs1.5 ltrs1 liter0.500 ltrs
Quantity16669
UTILITY $848.00 MXP

Table 4.

Results obtained.

A comparison with the Simplex Method reveals that still this method performs better at this stage in the implementation of our cultural algorithm. In table 5 we notice the maximum utility suggested by following this approach is $771.00 MXP, which is $ 77.00 MXP less than in our algorithm.

media/image42.jpg

Table 5.

Results using the Simplex Method.

As a result of our research we develop a hybrid intelligent system that employs a cultural algorithm with artificial evolution for the optimization of space in the delivery of purified water. Here we demonstrated that is feasible to use a cultural algorithm in problems such as the one described here. Our main contribution resides in a real application of the cultural algorithm, which few years ago exist only at the theoretical level.

In the second problem, we focus our attention on a practical problem adapted from the related literature within the Modelling Societies, “the negotiation toward a common well-being” for a set of societies: to find a safe place (a place where attacks don't exist) in an unknown place, inside a hostile environment with unknown dimensions and populated by attackers in unknown locations.

This type of optimization problem can be represented by a two-dimensional matrix, called “dimension”, like is shown in the Figure 12, where A represents the group of societies, M and B the Goal and the attackers (both unknown for the societies) respectively, and the numbers in the dimension represent the experimentation cost for each space. The objective of the cultural algorithm is to find the goal in the minimum number of steps while the spaces are sorted where “attacks” can exist, characterized by penalties of anxiety and uneasiness.

The solution to this problem will be given by a sequence of agents' generations, denoted as “community.” The agents can only know the adjacent spaces to them, like in the colonies carried out by a society that only knows finite distances. The group of spaces around the agent is denominated “quadrant.” From the agent's point of view, this optimization problem is absolutely complex, because we don't know the location of the goal – or if some exists – and it cannot see the world beyond its quadrant. Besides doesn't have any previous heuristic to try to improve the optimization. For better understanding of the selected cultural algorithm used to solve the optimization problem, now we introduce some basic concepts and representations of the artificial culture related to this problem. These representations are abstraction levels located between (the unknown part of the agent), the domain problem (dimension) and the agents. In the algorithm of cultural change, the space of beliefs (beliefspace) by means of the best paradigm (BestParadigm) are set to zero, representing the fact that the culture increases the quantity of pleasure associated with such spaces, giving an incentive to the behavior associated with the best paradigm (BestParadigm).

Agents

The agents are the actors those that will be able to experience each space in the dimension to what Freud refers as the “principle of satisfaction”, according to this, the agent will be able to select the spaces with the lower experimentation cost.

Paradigm

The paradigm is the agents’ personal representation for the space of beliefs (beliefspace) or its personal interpretation of the cultural references. According to Gessler, this is the agent’s cognition and its private vision of the cultural interpretation of the World. The paradigm could represent the best solution for the problem denoted as the best paradigm (BestParadigm).

Space of beliefs (Beliefspace)

The space of beliefs is the collective representation of the real World. In other words, this is the world as it is interpreted by one culture of the community, where the agents find the way to interact and moral values.

Dimension

The dimension is the real world, which never can be entirely known by the agent. This contains the experimentation cost and on which the agents are able to live when the optimization is improved.

Exploration

The agents belonging to one community search inside the dimension for the most appropriated place to be developed (goal). The obtained solution for the agents whom find the goal in the lesser number of steps could be considered as the community “model”, or the best paradigm (BestParadigm). According Geertz, this model or ideology is a “diagram of the psychological and social processes”. The culture could then try to lead the behavior of the new generations of agents by means of this best solution. The best solution for the optimization problem will be given by the agent’s sequence of movements that find the totality of the optimum number of steps. Each agent in the community is leaded by one function that allows it to select the spaces with the lower quantity of anxiety. It can be observed that the satisfaction principle does not affect the strategy for the global resolution of the problem at collective level (culture). To the contrary, this links the agent with an autonomous entity. The culture controls the behavior to be adopted as model, creating a strategy of global action –an ideology- regarding the given problem domain.

The agent selects the cell with the minimum anxiety, as the indicated for the space of beliefs (Beliefspace) adding to this the cultural value, as:

beliefspace (x) = beliefspace (x) + dimension (x)
(15)

Where x is a set of spaces in the dimension

In this research the functions represent the agent-culture interaction and are selected according with the adopted problem.

Therefore, we cannot try to establish a mathematical model of how the cultural process occurs in the real world. Adopting a random function as was shown previously to explain how we insert, into the process, a system of multiple interactions between the agent and the culture. We try to analyze other mathematical representations in our future work.

media/image44.jpeg

Figure 12.

Representation of the Dimension in a game board

Cultural Algorithms Simulator

To prove and validate the theoretical concepts previously presented, we developed a cultural algorithm simulator (Baharastar). Initially our intention was only to create an environment able to carry out analysis and experiments. When cultural algorithms are used, it becomes more difficult of understanding the peculiarities proposed for each solution. Each time that the system has a precise answer, the obtained solution can hardly being duplicated exactly. This property of the evolutionary algorithms in general and of the cultural algorithms in particular, has been little explored or discussed in the literature. The creation of systems with an individuality or “soul”, are our contribution in the area. For such purpose, we select 27 societies described in (Memory Alpha, 2009) and we characterize their behavior using seven base attributes (agility, ability to fight, intelligence, forces, stamina, speed and emotional control), those which allowed describe as well to the society as to the individual.

The development of Baharastar is based on our desire of sharing an intuitive understanding about the treatment for a new class of systems, individuals able to possess unexpected creativity, typical characteristic of living entities. Baharastar is shown in the figure 10, the user has the possibility to choose the starting point and the goal to reach, joined to the places where one can receive an attack by part of the enemy, and the quantity of anxiety associated to each space of the dimension where the societies reside in (agents' communities). Our prototype was developed using JBuilder X platform (see Figure 14).

Experiments

We describe the developed experiments using Baharastar which to contribute in the sense of making evident the importance of the creation of a new methodology to prove and to analyze the obtained results. This was not a trivial task, considering the diversity of behaviors of the provided solutions by Baharastar because it resembles more than a descriptive anthropology than a simple software test. In the first experiment, we compared the performance of 27 communities of 50 agents, and on the other hand 27 communities of 500 agents each one. The associated points to the beginning and goal are shown in the figure 13. The optimal number of steps from the beginning to the goal is 12.

media/image45.jpg

Figure 13.

Evaluation of a optimization problem using Baharastar

One of the most interesting characteristics observed in this experiment is the diversity of cultural patterns established for each community. For the solutions with the same number of steps the provided result for the “beliefspace” is entirely different. The structured scenarios associated to the agents cannot be reproduced in general due they belong to a given instant in the time and space. They represent a unique, precise and innovative form of adaptive behavior which solves a computational problem followed by a complex change of relationships. The generated configurations can be metaphorically related to the knowledge of the community behavior regarding to an optimization problem (to make alliances, to defend from a possible invasion), or a tradition with which to emerge from the experience and with which to begin a dynamics of the process. Comparing the 50 agents of the first community regarding the 500 agents community, this last obtained a better performance in terms of the average number of steps from the beginning to the goal (13.05 versus 14.30), as well as a smaller standard deviation (1.96 versus 2.64). They also had a greater average number of changes in the paradigm (5.85 versus 4.25), which indicates that even the “less negotiating” generations, that explored less interesting parts of the dimension, could optimize their search to achieve better results. In the second experiment, we consider the same scenario for the experiment one, except that after having obtained a solution from a community of 50 agents, we place five near spaces to the goal and we begin with a new community of 500 agents. The new community was informed of the previous cultural configurations but should take into account the new scenario. The comparison among both solutions is not immediate, from the point of view that try to solve different problems. In this experiment, it was surprising to see initially how the community of 500 agents uses the solution offered by the 50 agents, whenever these solutions were close the optimal grade, instead of finding entirely complete new solutions. These results make evident the conservation of a global action strategy which regulates the agents. This can be compared metaphorically with the concept of culture mentioned in the introduction (Suarent & Ochoa et al., 2008).

media/image46.jpg

Figure 14.

Developed tool called Baharastar.

In the third Combinatorial problem, we focused our attention on an adapted practical problem of the Literature related to the Society Modelling, "the friendship relationships" of a set of societies (127 societies represented by one issue – 57 Males & 70 Females) characterized in (Memory Alpha, 2009). The solution to this problem will be given by a sequence of generations of agents, denoted like "community". The agents can only select a set of possible friends based on previous behaviors of theirs societies (Beliefspaces). The ratings in Belief space are normalized associated to popularity of a friend (a society which has weighting qualities), this potential friend receive 12 points, the next one 10, and then 8, 7, 6, 5, 4, 3, 2 and 1 (the graph is built using these relations). This allows each person (society) voting to give positive ratings to ten other people (societies). Each individual (society) cannot vote for itself. The order in which the people (societies) generate points is randomly drawn before the beliefs space of each society starts. After their obtained a group of friends, the graph drawn this friendship links, finally the diorama is built. Results are puts in a scoreboard society by society and represented as an adjacency matrix which is analyzed for determining six degrees of separation, in the same order in which societies established friendship, and ranked according to their aggregate score.

The dynamics of social relationship is a highly complex field to study. Even though it can be found many literature regarding friendship networks, weak links / acquaintances, relationship evolution and so on, we are still far from understanding all the process involved. Social research has shown that people use numerous criteria when they consider the possibility of turning an acquaintance into a friend. But this research considers only two: cultural and technological characteristics of people (society) that determine the emergence and evolution of friendship. After studying the theory available, we have decided to use “Six degrees of separation” in order to model the friendship dynamics and determine the concept of popularity. This principle assesses that the more similar cluster formed by several people are, the stronger their chances of becoming a group of friends. Thus, we attempt to model the processes in which people of different societies turn to be acquaintances, those turn into friends, and some friends into couples, and some couples in a group of friends (more of 4). Select a friend is among the most personal of human choices, and thus it is not surprising that friendship groups tend toward cultural homogeneity. People with the same preferences usually associate with other similar persons, in our case people represented different societies from different quadrants select people with interesting features and similar profiles to become theirs friends with base in its own preferences.

A preliminary step to constructing a friendship modeling is adequate the relationships of people as a graph. A graph (or network) G is defined by a set of N vertices (or nodes) V ={v1, v2,...,vN} and a set of L edges (or links), E ={e1, e2,...,eL}, linking the nodes. Two nodes are linked when they satisfy a given condition, such as two persons participating in the same reaction in a social network. The graph definition does not imply that all nodes must be connected in a single component (friendship relation). A connected component in a graph is formed by a set of elements so that there is at least one path connecting any two of them. Additionally, graphs can also be weighted when links have values according to a certain property. This is the case for social networking, where weights indicate the strength and direction of regulatory interactions. Although graphs are usually represented as a plot of nodes and connecting edges, they can also be defined by means of the so-called adjacency matrix, i.e., an array A of NxN elements aij, where aij=1 if vi links to vj and zero otherwise. Figure 15 summarizes the different ways of representing a graph.

media/image47.jpg

Figure 15.

Different ways of representation for a directed and unweighted graph. Left: Adjacency matrix (A). Centre: Drawn graph. Right: List of pairs (edge list). The triangle motif (in dashed box) is indicated for the three representations. The friendship couple concept is represented in the vertex 5 with 1. Some examples of k, C and b values: for v3, k3=5, C3=0, b3=0.69; v8, k8=3, C8=0.33, b8=0.36; v10, k10=2, C10=1,b10=0. Whit all this fundaments is possible determine that exists the concept of Six degrees of separation in a Social Networking.

Six degrees of separation (also referred to as the "Human Web") refers to the idea that, if a person is one step away from each person they know and two steps away from each person who is known by one of the people they know, then everyone is no more than six "steps" away from each person on Earth. The easier way to understand this is that person A only needs a maximum of five people in between to connect to person B. (Supposing person A and B don't know each other, see right side of Figure 17).

Experiments

We simulated by means of the developed tool the expectations that propagation of friendship and interests of obtain a friend with specific features (see Figure 16). One of the observed most interesting characteristics in this experiment were the diversity of the cultural patterns established by each community because the selection of different attributes in a potential friend: Musical ability, Logical ability, Understanding emotion, Creativity, Narrative ability, spatial awareness & Physical ability. The structured scenes associated the agents cannot be reproduced in general, so that the time and space belong to a given moment. They represent a unique form, needs and innovator of adaptive behavior which solves a followed computational problem of a complex change of relations. Using Cultural Algorithms implementing with agents is possible simulate the behavior of many people in the selection of a group of friends and determinate whom people support this social networking.

media/image48.jpeg

Figure 16.

Individual features of an element and classification of friendship preferences of a sample of societies (127 societies) obtained with Cultural Algorithms.

We first observe that valued friendship (support in troubles related with financial, cultural or energy supplies situations are considered) always plays a very significant role, which should of course not be surprising. Hidden patterns observed in the agents are related with linguistic and cultural distances, and the expectative of selection of a friend whit specific attributes. The nodes with more value in their degree are considered more popular and support the social networking. To get some insight, we run 100 regressions on 100 random samples of half the number of observations, and count the number of times each parameter affect the graph built. Kelemane Society was selected as the most popular by the majority of societies because the attributes offered by it are adequates for others. In Figure 17 is shown the seven societies whom demonstrate the concept of Six degrees of separation.

8. Conclusions.

Evolving Compute offer a powerful alternative for optimization problems including Logistics, a real problem in our times. Nowadays all the societies try to improve Intelligent Systems of Logistics.

media/image49.jpeg

Figure 17.

Diorama obtained with Cultural Algorithms which show the clusters of preferences to become friendships, and an example of six degrees of separation.

Many approaches exist to improve the solution of a real problem using ACs System algorithm, which builds solutions of good quality in a short time. This shows the viability of the development of complex applications based on collaborative intelligent techniques. Specifically, in the logistic of companies which need to distribute their products to obtain significant savings in transportation. This will allow companies to increase their utilities and offer their products in smaller prices.

PSO studies the VRPTW as a tri-objective optimization problem. Specifically, the three dimensions of the problem to be optimized are considered to be separate dimensions of a multi-objective search space: total distance travelled, total cumulated waiting time and number of vehicles engaged. There are a number of advantages in using this MO-PSO model to solve the VRPTW. First, by treating the number of vehicles, total distance, and total waiting time as separate entities, search bias is not introduced. Second, there is a strong philosophical case to be made for treating the VRPTW as a MOO problem. It is not necessary to numerically reconcile these problem characteristics with each another. In other words, we do not specify that either the number of vehicles or the total distance travelled take priority.

CAs provide a comprehensible landscape of the cultural phenomenon. This technology leads to the possibility of an experimental knowledge discovering, created by the community of agents for a given application domain. How much this knowledge is cognitive for the community of agents is a topic for a future work. The answer can be similar to the involved in the hard work of communication between two different cultures. The cultural algorithms offer a long-range alternative for the problems of optimization and redistribution of clusters. For that reason, this technique provides a comprehensible panorama of the cultural phenomenon represented (Ochoa, 2007).

Logistics requiere of the solution propose by many evolving compute techniques (Ant Colony, PSO, and Cultural Algorithms) proportioned knowledge by obtain the best solution in the search space. There are an important number of questions that deserve additional research (Mendoza et al., 2009).

References

1 - D. C. Asmar, A. Elshamli, S. Areibi, 2005 A comparative assessment of ACO algorithms within a TSP environment. Dynamics of Continous Discrete and Impulsive Systems-Series B-Applications & Algorithms, 1 462 467 ,
2 - B. Bullnheimer, R. F. Hartl, C. Strauss, 1997 A New Rank Based Version of the Ant System: A Computational Study, Technical report, Institute of Management Science, University of Vienna, Austria,
3 - W. Chan, et al. 2005 Online Bin Parking of Fragile Objects with Application in Cellular Networks. Tech. report, Hong Kong RGC Grant HKU5172/03E.
4 - C. Chira, A. Gog, D. Dumitrescu, 2008 Exploring population geometry and multi-agent systems: a new approach to developing evolutionary techniques. GECCO (Companion) : 1953 1960
5 - D. Chitty, M. Hernandez, 2004 A hybrid ant colony optimisation technique for dynamic vehicle routing. In Proceedings of Genetic and Evolutionary Computation 2004 (GECCO 2004), 48 59. ACM, June
6 - J. . Cordeau, G. . Desaulniers, J. . Desrosiers, M. Solomon, F. Soumis, 2002The Results using the Simplex Method. VRP with time windows, 157 193. SIAM, Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematic,
7 - R. M. J. Cotterill, 2001 Cooperation of the basal ganglia, cerebellum, sensory cerebrum and hippocampus: possible implications for cognition, consciousness, intelligence and creativity, Progress in Neurobiology, 64 1 May 2001, Pags 1-33.
8 - R. L. Cruz, et al. 2008 DiPro: An Ant Colony System Algorithm to Solve Routing Problems Applied to the Delivery of Bottled Products. Springer-Verlag Berlin Heidelberg, 329 338 .
9 - R. L. Cruz, et al. 2007 DiPro: An Algorithm for the Packing in Product Transportation Problems with Multiple Loading and Routing Variants. Springer-Verlag Berlin Heidelberg, 1078 1088 .
10 - G. Dantzig, R. Ramser, 1959 The truck dispatching problem. Management Science, 6(1):80{91, October
11 - A. Desmond, J. Moore, 1995 “Darwin- la vida de un evolucionista atormentado”. Generación Editorial, São Paulo, Brazil.
12 - M. Dorigo, 1991 Positive Feedback as a Search Strategy. Technical Report. 91-016 91 016 . Politecnico Di Milano, Italy,
13 - M. Dorigo, L. M. Gambardella, 1996 Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem. Technical Report TR/IRIDIA/1996 5 , IRIDIA, Université Libre de Bruxelles,
14 - R. Eberhart, R. Dobbins, P. Simpson, 1996 Computational Intelligence PC Tools. Academic Press Professional, Boston, USA,
15 - J. Epstein, R. Axtell, 1996 Growing Artificial Societies. MIT Press/Brookings Institue, Cambridge, MA,.
16 - L. M. Gambardella, M. Dorigo, 1995 Ant-Q: A Reinforcement Learning Approach to the Traveling Salesman Problem. Proceedings of ML-95, Twelfth International Conference on Machine Learning, Tahoe City, CA, A. Prieditis and S. Russell (Eds.), Morgan Kaufmann, 252 260 ,
17 - B. Garro, H. Sossa, R. Vázquez, 2009 Design of Artificial Neural Networks using a Modified Particle Swarm Optimization Algorithm. International Joint Conference on Neural Networks (IJCNN 2009). June 14 19 ,. Atlanta, Georgia, USA.
18 - N. Hasnah, 2002 Hybrid genetic algorithms for vehicle routing problems with time windows. International Journal of the Computer, the Internet and Management, 10(1):51{67, January
19 - J. Kennedy, R. Eberhart, 1995 Particle swarm optimization. In Proceedings of IEEE International Conference On Neural Networks, 1942 1948 . IEEE, November
20 - R. Kube, 1993 Collective Robotics: From Social Insects to Robots, Adaptive Behavior, 2 2 189 218 .
21 - H. Li, A. Lim, 2003 Local search with annealing-like restarts to solve the vrptw. European Journal of Operational Research, 150(1):115{127, October
22 - M. W. Macy, R. Willer, 2002 From Factors to Actors. Annual Review of Sociology, 28; England;
23 - D. Marocco, S. Nolfi, 2007 Emergence of communication in embodied agents evolved for the ability to solve a collective navigation problem. Connection Science, 19 1 53 74 .
24 - Memory Alpha. 2009 memory-alpha.org (Star Trek World),
25 - R. Mendoza, M. Vargas, J. Muñoz, F. Álvarez, A. Ochoa, 2009 Web Service-Security Specification based on Usability Criteria and Pattern Approach, Special Issue of JSP, Journal of computer, Finland; May
26 - S. Mitri, P. Vogt, 2006 Co-evolution of Language and Behaviour in Autonomous Robots. In The sixth international conference on the Evolution of Language (Evolang6), World Scientific, 428 429 ,
27 - F. Montes, T. J. Prescott, J. Negrete, (2007)’Minimizing human intervention in the development of basal ganglia-inspired robot control’, Applied Bionics and Biomechanics, 43 101 110 -109.
28 - F. Montes, D. Flandes, L. Pellegrin, 2008 Action Selection and Obstacle Avoidance using Ultrasonic and Infrared Sensors. In Frontiers in Evolutionary Robotics, Book edited by: Hitoshi Iba, 327 340 , April 2008, I-Tech Education and Publishing, Vienna, Austria.
29 - T. Murata, R. Itai, 2005 Multi-objective vehicle routing problems using two-fold emo algorithms to enhance solution similarity on non-dominated solutions. In Proceedings of Third International Conference on Evolutionary Multi-Criterion Optimization (EMO 2005), 885 896. Springer, March
30 - A. Ochoa, J. Ponce, et al. 2007 Baharastar- Simulador de Algoritmos Culturales para la Minería de Datos Social. In Proceedings of COMCEV’2007, México,
31 - A. Ochoa, 2008 “Algoritmos Culturales” Gaceta Ide@s CONCYTEG, Año 3. Núm. 31,
32 - A. Ochoa, S. Quezada, J. Ponce, F. Ornelas, D. Torres, C. Correa, de la Torre, & Meza M. 2008 From Russia with Disdain: Simulating a Civil War by Means of Predator/Prey Game and Cultural Algorithms, Artificial Intelligence for Humans: Service Robots and Social Modeling, Grigori Sidorov (Ed.), 978-6-07000-478-0 137 145 , October 2008, Mexico.
33 - B. Ombuki, B. Ross, F. Hanshar, 2006 Multi-objective genetic algorithms for vehicle routing problem with time windows. Applied Intelligence, 24 1 17 30 , February
34 - OR/MS Today: 2006 Vehicle Routing Software Survey. Institute for O. R. and the Manag. Sciences, www.lionhrtpub.com/orms/surveys/Vehicle_Routing/vrss.html.
35 - V. Pareto, 1896 Cours d’Economie Politique. Lausanne, Paris, France,
36 - D. Pisinger, S. Ropke, 2005 A General Heuristic for Vehicle Routing Problems. Technical report, Department of Computer Science, Univ. Copenhagen.
37 - J. Ponce, F. Padilla, A. Ochoa, A. Padilla, León. E. Ponce de, Quezada F. 2009 Ant Colony Algorithm for Clustering through of Cliques, Artificial Intelligence & Applications, A. Gelbukh (Ed.),978-6-07953-670-1 29 34 , November 2009, Mexico.
38 - T. J. Prescott, F. M. Montes, K. Gurney, M. D. Humphries, P. Redgrave, 2006 A robot model of the basal ganglia: Behavior and intrinsic processing. Neural Networks 19 (2006), 31 61 .
39 - R. G. Reynolds, 1994 An introduction to cultural algorithms. Proc. Conf. on Evolutionary Programming,, 131C139
40 - R. Reynolds, B. Peng, R. Whallon, 2005 Emergent Social Structures in Cultural Algorithms”,
41 - R. Russell, 1995 Hybrid heuristics for the vehicle routing problem with time windows. Transportation Science, 29 2 156 166 , May
42 - S. Saadah, P. Ross, B. Paechter, 2004 Improving vehicle routing using a customer waiting time colony. In Proceedings of 4th European Conference on Evolutionary Computation in Combinatorial Optimization (EVOCOP’2004), 188 198 . Springer, April
43 - M. Salvelsberg, 1985 Local search in routing problems with time windows. Annals of Operations Research, 4 1 285 305 , December
44 - M. Solomon, 1987 Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research, 35 2 254 265 , March
45 - T. Stützle, H. H. Hoos, 1996 Improving the Ant System: A detailed report on the MAXMIN Ant System. Technical report AIDA-96 12 , FG Intellektik, FB Informatik, TU Darmstadt;
46 - A. Suarent, A. Ochoa, S. Jons, F. Montes, A. Spianetta, 2009 Evolving Optimization to Improve Dioram’s Representation using a Mosaic Image, journal of computers, august 2009, 4 8 0179-6203x. 734 737 , ed. Academy publisher, Oulu Finland.
47 - K. Tan, Y. Chew, Lee, 2006 2006. A hybrid multiobjective evolutionary algorithm for solving vehicle routing problem with time windows. Computational Optimization and Applications, 34(1):115 151 , May
48 - P. Toth, D. Vigo, 2002 editors. The vehicle routing problem. Monographs on Discrete Mathematics and Applications. SIAM. 363
49 - W. Wu, M. S. Hsiao, 2008 Efficient Design Validation Based on Cultural Algorithms EDAA