Average Case Analysis of Bounded Space Bin Packing Algorithms

We consider the one-dimensional bin packing problem and analyze the average case performance of bounded space algorithms. The analysis covers a wide variety of bin packing algorithms including Next-K Fit, K-Bounded Best Fit and Harmonic algorithms, as well as of others. We assume discrete item sizes, an assumption which is true in most real-world applications of bin packing. We present a Markov chains method which is general enough to calculate results for any i.i.d. discrete item size distribution. The paper presents many results heretofore unknown or conjectured from simulation. Some of the results are surprising as they differ considerably from results for continuous distributions.     

Optimal Edge Ranking of Trees in Linear Time

Given a tree, finding an optimal node ranking and finding an optimal edge ranking are interesting computational problems. The former problem already has a linear time algorithm in the literature. For the latter, only recently polynomial time algorithms have been revealed, and the best known algorithm requires more than quadratic time. In this paper we present a new approach for finding an optimal edge ranking of a tree, improving the time complexity to linear. Received April 22, 1998; revised November 19, 1998.     

Optimal foraging algorithm for global optimization

An optimization algorithm, inspired by the animal Behavioral Ecology Theory—Optimal Foraging Theory, named the Optimal Foraging Algorithm (OFA) has been developed. As a new stochastic search algorithm, OFA is used to solve the global optimization problems following the animal foraging behavior. During foraging, animals know how to find the best pitch with abundant prey; in establishing OFA, the basic operator of OFA was constructed following this foraging strategy. During foraging, an individual of the foraging swarms obtained more opportunities to capture prey through recruitment; in OFA the recruitment was adopted to ensure the algorithm has a higher chance to receive the optimal solution. Meanwhile, the precise model of prey choices proposed by Krebs et al. was modified and adopted to establish the optimal solution choosing strategy of OFA. The OFA was tested on the benchmark functions that present difficulties common to many global optimization problems. The performance comparisons among the OFA, real coded genetic algorithms (RCGAs), Differential Evolution (DE), Particle Swarm Optimization (PSO) algorithm, Bees Algorithm (BA), Bacteria Foraging Optimization Algorithm (BFOA) and Shuffled Frog-leaping Algorithm (SFLA) are carried out through experiments. The parameter of OFA and the dimensions of the multi-functions are researched. The results obtained by experiments and Kruskal-Wallis test indicate that the performance of OFA is better than the other six algorithms in terms of the ability to converge to the optimal or the near-optimal solutions, and the performance of OFA is the second-best one from the view of the statistical analysis.     

Weighted Average Errors in Set-Membership Estimation

Average-case analysis provides knowledge about the quality of estimation algorithms in the case when the influence of outliers (exceptionally difficult elements) is to be neglected. This is in contrast with the worst-case analysis, where exceptionally difficult elements are of particular interest. In this paper we consider the average behavior of estimation algorithms based on corrupted information, with values in a subspace of the problem element space. We study two local average errors, with respect to probability measures defined by a class of weight functions. We define the optimal algorithm and derive exact error formulas, in Euclidean norms in problem element and information spaces. The formulas explicitly show the dependence of the errors on basic components of the problem, in particular on the weights. Attention is paid to the class of isotropic weight functions, examples of which are provided by truncated Gaussian weight functions. An extension of the results to non-Euclidean norms in the information space in a special case is shown. Date received: July 19, 2002. Date revised: January 9, 2003. This research was partly supported by AGH Grant No. 10.420.03.     

Optimal Sublogarithmic Time Parallel Algorithms on Rooted Forests

The problem of finding a sublogarithmic time optimal parallel algorithm for 3 -colouring rooted forests has been open for long. We settle this problem by obtaining an O(( log log n) log ^* ( log ^* n)) time optimal parallel algorithm on a TOLERANT Concurrent Read Concurrent Write (CRCW) Parallel Random Access Machine (PRAM). Furthermore, we show that if f(n) is the running time of the best known algorithm for 3 -colouring a rooted forest on a COMMON or TOLERANT CRCW PRAM, a fractional independent set of the rooted forest can be found in O(f(n)) time with the same number of processors, on the same model. Using these results, it is shown that decomposable top-down algebraic computation and, hence, depth computation (ranking), 2 -colouring and prefix summation on rooted forests can be done in O( log n) optimal time on a TOLERANT CRCW PRAM. These algorithms have been obtained by proving a result of independent interest, one concerning the self-simulation property of TOLERANT: an N -processor TOLERANT CRCW PRAM that uses an address space of size O(N) only, can be simulated on an n -processor TOLERANT PRAM in O(N/n) time, with no asymptotic increase in space or cost, when n=O(N/ log log N) . Received May 20, 1997; revised June 15, 1998.     

遗传算法在矩形件优化排样中的应用

遗传算法是一种全局优化的数值计算方法。与传统优化算法相比,它对函数的要求不高,一般不会陷入局部最优解,更适应于求解大规模离散化问题。该文将遗传算法应用于工程问题的一个典型离散优化问题矩形件优化排样。通过该算法可以找出高效率的排样加工方法。设计结果能广泛应用于各零件的排样加工实例。     

Linear Quadratic Optimal Control of Time-Varying Systems with Indefinite Costs on Hilbert Spaces

In this paper we consider time-varying linear systems on Hilbert spaces and study the linear quadratic optimal control problem with an indefinite performance criterion over an infinite time interval. An example shows that in contrast to the finite-dimensional situation, in general, the solvability of the optimal control problem does not imply the solvability of the associated integral Riccati equation. Using an operator theoretic approach towards the time-varying integral Riccati equation, we derive equivalent conditions for the solvability of both problems. Date received: October 8, 1997. Date revised: August 10, 1998.     

Reductions Do Not Preserve Fast Convergence Rates in Average Time

Cai and Selman [CS] proposed the following definition for measuring average computation time: A time function t is T on average over a distribution μ if, for all , , where . This definition results in a modification of Levin's notion of average time [L]. The effect of the modification is to control the rate of convergence of the expressions that define average computation time. With this modification, they proved a hierarchy theorem for average-time complexity that is as tight as the Hartmanis—Stearns [HS] hierarchy theorem for worst-case deterministic time. They also proved that under a fairly reasonable condition on distributions, called condition W, a distributional problem is solvable in average polynomial time under the modification exactly when it is solvable in average polynomial time under Levin's definition. Various notions of reductions, as defined by Levin [L] and others, play a central role in the study of average-case complexity. However, the class of distributional problems that are solvable in average polynomial time under the modification is not closed under the standard reductions. In particular, we prove that there is a distributional problem that is not solvable in average polynomial time under the modification but is reducible, by the identity function, to a distributional problem that is, and whose distribution even satisfies condition W. Received August 26, 1996; revised May 29, 1997.     

Optimal genetic manipulations in batch bioreactor control

Advances in metabolic engineering have enabled bioprocess optimization at the genetic level. Large-scale systematic models are now available at a genome level for many biological processes. There is, thus, a motivation to develop advanced control algorithms, using these complex models, to identify optimal performance strategies both at the genetic and bioreactor level. In the present paper, the bilevel optimization framework previously developed by the authors is coupled with control algorithms to determine the genetic manipulation strategies in practical bioprocess applications. The bilevel optimization includes a linear programming problem in the inner level and a nonlinear optimization problem in the outer level. Both gradient-based and stochastic methods are used to solve the nonlinear optimization problem. Ethanol production in an anaerobic batch fermentation of Escherichia coli is considered in case studies that demonstrate optimization of ethanol production, batch time, and multi-batch scheduling.     

Average Case Analyses of List Update Algorithms, with Applications to Data Compression

We study the performance of the Timestamp (0) (TS(0)) algorithm for self-organizing sequential search on discrete memoryless sources. We demonstrate that TS(0) is better than Move-to-front on such sources, and determine performance ratios for TS(0) against the optimal off-line and static adversaries in this situation. Previous work on such sources compared on-line algorithms only with static adversaries. One practical motivation for our work is the use of the Move-to-front heuristic in various compression algorithms. Our theoretical results suggest that in many cases using TS(0) in place of Move-to-front in schemes that use the latter should improve compression. Tests using implementations on a standard corpus of test documents demonstrate that TS(0) leads to improved compression. Received December 3, 1995; revised April 5, 1997.     

湿法炼锌沉铁过程氧化速率优化控制

湿法炼锌沉铁过程针铁矿沉淀形成的条件要求苛刻, 亚铁离子的氧化速率必须控制在合理的范围内才能保证溶液中的铁离子以针铁矿形式除去. 本文在沉铁过程动态模型的基础上, 根据针铁矿沉淀形成的条件和结合流程工艺要求, 优化设定每个反应器出口的亚铁离子浓度, 进而建立针铁矿法沉铁过程氧化速率优化控制模型. 采用控制参数化方法将最优控制求解问题转化为非线性规划, 通过状态转移优化算法求取最优的氧气和氧化锌控制率, 以合理控制沉铁过程亚铁离子的氧化速率. 仿真结果表明, 优化控制模型计算所得的控制量不仅可以保证反应过程的氧化速率符合生成针铁矿沉淀的条件, 而且可以稳定生产流程.     

Tight error bounds for projection algorithms in conditional set membership estimation

In set membership estimation, conditional problems arise when the estimate must belong to a given set of assigned structure. Conditional projection algorithms provide estimates that are suboptimal in terms of the worst-case estimation error. In order to precisely evaluate the suboptimality level of these estimators, tight upper bounds on the estimation errors must be computed as a function of the conditional radius of information, which represents the minimum achievable error. In this paper, tight bounds are derived for ℓ_∞ and ℓ₁ estimation errors, in a general setting which allows to consider any compact set of feasible problem elements and linearly parameterized estimates.     

The Analysis of Evolutionary Algorithms—A Proof That Crossover Really Can Help

Abstract. Evolutionary algorithms are randomized search heuristics that were invented in the sixties and have been intensively applied and studied since the eighties. Since then there have been only a few theoretical investigations and no sound theoretical foundation. One of the main sources of difficulty for theoretical analyses is the crossover operator. It can be useful only if the current population of strings has a certain diversity. Here it is proved that an evolutionary algorithm can produce enough diversity such that the use of crossover can speedup the expected optimization time from superpolynomial to a polynomial of small degree.     

混合粗粒度遗传算法在约束最优化问题中的应用

选取粗粒度遗传算法,并针对其过早收敛、收敛速度慢的缺陷进行改进,提出混合粗粒度遗传算法。混合粗粒度遗传算法按照适应度函数值对染色体群体进行分组,各分组采用不同的惩罚系数、交叉、变异算子;同时采用同种互斥和最优解保留策略。实验结果表明该算法在约束最优化问题中应用良好。     

多粒度决策系统属性约简的最优粒度选择

粒计算理论从多个角度、多个不同的粒度层次出发,对不确定、不精确或复杂的问题进行求解,现已成为人工智能领域研究的一种重要方法。针对决策系统属性约简与高效决策的粒度选择问题,分析了多粒度决策系统中信息粒与粒度划分的概念,定义了粒化度量和粒结构关于对象的粒化粗糙度,能够准确地反映决策系统中不同粒结构下的知识粒度大小。为弥补传统决策系统约简往往只考虑基于论域属性约简的缺陷,讨论了基于对象的局部约简方法,提出了基于论域和对象的决策系统最优粒度选择约简算法,并结合实例验证了该算法的有效性。     

基于IAG-ABC算法的路径覆盖测试用例生成技术

针对遗传算法(genetic algorithm,GA)存在搜索初期收敛速度过快、易陷入局部最优解、未能充分结合搜索过程中的反馈信息,同时人工蜂群(artificial bee colony,ABC)算法存在初期寻优速度缓慢、局部搜索具有很大随机性等问题,对遗传算法和人工蜂群算法分别进行了改进,并将改进后的两种算法进行融合,实现两者的优势互补,提出了一种自适应遗传-蜂群（improved adaptive genetic-artificial bee colony, IAG-ABC）算法。采用路径覆盖信息设计引导算法搜索方向的适应度函数,并用IAG-ABC算法实现路径覆盖的测试用例生成,实验结果表明,相对于标准遗传算法和自适应遗传算法,IAG-ABC算法在测试用例生成效率和覆盖率上均有一定的优势。     

Automatic face detection in video sequences using local normalization and optimal adaptive correlation techniques

Automatic human face detection from video sequences is an important component of intelligent human computer interaction systems for video surveillance, face recognition, emotion recognition and face database management. This paper proposes an automatic and robust method to detect human faces from video sequences that combines feature extraction and face detection based on local normalization, Gabor wavelets transform and Adaboost algorithm. The key step and the main contribution of this work is the incorporation of a normalization technique based on local histograms with optimal adaptive correlation (OAC) technique to alleviate a common problem in conventional face detection methods: inconsistent performance due to sensitivity to variation illuminations such as local shadowing, noise and occlusion. The approach uses a cascade of classifiers to adopt a coarse-to-fine strategy for achieving higher detection rates with lower false positives. The experimental results demonstrate a significant performance improvement gains and achieved by local normalization over methods without normalizations in real video sequences with a wide range of facial variations in color, position, scale, and varying lighting conditions.     

Optimal Parallel Randomized Algorithms for the Voronoi Diagram of Line Segments in the Plane

Abstract. We present an optimal parallel randomized algorithm for the Voronoi diagram of a set of n nonintersecting (except possibly at endpoints) line segments in the plane. Our algorithm runs in O(log n) time with high probability using O(n) processors on a CRCW PRAM. This algorithm is optimal in terms of work done since the sequential time bound for this problem is Ω(n log n) . Our algorithm improves by an O(log n) factor the previously best known deterministic parallel algorithm, given by Goodrich, ó'Dúnlaing, and Yap, which runs in O( log ² n) time using O(n) processors. We obtain this result by using a new ``two-stage' random sampling technique. By choosing large samples in the first stage of the algorithm, we avoid the hurdle of problem-size ``blow-up' that is typical in recursive parallel geometric algorithms. We combine the two-stage sampling technique with efficient search and merge procedures to obtain an optimal algorithm. This technique gives an alternative optimal algorithm for the Voronoi diagram of points as well (all other optimal parallel algorithms for this problem use the transformation to three-dimensional half-space intersection).     

关于子带编码中的最优对称小波

线性相位的对称小波在信号或图像压缩中有广泛的应用.对称小波有几个自由度的选择灵活性,可以依信号或图像类型选择最优小波.文中讨论子带编码中的最优对称小波问题,其最优性能指标为编码增益Gsbc达极大.对于平稳随机信号,最优小波唯一依赖信号的谱密度.最后给出了几种典型谱密度分布所对应的最优对称小波.