In this paper, we introduce a novel approach to computing the contribution of input tuples to the result of the query, quantified by the Banzhaf and Shapley values. In contrast to prior algorithmic work that focuses on Select-Project-Join-Union queries, ours is the first practical approach for queries with aggregates. It relies on two novel optimizations that are essential for its practicality and significantly improve the runtime performance already for queries without aggregates. The first optimization exploits the observation that many input tuples have the same contribution to the query result, so it is enough to compute the contribution of one of them. The second optimization uses the gradient of the query lineage to compute the contributions of all tuples with the same complexity as for one of them. Experiments with a million instances over 3 databases show that our approach achieves up to 3 orders of magnitude runtime improvements over the state-of-the-art for queries without aggregates, and that it is practical for aggregate queries.

Quantifying the contribution of database facts to query answers has been studied as means of explanation. The Banzhaf value, originally developed in Game Theory, is a natural measure of fact contribution, yet its efficient computation for select-project-join-union queries is challenging. In this paper, we introduce three algorithms to compute the Banzhaf value of database facts: an exact algorithm, an anytime deterministic approximation algorithm with relative error guarantees, and an algorithm for ranking and top-k. They have three key building blocks: compilation of query lineage into an equivalent function that allows efficient Banzhaf value computation; dynamic programming computation of the Banzhaf values of variables in a Boolean function using the Banzhaf values for constituent functions; and a mechanism to compute efficiently lower and upper bounds on Banzhaf values for any positive DNF function. We complement the algorithms with a dichotomy for the Banzhaf-based ranking problem: given two facts, deciding whether the Banzhaf value of one is greater than of the other is tractable for hierarchical queries and intractable for non-hierarchical queries. We show experimentally that our algorithms significantly outperform exact and approximate algorithms from prior work, most times up to two orders of magnitude. Our algorithms can also cover challenging problem instances that are beyond reach for prior work.

Evolutionary multi-objective optimization has been employed in studies concerning evolutionary robotics, and in particular for the evolution of neuro-controllers. To allow the simultaneous multi-objective evolution of topology and weights, tailored search algorithms should be developed. Here, a modification to the well-known NEAT algorithm is suggested. The proposed algorithm, which is termed NEAT-MODS, involves a specialized selection process that aims to ensure both genotypic diversity and elitism in the context of Pareto-optimality. NEAT-MODS constitutes a generic Multi-objective Topology and Weight Evolution of Artificial Neural-Networks (MO-TWEANN) algorithm. The suggested NEAT-MODS is found to be statistically superior to NEAT-PS, when applied to solve complex multi-objective navigation problem.

In the last decade evolutionary multi-objective optimizers have been employed in studies concerning evolutionary robotics. In particular, the majority of such studies involve the evolution of neuro-controllers using either a genetic algorithm approach or an evolution strategies approach. Given the fundamental difference between these types of search mechanisms, a valid question is which kind of multi-objective optimizer is better for such applications. This question, which is dealt with here, is raised in view of the permutation problem that exists in evolutionary neural-networks. Two well-known Multi-objective Evolutionary Algorithms are used in the current comparison, namely MO-CMA-ES and NSGA-II. A multi-objective navigation problem is used for the testing, which is known to suffer from a local Pareto problem. For the employed simulation case MO-CMA-ES is better at finding a large sub-set of the approximated Pareto-optimal neuro-controllers, whereas NSGA-II is better at finding a complementary sub-set of the optimal controllers. This suggests that, if this phenomenon persists over a large range of case studies, then future studies should consider some modifications to such algorithms for the multi-objective evolution of neuro-controllers.