模糊描述逻辑FALNUI的tableaux推理

分析了模糊描述逻辑FALNUI与模糊ER模型的关系,即模糊ER模型可以转化为FALNUI的知识库,并且模糊ER模型的可满足性、冗余性和包含关系等推理问题可以转化为FALNUI的包含推理问题,但FALNUI缺乏相应的推理算法.提出了一种基于描述逻辑tableaux的FALNUI的可满足性推理算法,证明了该推理算法的正确性,以及提出了FALNUI的Tbox扩展和去除方法,证明了FALNUI的包含推理问题可以转化为可满足性推理问题,并给出了FALNUI的包含推理算法. FALNUI的tableaux推理算法为模糊ER模型的可满足性、冗余性和包含关系等自动推理的实现提供了理论基础.     

面向语义Web语义表示的模糊描述逻辑

分析了语义Web语义表示理论的研究现状及存在的问题,提出了一种新的面向语义Web语义表示的模糊描述逻辑FSHOIQ(fuzzy SHOIQ).给出了FSHOIQ的语法和语义,提出了FSHOIQ的模糊Tableaux的概念,给出了一种基于模糊Tableaux的FSHOIQ的ABox约束下的可满足性推理算法,证明了可满足性推理算法的正确性.提出了FSHOIQ的TBox扩展和去除方法,并证明了FSHOIQ的TBox约束下的包含推理问题可以转化为ABox约束下的可满足性推理问题.FSHOIQ为语义Web表示和推理模糊知识提供了理论基础.     

An Efficient Algorithm for Solving Fuzzy Linear Programming Problems

In this article, we consider some well-known approaches for solving fuzzy linear programming (FLP) problems. We present some of the difficulties of these approaches. Then, crisp linear programming problems are suggested for solving FLP problems. A new algorithm is also given. The proposed approach has advantages over the other methods. For example, we can achieve higher membership degrees for objective function and constraints. Moreover, we show that the fuzzy optimal solutions obtained by the proposed approach are efficient enough. Also, we see that unlike the previous methods, our method finds efficient solutions by solving only one crisp linear problem instead of solving two or three crisp problems. Finally some numerical examples are presented to show the efficiency of the given approach over the other approaches.     

可满足问题中的模型计数

模型计数问题是指计算给定问题的解的个数,这是一类比决策更困难的问题,也是人工智能领域研究的一个热点问题.对模型计数问题的研究不仅可以提高算法的求解效率,更能促进对问题困难本质的了解.以可满足问题（命题可满足（SAT）和约束可满足问题（CSP））为例,从精确算法和近似求解两方面综述了模型计数问题的研究现状,重点介绍了相关概念以及各个算法之间的优缺点,并提出了有待解决的开放性问题,对模型计数问题的研究予以了总结和展望.     

基于模糊命题模态逻辑的形式推理系统

探讨基于可信度的模糊命题模态逻辑的形式推理,给出相关的模糊Kripke语义描述.其研究目的旨在解决基于模态命题逻辑的模糊推理的能行问题.在研究过程与方法上,以完全形式化的方法将模糊模态逻辑语法和语义统一在一个形式系统中,以模糊约束作为基本表达式,给出推理规则,建立了相应的模糊推理形式系统,并以形式系统中模糊约束集的可满足性来表示模糊推理的有效性,使模糊推理过程变得容易,为最终在计算机上实现基于模态逻辑的模糊推理打下了一定的基础.主要结论是证明了基于可满足性的模糊推理形式系统的可靠性与完备性.     

Maximal covering location problem (MCLP) with fuzzy travel times

This paper presents a fuzzy maximal covering location problem (FMCLP) in which travel time between any pair of nodes is considered to be a fuzzy variable. A fuzzy expected value maximization model is designed for such a problem. Moreover, a hybrid algorithm of fuzzy simulation and simulated annealing (SA) is used to solve FMCLP. Some numerical examples are presented, solved and analyzed to show the performance of the proposed algorithm. The results show that the proposed SA finds solutions with objective values no worse than 1.35% below the optimal solution. Furthermore, the simulation-embedded simulated annealing is robust in finding solutions.     

A fuzzy particle swarm optimization algorithm for computer communication network topology design

Particle swarm optimization (PSO) is a powerful optimization technique that has been applied to solve a number of complex optimization problems. One such optimization problem is topology design of distributed local area networks (DLANs). The problem is defined as a multi-objective optimization problem requiring simultaneous optimization of monetary cost, average network delay, hop count between communicating nodes, and reliability under a set of constraints. This paper presents a multi-objective particle swarm optimization algorithm to efficiently solve the DLAN topology design problem. Fuzzy logic is incorporated in the PSO algorithm to handle the multi-objective nature of the problem. Specifically, a recently proposed fuzzy aggregation operator, namely the unified And-Or operator (Khan and Engelbrecht in Inf. Sci. 177: 2692–2711, 2007), is used to aggregate the objectives. The proposed fuzzy PSO (FPSO) algorithm is empirically evaluated through a preliminary sensitivity analysis of the PSO parameters. FPSO is also compared with fuzzy simulated annealing and fuzzy ant colony optimization algorithms. Results suggest that the fuzzy PSO is a suitable algorithm for solving the DLAN topology design problem.     

SLS算法求解平衡正则(k,2r)-CNF公式

可满足性问题的求解算法和结构性质研究是计算机科学中重要问题之一，为寻求某些CNF公式子类问题有效算法或算法改进途径，对公式的结构加以某些限制，其中限定子句长度为恒定常数和变元出现次数是常见的处理方式。研究具有正则结构且每个变元正负出现均衡的结构化公式的可满足性问题求解，其随机生成模型的构建及随机实验测试有助于观察解分布状况。并且，随机局部搜索算法在求解具有一定规则结构CNF公式实例中具有良好效率。本文集中研究平衡正则(k, 2r)-CNF公式的求解问题，即限制每个子句的长度为k，每个变元出现的次数为偶数2r,并且每个变元正负出现的次数在相等情况下的可满足性问题求解。给出BR(n,  k, 2r)模型，以此模型来生成具有特殊结构的平衡正则(k, 2r)-CNF公式实例，利用随机局部搜索算法求解问题。通过限制初始指派的0文字和1文字各占一半且均匀生成，以WalkSAT算法和NSAT算法做实验对比，发现对于平衡正则(k, 2r)-CNF公式，实例具有明显效率。     

用于求解混合车辆路径问题的混合进化算法

文中研究了具有NP难度的混合车辆路径问题(Mixed Capacitated General Routing Problem,MCGRP),其是在基本车辆路径问题(Vehicle Routing Problem,VRP)的基础上通过添加限载容量约束及弧上的用户需求而衍生的。给定一列车辆数不限的车队,使车辆从站点出发向用户提供服务,服务完用户需求后仍返回站点;规定每辆车的总载重不能超过其载重量,且每个需求只能被一辆车服务且仅服务一次。MCGRP旨在求解每辆车的服务路线,使得在满足以上约束条件的情况下所有车辆的旅行消耗之和最小。混合车辆路径问题具有较高的理论价值和实际应用价值,针对该问题提出了一种高效的混合进化算法。该算法采用基于5种邻域算符的变邻域禁忌搜索来提高解的质量,并通过一种基于路径的交叉算符来继承解的优异性,从而有效地加速算法的收敛。在一组共计23个经典算例上的实验结果表明,该混合进化算法在求解混合车辆路径问题时是非常高效的。     

LFA: a linear forward-chaining algorithm for AI production systems

Abstract: The LFA algorithm is a linear forward-chaining algorithm for AI production systems. It finds all the possible solutions for each given problem in a time proportional to the number of rules in a knowledge base, after all the possible evidence about the problem has been given. This paper presents the algorithm in detail. Another new technique, the'rule schema + rule body'representation, which is coupled with the chaining algorithm to support high efficiency of production system interpreters, is also described here.     

一类布尔方程组的可满足性阈值研究*

以一类布尔方程组形式的NP问题可满足性阈值估计为研究目的,通过将高斯消去算法与摘叶算法相结合的方法给出了一种求解该问题的完全算法,并通过不同参数条件下对大量随机实例进行数值实验得到了原问题可满足性阈值的算法估计值。所得研究结果不仅首次给出了该问题的可满足性阈值估计,而且可以作为相关启发式完全算法的设计依据。     

两种改进的模拟退火算法求解大值域约束满足问题

随机约束满足问题的相变现象及求解算法是NP-完全问题的研究热点。RB模型（Revised B）是一个非平凡的随机约束满足问题,它具有精确的可满足性相变现象和极易产生难解实例这两个重要特征。针对RB模型这一类具有大值域的随机约束满足问题,提出了两种基于模拟退火的改进算法即RSA（Revised Simulated Annealing Algorithm）和GSA（Genetic-simulated Annealing Algorithm）。将这两种算法用于求解RB模型的随机实例,数值实验结果表明：在进入相变区域时,RSA和GSA算法依然可以有效地找到随机实例的解,并且在求解效率上明显优于随机游走算法。在接近相变阈值点时,由这两种算法得到的最优解仅使得极少数的约束无法满足。     

求解模糊柔性Job-shop调度问题的多智能体免疫算法

考虑实际纸盆车间调度中模具、机器、操作人员等资源约束,以及加工时间和交货日期的不确定性,建立了批量可变的模糊柔性Job-shop调度问题模型.结合多智能体系统以及免疫信息处理机制,构造了一种求解实际Job-shop调度问题的多智能体免疫算法.该方法通过竞争、自学习、自适应疫苗接种、模拟退火等操作,更新每个智能体在解空间的位置,从而能精确地收敛到全局最优解.纸盆车间调度实例的求解结果验证了该算法的有效性.     

Configuration landscape analysis and backbone guided local search.: Part I: Satisfiability and maximum satisfiability

Boolean satisfiability (SAT) and maximum satisfiability (Max-SAT) are difficult combinatorial problems that have many important real-world applications. In this paper, we first investigate the configuration landscapes of local minima reached by the WalkSAT local search algorithm, one of the most effective algorithms for SAT. A configuration landscape of a set of local minima is their distribution in terms of quality and structural differences relative to an optimal or a reference solution. Our experimental results show that local minima from WalkSAT form large clusters, and their configuration landscapes constitute big valleys, in that high quality local minima typically share large partial structures with optimal solutions. Inspired by this insight into WalkSAT and the previous research on phase transitions and backbones of combinatorial problems, we propose and develop a novel method that exploits the configuration landscapes of such local minima. The new method, termed as backbone-guided search, can be embedded in a local search algorithm, such as WalkSAT, to improve its performance. Our experimental results show that backbone-guided local search is effective on overconstrained random Max-SAT instances. Moreover, on large problem instances from a SAT library (SATLIB), the backbone guided WalkSAT algorithm finds satisfiable solutions more often than WalkSAT on SAT problem instances, and obtains better solutions than WalkSAT on Max-SAT problem instances, improving solution quality by 20% on average.     

差分进化算法在模糊多资源约束联合补货模型中的应用

本文用三角模糊数表示不确定的资金约束,用梯形模糊数表示不确定的存储空间约束,构建了模糊规划联合补货模型,目标函数为最小化订货成本、库存持有成本和运输成本,决策变量为基本补充周期和每种产品的补充周期。通过对变异算子与选择操作进行变化,设计了改进的差分进化算法对模型进行求解,并通过实例证实了模型与算法的科学合理性。     

Setting due dates to minimize the total weighted possibilistic mean value of the weighted earliness-tardiness costs on a single machine

In this paper, it is investigated how to sequence jobs with fuzzy processing times and predict their due dates on a single machine such that the total weighted possibilistic mean value of the weighted earliness-tardiness costs is minimized. First, an optimal polynomial time algorithm is put forward for the scheduling problem when there are no precedence constraints among jobs. Moreover, it is shown that if general precedence constraints are involved, the problem is NP-hard. Then, four reduction rules are proposed to simplify the constraints without changing the optimal schedule. Based on these rules, an optimal polynomial time algorithm is proposed when the precedence constraint is a tree or a collection of trees. Finally, a numerical experiment is given.     

Set Constraints with Intersection

Set constraints are inclusions between expressions denoting sets of trees. The efficiency of their satisfiability test is a central issue in set-based program analysis, their main application domain. We introduce the class of set constraints with intersection (the only operators forming the expressions are constructors and intersection) and show that its satisfiability problem is DEXPTIME-complete. The complexity characterization continues to hold for negative set constraints with intersection (which have positive and negated inclusions). We reduce the satisfiability problem for these constraints to one over the interpretation domain of nonempty sets of trees. Set constraints with intersection over the domain of nonempty sets of trees enjoy the fundamental property of independence of negated conjuncts. This allows us to handle each negated inclusion separately by the entailment algorithm that we devise. We furthermore prove that set constraints with intersection are equivalent to the class of definite set constraints and thereby settle the complexity question of the historically first class for which the decidability question was solved.     

Solving fuzzy multiple objective generalized assignment problems directly via bees algorithm and fuzzy ranking

In this paper, a direct solution approach for solving fuzzy multiple objective generalized assignment problems is proposed. In the problem, the coefficients and right hand side values of the constraints and the objective function coefficients are defined as fuzzy numbers. The addressed problem also has a multiple objective structure where the goals are determined so as to minimize the total cost and the imbalance between the workload of the agents. The direct solution approach utilizes the fuzzy ranking methods to rank the objective function values and to determine the feasibility of the constraints within a metaheuristic search algorithm, known as bees algorithm. Different fuzzy ranking methods, namely signed distance, integral value and area based approach are used in bees algorithm. For the computational study, the effects of these fuzzy ranking methods on the quality of the solutions are also analyzed.     

一类可分离SAT问题的O(1.890n)精确算法

布尔可满足性问题（SAT）是指对于给定的布尔公式,是否存在一个可满足的真值指派.这是第1个被证明的NP完全问题,一般认为不存在多项式时间算法,除非P=NP.学者们大都研究了子句长度不超过k的SAT问题（k-SAT）,从全局搜索到局部搜索,给出了大量的相对有效算法,包括随机算法和确定算法.目前,最好算法的时间复杂度不超过O（（2-2/k）ⁿ）,当k=3时,最好算法时间复杂度为O（1.308ⁿ）.而对于更一般的与子句长度k无关的SAT问题,很少有文献涉及.引入了一类可分离SAT问题,即3-正则可分离可满足性问题（3-RSSAT）,证明了3-RSSAT是NP完全问题,给出了一般SAT问题3-正则可分离性的O（1.890ⁿ）判定算法.然后,利用矩阵相乘算法的研究成果,给出了3-RSSAT问题的O（1.890ⁿ）精确算法,该算法与子句长度无关.     

An approximate algorithm for estimating treatment lags from right censored data

The problem of likelihood estimate of a function, given limited data and a set of constraints, finds many practical applications. One of them is the lag function estimation for treatment effects in clinical trials. However, searching for the global optimum in such problems often turns out to be prohibitively complex. In this paper, we present an algorithm that can be effectively used to approximate such solutions. This algorithm modifies standard genetic algorithms, which model the natural processes of information inheritance and selective pressure. The most important modifications deal with the complex strong constraints imposed on the sought solution. We present few experiments with a simplified version of the problem and discuss possible future extensions that relax the restrictions.