Development, implementation and theoretical analysis of the bee colony optimization meta-heuristic method

Abstract

The Ph.D. thesis addresses a comprehensive study of the bee colony optimization meta-heuristic method (BCO). Theoretical analysis of the method is conducted with the tools of probability theory. Necessary and sufficient conditions are presented that establish convergence of the BCO method towards an optimal solution. Three parallelization strategies and five corresponding implementations are proposed for BCO for distributed-memory systems. The influence of method’s parameters on the performance of the BCO algorithm for two combinatorial optimization problems is analyzed through the experimental study.

Докторска дисертације се бави испитивањем метахеуристичке методе оптимизације колонијом пчела. Извршена је теоријска анализа асимптотске конвергенције методе посматрањем конвергенције низа случајних променљивих. Установљени су довољни и потребни услови за које метода конвергира ка оптималном решењу. Предложене су три стратегије паралелизације и пет одговарајућих имплементација конст- руктивне варијанте методе за рачунаре са дистрибуираном меморијом. Извршено је експериментално испитивање утицаја параметара методе на њене перформансе за два различита комбинаторна проблема: проблем распоређивања и проблем задовољивости.

Doktorska disertacije se bavi ispitivanjem metaheurističke metode optimizacije kolonijom pčela. Izvršena je teorijska analiza asimptotske konvergencije metode posmatranjem konvergencije niza slučajnih promenljivih. Ustanovljeni su dovoljni i potrebni uslovi za koje metoda konvergira ka optimalnom rešenju. Predložene su tri strategije paralelizacije i pet odgovarajućih implementacija konst- ruktivne varijante metode za računare sa distribuiranom memorijom. Izvršeno je eksperimentalno ispitivanje uticaja parametara metode na njene performanse za dva različita kombinatorna problema: problem raspoređivanja i problem zadovoljivosti.