An Algorithm for the Maximum Likelihood Problem on Evolutionary Trees

We investigate the problem of reconstructing evolutionary trees with maximum likelihood (MLET). In the MLET problem, a set of genetic sequences is given and a feasible solution is sought, consisting of an evolutionary tree (where general nodes correspond to sequences and input sequences occur as leaves) along with assignments for the interior nodes. Due to the difficulty of solving the MLET directly, we consider two restricted versions of the problem: the ancestral maximum likelihood (AML) and the maximum parsimony (MP) problems. If we let d_e denote the number of different characters occurring in two nodes linked by edge e, then the objective function of the AML problem is min ∑_{eσ E(T)} H(d_e/k), where H is the entropy function and k is the length of each sequence. In the MP we consider the objective function min σ_{e∊ E(T)} d_e/k. Both the AML and the MP are NP-hard. We propose a new approach for computing solutions for these problems, based on genetic algorithms.     

Improved Dynamic Programming in Connection with an FPTAS for the Knapsack Problem

A vector merging problem is introduced where two vectors of length n are merged such that the k-th entry of the new vector is the minimum over of the -th entry of the first vector plus the sum of the first k – + 1 entries of the second vector. For this problem a new algorithm with O(n log n) running time is presented thus improving upon the straightforward O(n ²) time bound.The vector merging problem can appear in different settings of dynamic programming. In particular, it is applied for a recent fully polynomial time approximation scheme (FPTAS) for the classical 0–1 knapsack problem by the same authors.     

A Heuristic for the Maximum Independent Set Problem Based on Optimization of a Quadratic Over a Sphere

For a given graph the maximum independent set problem is to find a maximum subset of vertices no two of which are adjacent. We propose a heuristic for the maximum independent set problem which utilizes classical results for the problem of optimization of a quadratic function over a sphere. The efficiency of the approach is confirmed by results of numerical experiments on DIMACS benchmarks.     

商业银行运营效率的综合评价与敏感度分析

对商业银行的盈利能力与服务水平进行综合评价,提出了新的评价模型,并结合安徽某商业银行的实例对评价方法进行了演示,所做的敏感度分析有助于决策者改进综合效率.     

蚂蚁算法在组合优化中的应用

蚂蚁算法是近年来新出现的一种随机型搜索寻优算法 ,自从在 TSP等著名问题中得到富有成效的应用之后 ,已引起越来越多的关注和重视 .本文进一步将这种新型的生物优化思想扩展到其他一些组合优化难题 ,包括目前尚缺乏有效求解手段的多目标组合优化问题 ,从实验上探索了蚂蚁算法的优化能力 ,获得了满意的效果     

On the Sensitivity Analysis of the IIM: A Rejoinder

In this note I reply to the comments by Haimes et al. on my paper on the sensitivity analysis of the inoperability input‐output model. I make the case for a moment‐independent sensitivity analysis.     

Sensitivity and Uncertainty Studies of the CRAC2 Computer Code

We have studied the sensitivity of health impacts from nuclear reactor accidents, as predicted by the CRAC2 computer code, to the following sources of uncertainty: (1) the model for plume rise, (2) the model for wet deposition, (3) the meteorological bin-sampling procedure for selecting weather sequences with rain, (4) the dose conversion factors for inhalation as affected by uncertainties in the particle size of the carrier aerosol and the clearance rates of radionuclides from the respiratory tract, (5) the weathering half-time for external ground-surface exposure, and (6) the transfer coefficients for terrestrial foodchain pathways. Predicted health impacts usually showed little sensitivity to use of an alternative plume-rise model or a modified rain-bin structure in bin-sampling. Health impacts often were quite sensitive to use of an alternative wet-deposition model in single-trial runs with rain during plume passage, but were less sensitive to the model in bin-sampling runs. Uncertainties in the inhalation dose conversion factors had important effects on early injuries in single-trial runs. Latent cancer fatalities were moderately sensitive to uncertainties in the weathering half-time for ground-surface exposure, but showed little sensitivity to the transfer coefficients for terrestrial foodchain pathways. Sensitivities of CRAC2 predictions to uncertainties in the models and parameters also depended on the magnitude of the source term, and some of the effects on early health effects were comparable to those that were due only to selection of different sets of weather sequences in bin-sampling.     

考虑碳配额差值的选址-路径-库存集成问题优化模型与算法

考虑碳配额差值对产供销一体化系统中的选址-路径-库存集成问题的影响,构建了嵌入碳配额差值和选址-路径-库存运作成本的非线性整数规划模型,并对模型中的碳配额差值和选址-路径-库存运作成本两个目标同时进行优化;通过对目标函数进行等价处理,设计了基于BFA-PSO的组合优化求解算法;数值仿真结果显示企业可以通过运作层的决策优化,以较小的经济成本获得较大的碳减排绩效。     

Sensitivity Analysis to Evaluate the Impact of Uncertain Factors in a Scenario Tree Model for Classical Swine Fever Introduction

Introduction of classical swine fever virus (CSFV) is a continuing threat to the pig production sector in the European Union. A scenario tree model was developed to obtain more insight into the main risk factors determining the probability of CSFV introduction (P(CSFV)). As this model contains many uncertain input parameters, sensitivity analysis was used to indicate which of these parameters influence model results most. Group screening combined with the statistical techniques of design of experiments and meta-modeling was applied to detect the most important uncertain input parameters among a total of 257 parameters. The response variable chosen was the annual P(CSFV) into the Netherlands. Only 128 scenario calculations were needed to specify the final meta-model. A consecutive one-at-a-time sensitivity analysis was performed with the main effects of this meta-model to explore their impact on the ranking of risk factors contributing most to the annual P(CSFV). The results indicated that model outcome is most sensitive to the uncertain input parameters concerning the expected number of classical swine fever epidemics in Germany, Belgium, and the United Kingdom and the probability that CSFV survives in an empty livestock truck traveling over a distance of 0-900 km.     

A Sensitivity Analysis of the Social Vulnerability Index

The Social Vulnerability Index (SoVI), created by Cutter et al. (2003) , examined the spatial patterns of social vulnerability to natural hazards at the county level in the United States in order to describe and understand the social burdens of risk. The purpose of this article is to examine the sensitivity of quantitative features underlying the SoVI approach to changes in its construction, the scale at which it is applied, the set of variables used, and to various geographic contexts. First, the SoVI was calculated for multiple aggregation levels in the State of South Carolina and with a subset of the original variables to determine the impact of scalar and variable changes on index construction. Second, to test the sensitivity of the algorithm to changes in construction, and to determine if that sensitivity was constant in various geographic contexts, census data were collected at a submetropolitan level for three study sites: Charleston, SC; Los Angeles, CA; and New Orleans, LA. Fifty-four unique variations of the SoVI were calculated for each study area and evaluated using factorial analysis. These results were then compared across study areas to evaluate the impact of changing geographic context. While decreases in the scale of aggregation were found to result in decreases in the variance explained by principal components analysis (PCA), and in increases in the variance of the resulting index values, the subjective interpretations yielded from the SoVI remained fairly stable. The algorithm's sensitivity to certain changes in index construction differed somewhat among the study areas. Understanding the impacts of changes in index construction and scale are crucial in increasing user confidence in metrics designed to represent the extremely complex phenomenon of social vulnerability.     

Fighting the Curse of Sparsity: Probabilistic Sensitivity Measures From Cumulative Distribution Functions

Quantitative models support investigators in several risk analysis applications. The calculation of sensitivity measures is an integral part of this analysis. However, it becomes a computationally challenging task, especially when the number of model inputs is large and the model output is spread over orders of magnitude. We introduce and test a new method for the estimation of global sensitivity measures. The new method relies on the intuition of exploiting the empirical cumulative distribution function of the simulator output. This choice allows the estimators of global sensitivity measures to be based on numbers between 0 and 1, thus fighting the curse of sparsity. For density-based sensitivity measures, we devise an approach based on moving averages that bypasses kernel-density estimation. We compare the new method to approaches for calculating popular risk analysis global sensitivity measures as well as to approaches for computing dependence measures gathering increasing interest in the machine learning and statistics literature (the Hilbert–Schmidt independence criterion and distance covariance). The comparison involves also the number of operations needed to obtain the estimates, an aspect often neglected in global sensitivity studies. We let the estimators undergo several tests, first with the wing-weight test case, then with a computationally challenging code with up to $\text{◂,▸}k=30,000$ inputs, and finally with the traditional Level E benchmark code.     

An Approach for Optimal Allocation of Safety Resources: Using the Knapsack Problem to Take Aggregated Cost‐Efficient Preventive Measures

On the basis of the combination of the well‐known knapsack problem and a widely used risk management technique in organizations (that is, the risk matrix), an approach was developed to carry out a cost‐benefits analysis to efficiently take prevention investment decisions. Using the knapsack problem as a model and combining it with a well‐known technique to solve this problem, bundles of prevention measures are prioritized based on their costs and benefits within a predefined prevention budget. Those bundles showing the highest efficiencies, and within a given budget, are identified from a wide variety of possible alternatives. Hence, the approach allows for an optimal allocation of safety resources, does not require any highly specialized information, and can therefore easily be applied by any organization using the risk matrix as a risk ranking tool.     

Global Sensitivity Analysis Applied to a Contamination Assessment Model of Listeria monocytogenes in Cold Smoked Salmon at Consumption

In this study, a variance‐based global sensitivity analysis method was first applied to a contamination assessment model of Listeria monocytogenes in cold smoked vacuum packed salmon at consumption. The impact of the choice of the modeling approach (populational or cellular) of the primary and secondary models as well as the effect of their associated input factors on the final contamination level was investigated. Results provided a subset of important factors, including the food water activity, its storage temperature, and duration in the domestic refrigerator. A refined sensitivity analysis was then performed to rank the important factors, tested over narrower ranges of variation corresponding to their current distributions, using three techniques: ANOVA, Spearman correlation coefficient, and partial least squares regression. Finally, the refined sensitivity analysis was used to rank the important factors.     

A Protocol for the Global Sensitivity Analysis of Impact Assessment Models in Life Cycle Assessment

The life cycle assessment (LCA) framework has established itself as the leading tool for the assessment of the environmental impact of products. Several works have established the need of integrating the LCA and risk analysis methodologies, due to the several common aspects. One of the ways to reach such integration is through guaranteeing that uncertainties in LCA modeling are carefully treated. It has been claimed that more attention should be paid to quantifying the uncertainties present in the various phases of LCA. Though the topic has been attracting increasing attention of practitioners and experts in LCA, there is still a lack of understanding and a limited use of the available statistical tools. In this work, we introduce a protocol to conduct global sensitivity analysis in LCA. The article focuses on the life cycle impact assessment (LCIA), and particularly on the relevance of global techniques for the development of trustable impact assessment models. We use a novel characterization model developed for the quantification of the impacts of noise on humans as a test case. We show that global SA is fundamental to guarantee that the modeler has a complete understanding of: (i) the structure of the model and (ii) the importance of uncertain model inputs and the interaction among them.     

Monte Carlo Sensitivity Analysis of Unknown Parameters in Hazardous Materials Transportation Risk Assessment

The US Department of Transportation was interested in the risks associated with transporting Hydrazine in tanks with and without relief devices. Hydrazine is both highly toxic and flammable, as well as corrosive. Consequently, there was a conflict as to whether a relief device should be used or not. Data were not available on the impact of relief devices on release probabilities or the impact of Hydrazine on the likelihood of fires and explosions. In this paper, a Monte Carlo sensitivity analysis of the unknown parameters was used to assess the risks associated with highway transport of Hydrazine. To help determine whether or not relief devices should be used, fault trees and event trees were used to model the sequences of events that could lead to adverse consequences during transport of Hydrazine. The event probabilities in the event trees were derived as functions of the parameters whose effects were not known. The impacts of these parameters on the risk of toxic exposures, fires, and explosions were analyzed through a Monte Carlo sensitivity analysis and analyzed statistically through an analysis of variance. The analysis allowed the determination of which of the unknown parameters had a significant impact on the risks. It also provided the necessary support to a critical transportation decision even though the values of several key parameters were not known.     

Sensitivity of Physiologically Based Pharmacokinetic Models to Variation in Model Parameters: Methylene Chloride

The parameters in a physiologically based pharmacokinetic (PBPK) model of methylene chloride were varied systematically, and the resulting variation in a number of model outputs was determined as a function of time for mice and humans at several exposure concentrations. The importance of the various parameters in the model was highly dependent on the conditions (concentration, species) for which the simulation was performed and the model output (dose surrogate) being considered. Model structure also had a significant impact on the results. For sensitivity analysis, particular attention must be paid to conservation equations to ensure that the variational calculations do not alter mass balance, introducing extraneous effects into the model. All of the normalized sensitivity coefficients calculated in this study ranged between −1.12 and 1, and most were much less than 1 in absolute value, indicating that individual input errors are not greatly amplified in the outputs. In addition to ranking parameters in terms of their impact on model predictions, time-dependent sensitivity analysis can also be used as an aid in the design of experiments to estimate parameters by predicting the experimental conditions and sampling points which will maximize parameter identifiability.     

Uncertainty in Climate Change Modeling: Can Global Sensitivity Analysis Be of Help?

Integrated assessment models offer a crucial support to decisionmakers in climate policy making. For a full understanding and corroboration of model results, analysts ought to identify the exogenous variables that influence the model results the most (key drivers), appraise the relevance of interactions, and the direction of change associated with the simultaneous variation of uncertain variables. We show that such information can be directly extracted from the data set produced by Monte Carlo simulations. Our discussion is guided by the application to the well‐known DICE model of William Nordhaus. The proposed methodology allows analysts to draw robust insights into the dependence of future atmospheric temperature, global emissions, and carbon costs and taxes on the model's exogenous variables.     

On the Local Sensitivity Analysis of the Inoperability Input‐Output Model

Natural and man‐made disasters are currently a source of major concern for contemporary societies. In order to understand their economic impacts, the inoperability input‐output model has recently gained recognition among scholars. In a recent paper, Percoco (2006) has proposed an extension of the model to map the technologically most important sectors through so‐called fields of influence. In the present note we aim to show that this importance measure also has a clear connection with local sensitivity analysis theory.     

Comparison of Sensitivity Analysis Methods Based on Applications to a Food Safety Risk Assessment Model

Sensitivity analysis (SA) methods are a valuable tool for identifying critical control points (CCPs), which is one of the important steps in the hazard analysis and CCP approach that is used to ensure safe food. There are many SA methods used across various disciplines. Furthermore, food safety process risk models pose challenges because they often are highly nonlinear, contain thresholds, and have discrete inputs. Therefore, it is useful to compare and evaluate SA methods based upon applications to an example food safety risk model. Ten SA methods were applied to a draft Vibrio parahaemolyticus (Vp) risk assessment model developed by the Food and Drug Administration. The model was modified so that all inputs were independent. Rankings of key inputs from different methods were compared. Inputs such as water temperature, number of oysters per meal, and the distributional assumption for the unrefrigerated time were the most important inputs, whereas time on water, fraction of pathogenic Vp, and the distributional assumption for the weight of oysters were the least important inputs. Most of the methods gave a similar ranking of key inputs even though the methods differed in terms of being graphical, mathematical, or statistical, accounting for individual effects or joint effect of inputs, and being model dependent or model independent. A key recommendation is that methods be further compared by application on different and more complex food safety models. Model independent methods, such as ANOVA, mutual information index, and scatter plots, are expected to be more robust than others evaluated.     

交通路网中最优路径算法的道路权重选择

在交通路网中,寻找任意两点间最优路径是出行导航的基本功能.除了最优路径算法自身性能外,道路权重的选择也直接决定了寻径结果的优劣.现有最优路径算法通常以通行能力为道路权重,其可能导致不合理的寻径结果,同时也不具有全局负载均衡的能力.因此本文以Dijkstra算法为例,引入可达性概念作为道路权重,从而弥补以通行能力为道路权重的缺陷.