Cooperative Multi-agent Systems for Single and Multi-objective Optimization

Abstract

Solving combinatorial and real-parameter optimization problems is an important challenge in all engineering applications. Researchers have been extensively solving these problems using evolutionary computations. In this thesis, three new multi-agent architectures are designed and utilized in order to solve combinatorial and realparameter optimization problems. First architecture introduces a novel learning-based multi-agent system (LBMAS) for solving combinatorial optimization problems in which all agents cooperate by acting on a common population and a two-stage archive containing promising fitness-based and positional-based solutions found so far. Metaheuristics as agents perform their own method individually and afterwards share their outcomes with others. In this system, solutions are modified by all running metaheuristics and the system learns gradually how promising metaheuristics are, in order to apply them based on their effectiveness. In the second architecture, a novel multi-agent and agent interaction mechanism for the solution of single objective type real-parameter optimization problems is proposed. The proposed multi-agent system includes several metaheuristics as problem solving agents that act on a common population containing the frontiers of search process and a common archive keeping the promising solutions extracted so far. Each session of the proposed architecture includes two phases: a tournament among all agents to determine the currently best performing agent and a search procedure conducted by the winner. The proposed multi-agent system is experimentally evaluated using the well-known CEC2005 benchmark problems set. The third architecture presents a creative multi-agent and dynamic multi-deme architecture based on a novel collaboration mechanism for the solution of multiobjective real-parameter optimization problems. The proposed architecture comprises a number of multi-objective metaheuristic agents that act on subsets of a population based in a cyclic assignment order. This multi-agent architecture works iteratively in sessions including two consecutive phases: in the first phase, a population of solutions is divided into subpopulations based on the dominance ranks of its elements. In the second phase, each multi-objective metaheuristic is assigned to work on a subpopulation based on a cyclic or round-robin order. The proposed multiagent system is experimentally evaluated using the well-known CEC2009 multiobjective optimization benchmark problems set. Analysis of the experimental results showed that the proposed architectures achieve better performance compared to majority of their state-of-the-art competitors in almost all problem instances. Keywords: Multi-agent systems, Metaheuristics, Combinatorial Optimization, Multiprocessor Scheduling, Agent Interactions, Multi-objective Optimization, Pareto Optimality

ÖZ: Bileşimsel ve gerçek parametreli en iyileme problemlerini çözmek tüm mühendislik uygulamalarında önemli bir sorundur. Araştırmacılar uzun süredir evrimsel algoritmaları kullanarak bu problemlerin çözümü üzerinde uğraşmaktadırlar. Bu tezde, bileşimsel ve gerçek parametreli en iyileme problemlerini çözmek için üç yeni çok ajanlı sistem mimarisi önerilip ve tasarlanmıştır. İlk sistem mimarisi bileşimsel en iyileme problemlerini çözmek amacıyla öğrenebilen çok ajanlı sistemi (LBMAS) tanıtır. Bu sistemde tüm ajanlar ortak nüfus ve çift aşamalı arşiv üzerinden işbirliği yaparlar. Sistemdeki çift aşamalı arşiv içerisinde uygunluk ve konumsal bakımından iyi olan çözümler bulunmaktadır. Önerilen sistemde metaheuristic’ler ajan olarak kendi yöntemlerini yürütüp, daha sonrasında bulunan sonuçları başkalarıyla paylaşıyorlar. Bu sistemde, bulunan çözümler çalışan tüm Metaheuristic’ler tarafından değiştirilir ve sistem metaheuristic’lerin ne kadar etkili olduklarını sınayarak öğreniyor. İkinci mimaride, tek amaçlı gerçek parametreli en iyileme problemlerini çözmek için çok ajanlı yeni bir sistem ve ajan etkileşim mekanizması öneriliyor. Önerilen çok ajanlı sistemde çeşitli Metaheuristic’ler ortak nufüs ve ortak arşiv üzeride çalışıyorlar. Ortak arşiv, şu ana kadar bulunan umut verici çözümleri içeriyor. Önerilen mimarideki her adım iki aşamayı içerir: birinci aşamada tüm ajanlar arasında en iyi performans gösteren ajanı bulmak için turnuva yapılıyor ve ikinci aşamada ise arama prosedürü, kazanan ajan tarafından devam ettiriliyor. Önerilen çok ajanlı sistem tanınmış CEC2005 problem kümesindeki problemleri çözümü üzerinden değerlendirilmiştir. Üçüncü çok ajanlı mimaride çok amaçlı gerçek parametreli en iyileme problemlerini çözmek için yeni bir işbirliği mekanizması sunulmuştur. Önerilen mimaride metaheuristic ajanlar döngüsel bir atama sırasına göre alt nüfuslar üzerinde çalışırlar. Bu çok ajanlı mimari ardışık iki faz üzerinden döngülenerek çalışır: ilk aşamada, çözüm nüfus unsurları baskınlık değerine göre alt nufüslara ayrılırlar, ikinci aşamada ise her çok amaçlı metaheuristic yuvarlak döngü usülüne göre bir alt nufüs üzerinde çalışmak için görevlendirilir. Önerilen çok ajanlı sistem tanınmış CEC2009 deneysel problemler kümesindeki çok amaçlı en iyileme problemleri kullanarak değerlendirilmiştir. Deney sonuçlarının analizi, önerilen mimarilerin hemen tüm deneysel problemler üzerinde rakiplerinden daha iyi başarıma sahip olduklarını göstermiştir. Anahtar Kelimeler: Çok ajanlı sistemler, Metaheuristic, Bileşimsel en iyileme, çok işlemcili planlama, Ajan etkileşimleri, Çok amaçlı en iyileme, Pareto en iyilik