### 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

## 20

## 0

## Popular in Course

## Popular in General Interdisciplinary Studies

This 16 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 Payman Arabshahi in Fall. Since its upload, it has received 20 views. For similar materials see /class/192159/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

I Examples of Local Search metaheuristics Simulated Annealing Kirkpatrick Gelatt Vecchi 1982 stochastic acceptance criterion steepest descent search the entire neighborhood and stop when there is no improvement First improvement accept the first generated solution that improves the current one Kopt local search Lin 1965 Johnson and McGeoch 1997 based on the k change neighborhood that has proved to be very successful for TSPs and similar problems Ms prescribes that k edges are removed from the tour 5 and then replaced with other k edges The best results are usually obtained for k 2 and k 3 Iterated local search Lourenco Martin and StUZle 2002 iteratively after hitting a local optimum the search is restarted and the new starting point is derived from some randomization of the current the local optimum Genetic algorithms Holland 1975 Goldberg 1989 the current solutionquot is a point in S n population dimension Simulated Annealing procedure Simulated nnealing defineneighborhoodslruclure 9 gelinilialsolulion3 sbest H T e initialJemperalureO while stoppingx te on seaTchmt zighbmho while seaTch eighboThood s H samplesolulionfromneighborhoodNs WW gt m f S if 5 pmpt HewpltM T else paccept H 1 ndi if random lt paccept s lt s seaTchmeighbmhood 9 false else seaTch eighbmhood lt keepsearchingcurrenlneighborhood0 end if if s lt Sbest bgs H 57 nd If en while T H updaleJemperalureT end while return sbest I Simulated Annealing O a o Applied to both combinatorial and continuous problems with mixed success Proofs of asymptotic convergence available Geman and Geman 1984 Lundy and Mees 1986 Temperature s schedule is critical to obtain good results in finite time at the beginning temperature T is expected to be high in order to favor exploration but it has to be gradually eg logarithmically and possibly monotonically decreased over the iterations Tabu Search procedure TabuSearch defineneighborhoodstructure s e getinitialsolutionS Sbest H 395 initializetabulist while stoppingxm39tem on Ms lt neighborsoutionsthatdonotviolatetabuconditionNs 15 lt neighborsoutionsthatmeetaspirationNs 5 lt getbestsolutionMs UNas updatetabulist if 5 lt 5175 5best H 395 end if end while return 5178 7 0 Tabu criteria recency frequency quality influence 39 Tabu criteria are applied to either complete solutions or solution components 39 Applied to several problems with good success Rollout a construction metaheuristic procedure Rolloutalgorithm t lt 0 5 H A while wt S V stoppmgxm39tem on ct e arg minckecm J 39Hwt ED 019 n1 H wt 69 Ct t lt t 1 end while return wt The heuristic H takes a partial solution wk and completes it into a feasible solution 39 At each decision step t each feasible choice C e 3a is scored according to an estimate of the cost associated to the feasible solution that would result from the completion of the partial solution an SD Ct by H 39 Instead of relying on systematic expansions of the partial solution eg dynamic programming the heuristic H is used to obtain an approximate and possibly quick evaluation of this cost H can be any heuristic 39 A pool of heuristics can be used and the heuristic providing the best expected cost can be used at each step Under mild mathematical conditions the rollout metaheuristic guarantees to improve the performancet a could be ob ained by using the base heuristic H Bertsekas Tsitsiklis and Wu 1997 ACO bioinspired multiagent metaheuristic procedure ACOmetaheuristic while a stoppingxriterion schedulejctivities antagentsconstructsoutionsusingpheromone pheromoneupdating daemonjctionso OPTIONAL end scheduleactivities end while return best olutiomgenerated Ant agents construct solutions according to stochastic decisional processes depending on pheromone variables stigmergic communication 39 Philosophical assumption memory and learning can be useful to solve combinatorial optimization problems ACO s logical structure I ACO in words 1 39 According to some chosen schedule eg groups of 10 ants atatime ant agents are repeatedly generated The task of each ant is to construct in a relatively simple and computationally light way a solution for the problem at hand Starting from an empty solution each ant during its forward journey constructs a possibly feasible solution by adding stepbystep components to the partial solution At each construction step an ant applies a stochastic decision policy to decide the next action that is the new solution component to include into the current partial solution The decision policy depends on two sets of variables in some sense local to the decision step the pheromone variables and the heuristic variables Both these two sets of variables encode the desirability of issuing a specific decision to extend the current partial solution conditionally to the fact of being in the current decision step I ACO in words 2 39 Pheromone variables as in the case of the ants encode the value of desirability of a local choice as collectively learned from the so far generated solutions Heuristic variables assign a value of desirability on the basis of either a priori knowledge about the problem or as the outcome of a process independent ofthe ants eg the computation of a lower bound estimate Pheromone variables which bias the probabilistic decisions of the ants are in turn repeatedly updated during algorithm execution to reflect the incremental knowledge about the characteristics ofthe solution set that has been acquired through the same solution generation processes 39 After building a solution metaphorically or in practice the ant reports the solution to a sort of pheromone manager which authorizes or not the ant to update the pheromone variables associated to the built solution according to its evaluation I ACO in words 3 In the positive case the ant starts its backward journey retracing its solution and updating pheromone values usually of an amount proportional to the evaluated quality of the solution In this way decisions associated to solutions which are either of good quality or are chosen more often will likely have associated higher levels of pheromone that is higher local desirability The process is iterated over time and can happen in a distributed or centralized way I Some facts about ACO It has been applied with success to a number of classical combinatorial problems traveling salesman quadratic assignment graph coloring sequential ordering set covering job scheduling and problems of adaptive routing in different types of networks Performance are very good better or comparable to stateof theart in the case of routing problems and in the case of several combinatorial problems usually when a local search daemon procedure is also used It is the most popular and effective framework inspired by an ant behavior and making use of stigmergy The workshop ANTS is held every two years and gathers between 50 and 100 participants http iridiaulbacbe antsantsZOO4 For more information and extensive discussions and review of applications referto Dorigo and Di Caro 1999 Dorigo Di Caro and Gambardella 1999 Dorigo and Stutzle 2004 Dorigo Di Caro and Sampels 2002 Di Caro 2004 I Ant System the rst ACO for TSP 1991 procedure ASanlagenlJifechleO i H 0 m H gelslarlingxiiYO CJYzi 0 710 lt zocoJzo whil m e foreach 0139 6 Nz do a F 729 39 my end foreach c e apply 51ochasticnecisionxuleAL c0 n1 lt xi WW Jltgt Jlt H n1 H an Ci1 i withHCi1 zi1 Jwi1 2e21 endwhile s lt an J5ltJZ i J coci I foreachci0j 671 20 2N71 21 do Ti lt Tij 1J s end foreach removaLfrothejyslemo end procedure I Ant System 2 v Pheromone evaporation for exploration 72705 n 1 p7 239jt7 Ant decision rule Vi7jE177N7pE071 127 Sangv Ci 15105 k 122705 7 12739 7 39 mi However many other choices are possible Dorigo and Di Caro 1999 Dorigo and Stutzle 2004 Di Caro 2004 I Cultural algorithms Reynolds 1994 procedure Cultural lgorithmo H PO lt initializepopulation Bt lt initializebeliefspace evaluatepopulationPt while terminationxondition communicate73tl3t BO lt adjustbeiefspacel3t communicatel3t73t PG 1 lt select73t 73t 1 lt evolve73t 1 evaluatepopulation73t 1 t lt t 1 end while return best olutiongenerated I Cultural algorithms 2 a Derived from cultural evolution process which support the basic mechanisms for cultural change Populationbased each individual has behavioral traits that can be modified and exchanged by socially motivated operators microevolutionary level At the macroevolutionary level individuals experiences generated solutions are evaluated and then collected merged generalized and specialized in a shared belief space The two levels interact through a communications protocol The End Thanks for listening I hope it was it will be useful Good luck for your studies and career

### 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.