Automatic knot adjustment using Artificial Immune

Transkript

Doç.Dr.Erkan ÜLKER, Selçuk Üniversitesi Mühendislik F, Bilgisayar Mühendisliği Bölümü
17.05.2014
Sayfa 1
Automatic knot adjustment using an Artificial Immune System for B-spline
curve approximation
Erkan ÜLKER, Ahmet ARSLAN
Özet
Ters mühendislik gerçek nesneleri mühendislik modelleri veya kavramlarına
dönüştürerek modellemektedir. Önce lazer tarayıcılar yada kameralar gibi araçlarla nesnelerin
yüzeylerinden örneklem noktaları elde edilir. Daha sonra örneklem noktaları geometrik
modelleme metotlarından birisi kullanılarak bir yüzeye yada şekile uydurulur. Yüzey
modellemeden önce yüzey üzerindeki eğrilerin modellenmesi gereklidir. Çok sayıda veriden
iyi bir B-spline eğri modeli bulmak için genelde düğümler değişkenler olarak ele alınır. Sonra
çok sayıda lokal optima ile sürekli nonlineer ve çok değikenli optimizasyon problemi olarak
eğri modellenmeye çalışılır. Bu nedenle global optimuma ulaşmak zordur. Bu makalede
orjinal problemi [1] ve [2] deki gibi ayrık bir kombinasyonel optimizasyon problemine
dönüştürdük. Sonra yapay bağışıklık sistemi vasıtasıyla dönüştürülmüş problemi çözen yeni
bir metot önerdik. Düğüm yerleşim adaylarını antikorlar olarak düşündük. Akaike’nin Bilgi
Kriterinden faydalanıp duyarlılık ölçütünü tanımladık. The proposed method determines the
appropriate number and location of knots automatically and simultaneously. Ayrıca herhangi
bir öznel parametreye yada iyi bir iteratif arama için iyi seçilmiş bir başlangıç populasyonuna
ihtiyacımız yoktur. Metodun verimliliği ve etkinliğini göstermek için bazı örnekler de
verilmiştir.
I. Introduction
Eğri veya Yüzey rekonstrüksiyon olarak da bilinen bir eğrinin/yüzeyin 2D/3D şeklini
geri alma problemi, son birkaç yıldır daha fazla ilgi almıştır. Literatürde iki farklı yönelim
vardır[10]. Birinci yönelim de yazarlar, verilmiş bir kesitler yada noktalar kümesinden bir eğri
yada yüzey modeli bulma problemini ele almışlardır. Bu, bir nesnenin genelde (3D lazer
tarama, ultrason görüntüsü, manyetik rezonans görüntüsü, bilgisayar tomografisi vesaireden
elde edilmiş) 2-boyutlu kesitler dizisi ile tanımlandığı CAD/CAM, biomedikal ve tıp bilimi
gibi araştırma ve uygulama alanlarının çoğunda tipik bir problemdir. İkinci yönelime dahil
olan diğer farklı yaklaşımlar verilmiş bir veri noktaları kümesinden eğriler/yüzeyler inşa
etmeyi içermektedir. Bu veri noktalarının doğasına bağlı olarak iki farklı yaklaşım
kullanılmıştır: enterpolasyon ve tahmin. İnterpolasyonla uydurma formunda parametrik eğri,
verilen veri noktaları kümesinin hespinden geçmeye zorlanır. İnterpolasyonla verinin
uydurulması tekniği; sayısallaştırılmış çevre çizgisini tanımlayan veri noktaları yeterince
doğru ve pürüzsüz olduğu zaman uygun olmaktadır. Tahminle veri uydurma formunda
parametrik eğri, verilen veri noktaları kümesine yakın geçer ama onların hespinin üzerinden
geçmesi zorunlu değildir. Birkaç uzaklık kriteri yardımıyla, verilen veri noktaları kümesi ile
tanımlanmış olan gerçek eğrinin bütün şeklini koruma garanti edilmez. Uzaklık (uydurulan
eğri ve verilen veri noktaları arasındaki uzaklık) genelde, uydurulan eğriye bir normal
boyunca yada bir koordinat boyunca ölçülür. Tahmin teknikleri özellikle veri doğru olmadığı
ama ölçüm hatalarına bağlı olduğu zaman tavsiye edilmektedir. Tahmin tekniğini seçmede
diğer önemli neden eğri formları gibi sonsuz sayıda veriyi enterpole ederek yüzeyler bulmada
gereksinim duyulan büyük hesaplamsal efor olmasıdır. Tahmin edilmiş eğri/fonksiyon toplam
hatayı minimize eder.
Tahmin metoduna girdi olarak sunulan veri Dağınık veri olduğunda (yani herhangi bir
sırası yada düzeni olmaksızın rasgele dağılan noktalar kümesi) ikinci bir problem daha ortaya
17.05.2014
Sayfa 2
çıkmaktadır. Ne yazık ki Hermit enterpolasyonu, Bezier eğriler yada B-splin eğrilere benzer
tüm standart enterpolasyon ve tahmin metotları bir noktalar sırası gerektirmektedir. Bu
yüzden dağıtık veriye eğer bu metotları uygulamak isterseniz veriyi sıralamak zorundasınız.
Yoğun ve gürültülü noktaların sıralanması üzerine yapılmış çalışmalar için [36-39]
kaynaklarına bakabilirsiniz.
Ayrıca B-spline eğri yada yüzey uydurma çok iyi bir parametrizasyon modeli
gerektirmektedir [4]. Örneğin en küçük kareler uydurma (LSQ) icra etmek için
sayısallaştırılmış noktaların parametre değerlerinin tanımlanması gibi. Prosedür,
parametrelerin öngörüsü (kestirimi, tahmini) ile başlar ve sonra öngörülen parametreler için
kontrol noktalarını öğrenmek adına bir LSQ gerçekleştirilir. Parametrelerin seçimi üzerine
sayısız çalışmaların yapılmış olmasına rağmen yine de yukarıda belirtildiği gibi özellikle
noktalar düzensiz dağıldığı ve karmaşık bir temel eğri yada yüzey üzerinde uzandıkları zaman
parametrelerin daha iyi hesabı günümüz yaklaşımları ile zor olmaktadır [4]. Veri uydurmada
bir spline’ı başarıyla kullanmak için anahtar nokta iyi düğümlerin tanımlanmasıdır. Bu
nedenle çok değişkenli ve multimodal nonlineer optimizasyon probleminin çözülmesi
gereklidir [1]. İyi model; modeldeki parametre sayısı ve model ile temel veri fonksiyonu
arasındaki fark mümkün olduğunca küçük olacak biçimde tahmin edilen modeldir. Büyük veri
için bu problemle, olası yerel optimadan kaçınan ve aynı zamanda iteratif tarzda arzulanan
çözümü elde eden optimizasyon algoritmalarıyla uğraşılması gereklidir.
Bu problemlere açık çözüm, önemli bir zaman ve bellek korumamızı bize sağlayan bir
tahmin şeması göz önüne almaktır. Bu yaklaşımda eğri/yüzey rekonstrüksiyon metotlarının
amacı aşağıdaki gibi belirlenmiştir: bilinmiyen bir U eğrisi/yüzeyi üzerinde uzandığı
varsayılan bir X örnek noktalar kümesi verildiğinde U ‘ya yakın olan bir S B-spline
eğri/yüzey modeli inşa etmektir. Tabii ki bu, “şekil kalitesi” ‘ni feda etmeksizin imalat işlemi
ile uyumlu verilmiş bir tolerans hatasını içermektedir. Burada üç farklı kriter önemlidir[11]:
Eğrinin/Yüzeyin “pürüzsüzlüğü”, “poligon düzenliliği” ve Bulunan eğriden/yüzeyden verilen
noktalar kümesine uzaklık. Bu problem, parametrik metotlar, fonksiyon rekonstrüksiyon,
örtük (implicit) yüzeyler vs gibi çeşitli görüş noktalarından analiz edilmiştir [10]. Bizim
çalışmamızın amacına benzer olarak literatürdeki son çalışma Li ve arkadaşları[35] nın veri
noktalarının ayrık kavislerini dikkate alarak yaptıkları adaptif düğüm yerleştirme çalışmasıdır.
Yapay zeka teknikleri açısından bakıldığında bu probleme en dikkat çekici ve umut
verici yaklaşımlardan birisi sinir ağlarına dayanmaktadır. Eğri tasarımında sinir ağlarının ilk
kullanıldığı çalışma [18] ve [12] de verilmiştir. Bundan sonra Kohonen ağları [13-14, 19, 20],
self-orgaized maps [21,22] ve Fonksiyonel ağların [10] kullanıldığı çalışmalarla yüzey
tasarımlarına genişleme sağlanmıştır. Yapay sinir ağı ile ilgili son çalışma Kohonen sinir
ağının sayısal kontrolü üzerinedir [15]. Ayrıca Genetik algoritma[1-4], simulated annealing,
simulated evolution[5] gibi evrimsel optimizasyon tekniklerinin çoğu bu probleme başarıyla
uygulanmaktadır. Modified continuous reactive tabu search [6], Multi objective optimization
[7] ve an Error-bounded method based on Dominant Point selection [8] gibi geleneksel
optimizasyon yöntemleri ilede probleme çözümler aranmıştır. R. Goldenthal ve M. Bercovier
[23,24] Eğri şeklini tasarlamak için bir maliyet fonksiyonu kullanımı yaklaşımını kullanan bir
stratejiyi benimsemişlerdir ve Maliyet fonksiyonunu çözmek için bir genetik algoritmanın
kullanılması maliyet fonksiyonlarının minimizesine verimli bir yol olarak ispatlamışlardır.
Bilim adamları kompleks problemlerin çözümünde tabiattan esinlenmelerinin sonucu
olarak Yapay sinir ağları ile başlayan insanın iç yapısındaki sistemleri modelleme akımında
Darwin’in evrim prosesini temel alan evrimsel algoritmalardan sonra insan bağışıklık
sisteminin modellenmesiyle Yapay bağışıklık sistemleri üretilmiştir. İnsan bağışıklık sistemi
ise oldukça güçlü, adaptif, dağıtık, bellek bulunduran, kendi kendine organize olan, güçlü
örüntü tanıma yeteneğine sahip ve yabancı etkenlere karşı tepki vermek için evrimsel bir
yapısı olan bir sistemdir [33]. Bu sistemin yetenekleri bilim adamları, mühendisler,
17.05.2014
Sayfa 3
matematikçiler, filozoflar ve diğer araştırmacıların ilgisini çekmiştir. Bunun sonucunda
İnsanın Bağışıklık prensiplerini uygulayan araştırma alanları hızla gelişmeye başlamıştır ve
bu alan Yapay Bağışıklık Sistemleri – YBS (Artificial Immune Systems) veya Bağışıksal
Hesaplama (Immunological Computation) olarak adlandırılmıştır.
Genetik algoritma ile kıyaslandığında temel bileşenlerindeki benzerliklerine rağmen
AIS’in GA üzerine üstünlükleri ispatlanmıştır[41]. Bizim açımızdan en önemli özelliği ise
amaç fonksiyona ulaşmadaki yakınsama hızının GA’dan daha iyi olmasıdır. Bu nedenle
tercihimizde ön plana çıkmıştır. Literatürde ise AIS kullanılarak yukarıdaki problemlere
çözüm aranmış bir çalışma yoktur. Sunulan makalede; Düğümlerin yerlerinin ve sayılarının
otomatik yerleşimi amaçlanmış ve B-spline eğriler vasıtasıyla verilen 2D veri noktaları
kümelerini uydurmak için Yapay bağışıklık sistemi metodolojisi uygulanmıştır.
Makalenin düzenlenişi şöyledir. Sonraki başlıkta B-spline eğri uydurma problemi
açıklanmıştır. Sonra yapay bağışıklık sistemlerinin detayına girilmiştir. Önerdiğimiz YBS ile
otomatik düğüm yerleştirme metodumuzun çalışma prensibi açıklandıktan sonra bazı sayısal
sonuçlarla metodumuzun etkinliği gösterilmiştir. Sonuçlar ve sonraki çalışmalarla makale
sonadırılmıştır.
II. Description of the problem
II.1. B-spline curves
B-spline’lar, 1940’larda çeşitli araştırmacılar tarafından araştırılmıştır. Ama de Boor
çalışmasını yayınlayıncaya kadar [9] endüstride popularite kazanmamıştır. B-spline eğriler
yerel etki alanlarına sahip geçişme fonksiyonları kullanır. Bir başka deyişle, B-spline
eğrilerinin kullandığı geçişme fonksiyonları kendilerine ait kısımlar dışında sıfıra eşittir.
Bundan dolayı eğrinin şekli sadece kendisine komşu birkaç kontrol noktasına bağlıdır. Bspline eğrilerinin bir başka önemli avantajı ise B-spline eğrilerinin derecesi ile kontrol
noktaları sayısının birbirlerinden bağımsız olmasıdır. Bu avantajlara karşın B-spline
eğrilerinin programlanması Bezier eğrilerine göre daha zor ve karışıktır. pi (i=0,1,2,...,n)
şeklinde n+1 adet kontrol tepesi (yada de Boor noktaları) verildiğinde, düzeni k (yada
derecesi d,ve k=d+1) olan bir B-spline eğrisi aşağıdaki gibi tanımlanır:
n
P(u)  i 0 pi N i ,d (u)
(1)
Bu benzerliğe rağmen geçişme fonksiyonlarının farklı olması Bezier ve B-spline
eğrileri arasında şu temel farklılıkları doğurur: ilk olarak, u parametresinin alabileceği
değerler [0,1] aralığında olmayabilir. Bir diğer fark ise Ni,d geçişme fonksiyonlarının
derecesinin kontrol noktalarının sayısına bağlı olmayıp, (d-1). dereceden olmasıdır.
Cox-deBoor özyinelemeli fonksiyonları B-spline eğrilerinin temelini oluşturur ve Bspline eğrilerinin geçişme fonksiyonları Cox-deBoor fonksiyonları kullanılarak hesaplanır.
T={t0,t1,...,tr-1,tr}, düğümler olarak bilinen bir azalmayan gerçel sayılar dizisidir. T, düğüm
vektörü olarak adlandırılır. k dereceli (yada k-1) i-inci B-spline basis fonksiyonu Nik(s)
aşağıdaki gibi yinelenme ilişkileri ile tanımlanmaktadır.
1, t i  u  t i 1
N i ,1 (u )  
0, aksi takdirde
u  ti
t u
N i ,k (u ) 
N i ,k 1 (u )  i  k
N i 1,k 1 (u )
t i  k 1  t i
t i  k  t i 1
17.05.2014
(2)
Sayfa 4
B-spline eğriler hakkında daha detaylı bir tartışma [16] de bulunabilir.
II. 2. B-spline ile veri uydurma
Eğri rekonstrüksiyon problemlerinde giriş (input), organize edilmemiş bir noktalar
kümesidir, bu nedenle eğri derecesi, düğümler ve kontrol noktalarının hepsi bilinmiyenlerdir.
Bunun için düzensiz veriye parametrik eğri/yüzey uydurma non-lineer en küçük kareler
problemi olarak formülleştirilebilir[34]. Rekonstrüksiyon metotlarının tüm amacı, temel
stratejisi aşağıdaki gibi olan bu değerleri tanımlamaktır[17]:
1. Eğri derecesi (k), kontrol noktaları sayıları (n) ve düğüm değerleri tj sabit
verilir.
2. Her bir dağınık Fj noktasına bir C(tj) parametre değeri atanır.
3. C t j   Fr sistemi çözülür yada
 C tj   F
2
j
minimize edilir.
j
B-spline eğriler açısından bu stratejinin kritik noktası, verilen verinin
parametrizasyonu olarak sıklıkla başvurulan ikinci adımdır. Parametrizasyon, her bir noktaya
parametre değerlerinin nasıl atanacağının yoludur. Burada normalde, çeşitli kısıtlama ve
varsayımlar ortaya konulmuştur. Birileri, bir optimizasyon problemi içinde bilinmiyen
parametreler olarak atanan değerleri gözönüne almaya çalışabilir, ama çok geniş miktarda veri
için bu yaklaşım, çeşitli bilinmiyenlerle kompleks bir non-lineer sisteme sebep olur. Düzensiz
veriye parametrik eğri uydurma probleminde kontrol noktalarının ayarlanması problemi
üzerine ilgili okuyucular detay bilgiler için Yang ve arkadaşlarının [40] çalışmasına
başvurabilirler.
Yukarıdaki strateji temelinde önerilen çalışmamızda B-spline eğri tahmini için izlenen
yöntem burada açıklanacaktır. Bu makalede orjinal problemi ayrık bir kombinasyonel
optimizasyon problemine dönüştürme işleminde Yoshimoto ve ark [1], Safraz ve ark [2] ve
Raza[3] ‘nın çalışmalarındaki matematiksel temelden faydanılmıştır. Sonra yapay bağışıklık
sistemi vasıtasıyla dönüştürülmüş problemi çözen yeni bir metot önerilmiştir.
Farzedelim ki uydurulacak veri, x-ekseninin [a,b] kapalı aralığında verilmiş olsun.
Buna aşağıdaki gibi bir ifade yazabiliriz
Fj  f ( x j )   j , ( j  1,2, , N )
(3)
Bu denklemde f(x) fonksiyonu (bilinmeyen) verinin temelinde olan fonksiyondur ve j
bir ölçüm hatasıdır. ti i  1  m, 2  m, , n  m ise veri uydurma için bir spline’ın düğümleri
olsun. Burada n harfi (a,b) aralığında yerleşmiş olan ti i  1, 2, , n düğümlerinin sayısıdır, m
terimi ise bir Nm,i(x) B-spline’ının düzenidir (derece+1). [a,b] kapalı aralığının sonlarında a ve
b değerlerine düğümler eşitlenir.
a  t1m   t0 , 
(4)


b  t n1   t nm .
Bu ayarlamada f(x) için bir model fonksiyonu aşağıdaki gibi verilir.
nm
S ( x )   c i N m ,i ( x )
(5)
i 1
Burada ci ifadesi bir B-spline katsayısıdır.
Denklem (3) deki B-spline’lar denklem (2) ile hesaplanırlar. Denklem (2) de,
düğümler sadece kesirlerin payında değil aynı zamanda paydasındadır. Bu yüzden denklem
(5) ile verilen bir spline nonlineer bir düğümler fonksiyonudur. Denklem (5), en küçük kareler
metodu vasıtasıyla denklem (3) ile verilen veriye uydurulur. Sonra kalanların karelerinin
toplamı olan Q1 aşağıdaki gibi yazılır.
17.05.2014
Sayfa 5
Q1   w j S ( x j )  F j  ,
N
2
(6)
j 1
Burada wj verinin ağırlığıdır ve N>n+m dir. Çalışmamızda tüm ağırlık değerleri 1
alınmıştır. Q’nun altindisi verinin boyutu anlamındadır. B-spline katsayıları olan ci
(i=1,2,...,n+m), minimizasyon denklemi (6) nin koşulu ile tanımlanır. İyi bir model bulmak
için, bununla beraber içteki ti i  1, 2, , n düğümlerinin sayıları ve yerleri, mümkün olduğu
kadar kesin tanımlanmalıdır. Çalışmada, verilen noktalar kümesindeki her bir noktaya bir
parametre değerinin atanması ve uygun bir düğüm vektörünün seçimi için vektördeki
düğümlerin belirlenmesinde Centripetal metot kullanılmıştır.
Yukarıda açıkladığımız gibi minimize edilen amaç fonksiyon denklem (6) dır ve amaç
fonksiyonun değişkenleri B-spline katsayılar ve içteki düğümlerdir [1-3]. B-spline katsayıları
lineer parametrelerdir. Bununla birlikte içteki düğümler nonlineer parametrelerdir, çünkü S(x)
fonksiyonu nonlineer bir düğümler fonksiyonudur. Bu minimizasyon problemi multimodal
optimizasyon problemi olarak bilinmektedir [6].
III. Artificial Immune Systems
İnsan bağışıklık sistemi neredeyse sınırsız sayıda virüs, bakteri, mantar, parazit gibi
hastalık yapıcı mikroorganizmalara karşı vücudu koruyan kompleks bir ağ yapısı gibidir. Bu
yapı potansiyel olarak çok zeki hesaplama uygulamalarına sahip , paralel ve dağıtılmış bir
adaptif (kendi kendine öğrenebilen) sistemdir. Buna ek olarak Bağışıklık sisteminin şu
özellikleri bilim adamlarının ve araştırmacıların ilgisini çekmiştir [25]: Uniqueness, Yabancı
etkenin tanınması, Anormal olanı bulma, Distributed Detection, Noise Tolerance, Imperfect
Detection, Reinforcement Learning and Memory. Böyle bir yapının modellenmesi
problemlerin çözümünde yeni bir yaklaşım olarak kullanılabilir. Bu yaklaşım Artificial
Immune System (YBS)’dir. Zeki hesaplama tekniği sayesinde, örüntü tanıma, veri analizi,
sınıflandırma, öğrenme, hata algılama, optimizasyon, bellek kazanımı, robotik, bilgisayar
güvenliği gibi bir çok alanda yapay bağışıklık sistemleri uygulanmıştır[26].
Bağışıklık sistemindeki etkileşimlerin sistem bazında ifade edilerek bir YBS
oluşturulması için şunlara ihtiyaç duyulur. (i) Sistemi oluşturan birimlerin gösterimi, (ii)
Sistemdeki birimlerin birbirleri ve çevre ile olan etkileşimlerini hesaplamak için bir
mekanizma, (iii) Bazı adaptasyon prosedürleri. Bunların detayları aşağıda verilecektir. YBS
hakkında daha detaylı bilgilere [25-27] ‘den ulaşılabilir.
Sistemi oluşturan birimler (Antijen ve Antikor)
Her sistemin temel uygulama alanıdır. Sistemi oluşturan birimlerin Antijen ve Antikor
gösterimi için en çok kabul gören ve kullanılan yaklaşım Perelson ve Oster’in 1979 yılında
ortaya attıkları şekil uzayı yaklaşımıdır [28]. Antibody-Antigen gösterimi kısmen etkileşim
derecesini hesaplamada kullanılan uzaklık ölçüsüne karar verecektir. Matematiksel olarak bir
molekülün genelleşmiş şekli ya bir antigendir yada bir antibody’dir. Molekülü m ile
gösterecek olursak Antigen yada antibody; L boyutlu gerçel-değer uzaylı bir nokta olarak
kabul edilen m={m1, m1,..., mL} şeklinde gerçel değerli koordinatların bir kümesi ile
gösterilebilir ve mSL dir. Burada S şekil uzayıdır. İnsan bağışıklığının tamamlayıcılık
özelliği şekil uzayında uzaklık kavramı ile modellenmiştir. Şekil uzayı gösteriminde
çoğunlukla Antigen’ler direkt değil tersleri alınarak gösterilirler. Şekil 1.a ‘da iki Antibody ve
bir antigen’in şekil uzayı gösterimi vardır. Şekil 1.b’da ise Şekil 1.a’da verilen A antigen’inin
tamamlayıcı gösterimi verilmiştir. Etkileşimler için kullanılan uzaklık kriterine göre şekil
17.05.2014
Sayfa 6
uzayına isim verilir. Öklit uzaklığı kullanıldığında Öklityen Şekil uzayı, Manhattan uzaklığı
kullanıldığında Manhattan şekil uzayı, ve Hamming uzaklığı kullanıldığında Hamming şekil
uzayı olarak adlandırılır [27].
Şekil 1.a) Şekil uzayı gösterimi b) Şekil uzayında tamamlayıcı gösterim.
Etkileşimleri hesaplayan mekanizma (Duyarlılık ölçütü)
Etkileşimleri hesaplamak için bir mekanizma kullanılmalıdır. Antijen ve antikor
arasındaki etkileşimler bir duyarlılık ölçütü kullanılarak modellenebilir. Bir antigen ve bir
antibody arasındaki affinity, iki dizi (yada vektör) arasındaki herhangi bir uzaklık ölçüsü
yoluyla tahmin edilebilen göreceli uzaklıkla ilgilidir. Şekil uzayında bağışıklık sistemindeki
iki hücreyi temsil eden iki nokta birbirinden ne kadar uzakta ise bu iki hücre arasındaki
tamamlayıcılık o kadar fazladır.örneğin Şekil 1’de A Antigen’i ve B antikor’u arasında iki
çeşit fizikokimyasal etkileşimin olduğu kabul edilmiştir. Dolayısıyla etkileşimleri temsilen iki
eksen vardır ve şekilde çizilmiştir. Etkileşimlerde iki teorem vardır; maksimum etkileşim için
maksimum uzaklık ve maksimum etkileşim için minimum uzaklık. Şekil 1.a için birinci
teorem, şekil 1.b için ikinci teorem geçerlidir. Bundan dolayı Şekil 1.a’da A antijeni ile C
antikoru arasındaki uzaklık B antikorundan fazla olduğu için A antijeni ile C antikoru
arasındaki etkileşimin şiddeti A antijeni ile B antikoru arasındakinden daha fazladır. Şekil
1.b’de ise A antijeni ile C antikoru arasındaki uzaklık B antikorundan daha az olduğu için A
antijeni ile C antikoru arasındaki etkileşimin şiddeti A antijeni ile B antikoru arasındakinden
daha fazladır. Antigen ile Antibody arasındaki uzaklıklar farklı yöntemlerle hesaplanabilir.
Eğer Antigen ve Antibody’u simgeleyen m vektörleri gerçel değerli vektörler ise Öklit yada
Manhattan uzaklık ölçütleri kullanılabilir. Ab={Ab1, Ab2,..., AbL} antikoru ve Ab={Ag1, Ag2,...,
AgL} antigen’i arasındaki Öklit uzaklığı denklem (7) ile Manhattan uzaklığı ise Denklem (8)
ile hesaplanır.
D
D
  Ab  Ag 
  Ab  Ag 
L
i 1
2
i
i
(7)
i
i
(8)
L
i 1
Antijen ve Antikorlar gerçel değerli vektörler yerine binary sembollerle ifade
edilirlerse Hamming uzaklık ölçütü kullanılır. Bu durumda Antikorun kapsamı, şekil
uzayındaki tüm antijenlerin tanınması için minimum antikor sayısının hesaplanması, binary
17.05.2014
Sayfa 7
uzaklık hesabı ve bağlanma değerlerinin değerlendirilmesi gerekmektedir. Detaylı bilgiye
[27] den ulaşılabilir.
Literatüre bakıldığında uzaklık ölçütü olarak çoğunlukla Öklit uzaklıt ölçütü
kullanıldığı için [25] çalışmamızda bu ölçüt tercih edilmiştir.
Adaptasyon prosedürü (Klonal seçim algoritması)
Adaptasyon prosedürleri, sistemin zamanla nasıl değiştiğini modeller. Bunlar, bir
bağışıklık fonksiyonu, işlemi ya da teorisi kullanılarak oluşturulur. Klonal seçme algoritması
[29], Negatif seçim [30] ve bağışıklık ağları [31] en çok kabul gören yöntemlerdir. Biz
bunların içinde çalışmanın amacına en uygun olan adaptasyon prosedürünün Klonal seçim
algoritması olduğuna karar verdik. Bu nedenle klonal seçim algoritması daha detaylıca
aşağıda ale aldık.
Bağışıklık sisteminde duyarlılık olgunlaşması sırasında bir çok seçme mekanizması
devreye girer. De Castro et al [32] duyarlılık olgunlaşmasındaki işlemleri baz alarak Klonal
Seçim Algoritmasını ortaya atmış ve oluşturdukları algoritmayı karekter tanıma, optimizasyon
gibi problemlere uygulayarak performansını analiz etmişlerdir. Algoritma, iki esası temel alır;
çoğalma için sadece antijeni tanıyan hücreler seçilirler, Seçilen ve çoğalan hücreler duyarlılık
olgunlaşması işlemine tabii tutularak Antijene olan duyarlılıkları arttırılır. Algoritmanın akış
şeması Şekil 2’de gösterilmektedir.
Şekil 2. Clonal Selection Algorithm (De Castro et al [32])
Algoritmanın Adımları şöyle sıralanabilir.
 aday çözümlerin bir kümesi (P) üretilir, hafıza hücrelerinin (M) alt kümesi
populasyona eklenir.(P=PR+M)
 Bir affinite (affinity) ölçüsü kullanılarak populasyonun (Pn) en iyi n bireyine
karar verilir(Seçim)
 Populasyonun bu n bireyi çoğaltılır (klonlama), klonların geçici bir
populasyonu verilir. Klonun boyu antijenin affinitesinin artan bir
fonksiyonudur.
 Bir hipermutasyon şemasına klonların populasyonu uygulanır. Burada
hipermutasyon antijenle antikorun affinitesine orantılıdır. Olgunlaşan antikor
polulasyonu üretilir(C*)
17.05.2014
Sayfa 8


C*’den hafıza kümesine(M) birleştirilen gelişmiş bireyler tekrar seçilir. P’nin
bazı üyeleri C*’nin gelişmiş diğer üyeleriyle değiştirilebilir.
Yeni bireylerle d antikorları değiştirilir. Düşük affinitili hücrelerin
değişitirilmesi ihtimali daha yüksektir.
Bu algoritma kompleks makine öğrenmesi araçlarına uygun bir evrimsel strateji
sunar. Öğrenme ve hafıza kazancı gibi alanlarda performans sağlar. Algoritmanın ikili
(binary) karakter tanıma, çok-modlu ve kombinasyonel optimizasyon , bağışıklık ağ teorisi
gibi alanlarda uygulaması vardır. Algoritma yapı olarak Genetik algoritmayı andırmaktadır.
Ama De Castro et al uygulamalar sonucunda görmüşlerdir ki, Klonal seçim algoritması
Genetik algoritma ile karşılaştırıldığında lokal optimumlardan oluşan çok çeşitli bir çözüm
seti üretebilir. Genetik algoritma ise tüm populasyonu en iyi bireye benzetmeye çalıştırır.
Gerçekte iki algoritmanında kodlama ve hesaplama yöntemleri çok farklı değildir fakat
araştırma işlemlerini gerçekleştirilerken esinlendikleri kaynak, kullandıkları notasyon ve
gerçekleştirdikleri işlemlerin sırası bakımından farklılık arz ederler.
IV. Automatic Knot Adjustment by An Artificial Immune Systems
B-spline eğri uydurma problemi belirli bir tolerans dahilinde bir hedef eğri tahmin
eden B-spline eğriyi tahmin etmektir. Hedef eğrinin 2D uzayda sıralı ve sık veri noktaları ile
tanımlandığı varsayılmıştır. Eğriyi tahmin etmek için verilen nokta sayısı N, bit stringi
şeklinde oluşturulan Antigen ve Antibody’nin boyutu olan L’ye atanır. Antibody ve
Antigen’in bir molekülü olarak adlandırılan her bir biti bir veri noktasına karşılık gelmektedir.
Bu formülasyonda eğer bir molekülün değeri 1 ise uygun veri noktasına bir düğüm
yerleştirilir, eğer molekülün değeri 0 ise uygun veri noktasına düğüm yerleştirilmez (Şekil 3).
Bu kabullenme genetik algoritmadaki gen ve kromozom terimlerine eşdeğerdir fakat klonal
seçim algoritması genetik algoritmadan farklıdır ve antijeni tamamlayıcı özelliği daha fazla
olan birey daha fazla klonladığı için yakınsama genetik algoritmaya göre daha hızlıdır.
Verilen noktalar [a,b] aralığında uzanıyorsa uygun sayıda düğüm bu aralıkta tanımlanır ve
interior knots olarak adlandırılır. Başlangıç populasyonu molekül sayısı L olan K adet
Antibody içerir. Moleküller rasgele olarak 0 ve 1’e set edilirler. Minimum hata ile veri
noktalarına uyan B-spline’ı tanımlayan interior düğümlerin yerlerini ve sayılarını ihtiva eden
molekül kümesi ise tanınması gereken antijendir.
Şekil 3. Antigen-Antibody Kodlama Metodu.
Çalışmada Antigen ve Antibody arasındaki etkileşimlerde maksimum etkileşim için
minimum uzaklık teoremi kullanılmıştır. Antijen-Antikor hücre etkileşimlerinin derecelerinin
17.05.2014
Sayfa 9
belirlenmesi için ölçüt olarak Denklem (7) deki Öklit uzaklık ölçütü kullanılır. Antikorların
Antijenlere yanıt üretebilmeleri için onları tanımaları gerekmektedir. Tanıma işlemi için
çalışmamızda Antikorların Antijene olan duyarlılıklarının Antikor-antijen arasındaki uzaklığa
ve [1] ve [2] referanslarında fitness measure olarak tercih edilen Akaike’nin Information
Criterion (AIC)’e göre aşağıdaki gibi olacağı hesaplanmıştır.
 AIC 
,
(9)
Affinity  1  
 Fitness 
avrg


Burada Fitnessavrg populasyondaki tüm Anitkorların AIC değerlerinin aritmetik
ortalamasıdır ve aşağıdaki gibi hesaplanır. Herhangi bir bireyin AIC değeri Fitnessavrg
değerinden büyükse denklem (9) daAffinity=0 kabul edilir.
K
Fitness avrg 
 AIC
i 1
i
,
(10)
K
Burada K populasyonun büyüklüğüdür ve AICi populasyondaki i’inci antibody’nin
fitness measure’ıdır. AIC aşağıdaki gibi verilir.
(11)
AIC  N log e Q1  22n  m
Burada N veri sayısıdır, n interior knots sayısıdır, m verilen veri üzerine uydurulan
spline’ın order’ıdır ve Q1 denklem (6) ile hesaplanır. Şuna dikkat edilmelidir ki Antibody’ler
içinde AFFINITY'si yüksek olan hatası en az olandır, ideal çözüm olan ve tanınması gereken
Antigen’in tam olarak tamamlayıcısı olan Antibody’nin Affinity değeri populasyon
içindekilerden (aslında Memory’deki) 1’e en yakın olanıdır. Ideal antibody ile aranan antigen
arasındaki öklit uzaklığı sıfırdır. Bu durumda problem eğri tahmini değil eğri interpolasyonu
olmaktadır.
Probleme çözüm aramadan önce belli kontrol parametre değerleri programa
verilmelidir. Bunlar eğrinin order’ı, populasyon büyüklüğü, Memory büyüklüğü, çeşitlilik
oranı, ve mutasyon oranıdır. Tercihan memory büyüklüğü populasyon büyüklüğünün 2 katı
verilmiştir. Memory içeriğinde o zamana kadarki tüm iterasyonların en iyi antibody’leri
tutulmaktadır. Populasyonun çeşitlilik derecesinide çeşitlilik oranı parametresi tayin
etmektedir. Bu değer molekülleri rasgele belirlenecek antibody sayısının populasyon
büyüklüğüne oranıdır. Klonlama aşamasında da AIS ruhuna uygun şekilde Affinity
değerlerine göre klonlama gerçekleştirilmektedir ve Affinity’si daha yüksek olan antibody’ler
daha fazla klonlanmakta, affinity’si daha az olan antibody’lerde daha az klonlanmakta veya
hiç klonlanmamaktadır. Klonlanan antibody’lere maturate uygulanması sırasında genelde
memory içinden rasgele seçilen bir bireyle çift nokta çaprazlama yapılmakta yada molekül
düzeni rasgele değiştirilmektedir. Bir antibody’nin klonu fazla ise genelde klonlarına her
ikiside uygulanmıştır. AIS belli bir iterasyon sayısınca çalıştırıldıktan sonra Antijene karşı en
yüksek duyarlılığa sahip antikor çözüm olarak seçilir.
Klonal seçim algoritmasını bu probleme entegre edebilmek için yukarıdaki
algoritmada bazı değişiklikler yapılmalıdır. Aşağıda ise algoritmaya yapılan modifikasyonlar
ve bunların yukarıdaki algoritmaya nasıl uygulandığı adım adım gösterilmektedir.
1. Uydurulacak veri noktalarını gir
2. Kontrol parametrelerini gir
3. Başlangıç Antibody populasyonunu rasgele moleküllerle oluştur.
4. Populasyon ilk defa oluşturuluyorsa Memory dizisini oluştur ve tüm
Antibody’leri Memory içinde sakla.
5. Aksi takdirde Antibody populasyonu ile Memory hücrelerini güncelle ve
Memory’i geliştir.
17.05.2014
Sayfa 10
6. Her bir Antibody için B-spline’ı denklem (5) ile hesapla ve Denklem (3) ile
verilen veriye uydur. Sonra kalanların karelerinin toplamı (Q1)nı hesapla
(denklem (6)).
7. Populasyondaki her bir Antibody’nin AIC değerini (denklem (11) ve
populasyonun ortalama AIC değerini (denklem (10)) hesapla.
8. Her bir antibody için Affinity hesapla (denklem (9)).
9. Affinity’e ve aranan Antigen’e göre populasyondaki her Antikor’un
etkileşimleri (Öklit uzaklığı denklem(7))’ne göre en iyi antibody’leri seç
(toplamda K-Cesitlilik adet klon).
10. Klonların Affinity değerleriyle orantılı şekilde molekül değiştirimi ile
Olgunlaşan antibody populasyonunu üret (Memory kullanılarak veya rasgele
antibody molekülleri değiştirilerek).
11. Mutasyon oranına göre mutasyonu gerçekleştir
12. Çeşitlilik oranına göre yeni antibody’ler üret.
13. İterasyon sınırına ulaşılmadı veya Antigen tamamen tanınmadıysa Adım 5’e
git.
V. Results
Tarafımızdan önerilen AIS temelli Automatic Knot Placement algoritmamızı
değerlendirmek için şekil 4 de bir B-spline eğri parametrizasyonu örneği gösterilmektedir.
Şekil 4(a) da gösterilen 2D veriyi (200 adet) bulmak için temiz bir veriye Uniform dağılımdan
%10
gürültü
eklenmiştir.
Modellenmiş
olan
tasarı
eğri,
{0.0,0.0,0.0,0.0,0.25,0.5,0.75,1.0,1.0,1.0,1.0} düğüm vektörüne ve 7 kontrol noktasına sahip
bir non uniform B-spline kübik eğridir. Şekiller kontrol poligonunuda göstermektedir. YBS
mimarisinde Memory içeriğinde duyarlılığı en fazla olan antibody’ler saklandığı için
sonuçlarda her nesil için Memory’nin en iyi duyarlığa sahip antibody’si verilmiştir. Memory
populasyonundaki Antibody’lere dayanarak modellenen eğri ve nokta bulutu arasındaki Root
Mean Square (RMS) hatası Tablo 1 de verilmiştir. Başlangıç populasyonu 500 nesile kadar
beslenmiştir. Şekil 4(b) de başlangıç populasyonundaki en iyi tamamlayıcı Antibody’u
göstermektedir. Şekil 4(c) 500 nesil sonraki yakınsayan örüntüyü göstermektedir. Eğri şimdi
veri noktalarına daha iyi uymaktadır. Nesiller arttıkça uygunlukta artmaktadır (hata
azalmaktadır). Eğrinin eğimi sonraki nesillerde hâla yakınsama olasılığının olduğunu
göstermektedir. Tablo 2, YBS optimizasyon icrasının istatistiklerini vermektedir.
17.05.2014
Sayfa 11
Şekil 4. Gürültü verisi ile eğriler için parametre optimizasyonu üzerine bir case study. (a) 3D
veri noktaları, başlangıç populasyonu içindeki bireylerle ilgili olarak 7 kontrol noktası ile Bspline (b) Başlangıç populasyonundaki en iyi tamamlayıcı Antibody, (c) 500 nesil sonra
parametreleştirilmiş tanınan Antigen.
Nesil
BEST RMS (AIS)
BEST RMS (GA)
İnitial
3.3571
3.4517
10
3.3198
3.3578
25
3.3198
3.2348
50
3.2848
3.2348
100
3.2848
3.2348
200
3.2840
3.1016
300
3.2682
3.1016
400
3.2443
3.1016
500
3.2443
3.1016
Tablo 1: Şekil 4(a) da gösterilen örnek eğri için AIS ve GA metodlarının RMS değerleri.
Performans değerlendirmesini ve yakınsama hızını kıyaslayabilmek için Sarfaz ve ark. [2, 3]
tarafından önerilen GA algoritması ile önerdiğimiz algoritma kıyaslanmıştır. Onların
algoritmalarında’ki knot ratio oranı ve ayrıca önemli noktaların düğüm kromozomlarında
sabitlenmesi işlemleri göz ardı edilmiştir. Girdi noktaları yine Şekil 4(a) daki veri
noktalarıdır. Doğruluklarının değerlendirilmesi için GA metodu ile elde edilen RMS değerleri
de Tablo 1’in üçüncü kolonunda verilmiştir. Bununla birlikte her iki algoritma için kullanılan
parametrelerin değerleri Tablo 2’de sunulmuştur. Önerdiğimiz AIS temelli algoritmamız ile
Safraz ve arkadaşlarının GA temelli algoritması yakınsama hızlarına görede karşılaştırılmıştır.
Eğitim süreci içindeki bazı nesillerde programların çıktıları alınmıştır. Bu çıktılara göre o
17.05.2014
Sayfa 12
nesildeki populasyonlara göre bireyler ve antikorlar’ın ortalama uygunluk, ortalama RMS,
maksimum Fitness ve Maksimum RMS değerleri Tablo 3’de verilmiştir. Tüm nesillere göre
öneridğimiz AIS yaklaşımımızın ve GA yaklaşımının yakınsama grafikleri de Şekil 5’de
sunulmuştur. Bu şekilde koyu çizgiler Maksimum AIC değerlerini kesikli çizgilerde minimum
AIC değerleridir.
Parametre
Population size
String length
Mutation Rate
Crosover Olasılığı
Cesitlilik Sayisi
Memory Size
AIS
20
200 (Antibody cell length)
None
None
6 (30%)
40
GA
20
200 (chromosome gen-length)
0.001
0.7
6 (30%)
None
Tablo 2. Parametre kümesi.
G.A.
A.I.S.
3000
2000
Fitness
Fitness
2500
1500
1000
500
0
1
52 103 154 205 256 307 358 409
MAX
Generation
MIN
2100
2050
2000
1950
1900
1850
1800
1750
1700
1650
MIN
MAX
1
57 113 169 225 281 337 393 449
Generation
Şekil 5. Nesillere göre GA ve AIS temelli parametre optimizasyonu.
G.A.
Max
Max Average
AIC
RMS AIC
(Fitness)
(Fitness)
Initial 2188
6.498 2001
10
2028
4.403 1960
25
1959
3.802 1943
50
2015
3.933 1911
100
2069
4.370 1911
200
2017
4.456 1900
300
2068
4.228 1958
400
1994
4.558 1920
500
1948
3.864 1924
A.I.S.
Average Max
Max Average
RMS
AIC
RMS AIC
(Fitness)
(Fitness)
4.078
2396
9.693 2032
3.641
1913
3.749 1906
3.551
1978
3.604 1868
3.529
1840
3.500 1838
3.510
1819
3.511 1813
3.539
1801
3.390 1798
3.588
1797
3.349 1793
3.579
1798
3.346 1791
3.659
1798
3.346 1791
Average
RMS
4.398
3.545
3.518
3.429
3.408
3.336
3.318
3.296
3.296
Tablo 3: Şekil 5 de gösterilen GA ve AIS optimizasyonunun AIC ve RMS istatistikleri.
17.05.2014
Sayfa 13
MAX(Fitness)
18.000
50
16.000
GA
70
14.000
60
40
30
20
10
12.000
50
10.000
40
8.000
30
6.000
20
4.000
0
10
2.000
Generations
0
Number of Knots
80
MAX(Fitness)
Number of Knots
60
AIS
MAX (Fitness)
1500
1480
1460
1440
1420
1400
1380
1360
1340
1320
1300
Number of Knots
MAX(Fitness)
0
Generations
Number of Knots
Şekil 6. Bir boyutlu durum için uygunluk ve düğüm sayısı grafiği (a) AIS (b) GA.
Ikinci bir case study olarak uydurulmuş olan veri aşağıdaki ile üretilmiştir.
100x j 0.4 
F j  90 1  e
,  j  1,2,, N 
(12)
Burada herhangi bir hata değeri kullanılmamıştır, xj nin değerleri 0.0, 0.01, ..., 1.0’dır
ve onların sayısı 101 dir. Uydurmanın aralığı [a,b]=[0,1]’e ayarlanmıştır. Tahmin fonksiyonu
olarak kübik bir spline kullanılmıştır. Metodumuz tahmin fonksiyonunun derecesine bağlı
değildir. Kontrol parametreleri Tablo 2’deki değerlerle aynıdır.
Şekil 6, nesillere karşı düğümlerin sayısı ve uygunluğu göstermektedir. Bu şekilde
siyah çizgi en iyi uygunluğu göstermektedir. Siyah çizgiden hesaplamamızın 38 ‘inci nesilde
yakınsadığını görebiliriz. Noktalı çizgi, en iyi uygunluk için düğümlerin sayısıdır. Düğüm
sayısı ilk nesilde 54’den, 38’inci nesilde 23’e azalmıştır. Aynı örnek için GA çözümü Şekil
6.b’de verilmiştir. GA için elde edilen en iyi uygunluk 488. nesildeki 1436 değeridir. Bu
nesildeki düğüm sayısı 41’dir. AIS ve GA için nesil, uygunluk ve Düğüm sayısı değerleri Ek
A’dadır.


VI. Conclusions and Future Works
Çok sayıda veriden iyi bir B-spline eğri modeli bulmak için genelde düğümler
değişkenler olarak ele alınır. Sonra çok sayıda lokal optima ile sürekli nonlineer ve çok
değikenli optimizasyon problemi olarak eğri modellenmeye çalışılır. Bu nedenle global
optimuma ulaşmak zordur. Bu makalede orjinal problemi [1] ve [2] deki gibi ayrık bir
kombinasyonel optimizasyon problemine dönüştürdük. Sonra yapay bağışıklık sistemi
vasıtasıyla dönüştürülmüş problemi çözen yeni bir metot önerdik. Düğüm yerleşim adaylarını
antikorlar olarak düşündük. Akaike’nin Bilgi Kriterinden faydalanıp duyarlılık ölçütünü
tanımladık. Metodumuzun en önemli yanı düğümlerin eş zamanlı yerleşimlerinin ve yeterli
sayılarının otomatik tanımlanmasıdır. Ayrıca kararlı bir yakınsama örüntüsü de
göstermektedir ve herhangi bir öznel parametreye yada iyi bir iteratif arama için iyi seçilmiş
bir başlangıç populasyonuna şimdilik ihtiyacımız yoktur.
Genetik Algoritmalar ise global perspektife sahiptir ve sağlamdırlar ama optimal
çözüme daha yakın geçen nesiller için yakınsama yavaşlamaktadır, bu yüzden maliyet
yükselmektedir. Bunun için önerdiğimiz algoritmamız iyi antikorlardan daha iyilerini üretme
yeteneği, iyi antikorların daha çok klonlanması, Antikorlar için Belleğe sahip olması gibi
AIS’e has özellikleri sayesinde maliyeti düşürebilmektedir. Evrimsel algoritmaların
sağlamlığı ve verimliliğinden dolayı bu yaklaşım umut verici görünmektedir
17.05.2014
Sayfa 14
Çalışmada, verilen noktalar kümesindeki her bir noktaya bir parametre değerinin
atanması ve uygun bir düğüm vektörünün seçimi için vektördeki düğümlerin belirlenmesinde
Centripetal metot kullanılmıştır. Bunun yerine diğer metotların (örneğin equally spaced veya
chord length yaklaşım) kullanılması yaklaşımı belki operatörlerin seçiminde ve düğüm
vektörü ve parametrizasyon arasındaki ilişkilerin ayarlanmasında daha fazla esneklik
sağlayabilir. Bu esneklik ilerde daha iyi sonuçlara bile ulaşmak için algoritmanın
ayarlanmasına yardım edebilir. Ama bu metotların kıyaslanması çalışmada
gerçekleştirilmemiştir.
Eğri şeklini tasarlamak için bir maliyet fonksiyonu kullanımı yaklaşımı genelde iyi bir
stratejidir. Maliyet fonksiyonunu çözmek için bir genetik algoritmanın kullanılması maliyet
fonksiyonlarının minimizesine verimli bir yol olarak literatürde ispatlanmıştır. Genetik
algoritmanın yakınsama hızını iyileştiren klonal seçim algoritması gibi bir AIS algoritmasının
kullanımının verimi daha da arttıracağı aşikardır ve çalışmamızda da gösterilmiştir. Temel
kısıtlama uygun maliyet fonksiyonunun hâla seçilmek zorunda olmasıdır. Diğer konu
performansdır, algoritma Visual Basic Programlama Dili üzerindedir. Daha iyi performans
için verimli bir C implementasyonu yada program kodunun optimizasyonu beklenebilir. Ama
hâlen genetik algoritma, yapay sinir ağları yada yapay bağışıklık sistemleri, yakın gelecekte
etkileşimli eğri tasarım programlarına uygun olmayacaktır.
Sunulan metot eğri tahmini işlemidir, sonra metodumuz çok-boyutlu mesh verisine
dolayısıyla B-spline yüzey tahminine doğal bir biçimde genişletilebilir. Bu algoritmanın
genişlemesi için sonraki adımlarda ağırlıklar ve kontrol noktalarının optimizasyonu işlemi
yapılarak NURBS spline’lar kullanılacaktır. Bu genişletme NURBS ağırlıklarının
optimizasyonunun karmaşık olması sebebiyle özellikle üstesinden gelinmesi gereken bir
işlemdir. Diğer umut verici yönelim eğriler için optimal tasarım problemini çözmektir.
NURBS eğri tahmininde Minimizasyon adımı için AIS algoritmasını biz şu anda
geliştirmekteyiz.
Bunlara ek olarak, [4] deki çalışmada genetik algoritmanın başlangıç populasyonu
oluşturan bireyler seçildiği gen havuzlarını oluşturmak için bir çatı sunulmuştur. O çatı bu
algoritmanın başınada eklenip başlangıç Antibody populasyonunun daha yakınsamış olarak
çıkması sağlanıp çalışma süresi azaltılabilir.
Algoritmanın çalışma süresini azaltmak amacıyla paralel işlemciler kullanılabilir.
Fakat algoritmamızın mevcut yapısı bu gaye için yeterli değildir. Yapılacak bazı
modifikasyonlarla paralel işlemciler için uygun hale de getirilebilir.
Appendix
Generations
1
2
10
20
30
40
50
60
70
80
90
Fitness
A.I.S.
1488
1488
1400
1384
1376
1364
1364
1364
1364
1364
1364
17.05.2014
G.A.
1500
1496
1476
1666
1488
1468
1492
1472
1464
1464
1713
Number of
Number of
Fitness
Knots
Knots
Generations
A.I.S G.A.
A.I.S. G.A. A.I.S G.A.
54
57
260 1364 1500 23
57
54
56
270 1364 1464 23
48
32
51
280 1364 1682 23
59
28
55
290 1364 1484 23
53
26
54
300 1364 1460 23
47
23
49
310 1364 1476 23
51
23
55
320 1364 1632 23
45
23
50
330 1364 10853 23
46
23
48
340 1364 2317 23
55
23
48
350 1364 1518 23
54
23
59
360 1364 1456 23
46
Sayfa 15
100
110
120
130
140
150
160
170
180
190
200
210
220
230
240
250
1364 2979
1364 1456
1364 1492
1364 1492
1364 1464
1364 1488
1364 1827
1364 3080
1364 15521
1364 1464
1364 1464
1364 1460
1364 1484
1364 1486
1364 1456
1364 2817
23
23
23
23
23
23
23
23
23
23
23
23
23
23
23
23
53
46
55
55
48
54
55
56
50
48
48
47
53
43
46
51
370
380
390
400
410
420
430
440
450
460
470
480
490
499
500
1364
1364
1364
1364
1364
1364
1364
1364
1364
1364
1364
1364
1364
1364
1364
1504
1658
1456
1447
1509
1607
1572
1484
1488
1674
2839
1456
1448
1493
1452
23
23
23
23
23
23
23
23
23
23
23
23
23
23
23
58
53
46
56
59
59
50
53
54
57
55
46
44
55
45
Appendix A. 500 nesil için AIS ve GA’nın Uygunluk ve Düğüm sayıları.
References
1. Yoshimoto, F., Moriyama, M., Harada, T., Automatic knot placement by a genetic
algorithm for data fiting with a spline, Proceedings of the International Conference on
Shape Modeling and Applications, IEEE Computer Society Press, pp. 162-169, 1999.
2. Sarfraz, M., Raza, S.A., Capturing Outline of Fonts using Genetic Algorithm and Splines,
Fifth International Conference on Information Visualisation (IV'01) , pp. 738-743, 2001.
3. Raza, S.A., Visualization with spline using a genetic algorithm, Master Thesis, King Fahd
University of Petroleum & Minerals, Dhahran, Saudi Arabia, 2001, 126 pages.
4. Kumar, G.S., Kalra, P.K., Dhande, S.G., Parameter Optimization for B-spline Curve
Fitting using Genetic Algorithms, The Congress on Evolutionary Computation CEC’03,
Vol. 3, pp. 1871-1878, 2003.
5. Sarfraz, M., Raza, S.A., and Baig, M.H., Computing Optimized Curves with NURBS
Using Evolutionary Intelligence, Lecture Notes in Computer Science, Volume 3480, pp.
806, 2005.
6. Youssef, A.M., Reverse engineering of geometric surfaces using Tabu search optimization
technique, Master Thesis, Cairo University, Egypt, 2001
7. Goldenthal, R., Bercovier, M. Design of Curves and Surfaces by Multi-Objective
Optimization, April 2005, Leibniz Report 2005-12.
8. Park, H., Lee, J.-H., Error-Bounded B-Spline Curve Approximation Based on Dominant
Point Selection, International Conference on Computer Graphics, Imaging and
Visualization (CGIV'05), pp. 437-446, 2005.
9. C. De Boor, A practical guide to splines, springer, 1978.
10. Iglesias, A., Echevarr´ýa, G., Galvez, A., Functional networks for B-spline surface
reconstruction, Future Generation Computer Systems, Vol. 20, pp. 1337-1353, 2004.
11. Laurent, P., Mekhilef, M., Optimization of a NURBS representation, Comput. Aided Des.
Vol 25(11), pp. 699-710, 1993.
12. Hoffmann, M., Várady, L., Free-form curve design by neural networks, Acta Acad. Paed.
Agriensis, Vol. 24, pp. 99-104, 1997
13. Hoffmann, M., Modified Kohonen Neural Network for Surface Reconstruction, Publ.
Math. Vol. 54, pp. 857-864, 1999.
17.05.2014
Sayfa 16
14. Hoffmann, M., Kovács E., Developable surface modeling by neural network,
Mathematical and Computer Modelling, Vol. 38, pp. 849-853, 2003
15. Hoffmann, M., Numerical control of Kohonen neural network for scattered data
approximation, Numerical Algorithms, Vol. 39, pp. 175-186, 2005.
16. Piegl, L., Tiller, W., The NURBS Book, 2nd ed., Springer Verlag, Berlin, Heidelberg,
1997.
17. Weis, V., Andor, L., Renner, G., Varady, T., Advanced surface fitting techniques, CAGD
Vol 19, pp. 19-42, 2002.
18. Chen, D.S., Jain, R.C., Schunck, B.G., Surface reconstruction using neural networks,
Proc. of IEEE Computer Society Conference on Computer Vision and Pattern Recognition
CVPR '92., pp. 815-817, 1992
19. Hoffmann, M., Local update of B-spline surfaces by kohonen neural network, Proc. of the
5th International Conference on Computer Graphics and Artificial Intelligence, Limoges,
pp. 103-112, 2002.
20. Boudjemaï, F., Enberg, P.B., Postaire, J.-G., Surface Modeling by using Self Organizing
Maps of Kohonen, Proceedings of the IEEE International Conference on Systems, Man
and Cybernetics, vol. 3, pp. 2418-2423, Washington DC (USA), 2003.
21. Barhak, J., Fischer, A., Adaptive Reconstruction of Freeform Objects with 3D SOM
Neural Network Grids, Special Issue on Geometrical Modeling and Computer Graphics,
in Journal of Computers & Graphics, vol. 26, no. 5, 2002.
22. Kumar, S.G., Kalra, P. K. and Dhande, S. G., Curve and surface reconstruction from
points: an approach based on Self-Organizing Maps, Applied Soft Computing Journal,
Vol. 5, Issue 5, pp. 55-66, 2004.
23. R. Goldenthal, M. Bercovier, Spline Curve Approximation and Design by Optimal
Control Over the Knots, Computing Vol. 72, pp 53-64, 2004.
24. Goldenthal, R., Bercovier, M., Spline Curve approximation and design by optimal control
over the knots using genetic algorithms, Int. Cong. On Evolutionary Methods for Design,
Optimization and Control with Applications to Industrial Problems EUROGEN 2003,
CIMNE, Barcelona, pp 1-18, 2003.
25. De Castro, L.N., Von Zuben, F.J., Artificial Immune Systems: Part I-Basic Theory and
Applications, Technical Report-RT DCA 01/99, pp. 89, 1999.
26. De Castro, L.N., Von Zuben, F.J., Artificial Immune Systems: Part II- A Survey of
Applications, Technical Report-RT DCA 02/00, pp. 65, 2000.
27. De Castro, L.N., Timmis, J., 2002. Artificial Immune Systems: A New Computational
Intelligence Approach, Springer-Verlag.
28. Perelsen, A. S., Oster, G. F., Theoretical Studies of Clonal Selection: Minimal Antibody
Repertuarie Size and Reliability of Self-Nonself Discrimination. J. Theor. Biol., Vol 81,
pp. 645-670, 1979.
29. Ada, G.L., Nossal, G., The Clonal Selection Theory”, Scientific American, 257(2), pp. 5057, 1987.
30. Forrest, S., Perelson, A., Allen, L., Cherukuri, R., Self-Nonself Discrimination in a
Computer, Proc. of the IEEE Symposium on Research in Security and Privacy, pp. 202212, 1994.
31. Farmer, J.D., Packard, N.H., Perelson, A.S., The Immune System, Adaptation, and
Machine Learning, Physica 22D, pp. 187-204, 1986.
32. De Castro, L.N., Von Zuben, F.J., The Clonal Selection Algorithm with Engineering
Applications, In Workshop Proceedings of GECCO'00, Workshop on Artificial Immune
Systems and their Applications, Las Vegas, USA, pp. 36-37, 2000.
17.05.2014
Sayfa 17
33. De Castro, L. N., Von Zuben, F. J., Immune and neural network models: theoretical and
empirical comparisons. International Journal of Computational Intelligence and
Applications Vol. 1 No. 3, pp. 239-257, 2001.
34. Krishnamurty, V., Levoy, M., Fitting Smooth Surfaces to Dense Polygon Meshes,
Computer Graphics (SIGGRAPH '96 Proceedings), 313—324, 1996.
35. Li, W., Xu, S., Zhao, G., Goh, L.P., Adaptive knot placement in B-spline curve
approximation, Computer-Aided Design, 37(2005), pp. 791-797, 2005.
36. Cheng, W.-K., Data thinning for the NURBS surface in reverse engineering (CAD),
Master Thesis, California State University, Long Beach, 1996.
37. Goshtasby, A.A., Fitting Parametric Curves to Dense and Noisy Points, 4th Int. Conf.
Curves and Surfaces, St. Malo, France., pp. 227-237, 1999.
38. Cohen, F.S., Ibrahim, W., Pintavirooj, C., Ordering and parametrizing scattered 3D data
for B-spline surface approximation, IEEE Transactions on pattern analysis and machine
intelligence, Vol 22, No. 6, pp. 642-648, 2000.
39. Yu, Z., Integrated NURBS surface reconstruction and boundary element analysis, PhD
Thesis, Universite Laval, 2003, 102 pages.
40. Yang, H., Wang, W., Sun, J., Control point adjustment for B-spline curve approximation,
Computer-Aided Design, Vol. 36, pp. 639-652, 2004.
41. Engin, O., Doyen, A., A new approach to solve hybrid flow shop scheduling problems by
artificial immune system, Future generation computer systems, Vol. 20, pp. 1083-1095,
2004.
17.05.2014
Sayfa 18

Automatic knot adjustment using Artificial Immune

Transkript

Benzer belgeler

B-Spline Curve Approximation using Pareto

Siemens Miyabi sistemini kullanarak hepatoselüler karsinomanın