Dipartimento di Matematica e Informatica

Now showing 1 - 2 of 2

Computational tasks in answer set programming: algorithms and implementation
(2014-12-01) Dodaro, Carmine; Leone, Nicola; Ricca, Francesco
L’Answer Set Programming (ASP) è un paradigma di programmazione dichiarativa basato sulla semantica dei modelli stabili. L’idea alla base di ASP è di codificare un problema computazionale in un programma logico i cui modelli stabili, anche detti answer set, corrispondono alle soluzioni del problema. L’espressività di ASP ed il numero crescente delle sue applicazioni hanno reso lo sviluppo di nuovi sistemi ASP un tema di ricerca attuale ed importante. La realizzazione di un sistema ASP richiede di implementare soluzioni efficienti per vari task computazionali. Questa tesi si occupa delle problematiche relative alla valutazione di programmi proposizionali, ed in particolare affronta i task di model generation, answer set checking, optimum answer set search e cautious reasoning. La combinazione dei primi due task corrisponde alla computazione degli answer set. Infatti, il task di model generation consiste nel generare dei modelli del programma in input, mentre il task di answer set checking ha il compito di verificare che siano effettivamente modelli stabili. Il primo task è correlato alla risoluzione di formule SAT, ed è implementato -nelle soluzioni moderne- con un algoritmo di backtracking simile al Conflict-Driven Clause Learning (CDCL); il secondo è risolto applicando una riduzione al problema dell’insoddisfacibilità di una formula SAT. In presenza di costrutti di ottimizzazione l’obiettivo di un sistema ASP è l’optimum answer set search, che corrisponde a calcolare un answer set che minimizza il numero di violazioni dei cosiddetti weak constraint presenti nel programma. Il cautious reasoning è il task principale nelle applicazioni dataoriented di ASP, e corrisponde a calcolare un sottoinsieme degli atomi che appartengono a tutti gli answer set di un programma. Si noti che tutti questi task presentano una elevata complessità computazionale. I contributi di questa tesi sono riassunti di seguito: (I) è stato studiato il task di model generation ed è stata proposta per la sua risoluzione una combinazione di tecniche che sono state originariamente utilizzate per risolvere il problema SAT; (II) è stato proposto un nuovo algoritmo per l’answer set checking che minimizza l’overhead dovuto all’esecuzione di chiamate multiple ad un oracolo co-NP. Tale algoritmo si basa su una strategia di valutazione incrementale ed euristiche progettate specificamente per migliorare l’efficienza della risoluzione di tale problema; (III) è stata proposta una famiglia di algoritmi per il calcolo di answer set ottimi di programmi con weak constraint. Tali soluzioni sono state ottenute adattando algoritmi proposti per risolvere il problema MaxSAT; (IV) è stato introdotto un nuovo framework di algoritmi anytime per il cautious reasoning in ASP che estende le proposte esistenti ed include un nuovo algoritmo ispirato a tecniche per il calcolo di backbone di teorie proposizionali. Queste tecniche sono state implementate in wasp 2, un nuovo sistema ASP per programmi proposizionali. L’efficacia delle tecniche proposte e l’efficienza del nuovo sistema sono state valutate empiricamente su istanze utilizzate nella competizioni per sistemi ASP e messe a disposizione sul Web.
Omega our multi ethnic genetic algorithm
(2014-03-13) Cerrone, Carmine; Grandinetti, Lucio; Gaudioso, Manlio
Combinatorial optimization is a branch of optimization. Its domain is optimization problems where the set of feasible solutions is discrete or can be reduced to a discrete one, the goal being that of nding the best possible solution. Two fundamental aims in optimization are nding algorithms characterized by both provably good run times and provably good or even optimal solution quality. When no method to nd an optimal solution, under the given constraints (of time, space etc.) is available, heuristic approaches are typically used. A metaheuristic is a heuristic method for solving a very general class of computational problems by combining user- given black-box procedures, usually heuristics themselves, in the hope of obtaining a more e cient or more robust procedure. The genetic algorithms are one of the best metaheuristic approaches to deal with optimization problems. They are a population- based search technique that uses an ever changing neighborhood structure, based on population evolution and genetic operators, to take into account di erent points in the search space. The core of the thesis is to introduce a variant of the classic GA approach, which is referred to as OMEGA (Multi Ethnic Genetic Algorithm). The main feature of this new metaheuristic is the presence of di erent populations that evolve simultaneously, and exchange genetic material with each other. We focus our attention on four di erent optimization problems de ned on graphs. Each one is iii iv proved to be NP-HARD. We analyze each problem from di erent points of view, and for each one we de ne and implement both a genetic algorithm and our OMEGA.

Dipartimento di Matematica e Informatica - Tesi di Dottorato

Browse

Filters

Settings

Sort By

Results per page

Search Results