Baskı devre delik delme makineleri için genetik algoritmalar yardımı ile güzergah belirleme
Determination of route by means of genetic algorithms for printed circuit board driller machines
Yazar: MURAT ALBAYRAK
Danışman: PROF. DR. NOVRUZ ALLAHVERDİ
Selçuk Üniversitesi / Fen Bilimleri Enstitüsü / Elektronik ve Bilgisayar Sistemleri Eğitimi Ana Bilim Dalı
Derece: Yüksek Lisans, 2008
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control
Dizin: Adaptif denetim = Adaptive control ; Genetik algoritmalar = Genetic algorithms ; Optimizasyon = Optimization ; Sezgisel algoritmalar = Heuristic algorithms

Özet:
Bu tez, elektronikte kullanılan baskı devre kartlarının makineler tarafından en kısa sürede delinmesi için en kısa mesafeye sahip delme işlemi güzergâhını bulmak amacıyla hazırlanmıştır. Tanımlanan problem bir optimizasyon işlemi olup literatürde Gezgin Satıcı Problemi (GSP) olarak bilinmektedir ve delme makinesinin en kısa turu dolaşması ile elektronik sanayindeki seri üretim yapan işletmelerde verim artışı sağlanması hedeflenmektedir. Bu amaçla, Genetik Algoritmalar (GA) birçok farklı operatörü ile birlikte, sezgisel algoritmalar, adaptif denetimler, yerel arama metotları, paralelizm ve tur bölme teknikleri ile melez bir yapıda uygulanmıştır. Çalışmada kullanılan tüm metotların reel ve etkileşimli performansları analiz edilerek en uygun melez parametreler ve operatörler belirlenmeye çalışılmış, belirlenen parametreler ile literatürdeki 63 farklı GSP probleminde 10 adet deneme yapılmıştır.Araştırmalarda kullanılan Basit Genetik Algoritmaların en iyi hata oranının yaklaşık %3.60988, ortalama hata oranının ise yaklaşık %5.35182 olduğu ve çok fazla çalışma süresi talep ettiği görülmüştür. Tez çalışmasında yeni geliştirilen Paralel Genetik Yerel Arama Algoritmasının GSP optimizasyonunda en iyi hata oranını yaklaşık %0.01795 seviyesine, ortalama hata oranını ise yaklaşık %0.04192 seviyesine düşürdüğü görülmüştür. Sonuç olarak GSP optimizasyonu için yeni geliştirilen Paralel Genetik Yerel Arama Algoritmasının oldukça başarılı olduğu gözlenmiştir.

Abstract:
This thesis has been prepared to find the drilling route having the shortest distance for drilling the printed circuit boards by machines in the shortest time. The defined problem is an optimization process and is known as Traveling Salesman Problem (TSP) in the literature. It aims to increase the efficiency by the help of the drilling machine?s feature of following the shortest tour in the businesses which make mass production in the electronic industry. For this aim, Genetic Algorithms (GA), besides many different operators, have been applied in a hybrid way with heuristic algorithms, adaptive controls, local search methods, parallelism and tour partition methods. The most appropriate hybrid parameters and operators have been tried to be determined by analyzing the sole and interactive performances of all the methods used in the research. 10 trials have been made on 63 different TSP problems in the literature with the determined parameters.It has been seen that, the best error rate of Simple Genetic Algorithms used in the researches is approximately 3.60988%, average error rate is approximately 5.35182% and that, for these error rates it requires so much running time. It has also been seen that, the Parallel Genetic Local Search Algorithms, which has just been developed in the thesis study, has reduced the best error rate to 0.01795% and average error rate to approximately 0.04192% in the TSP optimization. As a result, the newly developed Parallel Genetic Local Search Algorithm for the TSP optimization is highly successful.