Search

The minimum weighted vertex cover (MWVC) problem is to find a subset of vertices that can cover all the edges of the network and minimize the sum of the vertex weights in the vertex subset. MWVC is a generalization of the minimum vertex cover (MVC) problem and can be regarded as a combinatorial optimization problem. This paper proposes an evolutionary algorithm based on the snowdrift game to solve the MWVC problem. We use the evolutionary algorithm framework, and the snowdrift game is combined to construct and improve the initial solution. First, the network's vertex is regarded as an intelligent agent, and each vertex and its neighbors play a snowdrift game to form an initial solution. Then local search and global search are used to improve the initial solution. The solution is improved according to the proposed score function in the local search stage to obtain a better MWVC solution. The evolutionary algorithm is used in the global search stage to escape the local optimum. Experiments on different networks show that the proposed algorithm are effective on weighted networks. [ABSTRACT FROM AUTHOR]

A fuzzy equivalence relation can be used for clustering. But when using it in applications, we often get a similarity relation rather than an equivalence one because of various reasons. We need to reform it into an equivalence relation close to it to cluster. A commonly used method is transitive closure method, but it usually results in serious distortions about the relation. This paper further studies fuzzy similarity and equivalence relations using fuzzy graphs, and obtains some new results. The defects of transitive closure method are analyzed, and an improved clustering algorithm is given, but it cannot eliminate the inconsistency phenomenon in classification hierarchy structure. To solve this problem, the optimal fuzzy equivalence relation of similarity relation is studied. An optimization model which can derive it exactly is given, but it is too complex for applications. An effective approximation algorithm to get the optimal equivalence relation is thus presented. Several examples and some discussions are also given to illustrate the given methods. [ABSTRACT FROM AUTHOR]

Dominance-based rough set approach (DRSA) is an effective knowledge acquisition tool for ordered data, and to meet the needs of practical applications, the DRSA-based extended models have been widely studied. Nevertheless, the collected data in practical applications are always polluted by noise and most of these extended models are very susceptible to noise. In addition, with the arrival of new attributes and the removal of obsolete attributes, the ordered data have the characteristic of attributes evolving over time (i.e., dynamic ordered data). How to efficiently mining knowledge from dynamic ordered data is a meaningful topic. Motivated by these two issues, we first propose a robust fuzzy dominance rough set model to combat noise interference and then develop incremental update approximation mechanisms based on the proposed model for dynamic ordered data. Firstly, the vaguely quantified fuzzy dominance rough set (VQFDRS) and its matrix representation are introduced. Subsequently, we develop the incremental mechanisms to update the approximations of VQFDRS when multiple attributes are added to or deleted from an ordered data, respectively. Then, on this basis, a static calculation approximations algorithm and two incremental calculation approximations algorithms are designed, respectively. Finally, a series of numerical comparative experiments are performed on six public datasets. Experimental results indicate that the VQFDRS has good robustness, and the incremental algorithms are highly efficient compared with static algorithm under the dynamic data environment. [ABSTRACT FROM AUTHOR]

This study analyzes the conditional gradient method for constrained multiobjective optimization problems, also known as the Frank–Wolfe method. We assume that the objectives are continuously differentiable, and the constraint set is convex and compact. We employ an average-type nonmonotone line search, which takes the average of the recent objective function values. The asymptotic convergence properties without convexity assumptions on the objective functions are established. We prove that every limit point of the sequence of iterates that is obtained by the proposed method is a Pareto critical point. An iteration-complexity bound is provided regardless of the convexity assumption on the objective functions. The effectiveness of the suggested approach is demonstrated by applying it to several benchmark test problems. In addition, the efficiency of the proposed algorithm in generating approximations of the entire Pareto front is compared to the existing Hager–Zhang conjugate gradient method, the steepest descent method, the monotone conditional gradient method, and a nonmonotone conditional gradient method. In finding empirical comparison, we utilize two commonly used performance matrices—inverted generational distance and hypervolume indicators. [ABSTRACT FROM AUTHOR]

The aim of this paper is the study of trapezoidal approximation operators, preserving more indicators of fuzzy numbers, relationships between them and their applications. Initial results lead to achieve three main trapezoidal approximation operators that one of them preserves the core, value and the ambiguity, and another one preserves the core and the expected interval, and third operator preserves the value, ambiguity and expected interval. The related concepts and the important properties of these operators and also, comparisons between them are brought, in details. Finally, a ranking method, an approximation operator preserving the most indicators of fuzzy numbers, and a trapezoidal approximation algorithm with its advantages and comparative examples are given as practical applications of the obtained results. [ABSTRACT FROM AUTHOR]

Classical Rough Set Theory (RST) is a prominent tool to deal with uncertainty of categorical data. However, in a case where values of attributes maintain preference order over each other, RST does not consider it. Dominance-based Rough Set Approach (DRSA), a generalization of RST, studies the dominance aspect of attributes and defines the dominance relation. The lower and upper approximations form the basis of most algorithms based on RST. However, determining DRSA approximations is computationally expensive so that the algorithms using approximations may suffer serious performance bottleneck when dealing with datasets of larger sizes. In this paper, we proposed a heuristic approach to compute lower and upper approximations based on DRSA, in time efficient manner. The proposed algorithm directly calculates approximations without going through the heavy computations of dominance positive or negative cones. We introduce heuristic rules to calculate approximations without considering the intersection and subset relations. By using the properties and logical structure of approximations, our mathematical implications select an object for all relevant approximation sets. The proposed approach was compared with the conventional method using eleven benchmark datasets from UCI. The results showed that the proposed rules significantly reduce the execution time by avoiding the redundant computations, which ultimately affect the structural complexity and memory requirements. The average reduction in execution time was found to be 83%. The proposed approach also reduces the structural complexity and memory consumption by 89.69%. [ABSTRACT FROM AUTHOR]

Given an undirected, connected, edge-weighted graph G and a positive integer d, the degree-constrained minimum spanning tree (dc-MST) problem aims to find a minimum spanning tree T on G subject to the constraint that each vertex is either a leaf vertex or else has degree at most d in T, where d is a given positive integer. The dc-MST is NP -hard problem for d ≥ 2 and finds several real-world applications. This paper proposes a hybrid approach (H SSGA) combining a steady-state genetic algorithm and local search strategies for the this problem. An additional step (based on perturbation strategy at a regular interval of time) in the replacement strategy is applied in order to maintain diversity in the population throughout the search process. On a set of available 107 benchmark instances, computational results show the superiority of our proposed H SSGA in comparison with the state-of-the-art metaheuristic techniques. [ABSTRACT FROM AUTHOR]

Axiomatic characterization is the foundation of rough set theory: the axiom sets of approximation operators guarantee the existence of binary relations, coverings or (generalized) neighborhood systems that reproduce the approximation operators. Focusing on two pairs of generalized neighborhood system-based approximation operators (one pair is defined by Syau and Lin, the other pair is newly defined), we establish their axiomatic characterizations. [ABSTRACT FROM AUTHOR]

We develop an approach allowing to measure the “quality” of rough approximation of fuzzy sets. It is based on what we call “an approximative quadruple” Q=(L,M,φ,ψ) where L and M are complete lattice commutative monoids and φ:L→M, ψ:M→L are mappings satisfying certain conditions. By realization of this scheme, we get measures of upper and lower rough approximation for L-fuzzy subsets of a set equipped with an M-preoder R:X×X→M. In case R is symmetric, these measures coincide. Basic properties of such measures are studied. Besides, we present an interpretation of measures of rough approximation in terms of LM-fuzzy topologies. [ABSTRACT FROM AUTHOR]

The learning of variational inference can be widely seen as first estimating the class assignment variable and then using it to estimate parameters of the mixture model. The estimate is mainly performed by computing the expectations of the prior models. However, learning is not exclusive to expectation. Several authors report other possible configurations that use different combinations of maximization or expectation for the estimation. For instance, variational inference is generalized under the expectation-expectation (EE) algorithm. Inspired by this, another variant known as the maximization-maximization (MM) algorithm has been recently exploited on various models such as Gaussian mixture, Field-of-Gaussians mixture, and sparse-coding-based Fisher vector. Despite the recent success, MM is not without issue. Firstly, it is very rare to find any theoretical study comparing MM to EE. Secondly, the computational efficiency and accuracy of MM is seldom compared to EE. Hence, it is difficult to convince the use of MM over a mainstream learner such as EE or even Gibbs sampling. In this work, we revisit the learning of EE and MM on a simple Bayesian GMM case. We also made theoretical comparison of MM with EE and found that they in fact obtain near identical solutions. In the experiments, we performed unsupervised classification, comparing the computational efficiency and accuracy of MM and EE on two datasets. We also performed unsupervised feature learning, comparing Bayesian approach such as MM with other maximum likelihood approaches on two datasets. [ABSTRACT FROM AUTHOR]

The main goal of this paper is to investigate monadic bounded hoops and prove the completeness of the monadic hoop logic. In the paper, we introduce monadic bounded hoops: A variety of bounded hoops equipped with universal and existential quantifiers. Also, we study some properties of them and obtain some conditions under which a bounded hoop becomes a Heyting algebra and BL-algebra. In addition, we introduce and investigate monadic filters in monadic bounded hoops. Using monadic filters on monadic bounded hoops, we characterize simple monadic bounded hoops. Moreover, we focus on algebraic structures of the set MF[H] of all monadic filters on monadic bounded hoops and obtain that MF[H] forms a complete Heyting algebra. Further, we discuss relations between monadic bounded hoops and some related algebraic structures, likeness other monadic algebras, bounded hoops with regular Galois connection and rough approximation spaces. Finally, as an application of monadic bounded hoops, we prove the completeness of monadic hoop logic. These results will provide a more general algebraic foundations of soft computing intended as a method for dealing with uncertain information, fuzzy information and decision making. [ABSTRACT FROM AUTHOR]

The DBSCAN algorithm is a well-known density based clustering approach particularly useful in spatial data mining for its ability to find objects' groups with heterogeneous shapes and homogeneous local density distributions in the feature space. Furthermore, it can be suitable as scaling down approach to deal with big data for its ability to remove noise. Nevertheless, it suffers for some limitations, mainly the inability to identify clusters with variable density distributions and partially overlapping borders, which is often a characteristics of both scientific data and real-world data. To this end, in this work, we propose three fuzzy extensions of the DBSCAN algorithm to generate clusters with distinct fuzzy density characteristics. The original version of DBSCAN requires two precise parameters (minPts and ϵ) to define locally dense areas which serve as seeds of the clusters. Nevertheless, precise values of both parameters may be not appropriate in all regions of the dataset. In the proposed extensions of DBSCAN, we define soft constraints to model approximate values of the input parameters. The first extension, named Fuzzy Core DBSCAN, relaxes the constraint on the neighbourhood's density to generate clusters with fuzzy core points, i.e. cores with distinct density; the second extension, named Fuzzy Border DBSCAN, relaxes ϵ to allow the generation of clusters with overlapping borders. Finally, the third extension, named Fuzzy DBSCAN subsumes the previous ones, thus allowing to generate clusters with both fuzzy cores and fuzzy overlapping borders. Our proposals are compared w.r.t. state of the art fuzzy clustering methods over real-world datasets. [ABSTRACT FROM AUTHOR]

In this paper, a new group of optimization algorithms named Human Strategy Algorithm (HS) is proposed which is inspired by human strategies to problem solving. The main idea of HS is based on human actions to find the problem’s optima by means of accessible instruments. As the environment of an unknown problem assumed to be a black box, it is supposed that the environment of our problem is a dark room occupied by several men named blind men. The main mission of these men is to look for the optimum solution. Each man has at least one instrument as his assistance. Like real life, the instrument might be any tool such as stick, billy, rope, stone, yoyo, sweep. Any instrument by its unique features is suitable in some situations. In fact, this algorithm maps problem space and searches agents to dark room and people, respectively. In this paper, one sample algorithm of the group of human strategy, YOYO Blind Man Algorithm (YOYO-BMA), is introduced which uses yoyos as men’s accessible instruments. The performance of the YOYO-BMA is evaluated on a set of benchmark problems provided for CEC’2010 Special Session and Competition on Large-Scale Global Optimization (Tang et al. 2010). The results show superior performance of proposed algorithm in comparison with others. Moreover, the problem of designing urban traffic network is solve to evaluate the algorithm using a real complex problem. [ABSTRACT FROM AUTHOR]

Pseudo-centroid clustering replaces the traditional concept of a centroid expressed as a center of gravity with the notion of a pseudo-centroid (or a coordinate free centroid) which has the advantage of applying to clustering problems where points do not have numerical coordinates (or categorical coordinates that are translated into numerical form). Such problems, for which classical centroids do not exist, are particularly important in social sciences, marketing, psychology and economics, where distances are not computed from vector coordinates but rather are expressed in terms of characteristics such as affinity relationships, psychological preferences, advertising responses, polling data and market interactions, where distances, broadly conceived, measure the similarity (or dissimilarity) of characteristics, functions or structures. We formulate a K-PC algorithm analogous to a K-Means algorithm and focus on two key types of pseudo-centroids, MinMax-centroids and (weighted) MinSum-centroids, and describe how they, respectively, give rise to a K-MinMax algorithm and a K-MinSum algorithm which are analogous to a K-Means algorithm. The K-PC algorithms are able to take advantage of problem structure to identify special diversity-based and intensity-based starting methods to generate initial pseudo-centroids and associated clusters, accompanied by theorems for the intensity-based methods that establish their ability to obtain best clusters of a selected size from the points available at each stage of construction. We also introduce a regret-threshold PC algorithm that modifies the K-PC algorithm together with an associated diversification method and a new criterion for evaluating the quality of a collection of clusters. [ABSTRACT FROM AUTHOR]

This paper investigates a meta-heuristic (MH) for the Pareto-optimal dissimilar path problem (DPP) (PDPP) whose solution is a set composed of at least two different paths. The objective vector of a PDPP includes some conflicting objectives: on the one hand, the average path measures such as the length and risk of paths in a solution must be kept low and, on the other hand, the dissimilarity among these paths should be kept high. The dissimilarity of the DPP is a measure of a paths set with cardinality no less than two. However, just one path can be extracted from a chromosome in the existing MHs for various path problems. This results in a great difficulty to evaluate the chromosome in the existing MHs when we apply them to solve DPP and, consequently, there exists no MH for solving the DPP so far. In this paper, a new decoding approach of a chromosome is first explored and, with this approach, a set of paths can be extracted from a chromosome. By combining the simulated annealing (SA), in which the new decoding approach is adopted, with the well-known greedy randomized adaptive search procedure (GRASP), a SA-based GRASP for the PDPP is proposed. The proposed algorithm is compared against a most recent heuristic, whose performance is better than all of the early approaches, for the PDPP and the experimental results show that the proposed algorithm is able to quickly create superior approximation of the efficient set of the PDPP than the existing solution approaches for the PDPP. [ABSTRACT FROM AUTHOR]

In this study, a novel online support vector regressor (SVR) controller based on system model estimated by a separate online SVR is proposed. The main idea is to obtain an SVR controller based on an estimated model of the system by optimizing the margin between reference input and system output. For this purpose, 'closed-loop margin' which depends on tracking error is defined, then the parameters of the SVR controller are optimized so as to optimize the closed-loop margin and minimize the tracking error. In order to construct the closed-loop margin, the model of the system estimated by an online SVR is utilized. The parameters of the SVR controller are adjusted via the SVR model of system. The stability of the closed-loop system has also been analyzed. The performance of the proposed method has been evaluated by simulations carried out on a continuously stirred tank reactor (CSTR) and a bioreactor, and the results show that SVR model and SVR controller attain good modeling and control performances. [ABSTRACT FROM AUTHOR]

The rough approximations on a complete completely distributive lattice L based on binary relation were introduced by Zhou and Hu (Inf Sci 269:378-387, 2014), where the binary relation was defined on the set of non-zero join-irreducible elements. This paper extends Zhou and Hu's rough set model by defining new approximation operators via ideal. When I is the least ideal of L and R is a reflexive binary relation, these two approximations coincide. We present the essential properties of new approximations and also discuss how the new one relates to the old one. Finally, the topological and lattice structures of the approximations are given. [ABSTRACT FROM AUTHOR]

The purpose of this study is to investigate the universal approximation capabilities of a certain class of single-hidden-layer feedforward neural networks, which is called double 2 $$\pi $$ -periodic approximate identity neural networks. Using double 2 $$\pi $$ -periodic approximate identity, several theorems concerning the universal approximation capabilities of the networks are proved. The proofs of these theorems are sketched based on the double convolution linear operators and the definition of $$\epsilon $$ -net. The obtained results are divided into two categories. First, the universal approximation capability of the networks is shown in the space of continuous bivariate 2 $$\pi $$ -periodic functions. Then, universal approximation capability of the networks is extended to the space of pth-order Lebesgue-integrable bivariate 2 $$\pi $$ -periodic functions. These results can be interpreted as an extension of the universal approximation capabilities established for single-hidden-layer feedforward neural networks. [ABSTRACT FROM AUTHOR]

The paper presents a fragile watermarking technique that may be used to discover image manipulations at block level. The proposed algorithm, based on the Karhunen-Loève linear transform (KLT), modifies some of the KLT coefficients obtained from a secret base (defined by a secret key image) so that they contain a binary pseudo-random message. A genetic algorithm is used to compensate for rounding errors introduced by inverse transforming in the integer pixel domain. An extensive experimentation has been performed to test the effectiveness of the method and to show the sensitivity of the algorithm to single pixel modifications (also as a function of the number of modified coefficients). A comparison with other fragile watermarking methods is reported. It should be noted that the proposed approach results in both a high PSNR (more than 53 dB on average) and a high subjective quality. The system may be tested online by submitting images to be watermarked and subsequently verifying the presence of modifications in a previously marked image. [ABSTRACT FROM AUTHOR]

In this paper we propose several approximation algorithms for the problems of full and partial abductive inference in Bayesian belief networks. Full abductive inference is the problem of finding the $$k$$ most probable state assignments to all non-evidence variables in the network while partial abductive inference is the problem of finding the $$k$$ most probable state assignments for a subset of the non-evidence variables in the network, called the explanation set. We developed several multi-swarm algorithms based on the overlapping swarm intelligence framework to find approximate solutions to these problems. For full abductive inference a swarm is associated with each node in the network. For partial abductive inference, a swarm is associated with each node in the explanation set and each node in the Markov blankets of the explanation set variables. Each swarm learns the value assignments for the variables in the Markov blanket associated with that swarm's node. Swarms learning state assignments for the same variable compete for inclusion in the final solution. [ABSTRACT FROM AUTHOR]

This paper presents the design and the application of asynchronous models of parallel evolutionary algorithms. An overview of the existing parallel evolutionary algorithm (PEA) models and available implementations is given. We present new PEA models in the form of asynchronous algorithms and implicit parallelization, as well as experimental data on their efficiency. The paper also discusses the definition of speedup in PEAs and proposes an appropriate speedup measurement procedure. The described parallel EA algorithms are tested on problems with varying degrees of computational complexity. The results show good efficiency of asynchronous and implicit models compared to existing parallel algorithms. [ABSTRACT FROM AUTHOR]

Change-point methods (CPMs) are statistical tests design to assess whether a given sequence comes from an unique, stationary, data-generating process. CPMs eventually estimate the change-point location, i.e., the point where the data-generating process shifted. While there exists a large literature concerning CPMs meant for sequences of independent and identically distributed (i.i.d.) random variables, their use on time-dependent signals has not been properly investigated. In this case, a straightforward solution consists in computing at first the residuals between the observed signal and the output of a suitable approximation model, and then applying the CPM on the residual sequence. Unfortunately, in practical applications, such residuals are seldom i.i.d., and this may prevent the CPMs to operate properly. To counteract this problem, we introduce the ensemble of CPMs, which aggregates several estimates obtained from CPMs executed on different subsequences of residuals, obtained from random sampling. Experiments show that the ensemble of CPMs improves the change-point estimates when the residuals are not i.i.d., as it is often the case in real-world scenarios. [ABSTRACT FROM AUTHOR]

This paper discusses the subject of automatic evolutionary sound matching: systems in which evolutionary algorithms are used to automatically derive the parameters of a synthesiser to produce a sound that matches a specified target sound. The paper describes prior work and identifies the principal causes of match inaccuracy, which are often due to optimiser limitations as a result of search space problem difficulty. The components of evolutionary matching systems contributing to problem difficulty are discussed and suggestions as to how improvements can be made through problem simplification or optimiser sophistication are considered. Subsequently, a novel clustering evolution strategy is presented which enables the concurrent optimisation of multiple distinct search space solutions, intended for the purposes of sound matching with standard frequency modulation (FM) synthesisers. The algorithm is shown to outperform standard multi-membered and multi-start (1 + 1) evolution strategies in application to different FM synthesis models for static and dynamic sounds. The comparative study makes use of a contrived matching method, which ensures that results are not affected by the limitations of the matching synthesiser. [ABSTRACT FROM AUTHOR]

In standard frequent item set mining a transaction supports an item set only if all items in the set are present. However, in many cases this is too strict a requirement that can render it impossible to find certain relevant groups of items. By relaxing the support definition, allowing for some items of a given set to be missing from a transaction, this drawback can be amended. The resulting item sets have been called approximate, fault-tolerant or fuzzy item sets. In this paper we present two new algorithms to find such item sets: the first is an extension of item set mining based on cover similarities and computes and evaluates the subset size occurrence distribution with a scheme that is related to the Eclat algorithm. The second employs a clustering-like approach, in which the distances are derived from the item covers with distance measures for sets or binary vectors and which is initialized with a one-dimensional Sammon projection of the distance matrix. We demonstrate the benefits of our algorithms by applying them to a concept detection task on the 2008/2009 Wikipedia Selection for schools and to the neurobiological task of detecting neuron ensembles in (simulated) parallel spike trains. [ABSTRACT FROM AUTHOR]

The use of mechanical trading systems allows managing a huge amount of data related to the factors affecting investment performance (macroeconomic variables, company information, industrial indicators, market variables, etc.) while avoiding the psychological reactions of traders when they invest in financial markets. When trading is executed in an intra-daily frequency instead a daily frequency, mechanical trading systems needs to be supported by very powerful engines since the amount of data to deal with grow while the response time required to support trades gets shorter. Numerous studies document the use of genetic algorithms (GAs) as the engine driving mechanical trading systems. The empirical insights provided in this paper demonstrate that the combine use of GA together with a GPU-CPU architecture speeds up enormously the power and search capacity of the GA for this kind of financial applications. Moreover, the parallelization allows us to implement and test previous GA approximations. Regarding the investment results, we can report 870% of profit for the S&P 500 companies in a 10-year time period (1996-2006), when the average profit of the S&P 500 in the same period was 273%. [ABSTRACT FROM AUTHOR]

In a very large database, there exists sensitive information that must be protected against unauthorized accesses. The confidentiality protection of the information has been a long-term goal pursued by the database security research community and the government statistical agencies. In this paper, we proposed greedy methods for hiding sensitive rules. The experimental results showed the effectiveness of our approaches in terms of undesired side effects avoided in the rule hiding process. The results also revealed that in most cases, all the sensitive rules are hidden without generating spurious rules. First, the good scalability of our approach in terms of database sizes was achieved by using an efficient data structure, FCET, to store only maximal frequent itemsets instead of storing all frequent itemsets. Furthermore, we also proposed a new framework for enforcing the privacy in mining association rules. In the framework, we combined the techniques of efficiently hiding sensitive rules with the transaction retrieval engine based on the FCET index tree. For hiding sensitive rules, the proposed greedy approach includes a greedy approximation algorithm and a greedy exhausted algorithm to sanitize the database. In particular, we presented four strategies in the sanitizing procedure and four strategies in the exposed procedure, respectively, for hiding a group of association rules characterized as sensitive or artificial rules. In addition, the exposed procedure would expose missing rules during the processing so that the number of missing rules could be lowered as much as possible. [ABSTRACT FROM AUTHOR]

Three ways for generating the optimal transitive approximations or a suboptimal transitive approximation are given in this paper. The first one can obtain all the optimal transitive approximations for any proximity relation. However, trying to find all the optimal transitive approximations can be very expensive. The second one gives a method to obtain a suboptimal transitive approximation which can frequently generate an optimal transitive approximation. Furthermore, starting from the transitive closure the third method is proposed which can obtain a locally optimal transitive approximation. Finally, numerical experiments are carried out to show the abilities of these algorithms and compare them to other existing approximation algorithms. [ABSTRACT FROM AUTHOR]