Sezgisel En İyileme Yöntemleri

 

Resim2Optimizasyonun Tarihçesi

Bir işin en iyi yolun seçilerek başarılması fikri uygarlık tarihi kadar eskidir. Örneğin, Yunan tarihçisi Herodotus‘a göre, Mısırlılar Nil nehrinin her yıl taşması sonucu arazi sınırlarının yeniden belirlenmesi ve yeni sınırlara göre vergilendirme işleminin en iyi yolla yapılabilmesi için çaba sarfetmişlerdir.

Bu çabalar, ölçme ve karar verme aracı olarak düzlem geometrisinin temel kavramlarının oluşturulmasına yol açmıştır.  Mısırlılar, Nil nehrinin bahar dönemlerindeki yıllık taşmalarında nehir kıyısından toplu halde uzaklaşıp sular çekildiğinde yine büyük topluluklar halinde geri dönüyorlardı. Çekilme işlemi çok kısa sürede yapılamamaktaydı. Bunun için günlerce önceden halk uyarılmalıydı. Bu amaçla, Mısırlılar en iyi çekilme zamanını hesaplayabilmek için bir tür takvim bile geliştirmişlerdi. Söz konusu takvimi de sayma ve geometri konusundaki birikimlerini kullanarak yapmışlardı.

 

Resim3Newton ve Leibniz

Newton ve Leibniz tarafından Kalkülüs’ün (Calculus) 17. yüzyılda geliştirilmesi optimizasyon teorisinin gelişiminde önemli bir kilometre taşı olmuştur.

Kalkülüs

Kalkülüs, hem matematiksel bir fonksiyonun hem de fonksiyon oluşturabilen bağımsız değişkenlerin maksimum veya minimum cinsinden optimal koşullarının elde edilmesine olanak sağlamaktadır.

kalkulus

 

Gelişmeler

  • J.L. Lagrange’ın 1788 yılında Lagrange çarpanları yöntemini bulması
  • 1942’de İngiltere ve Amerika Birleşik Devletleri’nin Yöneylem Araştırması gruplarını oluşturması optimizasyon dünyası için bir dönüm noktası olmuştur
  • Yapay sinir ağları 1943’de W. McCulloch ve W. Pitts tarafından çalışıldı. Ertesi yıl ise, J. Von Neumann ve O. Morgenstern tarafından “Oyun Teorisi ve Ekonomik Davranış” adlı eserle oyun kuramı tanıtıldı.
  • Lineer programların çözümü için Simplex yöntem 1947’de G.B. Dantzig tarafından geliştirildi.
  • R. Bellman 1950’de dinamik programlama modelini ve çözümünü geliştirdi.
  • 1951’de H. Kuhn ve A. Tucker daha önce Karush’un önerdiği kısıtlandırılmış problemler için optimallik koşullarını tekrar formüle ederek doğrusal olmayan programlama modelleri üzerinde çalıştılar.
  • J. Von Neumann, G. Dantzig ve A. Tucker primal-dual lineer programlama modellerini geliştirdiler.
  • Yine önemli bir katkı 1955’de stokastik programlama adı altında G. B. Dantzig tarafından yapıldı.
  • Kuadratik programlama 1956’da M. Frank ve P. Wolfe tarafından geliştirildi.
  • 1958’deki önemli bir katkı R. Gomory tarafından tamsayılı programlama olarak adlandırıldı.
  • A. Charnes ve W. Cooper şans kısıtlı programlama modellerini 1959’da optimizasyon dünyasına armağan ettiler.
  • 1960’da sezgisel optimizasyon araçlarından birisi olan yapay zeka ve yöneylem araştırması ilişkilerini içeren çalışmalar yapıldı.
  • L. Khachian lineer programlama modellerinin çözümü için farklı bir algoritma olan elips yöntemini 1979’da geliştirildi.
  • 1984’te, N. Karmarkar lineer programlama için alternatif bir çözüm algoritması olan iç nokta algoritmasını geliştirdi.
  • 1992’de J.H. Holland tarafından bir sezgisel optimizasyon tekniği olarak kabul edilen genetik algoritma geliştirildi.

 

Optimizasyon Alanına Katkı Sağlayan Önemli Matematikçiler

  • John von Neumann
  • Leonid Vitalyevich Kantorovich
  • Naum Z. Shor
  • Leonid Khachian
  • Boris Polyak
  • Yurii Nesterov
  • Arkadii Nemirovskii
  • Michael J. Todd
  • Richard Bellman
  • Hoang Tuy

 

Eniyileme (Optimizasyon)

DDD

Optimizasyon (eniyileme) kavramı, “bir probleme en iyi ve mümkün olan  çözüm bulma süreci olarak” tanımlanmaktadır. Matematikte, bu süreç genellikle bir fonksiyonun değerinin verilen kısıtlar altında maksimize ya da minimize edilmesinden oluşur.

Bilgisayar bilimlerinde, sezgisel ya da buluşsal  bir problemi çözme tekniğidir. Sonucun doğruluğunun kanıtlanabilir olup olmadığını önemsememektedir fakat genelde iyiye yakın çözüm yolları elde eder. Sezgisel algoritmalar ise geçiş süresinde daha verimli hale gelebilmek için en iyi çözümü aramaktan vazgeçerek çözüm zamanını azaltan algoritmalardır. Sezgisel, diğer bir anlamıyla; bir düğümden başka bir düğüme olan en kısa yolun maliyetini hesaplayan fonksiyonlar olarak bilinir.

Sezgisel Eniyileme Yöntemleri

  • Tavlama benzetimi
  • Genetik algoritmalar
  • Karınca kolonisi
  • Parçacık sürü optimizasyonu
  • Çok yönlü ve hibrit metotları
  • Evrimsel algoritmalarda kısıt ele alma teknikleri

    1.Tavlama Benzetimi Algoritması

Kirkpatrick ve arkadaşları tarafından 1983 yılında önerilmiştir. Optimizasyon problemleri için iyi çözümler veren olasılıklı bir arama tekniğidir. Katıların ısıtılması ve sonra kristalleşmeye kadar yavaş yavaş soğutulması esasına dayanır.

TAVLMA

Sıcaklık değeri elde edilen en iyi çözümden daha kötü bir çözümün kabul edilme olasılığını belirlemek için kullanılır. Tavlama benzetimi yüksek bir sıcaklık değeriyle başlar. Her bir hesaplama adımında mevcut çözümün Tavlama Benzetimi her bir hesaplama adımında mevcut çözümün komşuları arasından çok sayıda çözüm üretilir. Yeni çözümler belirlenen kriterlere göre kabul edilir veya reddedilir. Her bir hesaplama adımından sonra sıcaklık belirlenen bir fonksiyona göre azaltılır. Algoritma istenen iterasyona ulaşıldığında ya da sıcaklık minimum değerine ulaştığında veya istenen çözüme ulaşıldığında sonlandırılır.

 

TAVALGRTMA

TAVLAMA BENZETİMİ AKIŞ ŞEMASI

2.Genetik Algoritma

 

  • İlk olarak 1970’li yıllarda, olarak, John Holland ve arkadaşlarının yaptığı çalışmalarda ortaya çıkmıştır.
  • Darwin’ in doğal seçilim ve evrim teorisi ilkelerine dayanan bir arama ve optimizasyon yöntemidir.
  • Ön bilgi ve varsayımlar olmadan, sadece uygunluk fonksiyonu ile çalışabilmektedir.

Biyolojik Altyapısı

  • Gen:  Kalıtsal molekülde bulunan ve organizmanın karakterlerinin tayininde rol oynayan kalıtsal birimlere denir.
  • Kromozom (Birey):  Birden fazla genin bir araya gelerek oluşturduğu diziye denir.
  • Popülasyon:  Kromozomlardan oluşan topluluğa denir. Popülasyondaki kromozom sayısı arttıkça çözüme ulaşma süresi (iterasyon sayısı) azalır.

B1

B2

B3

 

 

 

 

 

Kullanılan Operatörler

  • Uygunluk fonksiyonu (fitness) : Toplumdaki her kromozomun ne kadar iyi olduğu bulmayı amaçlayan fonksiyondur. Bu fonksiyon GA nın beynini oluşturmaktadır.
  • Yeniden kopyalama (recombination) : Yeni çözümler üretmek için çaprazlama (crossover) işlemi yapılır ve bu eşleme uygunluk fonksiyonuna göre yapılır.
  • Değiştirme (mutation) : Sadece bir çözüm üzerinde yapılan işlemdir.

Kromozomun şifrelenmesi

1.İkili kodlama

Bu yöntem ilk GA uygulamalarında kullanıldığı için hala en çok kullanılan yöntemdir. Her kromozom, 0 ve 1 lerden oluşan bit dizisidir ve ikili diziyle ifade edilir. Bu dizideki her bit, çözümün bir özelliğini taşır. Dizinin tümü ise bir sayıya karşılık gelir. Örneğin ,Kromozom A: 101110010110  ,Kromozom 2:  010110100000

 

2. Permütasyon kodlama

Bu kodlama Gezgin Satıcı Problemi ve iş sıralama problemleri gibi sıralama problemlerinde kullanılır. Burada her kromozom bir numaralar dizisidir. Örneğin , Kromozom A: 35127604 ve Kromozom B: 01562347

2.1. Gen takası (Çaprazlama) ve Mutasyon

2.1.a Tek noktalı gen takası

  • Kromozom-1  : 11011|00100110110
  • Kromozom-2  : 11011|11000011110
  • Çocuk-1        :  1101111000011110
  • Çocuk-2        :  1101100100110110

2.1.b  Çift noktalı gen takası

  • Kromozom-1  : 11011|00100|110110
  • Kromozom-2  : 11011|11000|011110
  • Çocuk-1         : 1101111000110110
  • Çocuk-2         : 1101100100011110

2.1.c  Tek biçimli (uniform) gen takası

  • Kromozom-1    : 11011001
  • Kromozom-2    : 00011110
  • Çocuk-1           : 10011010
  • Çocuk-2           : 01011101

 

Çaprazlama

  • Kromozom-1  : 123456789
  • Kromozom-2  : 453689721
  • Çocuk-1         : 123489721
  • Çocuk-2         : 453656789

 

Mutasyon işlemi

Mutasyon işlemi, problemin problemin populasyondaki çözümlerin yerel optimuma düşmesini engellemek için kullanılır. Mutasyon yeni üretilen çocuk kromozomu rastgele değiştirir.

  • Çocuk-1(orijinal)   : 11011001
  • Çocuk-2                : 11111001

Gen mutasyonu:

  • Çocuk-1(orijinal)  : 123456789
  • Çocuk-2               : 183456289

 

Kromozom Seçimi

1. Rulet tekeri seçimi

Bu yöntemde seçilme işlemi bireylerin (kromozomların) uygunluk değerine göre yapılmaktadır. Fakat uygunluk değeri en büyük olanın seçileceği garanti edilmez, yalnız seçilme şansı daha fazla olacaktır.

Bu yöntemde bütün uygunluk değerleri bir tabloya yazılır ve toplanır. Uygunluk değeri toplama bölünerek bireylerin [0,1] aralığında seçilme olasılıkları belirlenir. Rulet tekerleği seçimi çözümlerin uygunluk değerlerinin pozitif olması gerekir.

rulet

RULET TEKERİ

 

2. Sıralama seçimi

 

Rulet tekeri seçimi, uygunluklar çok farklıysa problemlere yol açar. (Örneğin, en iyi kromozomun uygunluğu %90 ise diğer kromozomlar çok az seçilme şansına sahip olacaktır.)

Sıralama seçimi önce populasyonu sıralamakta ve ardından her kromozomun bu sıralamada uygunluğu aranmaktadır. En kötüsü 1 uygunlukta, ikinci kötüsü 2 uygunlukta vb. en iyisi ise N uygunlukta olacaktır.

Böylelikle bütün kromozomlara seçilme şansı verilir. Fakat bu yöntemde en iyi kromozomlar, diğerlerinden daha farklı olmadığından çözüme yaklaşma yavaş olacaktır

 

3.Sabit durum seçimi

Bu yönteme göre ebeveynlerin seçimi için kromozomların büyük parçaları bir sonraki jenerasyona taşınmaktadır.  Her nesilde yeni bir birey (çocuk) oluşturmak için birkaç kromozom seçilir (büyük uygunlukta iyi olanlar). Az uygunlukta kötü olan kromozomlar atılır ve yeni çocuk kromozomlar yerine getirilir. Geri kalan kromozomlar değiştirilmeden yeni nesle aktarılır.

Genetik Algoritmaların Çalışma Prensibi

Adım 1: Olası çözümlerin kodlandığı bir çözüm grubu oluşturulur (çözüm grubu (population), çözümlerin kodları (string) da kromozom olarak adlandırılır).

Adım 2: Her kromozomun ne kadar iyi olduğu bulunur (fitness function).

Adım 3: Bu kromozomlar eşlenerek (mating), yeniden kopyalama (recombination) ve değiştirme (crossover) operatörleri uygulanır. Bu sayede yeni bir toplum oluşturulur.

Adım 4: Yeni kromozomlara yer açmak için eski kromozomlar ortadan kaldırılır.

Adım 5: Tüm kromozomların uygunlukları tekrar hesaplanır.

Adım 6: İşlemler tekrarlanarak verilmiş zaman içerisinde daha iyi olan yeni nesillerin oluşturulması gerçekleştirilir (3. adıma gidilir).

Adım 7: O ana kadar hesaplanma sırasında en iyi kromozom bulunduğunda istenen  sonuç elde edilmiş olur.

ttttt

GENETİK ALGORİTMA AKIŞ ŞEMASI

Örnek: Fonksiyon Maksimizasyonu

Problem  : f(x)=x²  ve   -1<x<32  olmak üzere  bir fonksiyonun

Amaç  : Verilen aralıkta fonksiyonun maksimizasyonu genetik algoritma ile gerçekleyiniz.

Adım 1: x’in , 0 ve 1’lerden oluşan 2 tabanındaki gösterilimi yapılmaktadır

  • 0   : “00000”
  • 31 : “11111” olacaktır.

´

Adım 2:  Toplumun birey sayısı n:4 olarak seçilmiştir. Toplumu oluşturan dört birey, her biri 5 bit uzunluğunda birer kromozomla temsil edildiği için toplam 20 kere yazı tura atmak suretiyle belirlenmiştir.

  • Birey 1: 01101,   x = 13 ,    x² = 169
  • Birey 2: 11000,   x = 24 ,    x² = 576
  • Birey 3: 01000,   x = 8 ,      x² = 64
  • Birey 4: 10011,   x = 19 ,    x² = 361

 

Adım 3: Belirlenen bireyler için f(x)=x² ile uygunluk değerleri hesaplanır. Dört bireyin toplam uygunluk değerleri;

169 + 576 + 64 + 361 = 1170

Her bir bireyin rulet tekerleğinde kaplayacağı alan;fffff

  • Birey 1:  169 / 1170 = 0.14   : %14
  • Birey 2:  576 / 1170 = 0.49   : %49
  • Birey 3:  64 / 1170 = 0.06     : %6
  • Birey 4:  361 / 1170 = 0.31   : %31

Bu değerler, rulet tekerleğinin her çevrilişinde hangi olasılıkla hangi bireyin seçileceğini belirtir.

Adım 4:  Toplumda ki birey sayısının sabit kaldığı varsayıldığından, rulet tekerleği 4 kere çevrilerek çiftleşme havuzu oluşturulur.

  • Birey 1 : 1 kere
  • Birey 2 : 2 kere
  • Birey 3 : 0 kere
  • Birey 4 : 1 kere

Elde edilen çiftleşme havuzu şu şekildedir;

  • Aday 1 : 01101 (Birey 1)
  • Aday 2 : 11000 (Birey 2)
  • Aday 3 : 11000 (Birey 2)
  • Aday 4 : 10011 (Birey 4)

Adım 5:  Çiftleşme havuzu belirlendikten sonra iki aşamalı çaprazlama uygulanır.

İlk aşamada adaylar  çiftleşmek üzere rasgele olarak eşlenirler. Rasgele eşleştirme sonucunda ( Aday 1, Aday 2) ve (Aday 3, Aday 4) ikili grupları oluşturulur.

İkinci aşamada her ikili grup için birer kere zar atılarak çaprazlaşmanın oluşacağı nokta belirlenir. Zar atılarak 1. Grup için k=4 ve 2. Grup içinde k=2 olarak belirlenmiştir.

Çiftleşme grubu 1: (k=4)

  • Aday 1 : 0110/1  oluşan  Birey 1 : 01100
  • Aday 2 : 1100/0  oluşan  Birey 2 : 11001

Çiftleşme grubu 2 : (k=2)

  • Aday 3 : 11/000   oluşan  Birey 3 : 11011
  • Aday 4 : 10/011   oluşan  Birey 4 : 10000

 

Adım 6: Son aşama olan mutasyon işlemi bitler düzeyinde uygulanır.

Birey 3’ün 2 numaralı bitinde mutasyon işlemi yapılmaktadır.

Oluşan Birey 3 : 11011

Mutasyon sonucu oluşan Birey 3 : 10011

Bu adımın tamamlanmasıyla bir sonraki kuşağı oluşturacak toplumun bireyleri belirlenmiş olur. Yeni toplum şu şekildedir;

  • Birey 1 : 01100,   x=12,   x²=144
  • Birey 2 : 11001,   x=25,   x²=625
  • Birey 3 : 10011,   x=19,   x²=361
  • Birey 4 : 10000,   x=16,   x²=256

 

Bu örnekte tek bir iterasyon yapılmış ve başlangıç toplumundan bir sonraki kuşak oluşturulmuştur ancak genetik algoritmanın çalışmasının tam olarak gözlenebilmesi için tek bir iterasyon yeterli değildir.

 

3.Karınca Kolonisi Optimizasyonukkkkkk

Karınca algoritmaları ilk olarak Dorigo ve meslektaşları tarafından, gezgin satıcı problemi (GSP) ve kuadratik atama (QAP) gibi zor optimizasyon problemlerinin çözümü için geliştirilmiştir

Karıncalar, yiyecek kaynaklarından yuvalarına en kısa yolu görme duyularını kullanmadan bulma yeteneğine sahiptirler.

Dış etkenler sonucu takip ettikleri mevcut yol artık en kısa yol değilse, yeni en kısa yolu bulabilmektedirler. Önlerine bir engel konulduğunda feromonları takip edemediklerinden, karıncalar gidebilecekleri iki yoldan birini öncelikle rastsal olarak seçmektedirler.Kısa olan yoldan birim zamandaki geçiş daha fazla olacağından bırakılan feromon miktarı da daha fazla olur. Buna bağlı olarak, zaman içerisinde kısa olan yolu tercih eden karıncaların sayısında artış olur. Belli bir süre sonra tüm karıncalar kısa yolu tercih ederler.

Başta rastsal hareket eden karıncaların izleri kontrol ederek yüksek olasılılıkla izlerin yoğun olduğu yönü takip etmesi otokatalitik bir davranış şeklidir ve karıncaların karşılıklı etkileşiminde sinerjik bir etki vardır.

Algoritma, karınca kolonilerinden esinlenerek geliştirildiğinden sisteme, karınca sistemi (KS), algoritma ise karınca kolonileri algoritması (KKA) olarak adlandırılır.
ggggg

Karınca kolonisi algoritmasına ait döngü

  1. Başlangıç feromon değerleri belirlenir
  2. Karıncalar her düğüme rastsal olarak yerleştirilir
  3. Her karınca,sonraki şehri denklemde  rastsal denklemde verilen lokal arama olasılığına bağlı olarak seçmek suretiyle turunu tamamlar
  4. Her karıncanın katettiği yol hesaplanır,lokal feromon miktarı güncellenir
  5. En iyi yol çözüm olarak seçilir,feromon yenilemesinde kullanılır
  6. Maksimum iterasyon sağlanan kadar 2. adıma gidilir

 

4.Parçacık Sürü Optimizasyonu

optimizasyon1-326x435

PSO AKIŞ ŞEMASI

1995 yılında Dr.Eberhart ve Dr.Kennedy tarafından geliştirilmiş popülasyon temelli sezgisel bir optimizasyon tekniğidir. Kuş veya balık sürülerinin sosyal davranışlarından esinlenerek geliştirilmiştir. Birbirleriyle ve çevresiyle etkileşim içerisinde olan bireylerin davranışları incelenerek geliştirilmiştir. Bu kavram parçacık zekası olarak da isimlendirilmektedir.

PSO’da parçacık olarak isimlendirilen potansiyel çözümler, mevcut en iyi çözümleri takip ederek problem uzayında gezinirler.

Belirli bir alanda, sadece bir bölgede yiyecek olduğu, bir kuş grubunun bu alanda yiyecek aradığı ve başlangıçta yiyeceğin nerede olduğunu bilmediği kabul edilir ise, yiyecek bulmak için en iyi çözüm ne olabilir?

PSO rastgele üretilmiş belirli sayıda çözümle (parçacıkla) başlatılır ve parçacıklar güncellenerek en uygun çözüm değeri araştırılır.

Parçacıkların her biri, parçacığın en iyi kendi çözümü (pbest) ve tüm parçacıkların en iyi çözümü (gbest) kullanılarak güncellenir. Bu değerler hafızada saklanır.

Kullanım alanları

Klasik algoritmalardaki gibi ilgilenilen problem üzerinde değişiklik gerektirmemesi vb. avantajlarından dolayı sezgisel algoritmalar;

  • Yönetim Bilimleri
  • Mühendislik
  • Tıp ve Genetik
  • İktisat ve İstatistik
  • Planlamacılık    gibi bir çok alanda kullanılmaktadır.

SONUÇ

Optimizasyon bilim ve teknoloji çağı olan 21.yy’da birçok disiplin ve çalışma alanında kullanılmaktadır. Gerçek dünyayı yazılım dünyasına taşımaya ve  çok kolay çözümler üretilmesine öncülük etmiştir. Rastsal değişkenlere bağlı fonksiyonların kullanılmaya başlanması ile gerçek yaşam modellenmesi kolaylaşmıştır.

Kalıtım çalışmaları gibi çok boyutlu çalışmaların sonuçlanmasında hızlı ve kolay bir yöntem sunarak bilime ne kadar katkı sağladığı anlaşılabilir.

Bu yazı hakkında ne düşünüyorsun ?
  • Faydalı 
  • Gereksiz 
  • Müthiş 
  • Normal 
The following two tabs change content below.
Musa YILDIRIM
1993 yılında Adana’da doğdu. 2011 yılında Sivas Fen Lisesi’nden mezun oldu. Pamukkale Üniversitesi Elektrik ve Elektronik Mühendisiği’nden mezun oldu. İlgi alanları otomasyon ve mikrodenetleyicilerdir. Arzunun varolduğu yerde çözümün de var olacağına inanmaktadır.
Musa YILDIRIM

Latest posts by Musa YILDIRIM (see all)