Realizing metaheuristic algorithms in multi-agent based modelling environments

Abstract

Türeve dayalı nümerik yöntemler zor optimizasyon problemlerinin çözülmesinde genellikle yetersiz kalmaktadır. Bu nedenle, bir çok araştırmacı çalışmalarını kompleks ve zor optimizasyon problemlerin çözümü için metasezgisel algoritmalar geliştirmeye adamıştır. Araştırmacılar genellikle metasezgisel algoritmalarında doğa olaylarını taklit etmeye çalışmaktadırlar. Birçok etkili metasezgisel algoritma geliştirilse de çok azı taklit ettikleri doğal olayın dinamiklerini gerçekten realize etmektedir. İnanıyoruz ki, etmen bazlı modelleme ortamı ilham alınan doğa olayının gerçeklenmesinde daha kullanışlı ve doğal bir yoldur. Etmenlerin sisteme giriş çıkışı, gruplaşma gibi davranışları modelleme, maksatlı etmen iletişimleri gibi aktiviteler etmen tabanlı modelleme ve algoritma geliştirmenin kullanımıyla mümkün hale gelmektedir. Bu çalışmada, dinamik bir metasezgisel optimizasyon algoritması olan Stokastik Yayılım Arama Agoritmasının(SYA) çoklu etmen modelleme ortamında gerçeklenmesi realize edilmeye çalışılmıştır. Önerilen SYA algoritmasında çözüm vektörleri(etmenler) kendi aralarında arama yönünün belirlenmesi konusunda iletişime geçebilmekte, etmenler sistemden çıkmaya karar verebilmekte, yeni etmenler sisteme girebilmektedir. Bir diğer deyişle, önerilen algoritma doğal bir dinamik yapıya sahip olduğundan, dinamik optimizasyon problemlerine kolayca adapte edilebilmektedir. Önerilen algoritma JACK çoklu-etmen modelleme ortamında geliştirilmiştir. Tek makine çizelgeleme problemi modellenmiş ve çözülmüştür.

Derivative-based numerical methods are generally insufficient for solving difficult computational optimization problems. Therefore, most of the researchers devoted their research efforts towards developing metaheuristic algorithms for solving complex/difficult computational optimization problems. Researchers are usually tried to imitate some natural phenomenon while developing metaheuristic algorithms. Although many effective metaheuristic algorithms were evolved for problem solving, very few of them truthfully realize dynamic characteristics of the phenomenon. We believe that an agent based modeling/design environment will be more useful and natural way for a better realization of the inspired phenomenon. It is possible to model various behaviors such as entering and leaving of agents, group forming etc. Additionally, purposeful inter-agent communications for goal seeking can be achieved easily by making use of the power of agent based system modeling and algorithm platforms. In this research we implemented a metaheuristic algorithm which is known as Stochastic Diffusion Search (SDS) as a truly dynamic optimization algorithm by using the multi-agent modelling and programming approach. In the proposed SDS algorithm, solution vectors, ie, agents can communicate with each other for determining search direction. They can decide to disappear and new agents can appear. Thus the population size is not fixed. In other words, the proposed algorithm has an inherent dynamic structure so it can be more easily adapted to dynamic optimization problems. The proposed algorithm is developed in JACK multi-agent development environment. Single machine scheduling problem is modelled and solved as a test case.