Automatic knot adjustment using Artificial Immune
Transkript
Automatic knot adjustment using Artificial Immune
Doç.Dr.Erkan ÜLKER, Selçuk Üniversitesi Mühendislik F, Bilgisayar Mühendisliği Bölümü 17.05.2014 Sayfa 1 Doç.Dr.Erkan ÜLKER, Selçuk Üniversitesi Mühendislik F, Bilgisayar Mühendisliği Bölümü 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 Doç.Dr.Erkan ÜLKER, Selçuk Üniversitesi Mühendislik F, Bilgisayar Mühendisliği Bölümü çı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 Doç.Dr.Erkan ÜLKER, Selçuk Üniversitesi Mühendislik F, Bilgisayar Mühendisliği Bölümü 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 Doç.Dr.Erkan ÜLKER, Selçuk Üniversitesi Mühendislik F, Bilgisayar Mühendisliği Bölümü 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 t1m t0 , (4) b t n1 t nm . Bu ayarlamada f(x) için bir model fonksiyonu aşağıdaki gibi verilir. nm 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 Doç.Dr.Erkan ÜLKER, Selçuk Üniversitesi Mühendislik F, Bilgisayar Mühendisliği Bölümü 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 mSL 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 Doç.Dr.Erkan ÜLKER, Selçuk Üniversitesi Mühendislik F, Bilgisayar Mühendisliği Bölümü 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 Doç.Dr.Erkan ÜLKER, Selçuk Üniversitesi Mühendislik F, Bilgisayar Mühendisliği Bölümü 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 Doç.Dr.Erkan ÜLKER, Selçuk Üniversitesi Mühendislik F, Bilgisayar Mühendisliği Bölümü 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 Doç.Dr.Erkan ÜLKER, Selçuk Üniversitesi Mühendislik F, Bilgisayar Mühendisliği Bölümü 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 22n 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 Doç.Dr.Erkan ÜLKER, Selçuk Üniversitesi Mühendislik F, Bilgisayar Mühendisliği Bölümü 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 Doç.Dr.Erkan ÜLKER, Selçuk Üniversitesi Mühendislik F, Bilgisayar Mühendisliği Bölümü Ş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 Doç.Dr.Erkan ÜLKER, Selçuk Üniversitesi Mühendislik F, Bilgisayar Mühendisliği Bölümü 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) Doç.Dr.Erkan ÜLKER, Selçuk Üniversitesi Mühendislik F, Bilgisayar Mühendisliği Bölümü 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. 100x 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 Doç.Dr.Erkan ÜLKER, Selçuk Üniversitesi Mühendislik F, Bilgisayar Mühendisliği Bölümü Ç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 Doç.Dr.Erkan ÜLKER, Selçuk Üniversitesi Mühendislik F, Bilgisayar Mühendisliği Bölümü 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 Doç.Dr.Erkan ÜLKER, Selçuk Üniversitesi Mühendislik F, Bilgisayar Mühendisliği Bölümü 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 Doç.Dr.Erkan ÜLKER, Selçuk Üniversitesi Mühendislik F, Bilgisayar Mühendisliği Bölümü 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
Benzer belgeler
B-Spline Curve Approximation using Pareto
anahatlarından toplanan düzlemsel veriye uydurulmuş olan optimal eğri vasıtasıyla temsil edilen şekiller için evrimsel bir yaklaşım öne sürmüştür. Kullanılan spline model rasyonel (rational) kübik ...
Detaylı