### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# SCIENCE OF SWARMS GIS 203

UW

GPA 3.9

### View Full Document

## 14

## 0

## Popular in Course

## Popular in General Interdisciplinary Studies

This 50 page Class Notes was uploaded by Mr. Felicita Klein on Wednesday September 9, 2015. The Class Notes belongs to GIS 203 at University of Washington taught by Staff in Fall. Since its upload, it has received 14 views. For similar materials see /class/192160/gis-203-university-of-washington in General Interdisciplinary Studies at University of Washington.

## Popular in General Interdisciplinary Studies

## Reviews for SCIENCE OF SWARMS

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/09/15

l Particle Swarm Optimization 0 Populationbased stochastic optimization technique Purpose optimization of continuous nonlinear functions Background bird flocking and fish schooling artificial life social systems First work Eberhart and Kennedy 1995 Popularity A book Kennedy and Eberhart 2001 a recent special issue on IEEE Transaction on Evolutionary Computation Vol 8 June 2004 topic of interest in several conferences and workshops It s actually a sort of generalization of Cellular Automata Nolfram 1980 so let s give a quick look to them first l Cellular Automata A set of simple automata that is finite state machines with few states S 51 52 5k A topology of interconnection among the automata such that each automaton 12 has 712 neighbors Mai ally a 7 llii A statetransition function F that depends on the current state slit of the automaton and on the state of its neighbors NaZ At discrete timesteps and either synchronously or asynchronously each automaton gets the state from its neighbors and possibly change state accordingly 5 Examples numeric solution of differential equations voting in social networks fluid dynamics cell behavior nnr39ls nf thenretinnl studies mnre than useful on I PSO background 0 Early work on simulation of bird flocking aimed at understanding the underlying rules that allow smooth flocking Reynolds 1984 and roosting behavior Heppner and Grenader 1990 The rule were supposed simple and based on social behavior sharing of information and reciprocal respect of the occupancy of physical space Social sharing of information among conspeciates seems to offer an evolutionary advantage Target study of human social behavior on the basis of birdfish swarm behavior The notion of change in human social behaviorpsychology is seen as the analogous of change in spatial position in birds l PSO background 2 Initial simulation a population of N gtgt 1 agents is initialized on a toroidal 2D pixel grid with random position and velocity 92242 239 1 N At each iteration loop each agent determines its new speed vector according to that of its nearest neighbor A random component is used in order to avoid fully unanimous unchanging flocking All this was not so exciting but the roosting behavior of Heppner was intriguing it looked like a dynamic force such that eventually the birds were attracted to land on a specific location The roost could be the equivalent of the optimum in a search space l PSO background 3 o In real life birds don t know for instance were food is but if one puts out a bird feeder heshe will see that within hours a great number of birds will find it even though they had no previous knowledge about it This looks like the flock dynamics enables members of the flock to capitalize on one another s knowledge The agents can be therefore assimilated to solution hunters thatsocially share knowledge while they fly over a solution space Each agent that has found anything good leads its neighbors toward it So that eventually they can land on the best solution in the field l PSO background 3 o In real life birds don t know for instance were food is but if one puts out a bird feeder heshe will see that within hours a great number of birds will find it even though they had no previous knowledge about it This looks like the flock dynamics enables members of the flock to capitalize on one another s knowledge The agents can be therefore assimilated to solution hunters thatsocially share knowledge while they fly over a solution space Each agent that has found anything good leads its neighbors toward it So that eventually they can land on the best solution in the field PSO the metaalgorithm Each agents is a particlelike data structure that contains the coordinates ofthe current location in the optimization landscape the best solution point visited so far the subset of other agents that are seen as neighbors procedure ParticleSwarmOptimization foreach particle E ParticleSet do initatrandompositionsandveocity seectatrandomtheneighborset end foreach while a stoppingcriteri0n foreach particle E ParticleSet do calculatecurrentfi tnessand update memoryO getneighborwithbestfi tnessO calculateindividuadeviationbetweencurrentandbestsofarfi tnessO caIcuatesociadeviationbetweencurrentandbestneighborfi tnessO caIculateveocityvectorvariationasweightedsumbetweendeviations u pdateveocityvector end foreach end while return bestsoutionfound PSO the algorithm procedure ParticleSwarm0ptimizationParticles Neighbors FitnessfuncO foreachparticlepii articles do pi inext Hpi e getandomposition piL7 lt getJandomyelocity pm H getJandommeighborsNeighbors piAbestAml e 700 end foreach s best lt 700 while stoppingcriterion foreach particle pi i P7A newt H p i 4 pFitness e FitnessFunc i if pFitness gt p best al p i bestual H pFitness pi end if 7 1 l l l Particles d0 bestltj R My if pFitness gt s best va slbestUal H pFitness s best q H pm tj nd if n lt getmeighbonwithbestjitnesspi foreach d 1 a a re im nsions do indFactor H indWeight randomiMin iMam socFactor lt socWeight randomsocMin socMam A10 H p bestld 1041M An H n be5td 7p qd A lt indFactor Ap socFactor n pUd H put d A putd lt k epveocitanaJnianaxJangeO pawn H p qd Judd and foreach end foreach ile I Some nal considerations on PSO 39 Equivalent to a realvalued ZD CA where the state of a partiCIe is 717 U Qbestv F jbest The neighborhood relationship is not transitive however other choices can be selected 0 Social networks can be asymmetric A is connected to B but B might not care about A An update of the state position on the optimization landscape is calculated as a tradeoff between individual and social knowledge Tested on benchmarks for continuous functions eg van den Berg and Engelbrecht 2004 and NN training 10 50 particles Performance comparable to genetic algorithms but simpler to design and analyze o7 l ACO background Shortest paths stigmergy l Outline 0 O Biological experiments that pointed out the shortest path behavior of ant colonies Ingredients that make the shortest path behavior happening Usefulness of solving shortest path problems Stigmergy indirect communication giving rise to selforganization Definition and examples of stigmergic variables Design of a stigmergybased multiagent system l Pheromone and Shortest Paths C Several ant species have trailIayingtraiIfollowing behaviorwhen foraging Holldobler and V lson 1990 While moving individual ants deposit on the ground a volatile chemical substance called pheromone forming in this way pheromone trails Ants can smell pheromone and when choosing their way they tend to choose in probability the paths marked by stronger pheromone concentrations In this way pheromone trails constitute a sort of attractive potential field Pheromone trails allows the ants to find their way back to food sources or to the nest and can be used by other ants to find the location of the food sources discovered by their nestmates I Ant behavior illustrated Stochastic Component Landscape Morphology Q 51 I More on pheromone and shortest paths O Pheromone trails act as a sort of distributed dynamic collective memory of the colony a repository of all the most recent foraging experiences of the ants belonging to the same colony By continually updating and sensing this chemical repository the ants can indirectly communicate and influence each other through the environment This basic form of indirect communication coupled with a form of positive feedback can be enough to allow the colony as a Whole to discover when only few alternative paths are possible the shortestpath connecting a source of food to the colony39s nest Experiments by Aron Beckers Deneubourg Goss Pasteels et al 1977 l The binary bridge experiment 0 After an initial transitory phase lasting few minutes during which some oscillations can appear ants tend to converge on the same path Deneubourg Aron Goss and Pasteels 1990 l Probabilistic model for binary bridge The amount of pheromone on a branch is proportional to the number of ants which have been using the branch in the past pheromone is assumed persistent The probability of choosing a branch at a certain time depends on the total amount of pheromone on the branch which in turn is proportional to the number of ants which have used the branch until that moment Um w PW Um w Lm k PLOW 17 The dynamics regulating the ant choices are if w PU7 w u071gt othenNise Um Um1 Um1 Monte Carlo simulations were run to test the model versus real data results of simulations were in agreement with the experiments with real ants for k m 20 and h m 2 5i l Binary bridge with unequal branches 1 If the branches of the bridges are of different length then the pheromone field can lead the majority of the ants in the colony to select the shortest between the two available paths Goss Aron Deneubourg and Pasteels 1989 39 The fi rst ants able to arrive at the food source are those that traveled following the shortest branch Accordingly the pheromone that these same ants have laid on the shortest branch while moving forward towards the food source makes this branch marked by more pheromone than the longest one The higher levels of pheromone present on the shortest branch stimulate these same ants to probabilistically choose again the shortest branch when moving backward to their nest Recursive behavior the very fact of choosing a path increases its probability of being chosen again in the near future autocatalytic effect l Binary bridge with unequal branches 2 Moving backward additional pheromone is released on the shortest path In this way pheromone is laid on the shortest branch at a higher rate than on the longest branch This reinforcement of the pheromone intensity on the shorter paths is the result of a form of implicit path evaluation the shorter paths are completed earlier than the longer ones and therefore they receive pheromone reinforcement more quickly 39 Therefore for a same number of ants choosing either the shortest or the longest branch at the beginning since the pheromone on the shortest branch is accumulated at a higher rate than on the longest one the choice of the shortest branch becomes more and more attractive for the subsequent ants at both the decision points I Binary bridge with unequal branches 3 l Ingredients of the shortest path behavior Population colony of foraging ants autonomous asynchronous concurrent distributed Forwardbackward path following Pheromone laying and sensing shared distributed memory distributed control Pheromonebiased stochastic decisions local fi eld Autocatalysis Implicit path evaluation Iteration over time Q 0 The colony realizes concurrent computation Multiple paths are repeatedly tried out back and forth and some information related to each followed path is released on the environment Stochastic decisions are based on the local pheromone content Implicit path evaluation coupled with autocatalysis results in distributed and collective path optimization Given enough time and depending on the number of ants relative length ofthe 39 paths pheromone evaporation etc this can result in the nnnunrnnnr n nnt n thn hnrtn t hath 58 l Ant repertoire vs colony repertoire A single ant is capable of building a solution cf with PSO every particle IS a solution point or with the Immune System where none of the agents provides a solution However it is only the simultaneous presence and synergistic action of a swarm of ants that makes possible the shortest path finding behavior This selforganized behavior is a property of the colony and of the concurrent presence of all the discussed ingredients It is not a property of the single ant l Solving shortest path problems is useful a O This class of problems is a very important one and encompasses a vast number of other problems Graphs whose nodes represent possible alternativesstates and whose edges represent distanceslossesrewardscosts associated to node transitions are graphical models for a huge number of practical and theoretical decision and optimization problems In general any combinatorial optimization or network flow problem can modeled in the terms of shortest paths Several general and very effective techniques to solve general shortest path problems are available label setting techniques eg Dijkstra algorithm Dijkstra 1959 label correcting techniques eg BellmanFord dynamicprogramming algorithms Bellman 1957 1958 Ford and Fulkerson 1962 Bertsekas 1995 and rollout algorithms Bertsekas Tsitsiklis and Wu 1997 The literature on the subject is extensive The novelty of ants is that they solve it in a distributed and dynamic way using environmentmediated communication an l Pheromone evaporation The characteristics of the dynamic pro cesses regulating pheromone evapora tion play a central role determining the conditions for shortest path behavior and to favor exploration and adaptation Both pheromone evaporation and the characteristics ofthe ant stochastic decision policy are strictly related to the choice of the tradeoff between exploitation eg of a path that seems to be particularly good and exploration eg of new alternative paths This is a major issue for any system engaged in a search process repeated overtime eg ACO Simulated Annealing 39 The literature on the mathematical and practical aspects of the explorationexploitation dilemma and on the related biasvariance dilemma is vast Kearns and Singh 1998 Thrun 1992 Robert and Casella 1999 Kirkpatrick Gelatt and Vecchi 1982 l Stigmergy 39 Stigmergy expresses the general idea of using indirect communication mediated by physical modifications of the environment to activate and coordinate selforganizing behaviors in a colony of insects The coordination of tasks and the regulation of constructions does not depend directly on the workers but on the constructions themselves The worker does not direct his work but is guided by it It is to this special form of stimulation that we give the name stigmergy stigma sting ergon work product of labour stimulating product of labour Grass 1959 39 Grass observed that insects are capable to respond to so called signi cant stimuli which activate a genetically encoded reaction In social insects the effects of these reactions can act as new signifi cant stimuli for both the insect that produced them and for other insects in the colony generating a recursive feedback that can lead to a phase of a global coordination Termite nest building The combination of stigmergy and phys ical characteristics of the environment gives rise to astonishing results Individual Sn 1h1B 3h23 5h15 8h13 agjq after start after start after start after start momma S l A more operative de nition O We call stigmergy any form of indirect communication among a set of possibly concurrent and distributed agents which happens through acts of local modification of the environment and local sensing of the outcomes of these modifications Dorigo Di Caro and Gambardella 1999 The local environment s variables whose value determine in turn the characteristics of the agents response are called stigmergic variables Dorigo Bonabeau and Theraulaz 1999 Stigmergic communication and the presence of stigmergic variables is expected depending on parameter setting to give raise to a synergy of effects resulting in selforganized global behaviors l Examples of stigmergic variables The height of a pile of dirty dishes floating in the sink Pheromone intensity in trailfollowing and shortest path behavior in ant colonies O Nest energy level in foraging robot activation Krieger and Billeter 1998 Level of customer demand in adaptive allocation of pickup postmen Bonabeau et al 1997 Two main model of response converging and diverging behavior at the group level I Threshold models of labor division 0 Diverging behavior is explained by threshold models of labor division and task allocation 5 stimulus intensity internal response threshold T9s response function probability of performing the task as a function of s ifsltltt9 a T9s 0 ifsgtgtt9 H T9s m 1 The internal response threshold can change overtime according to some evolution or learning A typical choice for T is Designing a stigmergybased system When a stigmergic approach is adopted to design a multiagent system the focus is put on the defi nition of effective stigmergic variables such that robust coordination and synergy can result an effective system of realizing in practice the indirect agent communication by exploiting environment structure The central issue is the defi nition of theprotocols interfaces rather than ofthe modules agents ofthe system Csete and Doyle 2002 simple cheap Protocols here are rules that prescribe allowed interfaces between modules permitting system functions that could not be achieved by isolated modules Protocols facilitate the addition of new protocols and simplify modeling and abstraction A good protocol supplies global robustness scalability evolvability and in the end allows to fully exploit the potentialities ofthe modules and of modularitv m l ACO and other metaheuristics for CO l Outline 0 Notes on combinatorial optimization and algorithmic complexity Construction and modification metaheuristics two complementary ways of searching a solution space Finally Ant Colony Optimization explained Other populationbased metaheuristics for optimization problems Genetic Algorithms Cultural Algorithms Crossentropy Single agent metaheuristics Local Search Tabu Search Rollout algorithms ACO and other metaheuristics for CO Outline J I Notes on combinatorial optimization and algorithmic complexity Construction and modification metaheuristics two complementary ways of searching a solution space Finally Ant Colony Optimization explained Other populationbased metaheuristics for optimization problems Genetic Algorithms Cultural Algorithms Crossentropy Single agent metaheuristics Local Search Tabu Search Rollout algorithms Ant Colony Optimization metaheuristic 9 Reverse engineering of the mechanisms behind the ant colony shortest path behavior Dorigo et al 1991 1 The agents called are an abstraction and an engineered version of real ants 1 Target solution of static and dynamic centralized and distributed 9 General idea repeated construction of solutions using a stochastic policy observation of the results and updating of realvalued variables used in turn by the decision policy in order to bias subsequent solution construction toward the most promising areas of the search space Before proceeding let s understand fi rst what a metaheuristic is and which is the class of problems A00 is intended for Algorithmic complexity J The time complexity function of an algorithm for a given problem indicates for each input size n the maximum time the algorithm needs to fi nd a solution to an instance ofthat size worstcase time complexity For instance a has time complexity Ogn where g is a polynomial function If the time complexity cannot be bounded by a polynomial the algorithm is said Garey and Johnson 1979 0 A problem is said if there is no polynomial time algorithm able to solve it 0 For the so called NPhard class of optimization problems exact algorithms need in the worst case exponential time to fi nd the optimum eg Traveling salesman quadratic assignment vehicle routing graph coloring satisfi ability o are guaranteed to fi nd the optimal solution and to prove its optimality for every fi nite size instance of the combinatorial problem in bounded instancedependent time Heuristics and metaheuristics J J For most NPhard problems of interest the performance of exact algorithms is not satisfactory Huge computational times are required sometimes even for small instances It is therefore necessary in practice to trade optimality for effi ciency seek to obtain good solutions at relatively low computational cost without being able to guarantee the optimality of the solution can be often proved for specifi c cases An algorithm that comes with the formal proof that it returns a solution worse than the optimal one by at most some fixed value or factor is ans22317 i A is a highlevel strategy which guides other problemspecifi c heuristics to search for solutions in a possibly wide set of problem domains eg Glover and Kochenber 2002 A metaheuristic can be seen as a general algorithmic framework which can be applied to different optimization problems with relatively few modifi cations to make them adapted to the specifi c problem 99 A trivial example of reallife metaheuristic 9 Metastrategy Before buying a new item eg a new laptop or a new pair of shoes it is mandatory to check at least 5 shops and collect related information 9 The highlevel strategy is independent from the specific item and doesn t tell anything about how the shops are actually selected and how the final decision is taken We therefore need at least two additional heuristics for the specific tasks of selecting the shop and taking the final decision Can you think of examples of metaheuristics that you adopt in your reallife andor that are adopted in your scientific field of interest Do you think it is useful in 37 Combinatorial problems S J where S is a and J is a function that associates a real if to each feasible solution J S gt IR The problem consists in fi ncling the element 3 e S which minimizes the function J J Instance of a combinatorial optimization problem is a pair 8 arg min Js 565 D Given the fi niteness of the set S the minimum of J on S indeed exists for at least one element 9 In the case of continuous optimization S is a subset of IR and the global minimum might not exist if the set is open 3 A combinatorial optimization problem is a set of instances of an optimization problem usually all sharing some core properties eg species genome and individuals DNA J A solution is a feasible solution in the set S 3 If mapping J changes during the execution ofthe algorithm 1 lie H the nrnhlem is rlvnamin as Characteristics of a solution 1 Given the fi niteness of the solution set this requires that the set of elements that can be part of arsolution is also fi nite Let s call them 1 Example fi nd the shortest path connecting two endpoints S 1237 137 13467 123467 1467 1567 is the loopless solution set The cost of a solution can be the sum ofthe costs ofthe single links The set C ofthe solution components is C 1 2 3 4 5 5 7 TSP constrained shortest path 1 Traveling Salesman Problem the minimal cost closed circuit touching all the nodes NPhard very fameus loads of applications studied since about1850 J For n cities gt n solutions n10 n 3628800 9 A solution is a ciclic permutation of cities 8 132451 J Z73 dij where dzj are the distances or more in general the link costs J d13 d32 d24 d45 d51 QAP quadratic assignment problem J D Quadratic Assignment Problem minimizing the assignment of activities ai e A to locations lj e L Extension of TSP which can be seen as a problem of assigning a city to a position from 1 to n bipartite assignment problems NPhard but more diffi cult than TSP A solution is a complete assignment 8 a1 l3 a2 l4 a3 l5 a4 l1 a5 l2 Every possible pair ailj has a cost The objective is to minimizing the sum of all costs 13 Zahljg czj where cij is the cost of assigning activities ai to location lj 18 013 024 035 041 052 Activities Locations 41 Construction heuristics 9 Starting from an empty partial solution 510 Z a complete solution 8 E S is incrementally built by adding oneat atime a new component c E C to the partial solution 9 The generic iteration also termed transition of a construction process can be described as 617 627 7 SCj l l 617627 7Cj7 Cj17 Ci E 07 1 where SCJ39 E X 290 is a partial solution of cardinality length j j g lCl lt oo 0 Solution construction Generic construction algorithm procedure Genericconstructionagorithm t lt O 177 lt Z while 517 g S V stopping riterion Ct lt selectcomponentC 5175 sct1 lt addcomponentzzt7 Ct 75 lt t 1 end while return 565 Construction illustrated 9 Stepbystep dependence on all the past decisions Pct Pct 611Ci176211t1 0 Appropriate when the cost Js is a combination of contributions each one related to the fact that a particular component cj is included into the partial gnllltinn gnllltinn fr 44 State diagram of the sequential process Modi cation methods 0 Construction algorithms work on the set of solution components Modification strategies act upon the search space of the complete solutions start with a complete solution and proceed by modifications of it Construction methods make use of an incremental local View of a solution while modification approaches are based on a global View of a solution This class numbers some of the most effective algorithms and heuristics for combinatorial problems Neighborhood of a solution 9 9 There is no assigned metric as in the continuous The notion of 2 is arbitrary A neighborhood is a mapping N that associates to each feasible solution 8 of an optimization problem a set Ns of other feasible solutions The mapping can be conveniently expressed in terms of a rule M that given 3 allows the defi nition of the set of solutions belonging to the neighborhood by applying some modi cation procedure on the components of 3 N3 s s e S s can be obtained from s from Ms N can be random but only those mappings preserving a certain degree of correlation between the value 13 associated to the point 8 and the values associated to the points in Ns are really meaningful Measure of closeness among the values associated to the solutions if some components of st are fixed the values of the solutions generated by modifying other components through M should be correlated to the value of st Local search methods Look for a solution localy optimal with respect to the defined neighborhood structure 9 They are based on the iteration of the process of neighborhood examination until no further improvements are found 9 The most effective heuristics Aarts and Lenstra 1997 Generic local search algorithm procedure Modifi cation heuristic defi ne neighborhood structure 8 lt getinitiasolutionS Sbest lt 5 while I stoppingcriteri0n 8 lt selectsoutionfromneighborhoodNs if acceptsolutions s lt 8 if 8 lt Sbest Sbest lt 5 end if end if end while return 8196875 Main design issues Neighborhood structure 9 Generation of the initial solution 0 Selection of a candidate solution from the neighborhood of the current solution 0 Criterion to accept or reject such selected solution

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.