共查询到20条相似文献,搜索用时 15 毫秒
1.
Continuous random variables are widely used to mathematically describe random phenomena in engineering and the physical sciences. In this paper, we present a higher-order logic formalization of the Standard Uniform random variable as the limit value of the sequence of its discrete approximations. We then show the correctness of this specification by proving the corresponding probability distribution properties within the HOL theorem prover, summarizing the proof steps. The formalized Standard Uniform random variable can be transformed to formalize other continuous random variables, such as Uniform, Exponential, Normal, etc., by using various non-uniform random number generation techniques. The formalization of these continuous random variables will enable us to perform an error free probabilistic analysis of systems within the framework of a higher-order-logic (HOL) theorem prover. For illustration purposes, we present the formalization of the Continuous Uniform random variable based on the formalized Standard Uniform random variable, and then utilize it to perform a simple probabilistic analysis of roundoff error in HOL. 相似文献
2.
在多播网络通信中,网络编码的应用,实现了最大流最小割定理所决定的多播传输的最大理论传输容量。对这一问题,可采用线性multicast,线性broadcast,线性dispersion,以及generic等线性网络编码构造算法进行求解。但这些方法,计算复杂度较高。在研究generic线性网络编码算法的基础上,结合离散路由的使用,对其进行了改进,提出了一种改进的多播网络编码算法,并给出了算法的合理性证明。复杂度分析表明,该算法较generic线性网络编码算法,复杂度有显著的下降。 相似文献
3.
Xiaoxia Huang 《国际通用系统杂志》2013,42(3):319-328
This paper researches portfolio selection problem in combined uncertain environment of randomness and fuzziness. Due to the complexity of the security market, expected values of the security returns may not be predicted accurately. In the paper, expected returns of securities are assumed to be given by fuzzy variables. Security returns are regarded as random fuzzy variables, i.e. random returns with fuzzy expected values. Following Markowitz's idea of quantifying investment return by the expected value of the portfolio and risk by the variance, a new type of mean–variance model is proposed. In addition, a hybrid intelligent algorithm is provided to solve the new model problem. A numeral example is also presented to illustrate the optimization idea and the effectiveness of the proposed algorithm. 相似文献
4.
Real-time systems usually involve a subtle interaction of a number of distributed components and have a high degree of parallelism,
which makes their performance analysis quite complex. Thus, traditional techniques, such as simulation, or the state-based
formal methods usually fail to produce reasonable results. In this paper, we propose to use higher-order-logic (HOL) theorem
proving for the performance analysis of real-time systems. The idea is to formalize the real-time system as a logical conjunction
of HOL predicates, whereas each one of these predicates define an autonomous component or process of the given real-time system.
The random or unpredictable behavior found in these components is modeled as random variables. This formal specification can
then be used in a HOL theorem prover to reason about both functional and performance related properties of the given real-time
system. In order to illustrate the practical effectiveness of our approach, we present the analysis of the Stop-and-Wait protocol,
which is a classical example of real-time systems. The functional correctness of the protocol is verified by proving that
the protocol ensures reliable data transfers. Whereas, the average message delay relation is verified in HOL for the sake
of performance analysis. The paper includes the protocol’s formalization details along with the HOL proof sketches for the
major theorems. 相似文献
5.
链路预测中普遍存在两大问题:特征提取困难和类别数据不平衡.本文借鉴文本处理中的深度学习特征提取算法和优化问题中的粒子群算法, 提出一种基于词向量的粒子群优化算法(Word2vec-PSO).该方法首先通过随机游走产生网络序列后, 利用Word2vec算法对节点序列特征提取.然后在有监督的条件下, 利用粒子群算法对提取好的特征进行筛选, 并确定重采样的参数来解决类别数据不平衡问题, 并分析了不同链路预测算法的计算复杂性.最后将本文的算法与基于相似性、基于深度学习、基于不平衡数据的3类链路预测算法, 在4个不同的时序网络中进行实证对比研究.结果表明, 本文提出的链路预测算法预测精度较高, 算法更加稳定且具有普适性. 相似文献
6.
Shahla Nemati Mohammad Ehsan Basiri Nasser Ghasem-Aghaee Mehdi Hosseinzadeh Aghdam 《Expert systems with applications》2009,36(10):12086-12094
Protein function prediction is an important problem in functional genomics. Typically, protein sequences are represented by feature vectors. A major problem of protein datasets that increase the complexity of classification models is their large number of features. Feature selection (FS) techniques are used to deal with this high dimensional space of features. In this paper, we propose a novel feature selection algorithm that combines genetic algorithms (GA) and ant colony optimization (ACO) for faster and better search capability. The hybrid algorithm makes use of advantages of both ACO and GA methods. Proposed algorithm is easily implemented and because of use of a simple classifier in that, its computational complexity is very low. The performance of proposed algorithm is compared to the performance of two prominent population-based algorithms, ACO and genetic algorithms. Experimentation is carried out using two challenging biological datasets, involving the hierarchical functional classification of GPCRs and enzymes. The criteria used for comparison are maximizing predictive accuracy, and finding the smallest subset of features. The results of experiments indicate the superiority of proposed algorithm. 相似文献
7.
进化算法成功应用于求解各种复杂优化问题,其理论研究尚处于初级阶段。时间复杂性分析可以估计算法的平均运行时间,是进化算法理论研究中的重要方向和有力工具。讨论了漂移分析和进化算法时间复杂性的关系,利用吸收马尔科夫链给出漂移定理的一个新的证明;用一步平均漂移估计算法计算时间,得到了线性函数进化算法时间复杂度的一个一般性的结果。这些结果有助于更好地理解进化算法的工作原理和性能。 相似文献
8.
《CVGIP: Graphical Models and Image Processing》1994,56(2):109-123
The most common approach for incorporating discontinuities in visual reconstruction problems makes use of Bayesian techniques, based on Markov random field models, coupled with stochastic relaxation and simulated annealing. Despite their convergence properties and flexibility in exploiting a priori knowledge on physical and geometric features of discontinuities, stochastic relaxation algorithms often present insurmountable computational complexity. Recently, considerable attention has been given to suboptimal deterministic algorithms, which can provide solutions with much lower computational costs. These algorithms consider the discontinuities implicitly rather than explicitly and have been mostly derived when there are no interactions between two or more discontinuities in the image model. In this paper we propose an algorithm that allows for interacting discontinuities, in order to exploit the constraint that discontinuities must be connected and thin. The algorithm, called E-GNC, can be considered an extension of the graduated nonconvexity (GNC), first proposed by Blake and Zisserman for noninteracting discontinuities. When applied to the problem of image reconstruction from sparse and noisy data, the method is shown to give satisfactory results with a low number of iterations. 相似文献
9.
In this paper, we consider single-machine scheduling problem in which processing time of a job is described by a convex decreasing resource consumption function. The objective is to minimize the total amount of resource consumed subject to a constraint on total weighted flow time. The optimal resource allocation is obtained for any arbitrary job sequence. The computational complexity of the general problem remains an open question, but we present and analyze some special cases that are solvable by using polynomial time algorithms. For the general problem, several dominance properties and some lower bounds are derived, which are used to speed up the elimination process of a branch-and-bound algorithm proposed to solve the problem. A heuristic algorithm is also proposed, which is shown by computational experiments to perform effectively and efficiently in obtaining near-optimal solutions. The results show that the average percentage error of the proposed heuristic algorithm from optimal solutions is less than 3%. 相似文献
10.
OFFSS: optimal fuzzy-valued feature subset selection 总被引:1,自引:0,他引:1
Feature subset selection is a well-known pattern recognition problem, which aims to reduce the number of features used in classification or recognition. This reduction is expected to improve the performance of classification algorithms in terms of speed, accuracy and simplicity. Most existing feature selection investigations focus on the case that the feature values are real or nominal, very little research is found to address the fuzzy-valued feature subset selection and its computational complexity. This paper focuses on a problem called optimal fuzzy-valued feature subset selection (OFFSS), in which the quality-measure of a subset of features is defined by both the overall overlapping degree between two classes of examples and the size of feature subset. The main contributions of this paper are that: 1) the concept of fuzzy extension matrix is introduced; 2) the computational complexity of OFFSS is proved to be NP-hard; 3) a simple but powerful heuristic algorithm for OFFSS is given; and 4) the feasibility and simplicity of the proposed algorithm are demonstrated by applications of OFFSS to fuzzy decision tree induction and by comparisons with three different feature selection techniques developed recently. 相似文献
11.
针对随机最大似然算法(SML)在波达方位(DOA)估计中由于多维非线性优化导致计算复杂度大的问题,提出一种限定粒子群(PSO)算法搜索空间的SML算法。该算法克服了一个缺陷,即在采用ESPRIT算法限定PSO初始化空间时,在阵列结构是非均匀线性阵列而且信号是相干信号时ESPRIT算法不能直接处理信号,且需要采用一组预处理技术,这增加了算法计算的复杂度。提出的算法的关键之处在于采用假设技术确定初始化点来代替ESPRIT算法的解,结合克拉美罗界(CRB)确定PSO算法的初始化解空间。这一方法不必再采用预处理技术,且利用限定PSO初始化空间的算法大大降低了SML算法的计算复杂度。实验结果表明,提出的算法为相干情况和非相干情况都提供了相当好的初始值。最后,将该算法与许多现有算法进行比较,验证提出算法的有效性和准确性。 相似文献
12.
13.
Scheduling Multi-Mode Projects under Uncertainty to Optimize Cash Flows: A Monte Carlo Ant Colony System Approach
下载免费PDF全文
![点击此处可从《计算机科学技术学报》网站下载免费的PDF全文](/ch/ext_images/free.gif)
Project scheduling under uncertainty is a challenging field of research that has attracted increasing attention. While most existing studies only consider the single-mode project scheduling problem under uncertainty, this paper aims to deal with a more realistic model called the stochastic multi-mode resource constrained project scheduling problem with discounted cash flows (S-MRCPSPDCF). In the model, activity durations and costs are given by random variables. The objective is to find an optimal baseline schedule so that the expected net present value (NPV) of cash flows is maximized. To solve the problem, an ant colony system (ACS) based approach is designed. The algorithm dispatches a group of ants to build baseline schedules iteratively using pheromones and an expected discounted cost (EDC) heuristic. Since it is impossible to evaluate the expected NPV directly due to the presence of random variables, the algorithm adopts the Monte Carlo (MC) simulation technique. As the ACS algorithm only uses the best-so-far solution to update pheromone values, it is found that a rough simulation with a small number of random scenarios is enough for evaluation. Thus the computational cost is reduced. Experimental results on 33 instances demonstrate the effectiveness of the proposed model and the ACS approach. 相似文献
14.
15.
Group shops scheduling with makespan criterion subject to random release dates and processing times 总被引:1,自引:0,他引:1
Fardin Ahmadizar Mehdi Ghazanfari Seyyed Mohammad Taghi Fatemi Ghomi 《Computers & Operations Research》2010,37(1):152-162
This paper deals with a stochastic group shop scheduling problem. The group shop scheduling problem is a general formulation that includes the other shop scheduling problems such as the flow shop, the job shop and the open shop scheduling problems. Both the release date of each job and the processing time of each job on each machine are random variables with known distributions. The objective is to find a job schedule which minimizes the expected makespan. First, the problem is formulated in a form of stochastic programming and then a lower bound on the expected makespan is proposed which may be used as a measure for evaluating the performance of a solution without simulating. To solve the stochastic problem efficiently, a simulation optimization approach is developed that is a hybrid of an ant colony optimization algorithm and a heuristic algorithm to generate good solutions and a discrete event simulation model to evaluate the expected makespan. The proposed approach is tested on instances where the random variables are normally, exponentially or uniformly distributed and gives promising results. 相似文献
16.
将几何定理机器证明的研究方法概括为确定性算法与概率性算法两大类,针对已有的确定性算法和概率性算法的证明速率偏低或占用内存过大等问题,提出一种改进的概率性算法。主要是在改进对多项式中独立变元次数的上界估计的算法的基础上,结合Schwartz-Zippel定理和统计学理论,通过随机检验若干实例来证明几何定理,并能控制证明结果不真的概率在给定的小范围内。通过改进的概率性算法,成功在2秒内证明出代数法难以证明的五圆定理。最后的多组对比实验进一步表明,改进的概率性算法具有明显高效性。 相似文献
17.
18.
This paper presents a new learning theory (a set of principles for brain-like learning) and a corresponding algorithm for the neural-network field. The learning theory defines computational characteristics that are much more brain-like than that of classical connectionist learning. Robust and reliable learning algorithms would result if these learning principles are followed rigorously when developing neural-network algorithms. This paper also presents a new algorithm for generating radial basis function (RBF) nets for function approximation. The design of the algorithm is based on the proposed set of learning principles. The net generated by this algorithm is not a typical RBF net, but a combination of "truncated" RBF and other types of hidden units. The algorithm uses random clustering and linear programming (LP) to design and train this "mixed" RBF net. Polynomial time complexity of the algorithm is proven and computational results are provided for the well known Mackey-Glass chaotic time series problem, the logistic map prediction problem, various neuro-control problems, and several time series forecasting problems. The algorithm can also be implemented as an online adaptive algorithm. 相似文献
19.
Pratima Rai Kapil K. Sharma 《Computers & Mathematics with Applications》2012,63(1):118-132
The objective of this paper is to present a numerical study of a class of boundary value problems of singularly perturbed differential difference equations (SPDDE) which arise in computational neuroscience in particular in the modeling of neuronal variability. The mathematical modeling of the determination of the expected time for the generation of action potential in the nerve cells by random synaptic inputs in dendrites includes a general boundary-value problem for singularly perturbed differential difference equation with shifts. The problem considered in this paper exhibit turning point behavior which add to the complexity in the construction of numerical approximation to the solution of the problem as well as in obtaining theoretical estimates on the solution. Exponentially fitted finite difference scheme based on Il’in-Allen-Southwell fitting is used on a specially designed mesh. Some numerical examples are given to validate convergence and computational efficiency of the proposed numerical scheme. Effect of the shifts on the layer structure is illuminated for the considered examples. 相似文献