Genetik Algoritmaların İşleyişi ve Genetik Algoritma Uygulamalarında Kullanılan Operatörler

Abstract

Genler, canlılardaki görünüş, davranış, kişilik gibi özellikleri belirleyen ve bu canlılarla ilgili bilgi edinmek üzere kullanılan birimler olması ile birlikte canlıya ait bir özelliği denetleyen kromozom parçası olarak tanımlanmaktadırlar. İlk kez bir mühendis ve biyolog olan Holland tarafından 1975 yılında kullanılan genetik algoritma (GA), canlılardaki genetik kod mantığı aracılığı ile karmaşık problemleri hızlı ve kolay bir biçimde en iyi çözüme ulaştırmayı hedeflemektedir. Genetik algoritmalar, bir çözüm uzayındaki her noktayı, kromozom olarak adlandırılan ikili bit dizisi şeklinde kodlamaktadır. Bu noktaların her birine ait bir uygunluk değeri vardır. Dolayısıyla, tek bir nokta yerine noktalar kümesini muhafaza etmektedir. Genetik algoritmalar, çözümlerin kodlanması, uygunlukların hesaplanması, seçim, çaprazlama ve mutasyon operatörlerinin uygulanması adımlarını içermekte olup bu operatörlerden faydalanarak yeni bir popülasyon oluşturmaktadır. Bu derleme makalesinde genetik çalışmalarda çözümü oldukça zor olan problemlerin çözümünü kolaylaştırmak ve kısa zamanda mümkün olan en iyi çözümü ortaya çıkarmak adına geliştirilmiş olan genetik algoritmaların işleyişi ve uygulamalarında kullanılan operatörler ele alınmıştır.

Keywords

• Genetik algoritma
• Genetik operatörler
• Seleksiyon
• Çaprazlama
• Mutasyon

Functioning of Genetic Algorithms and Operators Used in Genetic Algorithm Applications

Abstract

Genes are defined as the parts of chromosomes that determine features such as appearance, behaviour and personality in living things and are used to obtain information about these living things, as well as control a feature of the living thing. Genetic algorithm (GA), which was first used by Holland, an engineer and biologist, in 1975, aims to quickly and easily find the best solution to complex problems through the logic of the genetic code in living things. Genetic algorithms encode each point in a solution space as a binary string of bits called chromosomes. Each of these points has a fitness value. Hence, it preserves a set of points rather than a single point. Genetic algorithms include the steps of coding solutions, calculating fitness, applying selection, crossover, and mutation operators, and creating a new population by using these operators. In this review, operators used in the operation and applications of genetic algorithms, which have been developed to facilitate the solution of problems that are very difficult to solve in genetic studies and to reveal the best possible solution in a short time, are discussed.

Keywords

• Genetic algorithm
• Genetic operators
• Selection
• Crossover
• Mutation

References

1. Altıparmak F., Dengiz B. Genetik algoritmalar. Gazi Üniversitesi Fen Bilimleri Enstitüsü Dergisi 1998; 11(3): 523-541.
2. Altıparmak F., Dengiz B. Smith AE. An evolutionary approach for reliability optimization in fixed topology computer networks. Transactions On Operational Research 2000; 12(1-2): 57- 75.
3. Beasley D., Bull DR., Martin RR. An overview of genetic algorithms: Part 1, fundamentals. University Computing 1993; 15(2): 56-69.
4. Bhattacharyya S. Direct marketing performance modeling using genetic algorithms. Journal on Computing 1999; 11(3): 248-267.
5. Bolat B., Erol K., Imrak C. Genetic algorithms in engineering applications and the function of operators. Sigma 2004; 4: 264-271.
6. Bräysy O. Local search and variable neighborhood search algorithms for the vehicle routing problem with time windows. Vaasan yliopisto, 2001.
7. Brown EC., Sumichrast RT. CF-GGA: a grouping genetic algorithm for the cell formation problem. International Journal of Production Research 2001; 39(16): 3651-3669.
8. Davis L., Coombs S. Genetic algorithms and communication link speed design: theoretical considerations. In ICGA 1987. 252-256.

9. Deb K. Multi-objective optimisation using evolutionary algorithms: an introduction. In: Multi-Objective Evolutionary Optimisation for Product Design and Manufacturing Springer 2011. 3-34.
10. Della Croce F., Tadei R., Volta G. A genetic algorithm for the job shop problem. Computers & Operations Research 1995; 22(1): 15-24.
11. Eksin I., Erol OK. Evolutionary algorithm with modifications in the reproduction phase. IEE Proceedings-Software 2001; 148(2): 75-80.
12. Eren H. Akış tipi çizelgeleme problemlerinin genetik algoritma (GA) ile çözüm performansının artırılmasında deney tasarımı uygulaması. İstanbul Teknik Üniversitesi Fen Bilimleri Enstitüsü, Doktora Tezi, İstanbul, Türkiye, 2002.
13. Gen M., Cheng R. Genetic algorithms & engineering design. John Wiley& Sons. Inc. 1997; 10: 9780470172254.
14. Goldberg DE. Genetic algorithms in search, optimization, and machine learning. Addison. Reading, 1989.
15. Gonzalez EL., Fernandez MAR. Genetic optimisation of a fuzzy distribution model. International Journal of Physical Distribution & Logistics Management, 2000.
16. Holland JH. Adaptation in natural and artificial systems, ann arbor: University of Michigan Press, 1975.
17. İşlier AA. Üretim hücrelerinin bir genetik algoritma kullanılarak oluşturulması. Anadolu Üniversitesi Bilim ve Teknoloji Dergisi: A-Uygulamalı Bilimler ve Mühendislik 2001; 2(1): 137-157.
18. Jang JSR., Sun CT., Mizutani E. Neuro-fuzzy and soft computing-a computational approach to learning and machine intelligence [Book Review]. IEEE Transactions on automatic control 1997; 42(10): 1482-1484.
19. Koza JR. Genetic programming, on the programming of computers by means of natural selection. A Bradford Book. MIT Press; 1992.
20. Kurt M., Semetay C. Genetik algoritma ve uygulama alanları. Mühendis ve Makine 2001; 42(501): 19-24.
21. Man, KF., Tang, KS., Kwong, S. Genetic algorithms: concepts and designs. Springer Science & Business Media; 2001.
22. Özkan R. tek modelli deterministik montaj hattı dengeleme problemlerine genetik algoritma ile çözüm yaklaşımı. İstanbul Teknik Üniversitesi Fen Bilimleri Enstitüsü, Doktora Tezi, İstanbul, Türkiye, 2003.
23. Rechenberg I. Evolutionstrategie (Evolution strategy). Stuttgart: Frommann-Holzboog; 1973.
24. Sakawa M. Genetic algorithms and fuzzy multiobjective optimization. Springer Science & Business Media, 2002; 4.
25. Schlottmann F., Seese D. A hybrid genetic-quantitative method for risk-return optimisation of credit portfolios. In Proceedings of the Conference of Quantitative Methods in Finance, University of Technology, Sydney, Australia, 2001. 55.
26. Sinriech D., Samakh E. A genetic approach to the pickup/delivery station location problem in segmented flow based material handling systems. Journal of Manufacturing Systems 1999; 18(2): 81-99.
27. Taşkın Ç., Emel GG. Genetik algoritmalar ve uygulama alanları. Uludağ Üniversitesi İİBF Dergisi 2002; 21:129-152.
28. Vural, M. Genetik algoritma yöntemi ile toplu üretim planlama İstanbul Teknik Üniversitesi, Fen Bilimleri Enstitüsü, Doktora Tezi, İstanbul, Türkiye, 2005.
29. Yeniay MÖ. Taguchi deney tasarımı problemlerine genetik algoritma yaklaşımı. Hacettepe Üniversitesi, Fen Bilimleri Enstitüsü, Doktora Tezi, Ankara, Türkiye, 1999.
30. Yeniay Ö. An overview of genetic algorithms. Anadolu Üniversitesi Bilim ve Teknoloji Dergisi 2001; 2(1): 37-49.
31. Zhou Y. Study on genetic algorithm improvement and application. Worcester Polytechnic Institute, PhD Thesis, 2006.