A
B
C
Ç
D
E
F
G
Ğ
H
I
İ
J
K
L
M
N
O
P
R
S
Ş
T
U
Ü
V
Y
Z
Q
W
X
+ İçerik Ekle
Genetik, Algoritma, Network, , Optimazasyon,
Genetik Algoritma,Network Ağ Optimazasyon

Genetik Algoritma,Network Ağ Optimazasyon

GENETİK ALGORİTMA ve BİLGİSAYAR AĞ
    YAPILARINDA OPTİMİZASYON

Bu çalışmada, bir bilgisayar ağı kurulacağı zaman, bilgisayar ağları arasında paketlerin yönlendirilmesini sağlayan yönlendiricilerin optimum de ağda yerleştirilmesi amacıyla farklı bir yöntem olarak Genetik
Algoritma önerilmiştir.

    Günümüzde gelişen teknolojilerin başında bilgisayar ağ yapıları gelmektedir. Aralarında bağlantı olan bağımsız
bilgisayar topluluğuna bilgisayar ağı denir. Bilgisayarların bağlantılı olmaları, aralarında bilgi alışverişi
yapabildikleri anlamına gelir. Bilgisayarlar arasındaki bağlantı, bir çift bakır tel üzerinden olabileceği gibi,
fiber
optik bağlantılar, radyo link sistemleri, haberleşme uyduları ya da kısa mesafeler için kızıl ötesi iletişim
sistemleri üzerinden de sağlanabilir [1, 2, 3].
Bu çalışmada, Genetik Algoritma kullanılmış olup, algoritmaya bir bilgisayar ağında bulunan düğümler ve bu



düğümlere ait maliyet değerleri bir matris şeklinde girdi olarak verilmektedir. Her bir düğümün birbirlerine
uzaklıkları rastgele girilip, GA yöntemi ile bir düğümden başlanıp tüm düğümlerden geçip, bir düğümde
sonuçlandığı tüm olası durumlar hesaplanmış olup, en kısa mesafe yani en optimum maliyet değeri buldurulmuştur.

    Genetik algoritmalar yapay zekanın gittikçe genişleyen bir kolu olan evrimsel hesaplama tekniğinin bir parçasını oluşturmaktadır. Adından da anlaşıldığı üzere, evrimsel hesaplama tekniğinin bir parçası olan genetik algoritma Darwin’in evrim teorisinden esinlenerek oluşturulmuştur. Herhangi bir problemin genetik algoritma ile çözümü,problemi sanal olarak evrimden geçirmek suretiyle yapılmaktadır.
Genetik algoritma geleneksel yöntemlerle çözümü zor veya imkânsız olan problemlerin çözümünde kullanılmaktadır [4, 5, 6]. Çok genel anlamda genetik algoritmanın üç uygulama alanı bulunmaktadır. Bunlar
deneysel çalışmalarda optimizasyon, pratik endüstriyel uygulamalar ve sınıflandırma sistemleridir.Genetik Algoritma Tekniğinde, ilk olarak populasyon diye tabir edilen bir çözüm(kromozomlarla ifade edilir)
seti ile başlatılır. Bir populasyondan alınan sonuçlar bir öncekinden daha iyi olacağı beklenen yeni bir populasyon oluşturmak için kullanılır. Yeni populasyon oluşturulması için seçilen çözümler uyumluluklarına
göre seçilir. Çünkü uyumlu olanların daha iyi sonuçlar üretmesi olasıdır. Bu istenen çözüm sağlanıncaya kadar devam ettirilir. Genetik algoritma aşamaları:

1.Başlangıç: n adet kromozom içeren populasyonun oluşturulması (problemin uygun bir çözümü)
2. Uyumluluk: her x kromozomu için uyumluluğun f(x) değerlendirilmesi,
3. Yeni populasyon: Yeni populasyon oluşuncaya kadar aşağıdaki adımların tekrar edilmesi,
- Seçim: İki ebeveyn kromozomun uyumluluğuna göre seçimi (daha iyi uyum seçilme şansını artırır.),
-Çaprazlama: Yeni bir fert oluşturmak için ebeveynlerin bir çaprazlama olasılığına göre çaprazlanması. Eğer
çaprazlama yapılmazsa yeni fert anne veya babanın kopyası olacaktır.
- Mutasyon: Yeni ferdin mutasyon olasılığına göre kromozom içindeki konumu değiştirilir.
- Ekleme: Yeni bireyin yeni populasyona eklenmesi.
4. Değiştirme: Algoritmanın yeniden çalıştırılmasında oluşan yeni populasyonun kullanılması,
5. Test: Eğer sonuç tatmin ediyorsa algoritmanın sona erdirilmesi ve son populasyonun çözüm olarak sunulması.
6. Döngü: 2. adıma geri dönülmesi.

   Görüldüğü üzere genetik algoritmanın yapısı oldukça geneldir ve herhangi bir probleme uygulanabilir.Kromozomların tanımlanması genellikle ikili düzendeki sayılarla yapılır. Çaprazlama işlemi için kullanılan
bireyler iyi bireylerden seçilir.GA kullanılarak bir problem çözülecekse algoritmanın ne zaman sonlanacağına kullanıcı karar vermektedir.
GA’nın belli bir sonlanma kriteri yoktur. Sonucun yeterince iyi olması veya yakınsamanın sağlanması algoritmanın durması için kriter olarak kullanılabilir.Genetik algoritmanın en önemli kısımları çaprazlama ve mutasyon işlemleridir. Bu işlemler bir olasılık değeri ile ve genelde rasgele olarak uygulanır. Bu iyi sonuç alınabilmektedir.Bir kromozomun ikili sayılarla temsil edilmesi:

Kromozom 1 1101100100110110,
Kromozom2 1101111000011110

Kromozom temsil ettiği çözümle ilgili bilgi içermelidir. Her kromozom ikili (binary) bir diziden oluşur. Bu dizi içindeki bit adı verilen her bir sayı çözümün bir karakteristiğini temsil edebilir veya bir dizi bütünüyle bir sayıya işaret edebilir.

Kromozomu ikili düzendeki sayılar dizisiyle ifade etmek çok tercih edilen bir temsil şeklidir ancak bunun yerine tamsayı veya reel sayılar da kullanılabilir. İkili düzenin tercih edilmesinin sebebi basit olması ve bilgisayar tarafından daha kolay ve hızlı bir biçimde işlenebilmesidir.

Üreme işlemi belli bir seçme kriterine göre bireylerin seçilip yeni kuşağın oluşturulması işlemidir. Seçme kriterleri uyumluluğu esas alarak birbiriyle uyumlu olan bireyleri seçer. Daha sonra çaprazlama ve mutasyon
uygulanacak olan bireylerden daha uyumlu yeni bireylerin ortaya çıkması olasıdır. Bireylerin tamamı uyumluluğa göre seçilebilir veya bir kısmı rasgele seçilerek yeni kuşağa aktarılabilir.Kromozomların nasıl temsil edileceğine karar verildikten sonra çaprazlama yapılabilir. Çaprazlama ebeveynlerden bazı genleri alarak yeni bireyler oluşturma işlemidir.

Kromozom 1 11011 | 00100110110,
Birey 1 11011 | 11000011110,
Kromozom 2 11011 | 11000011110
Birey 2 11011 | 00100110110

Çaprazlama yapılacak konum rasgele seçilir. Oluşan yeni birey ebeveynlerin bazı özelliklerini almış ve bir bakıma ikisinin kopyası olmuştur. Çaprazlama işlemi başka yapılabilir. Mesela birden fazla çaprazlama noktası seçilebilir. Daha iyi performans almak amacıyla değişik çaprazlamalar kullanılabilir. Çaprazlama gerçekleştikten sonra mutasyon gerçekleştirilir. Mutasyon oluşan yeni çözümlerin önceki çözümü
kopyalamasını önlemek ve sonuca daha hızlı ulaşmak amacıyla yapılır. Mutasyon oluşan yeni bireyin bir bitini (eğer ikili düzende ifade edilmiş ise) rasgele değiştirir.

Orjinal Birey 1 1101111000011110,
Değişmiş Birey 1 1100111000011110,
Orjinal Birey 2 1101100100110110
Değişmiş Birey 2 1101101100110110

Üreme, çaprazlama ve mutasyon işlemleri sonrasında kuşakta bulunan en iyi uyumluluğa sahip birey sonraki kuşağa aktarılamayabilir. Bunu önlemek için bu işlemlerden sonra oluşan yeni kuşağa bir önceki kuşağın en iyi
bireyi, yeni kuşaktaki herhangi bir birey ile değiştirilir. Buna elitizm adı verilir.

GA tekniğinin çaprazlama olasılığı ve mutasyon olasılığı olmak üzere iki basit parametresi vardır. Çaprazlama olasılığı çaprazlamanın hangi sıklıkta yapılacağını belirtir. Eğer hiç çaprazlama yapılmaz ise (çaprazlama olasılığı %0) yeni bireyler eski bireylerin aynısı olur ama bğ  yeni kuşağın eskisiyle aynı olacağı anlamına gelmez. Eğer bu oran %100 olursa yeni bireyler tamamıyla çaprazlama ile elde edilir. Çaprazlama eski bireylerden iyi taraflar alınarak elde edilen yeni bireylerin daha iyi olması umuduyla yapılır. Mutasyon olasılığı ise mutasyonun hangi sıklıkta yapılacağını belirtir. Mutasyon olmaz ise yeni birey çaprazlama veya kopyalama sonrasında olduğu gibi kalır. Eğer mutasyon olur ise yeni bireyin bir kısmı
değiştirilmiş olur. Eğer bu oran %100 olursa kuşak içindeki bireyler tamamen değişir, %0 olursa hiç değişmeden GA tekniği başka parametreler de içerir. Bunların en önemlilerinden birisi de populasyon büyüklüğüdür. Bu parametre populasyon içinde (yalnızca bir kuşakta) kaç adet kromozom yani birey olduğunu söyler. Eğer kromozom sayısı az olursa GA çözüm aranan uzayın ancak bir kısmını gezebilir ve çaprazlama için fazla bir seçeneği yoktur. Kromozom sayısı çok fazla olursa GA çok yavaş çalışır. Araştırmalar belli bir noktadan sonra populasyon sayısını artırmanın bir yararı olmadığını göstermiştir.

Yeni bireyler uyumluluğa göre veya rasgele olarak seçilebilir. Yeni bireylerin tamamen rasgele seçilme durumunda yakınsama zorlaşabilir. Tüm bireyler uyumluluğa göre seçildiğinde ise yeni kuşak içinde bölgesel
yakınsamalar olabilir. Bu sorunların üstesinden gelmek için belli bir oranda uyumluluk seçimi belli bir oranda da rasgele seçim yapılabilir. Bu oran Kuşak Farkı ile ifade edilir. Kuşak farkı %100 olduğunda yeni bireylerin
tamamı uyumluluğa göre seçilir. Ebeveynleri oluşturmak üzere bazı bireylerin seçilmesi gerekir. Teoriye göre iyi olan bireyler yaşamını
sürdürmeli ve bu bireylerden yeni bireyler oluşmalıdır. Bu seçim çeşitli kriterlere göre yapılabilir. Rulet seçimi, Boltzman seçimi, turnuva seçimi, sıralı seçim bunlardan bazılarıdır.

BULGULAR
Genetik algoritma yöntemiyle 10 düğümlü ve 20 düğümlü bilgisayar ağları için optimum sonuçlar elde edilmiş olup aşağıdaki gösterilmiştir.
n=10 içinGA simülasyon parametreleri
Simülasyon parametreleri
Popülasyon büyüklüğü40
Düğüm sayısı10
Iterasyon sayısı300
Mutasyon oranı0,3
GA matlab uygulaması simülasyon sonuçları.

İterasyon sayısı
1. 7. 17. 20 .182
Toplam maliyet
.50 .42 .38 .34. 33
182. iterasyonda bulunan en optimum yol.
En iyi yol
684132710 59
. İterasyon sayısına göre toplam maliyet değişimi.
n=20 için
. GA simülasyon parametreleri.
Simülasyon parametreleri
Popülasyon genişliği50
Düğüm sayısı20
Iterasyon sayısı20000
Mutasyon oranı0.4
Rastgele girilen uzaklık değerleri matrisi,
259

Olur

    Bu çalışmada, Genetik Algoritma kullanılmış olup, algoritmaya bir bilgisayar ağında bulunan düğümler ve bu düğümlere ait maliyet değerleri bir matris şeklinde girdi olarak verilmiştir. Her bir düğümün birbirlerine uzaklıkları rastgele girilip, GA yöntemi ile bir düğümden başlanıp tüm üğümlerden geçip, bir düğümde sonuçlandığı tüm olası durumlar esaplanmış olup, en kısa mesafe yani en optimum maliyet değeri buldurulmuştur. Genetik Algoritma Matlab ortamında yazılmış olup, yüksek düğümler için daha iyi sonuçlar verdiği görülmüştür.