Solving the knapsack problem with imprecise weight coefficients using genetic algorithms

This paper investigates solving the knapsack problem with imprecise weight coefficients using genetic algorithms. This work is based on the assumption that each weight coefficient is imprecise due to decimal truncation or coefficient rough estimation by the decision-maker. To deal with this kind of imprecise data, fuzzy sets provide a powerful tool to model and solve this problem. We investigate the possibility of using genetic algorithms in solving the fuzzy knapsack problem without defining membership functions for each imprecise weight coefficient. The proposed approach simulates a fuzzy number by distributing it into some partition points. We use genetic algorithms to evolve the values in each partition point so that the final values represent the membership grade of a fuzzy number. The empirical results show that the proposed approach can obtain very good solutions within the given bound of each imprecise weight coefficient than the fuzzy knapsack approach. The fuzzy genetic algorithm concept approach is different, but gives better results than the traditional fuzzy approach.     

综合评价中权数的函数性质及其生成研究

通过对权数进行系统的研究,本文认为从"权数的性质"这个角度出发,权数具有"重要性"、"模糊性"、"主观性"和"时序性".将区域因素考虑进去,提出了权数具有"空间性","时空性"的观点.进一步,随着时间或区域的连续变化时,若权数也连续取值,则此时权数可以看成函数的形式,并给出两种具体的方法求权函数.特别针对权函数取值范围在0和1之间,将其进行函数变换后,通过新函数(权函数的Logit函数)的函数生成方法,进而得出权函数的生成方法.最后通过例子说明该方法比较符合权数的实际取值.     

Goodness-of-fit tests based on a robust measure of skewness

In this paper we propose several goodness-of-fit tests based on robust measures of skewness and tail weight. They can be seen as generalisations of the Jarque–Bera test (Bera and Jarque in Econ Lett 7:313–318, 1981) based on the classical skewness and kurtosis, and as an alternative to the approach of Moors et al. (Stat Neerl 50:417–430, 1996) using quantiles. The power values and the robustness properties of the different tests are investigated by means of simulations and applications on real data. We conclude that MC-LR, one of our proposed tests, shows the best overall power and that it is moderately influenced by outlying values.     

Mixing weighted values of non-atomic games

Weighted values of non-atomic games were introduced by Hart and Monderer (1997). They study these values by using two approaches: the potential approach and the asymptotic approach. In this study we develop the random order approach (the mixing value, Aumann and Shapley, 1974) to weighted values and prove that these values coincide with the asymptotic weighted values of Hart and Monderer in pNA. Received April 1995/Revised version May 1996/ Final version October 1997     

Profit optimization for cattle growing in a randomly fluctuating environment

A class of stochastic differential equation models was applied to describe the evolution of the weight of Mertolengo cattle. We have determined the optimal mean profit obtained by selling an animal at the cattle market, using two approaches. One consists in determining the optimal selling age (independently of the weight) and the other consists in selling the animal when a fixed optimal weight is achieved for the first time (independently of the age). The profit probability distribution can be computed for such optimal age/weight. For typical market values, we observed that the second approach achieves a higher optimal mean profit compared with the first one, and, in most cases, even provides a lower standard deviation.     

A grey relational projection method for multi-attribute decision making based on intuitionistic trapezoidal fuzzy number

With respect to multiple attribute decision making (MADM) problems in which the attribute value takes the form of intuitionistic trapezoidal fuzzy number, and the attribute weight is unknown, a new decision making analysis methods are developed. Firstly, some operational laws and expected values of intuitionistic trapezoidal fuzzy numbers, and distance between two intuitionistic trapezoidal fuzzy numbers, are introduced. Then information entropy method is used to determine the attribute weight, and the grey relational projection method combined grey relational analysis method and projection method is proposed, and to rank the alternatives are done by the relative closeness to PIS which combines grey relational projection values from the positive ideal solution and negative ideal solution to each alternative. Finally, an illustrative example is given to verify the developed approach and to demonstrate its practicality and effectiveness.     

考虑后悔规避与匹配意愿的直觉模糊双边匹配方法

针对直觉模糊偏好信息的双边匹配问题,提出一种考虑匹配主体后悔规避心理行为和匹配意愿的双边匹配方法。首先,将双边主体的直觉模糊偏好信息转化为效用值;然后,依据后悔理论的思想,通过一方主体将另一方主体进行两两比较计算每个主体的后悔值和欣喜值,进而计算每个主体的总体后悔欣喜值,构建匹配满意度计算规则,建立双边匹配多目标优化模型,通过分析现有匹配意愿系数确定方法的不足,给出一种新的匹配意愿系数确定方法,在此基础上,考虑双边主体的匹配意愿,采用线性加权法将多目标优化模型转化为单目标规划模型进行求解,获得双边匹配结果;最后,通过一个算例验证了提出方法的可行性和有效性。     

A Dynamic Mixture Model for Unsupervised Tail Estimation without Threshold Selection

Exceedances over high thresholds are often modeled by fitting a generalized Pareto distribution (GPD) on R⁺. It is difficult to select the threshold, above which the GPD assumption is enough solid and enough data is available for inference. We suggest a new dynamically weighted mixture model, where one term of the mixture is the GPD, and the other is a light-tailed density distribution. The weight function varies on R⁺ in such a way that for large values the GPD component is predominant and thus takes the role of threshold selection. The full data set is used for inference on the parameters present in the two component distributions and in the weight function. Maximum likelihood provides estimates with approximate standard deviations. Our approach has been successfully applied to simulated data and to the (previously studied) Danish fire loss data set. We compare the new dynamic mixture method to Dupuis' robust thresholding approach in peaks-over-threshold inference. We discuss robustness with respect to the choice of the light-tailed component and the form of the weight function. We present encouraging simulation results that indicate that the new approach can be useful in unsupervised tail estimation, especially in heavy tailed situations and for small percentiles.     

主客观赋权合成指标权重及其在公共卫生综合评价中的应用

目的:探讨综合评价中指标权重的确定.方法:将相似权法和属性AHM赋权法相结合来确定指标权重,并应用于公共卫生质量的综合评价.结果:实现了对太原市5所普通旅店的聚类与排序;结论:主客观赋权合成指标权重,既充分利用了样本资料的统计信息,又反映了专家的理论知识和经验,可得到较为客观、合理的指标权重,将此权重用于综合评价,其结果准确可靠.     

Using eigenstructure of the Hessian to reduce the dimension of the intensity modulated radiation therapy optimization problem

Optimization is of vital importance when performing intensity modulated radiation therapy to treat cancer tumors. The optimization problem is typically large-scale with a nonlinear objective function and bounds on the variables, and we solve it using a quasi-Newton sequential quadratic programming method. This study investigates the effect on the optimal solution, and hence treatment outcome, when solving an approximate optimization problem of lower dimension. Through a spectral decompostion, eigenvectors and eigenvalues of an approximation to the Hessian are computed. An approximate optimization problem of reduced dimension is formulated by introducing eigenvector weights as optimization parameters, where only eigenvectors corresponding to large eigenvalues are included. The approach is evaluated on a clinical prostate case. Compared to bixel weight optimization, eigenvector weight optimization with few parameters results in faster initial decline in the objective function, but with inferior final solution. Another approach, which combines eigenvector weights and bixel weights as variables, gives lower final objective values than what bixel weight optimization does. However, this advantage comes at the expense of the pre-computational time for the spectral decomposition. A preliminary version of this paper was presented at the AAPM 46th annual meeting, held July 25–29, 2004 in Pittsburgh, PA.     

基于VIKOR和关联系数的犹豫三角模糊语言多属性决策方法

针对属性评价值为犹豫三角模糊语言集的多属性决策问题,提出一种基于VIKOR方法的犹豫三角模糊语言多属性决策方法.首先定义了犹豫三角模糊语言集的相关概念.然后运用VIKOR和关联系数方法,在可接受优势和决策过程稳定的条件下对方案进行择优,在理论分析的基础上,提出了这种新方法的计算步骤.并构建了确定最优属性权重的非线性规划模型,研究了当专家权重和属性权重未知情况下的犹豫三角模糊语言多属性决策方法.最后通过实例说明了该方法的有效性和可行性.     

风险型混合多属性消错决策方法

针对同时包含可线性补偿和不可线性补偿两种属性且属性值为确实数、区间数、语言信息的风险型多属性决策问题,提出一种基于消错理论的决策方法。首先,在消错理论的基础上将属性分为关键型、重要型和冗余型三类,结合属性值的类型分别给出对应的错误函数和极限损失值;接着,对关键型属性赋予极小权重,在保留关键型属性“一票否决”功能的同时又突出重要属性的作用;最后,根据对待错误损失的不同态度,建立计算错误损失值的三种方法,通过计算期望错误损失值对备选方案进行排序。通过新市民信息服务项目的例子,说明该方法的有效性和可行性。     

Determining common weights in data envelopment analysis based on the satisfaction degree

The traditional data envelopment analysis model allows the decision-making units (DMUs) to evaluate their maximum efficiency values using their most favourable weights. This kind of evaluation with total weight flexibility may prevent the DMUs from being fully ranked and make the evaluation results unacceptable to the DMUs. To solve these problems, first, we introduce the concept of satisfaction degree of a DMU in relation to a common set of weights. Then a common-weight evaluation approach, which contains a max–min model and two algorithms, is proposed based on the satisfaction degrees of the DMUs. The max–min model accompanied by our Algorithm 1 can generate for the DMUs a set of common weights that maximizes the least satisfaction degrees among the DMUs. Furthermore, our Algorithm 2 can ensure that the generated common set of weights is unique and that the final satisfaction degrees of the DMUs constitute a Pareto-optimal solution. All of these factors make the evaluation results more satisfied and acceptable by all the DMUs. Finally, results from the proposed approach are contrasted with those of some previous methods for two published examples: efficiency evaluation of 17 forest districts in Taiwan and R&D project selection.     

Binary linear codes with few weights from Boolean functions

Boolean functions have very nice applications in coding theory and cryptography. In coding theory, Boolean functions have been used to construct linear codes in different ways. The objective of this paper is to construct binary linear codes with few weights using the defining-set approach. The defining sets of the codes presented in this paper are defined by some special Boolean functions and some additional restrictions. First, two families of binary linear codes with at most three or four weights from Boolean functions with at most three Walsh transform values are constructed and the parameters of their duals are also determined. Then several classes of binary linear codes with explicit weight enumerators are produced. Some of the binary linear codes are optimal or almost optimal according to the tables of best codes known maintained at http://www.codetables.de, and the duals of some of them are distance-optimal with respect to the sphere packing bound.

     

A Lagrangean relaxation based approach for the capacity allocation problem in flexible manufacturing systems

This study considers the operation assignment and capacity allocation problem in flexible manufacturing systems. A set of operations is selected to be processed and assigned to the machines together with their required tools. The purchase or usage of the required tools incurs a cost. The machines have scarce time and tool magazine capacities. The objective is to maximize the total weight of the assigned operations minus the total tooling costs. We use Lagrangean relaxation approach to obtain upper and lower bounds on the optimal objective function values. The computational experiments show that our approach provides near optimal bounds in reasonable solution times.     

Bayesian Inference for Extremes: Accounting for the Three Extremal Types

The Extremal Types Theorem identifies three distinct types of extremal behaviour. Two different strategies for statistical inference for extreme values have been developed to exploit this asymptotic representation. One strategy uses a model for which the three types are combined into a unified parametric family with the shape parameter of the family determining the type: positive (Fréchet), zero (Gumbel), and negative (negative Weibull). This form of approach never selects the Gumbel type as that type is reduced to a single point in a continuous parameter space. The other strategy first selects the extremal type, based on hypothesis tests, and then estimates the best fitting model within the selected type. Such approaches ignore the uncertainty of the choice of extremal type on the subsequent inference. We overcome these deficiencies by applying the Bayesian inferential framework to an extended model which explicitly allocates a non-zero probability to the Gumbel type. Application of our procedure suggests that the effect of incorporating the knowledge of the Extremal Types Theorem into the inference for extreme values is to reduce uncertainty, with the degree of reduction depending on the shape parameter of the true extremal distribution and the prior weight given to the Gumbel type.     

On consistency of stochastic dominance and mean–semideviation models

We analyze relations between two methods frequently used for modeling the choice among uncertain outcomes: stochastic dominance and mean–risk approaches. New necessary conditions for stochastic dominance are developed. These conditions compare values of a certain functional, which contains two components: the expected value of a random outcome and a risk term represented by the central semideviation of the corresponding degree. If the weight of the semideviation in the composite objective does not exceed the weight of the expected value, maximization of such a functional yields solutions which are efficient in terms of stochastic dominance. The results are illustrated graphically. Received: September 15, 1998 / Accepted: October 1, 2000?Published online December 15, 2000     

A hybridized tabu search approach for the minimum weight vertex cover problem

The minimum weight vertex cover problem is a basic combinatorial optimization problem defined as follows. Given an undirected graph and positive weights for all vertices the objective is to determine a subset of the vertices which covers all edges such that the sum of the related cost values is minimized. In this paper we apply a modified reactive tabu search approach for solving the problem. While the initial concept of reactive tabu search involves a random walk we propose to replace this random walk by a controlled simulated annealing. Numerical results are presented outperforming previous metaheuristic approaches in most cases.     

Dividends and weighted values in games with externalities

In this paper, we provide further support for the family of average values for games with externalities defined in Macho-Stadler et al. (J Econ Theory 135:339–356, 2007). This is a large family of values that includes several recent proposals. We show that they can be constructed through the sharing of appropriately defined dividends. Furthermore, we show the flexibility of this approach by using it to generate non-symmetric values.     

Evidential reasoning based preference programming for multiple attribute decision analysis under uncertainty

Multiple attribute decision analysis (MADA) problems having both quantitative and qualitative attributes under uncertainty can be modelled and analysed using the evidential reasoning (ER) approach. Several types of uncertainty such as ignorance and fuzziness can be consistently modelled in the ER framework. In this paper, both interval weight assignments and interval belief degrees are considered, which could be incurred in many decision situations such as group decision making. Based on the existing ER algorithm, several pairs of preference programming models are constructed to support global sensitivity analysis based on the interval values and to generate the upper and lower bounds of the combined belief degrees for distributed assessment and also the expected values for ranking of alternatives. A post-optimisation procedure is developed to identify non-dominated solutions, examine the robustness of the partial ranking orders generated, and provide guidance for the elicitation of additional information for generating more desirable assessment results. A car evaluation problem is examined to show the implementation process of the proposed approach.