Slayt 1 - Bilgisayar Mühendisliği Bölümü

Transkript

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ı
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
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.
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.
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?
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ı
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... ”
8

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.
9

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.
10

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
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

…
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.
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  q0
dt C
dt
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
15

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.!
16

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!
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.
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.
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.

…
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)
xRn

iI
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

iE
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.
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.
22
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.
23
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.
24
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
Kısmi türevler x =a ve y=b noktasında hesaplanmıştır.
25
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!
26
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.
27
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).
28
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

Ö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

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

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

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

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

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

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

İ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

Ö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

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

Ö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
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

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

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

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

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

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

Dansın hızı, dikeyle yaptığı açı, yassı sekiz şekli gibi parametrelerle doğrultu ve mesafe
bilgisi verilmektedir.
83

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.
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
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.
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.
87

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



88






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

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.
90

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.
91

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,

…
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

…
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.
94
Yapay Zekanın Diğer Alanlarla İlişkisi

Problem Çözümleme: Kompleks, özellikle kombinasyonel problemler
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.... ”
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.
98

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)
99

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.
100

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.
101

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.
102

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.
103

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.
104

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



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ı…
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.
107

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)
108

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ü:

110 3 13 2 14 7 16

110 3 15 4 14 7 16
9.LK/ÇW
109

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ı.
110
Doç.Dr.Adem KALINLI
Prof.Dr.Adem
Problemin alt problemlere bölünerek çözülmesine örnek
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
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.
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
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,
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.
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.
124
Tepe Tırmanma Algoritması (Hill Climbing)

Tepe araştırma algoritması sisli bir havada dağa tırmanmaya benzer,
Genelde
Çok nadiren
125

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?
126

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.
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.
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…
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.
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.
131
Örüntü Tanıma
Minitua noktaları: Tümsek sonları
Ayrım
Kısa tümsek
132
Örüntü Tanıma
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.
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.
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.
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?
137
Algoritmalarla İlgili Pratik Bilgiler

Tasarım Vektörü

Optimizasyon Problemi:
min f ( x)
xR 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:
v  x1, x2 
138

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
139

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.
140

x1  101001112  1 27  0  26  1 25  0  24  0  23  1 22  1 21  1 20  167
x2  010010012  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
141


x1 ve x2’ nin [-2,2] aralğına ölçeklenmiş değerleri aşağıdaki gibi olur:
xmax  111111112  255
xmin  000000002  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
2
142


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 
4
 0.000976
4095
143


[-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


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  111111112
1
4
128
145

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.
146

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.
147

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
0
n
-1
148

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.
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.
150

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.
151

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.
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)

…
153
Teşekkürler…

Slayt 1 - Bilgisayar Mühendisliği Bölümü

Transkript

Benzer belgeler

GAZOZ KAPAĞINDAN ÇIKAN DOSTLUK 29 Ocak`ta

Gülpempe Paygamberimiz İçin Yazılmıştı

indir

Yapay Zeka Nedir II - Yapay Zeka Meraklıları

REKNOVA innovative reklame Märkische Str. 7 58300 Wetter Tel

PDF - Marmara Medical Journal

Yapay Yaşam I - Yapay Zeka Meraklıları

PDF Tam Metin - Başkent Üniversitesi Psikoloji Bölümü

Story - World Stories