On Construction of Sparse Probabilistic Boolean Networks

In this paper we envisage building Probabilistic Boolean Networks (PBNs) from a prescribed stationary distribution. This is an inverse problem of huge size that can be subdivided into two parts — viz. (i) construction of a transition probability matrix from a given stationary distribution (Problem ST), and (ii) construction of a PBN from a given transition probability matrix (Problem TP). A generalized entropy approach has been proposed for Problem ST and a maximum entropy rate approach for Problem TP respectively. Here we propose to improve both methods, by considering a new objective function based on the entropy rate with an additional term of $L_α$-norm that can help in getting a sparse solution. A sparse solution is useful in identifying the major component Boolean networks (BNs) from the constructed PBN. These major BNs can simplify the identification of the network structure and the design of control policy, and neglecting non-major BNs does not change the dynamics of the constructed PBN to a large extent. Numerical experiments indicate that our new objective function is effective in finding a better sparse solution.     

On Generating Optimal Sparse Probabilistic Boolean Networks with Maximum Entropy from a Positive Stationary Distribution

To understand a genetic regulatory network, two popular mathematical models, Boolean Networks (BNs) and its extension Probabilistic Boolean Networks (PBNs) have been proposed. Here we address the problem of constructing a sparse Probabilistic Boolean Network (PBN) from a prescribed positive stationary distribution. A sparse matrix is more preferable, as it is easier to study and identify the major components and extract the crucial information hidden in a biological network. The captured network construction problem is both ill-posed and computationally challenging. We present a novel method to construct a sparse transition probability matrix from a given stationary distribution. A series of sparse transition probability matrices can be determined once the stationary distribution is given. By controlling the number of nonzero entries in each column of the transition probability matrix, a desirable sparse transition probability matrix in the sense of maximum entropy can be uniquely constructed as a linear combination of the selected sparse transition probability matrices (a set of sparse irreducible matrices). Numerical examples are given to demonstrate both the efficiency and effectiveness of the proposed method.     

Construction of Probabilistic Boolean Networks from a Prescribed Transition Probability Matrix: A Maximum Entropy Rate Approach

Modeling genetic regulatory networks is an important problem in genomic research. Boolean Networks (BNs) and their extensions Probabilistic Boolean Networks (PBNs) have been proposed for modeling genetic regulatory interactions. In a PBN, its steady-state distribution gives very important information about the long-run behavior of the whole network. However, one is also interested in system synthesis which requires the construction of networks. The inverse problem is ill-posed and challenging, as there may be many networks or no network having the given properties, and the size of the problem is huge. The construction of PBNs from a given transition-probability matrix and a given set of BNs is an inverse problem of huge size. We propose a maximum entropy approach for the above problem. Newton’s method in conjunction with the Conjugate Gradient (CG) method is then applied to solving the inverse problem. We investigate the convergence rate of the proposed method. Numerical examples are also given to demonstrate the effectiveness of our proposed method.     

Distribution and enumeration of attractors in probabilistic boolean networks

Many mathematical models for gene regulatory networks have been proposed. In this study, the authors study attractors in probabilistic Boolean networks (PBNs). They study the expected number of singleton attractors in a PBN and show that it is (2 - (1=2)/sup L-1)/sup n/, where n is the number of nodes in a PBN and L is the number of Boolean functions assigned to each node. In the case of L = 2, this number is simplified into 1.5/sup n/. It is an interesting result because it is known that the expected number of singleton attractors in a Boolean network (BN) is 1. Then, we present algorithms for identifying singleton and small attractors and perform both theoretical and computational analyses on their average case time complexities. For example, the average case time complexities for identifying singleton attractors of a PBN with L = 2 and L = 3 are O(1.601/sup n/) and O(1.763/sup n/), respectively. The results of computational experiments suggest that these algorithms are much more efficient than the naive algorithm that examines all possible 2/sup n/ states.     

Optimal control policy for probabilistic Boolean networks with hard constraints

It is well known that the control/intervention of some genes in a genetic regulatory network is useful for avoiding undesirable states associated with some diseases like cancer. For this purpose, both optimal finitehorizon control and infinite-horizon control policies have been proposed. Boolean networks (BNs) and its extension probabilistic Boolean networks (PBNs) as useful and effective tools for modelling gene regulatory systems have received much attention in the biophysics community. The control problem for these models has been studied widely. The optimal control problem in a PBN can be formulated as a probabilistic dynamic programming problem. In the previous studies, the optimal control problems did not take into account the hard constraints, i.e. to include an upper bound for the number of controls that can be applied to the captured PBN. This is important as more treatments may bring more side effects and the patients may not bear too many treatments. A formulation for the optimal finite-horizon control problem with hard constraints introduced by the authors. This model is state independent and the objective function is only dependent on the distance between the desirable states and the terminal states. An approximation method is also given to reduce the computational cost in solving the problem. Experimental results are given to demonstrate the efficiency of our proposed formulations and methods.     

Analysis on D2D Heterogeneous Networks with State-Dependent PriorityTraffic

In this work, we consider the performance analysis of state dependent priority traffic and scheduling in device to device (D2D) heterogeneous networks. There are two priority transmission types of data in wireless communication, such as video or telephone, which always meet the requirements of high priority (HP) data transmission first. If there is a large amount of low priority (LP) data, there will be a large amount of LP data that cannot be sent. This situation will cause excessive delay of LP data and packet dropping probability. In order to solve this problem, the data transmission process of high priority queue and low priority queue is studied. Considering the priority jump strategy to the priority queuing model, the queuing process with two priority data is modeled as a two-dimensional Markov chain. A state dependent priority jump queuing strategy is proposed, which can improve the discarding performance of low priority data. The quasi birth and death process method (QBD) and fixed point iteration method are used to solve the causality, and the steady-state probability distribution is further obtained.Then, performance parameters such as average queue length, average throughput, average delay and packet dropping probability for both high and low priority data can be expressed. The simulation results verify the correctness of the theoretical derivation. Meanwhile, the proposed priority jump queuing strategy can significantly improve the drop performance of low-priority data.     

Inference of Boolean networks under constraint on bidirectional gene relationships

The coefficient of determination (CoD) has been used to infer Boolean networks (BNs) from steady-state data, in particular, to estimate the constituent BNs for a probabilistic BN. The advantage of the CoD method over design methods that emphasise graph topology or attractor structure is that the CoD produces a network based on strong predictive relationships between target genes and their predictor (parent) genes. The disadvantage is that spurious attractor cycles appear in the inferred network, so that there is poor inference relative to the attractor structure, that is, relative to the steady-state behaviour of the network. Given steady-state data, there should not be a significant amount of steady-state probability mass in the inferred network lying outside the mass of the data distribution; however, the existence of spurious attractor cycles creates a significant amount of steady-state probability mass not accounted for by the data. Using steady-state data hampers design because the lack of temporal data causes CoD design to suffer from a lack of directionality with regard to prediction. This results in spurious bidirectional relationships among genes in which two genes are among the predictors for each other, when actually only one of them should be a predictor of the other, thereby creating a spurious attractor cycle. This paper characterises the manner in which bidirectional relationships affect the attractor structure of a BN. Given this characterisation, the authors propose a constrained CoD inference algorithm that outperforms unconstrained CoD inference in avoiding the creation of spurious non-singleton attractor. Algorithm performances are compared using a melanoma-based network.     

Convergence Properties of Genetic Algorithmsin a Wide Variety of Noisy Environments

Random noise perturbs objective functions in practical optimization problems, and genetic algorithms (GAs) have been proposed as an effective optimization tool for dealing with noisy objective functions. In this paper, we investigate GAs in a variety of noisy environments where fitness perturbation can occur in any form-for example, fitness evaluations can be concurrently disturbed by additive and multiplicative noise. We reveal the convergence properties of GAs by constructing and analyzing a Markov chain that explicitly models the evolution of the algorithms in noisy environments. We compute the one-step transition probabilities of the Markov chain and show that the chain has only one positive recurrent communication class, which is also aperiodic. Based on this property, we establish a condition that is both necessary and sufficient for GAs to eventually (i.e., as the number of iterations goes to infinity) find a globally optimal solution with probability 1. We also identify a condition that is both necessary and sufficient for GAs to eventually with probability 1 fail to find any globally optimal solution. Furthermore, in all the noisy environments, our analysis shows that the chain has a stationary distribution that is also its steady-state distribution. Based on this property and the transition probabilities of the chain, we examine the number of iterations sufficient to ensure with at least a specified probability that GAs select a globally optimal solution upon termination.     

Element substitution algorithm for general two-terminal network reliability analyses

The computation of the reliability of two-terminal networks is a classical reliability problem. For these types of problems, one is interested, from a general perspective, in obtaining the probability that two specific nodes can communicate. This paper presents a holistic algorithm for the analysis of general networks that follow a two-terminal rationale. The algorithm is based on a set replacement approach and an element inheritance strategy that effectively obtains the minimal cut sets associated with a given network. The vast majority of methods available for obtaining two-terminal reliability are generally based on assumptions about the performance of the network. Some methods assume network components can be in one of two states: (i) either completely failed; or (ii) perfectly functioning, others usually assume that nodes are perfectly reliable and thus, these methods have to be complemented or transformed to account for node failure, and the remaining methods assume minimal cut sets can be readily computed in order to analyze more complex network and component behavior. The algorithm presented in this paper significantly differs from previous approaches available in the literature in the sense that it is based on a predecessor matrix and an element substitution technique that allows for the exact computation of minimal cut sets and the immediate inclusion of node failure without any changes to the pseudo-code. Several case networks are used to validate and illustrate the algorithms.     

RMS中工件路径网络生成方法

利用图论建立RMS中工件路径网络生成模型。给出设备物理布局生成的3种算法：设备物理规划布局算法、基于二次布置问题(QAP)模型的VMC设备物理布局算法以及已有设备物理布局算法。给出AGV路径网络生成算法、AGV路径网络生成改进算法、可替代路径网络生成算法,包括节点间最短路径寻找子算法、路径网络预处理子算法。算法的输入为表示重构对象节点间距离信息的距离矩阵文件和表示某生产周期多工艺路线的流量文件,输出为优化的路径网络。用Visual C 实现了以上算法,实例测试验证了算法的正确性。     

Analytical Solution of the serial Bernoulli production line steady-state performance and its application in the shipbuilding process

The modern shipbuilding industry is faced with numerous challenges urging abiding improvement of the shipbuilding process and its management. Such a demanding problem is usually approached using complex production management models involving large data basis handling. The same problem can be solved using simpler, intuitive and mathematically transparent models developed within production system engineering. For these purposes, the analytical solution of the serial Bernoulli production line steady-state performance involving an arbitrary number of machines and buffers of arbitrary occupancy is developed based on Markov chain approach and eigenvalue problem including formulation of the generalised transition matrix as a key novelty. Performance measures in case of general serial Bernoulli production line are developed and the theory is validated using serial Bernoulli lines composed of two, three, four and five machines. The obtained results are compared to those determined using a semi-analytical approach. In order to further demonstrate the applicability of the developed theory, performance measure analysis is performed in cases of longer lines composed of 6, 7, 8, 9 and 10 machines with non-equal buffer capacities. Application of the developed procedure in the analysis of the shipbuilding process is illustrated in a case of the plate prefabrication line usually placed in each shipyard.     

基于左矩阵分式模型的短记录数据模态参数识别

在测量数据有限情况下,由于难以获得频响函数(FRF)的准确估计,使用FRF 作为原始数据的传统模态参数识别方法将不再适用。针对该问题,提出一种基于频响函数左矩阵分式模型的模态参数识别方法。该方法直接使用输入输出数据FFT 谱(IO 谱)作为原始数据,避免了频响函数估计。通过最小二乘估计在Z 域内求解模态参数,改善了矩阵的求解性态。针对左矩阵分式模型的特点,给出了一种通过主分量分析(PCA)建立稳定图的方法。最后采用GARTEUR 飞机模型建立仿真算例对所提出的方法进行了验证。     

Knowledge-aided covariance matrix estimation: a MAXDET approach

The authors consider the problem of knowledge-aided covariance matrix estimation and its application to adaptive radar detection. The authors assume that an a priori (knowledge-based) estimate of the disturbance covariance M, derived from a physical scattering model of the terrain and/or of the environment, is available. Hence, starting from a set of secondary data, the authors evaluate the maximum likelihood (ML) estimate of M assuming that it lies in a suitable neighbourhood of the a priori estimate and formulate this ML estimation in terms of a convex optimisation problem which falls within the class of MAXDET problems. Both the cases of unstructured and structured disturbance covariance are considered. At the analysis stage, the authors assess the performance of the new knowledge-aided covariance estimators both in terms of estimation error and detection probability achievable by a class of adaptive detectors. The results highlight that, if the a priori knowledge is reliable, satisfactory levels of performance can be achieved with considerably less training data than those exploited by conventional algorithms.     

基于蚁群算法的资源均衡优化决策及其MATLAB实现

资源均衡问题已被证明属于组合优化中的NP-hard问题,随着网络计划的复杂化,传统的数学规划法和启发式算法已很难解决该问题。本文以各种资源标准差的加权之和作为衡量资源均衡的评价指标,建立了资源均衡优化决策的数学模型,其次,自行设计蚁群算法步骤,利用Matlab编程进行实现,将蚂蚁随机分布在可行域中,蚂蚁根据转移概率进行全局搜索或局部搜索,经迭代求解资源平衡的全局最优和对应的各工序的开始工作时间,最后使用单资源均衡和多资源均衡两个算例对算法进行了测试,验证了该算法的有效性。     

Modeling of uncertainties in long fiber reinforced thermoplastics

The present study is concerned with a numerical scheme for the prediction of the uncertainty of the effective elastic properties of long fiber reinforced composites with thermoplastic matrix (LFT) produced by standard injection or press molding technologies based on the uncertainty of the microstructural geometry and topology. The scheme is based on a simple analysis of the single-fiber problem using the rules of mixture. The transition to the multi-fiber problem with different fiber orientations is made by the formulation of an ensemble average with defined probability distributions for the fiber angles. In the result, the standard deviations of the local fiber angles together with the local fiber content are treated as stochastic variables. The corresponding probability distributions for the effective elastic constants are determined in a numerically efficient manner by a discretization of the space of the random variables and the analysis of predefined cases within this space.     

Optimal design of water distribution networks by a discrete state transition algorithm

In this study it is demonstrated that, with respect to model formulation, the number of linear and nonlinear equations involved in water distribution networks can be reduced to the number of closed simple loops. Regarding the optimization technique, a discrete state transition algorithm (STA) is introduced to solve several cases of water distribution networks. Firstly, the focus is on a parametric study of the ‘restoration probability and risk probability’ in the dynamic STA. To deal effectively with head pressure constraints, the influence is then investigated of the penalty coefficient and search enforcement on the performance of the algorithm. Based on the experience gained from training the Two-Loop network problem, a discrete STA has successfully achieved the best known solutions for the Hanoi, triple Hanoi and New York network problems.     

Stable Boundary and Internal Data Reconstruction in Two-Dimensional Anisotropic Heat Conduction Cauchy Problems Using Relaxation Procedures for an Iterative MFS Algorithm

We investigate two algorithms involving the relaxation of either the given boundary temperatures (Dirichlet data) or the prescribed normal heat fluxes (Neumann data) on the over-specified boundary in the case of the iterative algorithm of Kozlov91 applied to Cauchy problems for two-dimensional steady-state anisotropic heat conduction (the Laplace-Beltrami equation). The two mixed, well-posed and direct problems corresponding to every iteration of the numerical procedure are solved using the method of fundamental solutions (MFS), in conjunction with the Tikhonov regularization method. For each direct problem considered, the optimal value of the regularization parameter is chosen according to the generalized cross-validation (GCV) criterion. The iterative MFS algorithms with relaxation are tested for over-, equally and under-determined Cauchy problems associated with the steady-state anisotropic heat conduction in various two-dimensional geometries to confirm the numerical convergence, stability, accuracy and computational efficiency of the method.     

A Statistical Procedure for Testing Nuclear Powered Cardiac Pacemakers

This article presents the results of a study of the functional case of the problem of parameter estimation when there is error in all the variables. There is consequently no distinction between independent and dependent variables. Posterior probability density functions are developed for the parameters with both linear and nonlinear, and possibly multiple, relations among the true values of the variables. There is no distinction between models that are linear or nonlinear in the parameters. The results are equivalent to generalizations of the work of some previous authors, but lead to new and efficient algorithms for finding point estimates and their precisions. For most of the results the error covariance matrix is assumed known, though a case is treated where it is known except for a scalar multiplier. The results are also shown to be valid if the covariance matrix is singular. Geometric interpretations are described.     

Optimal distributed joint frequency, rate and power allocation in cognitive OFDMA systems

The problem of wireless resource management in broadband cognitive OFDMA networks is addressed. The objective is to maximise the multiple cognitive users' weighted rate sum by jointly adjusting their rate, frequency and power resource, under the constraints of multiple primary users' interference temperatures. First, based on two interpretations of the interference temperatures, the problem studied is formulated as two nonlinear and non-convex optimisation problems. Secondly, these two problems are analysed, and a centralised greedy algorithm is proposed to solve one problem, as well as a centralised algorithm based on Lagrangian duality theory for the other. The two centralised algorithms are shown to be optimal and both have polynomial time complexities. Finally, it is shown that the two centralized algorithms can be distributively implemented by introducing the idea of virtual clock. And the distributed algorithms can be interpreted as an interesting distributed negotiated secondary market approach. It is believed that the work will provide a good reference for the emerging cognitive network protocol design.     

Comparison of evolutionary computation algorithms for solving bi-objective task scheduling problem on heterogeneous distributed computing systems

The task scheduling problem in heterogeneous distributed computing systems is a multiobjective optimization problem (MOP). In heterogeneous distributed computing systems (HDCS), there is a possibility of processor and network failures and this affects the applications running on the HDCS. To reduce the impact of failures on an application running on HDCS, scheduling algorithms must be devised which minimize not only the schedule length (makespan) but also the failure probability of the application (reliability). These objectives are conflicting and it is not possible to minimize both objectives at the same time. Thus, it is needed to develop scheduling algorithms which account both for schedule length and the failure probability. Multiobjective Evolutionary Computation algorithms (MOEAs) are well-suited for Multiobjective task scheduling on heterogeneous environment. The two Multi-Objective Evolutionary Algorithms such as Multiobjective Genetic Algorithm (MOGA) and Multiobjective Evolutionary Programming (MOEP) with non-dominated sorting are developed and compared for the various random task graphs and also for a real-time numerical application graph. The metrics for evaluating the convergence and diversity of the obtained non-dominated solutions by the two algorithms are reported. The simulation results confirm that the proposed algorithms can be used for solving the task scheduling at reduced computational times compared to the weighted-sum based biobjective algorithm in the literature.