You are here

Swarm intelligence

21 January, 2016 - 14:46

It is known that classic optimization algorithms do not offer an efficient manner of solving involved large scale combinatorial and highly non-linear problems. The main characteristics of these classic algorithms are that they are characterized by an accentuated inflexibility concerning the need to adapt the algorithm to the proposed problem (Chan & Tiwari, 2007). So a set of assumptions is made and their truthfulness is not always easy to prove and it can easily affect the quality of the returned solution.

In this context, the development of nature-inspired algorithms is well motivated and it proposes a new perspective in solving these categories of problems by providing in most cases a better solution comparative to the classical optimization algorithms.

A branch of these nature-inspired algorithms is known as Swarm Intelligence and includes algorithms as Particle Swarm Optimization, Ant Colony Optimization, Artificial Bee Colony, and so one.

Swarm Intelligence was defined in 1989 by Gerardi Beni and Jing Wang as the collective behaviour of decentralized and self-organized systems. Swarm Intelligence Systems are composed of a population consisting in simple agents that interact locally with one another and with the environment by following simple rules (Chan & Tiwari, 2007). The agents’ behaviour is defined by a certain degree of randomness and their social interactions are inspired by nature. Swarm Intelligence techniques are based on applying behavioural response to the environmental state, which serves as a work state memory and do not depend on specific agents.

In 1994 Mark Millonas mentioned the five basic principles of swarm intelligence (Stanarevic & Bacanin, 2011):

  • The proximity’s principle – each individual is able to memorize space and time computations;
  • The quality’s principle – each individual is able to respond to the quality of the environmental factors;
  • The diverse response’s principle – each individual “should not commit its activities along excessively narrow channels”.
  • The stability’s principle – the changes considering the individuals behaviour should not be influenced by the environment changes;
  • The adaptability’s principle –individuals behaviour can be changed when it’s worth his computational price.

General AssignmentProblem is represented by the necessity of assigning with a minimum cost a set of tasks to a set of agents with limited capacity. Each task can be assigned to single agents and uses certain of this agents’ resource.

This study aims to propose a solution for a General Assignment Problem using a Swarm Intelligence technique, represented by Artificial Bee Colony algorithm.

Artificial Bee Colony represents a Swarm Intelligence technique that tries to model the natural behaviour of real honey bees in food foraging. By performing the waggle dance during the food procuring the bees can successfully share information about the direction and the distance of food and also about the amount of nectar available at the indicated location (Chan & Tiwari, 2007).

The studies considering bee comportment shows that the waggle dance contains a series of information about the food source: the direction of the bees’ body indicates the direction of the food in relation to the sun, the waggles intensity is proportional to the distance to the food location and the dance length indicates the amount of nectar available at the food source.

In 1996 Yonezawa and Kikuchi developed an algorithm after closely observing the foraging behavior of honey bees and indicated the importance of group intelligence (Yonezawa & Kikuchi, 1996). The proposed algorithm highlights the fact that the results obtained by simulating an artificial systems including two bees are superior to the results obtained by simulating an artificial systems including a single honey bee.

In 2005 Karaboga proposed a new perspective by simulating the foraging behaviour for solving multi-dimensional and multi-model optimization problems, called Artificial Colony (Karaboga, 2005).

The artificial bee population consists of three groups of bees (Chan & Tiwari, 2007):

  • Employed bees – they are assigned to a specific food location; when the amount of nectar on this area goes to zero, they become scouts;
  • Onlookers – considering the waggle dance performed by the employed bees, they choose one of the food locations described by this dance; the probability of choosing a location increase proportionally with the amount of nectar available there;
  • Scouts – they navigate through the search area without any assistance in order to find new food locations.

The ABC algorithm is based on representing the possible solution to the optimization problem as the position of the food source, while the amount of food corresponds to the solution quality. In these conditions, the number of the employed bees or onlookers bees is equal to the number of solutions in the population.

The main steps of this algorithm are (Stanarevic & Bacanin, 2011):

  • Send the employed bees into the search space and determine the nectar amountsavailable;
  • Calculate the probability values of the preferred sources for the onlooker bees
  • Stop the searching process on the location abandoned by bees;
  • Randomly send the scoots into the search area in order to find new food sources;
  • Memorize the location of the best food sources find so far.

The Artificial Bee Colony algorithm used in General Assignment Problem is presented in schema from Figure 14.3.

The variables used in problem codification are:

EmployedBeeNumber = the initial number of employed bees;
OnlookesBeesNumber = the initial number of employed bees;
MaximimIterationNumber = the maximum accepted iteration number;
fiti= the fitness value corresponding to the i bee;
EmplBeei=Employed Bee number i;
OnlkBeei =Onlooker Bee number i;
i_Neighbour= neighbor corresponding to the I bee;
pi=the probability of the Onlooker bee to choose the location of the EmplBeei
SN=Scout Number

media/image14.png
Figure 14.3 Continued 
media/image15.png
Figure 14.4 The Schema of the Artificial Bee Colony Algorithm 

The authors consider that the problems related to the learning process are difficult problems, non-determinist, so, in this chapter there is presented an approach based on neural networks and swarm intelligence in order to model the learning process into an adaptable and flexible e-learning system.