Genetic algorithms in engineering applications and the function of operators

Abstract

Keywords: Genetic Algorithms; crossover; mutation.

1. Gi̇ri̇ş

Sayısal optimizasyon yöntemlerinden olan genetik algoritmalar, evrimsel hesaplama tekniğinin bir parçasını oluşturmakta ve geleneksel yöntemlerle, çözümü zor veya hemen hemen imkansız olan problemlerin çözümünde kullanılmaktadır. Genetik algoritmalar, deneysel çalışmalarda optimizasyon aşamasında, endüstriyel uygulamalarda ve sınıflandırmalarda uygulama alanı bulunmaktadır. Mühendislik alanında en çok optimizasyon amaçlı olarak kullanılmakta ve diğer klasik yöntemlere göre daha iyi sonuç vermektedir. Genetik algoritmalar, bazı doğal olayları modelleyen stokastik algoritmalardır. Bu algoritmalar biyolojik evrimin işleyiş biçimini taklit eder.

Sorumlu Yazar/Corresponding Autor: e-mail:balpan@yildiz.edu.tr, Tel: (0212) 259 70 70/2213

Genetic Algorithms in Engineering Applications... Genetik algoritmalar doğal seleksiyon ve mekanizmasına dayanan sayısal optimizasyon algoritmalarıdır. Evrimsel hesaplama ilk olarak I.Rechenberg tarafından “Evrim Stratejileri” eserinde tanıtılmıştır [1]. İlk olarak John Holland evrim sürecini bir bilgisayar yardımıyla kullanarak genetik algoritmaları oluşturmuştur [2]. Holland’ın öğrencisi D.E.Golldberg 1989 yılında bu konuda çıkardığı kitabıyla genetik algoritmaların çeşitli konularda kullanılabileceğini göstermiştir [3]. 1992 yılında John Koza genetik algoritmayı kullanarak genetik programlamayı geliştirmiştir [4]. Bu çalışmada, genetik algoritmanın işlevleri ve yapısı ele alınmıştır. Ayrıca bu konuda çeşitli mühendislik alanlarında yapılmış çalışmalar irdelenmiş, konuyu açıklayıcı bir örnek üzerinde operatörlerin uygulanması ve etkileri incelenmiştir.

Algori̇tmalar

Konuyla ilgili çalışmalar incelendiğinde, araştırma alanı geniş ve karmaşık ise, konuyla ilgili bilgi az veya eldeki bilgi araştırma alanını daraltmada yeterli değilse, matematiksel analiz elde edilemiyorsa veya geleneksel araştırma metodları ile başarısız olunmuş veya iyi sonuç alınmamışsa genetik algoritmalardan faydalanıldığı görülmüştür. İncelenen literatürden önemli olanları aşağıda özetlenmiştir. So ve Chan, asansör kontrol sistemine genetik algoritmayı uygulamış ve ortalama bekleme zamanını bu yöntemle azaltmışlardır [5]. Tobita ve arkadaşları, asansör grup kontrol sisteminde kullanılan genetik algoritma için yeni bir metod tanıtmış, bina çevrimi ve çevre şartlarıyla diğer metodlar arasındaki farklılıkları anlatmışlardır [6]. Turğut ve Arslan, altı açıklıklı sürekli bir kirişte maksimum açıklık ve mesnet momentlerini veren hareketli yük kombinezonlarının genetik algoritmalarla otomatik bir şekilde düzenlenmesini incelemişlerdir. Sunulan metodun hesaplama hızı, tesir çizgileri yöntemi gibi klasik yöntemlerle yapılan çözüme kıyasla oldukça yüksek olduğunu göstermişlerdir [7]. Fığlalı ve Engin, optimum çözümü zor olan (NP-zor), çok makinalı akış tipi çizelgeleme problemlerinin genetik algoritma ile çözüm performansının arttırılmasına yönelik bir çalışma yapmışlardır. Sonuç olarak akış tipi çizelgeleme problemlerinin genetik algoritma ile çözümünde etkili olan parametreler ile genetik algoritmanın çözüm performansını artıracak parametre setlerini belirlemişlerdir [8]. Kandiller ve Küçükali, deniz savaşında filo konuşlandırma problemi ve akaryakıt tüketimi simülasyonu üzerine çalışmışlardır. Ortaya çıkan maksimum alan kapsama problemin çözümü için bir genetik algoritma geliştirilmişlerdir. Genetik algoritma çözümü, akaryakıt tüketim incelenmesi için geliştirilen simülasyon modeline girdi olarak kullanmışlardır. Bu model yardımıyla harp durumu, akaryakıt tüketimi açısından simüle edilmiş ve yüzer birliklerin harbe devamlılık süreleri analizi yapılmıştır [9]. Öztürk ve Yılmaz, makina tasarım optimizasyonu problemlerinin çözümünde genetik algoritmayı kullanmışlardır. Klasik yöntemlerle çözümü, uzun zaman alan ve optimuma ulaşılması sürecinde ıraksama veya lokal optimuma yakalama problemi içeren makina tasarım problemlerinin genetik algoritma yaklaşım ile optimizasyonunu açıklamışlardır [10]. Cortes ve arkadaşları ise asansör grup kontrolünü genetik algoritma ile analizini ve simülasyonunu yapmışlardır. Bu çalışmayla öğlen saatlerindeki yoğun trafik akışında yolcuların bekleme zamanı azaltmayı başarmışlardır [11]. Ele alınan problem asansör grup kontrollerinin analizi ve simülasyonu olduğundan, genetik algoritma uygulamasına elverişli olduğu görülmüştür. Bekiroğlu ve arkadaşları, çalışmalarında genetik algoritmada değer kodlaması kullanarak kafes sistemlerinin minimum ağırlıklı tasarımını amaçlamışlar ve değer kodlaması kullanılarak hazırlanan programın kafes sistemlerin genetik algoritma ile minimum ağırlıklı olarak boyutlandırılmasında etkin bir şekilde kullanıldığını göstermişlerdir [12].

Toğan yaptığı çalışmada genetik algoritma kullanarak çatı makaslarının farklı yüklemeler altında optimum tasarımlarını yapmıştır. Gerilme, burkulma ve çökme sınırlayıcılar göz önüne alınmış ve iki tip tasarım problemi incelemiştir. Önce çeşitli çatı makaslarının minimum ağırlıklı boyut optimizasyonları gerçekleştirilmiş daha sonra çatı makaslarının eleman kesit alanlarıyla birlikte optimum geometrilerini de bulacak şekilde boyut ve şekil optimizasyonları gerçekleştirilmiştir [13]. Bingül ve Söke yaptıkları çalışmada, farklı çaprazlama teknikleri kullanan genetik agoritmalar ve geliştirilmiş aşağı sol algoritmasının ortak kullanımıyla iki boyutlu giyontinsiz bir kesme problemine çözüm geliştirmişlerdir. 200x200 birimlik bir alan ile sınırlandırılmış bir büyük parça ve yerleşecek 29 adet birbirinden farklı düzgün dikdörtgen parçadan oluşan bir test problemi üzerinde çalışmışlardır. Çalışma sonucunda aynı problem için, farklı çaprazlama tekniklerinin birbirinden çok farklı sonuçlar verdiğini görmüşlerdir [14].

3. Geneti̇k Algori̇tmalarin Çalişma Prensi̇bi̇

Genetik algoritmalar doğal seçim ilkesine dayanan bir sayısal optimizasyon yöntemidir. Genetik algoritma, çözüm dizilerinden oluşan bir başlangıç nesliyle, çaprazlama ve mutasyon gibi doğal seçim operatörlerini kullanmaktadır. Genetik algoritmalar oldukça genel prensiplerle Şekil 1’de akış şemasında görüldüğü gibi çalışmaktadır. Öncelikle ele alınan problem için bir rastgele n kromozomlu populasyon oluşturulur. Daha sonra populasyondaki her bir kromozom için f(x) uygunluk fonksiyonu hesaplanır. Yeni bir populasyon oluşuncaya kadar aşağıdaki adımlar tekrar edilir: [Seleksiyon] : Uygunluk durumuna göre populasyondan iki tane kromozom, çaprazlanmak (crossover) amacıyla seçilir (çoğullama-reproduction). Burada uygunluk derecesi yüksek olanın seçilme şansı yüksektir. [Çaprazlama] : Seçilmiş olan ebeveyn kromozomlar, çaprazlama oranına göre yeni bireyler oluşturmak üzere çaprazlanırlar. Eğer çaprazlama uygulanmazsa bireyler atalarının tamamen kopyası olacaklardır. [Mutasyon] : Kromozom üzerindeki bazı dizilerin (DNA dizilerinin) yerleri ile oynanarak belirli mutasyon oranına göre değişiklikler yapılır. Yeni popülasyon kabul edildikten sonra, oluşturulan yeni populasyon eskileriyle yer değiştirilir. Hedeflenen uygunluk değerine ulaşıldığında program durdurulur ve populasyondaki en iyi çözüm alınır. B A Ş L A T

Değiştirme

Şekil 1. Genetik algoritmanın genel akış şeması Genetik algoritmalarda kromozomlarla bir başlangıç popülasyonu rastgele oluşturulur. Burada popülasyon genişliğinin belirlenmesi gerekmektedir. Büyük popülasyonlarda, çözüm

Genetic Algorithms in Engineering Applications... uzayı iyi örneklendiği için aramanın etkinliği artmakta, fakat buna bağlı olarak da arama süresi uzamaktadır. Küçük popülasyonlarda ise, çözüm uzayını yeterli örnekleyememe ve zamansız yakınsama oluşabilmektedir. Genetik algoritmanın her çevriminde, yığındaki dizilerin bir değerlendirme fonksiyonu yardımıyla uygunluk değeri hesaplanır [15]. Uygunluk fonksiyonu, kromozomları problemin parametreleri haline getirmekte ve bunlara göre hesaplama yapmaktadır. Genellikle genetik algoritmaların başarısı bu fonksiyonun verimli ve hassas olmasına bağlıdır. Genetik algoritmada bağımsız parametrelerin kromozomlar içinde kodlanması gerekmektedir. İki çeşit kodlama yöntemi bulunmaktadır. 1- İkili kodlama: En yaygın olarak kullanılan yöntemdir. Sayılar ikilik sisteme göre sıfır ve birden oluşmaktadır. 2- Permütasyonlu kodlama: Sıralama problemlerinde kullanılmaktadır. Her kromozom dizideki bir sırayı temsil eden sayılardan oluşmaktadır. Çoğullama (reproduction), başlangıç popülasyonu oluşturulduktan sonra yeni popülasyonun oluşturulabilmesi için seçim yöntemine karar verilmesi gerekmekte ve yüksek uyuma sahip bireylerin seçilme olasılığı daha fazla olmaktadır. Burada yüksek uyuma sahip bireyin bir sonraki kuşağa kopyalanması hedeflenmiştir. Seçim yöntemi olarak geliştirilmiş birçok yöntem bulunmakla beraber, rulet çemberi, turnuva ve elitist seçim yöntemleri en yaygın kullanılanlardır. Rulet Çemberi Seçim Yöntemi ilk defa Holland tarafından ortaya çıkarılmıştır [2]. Burada tüm bireylerin uygunluk değerleri bir çizelgede yazılır ve bu değerler toplanır. Tüm bireylerin uygunluk değerleri toplama bölünerek (0,1) aralığında sayılar elde edilir ve sayıların hepsi bir çizelgede toplanır. Çizelgedeki sayılar birbirine eklenerek rastgele olarak bir sayıya kadar ilerlenir ve bu sayıya ulaşıldığında son eklenen sayının ait olduğu çözüm seçilmiş olur. Turnuva Seçim Yönteminde yerine koyarak ya da koymadan rastgele t adet birey seçilir ve bu büyüklüğe turnuva genişliği adı verilir. Bu gruptaki en iyi birey, yeni popülasyona kopyalanır. Bu işlem kullanıcı tarafından önceden kararlaştırılan çevrim sayısı kadar tekrarlanır. Elitist Seçim Yönteminde popülasyonun en iyi bir bireyi korunup, popülasyonun geri kalan elemanlarını uyum orantılı seçim yöntemlerinden birini kullanarak yeni bireyler ile değiştirilir. Burada hedef en iyi uyum değerine sahip bireyin, genetik operetörler kullanıldığında kaybolmasını önlemektir. Yeni çözümler elde etmek için seçim yönteminden sonra uygulanan çaprazlama ve mutasyon adı verilen iki genetik operatör vardır.

Opti̇mi̇zasyonunda

Genetik algoritmaların nasıl çalıştığını göstermek için tek değişkenli bir fonksiyonun optimizasyonu örnek olarak ele alınmıştır [18]. Fonksiyon F(x) = x2 olup 0 ≤ x ≤31 aralığında fonksiyonu maximum eden x değerini bulmaktır. Çözümü zor olmayan bu fonksiyonu elle çözülebilmekte ve x = 31 için en yüksek değer vereceği açıkça görülmektedir. Problemin çözümü

Genetic Algorithms in Engineering Applications... için ikili kodlama kullanılmış ve kromozomlar 5 bitlik dizilerden oluşturulmuştur. İlk populasyon oluşturulmuş ve maximum değer olarak 24 (242 =576 ) elde edilmiştir. Problemin çözümü için çaprazlama ve mutasyon olmak üzere iki temel genetik operatör kullanılmıştır. Çizelge 1’de F(x) fonksiyonun başlangıç populasyonu ve uygunluk değerleri gösterilmiştir. Fonksiyonun ortalama değeri, Fi = ∑

Çizelge 1. Başlangıç populasyonu ve uygunluk değeri çizelgesi Başlangıç Fi / ∑ Fi x x2 Fi / Fi Populasyonu 01101 13 169 169 / 1170 = 0,14 169 / 293 = 0,58 11000 24 576 576 / 1170 = 0,49 576 / 293 = 1,97 01000 8 64 64 / 1170 = 0,06 64 / 293 = 0,22 10011 19 361 361 / 1170 = 0,31 361 / 293 = 1,23

Çizelge 1’de bulunan Fi / Fi değerleri dikkate alınarak yapılan çaprazlama neticesinde ele alınan fonksiyonun çaprazlama değerleri Çizelge 2’de verilmiştir.

Çizelge 2. Çaprazlama Çizelgesi Populasyon Eşleştirme Çaprazlama Havuzu 0110 / 1 2 4 1100 / 0 1 4 11 / 000 4 2 10 / 011 3 2

Çizelge 2’de görülen çaprazlama işlemden sonra ele alınan fonksiyon yeni populasyonu ve uygunluk değeri Çizelge 3’de görülmektedir. Burada Fi değeri Fi = ∑

Çizelge 3. Yeni populasyon ve uygunluk değerleri Yeni x x2 Fi / Fi Populasyon 01100 12 144 144 / 439 = 0,32 11001 25 625 625 / 439 = 1,42 11011 27 729 729 / 439 = 1,66 10000 16 256 256 / 439 = 0,58

Çizelge 3’de görülen üçüncü satırdaki yeni populasyondan 11011 kromozomuna mutasyon uygulandığında 11111 değeri elde edilir. İkili kodda bulunan (11111) değerinin ondalık karşılığı ise (11111)2 = 3110 olacaktır. Bu ise aranan maksimum x değeridir.

5. Sonuç

Genetik algoritmalar, evrimsel hesaplama tekniğinin bir parçasını oluşturmakta ve geleneksel yöntemlerle çözümü zor veya hemen hemen imkansız olan problemlerin çözümünde yaygın olarak kullanım imkanı bulmaktadır. Mühendislik alanında, daha çok optimizasyon için kullanılmakta ve diğer klasik yöntemlere göre daha iyi sonuç verdiği gözlemlenmektedir. Bu çalışmada, genetik algoritma yöntemi genel hatlarıyla incelenmiş ve en iyi bireyi elde etmek için kullanılan çaprazlama ve mutasyon operatörleri, yapıları ve kullanım yerine göre özellikleriyle karşılaştırmalı olarak incelenmiştir. Ele alınan bir örnek problemde, çaprazlama ve mutasyon operatörleri kullanılarak üçüncü nesilde mutasyon uygulanarak en iyi sonuç elde edilmiş ve böylece genetik algoritma ile optimizasyon gerçekleştirilmiştir. Genetik algoritmalar, ele alınan basit problemden, daha zor ve hesaplaması daha karmaşık matematiksel ifadelere (türev ve integral gibi) ve değişik mühendislik alanlarındaki optimizasyon probleminde başarılı ve tatminkar neticeler vermektedir.

Share and Cite