共查询到20条相似文献,搜索用时 15 毫秒
1.
2.
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. 相似文献
3.
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. 相似文献
4.
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. 相似文献
5.
Bolesław Kacewicz 《Mathematics of Control, Signals, and Systems (MCSS)》2003,16(2-3):238-253
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. 相似文献
6.
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. 相似文献
7.
遗传算法在矩形件优化排样中的应用 总被引:12,自引:1,他引:11
遗传算法是一种全局优化的数值计算方法。与传统优化算法相比,它对函数的要求不高,一般不会陷入局部最优解,更适应于求解大规模离散化问题。该文将遗传算法应用于工程问题的一个典型离散优化问题矩形件优化排样。通过该算法可以找出高效率的排样加工方法。设计结果能广泛应用于各零件的排样加工实例。 相似文献
8.
Birgit Jacob 《Mathematics of Control, Signals, and Systems (MCSS)》1999,12(2):196-218
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. 相似文献
9.
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. 相似文献
10.
Optimal genetic manipulations in batch bioreactor control 总被引:2,自引:0,他引:2
Kapil G. Gadkar Author Vitae Author Vitae Francis J. Doyle III Author Vitae 《Automatica》2006,42(10):1723-1733
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. 相似文献
11.
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. 相似文献
12.
湿法炼锌沉铁过程氧化速率优化控制 总被引:2,自引:2,他引:0
湿法炼锌沉铁过程针铁矿沉淀形成的条件要求苛刻, 亚铁离子的氧化速率必须控制在合理的范围内才能保证溶液中的铁离子以针铁矿形式除去. 本文在沉铁过程动态模型的基础上, 根据针铁矿沉淀形成的条件和结合流程工艺要求, 优化设定每个反应器出口的亚铁离子浓度, 进而建立针铁矿法沉铁过程氧化速率优化控制模型. 采用控制参数化方法将最优控制求解问题转化为非线性规划, 通过状态转移优化算法求取最优的氧气和氧化锌控制率, 以合理控制沉铁过程亚铁离子的氧化速率. 仿真结果表明, 优化控制模型计算所得的控制量不仅可以保证反应过程的氧化速率符合生成针铁矿沉淀的条件, 而且可以稳定生产流程. 相似文献
13.
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 ℓ1 estimation errors, in a general setting which allows to consider any compact set of feasible problem elements and linearly parameterized estimates. 相似文献
14.
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. 相似文献
15.
16.
粒计算理论从多个角度、多个不同的粒度层次出发,对不确定、不精确或复杂的问题进行求解,现已成为人工智能领域研究的一种重要方法。针对决策系统属性约简与高效决策的粒度选择问题,分析了多粒度决策系统中信息粒与粒度划分的概念,定义了粒化度量和粒结构关于对象的粒化粗糙度,能够准确地反映决策系统中不同粒结构下的知识粒度大小。为弥补传统决策系统约简往往只考虑基于论域属性约简的缺陷,讨论了基于对象的局部约简方法,提出了基于论域和对象的决策系统最优粒度选择约简算法,并结合实例验证了该算法的有效性。 相似文献
17.
针对遗传算法(genetic algorithm,GA)存在搜索初期收敛速度过快、易陷入局部最优解、未能充分结合搜索过程中的反馈信息,同时人工蜂群(artificial bee colony,ABC)算法存在初期寻优速度缓慢、局部搜索具有很大随机性等问题,对遗传算法和人工蜂群算法分别进行了改进,并将改进后的两种算法进行融合,实现两者的优势互补,提出了一种自适应遗传-蜂群(improved adaptive genetic-artificial bee colony, IAG-ABC)算法。采用路径覆盖信息设计引导算法搜索方向的适应度函数,并用IAG-ABC算法实现路径覆盖的测试用例生成,实验结果表明,相对于标准遗传算法和自适应遗传算法,IAG-ABC算法在测试用例生成效率和覆盖率上均有一定的优势。 相似文献
18.
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. 相似文献
19.
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
2
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). 相似文献
20.
关于子带编码中的最优对称小波 总被引:1,自引:0,他引:1
线性相位的对称小波在信号或图像压缩中有广泛的应用.对称小波有几个自由度的选择灵活性,可以依信号或图像类型选择最优小波.文中讨论子带编码中的最优对称小波问题,其最优性能指标为编码增益Gsbc达极大.对于平稳随机信号,最优小波唯一依赖信号的谱密度.最后给出了几种典型谱密度分布所对应的最优对称小波. 相似文献