Search

Pareto-based evolutionary multiobjective approaches are methods that use the Pareto dominance concept to guide the search of evolutionary algorithms towards the Pareto frontier of a problem. To address the challenge of providing an entire set of optimal solutions they use specially designed mechanisms for preserving search diversity and maintaining the non-dominated solutions set. The limitation of the Pareto dominance relation in high-dimensional spaces has rendered these methods inefficient for many-objective optimization. In this paper we aim to exploit existing Pareto-based methods to compute the generalized Nash equilibrium for multi-player games by replacing the Pareto dominance relation with an equilibrium generative relation. The generalized Nash equilibrium extends the Nash equilibrium concept by considering constraints over players’ strategies. Numerical experiments indicate that the selected methods can be employed for equilibria computation even for games with up to twenty players.

The critical node detection problem describes a class of graph problems that involves identifying sets of nodes that influence a given graph metric. One variant of this problem is to find the nodes that - when removed from the graph - maximize the number of connected components in the remaining graph. This is an example of a practical problem with multiple real-world applications in epidemic control, immunization strategies, social networks, biology, etc. This paper proposes the use of a simple GA to identify the set of the critical nodes of the problem without designing special problem specific variation operators. Problem specific information is used only in the fitness function and the constraint handling technique. We show that this simple approach performs as well as state-of-art methods.

This paper explores the influence maximization problem for the weighted cascade model by considering an approach based on Shapley value and Extremal Optimization. The Shapley value is a solution concept in cooperative game theory that, given a total value of the game assigns to each player a value as part of it, computed as its marginal contribution to all possible coalitions of players. In the weighted cascade model we consider adding and updating nodes in the initial set during the extremal optimization search based on their Shapley value in an approach already tested for the independent cascade model. Comparisons with other methods by means of numerical experiments show that results reported by this approach are promising, prompting for further research in this direction.

The community detection problem is an emerging part of complex networks, identifying communities can offer important insights for the network. Several methods exist for detecting communities in single layered networks, however for multilayered the problem has not been so thoroughly studied. In this paper we propose a new method for the community detection problem for multilayered network, based on the idea of semi-aggregation of different layers. We compare the proposed method with existing approaches in the literature on benchmark problems and apply our method on a co-authorship multiplex network.

Representation and analysis of publication data in the form of a network has become a common method of illustrating and evaluating the scientific output of a group or of a scientific field. Co-authorship networks also reveal patterns and collaboration practices. In this paper we propose the use of a hypergraph model—a generalized network—to represent publication data by considering papers as hypergraph nodes. Hyperedges, connecting the nodes, represent the authors connecting all their papers. We show that this representation is more straightforward than other authorship network models. Using the hypergraph model we propose a collaboration measure of an author that reflects the influence of that author over the collaborations of its co-authors. We illustrate the introduced concepts by analyzing publishing data of computer scientists and mathematicians in Romania over a 10 year period.

Determining the critical nodes in a complex network is an essential computation problem. Several variants of this problem have emerged due to its wide applicability in network analysis. In this article we study the bi-objective critical node detection problem (BOCNDP), which is a new variant of the well-known critical node detection problem, optimizing two objectives at the same time: maximizing the number of connected components and minimizing the variance of their cardinalities. Evolutionary multi-objective algorithms (EMOA) are a straightforward choice to solve this type of problem. We propose three different smart initialization strategies which can be incorporated into any EMOA. These initialization strategies take into account the basic properties of the networks. They are based on the highest degree, random walk (RW) and depth-first search. Numerical experiments were conducted on synthetic and real-world network data. The three different initialization types significantly improve the performance of the EMOA.

The paper proposes a general game theoretical model, called capacity demand game, for treating simultaneous capacity requests in scarce-resource cognitive radio (CR) environments. The approach is that of non-cooperative games describing CR interactions in terms of radio resource access. Experiments reveal stable states (equilibria) that favour an equitable usage of radio resources to the benefit of all participants. Several equilibria are detected and discussed: Nash (NE), Pareto, joint Nash–Pareto, and Lorenz equilibrium.

The problem of Network Influence Maximization is approached by an Extremal Optimization algorithm called Shapley value Extremal Optimization (SvEO). The influence maximization problem for the independent cascade model is considered as a cooperative game. In this cooperative game players seek to choose seeder nodes to maximize the value of the game computed as the size of the influence set of their cascade model by maximizing their average marginal contribution to all possible player coalitions (i.e. subsets of the seeder set). SvEO is compared with other influence maximization algorithms by means of numerical experiments, with promising results. Possible implications of the use of the Shapley value are discussed using a network constructed from highly cited publication data in the field of computer science.

Influence Extremal Optimization (InfEO) is an algorithm based on Extremal Optimization, adapted for the influence maximization problem for the independent cascade model. InfEO maximizes the marginal contribution of a node to the influence set of the model. Numerical experiments are used to compare InfEO with other influence maximization methods, indicating the potential of this approach. Practical results are discussed on a network constructed from publication data in the field of computer science.

The map equation is one of the most efficient methods of evaluating a possible community structure of a network, computed by using Shanon’s entropy and probabilities that a random walker would exit a community or would wonder inside it. Infomap, the method that optimizes the map equation to reveal community structures, is one of the most efficient computational approach to this problem when dealing with weighted, directed or hierarchical networks. However, for some unweighted and undirected networks, Infomap fails completely to uncover any structure. In this paper we propose an alternate way of computing probabilities used by the map equation by adding information about 3-cliques corresponding to links in order to enhance the behavior of Infomap in unweighted networks. Numerical experiments performed on standard benchmarks show the potential of the approach.

The Generalized Berge-Zhukovskii equilibrium extends the Berge-Zhukovskii equilibrium problem by introducing constraints over the set of strategy profiles. The new equilibrium is computed in a dynamic environment by using an evolutionary dynamic equilibrium tracking algorithm. Numerical experiments for the generalized Cournot duopoly illustrate the capability of the approach.

Noisy extremal optimization is a new optimization-based heuristic designed to identify the community structure of complex networks by maximizing the modularity function. The extremal optimization algorithm evolves configurations that represent network covers, composed of nodes evaluated separately. Each iteration, a number of nodes having the worst fitness values are randomly assigned different communities. A network shifting procedure is used to induce a noise in the population as a diversity preserving mechanism. Numerical experiments, performed on synthetic and real-world networks, illustrate the potential of this approach.

Recent advances in brain imaging technology, coupled with large-scale brain research projects, such as the BRAIN initiative in the U.S. and the European Human Brain Project, allow us to capture brain activity in unprecedented details. In principle, the observed data is expected to substantially shape our knowledge about brain activity, which includes the development of new biomarkers of brain disorders. However, due to the high dimensionality, the analysis of the data is challenging, and selection of relevant features is one of the most important analytic tasks. In many cases, due to the complexity of search space, evolutionary algorithms are appropriate to solve the aforementioned task. In this chapter, we consider the feature selection task from the point of view of classification tasks related to functional magnetic resonance imaging (fMRI) data. Furthermore, we present an empirical comparison of conventional LASSO-based feature selection and a novel feature selection approach designed for fMRI data based on a simple genetic algorithm.

A Cournot oligopoly is used as a benchmark for Nash equilibria tracking and detection in a dynamic setting. Several dynamics that induce different trajectories for the equilibria are considered: random, linear, cosine, and spiral. A new Extremal Optimization based method is tested on the proposed dynamic setting.

Berge-Zhukovskii equilibrium is an alternate solution concept to Nash equilibrium that induces cooperation in non-cooperative games. A solution of a game is a Berge-Zhukovskii equilibrium if the payoff of each player cannot increase regardless of what the other players do. The Berge-Zhukovskii equilibrium has been found to be us useful in trust games. We propose a new method, based on evolutionary algorithms, to detect and track the Berge-Zhukovskii equilibrium of a game considering a discrete-time dynamic environment. To test our method we propose a new dynamic multiplayer game model, based on the Voluntary contribution mechanism. Numerical results show the potential of the proposed method.

The concept of community in complex networks, which is intuitively expressed as a group of nodes more densely connected to each other than to the rest of the network, has not been formally defined yet in a manner that encompasses all aspect ensuing from this intuitive description. Among existing approaches, a popular one consists in considering the network community structure as the optimum value of a fitness function that reflects the modularity of the network. Recently, a new trend to model the problem as a game having the community structure as equilibrium has emerged. Both approaches are appealing as they allow the design of heuristic approaches to this problem and benefit from their adaptability and scalability. This paper analyzes the behavior of such a heuristic that is based on extremal optimization in combination with two possible game theoretic models that consider different payoff functions, in comparison with the corresponding optimization approaches.

Community structure detection algorithms are used to identify groups of nodes that are more connected to each other than to the rest of the network. Multipartite networks are a special type of network in which nodes are divided into partitions such that there are no links between nodes in the same partition. However, such nodes may belong to the same community, making the identification of the community structure of a multipartite network computationally challenging. In this paper, we propose a new fitness function that takes into account the information induced by existing links in the network by considering shadowed connections between nodes that have a common neighbor. The existence of a correct fitness function, i.e. one whose optimum values correspond to the community structure of the network, enables the design and use of optimization-based heuristics for solving this problem. We use numerical experiments performed on artificial benchmarks to illustrate the effectiveness of this function used within an extremal optimization based algorithm and compared to existing approaches. As a direct application, a multipartite network constructed from a direct marketing database is analyzed.

The network community structure detection problem consists in finding groups of nodes that are more connected to each other than to the rest of the network. While many methods have been designed to deal with this problem for general networks, there are few methods that deal with bipartite ones. In this paper we explore the behavior of an optimization method designed for identifying the community structure of unweighted networks when dealing with bipartite networks. We find that by using the specific Barber modularity, results are comparable with those reported in literature.

The development of search-based algorithms forautomatic test case generation is a key issue in the researcharea of software testing. Evolutionary algorithms have beenfrequently used for this purpose due to their ability to solvecomplex optimization problems. In this paper we introduce anovel approach to the automatic test-case generation problemfor reactive software systems. We build upon our previouswork where we defined a test generation framework based onparameterized executable environment models written in theLutin language. The main contribution of this paper is theapplication of a self-adaptive evolutionary algorithm, JADE inthe context of our test generation framework and the evaluationof its performance on a realistic reactive system written in Scade. Our preliminary results show that adaptive differential evolutioncan be used efficiently to increase the structural coverage of thesystem under test and is easier to use due to the fewer parametersthat require fine-tuning.

The network community detection problem consists in identifying groups of nodes that are more densely connected to each other than to the rest of the network. The lack of a formal definition for the notion of community led to the design of various solution concepts and computational approaches to this problem, among which those based on optimization and, more recently, on game theory, received a special attention from the heuristic community. The former ones define the community structure as an optimum value of a fitness function, while the latter as a game equilibrium. Both are appealing as they allowed the design and use of various heuristics. This paper analyses the behavior of such a heuristic that is based on extremal optimization, when used either as an optimizer or within a game theoretic setting. Numerical results, while significantly better than those provided by other state-of-art methods, for some networks show that differences between tested scenarios do not indicate any superior behavior when using game theoretic concepts; moreover, those obtained without using any selection for survival suggest that the search is actually guided by the inner mechanism of the extremal optimization method and by the fitness function used to evaluate and compare components within an individual.

Game theory models strategic and conflicting situations and offers several solution concepts that are known as game equilibria, among which the Nash equilibrium is probably the most popular one. A less known equilibrium, called the (k,t)-robust equilibrium, has recently been used in the context of distributed computing. The (k,t)-robust equilibrium combines the concepts of k-resiliency and t-immunity: a strategy profile is k-resilient if there is no coalition of k players that can benefit from improving their payoffs by collective deviation, and it is t-immune if any action of any t players does not decrease the payoffs of the others. A strategy profile is (k,t)-robust if it is both k-resilient and t-immune. In this paper an evolutionary approach of approximating (k,t)-robust equilibria is proposed. Numerical experiments are performed on a game that models node behavior in a distributed system.

The community structure detection problem in weighted networks is tackled with a new approach based on game theory and extremal optimization, called Weighted Nash Extremal Optimization. This method approximates the Nash equilibria of a game in which nodes, as players, chose their community by maximizing their payoffs. After performing numerical experiments on synthetic networks, the new method is used to analyze functional connectivity networks of the brain in order to reveal possible connections between different brain regions. Results show that the proposed approach may be used to find biomedically relevant knowledge about brain functionality.

Reactive systems interact continuously with their environments. In order to test such systems, one needs to design executable environment models. Such models are intrinsically stochastic, because environment may vary a lot, and also because they are not perfectly known. We propose an environment-model based testing framework optimized for reactive systems, where Differential Evolution (de ) is used to fine-tune the environment model and to optimize test input generation. In order to evaluate the proposed method, we present a case study involving a real-world scade system from the domain of railway automation. The problem specification was proposed by our industrial partner, Siemens. Our experimental data shows that de can be used efficiently to increase the structural coverage of the System Under Test.

Mixing Network Extremal Optimization is a new algorithm designed to identify the community structure in networks by using a game theoretic approach and a network mixing mechanism as a diversity preserving method. Numerical experiments performed on synthetic and real networks illustrate the potential of the approach.

The Berge-Zhukovskii equilibrium is an alternate solution concept in non-cooperative game theory that formalizes cooperation in a noncooperative setting. In this paper, the ϵ-Berge-Zhukovskii equilibrium is introduced and characterized by using a generative relation. The generative relation also provides a solution to the problem of computing the ϵ-Berge-Zhukovskii equilibrium for large games, by using evolutionary algorithms. Numerical examples illustrate the approach and provide a possible application for this equilibrium concept.

The Berge-Zhukovskii optimal Nash equilibrium combines the properties of the popular Nash equilibrium with the ones of the less known Berge-Zhukovskii by proposing yet another Nash equilibrium refinement. Moreover, a computational approach for the detection of these newly proposed equilibria is presented with examples for two auction games.

The problem of equilibria detection of a discrete-time Generalized Cournot Dynamic Oligopoly is approached by using a Differential Evolution and a Particle Swarm Optimization algorithm adapted to compute and track the set of generalized Nash equilibria in a dynamic setting. Both challenges of this problem, i.e. to correctly compute the entire set of generalized Nash equilibria of the constrained (generalized) game, and also to cope with the dynamic character of the landscape, are dealt with by using a simple adaptive mechanism. Numerical experiments for settings up to 60 players are performed to illustrate the efficiency of the approach.

Discrete-time dynamic games capture changes within game parameters (payoffs), representing thus a more realistic real-world decision model. A new approach to equilibria detection and tracking in a dynamic game setting, called Dynamic Equilibrium Tracking Differential Evolution, is proposed. A discrete-time dynamic asymmetric Cournot oligopoly is introduced and used to evaluate the proposed method by means of numerical experiments for instances up to 70 players. Results indicate the effectiveness and the potential of the proposed method.

Small-cell, open capacity sharing scenarios in Cognitive Radio (CR) environments are studied from a game theoretical (GT) perspective. Simultaneous capacity requests in small-cell scenarios are modelelled as strategic interactions between CRs and analysed as resource access games. CR capacity access competition is modelled based on discrete reformulations of the Bertrand GT model. Detected equilibria describe stable game situations. Numerical simulations identify situations where Nash equilibrium (NE) is both fair and Pareto efficient or where there are multiple NE solutions to choose from, indicating a flexible range for CR strategies. Adding to the analysis are the joint Nash-Pareto solutions (intermediate between Nash and Pareto) capturing heterogeneous behaviour of players. Stable and equitable states are detected even when players have different biases.

In a mixed strategy equilibrium players randomize between their actions according to a very specific probability distribution, even though with regard to the game payoff, they are indifferent between their actions. Currently, there is no compelling model explaining why and how agents may randomize their decisions is such a way, in real world scenarios. In this paper we experiment with a model for bimatrix games, where the goal of the players is to find robust strategies for which the uncertainty in the outcome of the opponent is reduced as much as possible. We show that in an evolutionary setting, the proposed model converges to mixed strategy profiles, if these exist. The result suggest that only local knowledge of the game is sufficient to attain the adaptive convergence.

The aim of this paper is to asses simultaneous spectrum access situations that may occur in Cognitive Radio (CR) environments. The approach is that of one-shot, non-cooperative games describing CR interactions. Open spectrum access scenarios are modelled based on continuous and discrete reformulations of the Cournot game theoretical model. CR interaction situations are described by Nash and Pareto equilibria. Also, the heterogeneity of players is captured by the new concept of joint Nash-Pareto equilibrium, allowing CRs to be biased toward different types of equilibrium. Numerical simulations reveal equilibrium situations that may be reached in simultaneous access scenarios of two and three users.

Nash equilibrium in many cases is not the best choice for human players. In case of trust games the Nash equilibrium is often mutual defection which is the worst possible outcome for all players. The Berge-Zhukovskii equilibrium models a more cooperative behavior, so in case of trust games, when players gain by cooperating, it is usually a better choice than Nash equilibrium. Real life results show that players rarely follow the theoretical predictions. Our aim is to find new equilibria types that offer a more realistic modeling of human players. The fuzzy Nash---Berge-Zhukovskii equilibrium is proposed which is a fuzzy combination of the Nash and Berge-Zhukovskii equilibrium. Several continuous trust games are investigated. Numerical results indicate that fuzzy Nash---Berge-Zhukovskii equilibrium is suitable to model real-life situations.

Nash equilibrium is an important solving concept in Game Theory. Playing in Nash sense means that no player can deviate from the equilibrium strategy in order to increase her/his payoff. Some games can have several Nash equilibria. Strong Berge and strong Berge Pareto equilibria are important refinements of the Nash equilibrium. An evolutionary technique based on non-domination is proposed in order to detect the strong Berge and strong Berge Pareto equilibria. Some numerical experiments are presented in order to illustrate the proposed method.

Nash equilibrium is an important solving concept in Game Theory. Playing in Nash sense means that no player (agent) wants to deviate from the equilibrium strategy in order to increase the payoff. Some games can have more Nash equilibria. Several refinements have been developed. Strong Berge Pareto equilibrium is an important refinement of the Nash equilibrium. An evolutionary technique based on non-domination is proposed in order to detect the strong Berge Pareto equilibria. Some numerical experiments are presented in order to illustrate the proposed method.

An evolutionary procedure based on nondomination with respect to the generative relation is proposed for detecting different new equilibria types. The notions of joint Pareto-Aumann, Aumann-Pareto, Nash-Aumann and Aumann-Nash equilibrium are introduced. These combinations (representing new solution concepts) may allow an approximation of how people play in real life situations. Some numerical experiments show the importance of this new equilibria types.

The problem of equilibria detection in many-player games is computationally untractable by standard techniques. Generative relations represent an useful tool for equilibria characterization and evolutionary equilibria detection. The generative relation for k-Berge-Zhukovskii equilibrium is introduced. An evolutionary technique based on differential evolution capable to cope with hundred players is proposed. Experimental results performed on a multi-player version of Prisoner’s Dilemma indicate the effectiveness of the approach.

Two important network system problems, the job scheduling, and the bin packing problem are presented from a game theoretical perspective. Solution concepts are related to Nash and Aumann equilibria. The concept of Aumann equilibrium is viewed from a different perspective. A generative relation of the Aumann equilibrium is considered. A generative relation is used for the evolutionary detection of the equilibrium. The numerical experiments demonstrate the effectiveness of the proposed method in addressing job scheduling and bin packing problems.

A generative relation for Aumann equilibrium is proposed. An evolutionary procedure based on nondomination with respect to the generative relation is used for detecting Aumann equilibrium.