İlginizi Çekebilir
  1. Ana Sayfa
  2. Algoritmalar
  3. Metasezgisel Algoritmalar

Metasezgisel Algoritmalar

pso
DMC Teknoloji

Gerçek dünya problemlerinin bilgisayar bilimi aracılığıyla çözülmesi ile ilgili pek çok algoritma geliştirilmiştir. Bu algoritmalardan kimisi bilgisayar bilimcileri tarafından öne sürüldüyse de farklı bilim dallarından da literatürde öne sürülen algoritmalar mevcuttur. Ancak bilgisayar bilimleri sayesinde bu algoritmalar bilgisayarın ve bilgisayar hesaplamasının gücüyle pek çok gerçek dünya problemini çözmeye başlamış ve halen de mevcut algoritmalar üzerinde iyileştirmeler ve akademik dünyada yeni yaklaşım önerileri devam etmektedir.

Ülkemizde matematik ve bilgisayar mühendisliği gibi bölümlerde genellikle lisansüstü eğitimde karşılaşılan bu problem çözme tekniğine sezgisel, metasezgisel veya buluşsal (heuristic) problem çözme yaklaşımı denilmektedir. Bu yaklaşımda sonucun doğruluğundan ziyade en iyiye yakın çözüm yollarının elde edilmesi ve yakın çözümlerin bulunması hedeflenir. Bu yüzden kimi algoritmların iyi ve zayıf yönleri vardır. Örneğin local minimuma takılı kalıp en iyi değeri bulamadan kendisini tamamlayan Hill Climbing algoritmasını bu yönüyle zayıf olarak nitelendirirken hızıyla da aavantajından bahsedebiliriz.  Sezgisel algoritmaların bu özelliği sayesinde en iyi çözümü aramak yerine çözüm zamanını optimize eden algoritmalar olduklarından söz edebiliriz. Buradan hareketle de sezgisel algoritmaların en iyi çözüme en yakın çözüm yolunu hızlı ve kolay bir şekilde bulabilmek ile ilgili çalıştıklarını ve çeşitleri olduğunu söyleyebiliriz.

Bu algoritmalar optimum sonuca ulaşamadığımız veya çok zaman harcadığımız problemlerde kullanıldığından yapay zeka, makine öğrenmesi, yapay sinir ağlarını eğitmede ve elbette optimizasyon çalışmada oldukça büyük bir yere sahiptir.

Klasik Arama Algoritmalarına Bir Bakış

Doğrusal programlama modellerinde geliştirilen algoritmalar sürekli bir karar değişkenine sahiptirler ve çözüme hızlıca ulaşabilmektedirler. Burada dikkat edilmesi gereken problemin en iyi noktasının zaten kesişim noktalarından birinde bulunuyor olmasıdır ve çözüm yalnızca bu noktalarla ilgilendiğinden hızlıca çözüme ulaşılabilmektedir. Ancak gerçek dünya problemi diye nitelendirdiğimiz problemlerde sonuca böyle kolayca ulaşamayabiliriz. Gerçek dünya problemlerini çözebilmek için öncelikle bir amaç fonksiyonumuz olmalıdır. Bu amaç fonksiyonu her zaman doğrusal bir fonksiyon olmak zorunda da değildir. Amaç fonksiyonlarımızda karar değişkenlerimiz tamsayı olabilmektedir. Rastsallıktan bahsettiğimiz biz uzay içerisinde çalıştığımız için bir değişken ile amaç fonksiyonumuz arasında negatif veya pozitiflik durumu için de bulunduğumuz nokta cevap verecektir.

Algoritmada problemi çözmek için kurduğumuz yapının en iyi çözümü bulabilmesi için tüm değişkenlerin tek tek denendiği yöntemler tercih edilmektedir. Ancak bu işlemi bilgisayara çözdürüyor olsak dahi best practise bir iş yapmamış olacağımızdan deneme yanılma ile en iyi sonucu bulma işini profesyonel hale getirmemiz gerekiyor. Süreyi optimize edebilmek ve deneme işlemini gerçekleştirebilmek için zeki arama algoritmalarına başvuruyoruz.

Zeki arama algoritmalarını kullanırken problemimize de uygun olan mantıksal modifiyeleri yapabiliriz. Tıpkı işletim sistemlerinin işlemleri parça parça alıp değerlendirip tamamlaması mantığındaki gibi zeki arama algoritmaları da problemi çözebilmek için daha küçük alanlarda arama yaparak sonuca hızlı ulaşmayı hedeflemektedir. Parça parça arama işleminde problemi küçük parçalar olarak ele alır ve üzerinde çalıştığı parça içinde en iyi çözüme ulaştıysa bunu bir node olarak tutar ve diğer parçaya geçer böyle böyle işleme devam eder ve node’ları da kendi arasında kıyaslayıp en iyiyi bulur. Böylece tüm node’lara tek seferde bakmadığı için hızlıdır ve sonucu bulduğu ilk node’da çalışmayı durduracaktır.

Buraya kadar sezgisel algoritmalara ihtiyaç duymadan geleneksel zeki arama algoritmalarıyla sonuca ulaşıyor gibi görünsek de bu işlemlerin zafiyeti node sayısının fazla ve buradaki işlemlerin zahmetli olabileceği endişesinden ötürüdür. Yani böyle bir durumda bu zeki arama algoritmaları da aslında istediğimiz optimum hızda sonucu bize döndürmemiş olacaktır.

İşte tam olarak böyle bir senaryoda geleneksel zeki arama algoritmalarının yerine problemimizi gerçek dünya problemine dönüştürerek sezgisel algoritmalar üzerinde çalıştırarak daha optimum sonuçlar elde edebiliriz. Bu makalenin amacı literatürde yer alan GA, ABC, PSO gibi metasezgisel algoritmaların incelenmesi ve bu algoritmaların da zafiyetlerinin tespit edilerek ne tür değişiklikler yapılabileceği, literatürde ne gibi eklemeler ve mekanizma değişiklikleri yapılmış durumlarını incelemek üzere birinci bölümü oluşturmaktır.

Aşağıdaki sezgisel algoritmaları örnek olarak verebiliriz;

  • A Star Arama Algoritması
  • Demet Araması (Beam Search)
  • Tepe Tırmanma Algoritması (Hill Climbing)
  • En İyi Öncelikli Arama Algoritması (Best First Search)
  • Açgözlü Yaklaşımı Algoritması (Greedy Best First Search)
  • Benzetimli Tavlama Algoritması (Simulated Annealing)
  • Geri İzleme Algoritması (Backtracking)

Sezgisel Optimizasyon Nedir ? 

Sezgisel algoritmalar, büyük ölçekli optimizasyon problemlerinin çözümü için optimuma yakın sonuçlar döndüren algoritmalardır. Sezgisel optimizasyon algoritmaları, genetik, fizik, sürü, sosyal, müzik gibi farklı başlıklar altında incelenmektedir. Örneğin doğada arıların yiyecek bulma davranışlarını inceleyen ve bu hareketler ile gerçek dünya problemlerinin çözümü için uyarlanan Yapay Arı Kolonisi Algoritması veya kuşların doğada yiyecek bulabilmek için sürü olarak izledikleri hareketleri de gerçek dünya problemine uyarlayarak süreci optimize eden Parçacık Sürü Optimizasyon Algoritmaları geliştirilen algoritmalara birer örnektir.

Sezgisel, metasezgisel optimizasyon ile artık gerçek dünya problemlerinin çözümlendiğini öğrendiğimize göre bu optimizasyon yöntemlerinin neler olduklarına da göz atalım.

  • Genetik Algoritma (GA)
  • Karınca Kolonisi Optimizasyonu (Ant Colony Opt.) (ACO)
  • Parçacık Sürü Optimizasyonu (Particle Swarm Opt.) (PSO)
  • Yapay Arı Kolonisi Optimizasyonu (Artificial Bee Colony Opt.) (ABC)
  • Diferansiyel Gelişim Algoritması (Differential Evolution ) (DEA)
  • Benzetim Tavlama Algoritması (Simulated Annealing) (SA)
  • Yerçekimi Arama Algoritması (Gravity Search Algorithm) (GSA)
  • Gaz Brownian Hareketi Optimizasyonu (Gases Brownian Motion Opt.) (GBMO)
  • Isı Transferi ARama (Heat Transfer Search) (HTS)
  • Elektromanyetik Alan Optimizasyonu (Electromagnatic Field Opt.)(EFO)
  • Optikten Esinlenen Optimizasyon (Optic Inspired Optimization)(OIO)
  • Ağırlıklı Süperpozisyon Çekimi (Weighted Superposition Attraction (WSA)
  • Orman Optimizasyonu Algoritması (Forest Optimization Algorithm)(FOA)
  • Kasırga Temelli Optimizasyon Algoritması (Hurricane Based Optimization Algorithm)
  • Kara Delik Optimizasyon Algoritması
  • Su Döngüsü Optimizasyon Algoritması
  • Meyve Sineği Optimizasyon Algoritması
  • Krill Sürü Optimizasyon Algoritması
  • Bakteri Yiyecek Arama Davranışı
  • Yarasa Algoritması
  • Ateş Böceği Algoritması
  • Aslan Algoritması
  • Gri Kurt Algoritması
  • Yunus Balığı Algoritması
  • Çalı Kolonisi Algoritması
  • Yapay Alg Algoritması
  • Virüs Koloni Arama Algoritması
  • Köpekbalığı Koku Alma Optimizasyon Algoritması
  • Sosyal Örümcek Algoritması
  • Ağaç-Tohum Algoritması(Tree-Seed Algorithm)(TSA)

Sezgisel algoritmalara giriş yaptığımız ve problemin ne olduğundan bahsetmeye çalıştığımız bu bölümün sonuna geldik. Gelecek bölümde konuya biraz daha derinlemesine giriş yapacak ve sonraki bölümlerde ise yaygın algoritmalardan ABC, PSO ve GA algoritmalarını inceliyor olacağız.

 

Bu konuyla ilgili sorularınızı https://forum.mshowto.org linkini kullanarak ulaşacağınız forum sayfamızda sorabilirsiniz.

Referanslar

www.mshowto.org

wikipedia

TAGs: Sezgisel Algoritmalar,

 

 

DMC Teknoloji
Yorum Yap

Yazar Hakkında

Bilgisayar Mühendisliği Doktora programında öğrenciliğim devam etmektedir. Bir Vakıf üniversitesinde 2016 yılı itibariyle Bilgisayar Mühendisi 2020 yılı itibariyle ise Ofis Yöneticisi mühendis olarak çalışmaktayım.  Başlıca uzmanlık alanlarım arasında Asp.Net Web Forms, Asp.Net MVC, .Net Core, C# ve SQL Server gelmektedir. Bunların yanı sıra iş hayatımda sistem ve siber güvenlik konularında da çalışmalarım devam etmektedir. Çeşitli AB destek projelerinde yazılım sorumlusu olarak görev yapıyor ve çalışmalarımı Secure Design Pattern, Yazılım Güvenliği, Siber Güvenlik, Bilgi Güvenliği konularında sürdürüyorum. Asp.net ile Proje Geliştirme ve Bilgisayar Mühendisliğine Giriş isimli kitapların yazarıyım.

Yorum Yap