Buradasınız

Anasayfa » Content

STEINER MİNİMU M YAYILAN AĞAÇ PROBLEMİNİN ÇÖZÜMÜNDE GENETİK ALGORİTMANIN KULLANILMASI

USING GENETIC ALGORTIHM TO SOLVE STEINER MINIMUM SPANNING TREE PROBLEM

Journal Name:

  • Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi

Publication Year:

  • 2006

Key Words:

Keywords (Original Language):

Author NameUniversity of AuthorFaculty of Author
Abstract (2. Language): 
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 and minimum spanning tree problem.
Bookmark/Search this post with
Abstract (Original Language): 
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.
FULL TEXT (PDF): 
PDF icon arastirmax-steiner-minimu-m-yayilan-agac-probleminin-cozumunde-genetik-algoritmanin-kullanilmasi.pdf
  • 3
429
437
  • Turkish

REFERENCES

References: 

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 Algorithms," AI Expert, 5 (3) : 48-53.
to Genetic
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/srproi/Documen tation2.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/iournal/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,
1 9 -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/S teiner/ .
Senior, C. 2002. Steiner Trees by: Jennifer Dorenbos, http://www.css.tayloru.edu/~idorenbo/ 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.

Thank you for copying data from http://www.arastirmax.com