Multi-objective Artificial Bee Colony for Multi-objective Quadratic Assignment Problem

Abstract

ABSTRACT: Optimization problems are interesting applications in engineering and they are mostly interdisciplinary in nature. This is due to their applications to real life problems. In some real life problems one objective function should be optimized and the aim is detecting the best solution from all possible solutions. These problems are known as Single- objective Optimization Problems (SO). In some other real life problems there is more than one objective function so called Multi-objective Optimization (MO) Problems. In MO Problems the objectives are mostly contradicting with each other. Hence, the aim is finding a class of fittest solutions regarding to all objective functions. Solutions to MO Problems appear in the form of a Pareto-front. The Quadratic Assignment Problem (QAP) is to allocate a set of facilities to a set of locations. There are two issues to consider in QAP. The first is the interaction between facilities which is indicated with a matrix called a flow matrix and the second is the distance between facilities indicated by a distance matrix. There is a new QAP model so called multi-objective Quadratic Assignment Problem (mQAP). In mQAP there are multiple flow matrices but still only one distance matrix. The desired goal of QAP is to assign the facilities to the locations so that, the summation of products between facilities becomes minimal. It follows that, the QAP is a Single-objective Optimization (SO) Problem and the mQAP is a Multi-objective Optimization (MO) Problem. The Artificial Bee Colony (ABC) Algorithm is inspired from honey bees. The ABC is an algorithm basically created to solve the SO Problems. It is a collection of family agents of honey bees that work together to get the job done. There are three kinds of bees and each is responsible for a different job. In this thesis ABC and MOABC have been used for the solution of QAP and mQAP respectively. ABC and MOABC are modified for the solution of QAP and mQAP by using some different crossover and mutation techniques with Tabu Search method. The performance of different updating methods on ABC and MOABC Algorithms is analyzed. Keywords: Single-objective Optimization (SO), Multi-objective Optimization (MO), Artificial Bee Colony Optimization (ABC), Quadratic Assignment Problem (QAP). …………………………………………………………………………………………………………………………

ÖZ: En iyileme problemleri mühendislikte ilginç uygulamalar olmalarına rağmen, doğal olarak farklı disiplinler arası kullanılan problemlerdir. Bunun sebeplerinden biri gerçek yaşam problemlerine uygulanmasıdır. Bazı gerçek yaşam problemlerinde sadece bir amaç fonksiyonu en iyilenmek istenmektedir. Buradaki amaç mevcut problem çözümlerinden en iyisine ulaşmaktır. Bu tip problemlere tek-amaçlı (TA) en iyileme problemleri denilmektedir. Bazı gerçek yaşam problemleri birden çok amaçlı olabilmektedir bunlara çok-amaçlı (ÇA) en iyileme problemleri denilmektedir. ÇA problemlerinde hedefleri çoğunlukla birbiriyle çelişmektedir. Bundan dolayı tüm amaç fonksiyonlarını kullanarak tek çözüm yerine en iyi olan çözümlerden oluşan bir çözüm sınıfı oluşturmaktadır. Bu sınıfa pareto-ön denmektedir. Karesel atama problemi (KAP) bir dizi aracı bir dizi lokasyona verilen lokasyonlar arası uzaklıklar ve araçlar arası akış bilgileri kullanılarak atama yapma problemi olarak tanımlanır. Ayrıca çoklu karesel atama problemlerinde mevcut olup birden çok akış bilgisi kullanılarak yapılan KAP problemleridir. Yapay arı kolonisi (YAK) algoritması gerçek bal arılarından ilham alınarak tek-amaçlı problemleri çözmek için tasarlanmışlardır. YAK algoritması popülasyon tabanlı bir arama algoritması olup sürü zekasına dayalı metasezgisel yöntemlerden birisidir. Algoritma gerçek bal arılarının yiyecek arama davranışlarını modellemeye dayanmaktadır. Bu çalışmada YAK ve MYAK, KAP ve MYAK algoritlamarında KAP ve MKAP problemlerinin çözümü için farklı çaprazlama ve mutasyon teknikleri ile birlikte tabu arama algoritması kullanarak performansları incelenmiştir. Anahtar Kelimeler: Tek-amaçlı en iyileme, çok-amaçlı en iyileme, yapay arı kolonisi en iyileme, karasal atama problemi.