Finding similar or diverse solutions in answer set programming: Theory and applications

Abstract

Birçok hesaplama probleminde ana amaç iyi tanımlanmış ölçütlere uygunen iyi çözümü (örneğin, en cok tercih edilen ürün yapılanışını, enkısa planı, en cimri filojeniyi) bulmaktır. Öte yandan, birçok gerçekuygulamada daha iyi karar verebilmek için bir küme birbirine benzerveya birbirinden farklı iyi çözümler hesaplamak istenebilir.Özellikle, üzerinde çalışılan problemin birçok iyi çözümü olabilir vekullanıcılar birkaç çözümü inceleyerek birini seçmek isteyebilir; budurumda, birbirine benzer veya birbirinden farklı iyi çözümler bulmakfaydalı olur. Ayrıca, birçok uygulamada kullanıcılar optimizasyonprobleminin formülasyonunda olmayan başka kriterleri de göz önündebulundururlar; bu durumda, daha önceden belirlenmiş belirli bir çözümkümesine yakın ya da uzak birkaç iyi çözüm bulmak faydalı olabilir.Bu motivasyon ile bu tezde Çözüm Kümesi Programlama'da (ÇKP)benzer/farklı (yakın/uzak) çözümlerin hesaplanması ile alakalı çeşitliproblemleri belirleyip, bu problemleri çözmek için çeşitli yenihesaplama yöntemleri geliştirdik. Bu yöntemlerden bir tanesinde ÇKPçözücülerden birinin algoritmasini değiştirerek, birçok ÇKP uygulamasıiçin kullanışlı olabilecek yeni bir ÇKP çözücü (Clasp-NK)geliştirdik. Bu yöntemlerin uygulanabilirliğini ve etkinliğinifilojeni çıkarımı, planlama ve biyomedikal sorgu cevaplama alanlarındagösterdik. Elde ettigimiz ümit verici deneysel sonuçlar neticesinde,bu alanlardaki uzmanlar tarafından kullanılabilecek yazılımlargeliştirdik.

For many computational problems, the main concern is to find a best solution (e.g.,a most preferred product configuration, a shortest plan, a most parsimonious phylogeny)with respect to some well-described criteria. On the other hand, in many real-world applications,computing a subset of good solutions that are similar/diverse may be desirablefor better decision-making. For one reason, the given computational problem may havetoo many good solutions, and the user may want to examine only a few of them to pickone; in such cases, finding a few similar/diverse good solutions may be useful. Also, inmany real-world applications the users usually take into account further criteria that arenot included in the formulation of the optimization problem; in such cases, finding a fewgood solutions that are close to or distant from a particular set of solutions may be useful.With this motivation, we have studied various computational problems related to findingsimilar/diverse (resp. close/distant) solutions with respect to a given distance function,in the context of Answer Set Programming (ASP). We have introduced novel offline/online computational methods in ASP to solve such computational problems. Wehave modified an ASP solver according to one of our online methods, providing a usefultool (Clasp-NK) for various ASP applications. We have showed the applicabilityand effectiveness of our methods/tools in three domains: phylogeny reconstruction, AIplanning, and biomedical query answering. Motivated by the promising results, we havedeveloped computational tools to be used by the experts in these areas.