In this paper, the monotone submodular maximization problem (SM) is studied. SM is to find a subset of size kappa from a universe of size n that maximizes a monotone submodular objective function f. We show using a no...
详细信息
ISBN:
(纸本)9780999241196
In this paper, the monotone submodular maximization problem (SM) is studied. SM is to find a subset of size kappa from a universe of size n that maximizes a monotone submodular objective function f. We show using a novel analysis that the Pareto optimization algorithm achieves a worst-case ratio of (1 - epsilon)(1 - 1/e) in expectation for every cardinality constraint kappa < P, where P <= n + 1 is an input, in O(nP ln(1/epsilon)) queries of f. In addition, a novel evolutionary algorithm called the biased Pareto optimization algorithm, is proposed that achieves a worst-case ratio of (1 - epsilon)(1 - 1/e - epsilon) in expectation for every cardinality constraint kappa < P in O(n ln(P) ln(1/epsilon)) queries of f. Further, the biased Pareto optimization algorithm can be modified in order to achieve a worst-case ratio of (1 - epsilon)(1 - 1/e - epsilon) in expectation for cardinality constraint kappa in O(n ln(1/epsilon)) queries of f. An empirical evaluation corroborates our theoretical analysis of the algorithms, as the algorithms exceed the stochastic greedy solution value at roughly when one would expect based upon our analysis.
evolutionary algorithms (EA) usually carry out an efficient exploration of the search-space, but get often trapped in local minima and do not prove the optimality of the solution. Interval-based techniques, on the oth...
详细信息
ISBN:
(纸本)9783319116839;9783319116822
evolutionary algorithms (EA) usually carry out an efficient exploration of the search-space, but get often trapped in local minima and do not prove the optimality of the solution. Interval-based techniques, on the other hand, yield a numerical proof of optimality of the solution. However, they may fail to converge within a reasonable time due to their exponential complexity and their inability to quickly compute a good approximation of the global minimum. The contribution of this paper is a hybrid algorithm called Charibde in which a particular EA, Differential Evolution, cooperates with a branch and bound algorithm endowed with interval propagation techniques. It prevents premature convergence toward local optima and is highly competitive with both deterministic and stochastic existing approaches. We demonstrate its efficiency on a benchmark of highly multimodal problems, for which we provide previously unknown global minima and certification of optimality.
For many years, computational tools have been widely applied to study such complex systems as metabolic networks. One of the principal questions in modeling of metabolic systems is the parameter estimation of model, w...
详细信息
The cooperation of evolutionary algorithms in a simple hierarchical model was proposed. Three adaptive variants of differential evolution and covariance-matrix-adaptation evolutionary strategy were chosen for cooperat...
详细信息
ISBN:
(纸本)9783319198248;9783319198231
The cooperation of evolutionary algorithms in a simple hierarchical model was proposed. Three adaptive variants of differential evolution and covariance-matrix-adaptation evolutionary strategy were chosen for cooperation. The performance of the model was tested on the learning-based CEC 2015 suite of 15 functions at levels of the dimension 10 and 30. The results showed that the proposed cooperation is beneficial. The proposed model was superior significantly compared to any of individual algorithms included in the cooperation. The cooperation of the selected four algorithms appeared beneficial especially in the problems of dimension D = 30, where the cooperative model outperformed all the algorithms including other cooperative models in comparison.
In this paper the novel selection method which can be used in any evolutionary algorithm is presented. Proposed method is based on steering between exploration and exploitation properties of evolutionary algorithms. I...
详细信息
ISBN:
(纸本)9783642132315
In this paper the novel selection method which can be used in any evolutionary algorithm is presented. Proposed method is based on steering between exploration and exploitation properties of evolutionary algorithms. In presented approach, at the start of the algorithm operation the probability of selection of individuals for new population is equal for all individuals. In such a case the algorithm possesses maximal value of pressure on global search of a solution space (exploration of solution space). As number of generations increases, the algorithm searches the solution space in more locally manner (exploitation of solution space) at expense of global search property. The results obtained using proposed method are compared with the results obtained using other selection methods like: roulette selection, elitist selection, fan selection, tournament selection, deterministic selection, and truncation selection. The comparison is performed using test functions chosen from literature. The results obtained using proposed selection method are better in many cases than results obtained using other selection techniques.
Inherent parallelism is regarded as one of the most important advantages of evolutionary algorithms. This paper aims at making an initial study on the speedup of scalable parallel evolutionary algorithms. First the sc...
详细信息
ISBN:
(纸本)9780780394872
Inherent parallelism is regarded as one of the most important advantages of evolutionary algorithms. This paper aims at making an initial study on the speedup of scalable parallel evolutionary algorithms. First the scalable parallel evolutionary algorithms are described;then the speedup of such scalable algorithms is defined based on the first hitting time;Using the new definition, the relationship between population diversity and superlinear speedup is analyzed;finally a case study demonstrates how population diversity plays a crucial role in generating the superlinear speedup.
Reversible circuits, i.e. circuits which map each possible input vector to a unique output vector, build the basis for emerging applications e.g. in the domain of low-power design or quantum computation. As a result, ...
详细信息
ISBN:
(数字)9783642205200
ISBN:
(纸本)9783642205194
Reversible circuits, i.e. circuits which map each possible input vector to a unique output vector, build the basis for emerging applications e.g. in the domain of low-power design or quantum computation. As a result, researchers developed various approaches for synthesis of this kind of logic. In this paper, we consider the ESOP-based synthesis method. Here, functions given as Exclusive Sum of Products (ESOPs) are realized. In contrast to conventional circuit optimization, the quality of the resulting circuits depends thereby not only on the number of product terms, but on further criteria as well. In this paper, we present an approach based on an evolutionary algorithm which optimizes the function description with respect to these criteria. Instead of ESOPs, Pseudo Kronecker Expression (PSDKRO) are thereby utilized enabling minimization within reasonable time bounds. Experimental results confirm that the proposed approach enables the realization of circuits with significantly less cost.
In this paper further investigation of the previously proposed method of speeding up single-objective evolutionary algorithms is done. The method is based on reinforcement learning which is used to choose auxiliary fi...
详细信息
ISBN:
(纸本)9780769549132;9781467346511
In this paper further investigation of the previously proposed method of speeding up single-objective evolutionary algorithms is done. The method is based on reinforcement learning which is used to choose auxiliary fitness functions. The requirements for this method are formulated. The compliance of the method with these requirements is illustrated on model problems such as Royal Roads problem and H-IFF optimization problem. The experiments confirm that the method increases the efficiency of evolutionary algorithms.
A detailed review of a wide range of meta-heuristic and evolutionary algorithms in a systematic manner and how they relate to engineering optimization problems This book introduces the main metaheuristic algorithms an...
详细信息
ISBN:
(数字)9781119387053
ISBN:
(纸本)9781119386995
A detailed review of a wide range of meta-heuristic and evolutionary algorithms in a systematic manner and how they relate to engineering optimization problems This book introduces the main metaheuristic algorithms and their applications in optimization. It describes 20 leading meta-heuristic and evolutionary algorithms and presents discussions and assessments of their performance in solving optimization problems from several fields of engineering. The book features clear and concise principles and presents detailed descriptions of leading methods such as the pattern search (PS) algorithm, the genetic algorithm (GA), the simulated annealing (SA) algorithm, the Tabu search (TS) algorithm, the ant colony optimization (ACO), and the particle swarm optimization (PSO) technique. Chapter 1 of Meta-heuristic and evolutionary algorithms for Engineering Optimization provides an overview of optimization and defines it by presenting examples of optimization problems in different engineering domains. Chapter 2 presents an introduction to meta-heuristic and evolutionary algorithms and links them to engineering problems. Chapters 3 to 22 are each devoted to a separate algorithm— and they each start with a brief literature review of the development of the algorithm, and its applications to engineering problems. The principles, steps, and execution of the algorithms are described in detail, and a pseudo code of the algorithm is presented, which serves as a guideline for coding the algorithm to solve specific applications. This book: Introduces state-of-the-art metaheuristic algorithms and their applications to engineering optimization; Fills a gap in the current literature by compiling and explaining the various meta-heuristic and evolutionary algorithms in a clear and systematic manner; Provides a step-by-step presentation of each algorithm and guidelines for practical implementation and coding of algorithms; Discusses and assesses the performance of metaheuristic algorithms in mu
With the advancement of Internet of Things, the cost of System-on-Chips (in terms of area, performance, etc.) becomes increasingly relevant for realizing affordable as well as performant devices. Although System-on-Ch...
详细信息
ISBN:
(纸本)9781728157580
With the advancement of Internet of Things, the cost of System-on-Chips (in terms of area, performance, etc.) becomes increasingly relevant for realizing affordable as well as performant devices. Although System-on-Chips are very diverse with respect to specifications and requirements, some components are ubiquitous. One of them is the Hardware/Software Interface, which serves for controlling communication and interconnected functionalities between Hardware and Software. Motivated by their common use, the implementation of optimized interfaces towards certain costs (in terms of area, performance, etc.) becomes a central problem in the design of embedded systems. In this work we introduce a novel optimization method for minimizing the cost of Hardware/Software Interfaces using Convolutional Neural Networks coupled with evolutionary algorithms.
暂无评论