Download "Evrimsel Çok amaçlı eniyileme. Tahir Emre Kalaycı Ege Üniversitesi Bilgisayar Mühendisliği Bölümü 25 Mart 2010"
1 Evrimsel Çok amaçlı eniyileme Tahir Emre Kalaycı Ege Üniversitesi Bilgisayar Mühendisliği Bölümü 25 Mart 2010
2 Gündem Çok amaçlı eniyileme Giriş Evrimsel çok amaçlı eniyileme Sonuç
3 Giriş Gerçek dünya problemleri genellikle birden fazla amaçlıdır Bu amaçlar birbirleriyle çelişebilir Bazen bu birden fazla amacı tek amaca düşürebiliriz Ama her zaman bu amaçların hepsini tek amaç ile doğru bir şekilde temsil etmek zordur Birden fazla amaç belirlemek görevin gerçekleştirilmesi açısından daha iyidir.
4 Giriş Çok amaçlı eniyilemenin amacı kabul edilebilir çözümler bulmak ve bu çözümleri bir karar mekanizmasına sunmak Amaçları en iyi şekilde karşılamak hedefimizdir Basit bir örnek: En verimli ulaşım aracı Kriterlerimiz: aldığı yol, harcadığı enerji
5 Giriş Kaynak: 2005,Ngatchou
6 Kaynak: 2005, Abraham Giriş Pareto
7 Giriş Çok amaçlı eniyilemede kullanılabilecek yöntemler: Tek bir amaca indirgemek (Aggregate Objective Function) Normal Boundary Intersection (NBI) Normal Constraint (NC) Succesive Pareto Optimization (SPO) Multiobjective Optimization Evolutionary Algorithms (MOEA) Pareto surface generation for convex multiobjective instances (PGEN) Indirect Optimization on the basis of Self-Organization (IOSO) Bunlara ek olarak var olan stokastik eniyileme yöntemleri (tabu arama, benzetimli tavlama, karınca kolonisi eniyilemesi) pareto kümesini bulmak için kullanılabilir.
8 Evrimsel çok amaçlı eniyileme Bizim odağımız evrimsel algoritmalar olacak 1960'larda Rosenberg'in doktora tezi ilk ipuçlarını içeriyordu İlk gerçekleştirilen MOEA Schaffer'in Vector Evaluation GA (VEGA)dır MOEA'lar aşağıdaki tiplerdedir: Birleştirme fonksiyonları Toplum temelli yaklaşımlar Pareto temelli yaklaşımlar
9 Evrimsel çok amaçlı eniyileme Birleştirme fonksiyonlar bütün amaçları tek bir amaç olarak birleştiren fonksiyonlardır. Toplama, çıkarma, çarpma, vb. yöntemler kullanılabilir. En eski matematiksel programlama türüdür. Kuhn-Tucker'ın egemen olmayan çözümlerinden türetilebilir. (Tucker, 1951) Bir örnek ağırlıkların doğrusal toplamı olabilir:
10 Evrimsel çok amaçlı eniyileme Toplum temelli yaklaşımlarda aramayı çeşitlendirmek için toplum kullanılmaktadır Klasik örneği VEGA'dır (Schaffer,1985) VEGA değiştirilmiş seçime sahip bir GA'dır. Her nesilde her amaçla orantılı alt toplumlar oluşturulmaktadır k amacın olduğu bir problemde, M/k büyüklüğünde k adet alt toplum oluşmakta (M toplum büyüklüğü), bu alt toplumlar daha sonra karıştırılmakta ve GA işleçleri uygulanmaktadır. VEGA'nın en önemli problemi pareto egemenlik kavramına zıtlıklar içermesidir. Eksikliklerine rağmen günümüzde kullanılıyor çünkü seçim sürecinde eğilim yaratmak istenilen ve oldukça fazla sayıda amacı olan problemlere rahatça uygulanabiliyor.
11 Evrimsel çok amaçlı eniyileme Pareto temelli yaklaşımlar seçim şemasını pareto optimalliğine dayandıran yaklaşımlardır. İlk olarak Goldberg tarafından önerilmiştir (Goldberg, 1989) İki nesilden bahsedilebilir 1. Nesil: Uygunluk paylaşımını ve nişingi pareto sıralama ile kullananlar NSGA, NPGA, MOGA 2. Nesil: Elitizm ile ortaya çıkmıştır. SPEA, SPEA2, PAES,NSGA-II, PESA,microGA
12 Sonuç Uygulama Alanları: Mühendislik, Robotik, Tasarım ve üretim, zamanlama, yönetim, kimya, fizik, tıp, bilgisayar bilimleri,... şeklinde bir çok alanda uygulanmaktadır. Algoritmalar geliştirilmeye devam ediyor, üçüncü nesil algoritmaların ne tür algoritmalar olacağı merak konusu Algoritmanın başarımına yönelik ölçütler söz konusu Bir çok teorik açık soru mevcut Bir çok gelecek vadeden açık yol mevcut
13 Kaynakça Ngatchou P, Zarei A. Pareto Multi Objective Optimization. Methods. 2005: Abraham A, Jain L, Goldberg R. Evolutionary Multiobjective Optimization. London: Springer-Verlag; 2005:1 9. Lucas C. Practical Multiobjective Optimization. Learning Multiobjective optimization, Wikipedia EK KAYNAKÇA Kuhn, HW and Tucker, AW, Nonlinear programming. In Neyman, J (ed), Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability, pp , Berkeley, CA, University of California Press. Schaffer, JD, Multiple objective optimization with vector evaluated genetic algorithms. In Genetic Algorithms and their Applications: Proceedings of the First International Conference on Genetic Algorithms, pp , Hillsdale, NJ, Lawrence Erlbaum. Goldberg, DE, Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Publishing Company, Reading, MA, 1989.
DİNAMİK PROGRAMLAMA. Dr. Mehmet Hulusi DEMİR 1
DİNAMİK PROGRAMLAMA Dr. Mehmet Hulusi DEMİR 1 Konunun Tarihçesi Tekniğin büyük adımlarla ilerlemesi, üretim işletmelerini sürekli olarak geliştirmekte, böylelikle teşebbüsleri plânlamalarında yeni yolları
SPARQL Sorgu Eniyilemesi için Karınca Kolonisi Yöntemi
Akıllı Sistemlerde Yenilikler ve Uygulamaları Sempozyumu - 2012 SPARQL Sorgu Eniyilemesi için Karınca Kolonisi Yöntemi 4 Temmuz 2012 E. Güzel Kalaycı 1, T. E. Kalaycı 2 1. Bilgisayar Mühendisliği, İzmir
Dersin Adı Ayrık Eniyileme İTÜ LİSANSÜSTÜ DERS KATALOG FORMU (GRADUATE COURSE CATALOGUE FORM) Course Name Discrete Optimization Kodu (Code) BLG 5E Lisansüstü Program (Graduate Program) Dersin Türü (Course
ÖZGEÇMİŞ VE ESERLER LİSTESİ ÖZGEÇMİŞ Adı Soyadı: ÖZLEM TÜRKŞEN Doğum Tarihi: 17 Temmuz 1979 Öğrenim Durumu: Derece Bölüm / Program Üniversite Yıl Lisans İstatistik Ankara Üniversitesi 2002 Y. Lisans İstatistik