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

Evolutionary programming using a mixed mutation strategy

INFORMATION SCIENCES 2007年第1期177卷 312-327页

作者： Dong, Hongbin He, Jun Huang, Houkuan Hou, Wei Beijing Jiaotong Univ Sch Comp Sci & Informat Technol Beijing 100044 Peoples R China Beijing Jiaotong Univ Dept Comp Sci & Informat Technol Beijing 100044 Peoples R China Harbin Normal Univ Dept Comp Sci Harbin 150080 Peoples R China Univ Birmingham Sch Comp Sci Birmingham B15 2TT W Midlands England

Different mutation operators have been proposed in evolutionary programming, but for each operator there are some types of optimization problems that cannot be solved efficiently. A mixed strategy, integrating several mutation operators into a single algorithm, can overcome this problem. Inspired by evolutionary game theory, this paper presents a mixed strategy evolutionary programming algorithm that employs the Gaussian, Cauchy, Levy, and single-point mutation operators. The novel algorithm is tested on a set of 22 benchmark problems. The results show that the mixed strategy performs equally well or better than the best of the four pure strategies does, for all of the benchmark problems. (c) 2006 Elsevier Inc. All rights reserved.

关键词： design of algorithms randomized algorithms global optimization evolutionary programming mixed strategy

来源：评论

学校读者我要写书评

暂无评论

On the longest increasing subsequence of a circular list

引用

INFORMATION PROCESSING LETTERS 2007年第2期101卷 55-59页

作者： Albert, M. H. Atkinson, M. D. Nussbaum, Doron Sack, Jorg-Rudiger Santoro, Nicola Univ Otago Dept Comp Sci Dunedin New Zealand Carleton Univ Sch Comp Sci Ottawa ON K1S 5B6 Canada

The longest increasing circular subsequence (LICS) of a list is considered. A Monte Carlo algorithm to compute it is given which has worst case execution time 0(n(3/2) log n) and storage requirement 0(n). It is proved that the expected length mu(n) of the LICS satisfies lim(n ->infinity) mu(n)/2 root = 1. Numerical experiments with the algorithm suggest that vertical bar mu(n) - 2 root n vertical bar = O(n(1/6)). (c) 2006 Elsevier B.V. All rights reserved.

关键词： combinatorial problems randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

New approaches for virtual private network design

引用

SIAM JOURNAL ON COMPUTING 2007年第3期37卷 706-721页

作者： Eisenbrand, Friedrich Grandoni, Fabrizio Oriolo, Gianpaolo Skutella, Martin Univ Dortmund Fachbereich Informat D-44221 Dortmund Germany Univ Roma La Sapienza Dipartimento Informat I-00198 Rome Italy Univ Roma Tor Vergata Dipartimento Ingn Impresa I-00165 Rome Italy Univ Dortmund Fachbereich Math D-44221 Dortmund Germany

Virtual private network design is the following NP-hard problem. We are given a communication network represented as a weighted graph with thresholds on the nodes which represent the amount of flow that a node can send to and receive from the network. The task is to reserve capacities at minimum cost and to specify paths between every ordered pair of nodes such that all valid traffic-matrices can be routed along the corresponding paths. Recently, this network design problem has received considerable attention in the literature. It is motivated by the fact that the exact amount of flow which is exchanged between terminals is not known in advance and prediction is often elusive. The main contributions of this paper are as follows: (1) Using Hu's 2-commodity flow theorem, we provide a new and considerably stronger lower bound on the cost of an optimum solution. With this lower bound we reanalyze a simple routing scheme which has been described in the literature many times, and provide an improved upper bound on its approximation ratio. (2) We present a new randomized approximation algorithm. In contrast to earlier approaches from the literature, the resulting solution does not have tree structure. A combination of our new algorithm with the simple routing scheme yields an expected performance ratio of 3.79 for virtual private network design. This is a considerable improvement of the previously best known 5.55-approximation result [ A. Gupta, A. Kumar, and T. Roughgarden, Simpler and better approximation algorithms for network design, in Proceedings of the ACM Symposium on Theory of Computing, ACM, New York, 2003, pp. 365 -372]. (3) Our VPND algorithm uses a Steiner tree approximation algorithm as a subroutine. It is known that an optimum Steiner tree can be computed in polynomial time if the number of terminals is logarithmic. Replacing the approximate Steiner tree computation with an exact one whenever the number of terminals is sufficiently small, we finally reduce t

关键词： approximation algorithms randomized algorithms network design

来源：评论

学校读者我要写书评

暂无评论

Choosing a random peer in Chord

引用

ALGORITHMICA 2007年第2期49卷 147-169页

作者： King, Valerie Lewis, Scott Saia, Jared Young, Maxwell Univ New Mexico Dept Comp Sci Albuquerque NM 87131 USA Univ Victoria Dept Comp Sci Victoria BC V8W 3P6 Canada

We present two new algorithms, Arc Length and Peer Count, for choosing a peer uniformly at random from the set of all peers in Chord (Proceedings of the ACM SIGCOMM 2001 Technical Conference, 2001). We show analytically that, in expectation, both algorithms have latency O(log n) and send O(log n) messages. Moreover, we show empirically that the average latency and message cost of Arc Length is 10.01log n and that the average latency and message cost of Peer Count is 20.02log n. To the best of our knowledge, these two algorithms are the first fully distributed algorithms for choosing a peer uniformly at random from the set of all peers in a Distributed Hash Table (DHT). Our motivation for studying this problem is threefold: to enable data collection by statistically rigorous sampling methods;to provide support for randomized, distributed algorithms over peer-to-peer networks;and to support the creation and maintenance of random links, and thereby offer a simple means of improving fault-tolerance.

关键词： peer-to-peer distributed Hash table Chord randomized algorithms distributed algorithms data collection attack-resistance

来源：评论

学校读者我要写书评

暂无评论

Approximate counting in bounded arithmetic

引用

JOURNAL OF SYMBOLIC LOGIC 2007年第3期72卷 959-993页

作者： Jerabek, Emil Acad Sci Czech Republic Inst Math CR-11567 Prague Czech Republic

We develop approximate counting of sets definable by Boolean circuits in bounded arithmetic using the dual weak pigeonhole principle (dWPHP(PV)), as a generalization of results from [15]. We discuss applications to fo... 详细信息

关键词： bounded arithmetic pigeonhole principle counting randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Exterminator: Automatically correcting memory errors with high probability 07

Exterminator: Automatically correcting memory errors with hi...

引用

Conference on Programming Language Design and Implementation

作者： Novark, Gene Berger, Emery D. Zorn, Benjamin G. Univ Massachusetts Dept Comp Sci Amherst MA 01003 USA Microsoft Res One Microsoft Way Redmond WA 98052 USA

ISBN: (纸本)9781595936332

Programs written in C and C++ are susceptible to memory errors, including buffer overflows and dangling pointers. These errors, which can lead to crashes, erroneous execution, and security vulnerabilities, are notoriously costly to repair. Tracking down their location in the source code is difficult, even when the full memory state of the program is available. Once the errors are finally found, fixing them remains challenging: even for critical security-sensitive bugs, the average time between initial reports and the issuance of a patch is nearly one month. We present Exterminator, a system that automatically corrects heap-based memory errors without programmer intervention. Exterminator exploits randomization to pinpoint errors with high precision. From this information, Exterminator derives runtime patches that fix these errors both in current and subsequent executions. In addition, Exterminator enables collaborative bug correction by merging patches generated by multiple users. We present analytical and empirical results that demonstrate Exterminator's effectiveness at detecting and correcting both injected and real faults.

关键词： algorithms languages reliability security DieFast Exterminator dynamic memory allocation error correction memory errors probabilistic memory safety randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Communication in Dynamic Radio Networks

Communication in Dynamic Radio Networks

引用

16th Annual ACM Symposium on Principles of Distributed Computing

作者： Clementi, Andrea E. F. Pasquale, Francesco Monti, Angelo Silvestri, Riccardo Univ Roma Tor Vergata Dipartimento Matemat I-00133 Rome Italy

ISBN: (纸本)9781595936165

We study the completion time of distributed broadcast protocols in dynamic radio networks. The dynamic network is modelled by means of adversaries: we consider two of them that somewhat axe the extremal cases. We first analyze the weakest one, i.e., an oblivious, memoryless random adversary. At each time slot t, a graph G(t) is selected according to the well-known random graph model G(n,p). We derive a randomized protocol that, on input n and p, completes broadcasting in O(log n) time. Then, we prove that any randomized protocol has Omega(logn) completion time. When p is unknown, we present air oblivious homogeneous version of the Bar Yehuda-Goldreich-Itai's randomized protocol having O(log(2) n) completion time and we prove a lower bound Omega(log(2) n/log log n) that holds for any randomized oblivious homogeneous protocol. We emphasize that the above (poly-)logarithmic upper bounds also hold when random graphs are sparse and disconnected, i.e., for p = o(ln n/n). We then consider the deterministic worst-case adversary that, at each time slot, can make any network change (thus the strongest adversary). Up to now, it is not even known whether finite expected completion time is achievable against this adversary. We present a simple randomized protocol that works in O(n(2)/log n) completion time. This bound is then shown to be optimal.

关键词： randomized algorithms Radio Networks

来源：评论

学校读者我要写书评

暂无评论

Energy Efficient Randomised Communication in Unknown AdHoc Networks 07

Energy Efficient Randomised Communication in Unknown AdHoc N...

引用

19th Annual Symposium on Parallelism in algorithms and Architectures

作者： Berenbrink, Petra Hu, Zengjian Cooper, Colin Simon Fraser Univ Sch Comp Sci Burnaby BC V5A 1S6 Canada

ISBN: (纸本)9781595936677

This paper studies broadcasting and gossiping algorithms in random and general AdHoc networks. Our goal is not only to minimise the broadcasting and gossiping time, but also to minimise the energy consumption, which is measured in terms of the total number of messages (or transmissions) sent,. We assume that the nodes of the network do not know the network, and that they cart only send with a fixed power, meaning they can not adjust the area sizes that their messages cover. We believe that under these circumstances the number of transmissions is a very good measure for the overall energy consumption. For random networks;we present a broadcasting algorithm where every node transmits at most once. We show that our algorithm broadcasts in O(log n) steps, w.h.p., where n is the number of nodes. We then present a O(d log n) (d is the expected degree) gossiping algorithm using O(log n) messages per node. For general networks with known diameter D, we present a randomised broadcasting algorithm with optimal broadcasting time O(D log(n/D) + log(2)n) that uses art expected number of O(log(2) n/ log(n/D)) transmissions per node. We also show a tradeoff result between the broadcasting time and the number of transmissions: we construct a network such that any oblivious algorithm using a tinge-invariant distribution requires Q(log2 n/ log(n/D)) messages per node in order to finish broadcasting in optimal time. This demonstrates the tightness of our upper bound. We also show that no oblivious algorithm can complete broadcasting w.h.p. using o(log n) messages per node.

关键词： AdHoc networks Broadcasting Gossiping randomized algorithms Energy Efficiency

来源：评论

学校读者我要写书评

暂无评论

Infrastructure leasing problems

引用

12th International Integer Programming and Combinatorial Optimization Conference

作者： Anthony, Barbara M. Gupta, Anupam Carnegie Mellon Univ Dept Math Sci Pittsburgh PA 15213 USA Carnegie Mellon Univ Dept Comp Sci Pittsburgh PA USA

ISBN: (纸本)9783540727910

Consider the following Steiner Tree leasing problem. Given a graph G = (V, E) with root r, and a sequence of terminal sets D-t subset of V for each day t is an element of [T]. A feasible solution to the problem is a set of edges E-t for each t connecting D-t to r. Instead of obtaining edges for a single day at a time, or for infinitely long (both of which give Steiner tree problems), we lease edges for say, { a day, a week, a month, a year}. Naturally, leasing an edge for a longer period costs less per unit of time. What is a good leasing strategy? In this paper, we give a general approach to solving a wide class of such problems by showing a close connection between deterministic leasing problems and problems in multistage stochastic optimization. All our results are in the offline setting.

关键词： Approximation algorithms Graph and network algorithms randomized algorithms Stochastic combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

New results on the scenario design approach

New results on the scenario design approach

引用

46th IEEE Conference on Decision and Control

作者： Campi, M. C. Calafiore, G. C. Univ Brescia Dipartimento Elettron Automaz Via Branze 38 I-25123 Brescia Italy Politecn Torino Dipartimento Automat & Informat Turin Italy

ISBN: (纸本)9781424414970

ne scenario optimization method developed in [1] is a theoretically sound and practically effective technique for solving in a probabilistic setting robust convex optimization problems arising in systems and control design, that would otherwise be hard to tackle via standard deterministic techniques. In this note, we further explore some aspects of the scenario methodology, and present two results pertaining to the tightness of the sample complexity bounds. We also state a new theorem that enables the user to make a-priori probabilistic claims on the scenario solution, with one level of probability only.

关键词： scenario design robust control randomized algorithms Probabilistic robustness robust convex optimization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：