Co-evolutionary planning

Abstract

vuı ÖZET Tasarlama NP -bütün (çözümü kesin olmayan) bir olgudur. Bununla birlikte, belli uygulama anlanları için kısıtlı çözümler önerilebilir. Bu nedenden, çok aracı dizgelerin tasarlama birimleri genelde belli bir uygulama alanına yönelik düzenlenirler. Ancak, alan bilgisinden de öte, kullanılan tasarlama algoritmaları dahi alana yönelik olduğundan bu çözümler oldukça o alana bağlı olurlar. Bu çalışmada, böyle belli bir alana yönelik bir çözüm yerine, alandan bağımsız bir genel yaklaşım anlatılıyor. Bu yaklaşım, etkileşim, çeşitlik, çoğaltma, odaklama, ve türlülük gibi çok aracı dizge kavramlarını eş evrimsel bir algoritmanın ilgili yapılarına aktaran ve uygulama alanlarından bağımsız olan algoritmik bir yöntem önerilmektedir. Algoritma bu sorunu, katılan aracıların tasan adımlarının tüm olası birleşimlerinden açılan arama uzayında seçimli genel tasarıları arayarak çözüm bulur. Bundan sonra, aracılar seçimli tasanlar üzerinde ya pazarlık yaparlar ya da eş evrimsel algoritmayı yeniden başlatırlar.

ABSTRACT Planning is known to be NP-complete. Nevertheless, practical solutions can be found, if the application domain is restricted to a specific area. Therefore, planning components of multi-agent systems are designed usually for a specific domain. However, these solutions are relative domain-dependent, in the sense that besides the heuristics even the planning algorithms are domain-oriented. To address this problem, a domain-independent algorithmic methodology is proposed, in which the multi-agent concepts interaction, variety, scalability, focus, and diversity are mapped onto related constructs of a co-evolutionary algorithm. The algorithm solves the planning problem by seeking for global alternative plans in the search space that is opened by all possible combinations of the plan steps of the involved agents. Thereafter, the agents negotiate on the alternative plans or restart the co-evolutionary algorithm.