• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>PRICAI'98 : Topics in artificial intelligence >SL Method for Computing a Near-Optimal Solution Using Linear and Non-linear Programming in Cost-Based Hypothetical Reasoning
【24h】

SL Method for Computing a Near-Optimal Solution Using Linear and Non-linear Programming in Cost-Based Hypothetical Reasoning

机译：基于成本的假设推理中使用线性和非线性规划计算近似最优解的SL方法

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Hypothetical reasoning is an important framework for knowledge-based systems because it is theoretically founded and it is useful for many practical problems. Since its inference time grows exponentially with respect to problem size, its efficiency becomes the most crucial problem when applying it to practical problems. Some approximate solution methods have been proposed for computing cost-based hypothetical reasoning problems efficiently; however, for humans their mechanisms are complex to understand. In this paper, we present an understandable efficient method called SL (slide-down and lift-up) method which uses a linear programming technique, namely simplex method, for determining an initial search point and a non-linear programming technique for efficiently finding a near-optimal 0-1 solution. To escape from trapping into local optima, we have developed a new local handler which systematically fixes a variable to a locally consistent value when a locally optimal point is detected. This SL method can find a near-optimal solution for cost-based hypothetical reasoning in polynomial time with respect to problem size. Since the behavior of the SL method is illustrated visually, the simple inference mechanism of the method can be easily understood.
机译：假设推理是基于知识的系统的重要框架，因为它是理论上建立起来的，并且对于许多实际问题很有用。由于推理时间相对于问题的大小呈指数增长，因此将其应用于实际问题时，其效率成为最关键的问题。为了有效地计算基于成本的假设推理问题，已经提出了一些近似的解决方法。但是，对于人类来说，其机制很难理解。在本文中，我们提出了一种可理解的有效方法，称为SL（滑降法）方法，该方法使用线性规划技术（即单纯形法）来确定初始搜索点，并使用非线性规划技术来有效地找到目标接近最佳的0-1解。为了避免陷入局部最优，我们开发了一种新的局部处理程序，当检测到局部最优点时，该系统将变量系统地固定为局部一致的值。这种SL方法可以针对问题大小在多项式时间内基于成本的假设推理中找到最佳解决方案。由于从视觉上说明了SL方法的行为，因此可以轻松理解该方法的简单推断机制。

著录项

  • 来源
  • 会议地点 Singapore(SG);Singapore(SG)
  • 作者

    Mitsuru Ishizuka; Yutaka Matsuo;

  • 作者单位

    Dept. of Information and Communication Eng. School of Engineering, University of Tokyo 7-3-1, Hongo, Bunkyo-ku, Tokyo 113-8656, Japan;

    Dept. of Information and Communication Eng. School of Engineering, University of Tokyo 7-3-1, Hongo, Bunkyo-ku, Tokyo 113-8656, Japan;

  • 会议组织
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类 自动化系统理论;
  • 关键词

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号