NP PROBLEMLERDE VE SİSTEM TASARIMINDA DNA HESAPLAMANIN KULLANILMASI

Abstract

Günümüze kadar birçok problem, matematiksel denklem ve modeller kullanılarak çözülmüştür. Fakat, karmaşık ve zor problemlerin optimizasyonu geleneksel yöntemlerle çözülemeyebilir. Özellikle, problemin parametre sayısı ve çözümün zorluk derecesi arttıkça algoritmanın tamamlanması daha çok zaman alır. Bu nedenle, yapılan bilimsel çalışmalarda bu tür problemlerin çözümü için optimizasyon algoritmaları geliştirilmiştir. Optimizasyon algoritmaları, belirli bir çözüm alanında rastlantısal olarak arama yapar ve matematiksel denklemlere gerek duymaz. Son yıllarda DeoksiriboNükleikAsit (DNA) hesaplama adı verilen bir optimizasyon yöntemi araştırmacılar tarafında farklı polinomal olmayan (Non Polinomial-NP) problemlere uygulanmıştır. Bu algoritma, DNA moleküllerini kodlayarak optimizasyon problemlerini çözer. DNA molekülü, veri saklama kapasitesi ve hızlı işlem yapma yeteneği ile literatürde yeni bir hesaplama alanı oluşturmaktadır.Bu çalışma sırasında NP problemlerin optimizasyonu ve denetleyici parametrelerinin ayarlanması için DNA hesaplama algoritması geliştirilmiştir. Doğal DNA hesaplama algoritması çözelti ortamında uygulanırken, bu çalışmada sayısal biçime dönüştürülerek optimizasyon problemlerine uygulanmıştır. Ayrıca sayısal DNA hesaplama algoritması; gezgin satıcı, sırt çantası problemi ile PI ve bulanık denetleyici parametrelerinin ayarlanması gibi üç farklı probleme uygulanmıştır. DNA hesaplamanın benzetim sonuçları diğer optimizasyon yöntemleri ile karşılaştırılmış, daha performanslı değerler elde edilmiştir.

Most of the problems have been solved by using mathematical equations and models up to now. But the optimization of complex and hard problems are may not be solved by using traditional methods. Especially when the number of parameters and the degree of hardness increase, the solution of these problems takes more time.Therefore, optimization algorithms have been developed to solve this kind of problems.Optimization algorithms randomly search the solution of a problem in a determined space and they needn?t mathematical equations. In recent years, an optimization algorithm named DNA computing is applied to different NP problems by researchers. This algorithm solves optimization problems by encoding DNA molecules. DNA molecule constitutes a new computation area in literature with its large data storage and parallel processing capability. In this study, DNA computing algorithm is used for optimization of NP problems and to tuning PI and fuzzy parameters.While natural DNA computing algorithm is implemented on solution environment, it is applied to optimization problems by transforming to a numeric form in this study.In this thesis, numeric DNA computing algorithm is applied tothree different problems such as travelling salesman, knapsack, and tuning of PI and fuzzy parameters. The simulation results of the DNA computing are compared to other optimization methods and good results are obtained.