A Study of optimization problems using neural nets on the transfer

Abstract

oz NÖRON AĞLARI KULLANARAK, ENİYİLEME PROBLEMLERİNİN TRANSPUTER ÜZERİNDE İNCELENMESİ ŞENER, Cevat Yüksek Lisans Tezi, Bilgisayar Mühendisliği Anabilim Dalı Tez Yöneticisi: Y. Doç. Dr. Marifi GÜLER Şubat, 1992, 124 sayfa. Bilim ve mühendislik alanlarında karşılaşılan birçok problem bileşimsel eniyileme türündedir. Bu gibi problemlerde amaç, maliyet fonksiyonlarının olabilecek en düşük değerlerini hesaplamaktır. Ancak bu fonksiyonların çoğu NP-tamlaşıktır. Hızlı ve eniyiye yakın çözümler sağladıkları için nöron ağları, bu gibi problemlerin çözümünde kullanılabilecek modeller olarak önerilmişlerdir. Bu çalışmada, görev atanması ve grafik bölünmesi (minimum bölünme ve maksimum bölünme) problemleri, nöron ağlarında bileşimsel eniyileme uygulanmasına iki örnek olarak verilmiştir. Bu modeller transputer geliştirme sistemi kullanılarak, çoklu komut çoklu veri tipinde işlem yapabilen transputer ağında uygulanmıştır. Ayrıca benzetilmiş tavlama işlemi değişik bir seçenek olarak sunulmuş ve tek bir transputer üzerinde denenmiştir. Anahtar Kelimeler: Benzetilmiş Tavlama, Bileşimsel Eniyileme, NP-tamlaşıklık, Nöron A'gları, Transjftıter. Bilim Dalı Sayısal Kodu: 619.02.03 iv

£JJ*J ABSTRACT A STUDY OF OPTIMIZATION PROBLEMS USING NEURAL NETS ON THE TRANSPUTER ŞENER, Cevat M. S. in Computer Engineering Supervisor: Asst. Prof. Dr. Marifi GÜLER February, 1992, 124 pages. A set of problems central to many disciplines in science and engineering are of the type combinatorial optimization. The major objective in this area is to find optimal values for the functions of the systems, generally called cost functions. Unfortunately, most of them are NP-complete. Neural networks have been declared as models for solving such problems as they provide quick and near-optimum solutions. Two problems, task- assignment and graph partitioning (min-cut and max- cut), are studied as examples to show the adoption of combinatorial optimization problems into neural networks. The models are set up using the transputer development system on a transputer network, an MIMD machine. Also, a simulated annealing process is introduced as an alternative method, and simulated on a single transputer. Keywords: Combinatorial Optimization, Neural Networks, NP- Completeness, Simulated Annealing, Transputer. Science Code: 619.02.03 iii