Steiner minimum yayılan ağaç probleminin çözümünde genetik algoritmanın kullanılması

KORUKOĞLU, Serdar; İŞÇİ GÜNERİ, ÖZNUR

Steiner minimum yayılan ağaç probleminin çözümünde genetik algoritmanın kullanılması

ÖZNUR İŞÇİ GÜNERİ, (Muğla Üniversitesi, Fen Edebiyat Fakültesi, Muğla, Türkiye)

Serdar KORUKOĞLU (Ege Üniversitesi, Mühendislik Fakültesi, Bilgisayar Mühendisliği Bölümü, İzmir, Türkiye)

Mühendislik Bilimleri Dergisi

25 2

Yıl: 2006 Cilt: 12 Sayı: 3 Sayfa Aralığı: 429 - 437 Metin Dili: Türkçe İndeks Tarihi: 29-07-2022

Steiner minimum yayılan ağaç probleminin çözümünde genetik algoritmanın kullanılması

Öz:

Genetik algoritmalar (GA) stokastik bir arama yöntemidir ve bu nedenle optimum ya da optimuma yakın çözümler verebilmektedir. GA son yıllarda gezgin satıcı problemi, karesel atama, yerleşim, atölye çizelgeleme, ders/sınav programının hazırlanması, iletişim şebekelerinin tasarımı, montaj hattı dengeleme, en küçük yayılan ağaç problemi ve benzeri bir çok kombinatoryal optimizasyon problemlerine başarılı bir şekilde uygulanabilinmektedir. Bu çalışmada Steiner minimum yayılan ağaç probleminin genetik algoritma ile çözümü için java programı geliştirilerek performansı incelenmiştir. Literatürde daha önce çözülmüş test problemleri üzerinde yapılan denemeler sonucunda bu çalışmada önerilen GA yaklaşımı ile optimuma yakın sonuçlar elde edilmektedir. Çalışmada belirlenen noktalar için Steiner minimum yayılan ağaç problemi ve minimum yayılan ağaç problemi için uzunluklar ve kazanç değerleri hesaplatılmıştır.

Anahtar Kelime:

Using genetic algorithm to solve Steiner minimum spanning tree problem

Öz:

Genetic algorithms (GA) are a stochastic research methods, and they produce solutions that are close to optimum or near optimum. In addition to GA's successful application to traveling salesman problem, square designation, allocation, workshop table, preparation of lesson/examination schedules, planning of communication networks, assembling line balanced, minimum spanning tree type many combinatorial optimization problems it would be applicable to make the best comparison in optimization. In this study a Java program is developed to solve Steiner minimum spanning tree problem by genetic algorithm and its performance is examined. According to the tests carried out on the problems that were given before in the literature, results that are close to optimum are obtained in by GA approach that is recommended in this study. For the predetermined points in the study, length and gain are calculated for Steiner minimum spanning tree problem.

Anahtar Kelime:

Belge Türü: Makale Makale Türü: Araştırma Makalesi Erişim Türü: Erişime Açık

Altıparmak, F. ve Deniz, B. 1998. Genetik Algoritmalar, Gazi Üniversitesi Fen Bilimleri Enstitüsü Dergisi, 11 (3) : 523-542.
Altıparmak, F., Dengiz B. ve Smith, A. E. 2000. An Evolutionary Approach For Reliability Optimization in Fixed Topology Computer Networks, Transactions On Operational Research, 2 (1-2) : 57-75.
Austin, S. 1990. "An Introduction to Genetic Algorithms," AI Expert, 5 (3): 48-53.
Boruvka, O. 1926. O Jistem Problemu Minimaln İm, Prace Mor. Prrodove Spol. v Brne (Acta Societ. Scient. Natur. Moravicae, 3 : 37-58.
Clarke, L. 2002. The Steiner Problem http://www.css.tayloru.edu/~lclarke/srproj/Documentation2.html (12.08.2002)
Dengiz, B., Altıparmak, F. 1997. Kombinatoryal Optimizasyon ve Genetik Algoritmalar, Makina Mühendisleri Odası Endüstri Mühendisliği Dergisi, 9 (3): 3-14.
Dong, S. Z. 2002. Genetic Algorithm Applications, Mech 580, Quantitative Analysis, Reasoning and Optimization Methods in CAD/CAM and Concurrent Engineering, http://www.me.uvic.ca/~ zdong/courses/mech620/G A App.PDF (27.09.2002).
Goldberg, D. E. 1989. Genetic Algorithms In Search, Optimization And Machine Learning", Addison-Wesley, New York, 1-7.
Goldberg, D. E. and Deb, K. 1991. A Comparison Of Selection Schemes Used In Genetic Algorithms", Foundations Of Genetic Algorithms, 69-93.
Holland, J. R. 1975. Adaptation in Natural and Artificial Systems, University of Michigan Press, 2-3.
Harris, C. F. 1995. An Introduction To Steiner Minimal Trees On Grids, 111 : 3-17. http://www.cs.unr.edu/~fredh/papers/journal/Journal .html
İşçi, Ö. 2002. Genetik Algoritmaların Yöneylem Araştırmasındaki Uygulamaları, Doktora Tezi, Ege Üniversitesi, Fen Bilimleri Enstitüsü, İzmir.
Jones, J., Harris, C. F.A. 1996. Genetic Algorithm for the Steiner Minimal Tree Problem, Proc. ISCA's Int. Conf. on Intelligent Systems (IS '96), Reno, NV, 19-21.
Kruskal, J. 1956. On The Shortest Spanning Subtree Of A Graph And The Traveling Salesman Problem, Proceedings Of The American Mathematical Society, 7:48-50.
Oğuz, M., Akbaş S. 1999. Genetik Algoritmalar, Bitirme Tezi, YTÜ Endüstri Mühendisliği, http://artemis.efes.net/moguz/.
Prim, R. C. 1957. Shortest Connection Networks And Some Generalizations, Bell System Technology Journal, 36:1389-1401.
Starsky, W. 2001. Using Algorithm for Solving the Steiner Minimal Tree Problem http://appsrv.cse.cuhk.edu.hk/~csc6200/y99/applet/Steiner/.
Senior, C. 2002. Steiner Trees by: Jennifer Dorenbos, http://www.css.tavloru.edu/~jdorenbo/ senior project/ (08.02.2002).
Zhou, G., Gen, M. 1999. Genetic Algorithm Approach on Multi- Criteria Minimum Spanning Tree Problem" European Journal of Operational Research, 114:141-151.

APA	İŞÇİ GÜNERİ Ö, KORUKOĞLU S (2006). Steiner minimum yayılan ağaç probleminin çözümünde genetik algoritmanın kullanılması. , 429 - 437.
Chicago	İŞÇİ GÜNERİ ÖZNUR,KORUKOĞLU Serdar Steiner minimum yayılan ağaç probleminin çözümünde genetik algoritmanın kullanılması. (2006): 429 - 437.
MLA	İŞÇİ GÜNERİ ÖZNUR,KORUKOĞLU Serdar Steiner minimum yayılan ağaç probleminin çözümünde genetik algoritmanın kullanılması. , 2006, ss.429 - 437.
AMA	İŞÇİ GÜNERİ Ö,KORUKOĞLU S Steiner minimum yayılan ağaç probleminin çözümünde genetik algoritmanın kullanılması. . 2006; 429 - 437.
Vancouver	İŞÇİ GÜNERİ Ö,KORUKOĞLU S Steiner minimum yayılan ağaç probleminin çözümünde genetik algoritmanın kullanılması. . 2006; 429 - 437.
IEEE	İŞÇİ GÜNERİ Ö,KORUKOĞLU S "Steiner minimum yayılan ağaç probleminin çözümünde genetik algoritmanın kullanılması." , ss.429 - 437, 2006.
ISNAD	İŞÇİ GÜNERİ, ÖZNUR - KORUKOĞLU, Serdar. "Steiner minimum yayılan ağaç probleminin çözümünde genetik algoritmanın kullanılması". (2006), 429-437.

APA	İŞÇİ GÜNERİ Ö, KORUKOĞLU S (2006). Steiner minimum yayılan ağaç probleminin çözümünde genetik algoritmanın kullanılması. Mühendislik Bilimleri Dergisi, 12(3), 429 - 437.
Chicago	İŞÇİ GÜNERİ ÖZNUR,KORUKOĞLU Serdar Steiner minimum yayılan ağaç probleminin çözümünde genetik algoritmanın kullanılması. Mühendislik Bilimleri Dergisi 12, no.3 (2006): 429 - 437.
MLA	İŞÇİ GÜNERİ ÖZNUR,KORUKOĞLU Serdar Steiner minimum yayılan ağaç probleminin çözümünde genetik algoritmanın kullanılması. Mühendislik Bilimleri Dergisi, vol.12, no.3, 2006, ss.429 - 437.
AMA	İŞÇİ GÜNERİ Ö,KORUKOĞLU S Steiner minimum yayılan ağaç probleminin çözümünde genetik algoritmanın kullanılması. Mühendislik Bilimleri Dergisi. 2006; 12(3): 429 - 437.
Vancouver	İŞÇİ GÜNERİ Ö,KORUKOĞLU S Steiner minimum yayılan ağaç probleminin çözümünde genetik algoritmanın kullanılması. Mühendislik Bilimleri Dergisi. 2006; 12(3): 429 - 437.
IEEE	İŞÇİ GÜNERİ Ö,KORUKOĞLU S "Steiner minimum yayılan ağaç probleminin çözümünde genetik algoritmanın kullanılması." Mühendislik Bilimleri Dergisi, 12, ss.429 - 437, 2006.
ISNAD	İŞÇİ GÜNERİ, ÖZNUR - KORUKOĞLU, Serdar. "Steiner minimum yayılan ağaç probleminin çözümünde genetik algoritmanın kullanılması". Mühendislik Bilimleri Dergisi 12/3 (2006), 429-437.