On local optima in multiobjective combinatorial optimization problems

In this article, local optimality in multiobjective combinatorial optimization is used as a baseline for the design and analysis of two iterative improvement algorithms. Both algorithms search in a neighborhood that is defined on a collection of sets of feasible solutions and their acceptance criterion is based on outperformance relations. Proofs of the soundness and completeness of these algorithms are given.     

Non-Contradictory Aggregation of Strict Order Relations

We study the problem of collective choice. The profile of individual preferences of experts is defined by relations of strict order. A non-contradictory aggregate preference relation is based on the weighted majority graph that characterizes the degree of superiority of one alternative over another. The aggregate relation also defines a strict order and satisfies requirements to group decisions, namely, the monotony, the preservation of the Pareto relation, the minimality of the distance to expert preferences.     

Adaptive Segmentation Model for Images with Intensity Inhomogeneity based on Local Neighborhood Contrast

Segmentation of images with intensity inhomogeneity is a significant task in the field of image processing, especially in medical image processing and analysis. Some local region-based models work well on handling intensity inhomogeneity, but they are always sensitive to contour initialization and high noise. In this paper, we present an adaptive segmentation model for images with intensity inhomogeneity in the form of partial differential equation. Firstly, a global intensity fitting term and a local intensity fitting term are constructed by employing the global and local image information, respectively. Secondly, a tradeoff function is defined to adjust adaptively the weight between two fitting terms, which is based on the neighborhood contrast of image pixel. Finally, a weighted regularization term related to local entropy is used to ensure the smoothness of evolution curve. Meanwhile, a distance regularization term is added for stable level set evolution. Experimental results show that the proposed model without initial contour can segment inhomogeneous images stably and effectively, which thereby avoiding the influence of contour initialization on segmentation results. Besides, the proposed model works better on noise images comparing with two relevant segmentation models.     

Manifold construction based on local distance invariance

This paper presents a distance invariant manifold that preserves the neighborhood relations among data patterns. All patterns have their corresponding cells in the manifold space. The constellation of neighborhood cells closely resembles that of patterns. The manifold is invariant under the translation, rotation and scale of the pattern coordinates. The neighborhood relations among cells are adjusted and improved in each iteration according to the reduction of the distance preservation energy.     

Analyticity of weighted central paths and error bounds for semidefinite programming

The purpose of this paper is two-fold. Firstly, we show that every Cholesky-based weighted central path for semidefinite programming is analytic under strict complementarity. This result is applied to homogeneous cone programming to show that the central paths defined by the known class of optimal self-concordant barriers are analytic in the presence of strictly complementary solutions. Secondly, we consider a sequence of primal–dual solutions that lies within a prescribed neighborhood of the central path of a pair of primal–dual semidefinite programming problems, and converges to the respective optimal faces. Under the additional assumption of strict complementarity, we derive two necessary and sufficient conditions for the sequence of primal–dual solutions to converge linearly with their duality gaps. This research was supported by a grant from the Faculty of Mathematics, University of Waterloo and by a Discovery Grant from NSERC.     

Covering rough sets based on neighborhoods: An approach without using neighborhoods

Rough set theory, a mathematical tool to deal with inexact or uncertain knowledge in information systems, has originally described the indiscernibility of elements by equivalence relations. Covering rough sets are a natural extension of classical rough sets by relaxing the partitions arising from equivalence relations to coverings. Recently, some topological concepts such as neighborhood have been applied to covering rough sets. In this paper, we further investigate the covering rough sets based on neighborhoods by approximation operations. We show that the upper approximation based on neighborhoods can be defined equivalently without using neighborhoods. To analyze the coverings themselves, we introduce unary and composition operations on coverings. A notion of homomorphism is provided to relate two covering approximation spaces. We also examine the properties of approximations preserved by the operations and homomorphisms, respectively.     

Topology Representing Networks for the Visualization of Manifolds

In practical data mining tasks, high-dimensional data has to be analyzed. In most of the cases it is very informative to map and visualize the hidden structure of a complex data set in a low-dimensional space. In this paper a new class of mapping algorithms is defined. These algorithms combine topology representing networks and different nonlinear mapping algorithms. While the former methods aim to quantify the data and disclose the real structure of the objects, the nonlinear mapping algorithms are able to visualize the quantized data in the low-dimensional vector space. In this paper, techniques based on these methods are gathered and the results of a detailed analysis performed on them are shown. The primary aim of this analysis is to examine the preservation of distances and neighborhood relations of the objects. Preservation of neighborhood relations was analyzed both in local and global environments. To evaluate the main properties of the examined methods we show the outcome of the analysis based both on synthetic and real benchmark examples.     

基于直觉犹豫模糊集的TOPSIS法

直觉犹豫模糊集集成了直觉模糊集和犹豫模糊集的优势,能更有效地刻画决策者偏好不一致的情况。距离测度一直是研究的热点问题,但尚没有文献研究直觉犹豫模糊集间的距离测度,因此本文定义了直觉犹豫模糊集间的Hamming距离、Euclidean距离和广义距离,同时考虑每个元素的权重,定义了加权距离。犹豫度是直觉犹豫模糊集的重要特性,因此在考虑犹豫度的基础上,又定义了一些距离测度。这些距离测度不仅考虑了直觉犹豫模糊数间的差异,同时考虑了犹豫度的影响,决策者可以根据对直觉犹豫模糊数和犹豫度之间偏好的不同,设置不同的偏好值得到距离测度。然后基于这些距离测度,又提出了直觉犹豫模糊环境下的TOPSIS法。最后通过实例说明了所提出的TOPSIS法的合理性与实用性。     

Matching based very large-scale neighborhoods for?parallel machine scheduling

In this paper we study very large-scale neighborhoods for the minimum total weighted completion time problem on parallel machines, which is known to be strongly $\mathcal{NP}$ -hard. We develop two different ideas leading to very large-scale neighborhoods in which the best improving neighbor can be determined by calculating a weighted matching. The first neighborhood is introduced in a general fashion using combined operations of a basic neighborhood. Several examples for basic neighborhoods are given. The second approach is based on a partitioning of the job sets on the machines and a reassignment of them. In a computational study we evaluate the possibilities and the limitations of the presented very large-scale neighborhoods.     

Two step estimators of the minimum distance type for parameters of the ARMA(1,1) model

New minimum distance estimators are constructed with the help of a preliminary estimator. The asymptotic normality of the constructed estimator is proved with use of a uniform linear expansion of a randomly weighted residual empirical process in a non-standard neighborhood of the true parameter value. Also the question on asymptotic efficiency of the constructed estimator is discussed.     

梯形直觉模糊数集成算子及在决策中的应用研究

在直觉模糊集理论基础上,用梯形模糊数表示直觉模糊数的隶属度和非隶属度,进而提出了梯形直觉模糊数;然后定义了梯形直觉模糊数的运算法则,给出了相应的证明,并基于这些法则,给出了梯形直觉模糊加权算数平均算子(TIFWAA)、梯形直觉模糊数的加权二次平均算子(TIFWQA)、梯形直觉模糊数的有序加权二次平均算子(TIFOWQA)、梯形直觉模糊数的混合加权二次平均算子(TIFHQA)并研究了这些算子的性质;建立了不确定语言变量与梯形直觉模糊数的转化关系,并证明了转化的合理性;定义了梯形直觉模糊数的得分函数和精确函数,给出了梯形直觉模糊数大小比较方法;最后提供了一种基于梯形直觉模糊信息的决策方法,并通过实例结果证明了该方法的有效性。     

Generalized hesitant fuzzy synergetic weighted distance measures and their application to multiple criteria decision-making

The purpose of this paper is to present a generalized hesitant fuzzy synergetic weighted distance (GHFSWD) measure, which is based on the generalized hesitant fuzzy weighted distance (GHFWD) measure and the generalized hesitant fuzzy ordered weighted distance (GHFOWD) measure proposed by Xu and Xia [Z. Xu, M. Xia, Distance and similarity measures for hesitant fuzzy sets, Inf. Sci. 181 (2011) 2128–2138.], and investigate its some desirable properties and special cases. The GHFSWD measure not only generalizes both the GHFWD and GHFOWD measures as well as the common hesitant fuzzy distance measures, but also reflects the importance degrees of both the given individual distances and their ordered positions. Then, based on the defined notions of positive ideal hesitant fuzzy set and negative ideal hesitant fuzzy set, we utilize the proposed GHFSWD measure to develop a method for multiple criteria decision making with hesitant fuzzy information. The method is flexible because it allows decision makers to provide preference with hesitancy and determine different decision results by choosing different decision strategies. Finally, a numerical example is provided to illustrate the feasibility and practicality of the proposed method.     

A GRASP algorithm for the multi-criteria minimum spanning tree problem

This paper proposes a GRASP (Greedy Randomized Adaptive Search Procedure) algorithm for the multi-criteria minimum spanning tree problem, which is NP-hard. In this problem a vector of costs is defined for each edge of the graph and the problem is to find all Pareto optimal or efficient spanning trees (solutions). The algorithm is based on the optimization of different weighted utility functions. In each iteration, a weight vector is defined and a solution is built using a greedy randomized constructive procedure. The found solution is submitted to a local search trying to improve the value of the weighted utility function. We use a drop-and-add neighborhood where the spanning trees are represented by Prufer numbers. In order to find a variety of efficient solutions, we use different weight vectors, which are distributed uniformly on the Pareto frontier. The proposed algorithm is tested on problems with r=2 and 3 criteria. For non-complete graphs with n=10, 20 and 30 nodes, the performance of the algorithm is tested against a complete enumeration. For complete graphs with n=20, 30 and 50 nodes the performance of the algorithm is tested using two types of weighted utility functions. The algorithm is also compared with the multi-criteria version of the Kruskal’s algorithm, which generates supported efficient solutions. This work was funded by the Municipal Town Hall of Campos dos Goytacazes city. The used computer was acquired with resource of CNPq.     

基于COWA算子的不同类型残缺判断矩阵集结方法

本文研究了决策信息以残缺不确定判断矩阵形式给出的群体决策问题。将残缺不确定区间互反判断矩阵转化为残缺不确定区间互补判断矩阵。基于COWA算子,定义了期望值函数,把残缺不确定区间互反判断矩阵转化成残缺实判断矩阵进行排序,减少了决策信息的丢失。利用IOWA算子来集结群体判断矩阵。最后通过算例说明了该方法的可行性和有效性。     

The Durrmeyer type modification of the q-Baskakov type operators with two parameter α and β

In this paper, we are dealing with q analogue of Durrmeyer type modified the Baskakov operators with two parameter α and β, which introduces a new sequence of positive linear q-integral operators. We show that this sequence is an approximation process in the polynomial weighted space of continuous function defined on the interval [0, ∞). We study moments, weighted approximation properties, the rate of convergence using a weighted modulus of smoothness, asymptotic formula and better error estimation for these operators.     

Wave Properties of Double One-Dimensional Periodic Sheet Grating

We show that the double one-dimensional periodic sheet gratings always have waveguide properties for acoustic waves. In general, there are two types of pass bands: i.e., the connected sets of frequencies for which there exist harmonic acoustic traveling waves propagating in the direction of periodicity and localized in the neighborhood of the grating. Using numerical-analytical methods, we describe the dispersion relations for these waves, pass bands, and their dependence on the geometric parameters of the problem. The phenomenon is discovered of bifurcation of waveguide frequencies with respect to the parameter of the distance between the gratings that decreases from infinity. Some estimates are obtained for the parameters of frequency splitting or fusion in dependence on the distance between the simple blade gratings forming the double grating. We show that near a double sheet grating there always exist standing waves (in-phase oscillations in the neighboring fundamental cells of the group of translations) localized near the grating. By numerical-analytical methods, the dependences of the standing wave frequencies on the geometric parameters of the grating are determined. The mechanics is described of traveling and standing waves localized in the neighborhood of the double gratings.     

Path-based distance functions in n-dimensional generalizations of the face- and body-centered cubic grids

Path-based distance functions are defined on n-dimensional generalizations of the face-centered cubic and body-centered cubic grids. The distance functions use both weights and neighborhood sequences. These distances share many properties with traditional path-based distance functions, such as the city-block distance, but are less rotational dependent. For the three-dimensional case, we introduce four different error functions which are used to find the optimal weights and neighborhood sequences that can be used to define the distance functions with low rotational dependency.     

非局部加权模糊C均值聚类图像分割

去除噪声与保持图像细节特征是含噪声图像分割中面临的一对矛盾。为此,提出一种改进的模糊C均值算法,通过引入非局部加权距离以抑制噪声影响。其中,权值通过局部图像块距离的指数形式计算,并利用半局部统计特性自适应调整其光滑参数。实验结果表明,新方法具有较强的抗噪声能力,同时能够保持较多地细节特征。     

Characterization of partial 3-trees in terms of three structures

A characterization of partial 3-trees is given based on the elimination sequence of vertices. It is proved that a partial 3-tree contains a vertex set satisfying either of certain three kinds of neighborhood relations on vertices and that a graph is a partial 3-tree if and only if eliminating such a vertex set results in a partial 3-tree. These results yield anO(n ²) time algorithm to recognize 3-trees.     

Jump-preserving surface reconstruction from noisy data

A new local smoothing procedure is suggested for jump-preserving surface reconstruction from noisy data. In a neighborhood of a given point in the design space, a plane is fitted by local linear kernel smoothing, giving the conventional local linear kernel estimator of the surface at the point. The neighborhood is then divided into two parts by a line passing through the given point and perpendicular to the gradient direction of the fitted plane. In the two parts, two half planes are fitted, respectively, by local linear kernel smoothing, providing two one-sided estimators of the surface at the given point. Our surface reconstruction procedure then proceeds in the following two steps. First, the fitted surface is defined by one of the three estimators, i.e., the conventional estimator and the two one-sided estimators, depending on the weighted residual means of squares of the fitted planes. The fitted surface of this step preserves the jumps well, but it is a bit noisy, compared to the conventional local linear kernel estimator. Second, the estimated surface values at the original design points obtained in the first step are used as new data, and the above procedure is applied to this data in the same way except that one of the three estimators is selected based on their estimated variances. Theoretical justification and numerical examples show that the fitted surface of the second step preserves jumps well and also removes noise efficiently. Besides two window widths, this procedure does not introduce other parameters. Its surface estimator has an explicit formula. All these features make it convenient to use and simple to compute.