Difference between revisions of "Walther MA279 Spring2016 topic2" - Rhea

Latest revision as of 10:28, 24 April 2016

Swarm Intelligence --- Group E

Basic Concepts

Swarm intelligence involves a complex system of semi-autonomous individual units working collectively to reach an optimum solution through environmental and intra-population interactions. This cooperation causes comprehensive patterns to emerge across the system through which the system can be better understood and researched.

Common examples of swarm intelligence systems include beehives, ant colonies, human crowds, and bird flocking. Often, these systems are modeled using algorithms and then applied to solve specific problems.

The discipline of swarm intelligence was pioneered in 1989 by the research of Gerardo Beni and Jing Wang, which focused on cellular swarm robotics.

Concepts

Collectivity (Decentralization): the population consists of many individuals without a centralized source of control.

Uniformity (Homogeny): individual units of the population are either undifferentiated or largely similar with specialized differences.

Self-organization (Stigmergy): individuals act and interact on the local level based on genetic instinct and learned behaviors, leading to a macrocosmic pattern becoming evident and individual intelligence becoming collectively magnified.

Classifications

Natural or artificial—swarm intelligence involving organic networks existing in nature is called “natural”, while swarm intelligence involving man-made systems is called “artificial”.

Scientific or engineering—research aiming to understand and replicate swarm intelligence systems is referred to as “scientific”, while utilization of swarm intelligence networks in search of a solution to a specific problem is described as “engineering”.

Big Results

Bird Flocking/Partical Swarm Optimization

This algorithm is used to mimic the behavior of a bird flock searching a local region. The algorithm executes in a space where the swarm (flock) will exist, call a search space. Each point in this search space can be evaluated to a numerical value, a fitness. The swarm is searching throughout this space for the point with the best fitness. This point is known as the global optimum point. In order to find this point, the algorithm makes use of particles, which are like agents that will move step-by-step around the search space. A step is known as an iteration. After a certain number of iterations or after the optimum point has been found, the algorithm will end.

Features of a Particle

• A position inside the search space
• A fitness value at this point
• Velocity (or displacement), used to calculate the next step
• A memory, storing the best position found so far by the particle (previous best)
• The fitness value of the previous best position

A set of these particles is known as the swarm and they will all exist inside the search space looking for the optimum point. The search for the optimum point happens in two phases: Initialization and Iteration.

Initialization

 For each particle:
   Set the position as a random point inside the search space
   Compute the fitness value of this point
   Set the previous best as this point
   Pick a random velocity

Iteration

 For each particle:
   Compute a new velocity (displacement) based on these elements:
     Current position
     Current velocity
     Previous best position
     Previous best position of the swarm
   Move by applying the new velocity to the current position

   (Optional) Apply a confinement method to ensure that the new position is still inside the search space and compute the new fitness.
   If you do not apply a confinement method, it is known as the “let them fly” method and if the new position is outside the search space
   there is no re-evaluation.

   If the fitness of the new position is better than the previous best, replace the previous best with a copy of this position and
   replace its fitness with a copy of the new fitness

 Stop Criteria
   If the optimum position is known, stop when the difference between the optimum’s fitness and the swarm’s best fitness goes below
   a defined error value.

   Stop after a certain number of iterations.

Artificial Bee Colony

One big result in the field of swarm intelligence is the Artificial Bee Colony (ABC) algorithm, developed by Dervis Karaboga in 2005. The three main components of the algorithm are food sources, employed foragers, and unemployed foragers. Employed foragers are associated with a particular food source, and unemployed foragers. Unemployed foragers can be either scouts, who patrol the area around the nest for undiscovered food sources, or onlookers, who stay in the nest and become employed foragers based on the information conveyed to them by other employed foragers.

Each iteration, a percentage employed foragers for each food source will attempt to recruit unemployed foragers to join that food source. That percentage is positively correlated to the amount of nectar in that food source. In the algorithm, a food source is equivalent to a potential solution to the problem, and the amount of nectar is equivalent to the fitness. If a food sources’ nectar amount is not increased after a given number of iterations, the food sources is abandoned. In this way, the ABC algorithm converges on a solution.

Below is the psuedocode for the ABC algorithm:

 Send the scouts onto the initial food sources
 REPEAT
   Send the employed bees onto the food sources and determine their nectar amounts.
   Calculate the probability value of the sources with which they are preferred by the onlooker bees.
   Stop the exploitation process of the sources abandoned by the bees.
   Send the scouts into the search area for discovering new food sources, randomly.
   Memorize the best food source found so far.
 UNTIL (requirements are met)

Ant Colony

Some of the most useful applications of swarm intelligence can be garnered by ant colonies. Ants use natural pheromones that they produce to “smell” each other. Then the ants use these pheromones to direct each other toward useful resources in their environment. This allows a group of ants to work as a team to make complex decisions for locating valuable resources, staying clear of dangerous predators or even finding the most efficient path from one place to another.

One prime example of ant colony based swarm intelligence is an algorithm that models the pathfinding abilities of some Argentine ants. When searching an area for a specific resource, these ants use pheromones to alert other ants when they have chosen a successful path. The ants repeat this process this until they have found a single, optimal path. Similarly, The algorithm works by continually retracing the most promising routes of several paths in an effort to create a single shortest path. This particular algorithm was created by Air Liquide in order to find the the shortest route for picking up packages and then delivering them to one of the company's major gas plants. According to the company, after implementing this algorithm they have notices a huge increase in gas and time savings.

Stochastic Diffusion Search Algorithm (SDS)

This is algorithm is one inspired by a particular species of ants, Leptothorax acervorum. This species of ants uses a ‘tandem calling’ method (one-to-one communication). After a forage ant finds a food location, it recruits a single ant upon its return to the nest. Therefore the location of the food is physically published. The actual algorithm iterates through two phases.

Phase 1: Testing the Hypothesis

Each agent is tested to see if it’s hypothesis is true or not. The hypothesis will simply be testing candidate solutions to the search to see if they are valid solutions. Relating to ants foraging, the hypothesis would test if the location the ant is at is a valid food source.

Phase 2: Diffusion

Based on the recruitment strategy, successful hypotheses will then be diffused across the population and in this way information on potentially good solutions spreads throughout the entire population of agents.

Human Crowds

Human swarms or social swarms are those that are used to heighten the intelligence level by using the collective intelligence of the entire swarm rather than a single human. A recent study on human swarm intelligence was used to show the difference in singular polls to unified swarms correctness on predicting Academy Awards. This type of swarm intelligence has been used to predict multiple things such as a possible prediction of earthquakes and other natural disasters. Some swarm intelligence for humans have been based off of other organisms that work as a collective group, such as ants. A study about ant behavior and their interactions with the world allows companies to use that type of behavior to make dividends in saving money over periods of time such as oil and gas companies.

Implications

Swarmic Art

Swarmic art is the result of a successful combination of two swarm algorithms. One algorithm is mimicking the behavior of a specific species of ants foraging (SDS algorithm), while the other is mimicking the behavior of birds flocking (PSO algorithm). An alternating combination of these two algorithms is used to sketch novel drawings of an input image.

First, the SDS algorithm will explore the input image and attempt to find a detailed region of the image. After it has located a detailed region, the PSO algorithm then attempts to trace a line it has found in that region from start to end. It does this by treating all the points on the line as targets. After the tracing of the line is completed, the line is removed from the search space and then the SDS starts exploring again for another detailed region.

Sudoku Solver

Since the ABC algorithm was created, it has been applied to many different fields such as neural networks, image processing, data mining, sensor networks, protein structure, and many types of engineering. In Karaboga’s original paper, he used the algorithm in a numerical optimization problem.

One interesting application of the ABC algorithm was by Pacurib et al. to solve sudoku puzzles. In this application, the food sources are potential solutions to sudoku puzzles and the nectar amount are based on the penalty value of that solution. The penalty value is taken by evaluating the number of errors in each column, and in each row, and then sum them.

Every iteration, the algorithm would take a look at each food source (the solution to a sudoku puzzle in this case), and explore another solution in the neighborhood of the current solution, trying to improve its nectar amount (or in this case, decrease the puzzle’s penalty score).

Human Crowd Simulation

Applications of human swarming has been used in ways to simulate crowds and how crowds will react to certain situations. This type of simulation has been used throughout time in movies such as Lord of the Rings, I Robot, and 300. This type of simulation can allow producers to predict the way that crowds, such as armies, would react and move in different ways when something happens. This simulation could be implemented by crowd control, law enforcement agencies, and governments to be able to predict certain events that could happen during riots, protests, or large crowded events.

Why Study

Swarm intelligence research and models can be utilized to solve complex problems that affect the world. Researchers are using swarm intelligence to find solutions to traveling salesman problems, to build faster computers, to better understand neurology, and to create artificial intelligence systems. Swarm intelligence in the form of nerve cell collective cognition could very well be the secret to how human brains work, and this discovery could mean the next step in the technological evolution of mankind.

Swarm intelligence has found applications in many fields of engineering, including, but not limited to industrial, mechanical, electrical, and control engineering. It is also relevant to computer science, finding applications in fields such as neural networks, software engineering and data mining. If you are interested in any of these fields, you should consider studying swarm intelligence.

References

al-Rifaie, Mohammad Majid, and John Mark Bishop. "Swarmic sketches and attention mechanism". Evolutionary and Biologically Inspired Music, Sound, Art and Design. Springer Berlin Heidelberg, 2013. 85-96.

Blum, C., & Li, X. (2008). Swarm intelligence in optimization (pp. 43-85). Springer Berlin Heidelberg.

Dorigo, M., & Birattari, M. (2007). Swarm intelligence. Scholarpedia, 2(9):1462.

From Prices to Politics, HUMAN SWARMS unleash collective intelligence. (2015).

Haken, H. (2008) Self-organization. Scholarpedia, 3(8):1401.

Karaboga, D. (2005). An idea based on honey bee swarm for numerical optimization (Vol. 200). Technical report-tr06, Erciyes university, engineering faculty, computer engineering department.

Karaboga, D., Gorkemli, B., Ozturk, C., & Karaboga, N. (2014). A comprehensive survey: artificial bee colony (ABC) algorithm and applications. Artificial Intelligence Review, 42(1), 21-57.

Massive Software – Simulating Life. (n.d.). Retrieved from http://www.massivesoftware.com/

Maurice Clerc. Standard Particle Swarm Optimisation. 15 pages. 2012.

Merkle, D., & Middendorf, M. (2014). Swarm intelligence. In Search Methodologies (pp. 213-242). Springer US.

Miller, P. (2007). Swarm Theory - National Geographic Magazine. Retrieved from http://ngm.nationalgeographic.com/2007/07/swarms/miller-text/4

Morad, R. (2015). Swarms of Humans Power A.I. Platform.

Pacurib, J. A., Seno, G. M. M., & Yusiong, J. P. T. (2009). Solving sudoku puzzles using improved artificial bee colony algorithm. In Innovative Computing, Information and Control (ICICIC), 2009 Fourth International Conference on (pp. 885-888). IEEE.

Riders on a swarm. (2010). Retrieved from http://www.economist.com/node/16789226

Rosenberg, L. B. (n.d.). Human Swarms, a real-time paradigm for Collective Intelligence.

Swarm theory. (2007). Retrieved from http://ngm.nationalgeographic.com/2007/07/swarms/miller-text/1