Slayt 1 - Bilgisayar Mühendisliği Bölümü
Transkript
Slayt 1 - Bilgisayar Mühendisliği Bölümü
Mühendislikte Zeki Programlama Teknikleri ve Uygulamaları Prof.Dr.Adem KALINLI Erciyes Üniversitesi Mayıs 2012 Sunum İçeriği Giriş Mühendislik Problemlerinin Çözüm Süreci Optimizasyon Kavramı Klasik Çözüm Yöntemleri Optimizasyon Yöntemlerinin Sınıflandırılması Metotların Kullandığı Arama Yöntemleri Problem Sınıfları Karmaşıklık Teorisi Graf Teorisi Amaç fonksiyon, kısıtlar, uygulanır bölge Zor Problemler Yapay Zeka Kavramı Prof.Dr.Adem KALINLI 2 Sunum İçeriği Yapay Zekanın Örnek Problemleri Yapay Zeka Yöntemleri Yapay Sinir Ağları Bulanık Mantık Sezgisel Optimizasyon Algoritmaları Genetik Algoritmalar Tabu Arama Algoritması Karınca Koloni Algoritması Yapay Bağışıklık Algoritması Tavlama Benzetimi Algoritması … Yapay Zekanın Mühendislik Uygulamaları Tıpta Yapay Zeka Örnek Yapay Sinir Ağı Tasarımı ve Uygulama Prof.Dr.Adem KALINLI 3 Giriş “Geçen yıl hiçbir radikal gelişme ortaya çıkmamış olmasından anlaşılıyor ki, otomobil gelişiminin son noktasına pratik olarak ulaşılmıştır.” Scientific American, Jan.2, 1909 Kazanmak için ittifak kurmak, taraf veya strateji değiştirmek yetisine sahip, düşünen ve konuşan bir yaratık olan insan, her zaman hayal kurmaktadır. Başlangıçta her şey masallarla başladı… Alaaddinin uçan halısı, Jule Verne yada diğerlerinin fantastik eserleri, aya yolculuk, denizler altında 20000 fersah.. İnsan bir problemi düşünür ve olabilirliğini teorik olarak ispatlar ise, o sonunda gerçekleşir. Prof.Dr.Adem KALINLI 4 Giriş İnsan gibi davranan makineler yapmak, kuşlar gibi uçan araçlar geliştirmek, tarih boyunca insanların en çok hayal kurduğu konulardandır. Bilim dünyası, bu hayalleri gerçek kılabilmek için yüz yıllardır uğraşmakta ve bu çabalar sonuç vermektedir. Gerek gerçekleştirilen teçhizatların zeki davranışlar sergilemesi, gerekse problem çözmede zeki yaklaşımlar sergileyen güçlü yöntemlerin geliştirilmesi ve kullanılması, son birkaç on yılda bir çok araştırmanın konusu olmuştur. Yapay Zeka, genel olarak insan ve doğadaki zeki davranışların taklit edilerek problemlerin çözümünde kullanılmasıyla ilgili bilim dalıdır. Prof.Dr.Adem KALINLI 5 Giriş Yapay Zeka, günümüzde Elektronik, Haberleşme, Endüstri, Havacılık, Robotik, Tıp, Ekonomi, Askeri ve Stratejik Uygulamalar v.b. neredeyse tüm alanlarda kullanılan önemli araçlardan birisi olmuştur. Dolayısıyla, farklı disiplinlerdeki araştırmacılar zaman zaman yapay zeka metotlarının kullanımına ihtiyaç duyar olmuşlardır. Yapay zeka nedir? Ne tür avantajlar sunar, Ne kadarını bilmelisiniz? Mesleğimle ilgili çalışma alanıma katkı sağlar mı? Bir problemin çözümüne nasıl uygulayabilirim? Prof.Dr.Adem KALINLI 6 Dersin Amacı Bu dersin amaçlarından bazıları aşağıda listelenmiştir: Problem türleri ve çözüm yöntemleri Geleneksel problem çözme yöntemleri Yapay Zeka yöntemlerinin diğer yöntemlere göre avantaj ve dezavantajlarının ortaya konması Yapay Zeka yöntemlerinin tanıtımı Problemlerin çözümlerine uygulanmasında dikkat edilmesi gerekli hususlar Örnek Yapay Zeka Uygulamaları Prof.Dr.Adem KALINLI 7 Prof.Dr.Polya (Matematikçi, 1888-1985) “Problemleri çözmek, yüzmeye, paten kaymaya veya piyano çalmaya benzer pratik bir beceridir. Buna yalnız, seçici taklitler ve daima antrenman yaparak erişmek mümkündür. Bu kitapta bütün problemleri çözmeniz için gerekli yöntemlerin, yani bütün kapıları açan olağanüstü anahtarın olmasını beklemeyin. Fakat, burada taklit için iyi örnekler ve pratik beceri kazanmak için uygun olanaklar elde edebilirsiniz. Yüzmeyi öğrenmek istiyorsanız suya girmeniz gerekir. Problem çözmeyi öğrenmek için ise, onları çözmelisiniz... ” Prof.Dr.Adem KALINLI 8 Mühendislik Problemlerinin Çözüm Süreci Bilgi ve anlama herhangi bir eşyanın (aracın) verimli kullanılması için ön şartlardır. Alet çantanız ne kadar zengin olursa olsun, eğer bir otomobilin nasıl çalıştığını bilmiyorsanız, onu onaramazsınız. Sistemlerin temel çalışma ilkeleri köklü bir şekilde kavranırsa, problemlerin çözülmesinde potansiyel yöntemler geliştirmekte mümkün olabilir. Sistemlerin çalışma ilkeleri ise genel olarak gözlem (tecrübe) ve deney yaparak kazanılır. Ancak, tecrübe ile kazanılan bilgiler önemli olmakla beraber, olayın sadece yarısıdır. Bilim adamları yıllarca yaptıkları gözlem ve deneylerin sonunda, sonuçların belirli yönlerden hep tekrarlandığını gördüler. Bu şekilde tekrarlanan genel davranışlar temel yasalar olarak ifade edilmektedir. Mühendislik problemlerinin çözümü, teorik analiz ve deneysellikten oluşan iki aşamalı bir yaklaşım uygulanmasını gerektirir. Prof.Dr.Adem KALINLI 9 Mühendislik Problemlerinin Çözüm Süreci Bir mühendislik probleminin çözümü açısından bakıldığında, matematiksel bir model şeklinde ifade edilebilen bir çerçeve çok kullanışlıdır. Matematiksel bir model, en genel anlamıyla, fiziksel bir sistemin veya bir sürecin ana özelliklerini matematiksel terimlerle ifade eden bir eşitlik veya formül olarak tanımlanabilir. Çok genelleştirilmiş olarak, matematiksel model aşağıdaki biçimde fonksiyonel bir ilişki olarak gösterilebilir: zorlayıcı bağımsız f , parametrel er , değişken değişenler fonksiyonl ar bağımlı Bağımlı değişken: sistemin davranışını yada konumunu belirten özellik Bağımsız değişken: zaman veya konum gibi boyut Parametreler: Sistemin özellikleri veya yapısı Zorlayıcı fonksiyonlar : sistemi etkileyen dış etkenler. Prof.Dr.Adem KALINLI 10 Mühendislik Problemlerinin Çözüm Süreci Gerçek matematiksel ifadeler basit bir cebirsel bağıntı Problemin Tanımı olabileceği gibi çok uzun karmaşık diferansiyel denklemler de olabilir. F=m.a dy Q Q 3 sin 2 t dt A A Matematiksel Model Veriler Çözüm Araçları: Bilgisayarlar, istatistik, sayısal yöntemler, grafikler v.b. Sayısal veya Grafik Sonuçlar Sosyal Arabirimler: Zamanlama, optimizasyon, iletişim, halkın katılımı v.b. Uygulama Prof.Dr.Adem KALINLI 11 Çözüm Yaklaşımları Denklemlerin Kökleri Cebirsel, doğrusal denklem sistemleri Optimizasyon Eğri Uydurma Sayısal İntegrasyon Adi diferansiyel denklemler Kısmi diferansiyel denklemler … Prof.Dr.Adem KALINLI 12 Mühendislik Uygulamaları İdeal ve İdeal Olmayan Gaz Yasaları (Biyomühendislik/Kimya Mühendisliği) İdeal gaz yasası Bu denklem çok yaygın kullanılmasına rağmen, bazı gazlar için uygundur ve sadece sınırlı basınç ve : pV=nRT; p: mutlak basınç, V:hacim, n mol sayısı, R evrensel gaz sabiti, T: sıcaklık sıcaklık aralığında doğru sonuç verir! a Alternatif : van der Waals denklemi: p 2 v b RT ; v=V/n:molar hacim, a ve b gaza bağlı deneysel v katsayılar Kimya mühendisliği tasarım projesinde, uygun saklama kaplarının seçilebilmesi için değişik basınç ve sıcaklık kombinasyonlarında karbondioksit ve oksijen molar hacimleri, v’ nin hassas olarak tahmin edilmesi gerekmektedir. Prof.Dr.Adem KALINLI 13 Mühendislik Uygulamaları Bir elektrik devresinin tasarımı Elektrik mühendisleri devrelerin kararlı hal davranışını inceler. Devrede anahtarın kapatılmasıyla, akım kondansatör (C) ve bobin (L) arasında salınır. S Tasarım Problemi: bilinen L ve C için enerjiyi belirli bir V hızda sönümleyecek uygun R değerini bulmak d 2q dq 1 L 2 R q0 dt C dt Prof.Dr.Adem KALINLI L C R VC 14 Denklemlerin Kökleri / Sayısal Yaklaşımlar Kapalı Yöntemler Grafik Yöntemler İkiye Bölme Yöntemi Yer Değiştirme Yöntemi Adım Adım Artırmalı Arama Açık Yöntemler Basit Sabit Noktalı İterasyon Newton-Raphson Yöntemi Sekant Yöntemi Polinomların Kökleri Müller Yöntemi Bairstow Yöntemi Diğer Yöntemler Prof.Dr.Adem KALINLI 15 Klasik Çözüm Yöntemleri Her problem için, çeşitli sayısal yöntem seçenekleri ile karşılaşabilirsiniz. Hangi problem için hangi yöntemin daha etkili olduğu genellikle kişiseldir ve akıllıca seçim yapmayı gerektirir. Klasik mühendislik hesaplamalarının çoğu, analitik çözüme olanak sağlamak için yapılan doğrusallaştırmalara dayanır. Bu tür doğrusallaştırmalar çözüme ulaşmayı kolaylaştırır, ancak sonuçlar belirli oranlarda hata içerir. Daha gerçekçi çözümler elde etmek, daha büyük boyutlu (daha zor) problemlerin çözülmesini gerektirir. Bir sistemin çalışmasını parametrelerinin bir fonksiyonu olarak saptamak çoğu zaman karmaşık olmayan basit bir iştir. Ancak, istenen çalışma şartları belirlendiğinde, parametrelerin olması gereken değerlerini belirlemek genellikle çok daha zordur.! Prof.Dr.Adem KALINLI 16 Klasik Çözüm Yöntemleri VO Alçak Geçiren Filtre devresi, 6 adet R, 2 adet C içeriyor. Geçen Band fC Alçak geçiren filtre karakteristiği C1 R4 R3 - R5 + giriş + C2 R6 + çıkış R 2 R 3 R 4 R 3 R 1 R 2 R 1 ω 0 4 R 3 C1C 2 R 5 R 6 R1 R2 - H f Q R 3 R 1 R 2 C1 R 4 R 5 R 1 R 3 R 4 C 2 R 3 R 6 Devrede, ω0=10000/2π = 1591.55 rad/sn ve Q=1.4142 olası için R ve C değerleri ne olmalıdır! Prof.Dr.Adem KALINLI 17 Optimizasyon Kök bulma, fonksiyonun sıfır olduğu noktaların aranmasıdır. Optimizasyon ise, minimum veya maksimumun aranmasıdır. maksimum f(x) 𝑓′ 𝑥 = 0 𝑓′′ 𝑥 < 0 𝑓 𝑥 =0 0 kök kök minimum kök x 𝑓′ 𝑥 = 0 𝑓′′ 𝑥 > 0 Bazı basit matematiksel ifadeler için birinci türevi sıfıra eşitleyerek elde edilen denklemi çözmek yeterlidir. Ancak, problemlerin türü, türevinin alınıp alınamaması ve kısıtlamalarda dikkate alındığında optimizasyon için geliştirilmiş pek çok yöntem vardır. Prof.Dr.Adem KALINLI 18 Optimizasyon Optimizasyon bilimin önemli araçlarından biridir. Bilimsel olmayan kaba bir yaklaşımla optimizasyon daha iyi yapmaktır (doing better). Genellikle verilen bir zaman içerisinde bir problemin mümkün olan en iyi çözümünü bulmaya çalışmak süreci optimizasyon olarak tanımlanır. Diğer bir söyleyişle optimizasyon, belirli şartları sağlayacak şekilde bir problemin parametre değerlerinin belirlenmesi işlemi olarak da tanımlanabilir. Prof.Dr.Adem KALINLI 19 Optimizasyon Doğadaki birçok davranış optimizedir. Fiziksel sistemler minimum enerjili bir durumda bulunma eğilimindedir. Yalıtılmış kimyasal bir sistemde moleküller, elektronlarının toplam potansiyel enerjisi minimum olana kadar birbirleriyle etkileşim halindedir. Işık ışınları ulaşım sürelerini minimum edecek yollar takip ederler. Karıncalar, yuva ve yiyecek kaynağı arasında en kısa yolu takip ederler. … Prof.Dr.Adem KALINLI 20 Optimizasyon Genel olarak bir optimizasyon problemi aşağıdaki şekilde yazılabilir: c x 0, subject to i ci x 0, min f ( x) xRn iI Burada x, bilinmeyenler veya parametreler olarak adlandırılan tasarım vektörüdür. f değeri maksimize yada minimize edilmek istenen ve x’ in fonksiyonu olan amaç fonksiyonudur. c bilinmeyenler tarafından sağlanması gereken sınırlamalar (kısıtlar) vektörüdür. min x1 2 x2 1 2 iE 2 x12 x2 subject to x1 x2 0 2 Optimizasyon probleminin temel öğeleri: (a) amaç fonksiyonu, (b) karar değişkenleri, (c) kısıtlar. Prof.Dr.Adem KALINLI 21 Klasik Optimizasyon Yöntemleri Bir Boyutlu Kısıtlamasız Optimizasyon Golden Bölme Araması İkinci Derece İnterpolasyon Newton Yöntemi Çok Boyutlu Kısıtlamasız Optimizasyon Doğrudan Yöntemler: Rastgele Arama, Benzer değişim ve model aramaları Gradyen Yöntemler Kısıtlamalı Optimizasyon Doğrusal Programlama, grafik çözüm, simpleks yöntemi Doğrusal olmayan kısıtlamalı optimizasyon: zor problemlerdir. Yöntemler sınırlıdır. Genelde, muhtelif indirgemeler ve varsayımlarla kullanılabilen gradyen tabanlı yöntemler kullanılır. Prof.Dr.Adem KALINLI 22 Klasik Optimizasyon Yöntemleri Gradyen Yöntemler Gradyen yöntemler optimumu bulmak için türev bilgisini kullanır. Bir boyutlu bir fonksiyonun birinci türevi, diferansiyeli alınan fonksiyonun eğimini ifade eder. Bu bilgi optimizasyon için anlamlıdır. Eğimin pozitif olması, bağımsız değişkeni artırmanın fonksiyonun değerini artıracağı anlamına gelir. f(x) 𝐸ğ𝑖𝑚 = 𝑓 ′ 𝑎 0 a f(x) x 0 𝐸ğ𝑖𝑚 = 𝑓 ′ 𝑏 = 0 b x Birinci türev, optimum noktasına ne zaman erişileceğini de söyler. Çünkü burası türevin sıfıra gittiği noktadır. Prof.Dr.Adem KALINLI 23 Klasik Optimizasyon Yöntemleri Gradyen Yöntemler Ayrıca, ikinci türevin işareti ilerleyişin minimuma mı yoksa maksimuma mı ulaşıldığını ifade ederi. maksimum f(x) 𝑓′ 𝑥 = 0 𝑓′′ 𝑥 < 0 𝑓 𝑥 =0 0 kök kök kök minimum x 𝑓′ 𝑥 = 0 𝑓′′ 𝑥 > 0 Bu bilgiler bir boyutlu aramalarda doğrudan işe yarar. Ancak, çok boyutlu aramaları tam olarak anlayabilmek için önce birinci ve ikinci türevlerin çok boyutlu bağlamda nasıl ifade edildiğine bakılmalıdır. Prof.Dr.Adem KALINLI 24 Klasik Optimizasyon Yöntemleri Gradyen Yöntemler İki boyutlu f(x,y) fonksiyonunu bir dağın üzerindeki konumunuza göre deniz seviyesinden yüksekliğinizi ifade etsin. Dağın üzerinde (a,b) konumunda olduğunuzu ve herhangi bir doğrultudaki eğimi bulmak istediğimizi varsayalım. Yönü belirlemenin bir yolu, tanımı, x ekseni ile θ açısı yapan yeni bir h ekseni boyunca yapmaktır. Bu yeni eksen boyunca yükseklik yeni bir g(h) fonksiyonu olarak düşünülebilir. x x=a y=b h=0 Konumunuzu bu eksenin başlangıcı olarak tanımlarsanız (h=0), bu yöndeki eğim g’(0) olacaktır. Yöne bağlı türev olarak verilen bu eğim x ve y eksenleri boyunca alınan kısmi türevlerle hesaplanabilir. θ h y Prof.Dr.Adem KALINLI Kısmi türevler x =a ve y=b noktasında hesaplanmıştır. 25 Klasik Optimizasyon Yöntemleri Gradyen Yöntemler Amacımız bir sonraki adımda en fazla yükseltiyi bulmak olduğunu varsayarsak, En dik çıkış hangi yöndedir? Bu sorunun yanıtı gradyendir! Bu aynı zamanda f(x,y) fonksiyonunun x =a ve y=b noktasındaki yöne bağlı türevini verir. Gradyeni nasıl kullanırız? Gradyen bize, en hızlı şekilde yükseklik kazanmak istiyorsak, hangi yöne ilerlememiz gerektiğini ve bu yönde gidersek ne kadar yükselti kazanacağımızı söyler. Ancak bu strateji bizi her zaman tepeye ulaştıramaz! Prof.Dr.Adem KALINLI 26 Klasik Optimizasyon Yöntemleri Gradyen Yöntemler, ÖRNEK Gradyeni kullanarak, aşağıdaki fonksiyon için (2,2) noktasındaki en hızlı iniş yönünü hesaplayalım. 𝑓 𝑥, 𝑦 = 𝑥𝑦 2 Bulunduğumuz yükseklik 𝑓 2,2 = 8. Kısmi türevler, 𝜕𝑓 2 𝑦 = 22 = 4 𝜕𝑥 𝜕𝑓 = 2𝑥𝑦 = 2 2 2 = 8 𝜕𝑦 Gradyen, ∇𝑓 = 4𝑖 + 8𝑗 x eksenine göre seçmemiz gereken yön, θ = 𝑡𝑎𝑛−1 8 4 = 1.107𝑟𝑎𝑑𝑦𝑎𝑛 (63.40 ) Bu en dik yolda bir birim ilerlersek, 8.944 birim yükseklik kazanırız. 𝑔′ 0 = 4 cos 1.107 + 8 sin 1.107 = 8.944 Bir boyutlu fonksiyonlarda olduğu gibi, kısmi türevlerin her ikisi de sıfır ise, iki boyutlu optimuma erişilmiştir. Prof.Dr.Adem KALINLI 27 Klasik Optimizasyon Yöntemleri Gradyen Yöntemler, Çok şanslı değilseniz ve doğrudan tepeyi gösteren bir yamaçtan başlamadıysanız, hareket eder etmez yolunuz en hızlı artış yönünden sapacaktır. Nasıl üstesinden gelinebilir? Sabit bir doğrultuda artış duruncaya kadar ilerlenip (yol düzleşene kadar), Yeni bir yön ve gradyen hesaplanarak devam edilebilir (en hızlı artış yöntemi). Prof.Dr.Adem KALINLI 28 Klasik Optimizasyon Yöntemleri Gradyen Yöntemler, Genellikle gradyen veya Newton gibi yöntemler bulunulan bölgenin optimumuna (yerel optimum) hızla yakınsamasına rağmen, genellikle ıraksama sorunu yaşarlar. f(x) global optimum yerel optimum 0 x 29 Optimizasyon Metotlarının Sınıflandırılması Optimizasyon metotları iki düzeyde tanımlanır; problem düzeyinde ve problem üstü düzeyde (meta level). Problem düzeyinde optimizasyon işleminde, bir problem kümesi içerisindeki her problem tek tek diğerlerinden bağımsız olarak çözülür. Problem üstü düzeyde çeşitli problemlerden oluşan bir küme bir bütün olarak göz önüne alınarak optimum çözüm aranır. Problem üstü düzeyde, optimizasyon metotları, problem düzeyindeki optimizasyon metotlarını yönlendirmek amacıyla da kullanılır. 30 Optimizasyon Metotlarının Sınıflandırılması Örneğin, Problem düzeyinde optimizasyonda yapay sinir ağının mimarisi (nöron sayısı, her bir nöronun aktivasyon fonksiyonu ve bağlantı yapısı v.b.) probleme göre tasarımcı tarafından seçilir ve sabittir. Optimizasyon işlemi ile sadece bağlantıların katsayıları değiştirilebilir. Bu durumda nöronlar arası bağlantı ağırlıkları birer parametre, yapay sinir ağının çıkışı ve olması istenen çıkış arasındaki fark ise minimum yapılması gereken bir amaç fonksiyonu olarak düşünülebilir. giriş katmanı boy 1 testis hacmi 2 saklı katman 1 ejakülat hacmi FSH . LH . T. testesteron çıkış katmanı 1 Genetik Anomali 8 6 31 Optimizasyon Metotlarının Sınıflandırılması Problem üstü düzeyde optimizasyonda ise, yapay sinir ağının mimarisi sabit değildir. Örneğin yapay sinir ağı ileri beslemeli veya geri beslemeli olabilir. Aktivasyon fonksiyonu her bir nöron için farklı olabilir. Probleme göre ağın yapısı optimizasyon işleminin bir parçası olarak algoritma tarafından tayin edilir ve değiştirilir. giriş katmanı boy testis hacmi saklı katmanlar 1 2 1 1 ejakülat hacmi FSH . . LH . . T. testesteron çıkış katmanı 1 Genetik Anomali ? 6 ? 32 Metotların Kullandığı Arama Yöntemleri Optimizasyon algoritmalarında kullanılan bir çok arama stratejisi vardır: Yorucu (exhaustive), Rasgele (random), Açgözlü (greedy), Tepe tırmanma (hill climbing), Sezgisel (heuristic), Belirleyici (deterministic) İhtimalci (stochastic) 33 Metotların Kullandığı Arama Yöntemleri Yorucu aramada, giriş veri kümesinin tüm kombinasyonları test edilerek araştırma uzayında en iyi çözüm aranır. Pratikte uygulanması zor bir metottur. Rasgele aramada, giriş veri kümesinin rasgele üretilen kombinasyonları makul bir çözüm bulununcaya kadar denenir. Küresel çözüme yakınsama özelliği yoktur. Rasgele arama metodu genellikle kısa zamanda iyi çözümler bulamaz. Açgözlü arama, rasgele aramaya benzemektedir. Giriş veri kümesinin rasgele üretilen kombinasyonlarını dener ve iyi bir çözüm bulduğunda bunu saklar. Daha sonra bu iyi çözüm etrafında araştırmaya devam eder. Bu metotta açgözlü kelimesi bölgesel ölçekte daha iyi çözümü kabul etmek yönünde tercihin yüksek oluşunu ifade eder. Bölgesel ölçekte aramayı kötüye götüren çözümler kabul edilmez. Oysa küresel optimum kimi zaman yeni araştırma yönü olarak bölgesel ölçekte kötü olan çözümleri kabul etmekle bulanabilmektedir. Açgözlü arama hızlı sonuç vermesine karşın küresel optimumu bulma bakımından yetersizdir. 34 Metotların Kullandığı Arama Yöntemleri Tepe tırmanma metodu, bölgesel optimumu aşabilmek için araştırma yönü olarak bölgesel optimum etrafında daha kötü çözümlerin kabul edilmesi gerektiğini temel alır. Bu metotta arama, hata veya maliyet değerini daha yükseğe çıkaran tarafa yönlendirildiği için arama işlemi tepe tırmanmayı çağrıştırır. Arama esnasında elde edilen çözümler iyiye giderken bir noktadan sonra kötüye giderse, o noktanın bir sırt noktası olduğu veya tersi yönde gelişim durumunda gelişimin yön değiştirdiği noktanın bir dip noktası olduğu anlaşılır. Bu metot türev alma işleminin verdiği neticeyi bir başka biçimde arayıp deneyerek bulur ve genellikle doğrusal olmayan problemlerde kullanılır. 35 Metotların Kullandığı Arama Yöntemleri Sezgisel stratejiler, genellikle problem üstü düzeyde kullanılır. Literatürde heuristic olarak tanımlanır. Yunanca kökenli olan (heurika), Türkçe’de bulmak fiilinin karşılığıdır. Sezgisel terimi; akıllı tahminlere dayalı buluş yöntemi veya yeni çözümlerin keşfine götüren bulgulara dayalı arama yöntemi olarak tanımlanır. Sezgisel terimi ile tanımlanan algoritmaların ortak özelliği; araştırma uzayı çok büyük olan problemlerde çözümün aranmasını sınırlayan bir kural, strateji, hile, sadeleştirme ve benzeri etmenler kullanmalarıdır. Bu etmenlerden genellikle araştırmayı yönlendiren bir bulgu kastedilir. Örneğin ACO için kullanılan etmen feromon bulgusu, TS için kullanılan etmen seçilen hareket hakkında yakınlık veya sıklık bulgusudur. Bulgucu algoritmalarda mevcut çözümlerden, sonraki aşamada elde edilecek olan yeni çözümleri daha önceden belirlemek mümkün değildir. Bulgucu stratejiler arama zamanını kısaltır, optimum çözüme yakın çözümler sunar fakat optimum çözümü garanti edemez. 36 Metotların Kullandığı Arama Yöntemleri Belirleyici (deterministik) stratejide, mevcut çözümlere göre bir sonraki aşamada elde edilecek çözümler belirlidir, sabittir. Belirleyici stratejiler genellikle problem düzeyinde uygulanır. Örneğin Newton-Raphson yönteminde, f(x)’ in çözümünü bulmak için, başlangıçta xi değeri seçilir ve bunun için amaç fonksiyonu değeri hesaplanır. Bir sonraki adımda, x parametresinin değeri aşağıdaki eşitlikle belirlenir: Deterministik yöntemde, belirli parametreler bir probleme her uygulanışında aynı sonucu verir. Deterministik yaklaşımların uygulanması, zaman gibi sınırlı kaynaklar nedeniyle, her problem için mümkün olmayabilir. Örneğin bir satranç oyunu yazarken, bir taşın bir hamlesinin oyunun sonucuna etkisini denetlemek gerekir. Bu amaç için oluşturulan oyun ağacında (game tree) en iyi hamleyi seçmek için ortalama olarak hamle başına (35^50)^2 olasılığı denemek gerekir. 37 Metotların Kullandığı Arama Yöntemleri İhtimalci (stokastik) stratejide ise, eski çözümlerin kalitesi nispetinde değerler alan bir olasılık dağılım fonksiyonuyla bir rasgele sayı üretecinden faydalanarak yeni çözümler belirlenir. Karar mekanizması olasılık tabanlı seçimlere dayanır. Dolayısıyla, araştırmanın sonraki adımları önceden kestirilemez. Deterministik olmayan yaklaşımlar, aynı durum için farklı çalışmalarında aynı sonucu garanti etmeyen yöntem veya algoritmalardır. Bunlara stokastik veya olasılık tabanlı yöntemler de denir. 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. Genetik Algoritma ve Karınca Koloni Algoritması gibi Sezgisel (heuristic) yöntemler deterministik olmayan yöntemlerdir. Bu yöntemler, en iyi çözümü garanti edemezler ama, daha az deneme ile "iyi" bir çözüm bulabilmeyi garanti ederler. 38 Metotların Kullandığı Arama Yöntemleri Örnek: Ankara’dan t0 anında hareket ettiği bilinen bir yolcu otobüsü Kayseri’de karşılanmak istensin. Amaç, otobüsün Kayseri’ye geliş vaktini olabildiğince yakın tahmin etmek. Belirleyici Kişi : Otobüsün ortalama hızını (Vort) ve Kayseri-Ankara mesafesini (x) tespit eder. Otobüsün Ankara’dan hareket saati t0’ı dikkate alır ve Kayseri’ye geliş vaktini, t = X/Vort+ t0 formülü ile hesaplar. Belirleyici, parametreler değişmedikçe soruya her defasında aynı kararla cevap verecektir. İhtimalci Kişi : İhtimalci geçmiş günlerin veya geçmiş yılların istatistiklerine ihtiyaç duyar. Otobüsün hangi olasılıkla hangi vakitte geleceğini gösteren bir olasılık dağılım fonksiyonu oluşturur. Kararını bu olasılık dağılım fonksiyonuna göre verir. Hangi vaktin karar olarak verileceği o vaktin olasılık değeri ile orantılıdır. İhtimalci’nin kararı, olasılık tabanlı bir sistem kullanıldığı için doğal olarak her defasında farklı olabilir 39 Metotların Kullandığı Arama Yöntemleri Bulgucu Kişi : Seyahat süresini etkileyen faktörleri ve ne oranda etkili olduklarını araştırır. Havanın yağmurlu veya yerlerin buzlu olması durumunu ve seyahat süresi üzerindeki etkisini dikkate alır. Dolayısıyla, hava durumu kararı etkileyen bir bulgudur. Ayrıca, otobüsün ne kadar sıklıkla (frekans) hangi vakitlerde gelmekte olduğunu dikkate alır. Frekans bulgusu bu problem dışında farklı türlerde bir çok problemde kullanılabileceğinden problem üstü bir bulgudur (meta-heuristic). Bulgucu her defasında farklı cevap verebilir. Çözüm kalitesini başlangıç bilgisi önemli derecede etkiler. Cevabını önceden kestirmek veya hesaplamak mümkün değildir. Her defasında bulgular ve bulguların karar üzerindeki etkinlikleri değişebilir. 40 Metotların Kullandığı Arama Yöntemleri Özetle, belirleyici yaklaşım probleme özeldir ve statik bir yapı kullanılır. Bulgucu ve ihtimalci yaklaşım farklı türde problemlere uygulanabilir ve dinamik bir yapıya sahiptir. Her karar sürecinde verilecek kararlar bulgucu ve ihtimalci yaklaşımda değişebilir, bu özellik onlara adaptif çözüm üretebilme esnekliğini (yeteneği) kazandırır. Akılcı (Intelligent) Yaklaşım : Gerçek hayatta insanlar hem ihtimalleri hem bulguları hem de hesaplanabilen durumları dikkate alarak karar verirler. Bu nedenle yukarıdaki örnekte bahsedilen otobüsün gelişini sadece ortalama hıza bağlı olarak tahmin etmek doğru değildir. Bunun yanında otobüsün genellikle hangi vakitlerde geldiği, hava durumunun seyri etkileyip etkilemeyeceği veya olması muhtemel aksaklıklar (yol çalışması, arıza v.b.) göz önüne alınarak tahmin yapılmalıdır. Bulguları, ihtimalleri ve hesaplanabilen belirli durumları dengeli oranda karar mekanizmasında kullanmak, akıllıca bir yaklaşımdır. 41 Metotların Kullandığı Arama Yöntemleri Modern optimizasyon algoritmaları, Genel olarak önce belirleyici bir yöntemle hesaplanabilen en iyi çözümü başlangıç çözümü olarak tespit eder, Sonra bu çözümü ihtimalci ve bulgucu stratejiler kullanılarak geliştirmeye çalışır. 42 Optimizasyon Problemlerinin Sınıflandırılması Optimizasyon problemleri kullanılan değişken tipine, kısıtlama varlığına ve hesaplama karmaşıklığına göre sınıflandırılabilir. Optimizasyon problemleri Sürekli Kısıtlamasız Ayrık Kısıtlamalı Kısıtlamasız Kısıtlamalı - Tek Modlu - Doğrusal - Polinomial - Çok Modlu - Doğrusal Olmayan - NP-Hard Optimizasyon problemleri değişken tipine göre sürekli ve ayrık problemler olmak üzere ikiye ayrılır. Problem değişkenleri üzerinde sınırlama varlığına göre sınırlamalı ve sınırlamasız olarak bölünür. İşlem karmaşıklığına (complexity) göre tek modlu, çok modlu, polinomal (P) ve belirleyici olmayan polinomal (NP) problemler olarak gruplandırılırlar. 43 Sürekli ve Ayrık Problemler Bir optimizasyon problemindeki bilinmeyenler uygulanabilir bölgede tüm değerleri alabiliyorsa, bir başka deyişle problem sonsuz sayıda giriş ve çıkış değerleri alabiliyorsa bu optimizasyon problemi sürekli problem olarak adlandırılır. Eğer değişkenler sonlu sayıda belirli değerleri alabiliyorsa optimizasyon problemi ayrık problem veya kombinasyonel problem olarak adlandırılır. Diğer bir deyişle ayrık problem, nesnelerin bir amacı gerçekleştirecek biçimde gruplandırılması, seçilmesi, veya sıraya konması problemi olarak tanımlanır. 44 Sürekli ve Ayrık Problemler Birinci grafikte dikkate alınan amaç fonksiyonun parametresi x, 0<x≤5 aralığında istenilen ondalık hassasiyette sonsuz sayıda değer alabilir. İkinci grafikte ise 0<x≤5 aralığında x parametresinin alabileceği değerler {1,2,3,4,5} kümesi ile sınırlıdır ve bu değerler sonlu sayıdadır. 45 Tek Modlu ve Çok Modlu Problemler Bazı optimizasyon problemlerinin yalnızca bir adet bölgesel minimumu vardır ve bu değer aynı zamanda problemin küresel minimum değeridir. Çözümü kolay bulunan bu tür problemlere tek modlu problemler denir. Gerçek hayat karmaşıktır ve genellikle çözüm aranan problemler doğrusal olmayan yapıya sahiptir. Bu yapıdaki problemlerde genellikle çok sayıda bölgesel minimum bulunur. Çözümü zor olan bu tür problemlere de çok modlu problemler denir 46 Doğrusal ve Doğrusal Olmayan Problemler Grafiği doğrulardan oluşan başka bir deyişle; y=Ax+B şeklinde birinci dereceden denklem eşitliği veya eşitsizliği ile tanımlanan fonksiyonlara doğrusal fonksiyon denir. (Linear) Grafiği eğrilerden oluşan ve y= e(x), log(x) ve xn şeklinde tanımlanan fonksiyonlara da doğrusal olmayan fonksiyon denir. (Nonlinear) Sınırlamalı sürekli problemler, sınırlama fonksiyonlarına bağlı olarak eğrisel veya doğrusal olurlar. Optimizasyon probleminde kısıtlamaları oluşturan fonksiyonlar doğrusal ise problem sınırlamalı doğrusal optimizasyon problemi (constraint linear optimization problem) olarak adlandırılır. Sınırlama fonksiyonlarından en az birisi eğrisel olan problem sınırlamalı doğrusal olmayan optimizasyon problemi (constraint nonlinear optimization problem) olarak adlandırılır. 47 Doğrusal Problem Örneği Bir Doğrusal Programlama Problemi Gaz işleyen bir tesisin her hafta sabit miktarlarda gaz aldığını varsayalım. Alınan gaz işlenerek normal ve süper gaz elde ediliyor. Üretilen gaz mutlaka satılıyor, ürünler farklı oranlarda kar bırakıyor. Ancak üretimleri hem zaman hem de depolama bakımından sınırlı. Örneğin aynı anda sadece bir tür gaz üretiliyor ve tesis haftada maksimum 80 saat çalışmaktadır. Şartlar tabloda özetlenmiş: Ürün Kaynak Kaynağın Varlığı Normal Süper Ham Gaz 7m3/ton 11m3/ton 77m3/ton Üretim Süresi 10saat/ton 8saat/ton 80saat/hafta Depolama 9 ton Kar 150/ton 6 ton Maksimum Z=150x1+175x2 7x1+11x2≤77 10x1+8x2≤80 x1≤9 x2<6 x1,x2≥0 175/ton İşletmenin maksimum kar etmesi için, hangi gazdan ne kadar üretilmelidir? 48 Karmaşıklık Teorisi Algoritmaların ne kadar karmaşık olduğunu, hızını, işlem süresin ve problemlerin ne kadar zor olduğunu araştıran matematik dalı karmaşıklık teorisi ile açıklanır . Karmaşıklık algoritmaların gerektirdiği işlem zamanını ve karmaşıklık derecesini ölçer. İşlem karmaşıklığı aynı zamanda algoritmaların yeterliliğinin bir ölçüsüdür. Çünkü bilgisayar teknolojisindeki hızlı gelişmeler birim işlem zamanı ve kullanılan hafıza miktarı gibi gereksinimleri önemsiz kılmaktadır. Bu nedenle algoritmanın işlem karmaşıklığı onun verimliliğini ölçmede standart bir yaklaşımdır. 49 Karmaşıklık Teorisi Boyutu n olan bir problemi çözen bir algoritmanın yaptığı hesap miktarının 7n8+2n+5 olduğunu varsayalım. İşlem karmaşıklığında önemli olan problem boyutu n arttıkça yapılan hesap miktarının ne oranda arttığıdır. Hesap miktarının artış oranı, 7n8 terimi dikkate alındığında adeta bir patlama gibidir, 2n teriminde ise sabittir. Bu nedenle işlem karmaşıklığının ölçümünde hesap miktarını gösteren fonksiyondaki düşük dereceden terimler göz ardı edilir sadece en yüksek dereceli terim esas alınır. Yukarıdaki örnek için sadece 7n8 terimi esas alınmıştır. Buradaki sabit katsayı 7 artış oranını etkilemez, çünkü artış oranı türeve dayalı bir büyüklüktür. Sonuç olarak söz konusu örnek için işlem karmaşıklığı n8 olarak belirlenir ve O(n8) olarak gösterilir. Bu gösterimle aynı zamanda algoritmanın n8 birim işlem zamanı tükettiği ifade edilir. 50 Karmaşıklık Teorisi Bir problemin boyutu (giriş veri miktarı) n ile ölçülür ve n boyutlu bir problemin bir işlemde gerektirdiği hesap miktarı N ile gösterilir. N ile n arasında fonksiyonel bir ilişki kurulabilir. Çünkü problem boyutu n büyüdükçe bir işlem için gerekli hesap miktarı N de büyür. Fakat bu büyüme oranı problem türlerine göre farklılık gösterir. Bu farklılık problemlerin zorluk derecesi ile ilişkilidir ve problem türlerinin sınıflandırılmasında da kullanılır . 51 Karmaşıklık Teorisi P (Polynomial, Polinom süreli veya büyüklüklü) olarak anılan problem sınıfında K ve r birer katsayı olmak üzere aşağıda gösterilen eşitsizlik geçerlidir. N ≤ K . nr n’ in her bir kuvveti (n1, n2, n3, n4 ) n’ in polinom büyüklükleri olarak adlandırılır. P sınıfı problemlerde hiçbir zaman N, n’ nin herhangi bir polinom büyüklüğünün K katından daha büyük olamaz. Özetle P sınıfı problemlerde n’ i N’ e bağlayan fonksiyon sadece sabit katsayılı polinom büyüklüklü bir fonksiyondur. Polinom büyüklüklü algoritmalarda, n ile N arasında logn, n, nlogn, n2, n3 biçiminde tanımlanan fonksiyonel bağıntılar vardır. Bu bağıntılar arasında işlem karmaşıklığı O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) olarak sıralanır. 52 Karmaşıklık Teorisi NP (Non Deterministic Polinomial), belirleyici olmayan polinom büyüklüklü anlamında başka bir problem sınıfıdır. NP sınıfına giren problemlerin bir kısmı deterministik metotlarla çözülemezken, deterministik olmayan (stokastik) metotlarla polinom büyüklüklü zaman aralığında çözülebilmektedir. Bu tür problemlere NPzor (NP-hard) problem denmektedir. Diğer taraftan bir kısım NP problemler stokastik metotlarla dahi çözülememektedir. Bu tür problemler bilinen en karmaşık tür problemlerdir ve NP-tam (NP-complete) olarak adlandırılır. 53 Karmaşıklık Teorisi, Gezgin Satıcı Problemi Bir TSP probleminde n adet şehir için, deterministik bir algoritma (n-1)!/2 farklı çözümü dener ve en kısa tur mesafesini belirleyebilir. Böyle bir algoritma gerçek hayatta kullanılacak kadar büyük n değerleri için pratikte çözüm bulamaz. Dolayısıyla bu problem P sınıfına girmez, NP sınıfındadır. Stokastik bir yöntem için “B” den daha kısa tur var mı? Sorusunun bulunması durumunda, algoritma araştırma yapar ve daha kısa bir tur bulur ise “evet” cevabını verir. Bu durumda problem NP sınıfına girer. Eğer, “B” den daha kısa tur var mı? Sorusuna kesin olarak “Hayır” cevabının olup olmadığı araştırılırsa, problem çok daha zorlaşır ve NP-complete sınıfına girer. Bu durumda tüm ihtimalleri denemek gerekir ve sezgisel algoritmalardan daha fazlası gerekir! 54 Optimizasyon Optimizasyon işleminin aşamaları genel olarak şöyle sıralanabilir: Parametreler setinin tanımlanması Parametrelere bağlı olarak amaç fonksiyonun tanımlanması (minimizasyon, maksimizasyon) Problem sınırlamalarının tanımlanması (constraints) Amaç fonksiyon, daha uygun parametre değerleri ile değerlendirildiğinde amaca daha uygun değerler üreten bir fonksiyondur. Sınırlamalar ise, parametrelerin yada fonksiyonun alamayacağı değerleri tanımlar. Sınırlamalar eşitlikler yada eşitsizlik ifadeleri ile tanımlanabilir. 55 Amaç Fonksiyonu ve Sınırlamalar Örnek Sayısal filtre tasarımında kararlılık çok önemli bir kavramdır. Kararlı olmayan sayısal filtrenin pratikte kullanılma imkanı yoktur. Bu nedenle tasarlanan tüm sayısal filtreler kararlı olmak zorundadır. İkinci dereceden bir sayısal filtrenin transfer fonksiyonu aşağıdaki gibi verilmiş olsun; H z 1 1 b1 z 1 b2 z 2 Bu filtrenin kararlı olabilmesi için kutupların birim çember içerisinde olması gerekir. Buna göre kararlılık kriterleri aşağıdaki gibi belirlenir: b2 1 b2 1 b1 56 Amaç Fonksiyonu Üzerine Pratik Bilgiler Kullanılan optimizasyon algoritmasının yapısı gereği optimize edilmek istenen amaç fonksiyonunun algoritma içerisinde minimizasyon yada maksimizasyon problemi olarak tanımlanması gerekebilir. f değeri minimize edilmek istenen amaç fonksiyonu olmak üzere, f değişik yaklaşımlarla maksimizasyon problemi olarak da tanımlanabilir. Örnek a) fmin=0 ise, g 1 f f=0.01 ise g→100 f=1x10-4 ise g→10000 b) fmin=0 ise, g 1 0.1 f Burada f ’ in değeri 0’ a yaklaştıkça g’ nin değeri 10’a yakınsar. İfadenin paydasında 0.1 yerine farklı değerler kullanılarak fonksiyonun değerinin farklı bir sınıra yakınsaması sağlanabilir. 57 Amaç Fonksiyonu Üzerine Pratik Bilgiler Önceki durumun aksine, f değeri maksimize edilmek istenen amaç fonksiyonu olmak üzere, f değişik yaklaşımlarla minimizasyon problemi olarak da tanımlanabilir. Örnek a) fmax=30 ise, g 30 f f=8 ise g→22 f=17 ise g→13 f=26 ise g→4 58 Çok Amaçlı Optimizasyon Problemi Birden çok minimize/maksimize edilecek fonksiyon içeren problem çok amaçlı optimizasyon problemi olarak tanımlanır. Gerçek optimizasyon problemlerinin çoğunluğu birden çok amaç fonksiyonu içerir. Bir köprü tasarımında düşük kütle, yüksek dayanım istenir. Otomobil için sunroof tasarımında sürücüye gelen gürültünün minimize edilmesi istenirken, hava sirkülasyonunun maksimize edilmesi amaçlanır. Lineer bir amplifikatör tasarımında kazanç maksimize edilmeye çalışılırken, distorsiyonun minimize edilmesi istenir. Yukarıda verilen örneklerde maksimize ve minimize edilmek istenen iki amaç değeri bulunmaktadır. Problemler bu türde olabileceği gibi, tüm amaç fonksiyonları maksimizasyon yada minimizasyon problemi olan problemlerde vardır. 59 Pratik Bilgiler Çok amaçlı problemlerde hedef tüm amaçlarda optimum sonuca ulaşmaktır. Basit problemlerin optimizasyonunda her bir amaç için benzer kalitede çözümler sağlamak mümkün olabilir. Örneğin iki amaç fonksiyonu bulunan bir optimizasyon probleminin herhangi bir optimizasyon algoritması ile çözümünde birinci amaca %1 hata ile ulaşılırken ikinci amaca %1.2 hata ile yaklaşılabilir. Ancak, zor problemlerin farklı amaçların bir arada optimizasyonunda, amaçların başarım oranları arasında ciddi farklılıklar bulunabilir. Örneğin herhangi bir amaç %0.5 hata ile sağlanırken, diğer bir amaç %18 hata ile sağlanabilir. Bu tür problemlerde optimizasyonun ne oranda başarılı olduğu, amaçlar için kabul edilebilir hata toleranslarına bağlıdır. Bu nedenle bir çok problemde, problemin yapısına bağlı olarak her bir amaç için kabul edilebilir toleranslar optimizasyon işleminin başlangıcında belirlenmelidir. 60 Pratik Bilgiler Minimize edilmek istenen iki farklı amaç fonksiyonu içeren bir problemde, her bir amaç fonksiyonunun minimum değerleri birbirinden çok farklı olabilir. Örneğin bir amacın minimum değeri 0 iken diğerininki 10 olabilir. Farklı minimumları olan amaç fonksiyonları araştırma esnasında algoritmanın ilerleyiş yönünü farklı oranlarda etkileyebilir. Yani amaç fonksiyonlardan birisi algoritmanın araştırma davranışında baskın durumda olabilir. Bu durumda algoritma çoğunlukla amaç fonksiyonlarından biri için optimal olan bölgeye yakınsayacak ve algoritmanın başarımı düşürecektir. Böyle durumlarda problemin karakteristiğini iyi bilmek ve gerekirse, farklı amaçların tanımlandığı amaç fonksiyonunda her bir amacın tanımlanmasında farklı yaklaşımlar göstermek gerekebilir. 61 Pratik Bilgiler Örnek: f1 ve f2 gibi iki amaç değeri olan bir f fonksiyonunun aşağıdaki gibi tanımlandığını düşünelim: f= f1 + f2 fmin =6.3487 Her bir amaç fonksiyon için minimum değerler, f1min=0.3487 ve f2min=6.0 olsun. Bu problemde gerekli görülmesi halinde düşük değerli amaç fonksiyona ait değerler belirli bir katsayı ile çarpılarak diğer amaç fonksiyonu değerine yakın düzeylere çıkartılabilir. Yada tersi olarak yüksek değerli amaç fonksiyonuna ait değerler belirli bir katsayıya bölünerek, küçük değerli amaç fonksiyona yakın düzeylere düşürülmesi olumlu sonuçlar verebilecektir. 62 Pratik Bilgiler Çok amaçlı optimizasyon problemlerinde, araştırmacı farklı amaç fonksiyonları için farklı öncelikler de tanımlayabilir. Yani farklı amaçlar için kabul edilebilir toleranslar farklı uygulanabilir. Örnek: Bir analog filtre tasarımında kesim frekansı (f) ve kalite faktörü (Q) olmak üzere optimize edilmek istenen iki parametre bulunduğunu düşünelim. Tasarımcı önceden belirlenen f ve Q değerlerini sağlayacak şekilde, devredeki çeşitli sayıdaki pasif elemanlar için en uygun değerler setini bulmaya çalışacaktır. C1 R4 R3 - R5 + giriş + R1 H C2 R6 R 1 ω 0 4 R 3 C1C 2 R 5 R 6 + çıkış Q R2 R 2 R 3 R 4 R 3 R 1 R 2 R 3 R 1 R 2 C1 R 4 R 5 R 1 R 3 R 4 C 2 R 3 R 6 63 Pratik Bilgiler Örnek devam… Problemin çözümü aşamasında, kullanılan algoritma öncelikle bir aday değerler seti üretir. Üretilen bu değerler setinin amaca ne kadar uygun olduğu ise, bu değerler kullanılarak hesaplanacak f ve Q değerlerine bağlı olarak belirlenir. Doğal olarak, araştırmanın başlangıcında, mevcut değerler seti ile sağlanan f ve Q değerleri ile olması gereken değerler arasında sırasıyla ∆f ve ∆Q ile temsil edilebilecek sapmalar bulunur. Bu problemde amaç bahsedilen sapmaların mümkün olduğunca küçük olmasıdır. Bu sapmalara bağlı olarak amaç fonksiyon bir minimizasyon problemi olarak aşağıdaki şekilde tanımlanabilir: 64 Pratik Bilgiler Örnek devam… g f f Q Q Yukarıda tanımlanan amaç fonksiyonunda hem kesim frekansı f hem de kalite faktörü Q aynı oranda ağırlığa sahiptir. Yani her iki büyüklükte aynı oranda önemsenmiştir. Eğer, araştırmacı bu büyüklüklerden birisini daha çok önemsiyor ve diğer büyüklükle ilgili olarak daha toleranslı davranılabileceğini düşünüyorsa, bu durumda amaç fonksiyonunu aşağıdaki şekilde tanımlamak ta mümkün olabilecektir. g a1 f f a2 Q Q Burada a1 ve a2 birer sabittir. Örnek olarak, her bir sabit için 0.5 değeri kullanılırsa amaç fonksiyonların problemdeki ağırlıkları aynı oranda olacaktır. Eğer kullanıcı kesim frekansını daha önemli buluyor ise bu durumda sabitler için sırasıyla 0.6 ve 0.4 değerlerini tercih edebilecektir. 65 Uygun Çözüm Bölgesi (Feasible Region) Problemde sınırlamaları sağlayan tüm çözümleri içeren bölge kabul edilir bölge veya uygulanabilir bölge (feasible region) olarak tanımlanır. 66 Grafik Teorisi Birçok problemde, durum uzayının veya çözüm ağacının gösterilmesinde graf yapıları kullanılmaktadır. Graf, bir noktalar kümesi ile (düğümler) bu noktalar arasındaki ilişkileri ifade eden kenarlar yardımıyla tanımlanan bir yapıdır. Her kenar iki düğümü birleştirmektedir. Grafın kenarlarının bir başlangıcı ve bir sonu varsa, bu graf yönlü olarak tanımlanır. Aksi halde, yönsüz olarak adlandırılır. Yönsüz graflarda kenarlar bağ olarak adlandırılmaktadır. Örneğin bir dağıtım probleminde düğümler depoları yada üretim merkezlerini, kenarlar ise bu merkezler arasındaki yolu veya mesafeyi temsil eder. 67 Grafik Teorisi Grafik teorisi ilişkilerin teorisidir. Bir G grafiği n adet noktadan oluşur. Noktalar Vi (i=1,2,…,n) ile; Vi-Vj noktalarını birleştiren çizgi eij ile gösterilir. eij bağıntısı ile birleştirilen Vi ve Vj noktaları komşu noktalar olarak tarif edilir. Noktaların veya bağlantıların sıralanmasından oluşan küme yol (path) olarak tanımlanır. Başladığı noktada biten yola (Vi=Vj) tur denir. 68 Grafik Teorisi 69 Grafik Teorisi Graf teorisi bunama hastalarında sinir bağlantılarını haritalamaya yardım eder. 70 Grafik Teorisi Kansas Üniversitesinden bir araştırmacı graf teorisini, insan beyninde kelimelerin nasıl depolandığını ortaya koymak için kullandı. 71 Grafik Teorisi 72 Zor Problemler Bir optimizasyon problemi muhtemel farklı çözümleri var olan ve çözümlerin kalitesi hakkında açıkça fikir sahibi olunabilecek basit bir yapıda olabilir. Böyle bir problemin farklı aday çözümleri var olduğunda, bunlar anlamlı bir şekilde ayrıştırılabilir ve karşılaştırılabilir. Bununla beraber, bir çok optimizasyon problemi esas itibariyle zordur. Endüstri veya bilimle ilgili problemler ve bir çok gerçek problemde tipik senaryo problemin zor olmasıdır. Örneğin bir haberleşme ağının tasarımında mümkün olan birçok yol vardır. Bunlardan hangisi en güvenilirdir? Bir fabrika üretim planlamasında mümkün olan birçok yol vardır. Bunlardan hangisi en yüksek işlem hacmini sağlar? 73 Zor Problemler Mühendislikte Karşılaşılan Bazı Optimizasyon Problemleri: Tasarım maliyetlerinin minimizasyonu Kayıpların minimizasyonu Maksimum taşıma kapasitesi için optimum yerleşim Minimum ağırlık ve maksimum mukavemet için uçak/köprü tasarımı En az maliyetle malzeme kesme stratejisi Makinelerin gücünün maksimuma çıkarılması, ısı üretiminin minimize edilmesi Sistemlerin bekleme ve boşta durma sürelerini minimize etmek Hava yolu şirketleri için uçuş maliyetlerini minimize etmek Satış elemanının ziyaret edeceği şehirler arasındaki en kısa yolun bulunması … 74 Zor Problemler Algoritmalar, problemleri çözmek için kullanılan yöntemlerdir. Örnekler: 1) Basit bir denklem, 2) Metal bir paranın iki kez atılmasında olası durumlar 2x=4 x=2 Y Y Y T T Y T T Optimizasyon, kabul edilebilir bir zaman içerisinde, problemin mümkün olan en iyi çözümünü bulmaya çalışma sürecidir. Muhtemel çözümler?, En iyi çözüm her zaman bulunabilir mi? Kabul edilebilir süre? 75 Zor Problemler Patolojik görüntülerdeki çok sayıda hücre hata yapmadan değerlendirilebilir mi? 76 Zor Problemler Zor problemin kabul edilebilir bir zaman diliminde en iyi çözümünün bulunması garanti edilemez. Temelde, endüstri ve bilimle ilgili bir çok problem zordur. Çözüm: Yapay zeka yöntemleri. 77 Yapay Zeka (Artificial Intelligence) İnsan ve doğadaki zeki davranışların programlamayla taklit edilerek problemlerin çözümünde kullanılmasıyla ilgili bilim dalıdır. Zeka gerektiren işlemlerin bilgisayarlar tarafından yapılmasını sağlamaya yönelik yöntemlerin geliştirilmesiyle ilgili bilim dalıdır. Bilgisayarların, algılama, görme, karar verme ve bilgi çıkarma gibi insan zekasına özgü yeteneklerle donatılması ve geliştirilmesi bilimi. … Zeka Nedir? 78 Zeka Nedir? Zekanın açık ve somut bir tanımı yoktur. Zeka, bireysel bilgi birikimi ve deneyimlerle ilişkilidir. Akıl yürütme Hüküm verme Kendisini iyileştirme kapasitesi Soyut düşünebilme süreci Algılama, sorgulama, yaratıcılık Gayeli davranma Mantıklı düşünme Yeni durumlara uyabilme yeteneği Öğrenme Problem çözme Yeni ürünler ortaya çıkarabilme İletişim kurabilme kapasitesi … 79 Zeka Nedir? Bir çok felsefeci ve psikolog zeka için farklı tanımlar yapmışlardır: Zeka, insanın sahip olduğu dikkat, bellek, yargılama, akıl yürütme, soyutlama gibi yetiler topluluğudur (Binet). Zeka, bireyin amaçlı bir biçimde hareket edebilme, mantıklı düşünebilme ve çevresine uyum gösterme yetilerinin tamamıdır (Wechsler). Zeka, bir amacın gerçekleştirilebilmesi için araçların duruma uygun kılınmasıdır (Oleron). Zeka, yeni duruma hızlı biçimde ayak uydurmak, uyum sağlamaktır. 80 Zeka Nedir? Prof.Howard Gardner, çoklu zeka kavramını ileri sürmüştür. Ona göre farklı zeka türleri vardır: Dilsel Zeka: konuşma ve yazma dilinde sözcükleri etkili kullanma yeteneğidir (Politikacılar, yazarlar), Sosyal Zeka: diğerlerinin duygularını, ruh hallerini anlama yeteneğidir (politik liderler, danışmanlar), Mantık-Matematik Zeka: Sebep-sonuç ilişkisi kurabilme, sayı ve numaraları akıllıca kullanabilme yeteneğidir (bilim adamları, matematikçiler, programcılar), Görsel Zeka: Nesneleri hayalinde canlandırma ve görme yeteneğidir (ressam, mimar), Müzik Zekası: müzisyenler Dışa dönük (bedensel) zeka: atletler, aktörler, dansçılar, heykeltıraşlar, İçedönük zeka: psikologlar, psikoterapistler, Doğal zeka: çevreciler v.b. Çoklu zeka teorisine göre, herkesin zeki olabilme ihtimali yüksektir. Önemli olan ise, hangi zeka türünden söz edildiğidir. 81 Hayvanlar Zeki midir? Psikologlar, genellikle iki zeka türünü karşılaştırmaya yönelik deneyler yapmaktadırlar: Nesnel Zeka : somut, deneysel ve pratik etmenleri olan zeka, Soyut Zeka : kuramsal ve sistematik olan zeka, (insana özgüdür ve hayvanlarda olmadığı düşünülmektedir) Hayvanlar zeki mi? İkilem (dilemma): Matadorun ölümcül darbeleri karşısında boğanın olayı anlamadan kırmızı kumaşa saldırması ! Hayvanların yaptığı yuvalar, aletler, tuzaklar, örümcek ağları, arı peteği, savunma şekilleri ! 1973 yılında biyolog Karl von Frish arıların dans dilini keşfettiği için, Nobel ödülü aldı. Yeni besin kaynağı bulmakta uzmanlaşmış bir arının, kovana döndüğünde, kovanın önünde özel bir dans yaparak, yiyecek kaynağının yerini diğer arılara bildirmektedir. 82 Hayvanlar Zeki midir? Dansın hızı, dikeyle yaptığı açı, yassı sekiz şekli gibi parametrelerle doğrultu ve mesafe bilgisi verilmektedir. 83 Hayvanlar Zeki midir? Petek yapısı çember, üçgen yada beşgen olsaydı, aralarında daha büyük boşluk oluşacaktır. Minimum malzeme ile daha çok bal depolanmaktadır. Çok mantıklı, ancak arıların gerçekten zeki olduğu söylenemez. Benzeri işlemleri dünyanın her yerindeki arılar yapmaktadır. Bu hareketler içgüdüsel olarak yapılmaktadır. Zekadan söz edebilmek için, geliştirilen uygulamanın bütün soya özgü kalıtımsal bir mekanizmanın basit bir uygulaması değil, yeni olması, bireye yada bir guruba mal edilebilecek bir buluştan kaynaklanması gerekir. Prof.Dr.Adem KALINLI 84 Basit Bir Problem: Su İçmek 1. Su gereksinimi olduğunun farkına varması, 2. Su bardağını ve içindeki suyu tanıması, 3. Bulunduğu sosyal koşullar içinde, suyu içmesinin normal bir davranış olduğuna karar vermesi, 4. Eli su bardağına uzanırken, bardakla eli arasında sürekli olarak kısalan mesafeyi, geri besleme sürecinden yararlanarak doğru algılaması ve bardağı yakalayabilmesi, 5. Bardağı yakalayan elin, bardağı belirli bir kuvvet derecesinde kavrayabilmesi (çok sıkarsa bardak kırılır; az sıkarsa bardak düşer), 6. Elin kavradığı bardağın, ağıza uygun hızla gerekli mesafeye getirilmesi (yine geri besleme sürecinden faydalanılarak), 7. Ağzın açılışı ile bardağın dudaklara dokunuşu arasında koordinasyonun sağlanması, 8. Yutkunma davranışının hızı ile ağıza giren suyun miktarı arasında dengenin oluşturulması, 9. Yutkunma davranışı ile nefes alma davranışı arasında koordinasyonun sağlanması, 10. Ağıza girmesi istenen su miktarı ile bardağın ağızla oluşturduğu açı arasında ve bunlara benzer yüzlerce davranışsal ve algısal süreç arasında dengeleme ve koordinasyon gerekir Prof.Dr.Adem KALINLI 85 Kuvvetli ve Zayıf YZ Yaklaşımı Kuvvetli Yapay Zeka Yaklaşımı: Eğer insanın düşünme mekanizması keşfedilirse bu işlem makinelere de uyarlanabilir. Bu şekilde makineler de insanlar gibi düşünebilir. Makineler gerekli teknolojik ilerleme sağlandıktan sonra insan zekasına, duygularına sahip olabilirler. Zayıf Yapay Zeka Yaklaşımı: Makinelere düşünmeyi öğretmek mümkün değildir. Dolayısıyla makinelerin insan gibi karar vermesi, duygulara sahip olması beklenemez. Makineleri zeki yapabiliriz, bunun için insan beynini, düşünce yapısını temel almamıza gerek yok. Her iki yaklaşımı da benimseyen araştırmacılar vardır. Günümüz teknolojisi kuvvetli yapay zekanın uygulanabilmesi için çok yetersizdir, en azından 50 yıl sonra mümkün olabileceği öngörülmektedir Gerçekleştirilen YZ uygulamalarının hepsi zayıf YZ’yı kullanmaktadır. Prof.Dr.Adem KALINLI 86 Başarılı Bazı YZ Uygulamaları IBM Deep Blue 1997’de dünya satranç şampiyonu Gary Kasparov’u yendi. 2007’de bütün dama hamlelerini oyunun sonuna kadar kontrol edebilecek bir YZ modeli geliştirildi. 1996’da 60 yıldır kanıtlanamayan Robbins varsayımı (Robbins conjecture) YZ ile bilgisayar tarafından kanıtlandı. Pittsburg’dan San Diego’ya yolun %98’ini kendi başına kullanan araba başarıyla test edildi. 1991 Körfez savaşı esnasında Amerikan ordusu taşıyıcı, kargo ve insandan oluşan 50,000 birimlik kuvvetin lojistik plan ve işbölümünü YZ ile gerçekleştirdi. NASA uzay araçlarındaki makine ve insanların operasyonlarının işbölümünü YZ sayesinde planlamaya başladı. Proverb adlı YZ programı kare bulmacaları çoğu insandan daha iyi çözer duruma geldi. Prof.Dr.Adem KALINLI 87 Başarılı Bazı YZ Uygulamaları Sony Aibo- Sahibinin sesini ve yüzünü tanıyan, ismini öğrenen ve oyun oynayan robot köpek Hastanelerde ilaç ve malzeme taşıyan otomatik araçlar Hewlett Packard Smart Drug Delivery-Deriye yapıştırılan ve zamanı gelince vücuda ilaç salgılayan bandajlar Prof.Dr.Adem KALINLI 88 Başarılı Bazı YZ Uygulamaları BMW 7 Hız Sınırı Göstergesi-Kameralarla yoldaki hız sınırı tabelalarının fotoğrafını çekip uymanız gereken azami hızı gösteren yazılım. Salvador DaBot: Konuşabilen ve resim yapabilen bir robot Prof.Dr.Adem KALINLI Biyonik Kol 89 Sibernetik İnsanlar ve hayvanlar arasında iletişim ve kontrol bilimi olarak Norbert Wiener tarafından 1948 yılında önerilmiştir. Özetle, sibernetik canlı organizmaların taklidi ve sentezidir. Sibernetik ve YZ arasındaki benzerlikler bilim adamları arasında tartışma konusu olmuştur. YZ, sibernetik kavramına göre daha geniş bir alanı kapsar. Prof.Dr.Adem KALINLI 90 Yapay Zeka (Artificial Intelligence) Yapay Zeka, bilgisayarların, algılama, görme, karar verme ve bilgi çıkarma gibi insan zekasına özgü yeteneklerle donatılması ve geliştirilmesi bilimi. Zeki programlama, insan zekasının ve doğadaki davranışların makinelerle simülasyonu işlemi olarak tanımlanabilir. Zeki Programlama, Yapay Zekanın zeki davranışın otomasyonu ile ilgilenen bir koludur. Zeki araştırma ise, problem uzayını sistematik olarak araştıran bir problem çözme tekniğidir. Prof.Dr.Adem KALINLI 91 Yapay Zeka (Artificial Intelligence) Bir programın yada sistemin zeki olarak nitelendirilebilmesi için en azından aşağıdaki özelliklerden bazılarını ihtiva etmesi gerekir: Zeki Programlamanın Karakteristiği: Bilgi temsili yeteneği (sembolik), Sezgisel muhakeme yeteneği, Tamamlanmamış, kusurlu veya karmaşık bilgi ile başa çıkabilmesi, Öğrenme yeteneği, Algılama, şekil yada resim tanıma, … Prof.Dr.Adem KALINLI 92 Yapay Zeka Sistemlerinin Avantajları Öğrenme kabiliyeti Genelleme yapabilme Adaptasyon kabiliyeti Sonuç çıkarma özelliği Lineer olmayan kompleks ilişkileri kurabilme Gürültüye karşı toleransı Tamamlanmamış, eksik bilgi ile başa çıkabilme Farklı tekniklerle entegrasyon kabiliyetleri Rastgele çözümlerden sonuca ulaşabilmeleri Matematiksel olarak ifade edilmesi zor veya imkansız sistemleri modelleyebilmeleri … Prof.Dr.Adem KALINLI 93 Yapay Zekanın Tarihçesi 1943 McCulloch & Pitts: Beynin Boole cebiri ile modellenmesi 1950 Turing Testi 1956 Dartmouth toplantısı: “Yapay Zeka“ terimi kabul edildi. 1952-69 Büyük beklentilerin oluştuğu zamanlar 1950’ler İlk YZ programları, Lisp, Samuel‘in dama programı, vs. 1965 Robinson‘un mantıksal sonuç çıkarma algoritması 1966-73 Yapay Zekanın öngörülenden zor olduğu fark ediliyor. Yapay sinir ağları çalışmalarından vazgeçiliyor. 1969-79 İlk bilgi-tabanlı sistemlerin geliştirilmesi 1980- Yapay Zeka bir endüstri haline geliyor. 1986- Yapay sinir ağları çalışmaları tekrar gündeme geliyor. 1987- Yapay Zeka bir bilim dalı olarak ortaya çıkıyor. 1995-- Akıllı sistem uygulamaları oluşturulmaya başlanıyor. 2000’ler YZ kullanan robotlar ve makineler günlük hayata giriyor. Prof.Dr.Adem KALINLI 94 Yapay Zekanın Diğer Alanlarla İlişkisi Problem Çözümleme: Kompleks, özellikle kombinasyonel problemler Prof.Dr.Adem KALINLI 95 Yapay Zeka Problemleri Problem Çözümleme: Kompleks, özellikle kombinasyonel problemler Oyunların modellenmesi: go, dama, satranç vs, Bilgilerin Modellenmesi: YSA, FL, anlamsal ağlar, simülasyon, arıza tespiti Otomatik teorem ispatı: Matematik ve mantıkla ilişkili olarak önermelerin ispatı ve yenilerinin bulunması, Doğal dil işleme: soru-cevap diyalog, cümle analizi, otomatik çeviri sistemleri Örüntü Tanıma: Görsel ve işitsel nesnelerin tanınması, el yazısı veya karakter tanıma, tıbbi görüntünün biometrik özelliklerinin tanınması, yüz tanıma, dudak okuma vs. Robotik: Zeki bilgilerle donatılmış, eğitilmiş sistemler … 96 G.W.Leibniz (Matematikçi, 1646-1716) “Özel buluşlara çok değer vermiyorum. En çok arzu ettiğim şey, icat etme sanatını mükemmelleştirmek ve problemlerin çözümünü bulmaktan ziyade, çözüm yöntemlerini bulmaktır. Çünkü, tek bir yöntem, sayısız çözümleri kapsar.... ” Prof.Dr.Adem KALINLI 97 Problem Çözümleme Problem Formülasyonu (Tanımı) Problemin net bir şekilde tanımlanması, Problemin bir çözümünü bulmayı denemek ve problemin üstesinden gelmek için bir stratejinin belirlenmesi. Prof.Dr.Adem KALINLI 98 Problem Çözümleme Bir problemi formüle etmek için aşağıdaki tanımlardan yararlanabiliriz: Başlangıç Durumu (Initial States) Operatörler (Operators) Komşuluk (Ardıl, Halef Fonksiyonu) Durum Uzayı (State Space) Hedef Testi (Goal Test) Yol Maliyeti (Path Cost) Prof.Dr.Adem KALINLI 99 Problem Çözümleme Başlangıç Durumu (Initial States): Problem tanımlarının başlangıç durumu, araştırmaya başladığımız pozisyonu ifade eder. Sezgisel algoritmalarda başlangıç çözümleri büyük çoğunlukla rasgele olarak oluşturulmaktadır. Bununla beraber, araştırmacılar başlangıç çözümlerini atayarak araştırmanın belirli bir noktadan başlamasını da sağlayabilir. Örneğin satrançta taşların başlangıçta belirli bir pozisyonda bulunmaları gibi. Çözümlerin belirli bir başlangıç değerinden veya rastgele başlaması problemin özelliğine göre belirlenmelidir. Örneğin problemin bir yerel optimal değerini sağlayan parametre değerleri biliniyor ise, algoritmanın bu noktadan veya yakınında bir noktadan araştırmaya başlayarak bir yerel optimum çözümden kurtulma başarımı incelenmek istenebilir. Prof.Dr.Adem KALINLI 100 Problem Çözümleme Operatörler (Operators): Bir durumdan diğer bir duruma geçmek için izinli değişimlere operatör denir. Belirli bir zamanda, mümkün olan (olası) etkileri uygulamanın bir setini tanımlar. Satranç oyununun başlangıcında operatör, piyonlar veya atların hareketine izin verecektir. Prof.Dr.Adem KALINLI 101 Problem Çözümleme Komşuluk (Ardıl, Halef Fonksiyonu): Bulunulan bir noktadan hareket edilebilecek noktaların seti komşuluk olarak adlandırılır. Farklı algoritmalar komşuluk oluşturma işleminde çeşitli stratejiler kullanmaktadır. Örneğin bilginin ikili (binary) sayılarla temsil edildiği algoritmalarda komşu çözümler çoğunlukla bit değerlerinin değiştirilmesiyle elde edilmektedir. Reel sayılarla bilgi temsili gerçekleştirilen algoritmalarda ise mevcut değerlere belirli sabit adım miktarlarında rastgele ekleme veya çıkarmalarla komşuluklar oluşturulabilmektedir. Yine reel sayılarla bilgi gösteriminde sayı değerinin belirli bir yüzdesi oranında artırma veya eksiltme ile komşuluk oluşturmak da mümkündür. Bu uygulamalara ek olarak literatürde farklı komşuluk oluşturma mekanizmaları da mevcuttur. Prof.Dr.Adem KALINLI 102 Problem Çözümleme Durum Uzayı (State Space) : Başlangıç durumu ve operatörler problemin durum uzayını tanımlar. Durum uzayı, başlangıç durumundan erişilebilir tüm durumların setidir. Bir problemin tüm izinli durumlarını içeren graftır. Bir problemin çözümü aranırken, durum uzayının sınırları kesin bir biçimde belirlenmelidir. Satranç oyununda durum uzayı, başlangıç noktasından itibaren, tahta üzerindeki geçerli tüm hareketleri kapsar. Prof.Dr.Adem KALINLI 103 Problem Çözümleme Hedef Testi (Goal Test) : Problem çözüldüğünde bu durum bilinmelidir. Bir hedef test, mevcut duruma uygulandığında, mevcut durumun hedeflenen durum olup olmadığını bildirir. Bu, mevcut bir tahta dizilim konfigürasyonunda 8’li puzzle da olduğu gibi açık/yalın bir biçimde olabilir. Hedef test, bazen çok soyut olabilir. Örneğin, satrançta şah-mat için gerekli olası tüm konfigürasyonları listeleyemeyiz. Bu yüzden, hedef test rakibin ne yapacağını önemsemeden şahın alınıp alınamayacağını kontrol etmek kadar basitleşebilecektir. Prof.Dr.Adem KALINLI 104 Problem Çözümleme Yol Maliyeti (Path Cost) : Bazı durumlarda yalnızca çözümün bulunması değil, çözümün maliyeti de önemli olur. Bu kavram, yol maliyeti olarak tanımlanır. Örneğin 8’li puzzle da maliyet basitçe hareketlerin sayıdır. Bazı problemlerde her bir hareketin önemli bir maliyeti olabilir. Satranç gibi problemlerde ise maliyete bakılmaksızın, kazanmaya odaklanılır. 105 Problem Çözümleme Durumlar (States) Parçaların düzenlenmesi Araçların pozisyonu Şehirlerin sıraya dizilmesi… Operatörler (Operators) İki parçayı birleştir Bir aracı yeni bir pozisyona taşı Yeni bir şehre git… Hedef Testi (Goal Test), Başarı Ölçütü Tüm parçalar yerleşti Tüm paketler ulaştırıldı Hedef şehre varıldı… Prof.Dr.Adem KALINLI 106 Problem Çözümleme, Örnek Problem Tanımı (8 Taş Problemi): Verilen başlangıç durumundan hedefe ulaşmak için boşluğun yapması gereken en kısa hareket dizisi nedir? Operatör kullanımına örnek 5 6 7 1 8 3 4 1 4 2 5 2 7 8 Başlangıç Durumu 3 6 Hedef Durum Durumlar: Boşluk ve işgal edilenlerde dahil olmak üzere, yerleşimlerdeki 8 taşın her birinin tanımı, Operatör: Boşluk, sağa, sola, yukarı veya aşağı hareket eder, Hedef Testi: Mevcut durumu, belirli bir hedef durum ile eşleştirilir, Yol Maliyeti: Boşluğun her bir hareketinin maliyeti 1 dir. Prof.Dr.Adem KALINLI 107 Problem Çözümleme, Örnek Problem Tanımı (Kurt-Kuzu-Lahana): Çiftçi, yalnızca iki nesne alabilen bir kayık ile kurt, kuzu ve lahanayı karşı kıyıya geçirmek istiyor? Çiftçi yanlarında iken kuzu lahanayı, kurt kuzuyu yiyemiyor. Durum uzayının araştırılmasına örnek Ç B L K W A İfade Edilmesi Gerekenler: 4 Nesnenin Pozisyonu, Nesneler (A) yada (B) de. Her nesneyi poziyonunu ifade eden bir harf ile gösterelim: (Çiftçi, Kurt, Keçi, Lahana), (Ç,W,K,L) Başlangıç Durum : (A, A, A, A) Yasaklı Durumlar: Kurt keçiyi yer (Çiftçi olay yerinde değilse) (B, A, A, _) (A, B, B, _) Keçi lahanayı yer (Çiftçi olay yerinde değilse) (B, _, A, A) (A, _, B, B) Hedef Durum: (B, B, B, B) Prof.Dr.Adem KALINLI 108 Problem Çözümleme, Örnek Her bir nesne iki yerde olabildiğine göre 24 = 16 durum (state) vardır: 1-Başlangıç, 16- hedef durum 1. ÇLKW/Ø 2. ÇLK/W 10.LW/ÇK 3. ÇLW/K 11.KW/ÇL 4.ÇKW/L 12.Ç/LKW 5.LKW/Ç 13.L/ÇKW 6.ÇL/KW 14.K/ÇLW 7.ÇK/LW 15.W/ÇLK 8.ÇW/LK 16. Ø/ÇLKW Problemin 2 farklı çözümü: 110 3 13 2 14 7 16 110 3 15 4 14 7 16 Prof.Dr.Adem KALINLI 9.LK/ÇW 109 Problem Çözümleme, Örnek Problem Tanımı (Hanoi Kulesi Problemi): Birinci çubuğa takılı üç diskin, her adımda yalnızca bir disk taşınarak ve büyük disk küçüğün üzerine yerleştirilmeden diğer çubuğa taşınması. Prof.Dr.Adem KALINLI 110 Prof.Dr.Adem KALINLI Prof.Dr.Adem KALINLI Prof.Dr.Adem KALINLI Prof.Dr.Adem KALINLI Doç.Dr.Adem KALINLI Prof.Dr.Adem Problemin alt problemlere bölünerek çözülmesine örnek Prof.Dr.Adem KALINLI Hanoi Kulesi Hanoi kulesi problemini çözen bir algoritma yazabilir misiniz? Basit bir örnek: (çubukların bir çember olarak düzenlendiği kabul edilerek) Do 1.2 yapılamayana kadar 1.1. En küçük halkayı saat yönünde bir sonra duran çubuğa taşı, 1.2. Yalnızca geçerli (legal) hareketi yap (en küçük halka ile ilişkili olmayan) Stop Prof.Dr.Adem KALINLI 119 Hanoi Kulesi 3 halka için 7 hareket gerçekleştirildi. 4 Halka için kaç hareket gerçekleştirilmesi gerekir? Problemin hareketlerin alt sınırı 2N-1 dir. Çubuklar 2N-1 3 7 4 15 5 31 6 63 … 10 1023 n adet disk ve m adet çubuk için toplam durum sayısı mn dır. Prof.Dr.Adem KALINLI 120 Hanoi Kulesi Problemin orijinali Tibet’teki bir gurup rahibin pırlanta çubuklar üzerindeki 64 altın halkayı taşıma girişimlerine aittir. Onlar, bu işlem bittiğinde dünyanın da son bulacağına inanmaktadırlar !! Her sn de bir halka taşınırsa (daha gerçekçi bir yaklaşım 5 sn de bir), dünyanın sonuna ne kadar süre vardır? 500.000 yıl !! (veya 3 trilyon yıl) sn de 1.000.000 komut işleyen bir bilgisayarda gerekli süreler: 10 2N NN 20 50 1/1000 sn 1 sn 35.7 yıl 2.8 saat 3.3 trilyon yıl Prof.Dr.Adem KALINLI 70 digit sayı değerinde yy 100 200 > 400 trilyon yüzyıl 45 digit sayı değerinde yy 185 digit sayı değerinde yy 445 digit sayı değerinde yy 121 Arama (Searching) Arama stratejileri, bir durumdan diğer bir duruma giderken, gidilecek durumun olası durumlar arasından nasıl seçildiğini belirler. Kör araştırmalar (blind search), bir sonraki adım olarak hangi hareketin seçileceğine dair bir tercihte bulunmazlar, Herhangi bir boyut bilgisi içermez. Bazen, bilgisiz araştırma olarak da adlandırılır, Prof.Dr.Adem KALINLI 122 Lokal Arama Amaç arama uzayında istenen kısıtlara / özelliklere sahip veya fayda fonksiyonunu maksimum yapan durumu bulmaktır, Hafızada sadece mevcut durumu tutar ve onu düzeltmeye çalışır. Dolayısıyla çok az hafıza gerektirir. Prof.Dr.Adem KALINLI 123 Tepe Tırmanma Algoritması (Hill Climbing) Tepe, araştırma uzayında rastgele bir noktadır, Mevcut durumun tüm komşulukları dikkate alınır, En iyi kaliteyi sağlayan komşu seçilir ve o noktaya hareket edilir. Prof.Dr.Adem KALINLI 124 Tepe Tırmanma Algoritması (Hill Climbing) Tepe araştırma algoritması sisli bir havada dağa tırmanmaya benzer, Genelde Prof.Dr.Adem KALINLI Çok nadiren 125 Problem Çözümleme Kullandığımız araştırma metodu gerçekten bir çözüm bulur mu? Eğer araştırma stratejisi problem için çözümün herhangi bir sınıfını vermiyorsa, zamanımızı boşa harcamış oluruz. Araştırmanın maliyeti aşağıdaki iki maliyetin toplamıdır: Yol Maliyeti: Daha düşük yol maliyetli çözüm daha iyidir. Araştırma Maliyeti (zaman ve hafıza) Bulunan çözüm optimal bir çözüm müdür? Optimal çözüm nedir? Prof.Dr.Adem KALINLI 126 Problem Çözümleme Problemleri genel olarak iki sınıfa ayırabiliriz: İyi biçimlendirilmiş problemler Kötü biçimlendirilmiş problemler İyi biçimlendirilmiş problemler, çözümün doğruluğu algoritmik olarak gösterilebilen problemlerdir. Algoritmik yaklaşımda, durum uzayının her elemanının çözüm şartlarına uyup uymadığı birer birer kontrol edilmektedir. Gerçek yaşamdaki problemlerin çoğu ise kötü biçimlendirilmiştir ve durum uzayının her elemanını değerlendirmek pratik olarak mümkün değildir. Dolayısıyla, kabul edilebilir sürelerde, en iyi çözümün bulunmasını garanti etmeyen ancak makul çözümler bulabilen yöntemler kullanılmaktadır. Prof.Dr.Adem KALINLI 127 Gezgin Satıcı Problemi, TSP Daha önceden belirlenen noktaları dolaşarak başlanan noktaya dönmek üzere en kısa yolu bulma problemidir. n şehirli bir TSP probleminde (n-1)!/2 adet farklı tur kombinasyonu vardır: 10 şehir için 1.8x105 adet farklı tur kombinasyonu, 20 şehir için 6x1016 adet farklı tur kombinasyonu, Veri kümesi 2 kat büyüdüğünde araştırma uzayı 1011 (100 milyar) kat büyümüştür. Prof.Dr.Adem KALINLI 128 Gezgin Satıcı Problemi, TSP 20 şehir için tüm turları 1 saatte listeleyen bir bilgisayar, 21 şehir için 20 saat, 22 şehir için 17,5 gün ve 25 şehir için 590 yılda tüm turları listeler. 50 şehirli bir TSP problemi için 3x1062 adet farklı tur kombinasyonu vardır. Gerekli süre? VLSI yonga üretimi? Uçuş planlama, haberleşme ağ planlaması vs… Prof.Dr.Adem KALINLI 129 Satranç Problemi Tüm oyun ağacını dolaşmak mümkün değildir. 5 gidiş ileriye araştırmada 1015 (katrilyon) durum, 40 gidişle biten oyun için 10120 farklı durum Askeri hareketler, tıbbi tanı, ekonomik planlama vs problemler için model. Prof.Dr.Adem KALINLI 130 Go Oyunu Go Oyunu: 19x19 çizgili oyununun karmaşıklığı 10360 !! Japonya, Go oyununu birinci dan seviyesinde oynayabilen program için 1.000.000$ ödül koymuştur. Uzmanlar başarılı bir Go programının ancak 2050’ de yazılabileceğini tahmin ediyorlar. Prof.Dr.Adem KALINLI 131 Örüntü Tanıma Minitua noktaları: Tümsek sonları Prof.Dr.Adem KALINLI Ayrım Kısa tümsek 132 Örüntü Tanıma Prof.Dr.Adem KALINLI 133 Sezgisel Araştırma (Heuristic Search) Durum uzayı çok büyük olduğunda, tüm çözümleri denemek kabul edilebilir bir zamanın ötesinde süreler gerektirir. Bu tür problemler genelde yapay zekanın konusudur, Yapay zeka problemlerinin çözümünde genellikle sezgisel yöntemler kullanılmaktadır. Sezgisel araştırmada, çözümün aranmasını kesin biçimde sınırlayan herhangi bir kural, strateji, hile sadeleştirme ve diğer etmenler kullanılır. Bu etmenlerden genellikle araştırmayı yönlendiren bir bulgu kastedilir. Prof.Dr.Adem KALINLI 134 Sezgisel Araştırma (Heuristic Search) Sezgisel terimi; akıllı tahminlere dayalı buluş yöntemi veya yeni çözümlerin keşfine götüren bulgulara dayalı arama yöntemi olarak tanımlanır. Dolayısıyla, sezgisel yaklaşım, bu tür durumlarda çözüm yolunun gerçek zamanda aranması şeklinde ele alınabilir Sezgisel arama zamanını kısaltır, optimum çözüme yakın çözümler sunar, fakat optimum çözümü garanti edemez. Prof.Dr.Adem KALINLI 135 Sezgisel Araştırma Boyut hakkında bazı bilgilere sahiptir, Genellikle kör araştırmalardan daha etkilidir, Bilgilendirilmiş araştırma olarak da adlandırılır, Sezgisel araştırma, gelecek harekete en iyi hareket olmasını garanti etmeden karar verir, Modern sezgisel teknikler genellikle bazı doğal oluşum süreçlerini taklit etmektedir: Tavlama Benzetimi, termodinamik süreçleri taklit eder, Genetik algoritmalar, genetik biliminden hareketle geliştirilmiştir, Karınca koloni algoritmaları, karıncaların yön ve yiyecek bulma stratejilerini taklit etmektedir, Yapay sinir ağları, insan beyninin hesaplama özelliklerini taklit etmektedir. Muhtelif sezgisel yöntemler vardır ve bu yöntemlerin farklı problemlerdeki başarımları farklılık göstermektedir. Prof.Dr.Adem KALINLI 136 Algoritmaların Değerlendirilme Kriterleri Tamlık (Completeness): Strateji bir çözüm bulmayı garanti ediyor mu?, Çözümün kalitesi? Zaman Karmaşıklığı (Time Complexity): Bir çözüm bulmak ne kadar zaman gerektiriyor? Uzay Karmaşıklığı (Space Complekxity): Araştırmayı gerçekleştirmek için, ne kadar hafıza gerektiriyor? Dinçlik (Robustness): Farklı çözümlerden başlamasına rağmen, benzer kalitede optimal çözümleri bulabiliyor mu? Esneklik : Amaç fonksiyon veya sınırlamalar kolaylıkla adapte edilebiliyor mu? Prof.Dr.Adem KALINLI 137 Algoritmalarla İlgili Pratik Bilgiler Tasarım Vektörü Optimizasyon Problemi: min f ( x) xR n Burada x, bilinmeyenler veya parametreler olarak adlandırılan tasarım vektörüdür. f değeri maksimize yada minimize edilmek istenen ve x’ in fonksiyonu olan amaç fonksiyonudur. f(x) x1 2 x2 1 2 2 , x1,2 2, 2 Amaç, [-2,2] aralığında f(x) fonksiyonunu minimum yapan x değerlerini bulmak, Bir algoritma kullanarak parametre değerlerinin aranmasında, tasarım vektörü aşağıdaki gibi tanımlanır: Prof.Dr.Adem KALINLI v x1, x2 138 Algoritmalarla İlgili Pratik Bilgiler Bilginin Temsili Tasarım vektörü oluşturulurken parametre değerlerinin temsil edilmesinde genellikle üç farklı yöntem kullanılır: İkili (binary) kodlama, Gerçel (real) kodlama, Sembolik veya Permütasyon kodlama Prof.Dr.Adem KALINLI 139 Algoritmalarla İlgili Pratik Bilgiler Bilginin Temsili, İkili Kodlama İkili Kodlama: Her bir çözüm vektörü 0 ve 1’ lerden oluşan bit dizisidir. Dizideki her bir bit çözümün bir özelliğini taşır. Binary temsilde çözüm vektörünün her bir elemanı çoğunlukla aynı sayıda bit kullanılarak temsil edilir. x1 10100111 x2 01001001 v [ 10100111 01001001 ] x1 x2 Bu değerler optimizasyon probleminin yapısına uygun olarak daha sonra reel yada integer değerlere dönüştürülmektedir. Prof.Dr.Adem KALINLI 140 Algoritmalarla İlgili Pratik Bilgiler Bilginin Temsili, İkili Kodlama x1 101001112 1 27 0 26 1 25 0 24 0 23 1 22 1 21 1 20 167 x2 010010012 0 27 1 26 0 25 0 24 1 23 0 22 0 21 1 20 73 Problemin türüne göre, parametre değerleri tamsayı olabileceği gibi, belirli bir aralığa ölçeklenmiş reel sayılarda olabilir. Parametre değerlerinin belirli bir aralıkta reel sayılar olması durumunda, ikili kodlamanın temsil ettiği değerlerin ilgili aralığa ( [a,b] ) ölçeklenmesi gerekir: xnew xold xmin b a a xmax xmin Prof.Dr.Adem KALINLI 141 Algoritmalarla İlgili Pratik Bilgiler Bilginin Temsili, İkili Kodlama x1 ve x2’ nin [-2,2] aralğına ölçeklenmiş değerleri aşağıdaki gibi olur: xmax 111111112 255 xmin 000000002 0 x1 167 0 2 (2) 2 0.6196 255 0 x2 73 0 2 (2) 2 0.8549 255 0 Tasarım parametrelerinin amaç fonksiyondaki görüntülerinin değerlendirilmesinde bu ölçeklenmiş değerler kullanılır: f(x) x1 2 x2 1 5.3462 2 Prof.Dr.Adem KALINLI 2 142 Algoritmalarla İlgili Pratik Bilgiler Bilginin Temsili, İkili Kodlama Böyle bir yaklaşımda sabit bir eksen aralığındaki hassasiyet kullanılan bit sayısına bağlıdır ve (UB-LB)/(2n-1)’ e eşittir. Burada, UB ve LB sırasıyla eksen aralığının alt ve üst sınırları, n ise çözüm vektöründeki her bir elemanın bit sayısıdır. Önceki örnekte x1 ve x2 8’ er bit ile temsil edilmiş ve arama [-2,2] aralığına ölçeklenmiştir. Dolayısıyla her bir bite karşılık gelen hassasiyet: hassasiyet 4 0.0156 255 Eğer daha yüksek hassasiyetle arama yapmak istenir ise, parametreleri temsil etmekte kullanılan bit sayısı artırılmalıdır. Eğer yukarıdaki örnekte parametreler 12 bit ile temsil edilirse: hassasiyet Prof.Dr.Adem KALINLI 4 0.000976 4095 143 Algoritmalarla İlgili Pratik Bilgiler Bilginin Temsili, İkili Kodlama [-1,2] aralığında gerçekleştirilen bir aramada, parametrelerin noktadan sonra 6 haneli hassasiyet ile temsil edilebilmesi için, kaç bit ile temsil edilmesi gerekir? Arama uzayının büyüklüğü 2-(-1)=3’ tür. Aralık 3x1000000 eşit aralığa bölünmelidir. n bitlik ikili bilgi ile temsil edilebilecek farklı durumların sayısı 2n dir. Kullanılacak bit uzunluğu değeri ile aralığın bölünmesi gereken eşit parça sayısı sağlanabilmelidir: 2n = 3x106 Eşitliğin her iki tarafının log değeri alınırsa, log(2n) = log(3x106) nlog(2) = 6.477121255 Buradan n=21.51653107 elde edilir. Dolayısıyla gerekli bit sayısı n=22 olarak belirlenmelidir. 144 Algoritmalarla İlgili Pratik Bilgiler Bilginin Temsili, İkili Kodlama Binary temsilde hassasiyeti artırmanın yolu optimize edilecek her bir parametre için daha fazla sayıda bit kullanmaktır Fakat bu durum algoritmanın hızını yavaşlatacaktır. Dolayısıyla parametreleri temsil etmekte kullanılan bit sayısına dikkatle karar verilmelidir. Kullanılacak algoritmanın operatörlerinin de ikili temsil ile uyumlu olmasına dikkat edilmelidir. İkili gösterimde bitlerin ağırlık değerlerinin farklı olması, bazı algoritmalarda global optimuma ulaşılmasını zorlaştırabilir. x 111111112 1 4 128 Prof.Dr.Adem KALINLI 145 Algoritmalarla İlgili Pratik Bilgiler Bilginin Temsili, Gerçel (Real) Kodlama Kayan noktalı gösterimde, her bir parametre çözüm vektöründe eşit uzunlukta kayan noktalı sayılar kullanılarak kodlanır. x1 3.274 x2 2.456 v [ 3 . 274 . 456 2 ] x1 x2 Her bir eleman istenen aralıkta bulunmaya zorlanmaktadır ve operatörler bu şartı muhafaza etmek üzere dikkatle tasarlanmaktadır. Hassasiyet kullanılan bilgisayara bağlı olmakla beraber, genelde binary temsile göre daha iyi olmaktadır. Prof.Dr.Adem KALINLI 146 Algoritmalarla İlgili Pratik Bilgiler Bilginin Temsili, Sembolik veya Permütasyon Kodlama Özellikle gezgin satıcı ve iş sıralaması gibi problemlerde kullanılır. v [ 3 7 5 216 0 4 ] Bu problemlerde bilgi ikili kodlama da kullanılabilir. Ancak, ikili sayıların temsil ettiği tam sayı değerlerin geçerliliği ile ilgili kontrol mekanizmaları da kullanılmalıdır. Ayrıca muhtelif operatörlerin kullanımında değerlerin geçerliliği ve tekrara düşmemesi gibi hususlarda dikkate alınmalıdır. Prof.Dr.Adem KALINLI 147 Algoritmalarla İlgili Pratik Bilgiler Veri normalizasyonu Özellikle yapay sinir ağlarının eğitilmesi gibi uygulamalarda kullanılan çok sayıda veri, çok farklı değerlerde olabilir. Örneğin bir dizide, 0.001 değerinin yanı sıra, 234 gibi değerlerde yer alabilir. Veriler arasındaki değer farklılıklarının çok fazla olması algoritmaların ve YSA ların başarımını olumsuz yönde etkileyebilir. Bu tür durumlarda kullanılacak verilerin belirli aralıklara normalize edilmesi (ölçeklenmesi) başarım üzerinde olumlu etkilere sahip olabilmektedir. 10 ve 100 değerinin tanjant hiperbolik fonksiyonu değerleri noktadan sonraki 6 basamak için 1.000000 dir. Dolayısıyla ilk 6 hane için fark görülmez. F 1 e n e n F ( n) n e e n Prof.Dr.Adem KALINLI 0 n -1 148 Algoritmalarla İlgili Pratik Bilgiler Veri normalizasyonu [0,1] aralığına normalizasyon: xnew xold x min x max x min [-1,1] aralığına normalizasyon: xnew 2 [a,b] aralığına normalizasyon: xnew xold xmin 1 xmax xmin xold xmin b a a xmax xmin Bazı uygulamalarda giriş verisini logaritma, sinüs, cosinüs veya tanjant gibi fonksiyonlardan geçirerek normalizasyon gerçekleştirmekte başarılı sonuçlar verebilmektedir. Prof.Dr.Adem KALINLI 149 Seri ve Popülasyon Tabanlı Algoritmalar Seri (iteratif) Algoritmalar, yalnızca bir başlangıç çözümü ile araştırmaya başlamakta ve uyguladıkları çeşitli stratejilerle bu çözümü geliştirmeye çalışmaktadırlar. Bu yapıları nedeniyle ilgili algoritmalar seri veya iteratif algoritmalar olarak adlandırılmaktadır. Tabu Arama (Tabu Search) ve Tavlama Benzetimi (Simulated Annealing) Algoritmaları bu türdendir. Seri algoritmalar, genelde doğadaki bireysel başarılara odaklı sistemleri taklit etmektedir. Popülasyon tabanlı algoritmalar, mevcut çözümlerin belirli bir seti ile çalışır ve yeni çözümler üretmek için onları bir arada kullanırlar. Genetik Algoritma, Karınca Koloni algoritması ve Memetik algoritmalar popülasyon tabanlı algoritmalardır. Genel olarak popülasyon tabanlı algoritmalar ise, başarı için bireylerin işbirliği stratejilerine dayalıdır. Prof.Dr.Adem KALINLI 150 Seri ve Popülasyon Tabanlı Algoritmalar Seri algoritmaların global optimuma ulaşmaları için gerekli süre büyük oranda başlangıç çözümünün, global optimuma olan uzaklığına bağlıdır. Global optimum yakınından araştırmaya başlayan aramalarda optimum çözüme kısa sürede ulaşılabilmesine rağmen, global optimuma uzak noktalardan başlayan aramalarda global optimuma erişmek uzun süreler gerektirebilmektedir. Seri algoritmalar, genellikle bulunduğu bölgenin optimumuna hızla ulaşabilmektedir. Popülasyon tabanlı algoritmalarda, başlangıç popülasyonundaki çözümlerden en az birinin global optimuma yakın olma olasılığı yüksek olduğundan (birden çok noktadan aynı anda arama yapıldığından), genellikle global optimumun bulunduğu bölgeye kısa sürelerde ulaşılabilmektedir. Genellikle, popülasyon tabanlı algoritmalar, global optimumun bulunduğu bölgeye daha kısa sürede yakınsamalarına rağmen, çoğunlukla optimal çözüm bulmaları uzun süreler gerektirebilmektedir. Prof.Dr.Adem KALINLI 151 Seri ve Popülasyon Tabanlı Algoritmalar Literatürde, Seri ve Popülasyon tabanlı algoritmaların avantajlarını bir arada kullanan hibrid algoritma modelleri mevcuttur. Genel yaklaşım, paralel algoritmalar ile daha başarılı çözümleme yöntemleri geliştirmeye odaklıdır. Paralel algoritmalar işlem zamanını kısaltmaları, çözüm uzayını daha etkili bir şekilde tarayabilmeleri ve erken yakınsamadan kurtulma gibi avantajlara sahiptir. Paralellik donanımsal / yazılımsal veya senkron/asenkron gibi farklı şekillerde yapılmaktadır. Erken Yakınsama (Premature Convergence): Bir algoritmanın hızla (kısa sürede) bir lokal optimuma takılıp, bu noktayı aşamaması olarak tanımlanabilir. Prof.Dr.Adem KALINLI 152 Yapay Zeka Yöntemleri Yapay Sinir Ağları (Artificial Neural Network) Genetik Algoritma (Genetic Algorithm) Karınca Koloni Algoritması (Ant Colony Algorithm) Tavlama Benzetimi (Simulated Annealing) Tabu Arama Algoritması (Tabu Search) Yapay Bağışıklık Sistemi (Artificial Immune System) … Prof.Dr.Adem KALINLI 153 Teşekkürler…