Search

Grafik renklendirme problemi düğümler ve kenarlardan oluşan yapılar olan grafiklerin renklendirilmesi problemidir. Renklendirme işlemi düğümlerin renklendirilmesi veya kenarların renklendirilmesi gibi farklı şekillerde yapılabilmektedir. Grafik renklendirme problemi problemin türüne göre düğüm sayıları, düğümler arasındaki kenar sayıları ve kenarların düğümlerle bağlanma şekillleri, düğümlerin ağırlığının olup olmaması vs. gibi birçok etkene sahiptir ve bu etkenlerin çeşitliliğine göre problemin karmaşıklığı da değişmektedir. Grafik renklendirme probleminin düğüm renklendirilmesi, kenar renklendirilmesi gibi alt grupları vardır. Düğüm renklendirmesinin bir türü olan “ağırlıklı düğüm renklendirme problemi” bu çalışmada ele alınmaktadır. Bu problemde düğümlerin her birinin ağırlık değeri vardır ve aralarında kenar bulunan düğümler farklı renklerle renklendirilir. Her renk grubundaki en ağır düğüm ilgili renk grubunun temsilci düğümü olarak belirlenir ve temsilci düğümlerin ağırlıkları toplamı grafik renklendirilirken minimize edilmeye çalışılır. Ağırlıklı düğüm renklendirme probleminin çözülmesi gerçek hayat uygulamalarının bir kısmının çözümünde kullanılabilmesi açısından önem taşır. Buna ek olarak problemin polinom zamanda bilinen bir çözümünün olmaması problemle ilgili üretilen çözüm yöntemlerini değerli kılar. Bu çalışmada ağırlıklı düğüm renklendirme probleminin çözümünde kullanmak amacıyla geliştirdiğimiz algoritmayı sunmaktayız. Geliştirdiğimiz algoritma birçok problemde yaygın olarak kullanılan ve doğadan esinlenen genetik algoritma tabanlı bir algoritmadır. Doğada olduğu gibi, genetik algoritmada da bireylerden yeni nesiller oluşur. Bireylerden yeni nesiller oluşurken crossover (çaprazlama) ve mutasyon ile genetik aktarım ve çeşitlilik sağlanır. Çalışmamızda farklı özelliklere öncelik veren ancak birlikte çalışan 2 crossover tekniğini ve bu tekniklerin uygulanması neticesinde elde edilen çözümlere uygulanan bir mutasyon tekniğini önermekteyiz. Önermiş olduğumuz teknikleri literatürde yer alan 3 çalışma ile karşılaştırmış bulunmaktayız. Karşılaştırmada kullanılan materyallerle ilgili bilgileri, karşılaştırma tekniğimizi, elde edilen sonuçları ve bu sonuçların karşılaştırmalarına çalışmamızın ilgili bölümlerinde yer vermekteyiz.--------------------Graph coloring problem is the problem of coloring graphs which are structures consisting of vertices and edges. Coloring can be done in different ways such as, edge coloring or vertex coloring. Graph coloring problem includes many factors such as number of vertices, number of edges between vertices, how these edges are connected with the vertices and whether vertices have weight values or not depending on type of the problem. Consequently, degree of complexity of the problem changes according to variety of the factors. Graph coloring problem contains subcategories such as edge coloring and vertex coloring. In this study, Weighted Vertex Coloring Problem which is a type of vertex coloring is studied. In weighted vertex coloring problem, each vertex has a weight value and vertices connected with an edge are colored with different colors. Heaviest vertex in each color class becomes the representative vertex of that color class and sum of weights of the representative vertices is tried to be minimized while coloring the graph.Solving the weighted vertex coloring problem is important because of being used in solving some real life applications. In addition, being an NP-hard problem makes solution methods offered for this problem important. In this study, we offer an algorithm to solve the weighted vertex coloring problem. Our proposed algorithm is based on Genetic Algorithm which is a nature-inspired algorithm and widely used in the literature to solve problems. In Genetic Algorithm, individuals form offspring as in nature. While forming offspring, crossover and mutation operators provide transfer of genes to offspring and variety. In our study, we propose 2 crossover operators working together but giving priority to different features and a mutation operator which is applied on solutions obtained by application of the proposed crossover operators. The proposed techniques are compared with 3 other techniques in the literature. Information about materials used in the comparison, comparison techniques, obtained results and comparison of the results are provided related sections in our study.

Kutu paketleme problemi, literatürdeki en önemli optimizasyon problemlerinden biridir. Problem çok çeşitli gerçek yaşam kullanımına sahiptir. Kutu paketleme problemi NP-Hard sınıfına ait olduğundan, bu problemi farklı alanlarda kendi avantajlarıyla çözmek için önerilen birçok çözüm vardır, ancak çoğu optimum çözüme ulaşamamıştır.Kutu paketleme probleminde, kutulara yerleştirilmesi gereken sınırlı sayıda obje vardır. Her objenin kendi ağırlığı vardır ve her kutu sınırlı bir kapasiteye sahiptir. Problemin temel amacı, tüm objeleri kutulara koyarken, kullanılan kutu sayısını en aza indirmektir. Bu çalışmada, tek boyutlu kutu paketleme problemini çözmek için yeni bir havuz temelli evrimsel algoritma öneriyoruz. Algoritma, problemin arama alanını arttırmayı amaçlayan havuz tabanlı bir çaprazlama operatörü ve çaprazlama çözümü sonucunda oluşan bireyde mevcut olan az kullanılmış kutuları dikkate alarak çözümün kalitesini iyileştirmeyi amaçlayan yerel bir arama tekniğini kullanır. Önerilen yöntem, kıyaslama problem kümelerinden alınan orta ve zor örneklere uygulandı ve literatürdeki altı algoritma ile karşılaştırıldı. Deneysel sonuçlarımız, önerilen algoritmanın, sağlanan test vakalarının çoğunda bu algoritmalardan önemli ölçüde daha iyi performans sergilediğini göstermektedir.--------------------Bin packing problem is one of the most important optimization problems from the literature. The problem has a wide range of real life usage. Since bin packing problem belongs to NP-Hard class, there are many heuristics proposed to solve this problem with their own advantages in different domains, but most of them could not reach the optimum solution. In bin packing problem, there are finite number of items which must be placed into bins. Each item has their own weight and each bin has a finite capacity. Main objective of the problem is to place all items into the bins in a manner that minimizes the number of bins used. This work proposes a novel pool-based evolutionary algorithm for the solution of one-dimensional bin packing problem. The algorithm exploits a pool-based crossover operator which increases the problem’s search space and a local search method which tries to decrease the bin usage of the solution by considering underutilized bins available in the offspring. The proposed method is applied to medium and hard instances taken from benchmark problem sets and is compared with six algorithms from the literature. Our experimental evolution indicates that the proposed algorithm significantly outperforms these algorithms in most of the test cases provided.

Klinik karar almada yanlış bir teşhis hastanın yaşamına zarar verebilir. Bu sebeple veri madenciliğinin sağlık sektörüne uygulanmasındaki kayda değer artış ölçüm doğruluğunu klinik teşhis öngörüsünde kritik performans ölçümlerinden biri haline getirmektedir. Bununla birlikte sınıf dengesizliği problemi yaygın olarak klinik veri kümelerini sıkıntıya sokmaktadır. Bu hal, veri kümelerindeki sınıflar eşitsiz biçimde ortaya konduğunda meydana gelmektedir. Bu durum algoritmaların verilerle overfitting uyuşmazlığına sebep olan ve klinik öngörüde zayıf doğruluk veren sinirsel ağ algoritmalarıının işlerliğini azaltmaktadır. Torbalama metodu sınıf dengesizliği problemine yaklaşım becerisine sahip ve ölçme doğruluğunu artıran yaygın kümeleme metodlarından biridir. Bunun yanısıra torbalama metodu kararsız kümeleyicilerde olumlu biçimde işlemektedir. Kararsız kümeleyicilerden biri de sinirsel ağlardır. Bu sebeple bu çalışmada, yukarıdaki probleme yaklaşım konusunda torbalama tabanlı sinirsel ağ öne sürülmektedir. Deneysel sonuçlara göre bu yöntem doğru ölçmede konvansiyonel sinirsel ağdan daha iyi sonuç vermekte ve klinik teşhis öngörüsünde sınıf dengesizliği problemine başarılı bir yaklaşım sergileyebilmektedir.--------------------In clinical decision making, an inaccurate diagnosis might harm patient's life. Therefore, the significant growth of data mining’s implementation in healthcare industry takes the accuracy into one of the critical performance measures for clinical diagnosis prediction. However, clinical datasets commonly suffer from class imbalance problem. It occurs when the classes in the datasets are unequally presented. This situation degrades the performance of neural network algorithms which leads the algorithms to overfit the data and have poor accuracy in clinical prediction. Bagging method is one of the popular ensemble methods that is capable to address class imbalance problem and improve the accuracy. Furthermore, bagging method performs well with unstable classifiers. One of the unstable classifiers is neural networks. Therefore, bagging based neural network is proposed to address the above problem. From the experimental results, the proposed method achieves better accuracy than the conventional neural network and successfully addresses class imbalance problem on clinical diagnosis predictions.

Grafik renklendirme problemi literatürdeki en popüler optimization problemlerinden biridir. Problemin grafiklerle modellenebilen bir çok gerçek probleme uygulunabilmesi, grafik renklendirme problemini önemli kılmaktadır. Problemin polinom zamanda henüz bir çözümünün bulunamaması, bu problem için bir çok sezgisel algoritmanın geliştirilmesine sebep olmuştur. Ancak geliştirilen bu sezgisel algoritmalar dinamik grafiklerdeki renklendirme problemlerine uyum sağlayamamıştır.Dinamik grafiklerdeki renklendirme problemi dinamik grafik renklendirme problemi olarak adlandırılmış ve bir kaç senedir üzerinde çalışmalar yapılmaya başlanmıştır. Bu sebeple, literatürde bu yeni keşfedilen problem için az sayıda sezgisel algoritma bulunmaktadır.Bu çalışmada, dinamik grafik renklendirme problemini çözmek amacıyla bir evrimsel algoritma geliştirilmiştir. Algoritma belirlenen bir zaman aralığında değişen dinamik grafikleri dikkate almaktadır ve bu değişimlere kolayca uyum sağlayabilmektedir. Algoritma literatürde yer alan ve dinamik grafik renklendirme problemi için geliştirilen iki sezgisel algoritma ile birlikte çeşitli senaryolara sahip bir çok dinamik grafik üzerinde test edilmiştir ve bu çalışmada sunulan algoritmanın bir çok durumda diğer algoritmalardan daha iyi sonuçlar elde ettiği görülmüştür. Graph coloring problem is one of the most popular optimization problem in the literature. The problem can be applied to solve many real-world problems that are modeled by using graphs. Since graph coloring problem is an NP-hard problem, there are many heuristic algorithms to solve the problem in different domains. However, these heuristic solutions are for solving static graphs and they are hard to be adapted in dynamic graphs.Graph coloring problem in dynamic graphs is called dynamic graph coloring problem and this problem has been explored for the last few years. Therefore, there are only a few and recently proposed heuristic algorithms to solve the dynamic graph coloring problem in the literature.In this study, we propose an evolutionary algorithm for solving dynamic graph coloring problem. The algorithm considers dynamic graphs changing over a given number of time steps. It adapts to the changes in the graph with its novel pool-based crossover operator easily. We tested our algorithm with two heuristic methods for dynamic graph coloring problem in the literature on dynamic graphs which have different characteristics and compared the solutions of the algorithms. The results show that our algorithm outperforms these two algorithms in most of the test cases given. 64