Sampling from spatial databases

This paper deals with techniques for obtaining random point samples from spatial databases. We seek random points from a continuous domain (usually ²) which satisfy a spatial predicate that is represented in the database as a collection of polygons. Several applications of spatial sampling (e.g. environmental monitoring, agronomy, forestry, etc) are described. Sampling problems are characterized in terms of two key parameters: coverage (selectivity), and expected stabbing number (overlap). We discuss two fundamental approaches to sampling with spatial predicates, depending on whether we sample first or evaluate the predicate first. The approaches are described in the context of both quadtrees and R-trees, detailing the sample first, acceptance/rejection tree, and partial area tree algorithms. A sequential algorithm, the one-pass spatial reservoir algorithm is also described. The relative performance of the various sampling algorithms is compared and choice of preferred algorithms is suggested. We conclude with a short discussion of possible extensions.     

Finite mixture models with concomitant information: assessing diagnostic criteria for diabetes

The World Health Organization (WHO) diagnostic criteria for diabetes mellitus were determined in part by evidence that in some populations the plasma glucose level 2 h after an oral glucose load is a mixture of two distinct distributions. We present a finite mixture model that allows the two component densities to be generalized linear models and the mixture probability to be a logistic regression model. The model allows us to estimate the prevalence of diabetes and sensitivity and specificity of the diagnostic criteria as a function of covariates and to estimate them in the absence of an external standard. Sensitivity is the probability that a test indicates disease conditionally on disease being present. Specificity is the probability that a test indicates no disease conditionally on no disease being present. We obtained maximum likelihood estimates via the EM algorithm and derived the standard errors from the information matrix and by the bootstrap. In the application to data from the diabetes in Egypt project a two-component mixture model fits well and the two components are interpreted as normal and diabetes. The means and variances are similar to results found in other populations. The minimum misclassification cutpoints decrease with age, are lower in urban areas and are higher in rural areas than the 200 mg dl^-1 cutpoint recommended by the WHO. These differences are modest and our results generally support the WHO criterion. Our methods allow the direct inclusion of concomitant data whereas past analyses were based on partitioning the data.     

Sensitivity of the Optimum to Perturbations of the Profit or Weight of an Item in the Binary Knapsack Problem

In the binary single constraint Knapsack Problem, denoted KP, we are given a knapsack of fixed capacity c and a set of n items. Each item j, j = 1,...,n, has an associated size or weight w_j and a profit p_j. The goal is to determine whether or not item j, j = 1,...,n, should be included in the knapsack. The objective is to maximize the total profit without exceeding the capacity c of the knapsack. In this paper, we study the sensitivity of the optimum of the KP to perturbations of either the profit or the weight of an item. We give approximate and exact interval limits for both cases (profit and weight) and propose several polynomial time algorithms able to reach these interval limits. The performance of the proposed algorithms are evaluated on a large number of problem instances.     

基于二元关系的产业关联分析方法研究

本文运用二元关系理论和Warshall算法计算产业系统中各产业之间的连通关联关系,为认识产业结构和产业关联状况提供了简便的量化分析方法。结合安徽产业系统的实例,分析了安徽产业结构的特点及产业关联状况。     

Penalty guided genetic search for redundancy optimization in multi-state series-parallel power system

This paper presents a genetic algorithm (GA) for parallel redundancy optimization in series-parallel power systems exhibiting multi-state behavior, optimizing the reliability subject to constraints. The components are binary and chosen from a list of products available in the market, and are being characterized by their feeding capacity, reliability, cost and weight. System reliability is defined as the ability to satisfy consumer demand and is presented as a piecewise cumulative load curve. In GA, to handle infeasible solutions penalty strategies are used. Penalty technique keep a certain amount of infeasible solutions in each generation so as to enforce genetic search towards an optimal solution from sides of, both, feasible and infeasible regions. We here present a dynamic adaptive penalty function which helps the algorithm to search efficiently for optimal/near optimal solution. To evaluate system reliability, a fast procedure, based on universal generating function, is used. An example considering a multi-state series-parallel power system is solved considering both homogeneous and heterogeneous types of redundancy. Also an example considering price discounts is solved. The effectiveness of the penalty function and the proposed algorithm is studied and shown graphically.     

信息不完全确定的区域产品模糊区间聚类方法

区域产品分类与选择是区域经济发展中最重要和最基础的工作.在产品选择与分类时,需要确定指标权系数和分类阈值等参数,这在实际应用中是比较困难的.针对这种情况,提出了一种信息不完全确定的区域产品模糊区间聚类方法.该方法构建了指标权系数信息不完全确定的最优模糊区间聚类模型,利用遗传算法和改进的FCM算法联合求解所得优化模型,得到指标权系数、最优聚类中心和最优划分,进而确定各产品所属类别.最后将该方法应用于某区域的产品分类和主导产品的确定中,实例计算说明该方法的可行性和有效性.     

动态联盟中伙伴选择问题的区间规划模型及其求解

伙伴选择和风险管理是动态联盟中的重要决策问题,当考虑失败风险时,失败概率无法给出精确值,因此,考虑采用不确定性规划描述此类问题.提出动态联盟中伙伴选择问题的区间规划模型,模型中用区间数表示联盟伙伴的失败概率.为了求解该模型,引入序关系,并利用Nakahara和Ishibuchi的定理,将区间规划模型转化为等价的清晰双目标模型.设计带自适应适值函数的遗传算法,求出问题的全部非劣解.经过对多个问题的仿真,证明了算法的有效性.     

基于混合智能算法的电子市场供应链期权合同协调

在电子市场环境下,考虑了需求、市场价格和市场准入程度的随机性,基于Stack-erlberg主从对策,建立了供应链期权合同协调的随机期望值模型。在这一主从对策模型中,主方供应商的目标函数是预期利润,决策变量是期权合同预订费用和执行费用;从方分销商的目标函数是预期利润,决策变量是订货量。应用包括随机模拟、人工神经元网络和遗传算法组成的混合智能算法求解该主从对策问题。最后,结合上海宝钢集团益昌公司电子商务的运作实例,运用混合智能算法进行了仿真计算与分析。     

基于两阶段优化算法的神经网络预测模型

采用基于两阶段优化算法(multi-stage optimization approach,MSOA)的GA人工神经网络,将训练集分为两部分,在前一训练集训练后获得的网络基础上使用后一训练集进行进一步的训练获得更为优化的网络结构.针对复杂系统建模输入节点难以确定的问题,提出将其与自组织数据挖掘算法相结合,利用GMDH算法获得神经网络的初始化节点,使用训练好的神经网络模型进行预测.将由此建立的预测模型应用于粮食价格的预测,并进一步探讨了MSOA算法的收敛性问题.结果表明基于GMDH和MSOA的神经网络组合预测模型能较大提高神经网络的全局收敛能力和收敛速度,提高预测精度.