Bu site emekli olmuştur. Arşiv amaçlı olarak BT AKADEMİ sponsorluğunda yayın hayatına devam etmektedir.




C#nedir?com
 
YAZAR HAKKINDA
Yaşar Gözüdeli
Yaşar Gözüdeli
http://www.csharpnedir.com/
İletişme geçmek için tıklayın.
10 Makalesi yayınlanmakta.
Yazar hakkında detaylı bilgi için tıklayın.
Yayınlanan diğer makaleleri için tıklayın.
İlgili etiketler: algoritma bireyin bireyler burada denir. deterministik farkli genetik genlerin makale makalenin rastgele sayisi sinifinin uygunluk C# / VC#/.NET Yaşar Gözüdeli
 
YAZI HAKKINDA
Türü : Makale
Serbest Köşede C#nedir?com üyelerinin hazırladıkları yazılar yayınlanır. Bu yazılar editör incelemesine girmeden yayınlanır.
Seviyesi : İleri
Kategori : C# / VC#/.NET
Yayınlanma Tarihi : 14.1.2005
Okunma Sayısı : 36290
Yorum Sayısı : 1     yorum yaz
Site İçi AramaSİTE İÇİ ARAMA
Üye Girişini AçÜye GİRİŞİ
Üye girişi için tıklayın.
Kullanıcı Adı
Şifre
 
Beni her zaman hatırla
Bir hafta boyunca kullanıcı bilgilerinizi kullanıcı çıkışı yapana kadar hatırlar. (Paylaşılan bilgisayarlarda önerilmez.)
 
Şifremi / Kullanıcı Adımı unuttum.
 
.net TV RSS Serbest KÖŞE (?)
Serbest Köşede C#nedir?com üyelerinin hazırladıkları yazılar yayınlanır. Bu yazılar editör incelemesine girmeden yayınlanır.
emre TAŞ
Silindi
emre TAŞ
yazının devamı >
emre TAŞ
silindi
emre TAŞ
yazının devamı >
emre TAŞ
silindi
emre TAŞ
yazının devamı >
emre TAŞ
silindi
emre TAŞ
yazının devamı >
emre TAŞ
silindi
emre TAŞ
yazının devamı >
Makale Gönder Bende Yazmak İstiyorum
.net TV RSSBlogroll
Turhal Temizer
Conda install environment.yml Package 29.3.2024
Turhal Temizer
Mac OS/X Removing CUDA 29.3.2024
Burak Selim Şenyurt
Kurumsal Yazılımcının Oyun Geliştirme ile İmtihanı 29.3.2024
Burak Selim Şenyurt
Matematik ve Oyun Programlama - Missile Command - Final 29.3.2024
  Diğer Herşey
Sponsorlar
BT Akademi
Medya Portakal
Video Hosting Sponsoru
Csharpnedir.com bir Ineta üyesidir
Uzman Abi
Her Yönüyle C# - Sefer Algan
Genetik Algoritma Kullanarak Makale Yerleşimi Optimizasyonu
 
Kapat
Sayfayı Yazdır Sık Kullanılanlara Ekle Arkadaşıma Gönder MySpace Del.Ico.Us Digg Facebook Google Mixx Reddit StumbleUpon
Bu makalede, yapay zeka tekniklerinden, genetik algoritma kullanarak bir sayfada yer alan makaleleri iki sütunda gösterme işlemini, en az satırda en çok makale özeti olacak şekilde optimize edeceğiz. Genetik algoritma, bir çözümün en iyisini bulmak için özellikle çok fazla ihtimalin karşılaştırılması gerekiyorsa, kullanılabilen bir "meta-heuristic" yoptimizasyon yöntemidir ve her zaman en iyiyi bulmayı vaadetmediği halde, hep en iyiye yakın çözümlerden birini elde etmemizi sağlar.

1.Giriş

Optimizasyon, hayatın hemen her alanında gerekliliği kaçınılmaz bir kavram olup, kazancı maksimize veya kaybı minimize etmeyi hedefler. Bu amaç için bir çok yöntem kullanılabilir. Şayet kullanılan yöntem(veya algoritma) parametreleri belli bir probleme her uygulanışında aynı sonucu veriyorsa, bu tür yöntemlere deterministik yöntemler denir. Deterministik yöntemler, genellikle en iyi bir tek çözüm için kodlanırlar.

Deterministik yaklaşımlar her durum için, kaynaklar nedeniyle mümkün olmayabilir. Örneğin bir satranç oyunu yazarken, bir taşın bir hamlesinin oyunun sonucuna etkisini denetlemek gerkir. Bu amaç için oluşturulan oyun ağacı(game tree) bu karmaşıklığa örnek verilebilir. Böyle bir oyun ağacında, ortalama olarak en iyi hamleyi seçmek için hamle başına (35^50^)^2 olasılığı denemek gerekir. (Satranç için Game Tree ile ilgili Internet’ten araştırma yaparak formülün kaynağını bulabilirsiniz). Alfa-Beta budaması, min-max arama benzeri olasılık azaltma yöntemleri ile bu sayı belli oranlarda azaltılsa bile bu türden bir deterministik programı, şu anda sıradan bir PC’de çalıştırmak olası değildir. Bu tür durumlarda bir yaklaşım olarak deterministik olmayan(non-deterministik) yöntemlerin kullanımı ele alınabilir.

Deterministik olmayan yaklaşımlar, aynı durum için farklı çalışmalarında aynı sonucu garanti etmeyen yöntem veya algoritmalardır. Yani bir satranç oyununda aynı pozisyon için program ilk çalışmasında A7 karesine oynamayı çözüm olarak verdiği halde, sonraki denemede A3’ü uygun çözüm olarak verebilir.

Meta Sezgisel(meta-heuristic) yöntemler deterministik olmayan yöntemlerin bir alt grubudur ve en iyi çözümü garanti etmemekle birlikte, denenmesi gereken ihtimallerin çok fazla olduğu durumlarda, daha az deneme ile "iyi" bir çözüm önermek amacıyla kullanılırlar. Genetik algoritma, 1970’li yıllarda John Holland tarafından ortaya atılmış, 1989 yılında David E. Goldberg’in yayınladığı, uygulanabilirliğin çeşitli alanlarda gösterildiği bir kitap ile popülerlik kazanmıştır.

Problem

Bizim bu makalede ele alacağımız problemin, deterministik yöntemlerle çok basit bir çözümü olmasına rağmen, genetik algoritmayı kavratması açısından basit bir örnek olduğu için, genetik algoritma ile ele alacağız.

Özet olarak problem şu, Elimizde 2n kadar makale var. Ama bu makaleleri iki sütunda göstermek istiyoruz. Bu durumda ikisi eşit olmayan makaleler, aynı satıra geldiğinde belli bir boşluk oluşacaktır(Şekil 1). Bu nedenle de bu boşlukları azaltacak bir yöntemi genetik algoritma ile hesaplamayı ele alacağız. Sorun ve çözümü şekil.1 ve şekil.2 ’de görülmekte.


Şekil 1 : Rasgele veya uzunluk dışında bir unsura göre sıralanmış, örneğin yayına giriş tarihi, makale yerleşimi. Boşluklar turuncu ile gösterilmiştir.
Şekil 2 :Yerleşimdeki boşlukların optimize edilmiş hali. Birbirine yakın sayıda satır kaplayan makaleler yan yana getirilerek çözüm elde edilmiştir. Elimizdeki makale sayısını 100 olarak düşünürsek, olasılıklar üstünden ilerlediğimizde, 100 makalenin 100! Farklı şekilde dizilebileceğini görürüz. Genetik algoritmayı, rastgele sıralanmış makalelerden başlamak üzere, genetik operatörler yardımıyla en iyiye yakın dizilişleri elde etmek için kullanacağız. Bu olasılıkları denemeye göre oldukça kolay bir deterministik çözümü ayrıca, makalenin en sonunda sizlerle paylaşacağım.

Genetik Algoritma’ya Hızlı Bir Bakış

Genetik Algoritmadan burada kısaca bahsedeceğim. Daha geniş bilgi için, Internet’ten arama yapabilirsiniz. Konunun daha iyi anlaşılması için terimlerle birlikte genetik algoritmayı tanımaya çalışalım.

Çözümün her bir parçasına gen denir. Aslında çözüm, aynı genlerin farklı dizilişlerinden en iyi olanı seçmektir. Bizim örneğimizde, yerleştirilmesi gereken her makale bir gendir. Genlerden her birinden eksiksiz-fazlasız sadece bir adet bulunduran her bir yapıya birey(veya kromozom) denir. Örnek durum için iki farklı birey, şekil.1 ve şekil.2’de görülmektedir. Bu iki durum için, gen sayısı 4 diye düşünebiliriz. Dikkat edilirse, bireyler arasında değişen tek şey, genlerin sırasıdır. Her bir bireyin gen sıralarındaki bu farklılıklarının çözüm üstündeki etkisini yansıtacak tek bir fonksiyon bulunur. Bu fonkisyon probleme bağlıdır ve bireyin çözüme yaklaşmasını ifade edecek bir hesaplamadan ibarettir. Bu fonksiyona uygunluk fonksiyonu(fitness function) denmektedir. Bu fonksiyondan elde edilen sonuca da birey uygunluk değeri denmektedir. Birden fazla bireyden oluşmuş bireyler topluluğuna populasyon denir. Literatürde, iyi bir çözüm için, genetik algoritmanın 100 ile 300 bireyden oluşan bir populasyon ile çalıştırılması önerilmektedir.

Herhangi bireyde, genlerin dizilişlerinde bir kurala bağlı olmaksızın, nedensiz ve düşük ihtimallerle meydana gelen değişikliğe mutasyon denmektedir. Çaprazlama , populasyonda yer alan iki bireyin karşılıklı ama rastgele bir veya daha fazla noktadan bölünüp bu parçaların birleşmesi sonucunda ortaya çıkan ve her iki bireyden de farklı olan iki birey üretmeye verilen addır. Bu işlemin sonucunda, her iki bireyde de tekrarlayan ve dolayısıyla da eksik kalan genler olabilir. Bu nedenle bir tamirat yapmak gerekecektir.

Nesil (Jenerasyon), popülasyondan çaprazlama, mutasyon ve elitizm gibi yöntemlerle elde edilen ve onun yerini alan yeni birey topluluğuna verilen addır. Elitizm , bir popülasyondaki en iyi n bireyin, yeni popülasyona hiç bir işleme tabi tutulmadan, kontenjandan aktarılmasıdır. Bu kontenjana elitizm kriteri denir. Burada amaç, bir önceki neslin kazanımını korumaktır. Ancak çok fazla bir sayı verilirse egemen birey sorunu başlar ve en iyi başka bir bireyin türetilmesi zorlaşır.

Genetik algoritmanın kaç nesil veya hangi doğruluk değerine kadar devam ettirileceği problemi çözen kişiye kalmış bir seçimdir. Basitçe problem şu şekilde uygulanır:

  1. Rasgele veya bir kurala bağlı olarak bir başlangıç popülasyonu oluşturulur.
  2. Bu popülasyondan elitizm, çaprazlama ve mutasyon sonucunda yeni popülasyon oluşturulur
    1. Elitizm yapılacaksa, oluşturulmuş pülasyon için uygunluk değerleri hesaplanır ve en iyi n değer kontenjandan yeni nesle aktarılır. Burada n parametrik olabilir.
    2. Çaprazlamaya girecek bireyler, rastgele veya Rulet Tekerleği ile seçilebilir. Biz rastgele seçtik. Rulet tekerleği için Internet’ten arama yapabilirsiniz.
    3. Çaprazlama tek noktadan böldükten sonra veya birden fazla noktadan böldükten sonra, karşılıklı genleri değiştirerek yapılabilir.
    4. Çaprazlama sonucunda doğan yeni iki bireyden her ikiside veya sadece bir tanesi veya belli bir doğruluk değerinin üstündeki bireyler alınabilir.
    5. Mutasyon işlemi için verilen oran dahilinde bireyler mutasyona tabi tutulur.
  3. 2 nolu işleme, belli bir nesil sayısı kadar veya en iyi bireyin belli bir uygunluk değerine kadar devam edilir.
    1. Bu işlemlerden sonra en iyi birey çözüm olarak alınır.

Gerçekleme

Yukarıda özet olarak geçilen genetik algoritma, makale özetlerinin yerleşim planlarını optimize etme sorununa adapte edilirken, kullanılan araç ve yöntemleri bu bölümde ele alacağız. Dil olarak C#, veritabanı olarak taşınabilirliğindeki kolaylık nedeniyle MS Access ve ortam olarak da ASP.NET sayfalarını kullanacağız. Buradaki istatistikler, Intel Centrino 1.6 GHz işlemci ve 512MB RAM üstünde, Windows XP Professional işletim sistemi üstündeki deneyleri yansıtmaktadır.

Veritabanı

Veritabanı olarak MS Access kullanacağız. Bu, herhangi bir sitedeki makalelerin tutulduğu temel tablo olabilir. icerikKOD sütununda her bir makaleye ait tekil kod tutulmaktadır. baslik, Her bir makalenin başlığını tutan sütundur. Spot , her bir makaleye ait özetlerin yer aldığı sütundur. baslangicTarihi , makalelerin yayına giriş tarihini, durum makalenin yayında olup olmadığını, son olarak bitisTarihi de makalenin yayından kalkacağı tarihi göstermektedir.

Diğer sütunlar, buradaki problemin bir parçası olmamasına rağmen bir içerik yönetim sisteminde bulunması gereklilik arzettiğinden burada da yer almaktadır. icerik, makalelerin içeriğini göstermektedir. kategoriKOD , her bir makalenin hangi kategori altında çıkacağını göstermektedir.


Şekil 3 : Probleme uygun örnek veritabanı tasarımı

Amacımız, şu anda yayında olan makalelerden, yayın tarihine göre baştan 2n adedini seçip, düzgün bir şekilde sayfaya iki sütun halinde en az yer kaplayacak şekilde yerleştirmeyi sağlamaktır.

Bu tasarım ve içerisine eklenmiş 50 kadar makale bilgisinden sonra, veri katmanı ile işimiz bitti. Şimdi iş katmanını kodlayalım:


Şekil 4 :Kullanacağımız birimlerin UML Class diyagramı

Gen Yapısı

Karşılaştırmaların hızlı olması açısından, gen bilgileri stack türü bir değişken ile gerçekleştirilmiştir. Yapıyı şu şekilde oluşturalım:


Şekil 5 : Gen struct’ının yapısı

Genler, her bir makaleye ait bilgileri tutmaktadır. Her bir bireyde, bu genlerden, sayfaya yerleşecek makale sayısı kadar bulunacaktır.

Birey Sınıfı

Birey sınıfını özet olarak şu şekilde kodlayalım. Detaylar için ekteki kodları gözden geçirebilirsiniz. Burada, özellik ve metodları özet olarak ele alacağım. Öncelikle, Birey sınıfı, IComparable arayüzünü gerçeklemektedir. Çünkü, birazdan kodlayacağımız, Populasyon sınıfının ArrayList bir özelliğinde, bireyler tutulmakta ve bu bireyler, yeri geldiğinde ArrayList.Sort() metodu yardımıyla, uygunluk(fitness) değerlerine göre sıralanmaktadır. Bu sıralama için, birey sınıfının IComparable arayüzünü gerçeklemesi(CompareTo metodunun gerçeklenmesi) gerekmektedir


Şekil 6 : Birey sınıfının özet bir görünümü

Uzunluk özelliğinde, bireydeki gen sayısı tutulmaktadır. gecerliDogruluk özelliği, çözüme uygunluk derecesini tutmaktadır ve default değer olarak 100 verilmiştir. Boş geçen her bir satır için, bir puan’lık ceza verilmektedir(uygunluk hesaplaması bu şekilde kurgulanmıştır). bireyGenleri dizisinde, herhangi bir bireye ait genlerin dizilişleri tutulacaktır. caprazlanacakBirey, bir Birey sınıfını işaret etmekte olup, çaprazlama aşamasında, dışarıdan gelen nesneyi tutmak üzere kodlanmıştır. yeniBirey1, çaprazlamanın sonucunda elde edilen yeni bireyi, yeniBirey2 de aynı çaprazlamadan çıkan ikinci bireyi göstermektedir.

CaprazlanacakBirey , sadece yazılabilir bir özellik olup, dışarıdan gelen bir Birey nesnesini, private değişkene aktarmaktadır. GecerliDogruluk da okunabilir bir özellik(property) olup, bireye ait geçerli uygunluk değerini vermektedir.

YeniBirey1 ve YeniBirey2 özellikleri de birer sadece okunabilir özellik olup, çaprazlamadan sonra oluşan bireylerin okunmasını sağlamak amacıyla ekledik.

Bunların dışında, birey sınıfına ait iki adet yapıcı metod bulunmakta. Bunlardan biri boş bir birey türetirken, diğeri, başlangıç aşamasında kullanılmak üzere yazılmış bir aşırı yükleme ve dışarıdan bireye ait genleri alarak işe başlamakta.

GenleriTanimla metodu, boş bir bireyin genlerini gen havuzundan rasgele seçip bütün genleri bir defa barındıran birey haline getirmek için kullanılmaktadır. Bu nedenle, Birey sınıfının kendisine özel bir metoddur.

BireyCaprazla metodu dışarıdan da çağrılabilmektedir. Ancak bu metod çağrılmadan önce, CaprazlanacakBirey özelliği ile, eldeki birey nesnesine, çaprazlanacağı bireyin atanması gerekir.

Mutasyon metodu, belirtilen mutasyon oranı olasılığında bir rastgele sayı üretip, elde edilen sayının aralığına bakarak rasgele iki genin sıralarını değiştirip değiştirmeyeceğine karar vermek üzere kodladığımız herkese açık bir metoddur.

Son olarak GenTamircisi metodu, genlerin mutasyon sonucunda bozulmaları halini denetleyip, her şeye rağmen her genden birey başına sadece bir adet kullanıldığını ve eksik gen bulunmadığını garanti etmek üzere oluşturulmuş bir metoddur.

Burada, özellikle ele alınması gereken bir metod olarak RandomSayiUretici metodunu ele almakta fayda var. Çünkü Web uygulamaları, belli bir çekirdek değer ile başladıklarından her bir istek geldiğinde aynı rastsal sayıyı üretirler. Bunu önlemek için, Birey sınıfının bu metodunda bir rasgele sayı üreticisi temel kütüphane(base library)’den türetilmiş ve http response buffer’a kaydedilerek durumunu her bir istek için koruması sağlanmıştır. Böylelikle, her seferinde aynı çekirdek değer ile başlayan rastsal sayıların üretimini engellemiş olduk.

Popülasyon Sınıfı

Kodlayacağımız en kapsamlı sınıf olan Populasyon sınıfına bir göz atalım:

Herkes tarafından erişilebilir bir genHavuzu adında gen dizisinden oluşuyor. Bu dizi, sınıfın özel GenHavuzu() adlı metodu tarafından veritabanına bağlanılarak doldurulmakta. Bir nevi Nuh’un gemisi diyebileceğimiz bu dizinin amacı, her genden bir adet bulundurarak, eksik genin tespitini kolaylaştırmak.

mutasyonIhtimali değeri bir float değer olup, %1 başlangıç değeri ile tanımlı ve bir bireyin mutasyona uğrama ihtimalini tayin etmek için kullanılmakta.

bireySayisi özel değişkeninde, popülasyonun bulunduracağı birey sayısı tutulmakta. IterasyonSayisi ise, genetik algoritmanın kaç adım çalıştırılacağını göstermekte ve 10 başlangıç değeri ile tanımlı.


Şekil 7 : Populasyon sınıfının özet bir görünümü YeniPopulasyon, asıl genlerin değişimini ve bireylerin gelişimini sağlayan bir metod. Bu metoda, sırayla bütün bireyler için doğruluk değeri hesaplanmakta, ardından en iyi bireyler elitizm kriteri dahilinde yeni nesile aktarılmakta. Ardından kalan kontenjan, rastgele seçilen iki bireyin çaprazlanması ile elde edilen iki yeni birey her seferinde aktarılarak yeni nesil oluşturulmakta ve son olarak da nesil mutasyona tabi tutulmaktadır. Bütün bu işlemler, iterasyon sayısı kadar tekrarlanmaktadır.

EnIyiBirey metodu, eldeki popülasyonu, ceza puanına göre sıralayarak en az ceza alan bireyi döndürmektedir.

ASP.NET Ortamına Dair Bazı Düzenlemeler

ASP.NET ortamında, daha uygun bir bağlantı ifadesi için, Access veritabanının yolu Server.MapPath ile çekilip, Global.ConnStr adı ile erişime hazır hale getirilmektedir.

Yine ASP.NET uygulamasının CodeBehind sayfasından, bir adet Populasyon nesnesi nüshalandırılmakta ve bu nüsha üstünden, genetik algoritma çalıştırıldıktan sonra en iyi birey, yine bu arka plandaki derlenmiş dosya tarafından, bir döngü içerisinde,( en iyi bireye ait gen dizisi) HTML ortamına yazdırılmaktadır.


Şekil 8 : Mükemmel olmasa da iyi bir yerleşim planı elde edilmektedir.

Sonuç

Her ne kadar, deterministik yöntemlerle rahat bir şekilde çözülebilecek bir sorunu ele almış olsak da, neticede genetik algoritmanın bu konuda ne kadar başarılı olduğu görülmektedir. Olayın kötü tarafı, genetik algoritma gibi meta-sezgisel yaklaşımların bir iterasyon mantığı dahilinde iyileştirmede bulunması ve burada kullanılan sunucu taraflı programlamanın da iterasyonlara karşı zayıf bir platform olması en azından bugünkü kaynaklarla bu tekniğin pratikte pek uygulanabilir olmadığını göstermektedir.

Başta söz verdiğim üzere, deterministik çözüme yer verelim; makale özetlerini uzunluklarına göre sıraladıktan sonra, mod 2’ye bağlı olarak ikişer’li yan yana koyduğumuz zaman çok iyi bir çözümü elde edebiliriz. Ancak bu yöntem örneğin güncel makalelerin daha üstte çıkmaya meyilli olduğu bir esnek çözüme müsaade etmez.


Şekil 9 : Uzunluklarına göre sıralanmış makaleler
Şekil 10 : Makalelerin Deterministik yaklaşım ile sıradan mod 2 ile ikili sütunlanmış hali


Şekil 11 : Eşit uzunluktaki makaleleri yan yana getirmeyi azamiye çıkararak elde edilmiş bir diğer deterministik optimizasyon her zaman olmasa da bazı durumlarda aynı sonucu vermekte.


Uygulama Projesi


Kaynaklar

[1] "Web Newspaper Layout Optimization Using Simulated Annealing" Gonzalez, J.; Rojas, I.; Pomares, H.; Salmeron, M.; Merelo, J.J.; IEEE Transactions on Systems, Man and Cybernetics, Part B, Volume: 32 , Issue: 5 , Oct. 2002 - Pages:686 – 691
Makale:
Genetik Algoritma Kullanarak Makale Yerleşimi Optimizasyonu C#, Visual C# ve .NET Yaşar Gözüdeli
  • Yazılan Yorumlar
  • Yorum Yaz
NİS
8
2012
Merhabalar. benimde bu konu üzerinde ufak tefek çalışmalarım var, siz uyguluma projenizi geliştirrken c# programını mı kullandınız?
Sayfalar : 1 
Yorum yazabilmek için üye girişi yapmalısınız. Üye girişi için tıklayın.
Üye değilseniz Üyel Ol linkine tıklayarak üyeliğinizi hemen başlatabilirisniz.
 
  • Bu Konuda Son 10
  • Eklenen Son 10
  • Bu Konuda Geçmiş 10
Bu Konuda Yazılmış Yazılmış 10 Makale Yükleniyor
Son Eklenen 10 Makale Yükleniyor
Bu Konuda Yazılmış Geçmiş Makaleler Yükleniyor