Data integration constraints for consistent data redundancy in fuzzy databases

Although the problem of data integration in relational databases has been extensively studied, little work has addressed this problem in the context of fuzzy relational databases. Data integration is highly complex in fuzzy relational databases, partially because of the involvement of the resemblance relation. Inconsistent data redundancy may occur when the fuzzy databases to be integrated are associated with different resemblance relation on a given domain. This work presents the notions of consistency constraints, and applies them to the problem of data integration in several fuzzy data models. The constraints ensure that fuzzy databases with different resemblance relations agree to each other regarding data redundancy. In addition a solution for integrating inconsistent fuzzy databases with minimal information loss is provided. © 2008 Wiley Periodicals, Inc.     

基于区间—遗传算法求解非线性方程组

将非线性方程组的求解转化为函数优化问题,结合遗传算法的群体搜索、全局收敛的优点,及区间算法特有的解的存在性检验准则,提出了一种区间—遗传算法。在迭代计算过程中,区间算法为遗传算法搜索提供可靠区域,同时遗传算法为区间算法提供安全的初始区域。数值实验表明,该算法能够在较大范围的初始区间内快速,可靠地迭代得到高精度的区间解,是求解非线性方程组的一种有效的算法。     

求解非线性规划问题的改进直觉模糊遗传算法

提出一种改进的直觉模糊遗传算法用于求解带有多维约束的非线性规划问题。以遗传算法在迭代寻优中的个体适应度大小构造相应可行解的隶属度和非隶属度函数,将非线性规划问题直觉模糊化转化为直觉模糊非线性规划问题,通过建立直觉模糊推理系统,自适应地调节遗传算法的交叉率和变异率;并采用一种改进的选择策略,将个体按适应度值大小排序、等量分组,对适应度低的个体组随机选择复制,保留不可行解中可能隐含的有利寻优信息,增强种群个体的多样性和竞争性。仿真实验结果表明,该算法求解非线性规划问题时是可行和有效的。     

Deriving minimal solutions for fuzzy relation equations with max-product composition

This work considers fuzzy relation equations with max-product composition. The critical problem in solving such equations is to determine the minimal solutions when an equation is solvable. However, this problem is NP-hard and difficult to solve [A.V. Markovskii, On the relation between equations with max-product composition and the covering problem, Fuzzy Sets and Systems 153 (2005) 261-273]. This work first examines the attributes of a solvable equation and characteristics of minimal solutions, then reduces the equation to an irreducible form, and converts the problem into a covering problem, for which minimal solutions are correspondingly determined. Furthermore, for theoretical and practical applications, this work presents a novel method for obtaining minimal solutions. The proposed method easily derives a minimal solution, and obtains other minimal solutions from this predecessor using a back-tracking step. The proposed method is compared with an existing algorithm, and some applications are described in detail.     

An Efficient Procedure for Solving a Fuzzy Relational Equation With Max–Archimedean t-Norm Composition

In the literature, a necessary condition for minimal solutions of a fuzzy relational equation with max-product composition shows that each of its components is either zero or the corresponding component's value of the greatest solution. In this paper, we first extend this necessary condition to the situation with max-Archimedean triangular-norm (t-norm) composition. Based on this necessary condition, we then propose rules to reduce the problem size so that the complete set of minimal solutions can be computed efficiently. Furthermore, rather than work with the actual equations, we employ a simple matrix whose elements capture all of the properties of the equations in finding the minimal solutions. Numerical examples with specific cases of the max-Archimedean t-norm composition are provided to illustrate the procedure.     

Numerical solution of fuzzy relational equations based on smooth fuzzy norms

In this paper, we study and formulate a BP learning algorithm for fuzzy relational neural networks based on smooth fuzzy norms for functions approximation. To elaborate the model behavior more, we have used different fuzzy norms led to a new pair of fuzzy norms. An important practical case in fuzzy relational equations (FREs) is the identification problem which is studied in this work. In this work we employ a neuro-based approach to numerically solve the set of FREs and focus on generalized neurons that use smooth s-norms and t-norms as fuzzy compositional operators.     

The quadratic programming problem with fuzzy relation inequality constraints

The quadratic programming has been widely applied to solve real world problems. The quadratic functions are often applied in the inventory management, portfolio selection, engineering design, molecular study, and economics, etc. Fuzzy relation inequalities (FRI) are important elements of fuzzy mathematics, and they have recently been widely applied in the fuzzy comprehensive evaluation and cybernetics. In view of the importance of quadratic functions and FRI, we present a fuzzy relation quadratic programming model with a quadratic objective function subject to the max-product fuzzy relation inequality constraints. Some sufficient conditions are presented to determine its optimal solution in terms of the maximum solution or the minimal solutions of its feasible domain. Also, some simplification operations have been given to accelerate the resolution of the problem by removing the components having no effect on the solution process. The simplified problem can be converted into a traditional quadratic programming problem. An algorithm is also proposed to solve it. Finally, some numerical examples are given to illustrate the steps of the algorithm.     

Genetic algorithm and large neighbourhood search to solve the cell formation problem

We first introduce a local search procedure to solve the cell formation problem where each cell includes at least one machine and one part. The procedure applies sequentially an intensification strategy to improve locally a current solution and a diversification strategy destroying more extensively a current solution to recover a new one. To search more extensively the feasible domain, a hybrid method is specified where the local search procedure is used to improve each offspring solution generated with a steady state genetic algorithm. The numerical results using 35 most widely used benchmark problems indicate that the line search procedure can reduce to 1% the average gap to the best-known solutions of the problems using an average solution time of 0.64 s. The hybrid method can reach the best-known solution for 31 of the 35 benchmark problems, and improve the best-known solution of three others, but using more computational effort.     

一种基于GA-FAHP的软件漏洞风险评估方法

针对软件系统中漏洞的风险等级确定等问题,提出了一种利用遗传模糊层次分析法(GA-FAHP)评估软件漏洞风险的方法。该方法首先利用改进的模糊层次分析法求出各风险因素权重,并建立模糊判断矩阵;其次将模糊判断矩阵的一致性检验与修正计算过程转化为带约束的非线性系统优化问题,并利用遗传算法求解;最后,通过GA-FAHP算法求出软件漏洞的风险值。实验结果表明,该方法具有较好的准确性和有效性,为软件漏洞风险评估提供了一种可行的途径。     

一种基于遗传算法求解TSP问题的优化算法

旅行商问题是组合优化的一个经典问题,也是评价算法好坏的一个标准,它要求在给定的一张图中寻找一条哈密尔顿回路,使得该回路在所有的回路中长度最短。然而,该问题是一个NP完全问题,其求解时间会随着问题规模的扩大急剧上升。因此,只能希望在允许的时间内寻求问题的一个较优的解来替代。本文借助生物学的相关理论与思想采用遗传算法对该问题进行求解,最后通过对遗传算法的进一步分析,提出了一种可行的改进算法,达到了获得较优解的目的。     

An algorithm for solving fuzzy relation equations with max-T composition operator

This paper studies the problem of solving a max-T composite finite fuzzy relation equation, where T is a special class of pseudo-t-norms. If the equation is solvable, then its set of feasible solutions is determined by the greatest solution and a finite number of minimal solutions. Some necessary conditions are presented for the minimal solutions in terms of the maximum solution and zero value. Under these conditions, some minimal solutions of the system can be obtained easily. Some procedures are also proposed in order to simplify the original system. The simplified system is then decomposed (if possible) into several subsystems with smaller dimensions, which are very easy to solve. Furthermore, a method is presented to solve each subsystem. By combining the method and those procedures, an efficient algorithm is proposed to obtain the set of feasible solutions of the original system. Two examples are also given to illustrate the algorithm.     

Fuzzy Relation Equations (II): The Branch-point-solutions and the Categorized Minimal Solutions

This paper presents some novel theoretical results as well as practical algorithms and computational procedures on fuzzy relation equations (FRE). These results refine and improve what has already been reported in a significant manner. In the previous paper, the authors have already proved that the problem of solving the system of fuzzy relation equations is an NP-hard problem. Therefore, it is practically impossible to determine all minimal solutions for a large system if P ≠ NP. In this paper, an existence theorem is proven: there exists a special branch-point-solution that is greater than all minimal solutions and less than the maximum solution. Such branch-point-solution can be calculated based on the solution-base-matrix. Furthermore, a procedure for determining all branch-point-solutions is designed. We also provide efficient algorithms which is capable of determining as well as searching for certain types of minimal solutions. We have thus obtained: (1) a fast algorithm to determine whether a solution is a minimal solution, (2) the algorithm to search for the minimal solutions that has at least a minimum value at a component in the solution vector, and (3) the procedure of determining if a system of fuzzy relation equations has the unique minimal solution. Other properties are also investigated.     

有限车辆调度问题的模型和改进遗传算法*

考虑到对带时间窗的有限车辆调度问题研究不足的事实,在建立了数学模型的基础上对传统的遗传算法(GA)进行改进：提出采用BellmanFord求最短路算法找出染色体所表示路径的最优组合形式;变异操作应用禁忌搜索算法(TS),并采用TS的动态摆动策略,对邻域结构的可行及不可行解进行有效的搜索。最后用Solomon中的Rc1数据验证了算法的有效性,其结果比较理想。     

Solving exclusionary side constrained transportation problem by using a hybrid spanning tree-based genetic algorithm

In real life applications we often have the following problem: How to find the reasonable assignment strategy to satisfy the source and destination requirement without shipping goods from any pairs of prohibited sources simultaneously to the same destination so that the total cost can be minimized. This kind of problem is known as the transportation problem with exclusionary side constraint (escTP). Since this problem is one of nonlinear programming models, it is impossible to solve this problem using a traditional linear programming software package (i.e., LINDO). In this paper, an evolutionary algorithm based on a genetic algorithm approach is proposed to solve it. We adopt a Prüfer number to represent the candidate solution to the problem and design the feasibility of the chromosome. Moreover, to handle the infeasible chromosome, here we also propose the repairing procedure. In order to improve the performance of the genetic algorithm, the fuzzy logic controller (FLC) is used to dynamically control the genetic operators. Comparisons with other conventional methods and the spanning tree-based genetic algorithm (st-GA) are presented and the results show the proposed approach to be better as a whole.     

改进型粒子群优化算法求解车辆径优化问题

为了避免粒子群算法求解车辆路径问题容易陷入局部最优,提出了扫描-粒子群算法。运用扫描算法对矿点进行扫描,生成初始可行解链,将其作为粒子的初始位置代入到粒子群中搜索,得到粒子种群历史最优位置,将种群粒子最优位置逆转录生成对应的可行解链。将改进型粒子群算法用于求解郑州煤电物资供销有限公司的车辆调度问题同时将该算法与经典的粒子群算法和遗传算法做了对比实验,仿真实验结果表明,改进型粒子群算法可以更快速、更有效求得车辆路径问题的最优解。     

Efficient DE-based symbiotic cultural algorithm for neuro-fuzzy system design

This study proposes a differential-evolution-based symbiotic cultural algorithm (DESCA) for the implementation of neuro-fuzzy systems (NFS) to solve nonlinear control system problems. DESCA adopts symbiotic evolution to decompose a fuzzy system into multiple fuzzy rules as multiple subpopulations. In addition, DESCA randomly selects fuzzy rules from different subpopulations that combine into a complete solution whose performance is be evaluated. Moreover, DESCA uses various mutation strategies of differential evolution as five knowledge sources in the belief space. These knowledge sources influence the population space in the cultural algorithm and can be used as models to guide the feasible search space. Finally, the proposed algorithm is applied to various simulations. The results demonstrate the effectiveness of this approach.     

求解VRPSDP问题的改进模拟退火遗传算法

配送和回收一体化的车辆路径问题（VRPSDP）是一种非常复杂的NP难题。针对这一问题,设计了一种改进的模拟退火遗传算法ISAGA,采用非零自然数编码机制和弱可行解到强可行解的解码机制,将3PM交叉算子和退火选择相结合,形成贪心3PM交叉算子,引进insert 、swap和2-opt分别对解进行迭代优化,并将模拟退火算法和遗传算法巧妙地结合,使得遗传算法在前期发挥着全局搜索的强大功能;后期用模拟退火算法来处理遗传算法前期的全局较优解,充分利用模拟退火算法后期局部搜索的强大功能。经过国际公认的测试算例验证,ISAGA算法在Min算例、Salhi和Nagy算例中均找到了比现有算法已知最好解更优的解。     

Simulated evolution for timing and low power VLSI standard cell placement

This paper presents a Fuzzy Simulated Evolution algorithm for VLSI standard cell placement with the objective of minimizing power, delay and area. For this hard multiobjective combinatorial optimization problem, no known exact and efficient algorithms exist that guarantee finding a solution of specific or desirable quality. Approximation iterative heuristics such as Simulated Evolution are best suited to perform an intelligent search of the solution space. Due to the imprecise nature of design information at the placement stage the various objectives and constraints are expressed in the fuzzy domain. The search is made to evolve toward a vector of fuzzy goals. Variants of the algorithm which include adaptive bias and biasless simulated evolution are proposed and experimental results are presented. Comparison with genetic algorithm is discussed.     

Strategic bidding using fuzzy adaptive gravitational search algorithm in a pool based electricity market

A novel stochastic optimization approach to solve optimal bidding strategy problem in a pool based electricity market using fuzzy adaptive gravitational search algorithm (FAGSA) is presented. Generating companies (suppliers) participate in the bidding process in order to maximize their profits in an electricity market. Each supplier will bid strategically for choosing the bidding coefficients to counter the competitors bidding strategy. The gravitational search algorithm (GSA) is tedious to solve the optimal bidding strategy problem because, the optimum selection of gravitational constant (G). To overcome this problem, FAGSA is applied for the first time to tune the gravitational constant using fuzzy “IF/THEN” rules. The fuzzy rule-based systems are natural candidates to design gravitational constant, because they provide a way to develop decision mechanism based on specific nature of search regions, transitions between their boundaries and completely dependent on the problem. The proposed method is tested on IEEE 30-bus system and 75-bus Indian practical system and compared with GSA, particle swarm optimization (PSO) and genetic algorithm (GA). The results show that, fuzzification of the gravitational constant, improve search behavior, solution quality and reduced computational time compared against standard constant parameter algorithms.     

Fuzzy relation equations (I): the general and specialized solving algorithms

 In this article, we develop a new method and an algorithm to solve a system of fuzzy relation equations. We first introduce a solution-base-matrix and then give a tractable mathematical logic representation of all minimal solutions. Next, we design a new universal algorithm to get them. Two simplification rules are found to simplify the solution-base-matrix. We show that a polynomial time algorithm to find all minimal solutions for a general system of fuzzy relation equations simply does not exist with expectation of P=N P. Hence, the problem of solving fuzzy relation equations is an N P-hard problem in terms of computational complexity. Our universal algorithm is still useful when one does not solve a large number of equations. In many real applications the problem of solving fuzzy relation equations can be simplified in polynomial time problems. In this article, we will discuss several cases of practical applications which have such polynomial algorithms.