In this paper we propose a new evolutionary clustering algorithm named E-means. E-means is an evolutionary extension of k-means algorithm that is composed by a revised k-means algorithm and an evolutionary approach to...
详细信息
ISBN:
(纸本)9783540921363
In this paper we propose a new evolutionary clustering algorithm named E-means. E-means is an evolutionary extension of k-means algorithm that is composed by a revised k-means algorithm and an evolutionary approach to Gaussian mixture model, which estimates automatically the number of clusters and the optimal mean for each cluster. More specifically, the proposed E-means algorithm defines an entropy-based fitness function, and three genetic operators for merging, initiation, and deletion components. We conduct two sets of experiments using a synthetic dataset and an existing benchmark to validate the proposed E-means algorithm. The results obtained in the first experiment show that the algorithm can estimate exactly the optimal number of Clusters for a set of data. In the second experiment. we compute nine major clustering validity indices and compare the corresponding results With those obtained using four established Clustering techniques, and found that our E-means algorithm achieves better clustering structures.
Particle swarm optimization (PSO) is a global search optimization algorithm that simulates the swarm behavior of birds. Compared with other evolutionary computation algorithms, PSO is simple, easy to implement, and ha...
详细信息
ISBN:
(纸本)9798350321456
Particle swarm optimization (PSO) is a global search optimization algorithm that simulates the swarm behavior of birds. Compared with other evolutionary computation algorithms, PSO is simple, easy to implement, and has powerful optimization ability. However, the performance of PSO is heavily affected by the inertial weight parameter. Many studies have shown that PSO variant with smaller inertial weight has good local search ability and can improve the solution accuracy;while the PSO variant with larger inertial weight has good global search ability and can avoid falling into local optimum to a certain extent. Therefore, many researchers have proposed a variety of control schemes for dynamically adjusting the inertia weight. This paper systematically introduces, analyzes, and compares five typical decreasing and random control schemes in the literatures for dynamically adjusting the inertia weight. Moreover, a decreasing scheme based on concave exponential function, and two incremental schemes based on concave exponential function and convex exponential function are also designed and compared. The investigations and comparisons are conducted on 10 typical different unimodal and multimodal functions. The experimental investigations and comparisons are helpful for researchers to adopt different kind of inertia weight control schemes to solve different kinds of optimization problems.
Multivariate-to-anything methods for partially specified random vector generation work by transforming samples from a driving distribution into samples characterized by given marginals and correlations. The correlatio...
详细信息
ISBN:
(纸本)0780385152
Multivariate-to-anything methods for partially specified random vector generation work by transforming samples from a driving distribution into samples characterized by given marginals and correlations. The correlations of the transformed random vector are controlled by the driving distribution;sampling a partially specified random vector requires finding an appropriate driving distribution. This paper motivates the use of evolution strategies for solving such problems and compares evolution strategies to conjugate gradient methods in the context of solving a Dirichlet-to-anything transformation. It is shown that the evolution strategy is at least as effective as the conjugate gradient method for solution of the parameterization problem.
evolutionary Algorithms (EAs) are commonly used for finding optimal solutions in large and difficult search spaces. In real-time strategy (RTS) games, huge search spaces in addition to the highly dynamic environments ...
详细信息
ISBN:
(纸本)9780954901660
evolutionary Algorithms (EAs) are commonly used for finding optimal solutions in large and difficult search spaces. In real-time strategy (RTS) games, huge search spaces in addition to the highly dynamic environments constitute tremendous challenges for the generation of game artificial intelligence (AI), yet there have been very few attempts to date that use EAs to optimize game AI in RTS games. This paper describes an experiment regarding how RTS military strategies can be optimized using a branch of EAs known as evolutionary Programming (EP). To reduce the effect of dynamic noise arising from the highly stochastic RTS playing environment, a (mu+mu) EP survivor selection strategy is applied. The results from the experiment clearly show that firstly, the problem is non-trivial and more importantly, the (mu+mu) EP methodology is able to automatically generate good military strategies and significantly outperforms the control setup of using randomly generated strategies. Moreover, the results also show that the evolutionary optimization approach could learn very fast and can thus be practically used as an online game AI evolutionary method against human players, which can then make the game more challenging and interesting for the human players.
Opponent models are necessary in games where the game state is only partially known to the player, since the player must infer the state of the game based on the opponent's actions. This paper presents an architec...
详细信息
ISBN:
(纸本)9781595936974
Opponent models are necessary in games where the game state is only partially known to the player, since the player must infer the state of the game based on the opponent's actions. This paper presents an architecture and a process for developing neural network game players that utilize explicit opponent models in order to improve game play against unseen opponents. The model is constructed as a mixture over a set of cardinal opponents, i.e. opponents that represent maximally distinct game strategies. The model is trained to estimate the likelihood that the opponent will make the same move as each of the cardinal opponents would in a given game situation. Experiments were performed in the game of Guess It, a simple game of imperfect information that has no optimal strategy for defeating specific opponents. Opponent modeling is therefore crucial to play this game well. Both opponent modeling and game-playing neural networks were trained using NeuroEvolution of Augmenting Topologies (NEAT). The results demonstrate that game-playing provided with the model outperform networks not provided with the model when played against the same previously unseen opponents. The "cardinal mixture" architecture therefore constitutes a promising approach for general and dynamic opponent modeling in game-playing.
Many real-world engineering and science problems can be mapped to Boolean satisfiability problems (SAT). CDCL SAT solvers are among the most efficient solvers. Previous work showed that instances derived from a partic...
详细信息
ISBN:
(纸本)9781538627266
Many real-world engineering and science problems can be mapped to Boolean satisfiability problems (SAT). CDCL SAT solvers are among the most efficient solvers. Previous work showed that instances derived from a particular problem class exhibit a unique underlying structure which impacts the effectiveness of a solver's variable selection scheme. Thus, customizing the variable scoring heuristic of a solver to a particular problem class can significantly enhance the solver's performance;however, manually performing such customization is very labor intensive. This paper presents a system for automating the design of variable scoring heuristics for CDCL solvers, making it feasible to tailor solvers to arbitrary problem classes. Experimental results are provided demonstrating that this system, which evolves variable scoring heuristics using an asynchronous parallel hyper-heuristics approach employing genetic programming, has the potential to create more efficient solvers for particular problem classes.
Patrolling an environment consists in visiting as frequently as possible its most relevant areas in order to supervise, control or protect it. This task is commonly performed by a team of agents that need to coordinat...
详细信息
ISBN:
(纸本)9781479914883
Patrolling an environment consists in visiting as frequently as possible its most relevant areas in order to supervise, control or protect it. This task is commonly performed by a team of agents that need to coordinate their actions for achieving optimal performance. We address here the problem of multi-agent patrolling in known environments where agents may move at different speeds and visit priorities on some areas may be specified. Two classes of patrolling strategies are studied: the single-cycle strategies and the partition-based strategies. Several single-core and multi-core variants of a template state-of-the-art hybrid algorithm are proposed for generating partition-based strategies. These are experimentally compared with a state-of-the-art heuristic-based algorithm generating single-cycle strategies. Experimental results show that: the heuristic-based algorithm only generates efficient strategies when agents move at the same speeds and no visit priorities have been defined;all single-core variants are equivalent;multi-core hybrid algorithms may improve overall quality or reduce variance of the solutions obtained by single-core algorithms.
Reinforcement learning (RL) has proven to be a powerful paradigm for deriving complex behaviors from simple reward signals in a wide range of environments. When applying RL to continuous control agents in simulated ph...
详细信息
ISBN:
(纸本)9781450363099
Reinforcement learning (RL) has proven to be a powerful paradigm for deriving complex behaviors from simple reward signals in a wide range of environments. When applying RL to continuous control agents in simulated physics environments, the body is usually considered to be part of the environment. However, during evolution the physical body of biological organisms and their controlling brains are co -evolved, thus exploring a much larger space of actuator/controller configurations. Put differently, the intelligence does not reside only in the agent's mind, but also in the design of their body. We propose a method for uncovering strong agents, consisting of a good combination of a body and policy, based on combining RL with an evolutionary procedure. Given the resulting agent, we also propose an approach for identifying the body changes that contributed the most to the agent performance. We use the Shapley value from cooperative game theory to find the fair contribution of individual components, taking into account synergies between components. We evaluate our methods in an environment similar to the the recently proposed Robo-Sumo task, where agents in a software physics simulator compete in tipping over their opponent or pushing them out of the arena. Our results show that the proposed methods are indeed capable of generating strong agents, significantly outperforming baselines that focus on optimizing the agent policy alone. A video is available at: https://***/CH1ecRim9PI
We present a theoretical analysis of Watson's Hierarchical-if-and-only-if (HIFF) problem using a variety of tools. These include schema theory and course graining, the concept of effective fitness, and statistical...
详细信息
ISBN:
(纸本)1595930108
We present a theoretical analysis of Watson's Hierarchical-if-and-only-if (HIFF) problem using a variety of tools. These include schema theory and course graining, the concept of effective fitness, and statistical analysis. We first review the use of Stephen's exact schema equations and schema basis to compute the changes in population distributions over time. We then use the tools described above to solve for the limit distributions of the 2 and 4-bit HIFF problems, and show that these limit distributions are essentially one-dimensional. We also show that a combination of fitness and the number of break points (a rough measure of distance in crossover space) in a string can be used to almost completely explain the limit distribution in the 4-bit HIFF problem.
Boolean networks consist of nodes that represent binary variables, which are computed as a function of the values represented by their adjacent nodes. This local processing entails global behaviors, such as the conver...
详细信息
ISBN:
(纸本)9783319946498;9783319946481
Boolean networks consist of nodes that represent binary variables, which are computed as a function of the values represented by their adjacent nodes. This local processing entails global behaviors, such as the convergence to fixed points, a behavior found in the context of the density classification problem, where the aim is the network's convergence to a fixed point of the prevailing node value in the initial global configuration of the network;in other words, a global decision is targeted, but according to a constrained, non-global action. Here, we rely on evolutionary searches in order to find rules and network topologies with good performance in the task. All nodes' neighborhoods are assumed to be defined by non-regular and bidirectional links, and the Boolean function of the network initialized by the local majority rule. Two evolutionary searches are carried out: first, in the space of network topologies, guided by a parameter (omega) related to the 'small-worldness' of the networks, and then, in the space of Boolean functions, but constraining the network topologies to the best family identified in the previous experiment. The results clearly make it evident the key and successful role of the. parameter in looking for solutions to the task at issue.
暂无评论