检索结果-内蒙古大学图书馆

A Pareto-Archived estimation-of-distribution algorithm for Multiobjective Resource-Constrained Project Scheduling Problem

引用

IEEE TRANSACTIONS ON ENGINEERING MANAGEMENT 2013年第3期60卷 617-626页

作者： Wang, Ling Fang, Chen Mu, Chun-Di Liu, Min Tsinghua Univ Dept Automat Beijing 100084 Peoples R China

In this paper, a Pareto-archived estimation-of-distribution algorithm (PAEDA) is presented for the multiobjective resource-constrained project scheduling problem with makespan and resource investment criteria. First, by combining the activity list and the resource list, an encoding scheme named activity-resource list is presented. Second, a novel hybrid probability model is designed to predict the most promising activity permutation and resource capacities. Third, a new sampling and updating mechanism for the probability model is developed to track the area with promising solutions. In addition, a Pareto archive is used to store the nondominated solutions that have been explored, and another archive is used to store the solutions for updating the probability model. The evolution process of the PAEDA is visualized showing the most promising area of the search space is tracked. Extensive numerical testing results then demonstrate that the PAEDA outperforms the existing methods.

关键词： estimation-of-distribution algorithm makespan multiobjective resource-constrained project scheduling problem (RCPSP) Pareto-archived probability model resource investment

来源：评论

学校读者我要写书评

暂无评论

estimation of distribution algorithm for Resource Allocation in Green Cooperative Cognitive Radio Sensor Networks

引用

SENSORS 2013年第4期13卷 4884-4905页

作者： Naeem, Muhammad Pareek, Udit Lee, Daniel C. Anpalagan, Alagan Ryerson Univ Dept Elect & Comp Engn Toronto ON M5B 2K3 Canada Simon Fraser Univ Sch Engn Sci Burnaby BC V5A 1S6 Canada

Due to the rapid increase in the usage and demand of wireless sensor networks (WSN), the limited frequency spectrum available for WSN applications will be extremely crowded in the near future. More sensor devices also mean more recharging/replacement of batteries, which will cause significant impact on the global carbon footprint. In this paper, we propose a relay-assisted cognitive radio sensor network (CRSN) that allocates communication resources in an environmentally friendly manner. We use shared band amplify and forward relaying for cooperative communication in the proposed CRSN. We present a multi-objective optimization architecture for resource allocation in a green cooperative cognitive radio sensor network (GC-CRSN). The proposed multi-objective framework jointly performs relay assignment and power allocation in GC-CRSN, while optimizing two conflicting objectives. The first objective is to maximize the total throughput, and the second objective is to minimize the total transmission power of CRSN. The proposed relay assignment and power allocation problem is a non-convex mixed-integer non-linear optimization problem (NC-MINLP), which is generally non-deterministic polynomial-time (NP)-hard. We introduce a hybrid heuristic algorithm for this problem. The hybrid heuristic includes an estimation-of-distribution algorithm (EDA) for performing power allocation and iterative greedy schemes for constraint satisfaction and relay assignment. We analyze the throughput and power consumption tradeoff in GC-CRSN. A detailed analysis of the performance of the proposed algorithm is presented with the simulation results.

关键词： green resource allocation carbon foot print cognitive radio cooperative communication estimation-of-distribution algorithm

来源：评论

学校读者我要写书评

暂无评论

Unbiasedness of estimation-of-distribution algorithms

引用

THEORETICAL COMPUTER SCIENCE 2019年 785卷 46-59页

作者： Friedrich, Tobias Koetzing, Timo Krejca, Martin S. Univ Potsdam Hasso Platter Inst Potsdam Germany

In the context of black-box optimization, black-box complexity is used for understanding the inherent difficulty of a given optimization problem. Central to our understanding of nature-inspired search heuristics in this context is the notion of unbiasedness. Specialized black-box complexities have been developed in order to better understand the limitations of these heuristics - especially of (population-based) evolutionary algorithms (EAs). In contrast to this, we focus on a model for algorithms explicitly maintaining a probability distribution over the search space: so-called estimation-of-distribution algorithms (EDAs). We consider the recently introduced n-Bernoulli-lambda-EDA framework, which subsumes, for example, the commonly known EDAs PBIL, UMDA, lambda-MMAS(IB), and cGA. We show that an n-Bernoulli-lambda-EDA is unbiased if and only if its probability distribution satisfies a certain invariance property under isometric automorphisms of [0, 1](n). By restricting how an n-Bernoulli-lambda-EDA can perform an update, in a way common to many examples, we derive conciser characterizations, which are easy to verify. We demonstrate this by showing that our examples above are all unbiased. (C) 2018 Elsevier B.V. All rights reserved.

关键词： estimation-of-distribution algorithm Unbiasedness Theory

来源：评论

学校读者我要写书评

暂无评论

Significance-based estimation-of-distribution algorithms 18

Significance-based Estimation-of-Distribution Algorithms

引用

Genetic and Evolutionary Computation Conference (GECCO)

作者： Doerr, Benjamin Krejca, Martin S. Ecole Polytech Lab Informat LIX Palaiseau France Hasso Plattner Inst Potsdam Germany

ISBN: (纸本)9781450356183

estimation-of-distribution algorithms (EDAs) are randomized search heuristics that maintain a stochastic model of the solution space. This model is updated from iteration to iteration based on the quality of the solutions sampled according to the model. As previous works show, this short-term perspective can lead to erratic updates of the model, in particular, to bit-frequencies approaching a random boundary value. This can lead to significant performance losses. In order to overcome this problem, we propose a new EDA that takes into account a longer history of samples and updates its model only with respect to information which it classifies as statistically significant. We prove that this significance-based compact genetic algorithm (sig-cGA) optimizes the common benchmark functions ONEMAX and LEADINGONES both in O(n logn) time, a result shown for no other EDA or evolutionary algorithm so far. For the recently proposed scGA - an EDA that tries to prevent erratic model updates by imposing a bias to the uniformly distributed model - we prove that it optimizes ONEMAX only in a time exponential in the hypothetical population size 1/rho.

关键词： estimation-of-distribution algorithm theory run time analysis

来源：评论

学校读者我要写书评

暂无评论

The Runtime of the Compact Genetic algorithm on Jump Functions

引用

algorithmICA 2021年第10期83卷 3059-3107页

作者： Doerr, Benjamin Inst Polytech Paris Ecole Polytech CNRS La Informat LIX Palaiseau France

In the first and so far only mathematical runtime analysis of an estimation-of-distribution algorithm (EDA) on a multimodal problem, Hasenohrl and Sutton (GECCO 2018) showed for any k = o(n) that the compact genetic algorithm (cGA) with any hypothetical population size mu = Omega(ne(4k) + n(3.5+epsilon)) with high probability finds the optimum of the n-dimensional jump function with jump size k in time O(mu n(1.5) log n). We significantly improve this result for small jump sizes k <= 1/20 ln n - 1. In this case, already for mu = Omega(root n log n) boolean AND poly (n) the runtime of the cGA with high probability is only O(mu root n). For the smallest admissible values of mu, our result gives a runtime of O(n log n), whereas the previous one only shows O(n(5+epsilon)). Since it is known that the cGA with high probability needs at least Omega(mu root n) iterations to optimize the unimodal ONEMAX function, our result shows that the cGA in contrast to most classic evolutionary algorithms here is able to cross moderate-sized valleys of low fitness at no extra cost. For large k, we show that the exponential (in k) runtime guarantee of Hasenohrl and Sutton is tight and cannot be improved, also not by using a smaller hypothetical population size. We prove that any choice of the hypothetical population size leads to a runtime that, with high probability, is at least exponential in the jump size k. This result might be the first non-trivial exponential lower bound for EDAs that holds for arbitrary parameter settings. To complete the picture, we show that the cGA with hypothetical population size mu = Omega(log n) with high probability needs Omega(mu root n + n log n) iterations to optimize any n-dimensional jump function. This bound was known for ONEMAX, but, as we also show, the usual domination arguments do not allow to extend lower bounds on the performance of the cGA on ONEMAX to arbitrary functions with unique optimum. As a side result, we provide a simple general metho

关键词： estimation-of-distribution algorithm Runtime analysis Combinatorial optimization Local optima Parallel runs

来源：评论

学校读者我要写书评

暂无评论

EDA-Based Scheduling of Users in the MIMO Multiple Access Channel

引用

WIRELESS PERSONAL COMMUNICATIONS 2013年第1期71卷 467-490页

作者： Naeem, Muhammad Lee, Daniel C. Simon Fraser Univ Sch Engn Sci Burnaby BC V5A 1S6 Canada

In this paper, we address a user scheduling (selection) problem in the uplink multiuser multiple input multiple output (MIMO) wireless communication system. For this problem, the computational complexity of exhaustive search grows exponentially with the number of users. We present an iterative, low-complexity, sub-optimal algorithm for this problem. We apply an estimation of distribution algorithm (EDA) for the user scheduling problem. An EDA is an evolutionary algorithm and updates its chosen population at each iteration on the basis of the probability distribution learned from the population of superior candidate solutions chosen at the previous iterations. The proposed EDA has a low computational complexity and can find a nearly optimal solution in real time for the user scheduling problem. Beyond applying the general EDA to user scheduling, we also present specific improvements that reduce computation for obtaining an acceptable solution. These improvements include the idea of generating an initial population by cyclically shifting a candidate solution. The simulation results show that our proposed algorithm performs better than other scheduling algorithms with comparable complexity.

关键词： estimation-of-distribution algorithm User scheduling MIMO Wireless communication

来源：评论

学校读者我要写书评

暂无评论

The Univariate Marginal distribution algorithm Copes Well with Deception and Epistasis

引用

EVOLUTIONARY COMPUTATION 2021年第4期29卷 543-563页

作者： Doerr, Benjamin Krejca, Martin S. Inst Polytech Paris Ecole Polytech CNRS Lab Informat LIX Palaiseau France Sorbonne Univ CNRS LIP6 Paris France

In their recent work, Lehre and Nguyen (2019) show that the univariate marginal distribution algorithm (UMDA) needs time exponential in the parent populations size to optimize the DeceptiveLeadingBlocks (DLB) problem. They conclude from this result that univariate EDAs have difficulties with deception and epistasis. In this work, we show that this negative finding is caused by the choice of the parameters of the UMDA. When the population sizes are chosen large enough to prevent genetic drift, then the UMDA optimizes the DLB problem with high probability with at most lambda(n/2+2e ln n) fitness evaluations. Since an offspring population size lambda of order nlogn can prevent genetic drift, the UMDA can solve the DLB problem with O(n(2) log n) fitness evaluations. In contrast, for classic evolutionary algorithms no better runtime guarantee than O(n(3)) is known (which we prove to be tight for the (1+1) EA), so our result rather suggests that the UMDA can cope well with deception and epistatis. From a broader perspective, our result shows that the UMDA can cope better with local optima than many classic evolutionary algorithms;such a result was previously known only for the compact genetic algorithm. Together with the lower bound of Lehre and Nguyen, our result for the first time rigorously proves that running EDAs in the regime with genetic drift can lead to drastic performance losses.

关键词： estimation-of-distribution algorithm univariate marginal distribution algorithm runtime analysis epistasis theory

来源：评论

学校读者我要写书评

暂无评论

A simplified run time analysis of the univariate marginal distribution algorithm on LeadingOnes

引用

THEORETICAL COMPUTER SCIENCE 2021年 851卷 121-128页

作者： Doerr, Benjamin Krejca, Martin S. Ecole Polytech Lab Informat LIX Inst Polytech Paris CNRS Palaiseau France Univ Potsdam Hasso Platter Inst Potsdam Germany

With elementary means, we prove a stronger run time guarantee for the univariate marginal distribution algorithm (UMDA) optimizing the LEADINGONES benchmark function in the desirable regime with low genetic drift. If the population size is at least quasilinear, then, with high probability, the UMDA samples the optimum in a number of iterations that is linear in the problem size divided by the logarithm of the UMDA's selection rate. This improves over the previous guarantee, obtained by Dang and Lehre (2015) via the deep level-based population method, both in terms of the run time and by demonstrating further run time gains from small selection rates. Under similar assumptions, we prove a lower bound that matches our upper bound up to constant factors. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Theory estimation-of-distribution algorithm Run time analysis

来源：评论

学校读者我要写书评

暂无评论

Lower bounds on the run time of the Univariate Marginal distribution algorithm on OneMax

引用

THEORETICAL COMPUTER SCIENCE 2020年 832卷 143-165页

作者： Krejca, Martin S. Witt, Carsten Univ Potsdam Hasso Platter Inst Potsdam Germany Tech Univ Denmark DTU Compute Lyngby Denmark

The Univariate Marginal distribution algorithm (UMDA) - a popular estimation-of-distribution algorithm - is studied from a run time perspective. On the classical OneMax benchmark function on bit strings of length n, a lower bound of Omega(lambda + mu root n + n logn), where mu and lambda are algorithm-specific parameters, on its expected run time is proved. This is the first direct lower bound on the run time of UMDA. It is stronger than the bounds that follow from general black-box complexity theory and is matched by the run time of many evolutionary algorithms. The results are obtained through advanced analyses of the stochastic change of the frequencies of bit values maintained by the algorithm, including carefully designed potential functions. These techniques may prove useful in advancing the field of run time analysis for estimation-of-distribution algorithms in general. (C) 2018 Elsevier B.V. All rights reserved.

关键词： estimation-of-distribution algorithm Run time analysis Lower bound

来源：评论

学校读者我要写书评

暂无评论

Comparison of Cauchy EDA and pPOEMS algorithms on the BBOB Noiseless Testbed 10

Comparison of Cauchy EDA and pPOEMS algorithms on the BBOB N...

引用

12th Annual Genetic and Evolutionary Computation Conference (GECCO)

作者： Posik, Petr Kubalik, Jiri Czech Tech Univ Dept Cybernet Fac Elect Eng Prague 16627 6 Czech Republic

ISBN: (纸本)9781450300735

estimation-of-distribution algorithm using Cauchy sampling distribution is compared with the iterative prototype optimization algorithm with evolved improvement steps. While Cauchy EDA is better on unimodal functions, iterative prototype optimization is more suitable for multimodal functions. This paper compares the results for both algorithms in more detail and adds to the understanding of their key features and differences.

关键词： Benchmarking Black-box optimization estimation-of-distribution algorithm Cauchy distribution POEMS Iterative prototype optimization with evolved improvement steps

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：