A hybrid multi-objective genetic algorithm for bandwidth multi-coloring problem

Abstract

Genetik Algoritmalar (GAs) çeşitli problemler üzerinde başarıyla uygulanmıştır. Çok hedefli Genetik Algoritmalar (ÇHGAs) birbirinden farklı hedefleri paralel olarak iyileştirebilmektedir. Kombinatoryal optimizasyon problemleri için çeşitli ÇHGA uyguları vardır. Ancak, ÇHGA yaklaşımı özellikle gruplama problemi üzerinde sınırlı seviyede başarı oranına sahiptir. Bu düşük başarı oranından çoğalma yöntemlerinden biri olan çaprazlama operatörü sorumludur. Çaprazlama operatörü, gruplama problemi üzerinde yıkıcıdır ve bu tür problemler üzerinde çaprazlama operatörü kullanarak başarılı yeni bireyler üretilmesi zordur. Bu çalışmada, çaprazlama operatörünün gruplama problemleri üzerindeki başarı oranını arttıran yenilikçi bir metot sunulmuştur. Metot ÇHGA'nın Yapay Sinir Ağları (YSA) ile melezlenmesinden oluşmaktadır; YSA çaprazlama operasyonuna genetik arama işlemi sırasında yol göstermektedir. Sunulan metot, standart ÇHGA'ların sınırlı başarı elde ettiği Çizgeyi Kümeli Boyama problemi üzerinde test edilmiştir. Problem, bant genişliği ve çakışma sayısının aynı anda azaltılmaya çalışıldığı bir çok-hedefli gerçekleme kullanılarak çözülmüştür. Yapılan testler sonucunda, YGS tarafından yönlendirilmiş olan çaprazlama operasyonunun başarılı birey üretme olasılığını arttırdığı ve elde edilen genel çözümlerin kalitesinin de yükseldiği görülmüştür.

Genetic Algorithms (GAs) have been successfully applied on different kinds of problems. Multi-objective Genetic Algorithms (MOGAs) are capable of improving different objectives in a parallel manner. Various applications of MOGAs exist for combinatorial optimization problems. However, the MOGA approach yields a limited success rate especially on grouping problems. The crossover operation, one of the reproduction methods in GAs, is the main reason for the low performance. The crossover operation is quite destructive in grouping problems and it is difficult to produce successful offspring with this operator in this domain. In this study, a novel method that can increase the success rate of crossover operation is proposed for grouping problems. The method is a hybridization of MOGA with Artificial Neural Networks (ANNs), where ANNs guide the crossover process in the genetic search. The bandwidth multicoloring problem where standard MOGA yields limited performance has been used as the testbed for the method. The problem is solved using a multi-objective framework that minimizes bandwidth as well as conflict number in a parallel fashion. It has been observed that the crossover operation guided by the trained ANN improves the possibility of producing high fit offspring and the quality of the overall solution obtained at the end of MOGA runs.