swords

Information about swords

Published on February 26, 2008

Author: Melinda

Source: authorstream.com

Content

Ant Colony Optimisation:  Ant Colony Optimisation Dr Jonathan Thompson, School of Mathematics, Cardiff University Outline:  Outline Introduction to ant algorithms Overview of implementation for TSP (Dorigo et al.) Application to Dynamic Vehicle Routing (Wallace and Thompson) Application to Room Fitting (Thompson) Application to Examination Timetabling / Graph Colouring (Dowsland and Thompson) Conclusions Classification of Meta-heuristics:  Classification of Meta-heuristics Osman divided meta-heuristics into: Local search Population Construction Slide4:  Solution Space Feasible regions Slide5:  Local Search Solution Space Slide6:  Local Search Solution Space Slide7:  Local Search Solution Space Slide8:  Population Based Solution Space Slide9:  Population Based Solution Space Slide10:  Construction Solution Space Slide11:  Construction Solution Space Slide12:  Construction Solution Space Ant Algorithms:  Ant Algorithms Slide14:  The Ant System in Nature Ant Algorithms:  Ant Algorithms Proposed by Dorigo et al. Probabilistic greedy construction heuristic Probabilities are adjusted according to information on solution quality gained from previous solutions Initially use limited to routing problems but now being applied to a broad range of problems. Ant Systems for the TSP:  Ant Systems for the TSP No. ants = No. cities Each ant i produces a (probabilistic) solution, cost ci Trail between each pair of cities in route i = trail + Q/ci Trail is subject to evaporation i.e. trail = trail * σ, σ < 1 Each ant chooses next city with a probability proportional to the distance and the trail. Ants for TSP:  Ants for TSP Probability of next city from i being k is P(ik) = [ik] [ik]  [jk] [jk] where μik = Q / distance from i to k, ik = trail between i and k. Continues through generations until reaches stagnation Has outperformed other meta-heuristics The Static VRP:  The Static VRP A set of geographically dispersed customers need to be serviced. All routes start and end at the depot. A cost cij, is associated with travelling from customer i to customer j. Customer i has demand Di, vehicles have capacity Q Construct a set of routes such that cost is minimised and each customer is visited once and capacity constraints are satisfied. Example VRP:  Example VRP Adding Dynamism (DVRP):  Adding Dynamism (DVRP) Static VRP Customers are known a priori and do not change after the routes have been constructed. Dynamic VRP Customers can change after the initial routes have been constructed. Graphically Explained:  Graphically Explained New Customer Arrives What happens now ? Two Solution Approaches:  Two Solution Approaches Insertion Heuristics Insert the new customers in the current routes. Improvement heuristics when system is idle. Re-Optimization i.e. solve static VRPs Re-planning from scratch when new information is received / after each time period. Graphically Explained – Re-Opt:  Graphically Explained – Re-Opt New Customer Arrives If capacity is not exceeded then a new route is created. Current route is discarded. If exceeded then new routes are constructed ACS-DVRP Pseudo-code:  ACS-DVRP Pseudo-code Overnight, an initial solution is created and commit drivers to customers for first time period + small commitment time. Each time period is then considered in turn. Customers = existing customers who have not been committed to + new customers who arrived during the previous time slot. Solve problem during current time period and commit drivers to customers if start time is within the subsequent time period Continue until all customers are committed to. Roulette Wheel Choice:  Roulette Wheel Choice A schedule is being created, truck is at customer i. A roulette wheel type selection is made to decide where to go next. Size of the slot depends on attractiveness of the move. Ants for the DVRP (ACS-DVRP):  Ants for the DVRP (ACS-DVRP) Better solutions obtained by: Diversification: local trail update ij = (1 – ρ) ij + ρ 0 Select best choice with probability q, probabilistically with probability (1 – q). Elitism – only use best ant solution to update trail globally Maintain trails from one problem to another ij = (1 – γ) ij + γ 0 Apply descent to each ant solution Full parameter optimisation Preliminary Results:  Preliminary Results Min, Ave, Max 3 Data Sets Problems with the ACS-DVRP:  Problems with the ACS-DVRP Sequential route construction: Each route is completed before the next is created. Customers may be scheduled in an early truck, though may have been better placed in a later one. High variance within results: Difficult to interpret results. Minimized through use of trials. Extended Roulette Wheel:  Extended Roulette Wheel Consider more than 1 truck at a time. Arcs that would have been ignored previously are now considered. Consider 3 trucks, 1 at customer i, 1 at customer j and 1 at the depot Extended Roulette Wheel Results:  Extended Roulette Wheel Results Why ? An increase in the number of trucks used. Truck Reduction Techniques:  Truck Reduction Techniques Capacity Utilization. Encourages the use of existing trucks over the selection of a new truck. Let kij=(Qi+qj)/Q Advanced construction formula Truck Reduction Results:  Truck Reduction Results Reduction in average cost for each data set. Truck Reduction Graphic:  Truck Reduction Graphic The Room Fitting Problem:  The Room Fitting Problem Allocate examinations to rooms such that :- no rooms are overfull exams of different length are allocated to different rooms Additional objectives:- Minimise the number of split exams Allocate exams to adjacent rooms Simple Solutions :  Simple Solutions Randomly allocate exams to rooms Evaluate cost function = overflow + number of pairs of exams of different duration in the same room Randomly move a single exam to a new room or swap two exams Apply local search - SA / TS etc. Ants for Room Fitting:  Ants for Room Fitting Number of ants = number of exams Exams ordered according to size / duration Initially, each ant i produces a solution, with cost ci. Possible trail: Between pairs of exams? (1) Or Between exams and rooms (2) 1(j,k)= 1 (j,k) + 100/ci if ant i places exams j and k in the same room 2 (j,l) = 2 (j,l) + 100/ci if ant i places exam j in room l All trails are reduced by an evaporation rate Ants for Room Fitting:  Ants for Room Fitting Each ant now produces another solution, by considering each exam in turn and choosing which room to place it in according to the two trails and the immediate cost. The trails are combined so that the trail associated with allocating exam j to room k is combined with the trails between exam j and any other exams already allocated to room k. The Trails:  The Trails How should we combine the trails? Average of all trails. Average of the two trails. Alter the factor applied to each trail according to the cost function. When producing trails, just use part of cost function concerning each trail. Experiments:  Experiments Data Set One - Artificial, Optimal cost = 0, one optimal solution only. Size varies from 5 rooms, 13 exams to 20 rooms, 70 exams Data Set Two - Real, Optimal cost is unknown. Size varies from 12 exams to 90 exams. Five random runs Best parameters found by experimentation with artificial data, then used on real data set. Results from Artificial Data:  Results from Artificial Data Results from Real Data:  Results from Real Data Graph Colouring:  Graph Colouring Given a Graph with a set of vertices and a set of edges, assign to each vertex a colour so that no adjacent vertices have the same colour. NP-Complete Applications include timetabling, frequency assignment and register allocation. Ants for Graph Colouring:  Ants for Graph Colouring Costa and Hertz, Ants Can Colour Graphs (1997) Each ant produces a solution by choosing vertices randomly in proportion to some definition of cost. Allocate to some colour. A trail records the quality of solution when pairs of vertices are in the same colour class. Subsequent ants construct solutions, considering cost (visibility) and trail. Trails are subject to evaporation. Ants for Graph Colouring:  Ants for Graph Colouring Normal Probabilistic selection: Trail update: tij = ρtij +  1/q(s) for each solution s in which vertices i and j are in the same colour class Trail calculation: jk = tij / |Vk| where Vk = no. vertices already coloured k. Ants for Graph Colouring:  Ants for Graph Colouring Eight variants based on RLF and DSatur: W = uncoloured vertices than can be included in current colour class B = uncoloured vertices that cannot be included in current colour class degX(i) = degree of vertex i in subgraph of vertices X RLF(i,j), i = visibility, j = choice of first vertex i = 1 degB(i) j = 1 max degW(i) i = 2 |W| - degW(i) j = 2 randomly i = 3 degBUW(i) Ants for Graph Colouring:  Ants for Graph Colouring DSatur(i). Visibility = saturation degree i = 1. First available colour. i = 2. Vertex chosen wrt visibility. Colour chosen probabilistically wrt trail. Results are encouraging. However Vesel and Zerovnik (2000) question quality of results. Improvements - Reward Function:  Improvements - Reward Function 40 colour graph No. Colours Trail Ratio 41 1 42 0.976 43 0.953 44 0.932 10 colour graph No. Colours Trail Ratio 11 1 12 0.917 13 0.846 14 0.785 Improved Reward Function:  Improved Reward Function Instead reward function = 1 q(s) - r where r = best solution so far N colour graph No. Extra Trail Ratio Colours 1 1 2 0.5 3 0.33 4 0.25 Further Improvements:  Further Improvements Solution 1 r colours rth colour class contains several vertices Solution 2 r colours rth colour class contains one vertex Instead limit number of colours to target value and use number of uncoloured vertices u(s) as the reward function. Potential Problems:  Potential Problems No trail from uncoloured vertices Instead trail between uncoloured vertices and all other vertices is increased by 1/u(s) This is a diversification function. Experiments:  Experiments Initially used examination scheduling data Known number of colours (number of timeslots) Some structure to graphs Larger number of large cliques than random graphs Examination Scheduling Data:  Examination Scheduling Data 7 datasets from Carter Problem sizes vary between 80 and 487 vertices Density varies between 6% and 29% Maximum clique between 10 and 21 Clique vertices have high degree Optimal colouring between 10 and 21 Results for Sample Dataset:  Results for Sample Dataset Results for all Datasets:  Results for all Datasets Results for Best Parameters:  Results for Best Parameters Best Ant Implementation:  Best Ant Implementation RLF(1,2) Reward function of 1/u(s) Diversification included Alpha = 2, higher beta values (4 or 5) Evaporation rate = 0.5 Results confirmed on larger datasets Results comparable to those of other researchers Random Graphs:  Random Graphs Graphs used by Costa and Hertz (from Ferland and Fleurent) 20 G(100,0.5), 10 G(300,0.5), 5 G(500,0.5) and 2 G(1000,0.5) Size C & H D & T 100 15.2 15.15 300 35.7 34.5 500 55.6 53.0 1000 111.0 100.5 Random Graphs:  Random Graphs Graphs used by Costa and Hertz (from Ferland and Fleurent) 20 G(100,0.5), 10 G(300,0.5), 5 G(500,0.5) and 2 G(1000,0.5) Size C & H D & T C et al. 100 15.2 15.15 14.95 300 35.7 34.5 33.3 500 55.6 53.0 49.5 1000 111.0 100.5 85.0 Random Graphs:  Random Graphs Emphasise diversity function by raising to power Improvements :  Improvements Improve Construction – make several attempts at each colour class and select the one that minimises the no. edges in remaining graph Change evaluation function to no. clashing edges if vertex inserted into best colour class Add local search Local Search :  Local Search Shuffle – Reorder colours and move vertices into earlier colours if possible. Focus on likely colour classes i.e. consider them last. Tree. Depth first search where uncoloured vertices are coloured into colours with least clashes, and clashing vertices are moved out, and we try to colour them elsewhere. Tabu Search, considering clashing vertices. Tabu list contains vertex colour pairs Best Results:  Best Results * = Costa et al. Conclusions:  Conclusions Ant colony optimisation is a competitive meta-heuristic for a wide variety of problems Often needs extra assistance e.g. local search Need the correct balance between intensification and diversification (exploitation and exploration) Randomness is important Parameter heavy Future – consider more ill-structured / dynamic / stochastic problems

Related presentations


Other presentations created by Melinda

MOLLUSCA Power Point
20. 02. 2008
0 views

MOLLUSCA Power Point

using physician extenders
08. 05. 2008
0 views

using physician extenders

Consumer s Rights
07. 05. 2008
0 views

Consumer s Rights

spscicomp6
02. 05. 2008
0 views

spscicomp6

Energy1
02. 05. 2008
0 views

Energy1

FML2004 1
02. 05. 2008
0 views

FML2004 1

Roberta Zobbi
02. 05. 2008
0 views

Roberta Zobbi

Brain Cancer Causes
02. 05. 2008
0 views

Brain Cancer Causes

Anes Equip Probs 03
30. 04. 2008
0 views

Anes Equip Probs 03

Fin525Fall2006Week7
28. 04. 2008
0 views

Fin525Fall2006Week7

Keynote
22. 04. 2008
0 views

Keynote

Bonding
16. 02. 2008
0 views

Bonding

Systems Analysis Presentation
06. 03. 2008
0 views

Systems Analysis Presentation

BizRetPresentation Final
01. 10. 2007
0 views

BizRetPresentation Final

9 Oyieke Illicit Trade
10. 10. 2007
0 views

9 Oyieke Illicit Trade

Khosla Biofuels GEC DC 3 1 06
15. 10. 2007
0 views

Khosla Biofuels GEC DC 3 1 06

28 Thermal Baths at Vals
19. 10. 2007
0 views

28 Thermal Baths at Vals

pk momterrey 11 04
21. 10. 2007
0 views

pk momterrey 11 04

marie robinson
22. 10. 2007
0 views

marie robinson

OceanStore tahoe2
07. 10. 2007
0 views

OceanStore tahoe2

gis in health
23. 10. 2007
0 views

gis in health

Spalart SanFran 06
30. 10. 2007
0 views

Spalart SanFran 06

W Simpson Foresman
02. 11. 2007
0 views

W Simpson Foresman

transitioning
07. 11. 2007
0 views

transitioning

Lopez Cerezo y Lujan
22. 10. 2007
0 views

Lopez Cerezo y Lujan

024
25. 10. 2007
0 views

024

qiao
15. 11. 2007
0 views

qiao

Skills for Life2
19. 11. 2007
0 views

Skills for Life2

Dr Painter Food Psychology
22. 10. 2007
0 views

Dr Painter Food Psychology

MIE2006 RIDE
29. 10. 2007
0 views

MIE2006 RIDE

thesaurus 1
04. 12. 2007
0 views

thesaurus 1

burns pp
04. 01. 2008
0 views

burns pp

rubrics
01. 01. 2008
0 views

rubrics

IZ 101 Slides Revision
30. 10. 2007
0 views

IZ 101 Slides Revision

midterm review
02. 11. 2007
0 views

midterm review

Armstrong
03. 01. 2008
0 views

Armstrong

Mr KONDO Presentation 070603
09. 10. 2007
0 views

Mr KONDO Presentation 070603

dossier de presse
24. 10. 2007
0 views

dossier de presse

pres clarkm5
15. 10. 2007
0 views

pres clarkm5

Joe Caddell ppt
24. 10. 2007
0 views

Joe Caddell ppt

Slivovsky CPE350 Lecture1
31. 12. 2007
0 views

Slivovsky CPE350 Lecture1

materiasprimas
04. 10. 2007
0 views

materiasprimas

capstone designing
31. 10. 2007
0 views

capstone designing

03 Basic Chemistry
04. 03. 2008
0 views

03 Basic Chemistry

Contraception
12. 10. 2007
0 views

Contraception

P Letardi
01. 11. 2007
0 views

P Letardi

NUR lecture 2
07. 01. 2008
0 views

NUR lecture 2

Global Health
11. 03. 2008
0 views

Global Health

Solar5
07. 04. 2008
0 views

Solar5

Gumbert vormittags
29. 12. 2007
0 views

Gumbert vormittags

35
22. 10. 2007
0 views

35

STB OrgChart 050819
25. 03. 2008
0 views

STB OrgChart 050819

wf conf june5
09. 04. 2008
0 views

wf conf june5

global nondeal roadshow
11. 04. 2008
0 views

global nondeal roadshow

L04 dg c2
10. 12. 2007
0 views

L04 dg c2

20 Non renewables
16. 04. 2008
0 views

20 Non renewables

SAINSEL Kickoff
23. 10. 2007
0 views

SAINSEL Kickoff

Futures Pricing and Strategies
17. 04. 2008
0 views

Futures Pricing and Strategies

tutorial avedon
24. 02. 2008
0 views

tutorial avedon

k waldron avnwx tdas
07. 03. 2008
0 views

k waldron avnwx tdas

ASPO2005 Leonard
12. 10. 2007
0 views

ASPO2005 Leonard

powerpointmba
16. 11. 2007
0 views

powerpointmba

marxfam2
19. 02. 2008
0 views

marxfam2

antihistamines 2006
16. 10. 2007
0 views

antihistamines 2006

CD San Francisco 11 14
29. 10. 2007
0 views

CD San Francisco 11 14

russian transportation
11. 10. 2007
0 views

russian transportation

ibcoldwar
08. 04. 2008
0 views

ibcoldwar

Agrimi Workshop7 THC5
17. 10. 2007
0 views

Agrimi Workshop7 THC5

Pompey the Great
03. 04. 2008
0 views

Pompey the Great

wipo smes sin 07 8 parta
28. 02. 2008
0 views

wipo smes sin 07 8 parta

P1Slides
17. 10. 2007
0 views

P1Slides

JubbDinner Keynote
07. 01. 2008
0 views

JubbDinner Keynote

old china new japan
09. 10. 2007
0 views

old china new japan

Paul Browne Selected MSc Work
29. 09. 2007
0 views

Paul Browne Selected MSc Work

ppt simons
13. 11. 2007
0 views

ppt simons

Bucharest Denisov
11. 10. 2007
0 views

Bucharest Denisov

Huettner QA systems 00 04 11
16. 10. 2007
0 views

Huettner QA systems 00 04 11

4941
13. 04. 2008
0 views

4941

Lucy
05. 01. 2008
0 views

Lucy