A hybrid genetic algorithm proposal for the team formation problem / Sosyal ağ varlığında takım oluşturma problemine bir hibrit genetik algoritma önerisi

Abstract

Birçok sektördeki faaliyetler daha karmaşık hale gelirken, takımlar, birden fazla beceri ve kavrayış gerektiren görevleri yerine getirmede belirgin bir şekilde baskın olmaya başlamıştır. Bu durum bir işi bir arada yürütebilecek ve yeterli düzeyde bağlılığa sahip kişilerin bir araya toplanmasını kapsayan sosyal ağ varlığında takım oluşturma probleminin literatürde yer almasına sebep olmuştur. Şimdiye dek takım oluşturma probleminin NP-hard karmaşıklık sınıfında olması nedeniyle, bazı kesin yöntemlerin yanı sıra, farklı sezgisel yöntemler de denenmiştir. Bu çalışmada, biri problemden bağımsız ve diğeri probleme özgü bilgiler kullanan iki yerel arama algoritması ile melezleştirilmiş bir genetik algoritma olan takım oluşturucu hibrit genetik algoritma (TFHGA) önerilmiştir. Bu şekilde sosyal ağ varlığında takım oluşturma problemini çözmek için klasik genetik algoritmanın tüm arama uzayını keşfetme gücü ile yerel arama algoritmalarının arama uzayındaki sınırlı bölgeleri inceleme gücü birleştirilmiştir. Ayrıca yeni bir olurlu çözüm üreteci ve probleme özgü mutasyon operatörü tasarlanarak önerilen algoritmada kullanılmıştır. Deneysel çalışma olarak, önerilen algoritma, takım oluşturma problemi için literatürde yaygınca kullanılan bir veri seti ile test edilmiştir. Elde edilen sonuçlar takım oluşturucu hibrit genetik algoritmanın etkinliğini doğrulamaktadır. While activities in numerous sectors became more complex, teams prominently started to predominate in performing the tasks requiring multiple skills and perspicacity. When it is the case, the team formation problem has been discussed in the literature as a problem that involves huddling people who can carry out a task together and have a sufficient level of cohesion. Up to the present, several heuristic methods have experimented on the team formation problem considering the social network besides some exact methods due to its complexity class being NP-hard. In this study, we propose the team-forming hybrid genetic algorithm (TFHGA) which is a genetic algorithm hybridized with two local search algorithms, where one of them uses some problem-specific information while the other is problem-independent. In this way, we combine the strength of the classic genetic algorithm in exploring the whole search space with the power of local search algorithms in exploiting a limited portion of the search space to solve the team formation problem in the presence of a social network. A feasible solution generator and problem-specific mutation operator are also designed and employed in the proposed algorithm. As the experimental work, the proposed algorithm is tested with a dataset commonly used in the literature for the team formation problem. Obtained results validate the efficiency of the team-forming hybrid genetic algorithm.