Multi Meta-Heuristics For Simulation Optimisation

Yıl 2014, Cilt: 10 Sayı: 1, 13 - 31, 01.04.2014

Serdar Bozoğlan Murat M.günal

Öz

Optimisation with simulation is a happy marriage of two Operations Research methods. In the last decade, the research in this field has accelerated and many researchers have been interested in Simulation Optimization (SO). New techniques have been developed as a result of this interest. Almost all commercial simulation software contains an optimization module. Generally, these modules exploit meta-heuristic methods; however, they do not allow the analyst to choose the method. The performance of meta-heuristic methods may depend on the problem type and therefore the choice of method is crucial. In this paper, we aim to fill this gap and presented an open-source java-based simulationoptimization code library. The library includes three heuristic methods; genetic algorithm, tabu search, simulated annealing, as well as three enumeration based methods; partial and complete enumeration, and a new neighbourhood-based heuristic method. At the simulation side, Simkit, an event-based and open-source simulation library, is used. At the application side, we defined a fictional optimisation problem and used it to compare performances of the algorithms. Our results demonstrated the potential benefits of having multi metaheuristics available in SO. eniyileme problemi tanımlanmış ve algoritmalar karşılaştırılmıştır. Çalışmanın sonuçları BE’de çoklu meta sezgisellere sahip olmanın potansiyel faydalarını göstermiştir

Anahtar Kelimeler

Simulation Optimization, heuristics, genetic algorithm, tabu search

BENZETİMLE ENİYİLEME İÇİN ÇOKLU META-SEZGİSELLER

Öz

Benzetim ile eniyileme iki yöneylem araştırması yönteminin mutlu bir evliliğidir.
Son on yılda bu alandaki araştırmalar ivme kazanmış ve birçok araştırmacı Benzetimle
Eniyileme (BE) alanına ilgi göstermiştir. Bu ilginin sonucu olarak yeni yöntemler de
geliştirilmiştir. Hemen hemen bütün ticari benzetim yazılımları bir çeşit BE modülü
içermektedir. Genel olarak bu modüller meta-sezgisel yöntemleri kullanmaktadır ancak
analizcinin yöntem seçimine izin vermemektedir. Meta sezgisel yöntemlerin problem tipine
bağlı olarak performansları değişebilir ve bu nedenle de yöntem seçimi önemlidir. Bu
makalede bu açığı doldurmayı hedefliyoruz ve açık kaynak kodlu Java tabanlı bir BE kod
kütüphanesi sunuyoruz. Kütüphane üç meta sezgisel; Genetik algoritma, yasaklı arama,
simulated annealing, ve üç sıralı aramalı algoritma; parçalı ve tam sıralı aramalı, ve yeni
bir komşuluk tabanlı sezgisel yöntemi içermektedir. Benzetim tarafında ise açık kaynak
kodlu ve olay tabanlı bir kütüphane olan Simkit kullanılmıştır. Uygulama olarak hayali bir eniyileme problemi tanımlanmış ve algoritmalar karşılaştırılmıştır. Çalışmanın sonuçları
BE’de çoklu meta sezgisellere sahip olmanın potansiyel faydalarını göstermiştir.

Anahtar Kelimeler

Benzetim, Eniyileme, Sezgisel yöntemler, yasaklı arama, genetic algoritma

Kaynakça

• applications for marrying simulation and optimization. In Proceedings of the Winter Simulation Conference, R .G. In-galls et al., Eds. IEEE, Piscataway, NJ. 80–86. for multi-objective simulation optimization. Applied mathematics and computation.2009 215 pp 3029-3035
• Proceedings of the 1999 Winter Simulation Conference.
• Simulation News Europe, April 2001: 1-6.
• Search. Proceedings of the 2000 Winter Simulation Conference. J. A.
• Joines, R. R. Barton, K. Kang, and P. A. Fishwick, eds. INFORMS Journal on Computing 14:192-215. Review, New Develop-mens, and Applications. Proceedings of the 2005
• Winter Simulation Conference. M. E. Kuhl, N. M. Steiger, F. B. Armstrong, and J. A. Joines, eds. genetic algorithms. SIMULATION 62(4), 242–253. using COMPASS. Operations Research 54:115-129. L. J.Hong, B.L. Nelson (2007) A framework for locally convergent random-search algorithms for discrete optimization via simulation. ACM
• Transactions on Modeling and Computer Simulation (TOMACS) 17(4), 19. A.Law, M.McComas (2000) Simulation-based optimization.
• Proceedings of the 2000 Winter Simulation Conference.
• A.M.Law (2007) Simulation Modeling and Analysis, 4th ed. McGraw-Hill, New York.
• Z.Michalewicz (1992) Genetic Algoritms + Data Structures =
• Evolution Programs, Springer Verlag, Berlin Hiedelberg. methodologies. A.H.Buss (2001) Basic Event Graph Modeling. Technical Notes,
• B.Dengiz, C. Alabas (2000) Simulation Optimization Using Tabu
• M.C. Fu (2002) Optimization for simulation: Theory vs. practice.
• M.C. Fu, F.W. Glover, J.April (2005) Simulation Optimization: A
• A.Homaifar, C. X. Qi, S.H. Lai (1994) Constrained optimization via
• L. J. Hong, B.L. Nelson (2006) Discrete optimization via simulation