Ant Colony Optimization and Swarm Intelligence: 5th International Workshop, ANTS 2006, Brussels, Belgium, September 4-7, 2006, Proceedings

000......Page 1
Introduction......Page 15
Canonical Particle Swarm Optimizer......Page 16
Fully Informed Particle Swarm Optimizer......Page 17
Experimental Setup......Page 18
Results......Page 19
Conclusions......Page 24
Overview......Page 27
Previous Work......Page 28
Framework Overview......Page 29
Packet Forwarding......Page 30
Metric Update......Page 31
Steady State Routing Probabilities......Page 32
Analysis Overview......Page 34
Effect of Network Sample Rate......Page 35
Conclusion......Page 36
Introduction......Page 39
The Traffic Assignment Problem......Page 40
Theoretical Properties and Classical Solution Algorithms of the Traffic Assignment Problem......Page 42
The Proposed Assignment Algorithm......Page 45
First Results......Page 47
Conclusions and Research Prospects......Page 49
Introduction......Page 51
Metrics for Path Quality and Pheromone Tables......Page 53
Proactive Path Maintenance and Exploration......Page 54
Stochastic Data Routing......Page 55
Experimental Methodology and Characteristics of the Simulation Environment......Page 56
Using Different Optimization Metrics for Pheromone Definition......Page 57
Varying the Number of Entries in Pheromone Diffusion Messages......Page 58
Varying the Routing Exponent for Ants and Data......Page 59
References......Page 61
Introduction......Page 63
Related Work......Page 64
Basic Ant Based Routing for WSNs......Page 66
Improved Ant Based Routing for WSNs......Page 67
Energy-efficient Ant Based Routing for WSNs......Page 68
Experimental Results......Page 69
Conclusions......Page 72
Introduction......Page 74
A Review of Aggregation Pheromone System (APS)......Page 75
The Model of the eAPS......Page 76
Updating the Pheromone Intensity and Sampling New Individuals......Page 77
Experimental Methodology......Page 80
Results......Page 81
Conclusions......Page 84
Introduction......Page 86
Estimation of Distribution Optimization Algorithms......Page 88
Estimation of Distribution Particle Swarm Optimization Algorithm......Page 89
Experimental Setup......Page 91
Results......Page 93
Conclusions......Page 95
Introduction......Page 98
The Knowledge Fusion Problem......Page 99
AntMiner+......Page 100
Decision Tables......Page 102
Using Decision Tables to Validate AntMiner+ Rulesets......Page 103
Incorporating Domain Knowledge in AntMiner+......Page 104
The Use of Heuristics to Incorporate Domain Knowledge......Page 105
Experiments......Page 106
Conclusion......Page 108
Introduction......Page 110
TSALBP-1......Page 112
The Algorithm......Page 113
Computational Results......Page 116
Results for SALBP-1 Instances......Page 117
Results for the TSALBP-1 Instances......Page 119
Conclusions and Outlook to the Future......Page 120
Introduction......Page 122
An Alternative Boundary Search Approach......Page 123
The Boundary Operators......Page 124
The Proposed Method......Page 125
Boundary Approach in ACO Algorithms......Page 126
Analysis of Results......Page 127
Study of the Application of ACO$_{\mathcal B}$......Page 128
Comparison with a State-of-the-Art Algorithm......Page 131
Conclusions and Future Work......Page 132
Introduction......Page 134
The S-bot and Its Simulator......Page 136
Controller......Page 138
Setup......Page 140
Results......Page 141
Conclusions and Future Work......Page 143
Introduction......Page 146
Abstracting PSO States and State Transitions......Page 148
Particle Communication as It Is and as It Could Be......Page 150
Experimental Setup......Page 151
Results......Page 153
Discussion......Page 155
Introduction......Page 158
The Mark-Ant-Walk (MAW) Algorithm......Page 159
Related Work......Page 160
MAW - Formal Proof of Correctness and Upper Time Bound......Page 161
Repetitive Coverage......Page 163
Using Other Metrics......Page 165
Comparing MAW to Other Algorithms......Page 166
Conclusions......Page 168
Introduction......Page 170
Incremental Local Search in Ant Colony Optimization for the Quadratic Assignment Problem......Page 172
Experiments......Page 173
Analysis......Page 175
Conclusions......Page 179
The Individual Discrimination Capabilities......Page 181
Hydrocarbons Profile and Communication in Ants......Page 182
The Foraging Strategy in Social Insects......Page 183
The Mean Field Model......Page 184
Results......Page 186
Discussion......Page 189
Introduction......Page 193
QAP, $\mathcal{MAX--MIN}$ Ant System and Iterated Ants......Page 194
Computational Study......Page 197
Study of ia$\mathcal{MMAS} Parameters......Page 198
Comparison of $\mathcal{MMAS} and ia$\mathcal{MMAS}$......Page 199
Discussion and Conclusions......Page 203
Introduction......Page 205
Methods......Page 207
Results......Page 211
Discussion......Page 213
Introduction......Page 217
$\mathcal{MAX--MIN}$ Ant System......Page 218
Number of Ants $m$......Page 219
Evaporation Rate $\rho$......Page 220
Exponent Values $\alpha$ and $\beta$......Page 221
Experiments......Page 223
Conclusion......Page 226
Introduction......Page 229
Preliminary Definitions......Page 230
Ant System......Page 231
Strongly-Invariant Ant System......Page 235
Conclusions......Page 236
Introduction......Page 238
Parallel Implementation of $\mathcal{MAX--MIN}$ Ant System......Page 239
Experimental Setup......Page 241
Results......Page 242
Conclusions......Page 246
Introduction......Page 249
Cell Definition......Page 250
General Use Placement Constraints......Page 251
Particle Swarm Optimization (PSO)......Page 254
Extend PSO Searching Space......Page 255
Overlap Detection and Removal Mechanism......Page 256
Experiments......Page 257
Conclusions......Page 259
Introduction......Page 261
PLANTS......Page 262
Parameter Optimization and Validation of PLANTS......Page 266
Virtual Screening......Page 269
Conclusions......Page 271
Introduction......Page 273
Overview......Page 274
Algorithm Description......Page 275
Modelling of Perceptional Noise......Page 277
Simulation Experiments......Page 278
Performance of the Algorithm in the Presence of Noise......Page 279
Glowworms......Page 280
Sound Source Localization......Page 281
Conclusions......Page 282
Motivation and Related Work......Page 284
Ant Colony Optimization......Page 285
AntDA: An ACO Algorithm for DA$rep$......Page 287
Transitioning from ${\langle d,q \rangle}$ Pairs to Servers......Page 288
Pheromone Update Rule......Page 290
Experimental Validation of AntDA......Page 291
Conclusion......Page 294
Introduction......Page 296
System Model......Page 297
Cross Entropy Ants (CE-ants)......Page 298
Rate Adaptation Strategies......Page 299
Fixed Rate......Page 300
Implicit Adaptation......Page 301
Case Studies of a National-Wide Internet Topology......Page 302
Concluding Remarks......Page 306
Introduction......Page 308
Pareto Ant Colony Optimization......Page 309
PACO with Path Relinking......Page 311
Evaluation Metrics......Page 313
Analysis......Page 314
Conclusion and Future Direction......Page 316
Introduction......Page 320
Unidirectional Case......Page 321
Bidirectional Case......Page 324
Summary and Discussions......Page 326
Introduction......Page 330
A Pure PSO Algorithm......Page 331
PSO with Local Search......Page 333
Experimental Results......Page 334
Conclusion......Page 336
Introduction......Page 338
Pheromone Update......Page 339
Methods to Avoid Premature Convergence......Page 340
Primary Experiments for Parameter Setting......Page 341
Comparison with Other Algorithms......Page 342
Conclusions......Page 344
Introduction......Page 346
General Ideas......Page 347
Parallel MMAS (PMMAS)......Page 348
Parallel ACS (PACS)......Page 349
General Description......Page 350
Comparison with the Sequential Algorithms......Page 351
Conclusion and Future Work......Page 352
Introduction......Page 354
Ant Algorithms......Page 355
Mathematical Formulation......Page 356
Computing Procedure......Page 357
Numerical Experiments......Page 359
Conclusion......Page 360
Introduction......Page 362
Formulation of the CFCLP......Page 363
Ant Colony Optimization for the CFCLP......Page 364
Computational Experience......Page 367
Conclusions......Page 368
Introduction......Page 370
Problem Definition......Page 371
Ant Colony System for Solving the OVRP......Page 372
Experiment Setting......Page 374
Computational Results and Comparison with Other Algorithms......Page 375
Conclusions......Page 377
Introduction......Page 378
Modified Ant-Based Clustering......Page 379
Parameters Analysis......Page 381
Memory Threshold......Page 382
Experimental Results......Page 383
Conclusion......Page 384
Introduction......Page 386
Orthogonal Experimental Design......Page 387
The Orthogonal Search Embedded ACO Algorithm......Page 388
Grid Selection......Page 389
Elitist Set Construction......Page 390
Computational Results and Discussing......Page 391
Conclusion......Page 392
Introduction......Page 394
The First Aid Problem......Page 395
Ant Colony System Model......Page 396
Reacting to a Change......Page 397
Experiment Environment......Page 398
Tests and Results......Page 399
Conclusion......Page 401
Introduction......Page 402
Gossip-Based Diffusion......Page 403
Artificial Ant for Information Dissemination......Page 404
Ant's Gossiping Activity......Page 405
Simulation Environment and Performance Criteria......Page 406
Results......Page 407
Conclusion and Future Directions......Page 408
Introduction......Page 410
The Proposed Tiled Architecture......Page 411
Computational Tile......Page 412
Agent Intelligence and Colony Behavior......Page 413
Cell Health and Fault Tolerance......Page 414
Synthesis and Experimental Results......Page 415
Performances in Case of Faults......Page 416
Conclusions......Page 417
Introduction......Page 418
Distributed Shortest-Path Algorithm......Page 419
Shortest Path Negotiation Phase......Page 420
Experiments......Page 423
Future Work......Page 424
The Fleet Preventive Maintenance Scheduling Problem - FPMSP......Page 426
Ant System for the FPMSP - $ASmnt$......Page 428
Tests and Applications......Page 429
Conclusions and Recommendations......Page 432
Introduction......Page 434
Inversion for Bottom Geoacoustic Parameters......Page 435
ACO and Other Metaheuristics for Inversion......Page 436
Tuning of $\mathcal{MAX-MIN}$ Ant System......Page 437
Results for Yellow Shark......Page 438
Uncertainty Analysis......Page 439
Conclusion......Page 440
Introduction......Page 442
Pheromone Models......Page 443
Using Higher Order Models......Page 444
Defining $C_c$, $f$ and $\tau_1$ for a Problem......Page 445
Utility of Higher Order Pheromones......Page 447
Conclusions......Page 448
Introduction......Page 450
Hybrid Particle Swarm Optimization......Page 451
Experiments on PSO Variants......Page 452
Conclusions......Page 456
Solution Construction......Page 458
Pheromone Update......Page 459
Pheromone as Probability......Page 460
Function Optimization Problem......Page 461
Multidimensional Knapsack Problem......Page 462
Conclusions......Page 464
ACS for the Minimum Vertex Cover Problem......Page 466
Random Proportional Transition Rule......Page 467
Parameterized Complexity......Page 468
Ant Colony System with Structure......Page 469
Challenging Benchmarks......Page 470
Random Graphs......Page 471
Conclusion......Page 472
Introduction......Page 474
Modified MHRM Heuristic......Page 475
Discrete Particle Swarm Optimization Algorithm......Page 477
Computational Results......Page 478
Conclusions......Page 480
Introduction......Page 482
SVM Classification Error......Page 483
The Proposed ACO Procedure......Page 484
Standard Datasets......Page 486
Electronic Nose Datasets......Page 487
Conclusion......Page 489
Introduction......Page 490
General Description of the Exhibition......Page 491
Module 1: Following Pheromone Trails......Page 492
Module 2: The Foraging Boe-Bot......Page 493
Module 3: Team Work......Page 494
Module 5: Artistic Design......Page 495
Conclusion......Page 496
Introduction......Page 498
Job Shop Scheduling and Solution Construction......Page 499
A Real-World JSP......Page 500
ACO for a Fuzzy JSP......Page 502
Solution Quality......Page 503
Conclusions......Page 504
Introduction......Page 506
General Modifications for the Exam Timetabling Problem......Page 507
Computational Experiments......Page 509
Comparison with Other Exam Timetabling Approaches......Page 510
Conclusion......Page 512
Experimental Result and Concluding Remarks......Page 514
502......Page 516
504......Page 518
Introduction......Page 520
Experiments and Preliminary Results......Page 521
Multiple Ant Colony System......Page 522
Summary......Page 523
Introduction and Problem Formulation......Page 524
Energy Efficient Sink Node Placement Using Particle Swarm Optimization......Page 525
512......Page 526
Approach......Page 528
Conclusion......Page 529
516......Page 530
Simulation Police Allocation and Criminal Activity......Page 532
Evaluation of the Learning Models......Page 533
Approach, Scenario and Results......Page 534
522......Page 536
600......Page 538