Tüketici-Kaynak modeli

Bu model kitapta çok kısa anlatılmıştı. Bu nedenle kaynak olarak verilen makaleleri bulup anlamaya çalıştım. Bu modelde de iki tür kullandım. Bunlar iki bitki türü ve kaynak olarak da topraktaki besleyici maddeler ve güneş ışığı var.

Önce türlerin gelişimini kontrol eden denklemleri vereyim. İtiraf edeyim, bu denklemler önceki modellerdeki denklemlerden daha karmaşık. İki türün seçtiği stratejiler aşağıdaki \(A_1\) ve \(A_2\) parametreleriyle seçiliyor.

\(\frac{dB_1}{dt} = B_1 \cdot MIN(\frac{r \cdot N \cdot A_1}{N + k_N} – R – d , \frac{r \cdot L (1 – A_1)}{L + k_L} – R – d) \)

\(\frac{dB_2}{dt} = B_2 \cdot MIN(\frac{r \cdot N \cdot A_2}{N + k_N} – R – d , \frac{r \cdot L (1 – A_2)}{L + k_L} – R – d) \)

Bu denklemlerde MIN işlemi, iki değerin en küçüğünü seçiyor. Görüldüğü gibi modelde bir sürü sabit ve parametre var. Bunları kısaca açıklamaya çalışayım.

\(B_1\): Birinci türün toplam biyokütlesi. Burada bitki türlerinden bahsettiğimiz için nüfus yerine toplam ne kadar biyokütle oluşturduğuna bakılmış denklemlerde. Her iterasyonda bu değer yeniden hesaplanacak.

\(B_2\): İkinci türün toplam biyokütlesi. Bu değer de her iterasyonda yeniden hesaplanıyor.

Şimdi bu biyokütleleri hesaplamak için kullanacağım diğer parametreleri açıklayayım.

\(r \): Her bitkinin maksimum büyüme oranı. Bitkilerin biyokütlelerinin artışı bu sabitle doğru orantılı, yani bu sabit ne kadar büyükse bitkilerin büyüme oranı da o kadar hızlı. Doğru orantıyı görmek için ilk denklemde önce \(B_1 \cdot {r \cdot N \cdot A_1}{N + k_N} \) kısmına bakalım. Burada \(r \) sayısı büyürse çarpım da büyür. Aynı şekilde minimum işleminin diğer adayında da \(r \) sayısı pay kısmında bulunuyor. \(B_1 \cdot r \cdot L (1 – A_1) \). Yani \(r \) sayısı büyüdükçe eşitliğin sağ tarafı da büyüme eğiliminde.

\(A_1\): Birinci tür için köke ayrılan biyokütle. Bu parametre birinci türün seçtiği stratejiyi de belirliyor. Yani daha çok besine mi güneş ışığına mı ağırlık veriyor.

\(A_2\): İkinci tür için köke ayrılan biyokütle. Bu parametre ikinci türün seçtiği stratejiyi de belirliyor. Yani daha çok besine mi güneş ışığına mı ağırlık veriyor.

\(k_N\): Topraktaki besine dayalı büyüme için yarı doyma sabiti. Bu sabit paydada olduğu için arttıkça topraktaki besinden gelen biyokütle artışı azalıyor. Bu sabit sayesinde topraktaki besin değişikliğinin ani etkileri biraz azaltılmış oluyor. Yani \(N \) değeri aniden büyürse ya da küçülürse türün biyokütlesi daha az bir oranda büyüyüp küçülecek. Bunu görmek için \(\frac{N}{N + k_N} \) ifadesiyle biraz oynamak yeterli.

\(k_L\): Güneş ışığına bağlı büyüme için yarı doyma sabiti. Bu sabit paydada olduğu için arttıkça güneş ışığından gelen biyokütle artışı azalıyor. Bu sabit sayesinde güneş ışığındaki değişikliğinin ani etkileri biraz azaltılmış oluyor. Yani \(L \) değeri aniden büyürse ya da küçülürse türün biyokütlesi daha az bir oranda büyüyüp küçülecek. Bunu görmek için \(\frac{L}{L + k_L} \) ifadesiyle biraz oynamak yeterli.

\(R \): Solunum oranı. Türlerden bağımsız bir sabit. Sanırım solunum sırasında besinlerin yakılması nedeniyle biyokütledeki bir tür azalmayı modelliyor. Bu sabitle biyokütlenin çarpımı çıkarma işlemi yüzünden biyokütleyi her zaman azaltma eğiliminde.

\(d \): Kayıp oranı. Türlerden bağımsız ve iç ya da dış nedenlerle herhangi bir şekilde ölümlerin modellendiği bir sabit. Bu sabitle biyokütlenin çarpımı o anki biyokütleden çıkarıldığı için beklendiği gibi biyokütleyi her zaman azaltma eğiliminde.

\(N \): Topraktaki toplam besin miktarı. Bu modelde kullanılan kaynaklardan birisi bu. Bitkiler çoğaldıkça topraktaki besin miktarı azalacaktır ve bitkiler ölünce toprak da besin bakımından zenginleşecektir. Bu kaynağın zamana göre değişim denklemini aşağıda vereceğim.

\(L \): Bitkiler tarafından kullanılabilen güneş ışığı miktarı. Bu da bitkilerin kullanabildiği kaynaklardan ikincisi.

Şimdi kaynakların değişimini modelleyen denklemlere bakalım.

\(\frac{dN}{dt}=a (T – N – B_1 \cdot p – B_2 \cdot p) \)

\(– MIN(\frac{r\cdot N \cdot A_1}{N + k_N} – R, \frac{r\cdot L (1 – A_1}{L + k_L} – R) \cdot B_1 \cdot p \)

\(– MIN(\frac{r\cdot N \cdot A_2}{N + k_N} – R, \frac{r\cdot L (1 – A_2}{L + k_L} – R) \cdot B_2 \cdot p \)

\(L = \frac {L_0}{1 + \alpha \cdot B_1(1-A_1) + \alpha \cdot B_2(1 – A_2)} \)

Bu iki denklemin parametrelerini açıklayayım:

\(T \) : Habitattaki toplam besin miktarı. Bu toplama topraktaki, ölü bitkilerdeki ve bitki biyokütlelerindeki besinlerin hepsi dahil.

\(p \): Bitki dokularındaki besin konsantrasyonu.

\(a \): Mineralleşme oranı. Yani ölü biyokütlenin hangi oranda besine dönüştüğünü belirliyor. \(a (T – N – B_1 \cdot p – B_2 \cdot p) \) ifadesindeki \(T – N – B_1 \cdot p – B_2 \cdot p \) kısmına bakarsak önce habitattaki toplam besinden topraktaki besin miktarını çıkarıyoruz. Sonra kalandan birinci türün biyokütlesiyle bitki dokusundaki besin konsantrasyonunu yani birinci türdeki toplam besin miktarını çıkarıyoruz. Sonra yine kalandan ikinci türdeki toplam besin miktarını çıkarıyoruz. Dolayısıyla elimizde kalan miktar aslında ölü bitkilerdeki besin miktarını verir. Bu miktarıda mineralleşmeyle çarparsak o iterasyonda ölü bitkilerden toprağa ne kadar besin geri dönüşü olacağını buluruz. Tabii ki mineralleşme oranının kullanıldığı ilk kaynak denkleminde minimum işleminin yapıldığı bir terim daha var. Dikkat edersek bu terim neredeyse biyokütle değişim denklemlerinin aynısı. Farkların biri kayıp parametresi burada yok, diğeri de biyokütledeki artışın bitki besin konsantrasyonuyla çarpılması. Bu iki fark aslında bu terimin biyokütledeki değişim sayesinde ne kadar besinin topraktan uzaklaştırıldığını gösteriyor ve bu nedenle topraktaki besin miktarına etkisi de çıkarma işleminden görüldüğü gibi negatif.

\(L_0\): Güneş ışığı sabiti.

\(\alpha \): Birim yaprak biyokütlesi başına soğrulan ışık miktarı. Bu sabit paydada olduğundan büyüdükçe ortamdaki diğer bitkilere kalan ışık miktarı da azalıyor. Paydadaki diğer terimler de toplam ışıktan faydalanan biyokütle olduğunu görmek kolay. Yani bütün ifade bir tür biyokütle başına düşen ışık miktarı gibi düşünülebilir.

Bu modeli denemek için aşağıdaki basit kodu yazdım. Sabitlerle ve stratejilerle oynayarak çok değişik çoğalma davranışları görmek mümkün. Değişkenleri yazıdaki şekliyle tanımladım ki, değişiklik yapmak daha kolay olsun.

import numpy as np
import matplotlib.pyplot as plt

B1 = 0.5  # Biomass of population 1
B2 = 0.5  # Biomass of population 2
N = 1.0  # available soil nutrient
L = 1.0  # light availability
A1 = 0.8  # fraction of biomass allocated to root by population 1
A2 = 0.2  # fraction of biomass allocated to root by population 2
r = 5.0  # per capita maximal rate of plant growth
kn = 0.1  # 1/2 saturation constant for nutrient
kl = 0.1  # 1/2 saturation constants for light
R = 0.2  # density independent per capita respiration rate
d = 0.1  # density independent per capita loss rate


def G1(L, N):
    return r*N*A1/(N+kn) - R - d


def G2(L, N):
    return r*L*(1-A2)/(L+kl) - R - d


T = 3.0  # Total soil nutrient in habitat
a = 0.5  # mineralization rate
p = 0.4  # plant tissue nutrient concentration

L0 = 2.0  # solar constant
alpha = 0.01  # light decay rate per unit leaf biomass

populations = np.empty((0, 4), int)
populations = np.append(populations, np.array(
    [[B1, B2, N, L]]), axis=0)

for i in range(1, 100):
    B1 = B1 + B1*min(G1(L, N), G2(L, N))
    if B1 < 0:
        B1 = 0
    B2 = B2 + B2*min(G1(L, N), G2(L, N))
    if B2 < 0:
        B2 = 0

    N = N + a*(T - N - B1*p - B2*p) - min(G1(L, N), G2(L, N)) * \
        B1*p - min(G1(L, N), G2(L, N))*B2*p
    if N < 0:
        N = 0
    L = L0 / (1 + alpha*B1*(1 - A1) + alpha*B2*(1 - A2))
    if L < 0:
        L = 0

    populations = np.append(populations, np.array(
        [[B1, B2, N, L]]), axis=0)


f, (ax1, ax2, ax3, ax4) = plt.subplots(4)
line1, = ax1.plot(populations[:, 0], color="b")
line2, = ax2.plot(populations[:, 1], color="r")
line3, = ax3.plot(populations[:, 2], color="g")
line4, = ax4.plot(populations[:, 3], color="y")

ax1.set_ylabel("B1")
ax2.set_ylabel("B2")
ax3.set_ylabel("Besin")
ax4.set_ylabel("Güneş")
ax2.set_xlabel("zaman")
plt.show()

Bu da yukarıdaki programın çıktısı

Leslie modeli (bir avcı ve bir av türü)

Bu modeli internette arattığımda daha çok yaşlara göre tanımlanmış bir popülasyonda matrisli modeller buldum ama kitapta iki denklemle tanımlanmış bir model anlatılıyordu.

Lotka-Volterra modelinden farklı olarak av türü için yoğunlupa bağlı bir ölüm oranı parametresine ve avcı için de daha gerçekçi bir ölüm oranı terimine sahip. Önce modelin denklemlerini göstereyim:

\(\frac{dx}{dt} = \frac{r_1}{K_1}(K_1 – x) – b \cdot y \)

\(\frac{dy}{dt} = r_2 \cdot (1 – \frac {y}{c\cdot b \cdot x}) \)

\(x \) burada da av türünün nüfusunu gösteriyor, \(y \) de avcı nüfusunu.

\(K_1 \) sabiti diğer türlerin olmadığı durumda ortamda bulunabilecek popülasyon büyüklüğünü, bu durumda av türünün nüfusunu, belirliyor.

\(r_1 \) sabitini nüfuslar sıfıra yakınken av türünün çoğalma hızı olarak düşünebiliriz.

\(b \) sabiti avcıların avları ne kadar kolay avlayabildiğini gösteriyor. Yani yüksek \(b \) değeri avlanmanın çok olduğunu modelliyor.

\(r_2 \) sabitini nüfuslar sıfıra yakınken avcı türünün çoğalma hızı olarak kullanıyoruz.

\(c \) sabiti de avların avcı için besleyici değerini gösteriyor.

Şimdi bu sabitlerin nüfusların değişimini nasıl etkilediğine bakayım.

\(r_1 \) ve \(r_2 \) sabitleri kendilerinden beklendiği gibi türlerin üremelerini artırma eğiliminde. Bu sabitler büyüdükçe türlerin çoğalma hızı da artacaktır.

\(K_1 \) sabitinin sisteme etkisi biraz daha karışık. Bu terim hem payda hem de paydada bulunuyor. Burada \(\frac {K_1 – x}{K_1} \) ifadesine bakayım önce. Bu ifadenin payı ortamda daha ne kadar avcı nüfusu olabileceğini gösteriyor, paydası da ortamın tek başına ne kadar avı besleyebileceğini. Yani bu bölüm ortamda henüz tüketilmemiş av potansiyelinin oranını veriyor. Örneğin daha yüzde otuz av daha olabilir gibi. Yani bu terim av nüfusu azaldıkça artıyor ve \(r_1 \) terimiyle beraber av nüfusunun artması için daha çok uğraşıyor. Av nüfusu ortamın besleyebileceği maksimum olan \(K_1 \) sayısına ulaştığında bu oran da sıfır oluyor ve av türünün üremesini durdurmaya çalışıyor. Nüfus daha da artarsa av nüfusu ortamın kaldırabileceğinden fazla olduğundan bu terim üremeyi değil ölümü tetiklemeye başlıyor.

\(b \cdot y \) terimi avcıların o an toplamda ne kadar avlayacağını gösteriyor. Bunu da avın nüfus artışından çıkararak av nüfusunun net değişikliğini modelliyoruz. \(b \) sabiti ne kadar yüksekse av nüfusunda ölümler de o kadar çok olacaktır.

Avcı nüfusunu artıran ana terim tabii ki \(r_2 \) sabiti. Bunun yanında avcıların ölümünü belirleren diğer terim biraz daha karmaşık. Şimdi bunu anlamaya çalışayım.

\(1 – \frac {y}{c\cdot b \cdot x} \) teriminin değeri avcı nüfusu arttıkça azalmakta ve bir süre sonra negatife dönüşecek. Yani bu modelde avcı nüfusunun kontrolsüz artmasının avcıların nüfus artışını azaltacağı ve hatta avcılarda ölümleri artıracağı da göz önüne alınmış. Aynı mantıkla baktığımızda \(b \) (başarılı avlanma oranı), \(c\) (avın avcı için besleyiciliği) ya da av nüfusu arttıkça avcılarda ölüm miktarı azalacaktır.

Madem parametreleri biraz anlayabildim, bir de bu modeli python ile programlayayım dedim. Parametreleri seçmek biraz zor oldu ama. Epey bir deneme yanılmadan sonra şöyle bir sonuç elde ettim.


from random import betavariate
import numpy as np
import matplotlib.pyplot as plt

x = 10
y = 10
b = 0.1  # effectiveness of predators in killing preys
c = 5  # nutritional value of the prey to the predator
r1 = 1.4  # birth rate of prey
r2 = 0.8  # birth rate of predator
K1 = 50  # capacity

populations = np.empty((0, 2), int)
populations = np.append(populations, np.array(
    [[x, y]]), axis=0)

for i in range(1, 100):
    H1 = ((r1/K1)*(K1 - x) - b*y)
    H2 = 0
    x = x + x*H1
    if x < 0:
        x = 0

    if x != 0:
        H2 = (r2*(1 - (y/(c*b*x))))
        y = y + y*H2
    if y < 0:
        y = 0
    populations = np.append(populations, np.array(
        [[x, y]]), axis=0)

f, (ax1, ax2) = plt.subplots(2)
line1, = ax1.plot(populations[:, 0], color="b")
line2, = ax2.plot(populations[:, 1], color="r")

ax1.set_ylabel("Av")
ax2.set_ylabel("Avcı")
ax2.set_xlabel("zaman")
plt.show()

Lotka-Volterra modeli

Oyun teorisi her zaman ilgimi çekmiştir. Geçtiğimiz yıllarda evrimsel oyun teorisine bir giriş yaptım fakat kullandığım kitapta birçok şey başlangıç seviyesi için uygun olmadığından çok ileri gidemedim. Geçenlerde başka bir kitap buldum ve şansımı bir de bununla deneyeyim dedim.

İlk pratik konular popülasyon modelleme üzerineydi. Bu modellerden birini bu yazıda anlamaya ve anlatmaya çalışacağım.

Bu modelde iki türden oluşan popülasyonların bir türü ele alınıyor. En basit örnekleri av ve avcılardan şeklindeki türler. Avcıların doğum oranı çevredeki av oranına bağlı. Ne kadar çok avlanabilirlerse o kadar iyi beslenirler ve üremeleri kolaylaşır. Avcıların ölüm miktarı ise normal şartlarda sadece kendi nüfuslarına bağlı. Aynı şekilde avların üreme miktarı sadece kendi nüfuslarına bağlıyken ölüm sayıları tabii ki avcıların sayısına da bağlı. Ortamdaki kaynakların hem av hem de avcı için yeterli olduğunu varsayalım.

Bu düşünceler doğrultusunda şimdi Lotka-Volterra denklemlerini yazayım. x av türünün nüfusu, y de avcı türünün nüfusu olsun.

\(\frac{dx}{dt} = \alpha x – \beta x \cdot y \)

\(\frac{dy}{dt} = \delta x \cdot y – \gamma y \)

Bu modeli biraz açıklamaya çalışayım. \(\frac{dx}{td} \) terimi av türünün nüfusunun zamana göre değişimini göstermekte. Yani bir süre geçince bu nüfusun artışını ya da azalışını, kısaca değişimini gösteriyoruz. Bu değişim o anki nüfus sayılarıyla ve bası sabitlerle orantılı. Aynı şekilde \(\frac{dy}{td} \) terimi de avcı nüfusundaki zamana göre değişimi ifade etmekte.

Denklemlerdeki sabitlere bakalım şimdi: Öncelikle bütün sabitlerin pozitif sayılar olduğunu varsayalım. Bu sayede o sabitlere daha alışık olduğumuz anlamlar yükleyebileceğiz.

\(alpha \) : av türünün doğum oranı. Doğum oranı av türünde sadece av türünün popülasyonunu etkiliyor. Bunu \(\alpha x \) ifadesinden görebiliyoruz. Av türünün çoğalması için çevredeki kaynaklara ve kendi türüne ihtiyacı var ve çevredeki kaynakların yeterli olduğunu varsaymıştık.

\(\beta \): bunu av türündeki ölüm oranı diye yorumlayabiliriz. Genelde iki tür arasındaki etkileşim faktörü olarak kullanılıyor ama bu denklemde ölüm oranı olarak çalıştığını görebiliriz. Öncelikle $\beta x \cdot y $ terimi diğer terimden çıkarılıyor, yani bir azalmayı simgeliyor. Diğer taraftan iki popülasyonun sayısına da etki ediyor. Yani bu sayılar arttıkça etkisi de artıyor. Bunu avcı sayısı arttıkça bu avcıların avlayacağı av sayısının artması şeklinde yorumlayabiliriz. Aynı şekilde av sayısı artarsa da avcılar daha kolay av bulacağından, az avcı olsa bile yine de daha çok av ölecektir.

\(\delta \): Bu sabiti de avcıların doğum oranı olarak düşünebiliriz. Aslında \(\beta \) sabiti gibi iki tür arasındaki bir etkileşim sabiti ama \(\delta x \cdot y \) teriminin pozitif olduğuna bakarsak avcı popülasyonunu artıracak bir etki yaptığını görürüz. Ayrıca iki popülasyona da bağlı bir artış sağlıyor. Eğer avcı sayısı artarsa türün üremesi kolaylaşacak. Eğer av sayısı artarsa avcılar daha iyi beslenebilecek ve yine daha çok üreyebilecekler.

\(\gamma \): Bu sabiti de avcıların ölüm oranı şeklinde düşünebiliriz. \(\gamma y \) teriminin diğer terimden çıkarılması popülasyonda azaltıcı bir etki yapacaktır ve bu da ölümü çağrıştırabilir. Av türü avcılar için tehdit olmadığında bu sabit av nüfusundan bağımsız bir etki yapmakta.

Şimdi bu denklemleri python programlarıyla deneyerek popülasyonların nasıl değiştiğinin grafiklerini elde etmeye çalışacağım.

import numpy as np
import matplotlib.pyplot as plt

x = 10
y = 10
alpha = 0.1
beta = 0.04
gamma = 0.04
delta = 0.01

populations = np.empty((0, 2), int)
populations = np.append(populations, np.array(
    [[x, y]]), axis=0)

for i in range(1, 1000):
    x = x + alpha*x - beta*x*y
    if x < 0:
        x = 0
    y = y + delta*x*y - gamma*y
    if y < 0:
        y = 0
    populations = np.append(populations, np.array(
        [[x, y]]), axis=0)

f, (ax1, ax2) = plt.subplots(2)

line1, = ax1.plot(populations[:, 0], color="b")
line2, = ax2.plot(populations[:, 1], color="r")

ax1.set_ylabel("Av")
ax2.set_ylabel("Avcı")
ax2.set_xlabel("zaman")
plt.show()

Av sayısı artışından hemen sonra bol besin bulan avcıların sayısı da hızla yükselmiş. Avcı sayısının yükselmesiyle av nüfusunda aşırı avlanma nedeniyle hızlı bir düşüş görülüyor. Grafikten ayrıca bu davranışların sürekli tekrarlandığını görüyoruz. Bu grafiğe bakıp her zaman bu tür bir nüfus değişimi gözlemleneceği düşünülmemeli ama. Sabit sayılara ve ilk durumdaki nüfus değerlerine göre çok farklı bir davranış da görülebilir. Şimdi buna bir örnek vereyim.


import numpy as np
import matplotlib.pyplot as plt

x = 10
y = 10
alpha = 0.1
beta = 0.1092
gamma = 0.04
delta = 0.01

populations = np.empty((0, 2), int)
populations = np.append(populations, np.array(
    [[x, y]]), axis=0)

for i in range(1, 5000):
    x = x + alpha*x - beta*x*y
    if x < 0:
        x = 0
    y = y + delta*x*y - gamma*y
    if y < 0:
        y = 0
    populations = np.append(populations, np.array(
        [[x, y]]), axis=0)

f, (ax1, ax2) = plt.subplots(2)

av, = ax1.plot(populations[:, 0], color="b")
avci, = ax2.plot(populations[:, 1], color="r")

ax1.set_ylabel("Av")
ax2.set_ylabel("Avcı")
ax2.set_xlabel("zaman")
plt.show()

Bu programda sadece \(\beta \) sabitini yükselttim, yani avcıların avlanma oranını artırdım. Bir noktadan sonra aşırı avlanmadan sonra av türünün nüfusu tamamen tükeniyor. Bu noktadan sonra avcılar da yok olmaya başlıyor.

Zamanı bu grafikte daha da ileriye götürdüm ki türlerin bir daha dirilmediği daha iyi görülebilsin. Demek ki seçilen sabitlere göre iki türün de ortadan kalkması mümkün.

Peki av türü ilk azalmadan sonra nasıl yeniden çoğalmayı başardı? Bunu görebilmek için grafiği çok büyütmek lazım.

Bu grafikte sadece av nüfusunu 3. ile 9. iterasyon arasında büyüttüm. Avcı grafiğine dokunmadım. Burada görüyoruz ki av nüfusu sıfıra çok yaklaşmış (\(5\cdot 10^{-11}\) ). Evet bu sayı gerçek hayatta çok anlamsız ama modeli tanımlayan diferansiyel denklemler için geçerli ve yeterli sayılar.

Bir de bu iki türün popülasyonlarını zamana göre değil de birbirlerine göre gösterebiliriz. Buna faz uzayı deniyor sanırım, ingilizcesi phase-space plot. Programı bir de bu gösterim için düzenledim.


from random import betavariate
import numpy as np
import matplotlib.pyplot as plt

x = 10
y = 10
alpha = 0.1
beta = 0.04
gamma = 0.04
delta = 0.01

populations = np.empty((0, 2), int)
populations = np.append(populations, np.array(
    [[x, y]]), axis=0)

for i in range(1, 1000):
    x = x + alpha*x - beta*x*y
    if x < 0:
        x = 0
    y = y + delta*x*y - gamma*y
    if y < 0:
        y = 0
    populations = np.append(populations, np.array(
        [[x, y]]), axis=0)

plt.plot(populations[:, 0], populations[:, 1])
plt.ylabel("avcı")
plt.xlabel("av")
plt.show()

Bu da programı çalıştırınca çıkan grafik:

Bu model çevremizdeki türleri çok iyi modellemese de uzun süre ekonomi alanında kullanılmış.

Doğrusal arama

Eski bir espride değişik mesleklerin Afrika’da nasıl fil avladığı sorulur. Espriye göre bilgisayarcı aşağıdaki algoritmayı kullanır:

  1. Afrikaya gidilir
  2. En güneyde Ümit burnunda başlanır.
  3. Kuzeye doğru yavaşça ilerlerken kıta doğudan batıya doğru taranır.
  4. Doğudan batıya her taramada aşağıdaki işlemler yapılır:
1. Görülen her hayvan yakalanır.
2. Yakalanan hayvan bilinen bir fil ile karşılaştırılır.
3. Eğer yakaladığımız hayvan fil ise arama biter.

Yazılımlarda sık sık verilen bir listede belli bir elemanın olup olmadığını ararız. Bu işi için de çoğunlukla yukarıdakine benzer algoritmalar kullanırız. Listenin başından başlarız ve her adımda listenin sonuna gelip gelmediğimizi ve o anki elemanın aradığımız eleman olup olmadığını kontrol ederiz. Bu arama işleminde her adımda iki şeyi kontrol ettiğimize dikkatinizi çekmek istiyorum.

  1. Listenin sonuna geldik mi?
  2. O anki eleman aradığımız eleman mı?

Bu meseleyi ilerde tekrar ele alacağım. Şimdilik algoritmanın bu en basit halinin bir sümulasyonunu yapmak istedim. Aşağıdaki linkten simulasyonu deneyebilirsiniz. Simulasyonda aranan sayı 82 olacaktır ve listede bu sayı mevcut. Arama işleminde her adımda yapılan işlemler açıklama alanında gösteriliyor.

Simulasyon linki

Boyer-Moore Algoritması

Boyer-Moore metin arama algoritmasının simulasyonuna da aşağıdaki linkten ulaşabilirsiniz. Bu algoritmanın diğer arama algoritmalarından farkı aranan metin ile ana metin soldan sağa doğru değil de sağdan sola doğru karşılaştırılıyor. Karşılaştırmada uyumsuz bir harf bulunursa daha önceki simulasyonlarda gördüğümüz Good Suffix ve Bad Character kurallarına göre oluşturduğumuz tablolara göre aranan metnin ne kadar kaydırılması gerektiği okunuyor ve aranan metin sağa doğru bu iki sayının daha büyüğü kadar kaydırılıyor. Bu işlem metin bitene ya da aranan metin bulunana kadar devam ediyor.

Simulasyon linki

Good suffix rule (Boyer-Moore algoritması)

Boyer-Moore metin arama algoritması serisinde öğrenmeye çalışacağım ikinci algoritma good suffix rule adı altında biliniyor. Aranan metnin ne kadar sağa kayrıdılacağını belirleyen iki kuralın ikincisi ve diğer yöntemden (bad character rule) biraz daha karışıkmış.

Bad character kuralında sadece uyumsuzluk olan noktadaki karaktere bakmıştık. Bu sefer uyumsuzluğun olduğu noktadan önceki sonek kısmına bakacağım, çünkü aranan metni uyumsuz noktanın sağındaki karakterler de birbirine uymazken, sadece uyumsuzluk olan yerdeki karakterin doğru olacağı şekilde kaydırmak yeterli olmayacaktır. Yani bu şekilde bir kaydırmada aranan metnin bulunamayacağı açıktır.

Örneğin aradığımız metin HAABH ise ve aşağıdaki bir durum oluşmuşsa algoritmamız sağdan sola doğru karakterleri kontrol edecek ve en sondaki BH kısmının uyduğunu ve sonraki konumdaki H ve A karakterlerinin uyumsuz olduğunu görecek.

... A B A B H A A H B H ...
              H A A B H

Bu durumda daha önceden anlattığım bad character kuralı aranan metni sadece iki karakter sağa kaydırmayı teklif edecek, çünkü bir sonraki H karakteri iki karakter daha solda.

... A B A B H A A H B H ...
                  H A A B H

Burada ana metindeki sonekin (BH) aranan metinde eşleşen kısımdaki altmetne (AA) uymadığını kolayca görebiliriz. Demek ki bad character kuralı bize kaydırma miktarıyla ilgili yeterli bilgi vermiyormuş. Bu bilgiyi kullanmanın yolu da sonekin aranan metinde daha solda mevcut olup olmadığını kontrol etmek. Eğer varsa bu daha soldaki sonekle uyuşan kısmı ana metindeki sonekin altına getirecek kadar kaydırmak yeterli olabilir. Tabii ki bu noktada küçük bir optimizasyon yapmayı da düşünebiliriz. Örneğin son ekten hemen sonraki uyumsuz karakteri de aranan metindeki bir sonekle uyuşan bir sonraki altmetnin hemen sonunda arayabiliriz ama burada küçük bir sorun karşımıza çıkacak gibi. Hedefimiz sadece aranan metni kullanarak bu kaydırma miktarlarını hesaplamak, böylece aramaya başlamadan önce bir kereliğine bütün bu hesaplamaları yapabiliriz. Elimizde sadece aranan metin varsa da o uyumsuz noktada (yani sonekin hemen solundaki konum) hangi karakterin olduğunu henüz bilmiyoruz. Evet bu ciddi bir engel ama bunu aşmak için o noktada uyumsuz olabilecek bütün karakterler için bu hesapları bir kereliğine yapabiliriz. Buradaki sorun da hem bu bir kerelik işlemin oldukça uzun sürmesi hem de bütün bu bilgiler için hafızada çok fazla yer tutmamızın gerekmesi olacaktır. Bunun yerine çok daha basit bir bilgiyi kullanarak bazı durumlarda işimize yarayacak bir optimizasyon elde edebiliriz ama. O da, aranan metindeki daha soldaki sonek tekrarını ararken bulduğumuz altmetnin solundaki karakterin aranan metinde uyumsuzluğun olduğu karakterden farklı olup olmadığına bakabiliriz. Eğer aynıysa bu altmetin işimize yaramayacaktır çünkü altmetni kaydırdığımız zaman aynı uyumsuzluğu aynı yerde bir kere daha bulacağız. Örneğin aradığımız metnin BABHAABH olduğunu varsayalım ve aşağıdaki durumu inceleyelim.

... A B A B H A A H B H ...
        B A B H A A B H

Sağdan sola baktığımızda bulduğumuz uyumsuzluk üçüncü konumda (H ve A) ve sonekimiz BH. BH dizisini aranan metinde solda aradığımız zaman bir kere daha buluyoruz ama BH’nın hemen solundaki karakter en sonda olduğu gibi yine A. Bu durumda sonekleri altalta gelecek şekilde kaydırırsak aşağıdaki durumu elde edeceğimiz açık.

... A B A B H A A H B H ...
                B A B H A A B H

Yani aynı konumda yine aynı uyumsuzluğu (H ve A) elde edeceğiz. Bu uyumsuzluğun ana metindeki H karakterinden bağımsız olacağına dikkat edelim. Yani soneki aranan metinde sola doğru ararken bu sonekin hemen solundaki karakterin farklı bir karakter olmasına dikkat etmeliyiz. Aynı karakter ise aramaya devam edeceğiz, farklı ise aradığımız kaydırma miktarını bulduk diyeceğiz.

Bu linkte burada anlamaya çalıştığım algoritma için gerken tabloyu hesaplayan bir simulasyon hazırladım.

Bad Character algoritması

Bu yazı ve algoritma dizisinde de metin arama algoritmalarından Boyer-Moore algoritmasını öğrenmeye çalışacağım. Diğer bazı metin arama algoritmalarında olduğu gibi bu algortimada da aranan metin her adımda tek adım kaydırılmıyor, aksine aranan metnin özelliğine göre kaydırma miktarları optimize ediliyor. Boyer-Moore algoritmasının şimdiye kadar öğrendiğim algoritmalara göre iki farklı özelliği var. Birincisi, aranan metin ve ana metin karşılaştırması sağdan sola doğru yapılıyor. İkincisi de kaydırma miktarını bulmak için iki değişik alt algoritma kullanılıyor. Bu yazıda bu iki algoritmadan biri olan Bad Character algoritmasını anlamaya çalışacağım.

Bu algoritma için aşağıdaki animasyonu programlamaya çalıştım.

Bad Character Rule

Bu animasyon başlatıldığında henüz hazırlanmamış bir tablo ve tablonun üzerinde seçilmiş bir aranan metin gösteriliyor. Tabloda normalde bir metinde olabilecek bütün karakterler olmalı (küçük harfler, büyük harfler, rakamlar vb.) ama sadece fikri gösterebilmek için tabloyu küçük tuttum. Animasyonda ana metni kullanmadım çünkü bu algoritma için ana metin değil aranan metne herhangi bir konumda uymayan bir karakter önemli. Bunu da aranan metnin üzerinde hesaplanacak konumda gösterilen bir karakterle göstermeye çalıştım.

Animasyonda aranan metin olarak

 NNAAMAN

dizisini kullandım. Her tablo seçilen aranan metne göre ayrı oluşturulması gerekiyor. Tabloyu şöyle düşünmeye çalıştım. Aranan metinde ana metni sağdan sola doğru karşılaştırdığımızda ana metindeki ilk uyumsuz karakteri en soldaki sütundan buluyoruz. Ardından bu uyumsuzluğun aranan metindeki hangi pozisyonda olduğunu da birinci satırdan okuyoruz. Algoritma bittiğinde bu tablo bize o karakter ve o konum için aranan metni sağa doğru kaç karakter kaydırabileceğimizi söyleyecek.

Bu tabloyu hazırlamak aslında çok kolay ama bu şekliyle tablo oldukça fazla yer tutmakta, çünkü olası her karakter için tabloda yer harcanıyor ama bu ilk versiyon için bu basit yöntemi anlamak yeterliydi benim için. Literatürde bu sorunla ilgili çeşitli çözümler var ve ileride onlara da bakabilirim.

Tablodan sırayla her satırdaki harf için olası her pozisyonu alıyorum ve bu harfi aranan metnin üzerinde o pozisyonda gösteriyorum. Eğer seçtiğim harfler aranan metindeki harf aynı ise tabloda bu noktaya “-” işareti koyuyorum, çünkü bu algoritma sadece uyumsuzluk varken kullanılıyor. Eğer uyumsuzluk varsa aranan metinde sola doğru harfleri tek tek kontrol ediyorum. Seçilen harfle aynı harfi ilk bulduğum konuma kadar aranan metni sağa doğru kaydırabilirim, çünkü aradaki her durumda bir uyumsuzluğun çıkacağı kesin. Eğer bir harfi uyumsuzluğun çıktığı konumdan sonra bir daha bulamazsam da aranan metni uyumsuzluktan bir sonraki konuma kadar kaydırabilirim. Bu şekilde her karakter ve konum için aranan metni ne kadar kaydırmam gerektiğini tabloya işliyorum. Bu şekilde bu basit algoritma da tabloyu oluşturmuş oluyor.

Knuth-Morris-Pratt algoritması

Bu algoritma failure function yazısında oluşturduğumuz tabloyu kullanarak aradığımız metni uyumsuzluğun olduğu konuma göre değişik miktarlarda kaydırmaktadır. Bu şekilde aranan metni her adımda bir karakter kaydırma algoritmasına göre bir iyileştirme elde edeceğiz.

Aşağıdaki linkle animasyon sayfasına ulaşabilirsiniz. Sayfa yüklendiği zaman aranan metin için daha önceki yazıda tanımlanan tabloyu hesaplayacak. Ardından ana metni ve aranan metni gösterip uyumlu karakterleri yeşil renkle, uyumsuz olan ilk karakteri de kırmızı ile gösterecek. Ondan sonra uyumlu ortak metin uzunluğundan tabloda seçilen sütunu yeşi ile gösterip oradan kaydırma miktarını okuyacak. Aranan metin bu miktar kadar kaydırıldıktan sonra aynı işlemleri tekrarlıyor. Animasyon aranan metin bulunana kadar devam ediyor.

Animasyon

Failure Function

Bu seferki algoritma aslında yine başka bir algoritmada kullanılan bir parça olacak. Basit metin arama algoritmasında bulmak istediğimiz metin parçasını ana metin üzerinde her adımda bir karakter kaydırarak üst üste gelen harflerin aynı olup olmadığına bakıyorduk. Bu yazıda bakacağımız algoritma her adımda bir karakter kaydırma sorununa bir çözüm bulmaya çalışacak.

Aradığımız metin parçasındaki harflerin özelliklerini kullanarak bazen birden fazla karakter kaydırma imkanını elde edebiliriz. Yani karakterleri karşılaştırırken fark olan ilk konuma kadar olan karakterlere göre birer karakter kaydırmanın bu başlangıç kısmında bir eşitlik yaratamayacağından emin olabilirsek bundan faydalanarak kaydırma adımını hızlandırabiliriz. Hedefimiz şu: Arama metnindeki ilk uyumsuzluğun konumuna göre kaç adım sıçrama yapmamız gerektiğini söyleyen bir tablo bulmak istiyoruz. Dolayısıyla normal arama işleminde yine karakterleri tek tek kontrol edeceğiz ama ilk farkta bu tablo bize bir sonraki arama için ne kadar sıçrama yapmamız gerektiğini (şansımız iyi giderse birden fazla) söyleyecek.

Wikipediadan aldığım bazı örnekleri vereyim şimdi.

             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W: ABCDABD
i: 0123456

Burada ana metin S ile aradığımız metin de W ile gösterilmekte. Burada i = 3 indeksli karakter ilk uyumsuzluğun olduğu yer. Şimdi W ile gösterilen karakter dizisini birer birer sağa kaydıracağım ama bu sırada S karakter dizisinde algoritmanın henüz görmediği yerlere X koyacağım. Bu X koyulu yerlere karşılık gelecek W karakterlerini de kullanmaya gerek olmayacak çünkü bu karakterleri henüz görmediğimizden buralarda eşitlik olup olmadığını bilmiyoruz.

             1         2  
m: 01234567890123456789012
S: ABCXXXXXXXXXXXXXXXXXXXX
W:  ABC
i: 0123456

İlk kaydırmadan sonra ilk konumda (i = 1) bir eşitsizlik var. Daha bakmaya gerek yok, bir kere daha kaydıralım.

             1         2  
m: 01234567890123456789012
S: ABCXXXXXXXXXXXXXXXXXXXX
W:   ABC
i: 0123456

Yine W parçasının başı yukarıdaki S dizisinin bilinen kısmının sonuyla uyuşmadı. Demek ki bu diziyi iki adım kaydırmak da işe yaramayacak. O zaman aramaya 3 adım kaydırarak devam etmek lazım.

Bu örnekten sonra iki şeye dikkat çekmek istiyorum.

  1. Aradığımız şey aslında W dizisinin başındaki bir dizinin (önek) yine W dizisinin sonundaki bir diziyle (sonek) uyuşup uyuşmadığı. İlk X nerede olursa olsun oraya kadar S dizisiyle yine aynı konuma kadarki W dizileri aynı olduğundan yukarıdaki fikri kullanabiliriz.
  2. İlk bakışta yine her adımda W dizisinin bir önekini bir kaydırıp kontrol ediyoruz gibi görünüyor ve böylece aramada yine her seferinde W dizisini bir karakter kaydırıp basit arama algoritmasına döneceğiz gibi geliyor ama aslında bunu sadece örnek olarak verdim. İleride bu tabloyu aramadan önce sadece arama metnini kullanarak bir kereliğine oluşturabileceğimizi göreceğiz.

Örnek:

             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:            ABCDABD
i:            0123456

Burada ilk uyumsuzluk i = 6 konumunda oluşmuş. O zaman ana metinle aranan metin arasında i = 5 noktasına göre tam uyum vardır. O zaman aranan metnin o noktasına kadarki önekiyle ilgileneceğiz.

             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABXXXXXX
W:            ABCDAB
i:            012345

Şimdi aranan metni birer kaydırdığımızda kendi önekiyle yine kendi soneki arasındaki uyumlara bakalım.

             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABXXXXXX
W:             ABCDAB
i:            012345

i = 0 noktasında uyumsuzluk var. Yine kaydırmamız lazım.

             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABXXXXXX
W:              ABCDAB
i:            012345

Uyumsuzluk devam ediyor. Yine kaydıracağız.

             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABXXXXXX
W:               ABCDAB
i:            012345

Hala uyum bulunamadı. Kaydırmaya devam ediyoruz.

             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABXXXXXX
W:                ABCDAB
i:            012345

Burada sonunda aranan W metninin iki karakterlik öneki ile yine W nin (tabii ki 6 karakterlik kısmı için, bu uzunluk en baştaki ilk uyumsuz nokta ile belirleniyor) iki karakterlik soneki arasında bir uyum bulundu. Demek ki tablomuzda ilk uyumsuzluk 6. konumda bulunursa 4. konuma kadar kaydırılmalı diye bir kayıt bulunmalı. Algoritma bu uyumsuzlukla karşılaştığında birer birer kaydırmak yerine hemen 4 karakter kaydırarak aradaki kontrolleri gönül rahatluğıyla atlayabilir.

Burada bir gözlemden daha bahsedeyim. Sağa doğru birer birer kaydırırken ilk uyumlu önnek, sonek çiftini bulduğumuzda kaydırmayı kesmemiz lazım. Yani en uyumlu olan en uzun önek, sonek çiftini arıyoruz. Bunun nedeni de aslında kolayca anlaşılabilir. Aranan metni kaydırdıkça bu metnin en son kısmı hep X ile gösterdiğimiz bölüme kayıyor, yani bu bölümde de uyumun devam etme hatta aranan metnin tamamının bulunma şansı var. Dolayısıyla bulunan ilk önek, sonek uyumunda durulmalı ki bu ihtimal gözden kaçırılmadan kontrol edilebilmeli.

Bir küçük nokta daha var ama onu zaten farketmişsinizdir. Önek ve soneklerin uyumuna bir kere kaydırdıktan sonra bakıyoruz. Kaydırmadan bakarsak her zaman uyumlu olurlar ve bu durumda algoritmamız kaydırmaya gerek yok diye saçma bir düşünceye kapılabilir.

Aşağıdaki linkten animasyon sayfasına girerek bu tablonun başta ana metne ihtiyaç duymadan nasıl hazırlandığını görebilirsiniz. Yani tabloyu arama algoritmasının en başında üretebiliriz ve sonra ana metinle beraber kolaylıkla kullanabiliriz. Bu kullanımı da başka bir yazı ve animasyonda göstereceğim.

Tablonun üzerindeki kısım önce indeks listesiyle başlıyor. İkinci satır ana metnin o ana kadar uyum sağlanmış kısmını gösteriyor. Bu farazi bir ana metin tabii ki, bütün işlemi aslında aranan metinde yapmama rağmen bu ana metin kısmını da göstermek istedim. Aranan metindeki uyumsuzluğun olduğu ilk nokta dolaylı olarak da ana metni o noktaya kadar belirlediği böylece daha kolay anlaşılır belki. Üçüncü satır aranan metnin tamamını gösteriyor. Son satır ise simulasyon sırasında kaydırılan kısmı gösteriyor. Yukarıdaki örneklerdeki W kısmı (ana metinle tam uyum sağlayan kısmı tabii ki) yani.

Tablonun başlık satırı indekslerden oluşuyor, yani yukarıdaki örneklerdeki i satırı. İkinci satır önek ve soneklerdeki en uzun uyumlu karakter dizisini gösteriyor. Son satır da algoritmanın indeks numaralı pozisyondaki uyumsuzluk için arama metnini kaç karakter kaydetmesi gerektiğini gösteriyor. Dikkat ederseniz index – maksimum uzunluk = kaydırma miktarı gibi bir eşitlik de var.

Simulasyon

Hebb öğrenme kuralı

Uzun zamandır algoritma simulasyonlarına ve özellikle de yapay sinir ağlarına ara vermiştim. Bu sefer bu alana Hebb öğrenme kuralıyla bir dönüş yapmak istedim.

Bu basit kural Donald Hebb’in 1949 yılında yayınlanan “The Organization of Behaviour” kitabında tanımlanmıştır. Eğer bir nöronun bir aksonu başka bir nörona yeterince yakınsa ve bu nöron diğer nöronun ateşlenmesinde sık sık bir rol oynuyorsa aradaki bu bağlantı güçlenir.

Evet , bu kural biyolojik bir şekilde tanımlanmış. Çok normal, çünkü Donald Hebb nöropsikoloji alanında çalışan bir psikologtu. Peki yapay sinir ağlarında bu kuralı nasıl düşünebiliriz?

Bu şekilde simulasyonda da kullandığım basit bir örneği görüyorsunuz. Şistemin girdileri x1 ve x2 değerleri. Bunları başka nöronların çıktıları olarak da düşünebilirsiniz. Bu çıktılar w1 ve w2 ağırlıklarıyla çarpıldıktan sonra nöronda toplanıyor ve nöronun ateşleyip ateşlemediğine bakılıyor. Eğer ateşlemişse y çıktısı 1 değerini alıyor, ateşlememişse -1 değerini.

Kuralı şekle göre yazarsak yapay sinir ağlarında kullandığımız şekli şöyle oluyor:

\(\Delta w = \eta \cdot x \cdot y \)

Burada \(\Delta \) ağırlıklardaki değişimi göstermekte. \(\eta \) da öğrenme faktörü oluyor, genelde küçük bir sayıdır ve simulasyonda 0.1 değerini kullandım.

bu gösterimde x ve w vektördür. Bunları daha açık yazarsam şöyle olur.

\(\Delta w1 = \eta \cdot x1 \cdot y \)

\(\Delta w2 = \eta \cdot x2 \cdot y \)

Hesapta kullandığım şekli de şöyle:

\(w1 (sonraki) = w1 (önceki) + \eta \cdot x1 \cdot y \)

\(w2 (sonraki) = w2 (önceki) + \eta \cdot x2 \cdot y \)

Her adımda önce bir girdi seçiliyor. Yani o adım için x1 ve x2 değerleri seçiliyor. Ardından y çıktısı o anki ağırlık değerleriyle hesaplanıyor. Ardından o girdiler ve çıktılar için ağırlıkların yeni değerleri yukarıdaki formüllere göre hesaplanıyor ve ağırlık değerleri güncelleniyor.

Simulasyonda bu modeli yukarıda açıkladığım şekilde kullandım. Simulasyon başlatıldığında ağırlıklara rastgele değerler atanıyor. Simulasyonun altında ağırlıkları nasıl güncellediğimi gösterdim. En altta ise öğrenme için kullandığım girdi noktalarını bir koordinat sisteminde kırmızı noktalarla ve ağırlık vektörünün de bu noktaları birbirinden nasıl ayırdığını gösterdim. Bu öğrenmede sistem kendi kendine öğreniyor, yani sisteme kullanılan nokta için ulaşılması gereken çıktı değeri hiçbir şekilde verilmiyor. Bu durumda sistem verilen noktaları kendine göre sınıflandırıyor. Tabii ki sadece iki nokta ile bu kuralın öğrenme yeteneği yeterli bir şekilde anlaşılamaz ama en azından algoritmanın nasıl çalıştığını görebiliriz.

Simulasyon