检索结果-内蒙古大学图书馆

An SVM-Based Prediction Method for Solving SAT Problems

Chinese Journal of Electronics 2019年第2期28卷 246-252页

作者： HUANG Shaobin LI Ya LI Yanmei College of Computer Science and Technology Harbin Engineering University

We show how Support vector machines(SVM) can be applied to the Satisfiability(SAT) problem and how their prediction results can be naturally applied to both incomplete and complete SAT solvers. SVM is used for the classification of the variables in the SAT problem and the classification results are the assignment of the variables. And we also present empirical results of applying SVM to instances of the SAT problem from the Center for Discrete Mathematics and Theoretical Computer Science(DIMACS) archive and compare them against the results of other incomplete and complete algorithms for the SAT problem.

关键词： Support vector machines Satisfiability Complete algorithms incomplete algorithms

来源：评论

学校读者我要写书评

暂无评论

Applying max-sum to teams of mobile sensing agents

引用

ENGINEERING APPLICATIONS OF ARTIFICIAL INTELLIGENCE 2018年 71卷 87-99页

作者： Yedidsion, Harel Zivan, Roie Farinelli, Alessandro Ben Gurion Univ Negev Ind Engn & Management Dept Beer Sheva Israel Univ Verona Comp Sci Dept Verona Italy

Multi-agent applications that include teams of mobile sensing agents are challenging since they are inherently dynamic and a single movement of a mobile sensor can change the problem that the entire team is facing. A variation of the Distributed Constraint Optimization model for Mobile Sensor Teams (DCOP_MST) was previously adjusted to represent such problems along with local search algorithms that were enhanced with exploration methods. This paper considers the use of the Max-sum algorithm for solving problems of deploying a mobile sensor team in an unknown environment to track and monitor points of interest (targets), represented by the DCOPMST model. The DCOP_MST model allows the representation of different functions for aggregating the joint coverage of targets by multiple sensors. The use of different functions has a dramatic effect on the complexity of the Max-sum algorithm. When using cardinality functions, Max-sum can be performed efficiently regardless of the arity of constraints. When Max-sum is used to solve applications that require other (more complex) aggregation functions, its complexity is exponential in the arity of the constraints and thus, its usefulness is limited. In this paper we investigate the performance of the Max-sum algorithm on two implementations of the DCOPMST model. Each implementation considers a different joint credibility function for determining the coverage for each target, with respect to the locations and the credibility of agents. In the first, the coverage is calculated according to the number of agents that are located within sensing range from the target. This function can be calculated efficiently. The second takes the angle between the lines of sight of different agents to a target into consideration. The larger the difference in the angle between the lines of sight, the higher the coverage efficiency. We analyze the challenges in adjusting the Max-sum algorithm in both scenarios and propose enhancements of the algorithm

关键词： Distributed constraint optimization incomplete algorithms GDL Max-sum Multi-agent systems Exploration Mobile sensor networks

来源：评论

学校读者我要写书评

暂无评论

Explorative Max-sum for Teams of Mobile Sensing Agents 13

Explorative Max-sum for Teams of Mobile Sensing Agents

引用

International Conference on Autonomous Agents and Multiagent Systems (AAMAS)

作者： Yedidsion, Harel Zivan, Roie Farinelli, Allesandro Ben Gurion Univ Negev Dept Ind Engn & Management Beer Sheva Israel Univ Verona Dept Comp Sci Verona Italy

ISBN: (纸本)9781450327381

Multi-agent applications that include teams of mobile sensing agents are challenging since they are inherently dynamic and a single movement of a mobile sensor can change the problem that the whole team is facing. While agents select their positions with respect to the information available to them in their local environment, by moving to a different location they can reveal new information, e.g., targets, which they were not aware of before. Thus, exploration is required for such information to be revealed. A variation of the DCOP model (DCOP_MST) was previously adjusted to represent such problems along with local search algorithms that were enhanced with exploration methods. In this paper we design an explorative version of Max-sum for solving DCOP_MST, which is based on an iterative process where, at each iteration, agents generate and solve a specific problem instance. We demonstrate that this basic algorithm (Max-sum_MST) converges faster than other standard local search algorithms that were adjusted to solve DCOP_MSTs, however, its exploitive nature makes it inferior to explorative local search algorithms. Thus, we designed exploration methods that when combined with basic Max-sum_MST, significantly outperform the existing explorative local search algorithms. Moreover, the best performing method we propose also eliminates the exponential time complexity of Max-sum by bounding the number of agents involved in each constraint.

关键词： DCOP incomplete algorithms GDL

来源：评论

学校读者我要写书评

暂无评论

Constraint-Based Techniques in Stochastic Local Search MaxSAT Solving 25th

Constraint-Based Techniques in Stochastic Local Search MaxSA...

引用

25th International Conference on the Principles and Practice of Constraint Programming (CP)

作者： Guerreiro, Andreia P. Terra-Neves, Miguel Lynce, Ines Figueira, Jose Rui Manquinho, Vasco Univ Lisbon Inst Super Tecn INESC ID Lisbon Portugal OutSystems Lisbon Portugal Univ Lisbon Inst Super Tecn CEG IST Lisbon Portugal

ISBN: (纸本)9783030300487

The recent improvements in solving Maximum Satisfiability (MaxSAT) problems has allowed the usage of MaxSAT in several application domains. However, it has been observed that finding an optimal solution in a reasonable amount of time remains a challenge. Moreover, in many applications it is enough to provide a good approximation of the optimum. Recently, new local search algorithms have been shown to be successful in approximating the optimum in MaxSAT problems. Nevertheless, these local search algorithms fail in finding feasible solutions to highly constrained instances. In this paper, we propose two constraint-based techniques for improving local search MaxSAT solvers. Firstly, an unsatisfiability-based algorithm is used to guide the local search solver into the feasible region of the search space. Secondly, given a partial assignment, we perform Minimal Correction Subsets (MCS) enumeration in order to improve upon the best solution found by the local search solver. Experimental results using a large set of instances from the MaxSAT evaluation 2018 show the effectiveness of our approach.

关键词： Maximum Satisfiability Local search incomplete algorithms

来源：评论

学校读者我要写书评

暂无评论

Max/Min-sum Distributed Constraint Optimization through Value Propagation on an Alternating DAG 12

Max/Min-sum Distributed Constraint Optimization through Valu...

引用

International Conference on Autonomous Agents and Multiagent Systems

作者： Roie Zivan Hilla Peled Ben Gurion University Beer-Sheva Israel

ISBN: (纸本)9780981738116

Distributed Constraint Optimization Problems (DCOPs) are NPhard and therefore the number of studies that consider incomplete algorithms for solving them is growing. Specifically, the Max-sum algorithm has drawn attention in recent years and has been applied to a number of realistic applications. Unfortunately, in many cases Max-sum does not produce high quality solutions. More specifically, when problems include cycles of various sizes in the factor graph upon which Max-sum performs, the algorithm does not converge and the states that it visits are of low quality. In this paper we advance the research on incomplete algorithms for DCOPs by: (1) Proposing a version of the Max-sum algorithm that operates on an alternating directed acyclic graph (Maxsum_AD), which guarantees convergence in linear time. (2) Identifying major weaknesses of Max-sum and Max-sum_AD that cause inconsistent costs/utilities to be propagated and affect the assignment selection. (3) Solving the identified problems by introducing value propagation to Max-sum_AD. Our empirical study reveals a large improvement in the quality of the solutions produced by Max-sum_AD with value propagation (VP), when solving problems which include cycles, compared with the solutions produced by the standard Max-sum algorithm, Bounded Max-sum and Maxsum_AD with no value propagation.

关键词： DCOP incomplete algorithms GDL

来源：评论

学校读者我要写书评

暂无评论

Explorative Max-sum for Teams of Mobile Sensing Agents 14

Explorative Max-sum for Teams of Mobile Sensing Agents

引用

International Conference on Autonomous Agents and Multiagent Systems

作者： Harel Yedidsion Roie Zivan Allesandro Farinelli Dept. of Industrial Engineering and Management Ben Gurion University Dept. of Computer Science University of Verona

ISBN: (纸本)9781634391313

Multi-agent applications that include teams of mobile sensing agents are challenging since they are inherently dynamic and a single movement of a mobile sensor can change the problem that the whole team is facing. While agents select their positions with respect to the information available to them in their local environment, by moving to a different location they can reveal new information, e.g., targets, which they were not aware of before. Thus, exploration is required for such information to be revealed. A variation of the DCOP model (DCOP_MST) was previously adjusted to represent such problems along with local search algorithms that were enhanced with exploration methods. In this paper we design an explorative version of Max-sum for solving DCOP_MST, which is based on an iterative process where, at each iteration, agents generate and solve a specific problem instance. We demonstrate that this basic algorithm (Max-sum_MST) converges faster than other standard local search algorithms that were adjusted to solve DCOP_MSTs, however, its exploitive nature makes it inferior to explorative local search algorithms. Thus, we designed exploration methods that when combined with basic Max-sum_MST, significantly outperform the existing explorative local search algorithms. Moreover, the best performing method we propose also eliminates the exponential time complexity of Maxsum by bounding the number of agents involved in each constraint.

关键词： algorithms Experimentation DCOP incomplete algorithms GDL SEARCHING ALGORITHM experimentation Teams Agents algorithms Mobile Exploration complexity classes Iterative Process

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：