When a set of agents (human or artificial) must agree on a series of measures, it is necessary to establish which criteria must be optimized to find the best agreement. In particular, under the egalitarian social welfare, the aim is to maximize the benefit of the agent who is most disadvantaged. In this way, the aim is to ensure that no agent is too dissatisfied with the agreement reached, so that the probability of breaking the agreement is lower. Unfortunately, it is not (computationally) straightforward to compute the best agreements under egalitarian social welfare. In addition, agents may try to lie about their true preferences to try to fool the optimization algorithm. In this paper we demonstrate the computational complexity of the problem and propose strategies to discourage agents from lying. In particular, we consider the case of political parties that have to reach an agreement on a given set of laws. Genetic algorithms are used to evaluate the usefulness of different strategies from an experimental point of view.

During the last years, computational techniques have been extensively applied to the field of criminology . Most of these works focus on learning how to predict future crimes or how to identify a criminal activity from some observed behaviors. In this paper, a different problem focusing on the resolution of a crime that has already been committed is faced. Let us suppose the spatio-temporal testimonies of a group of witnesses about the events involving a crime scene is given, that is, who was seen where and at what times, along with defined traveling limitations, such as the minimal time required to travel between the involved locations. The primary objective is to determine the consistency of these testimonies, i.e., whether the reported events align with each other. If inconsistencies arise, then the goal shifts to identifying the largest subset of witnesses whose testimonies are internally consistent. Modified versions of this problem are defined, and their computational complexity is identified, including the approximation hardness. In particular, a high difficulty of the problem is inferred by reaching that same difficulty even in a more simple case, where all testimonies involve the same actor, which will be the focal point of our analysis. In addition, approximate heuristic solutions , such as a memetic algorithm , a genetic algorithm (defined as a particular case of the latter algorithm), and two greedy algorithms , are used to heuristically solve our problem. The limitations of these methods are discussed, and experimental results are reported for many problem instances, including a case study .

Computational Complexity has grappled for decades with understanding which Boolean functions can be computed with small circuits. This knowledge would unlock new ways to approach paramount open problems in Computer Science, such as P vs NP. We present an empirical approach to the problem in which we classify 5-to-l-bit Boolean functions. We built a dataset of functions with small encoding circuits and tested different classifiers to isolate them from the vast complementary set of functions with big circuits. Simple multilayer perceptrons achieved 97% and higher accuracies. We introduce r-weights, a heuristic on neuron weights, to explain how and why this approach was so successful, and we present the theoretical conclusions we extracted from them to face the circuit complexity problem.

We present a process algebra capable of specifying parallelized Ant Colony Optimization algorithms in full detail: PA2CO. After explaining the basis of three different ACO algorithms (Ant System, MAX-MIN Ant System, and Ant Colony System), we formally define PA2CO and use it for representing several types of implementations with different parallel schemes. In particular fine-grained and coarse-grained specifications, each one taking advantage of parallel executions at different levels of system granularity, are formalized.

How much power does a political party really have, compared to another party? In principle, the answer might seem obvious, since power seems to be directly pro-portional to its number of voters (or its number of deputies). However, in reality, the power of a party depends on its ability to form government majorities. In this paper we will demonstrate the computational hardness (in particular, #P-hardness) of determining the relative power of a party in different settings, and provide practical algorithms to compute it. We will use our algorithms to face a case study where we will compare the relative power of parties in real elections. Although we will use political parties as an illustration, the problem is equally applicable to any multi-agent voting system, and this type of environment poses the greatest difficulties.

In multi-agent resource allocation systems, it is reasonable that the specific allocation of resources depends on the utility functions declared by the different agents. However, this can easily lead to strategic behaviors in which the agents involved are interested in lying, since such lies can bring them more profitable deals. In this paper we analyze the case of egalitarian social welfare, where the objective is to maximize the utility of the agent who receives the least utility. In this context, agents can obtain advantages by undervaluing their preferences. Thus, we will see how to discourage such lies even in the presence of public goods and non-additive utilities. Likewise, we will use genetic algorithms to show, through experimental results, the robustness of our proposal against lies.

Reaching agreements is part of the life of any human group, but it is especially important in the context of political relations. In parliamentary systems, when no party has an absolute majority, it is necessary to establish pacts with other parties to carry out as many laws as possible that fit with our ideology. However, finding the best possible deals is not an easy task. In fact, in this work we not only show that it is an NP-complete problem, but also that it is impossible to guarantee a good approximation ratio in polynomial time. Even so, we show that it is possible to use genetic algorithms to obtain reasonably satisfactory pacts, and we illustrate it for a specific case study of the Spanish parliament.

Benchmarks are useful to allow evaluating the usefulness of new algorithms. However, care has to be taken to avoid cheating in case the users know the benchmarks in advance. In this paper, we present a blockchain-based tool that allows the generation of dynamic benchmarks. Moreover, it provides a verifiable certification about the moment when the benchmark was created, the researcher who asked for it, how much time was spent before solving it, etc. By using it, we can safely deal with the use of dynamic benchmarks without requiring a trusted third party.

When some resources are to be distributed among a set of agents following egalitarian social welfare, the goal is to maximize the utility of the agent whose utility turns out to be minimal. In this context, agents can have an incentive to lie about their actual preferences, so that more valuable resources are assigned to them. In this paper we analyze this situation, and we present a practical study where genetic algorithms are used to assess the benefits of lying under different situations.

The Cooperative Co-evolution framework is an effective approach for decomposing large scale global optimization problems into multiple sub-components. Every subcomponent uses different optimization algorithms which evolve cooperatively and are independent of each other. These subcomponents contribute in a different way to the overall improvement of the optimal solution. Hence, the computation cost can be decreased by separating out the stagnant subcomponents of the population. Therefore, it is appropriate to allocate resources in an intelligent manner to increase the computational efficiency. In this paper, we illustrate a decomposition strategy to solve large scale global optimization problems which is scalable to millions of variables. The proposed strategy improves computational efficiency and enables embracing parallelization. The framework presented in this paper constitutes Cooperative Co-evolution based Genetic Algorithm with Scalar Distance Grouping technique (CCGA-SDG) derived from Cooperative Co-evolution based Genetic Algorithm (CCGA). In our proposed scheme, a novel scalar distance grouping technique is employed that collates the dependent variables together. The stagnant sub-components of the population are detected using this grouping method and resource reallocation is performed accordingly to increase the computational efficiency. Using our proposed methodology, a benchmark function $f_{6}$ of CEC'08 benchmark composed of 10 million variables is evaluated in 1759.79 seconds using 04 processors connected with Message Passing Interface (MPI) exhibiting better accuracy as compared to other methods. Moreover, for ${f}3$ and $f_{6}$ functions we achieve a better accuracy and for rest of the benchmark functions we achieve acceptable solutions.

We study the problems of picking the media where a good or service is advertised in such a way the cost of placing these advertisements is minimized but, simultaneously, the individuals of some given population segments reach some minimum average advertisement impressions (views); or they reach some minimum probabilities of watching the advertisement at least once; or they reach both. The proposed model lets the publicist explicitly define the dependencies between media audience (i.e., whether viewers of some medium typically watch some other medium; or typically do not watch it; or typically watch it as the rest of the audience). We prove the Log-APX-hardness of these three problems. We present two heuristics to suboptimally solve each of these problems (one greedy and the other one based on genetic algorithms) and compare their performance for several problem instances.

In this paper we develop a general framework to reason about testing. The difficulty of testing is assessed in terms of the amount of tests that must be applied to determine whether the system is correct or not. Based on this criterion, five testability classes are presented and related. We also explore conditions that enable and disable finite testability, and their relation to testing hypotheses is studied. We measure how far incomplete test suites are from being complete, which allows us to compare and select better incomplete test suites. The complexity of finding that measure, as well as the complexity of finding minimum complete test suites, is identified. Furthermore, we address the reduction of testing problems to each other, that is, we study how the problem of finding test suites to test systems of some kind can be reduced to the problem of finding test suites for another kind of systems. This enables to export testing methods. In order to illustrate how general notions are applied to specific cases, many typical examples from the formal testing techniques domain are presented.

Abstract Given a finite state machine denoting the specification of a system, finding some short interaction sequences capable of reaching some/all states or transitions of this machine is a typical goal in testing methods. If these sequences are applied to an implementation under test , then equivalent states or transitions would be reached and observed in the implementation—provided that the implementation were actually defined as the specification. We study the problem of finding such sequences in the case where configurations previously traversed can be saved and restored (at some cost). In general, this feature enables sequences to reach the required parts of the machine in less time, because some repetitions can be avoided. However, we show that finding optimal sequences in this case is an NP-hard problem. We propose an heuristic method to approximately solve this problem based on an evolutionary computation approach, in particular river formation dynamics (RFD). Given finite state machine specifications and sets of states/transitions to be reached, we apply RFD to construct testing plans reaching these configurations. Experimental results show that being able to load previously traversed states generally reduces the time needed to cover the target configurations.

NP-complete problems are particularly hard to solve. Unless P=NP, any algorithm solving an NP-complete problem takes exponential time in the worst case. The intrinsic difficulty of NP-complete problems when we try to optimally solve them with compute

SUMMARY This paper introduces a formal framework to specify and test systems presenting both soft and hard deadlines. While hard deadlines must always be met on time, soft deadlines can be sometimes met in a different time, usually greater, from the specified one. It is this characteristic (to formally definetextitsometimes) that produces several reasonable alternatives to define appropriate implementation relations, that is, relations to decide whether an implementation is correct with respect to a specification. In addition to introducing these relations, the paper also presents a formal testing framework to test implementations and provides an algorithm to derive sound and complete test suites with respect to the implementation relations previously defined. That is, an implementation conforms to a specification if and only if the implementation successfully passes all the tests belonging to the suite derived from the specification. Copyright © 2011 John Wiley & Sons, Ltd.

We present a tool to automatically derive choreography-conforming web services systems. The user provides a specification that describes peer-to-peer collaborations of the observable behavior of parties from a global viewpoint, in our case WS-CDL documents, and the tool automatically extracts the particular behavior of each participant, more concretely, WS-BPEL documents defining the behavior from a local viewpoint. We implement two automatic methods(centralized and decentralized) that derive conforming systems even in cases where projecting the choreography into each service would lead to a non-conforming system. This issue is addressed by adding some control messages that make services interact as required by the choreography. Experiments where the number of exchanged messages is measured are presented, and strategies to reduce the number of these messages are discussed.

In this paper we introduce a timed extension of the extended finite state machines model. On the one hand, we consider that (output) actions take time to be performed. This time may depend on several factors such as the value of variables. On the other hand, our formalism allows to specify timeouts. In addition to present our language, we develop a testing theory. First, we define ten timed conformance relations and relate them. Second, we introduce a notion of timed test and define how to apply tests to implementations. Finally, we give an algorithm to derive sound and complete test suites with respect to the implementation relations presented in the paper.

One of the main problems to test timed systems is that the tester has to decide when to apply the next input to the system under test. Even though the tester could determine good sequences of inputs to find a big variety of errors, the quality of the test suite usually depends on the time when the different parts of the sequences are applied. In this paper we give a formal methodology to provide good time values to test timed systems. These values are computed by taking into account the time stability of the system, that is, if the system is more likely to remain in its current internal state during a given time interval then no input will be applied during that period. In other words, our method will (probabilistically) find those time values that are closer to a change of state in the system, being these values more suitable to apply the appropriate input to the system.

In this paper we formally present a methodology that allows us to adapt the intelligence of the agents conforming a multiagent system. We perform such adaptation of the intelligence by means of genetics. We call the resulting environments metaadaptable systems, as they allow to adapt the adaptive capabilities of elements. So, we propose systems in which the capability of the agents to adapt themselves to the environment (via mechanisms producing some kind of intelligence) is itself adapted according to the changes of their own environment. Actually, finding the optimal intelligence mechanism and the optimal key parameters that govern it is not a trivial task, as they dramatically depend on the environment that produces the events that an agent has to use to infer its own conclusions. We denote by intelligence mechanism any strategy to produce behavior that could be considered intelligent. We show a simple but illustrative example of such a metaadaptable system, which can be easily extended to deal with more real situations as the construction of software systems based on intelligent mobile agents. This system has been fully implemented, and some interesting conclusions have been extracted from it.

This paper presents a generic formal framework to specify and test autonomous e-commerce agents. First, the formalism to represent the behaviour of agents is introduced. The corresponding machinery to define how implementations can be tested follows. Two testing approaches are considered. The first of them, which can be called active, is based on stimulating the implementation under test (IUT) with a test. The peculiarity is that tests will be defined as a special case of autonomous e-commerce agent. The second approach, which can be called passive, consists of observing the behaviour of the tested agent in an environment containing other agents. As a case study the framework is applied to the e-commerce system Kasbah. Copyright © 2005 John Wiley & Sons, Ltd.