An experimental study of adaptive control for evolutionary algorithms

In this paper, we investigate how adaptive operator selection techniques are able to efficiently manage the balance between exploration and exploitation in an evolutionary algorithm, when solving combinatorial optimization problems. We introduce new high level reactive search strategies based on a generic algorithm's controller that is able to schedule the basic variation operators of the evolutionary algorithm, according to the observed state of the search. Our experiments on SAT instances show that reactive search strategies improve the performance of the solving algorithm.     

LTE系统多小区上行联合功控算法

针对传统的小区内开环功率控制算法通常以提升本小区的吞吐量性能为目标，忽略了当前小区用户对邻小区用户同频干扰的问题，为提升边缘用户性能的同时兼顾系统整体性能，提出了一种LTE系统小区间上行联合功率控制（UJPC）算法。该算法采用单基站三扇区为系统模型，以最优化系统吞吐量比例公平函数为目标，首先根据最小信干噪比（SINR）约束值和用户最大发射功率这两个约束条件得到相应的数学优化模型，然后采用连续凸近似的方法求解优化问题得出各个基站所管辖的小区内所有用户的最优发射功率。仿真结果表明，与基准的开环功控方案相比，联合功控方案在保证系统平均频谱利用率的情况下能够较大幅度地提高小区边缘频谱利用率，其最佳性能增益能达到50%。     

Optimal algorithms for adjacent side routing

We consider the switchbox routing problem of two-terminal nets in the case when all thek nets lie on two adjacent sides of the rectangle. Our routing model is the standard two-layer model. We develop an optimal algorithm that routes all the nets whenever a routing exists. The routing obtained uses the fewest possible number of vias. A more general version of this problem (adjacent staircase) is also optimally solved.This research was supported in part by NSA Contract No. MDA-904-85H-0015, NSF Grant No. DCR-86-00378, and by NSF Engineering Research Centers Program NSFD CDR 88003012.     

Shift-or string matching with super-alphabets

Given a text T[1…n] and a pattern P[1…m] over some alphabet Σ of size σ, we want to find all the (exact) occurrences of P in T. The well-known shift-or algorithm solves this problem in time O(n⌈m/w⌉), where w is the number of bits in machine word, using bit-parallelism. We show how to extend the bit-parallelism in another direction, using super-alphabets. This gives a speed-up by a factor s, where s is the number of characters processed simultaneously. The algorithm is implemented, and we show that it works well in practice too. The result is the fastest known algorithm for exact string matching for short patterns and small alphabets.     

Optimal Solutions for the Temporal Precedence Problem

Abstract. In this paper we refer to the Temporal Precedence Problem on Pure Pointer Machines . This problem asks for the design of a data structure, maintaining a set of stored elements and supporting the following two operations: insert and precedes . The operation insert (a) introduces a new element a in the structure, while the operation precedes (a,b) returns true iff element a was inserted before element b temporally. In [11] a solution was provided to the problem with worst-case time complexity O (log log n ) per operation and O(n log log n) space, where n is the number of elements inserted. It was also demonstrated that the precedes operation has a lower bound of Ω (log log n ) for the Pure Pointer Machine model of computation. In this paper we present two simple solutions with linear space and worst-case constant insertion time. In addition, we describe two algorithms that can handle the precedes (a,b) operation in O (log log d ) time, where d is the temporal distance between the elements a and b .     

Tight upper bound on the number of edges in a bipartite K3,3-free or K5-free graph with an application

We show that an n-vertex bipartite K_3,3-free graph with n?3 has at most 2n−4 edges and that an n-vertex bipartite K₅-free graph with n?5 has at most 3n−9 edges. These bounds are also tight. We then use the bound on the number of edges in a K_3,3-free graph to extend two known NC algorithms for planar graphs to K_3,3-free graphs.     

Time stepping schemes for coupled displacement and pore pressurē analysis

 The paper investigates the performance of various time stepping schemes for coupled displacement and pore pressure analysis. A number of alternative forms of the automatic time stepping method proposed by Sloan and Abbo (1999a) are also presented. These alternative schemes use different updates for the displacements and pore pressures and also adopt different starting conditions for the iterations. The automatic schemes are compared with an implicit θ-method, as well as an explicit method, through analysis of a variety of problems involving undrained loading, drained loading, and consolidation for Mohr-Coulomb and critical state models. As expected, the numerical results confirm that the explicit scheme is neither accurate nor robust. Although the implicit θ-method is accurate and fast, it fails to give a solution in a number of cases where the time step is large. The automatic schemes are shown to be accurate, fast and generally robust. Two of the automatic schemes proposed never fail to furnish a solution for the cases considered. In addition, all the automatic schemes are able to constrain the time-stepping (temporal integration) error in the displacements and pore pressures to lie near a prescribed tolerance, provided the iteration error tolerance is properly chosen. For complex soil models, it is important that the latter is set sufficiently small in order for the schemes to be able to constrain the time-stepping error to lie within a prescribed tolerance. Dedicated to the memory of Prof. Mike Crisfield, for his cheerfulness and cooperation as a colleague and friend over many years.     

Safety,liveness and fairness in temporal logic

In this paper we present syntactic characterization of temporal formulas that express various properties of interest in the verification of concurrent programs. Such a characterization helps us in choosing the right techniques for proving correctness with respect to these properties. The properties that we consider include safety properties, liveness properties and fairness properties. We also present algorithms for checking if a given temporal formula expresses any of these properties.This work is partly supported by NSF grant CCR-9212183. A preliminary version of this paper appeared in the Fourth ACM Symposium on Principles of Distributed Computing.