M. Emin Aydin
A distributed evolutionary simulated annealing algorithm for combinatorial optimisation problems
Aydin, M. Emin; Fogarty, Terence C.
Authors
Terence C. Fogarty
Abstract
In this paper, the Evolutionary Simulated Annealing (ESA) algorithm, its distributed implementation (dESA) and its application to two combinatorial problems are presented. ESA consists of a population, a simulated annealing operator, instead of the more usual reproduction operators used in evolutionary algorithms, and a selection operator. The implementation is based on a multi island (agent) system running on the Distributed Resource Machine (DRM), which is a novel, scalable, distributed virtual machine based on Java technology. As WAN/LAN systems are the most common multi-machine systems, dESA implementation is based on them rather than any other parallel machine. The problems tackled are well-known combinatorial optimisation problems, namely, the classical job-shop scheduling problem and the uncapacitated facility location problem. They are difficult benchmarks, widely used to measure the efficiency of metaheuristics with respect to both the quality of the solutions and the central processing unit (CPU) time spent. Both applications show that dESA solves problems finding either the optimum or a very near optimum solution within a reasonable time outperforming the recent reported approaches for each one allowing the faster solution of existing problems and the solution of larger problems.
Citation
Fogarty, T. C., Aydin, M. E., Aydin, M. E., & Fogarty, T. C. (2004). A distributed evolutionary simulated annealing algorithm for combinatorial optimisation problems. Journal of Heuristics, 10(3), 269-292. https://doi.org/10.1023/B%3AHEUR.0000026896.44360.f9
| Journal Article Type | Article |
|---|---|
| Publication Date | May 1, 2004 |
| Journal | Journal of Heuristics |
| Print ISSN | 1381-1231 |
| Publisher | Springer Verlag |
| Peer Reviewed | Peer Reviewed |
| Volume | 10 |
| Issue | 3 |
| Pages | 269-292 |
| DOI | https://doi.org/10.1023/B%3AHEUR.0000026896.44360.f9 |
| Keywords | distributed evolutionary simulated annealing, multi-agent systems, job-shop scheduling, uncapacitated facility location, distributed resource machine |
| Public URL | https://uwe-repository.worktribe.com/output/1060449 |
| Publisher URL | http://dx.doi.org/10.1023/B:HEUR.0000026896.44360.f9 |