Heuristic optimization through negotiation

Abstract

Hızla değişen koşullar ve çevre, dinamik problemlerin gerçekçi ve hızlı şekilde çözümünü gerekli kılmıştır. Dinamik problemleri; statik problemler gibi ele almak veya her değişim sonrasında yeniden model kurmak ve çözüm için uzun süreler beklemek gibi yaklaşımlar geçerliliğini yitirmeye başlamıştır. Bu bağlamda en etkili çözüm yaklaşımlarının; paralel ve dağıtık çözümler yapabilen, otonom kararlarla genel çözüme katkıda bulunabilen ve genellikle sezgisel yöntemleri içeren etmen tabanlı çözümler olduğu anlaşılmıştır. Bu bağlamda bu tez ile amaçlanan; 1) Gerek etmen tabanlı çözüm stratejileri için ortak bir gösterim şemasının oluşturulması 2) Gerekse bugüne kadar statik çözümler aranan Gezgin Satıcı Problemi'nin (GSP), dinamik türevlerine etmen tabanlı etkin çözümler bulunmasını içermektedir.Klasik GSP; her şehir bir kez ziyaret edilecek şekilde ?n sayıdaki şehrin? en uygun rota kullanılarak dolaşılmasını içermektedir. Benzer şekilde; klasik Genelleştirilmiş Gezgin Satıcı Problemi (GGSP) de ?c sayıdaki bölgenin? her bir bölgesinden en az bir şehir ziyaret edilecek şekilde en uygun rota kullanılarak dolaşılmasıdır. Ancak bazı özel durumlarda, klasik GSP ve GGSP'nin sabit şehir ve/veya bölge varsayımları sistemlerin fiziki gerçekliğini ve dinamikliğini yansıtmada tatmin edici nitelikte değildir. Problem çözümü esnasında, şehir listesine yeni şehirler eklenebilmekte veya bazı şehirler sistemden ayrılabilmektedir. Bu nedenle, gerçek sistemlerde, şehir sayısını sabit tutma varsayımı geçerliliğini yitirmektedir. Netice olarak, ?belirli bir an veya durum için bulunmuş sonuç? beklenilmeyen değişiklikler nedeniyle geçerliliğini yitirebilmektedir. Bu bağlamda dinamik GSP ve dinamik GGSP'nin geleneksel yöntemlerle modellenmesi oluşacak maliyet ve hafıza nedeniyle uygun olmayacaktır. Bu sebeplerden dolayı; bu tez kapsamında, dinamik GSP ve türevleri olan çeşitli problemler değişik ajan tabanlı stratejileri/politikaları ile çözülmektedir. Tanımlanan problemlerin çözümü için etmen tabanlı iki temel strateji sunulmaktadır. Bu stratejilerden biri; ajanların sezgisel kullanmadan; diğeri ise Büyük Kara Delik (BKD) sezgiselini kullanarak birbirleriyle rekabet etmesini içermektedir.

Finding realistic and express solutions to several problems has been a fundamental requirement in this rapidly changing conditions and environment. Conventional approaches, which are solving dynamic problems, ?as they are static? or reinventing their models after each corresponding change, have all expired. In this respect, it has been understood that, the most effective solution strategies have been the agent-based strategies. These strategies, which are mostly constructed upon a heuristic, are capable to provide parallel and distributed solutions and furthermore they let agents to take autonomous decisions that can add value to the objectives of the problem. This PhD thesis aims both 1) setting up a representation scheme for agent-based approaches and 2) providing solutions to dynamic variants of Travelling Salesman Problem (TSP), which has been solved by static approaches up to now.Classical TSP consists of ?n number of cities? where, each city is visited once using an optimal route. Similarly, Generalized Travelling Salesman Problem (GTSP) covers ?c number clusters? where, each cluster is visited exactly once by visiting one of cities of the clusters using an optimal route. However, in some specific cases, assumptions of classical TSP and GTSP may not be satisfactorily enough to reflect physical reality and dynamism of actual systems. During solution of those problems, some cities are added to city domain or some disappear from the system. Thereby, the assumption of keeping the number of cities constant fails. Consequently, ?a solution provided for a specific to state defined for a time? may lose its superiority immediately after these unexpected changes. In this respect, these dynamic types of TSP and GTSP may not be modeled with the conventional research methods since much time and memory spaces are required to setup novel models and solve them repeatedly. With those considerations in mind, this thesis covers different agent-based solution policies/strategies for providing promising solutions to different problems in domain of dynamic TSP. In this respect, two main solution strategies are proposed for the solution of the defined problem types in this PhD thesis. One of these is competition of agents without a heuristic and the other is competition of agents using Great Deluge Algorithm (GDA). All those strategies have proved themselves competed with other findings in literature.