Memory intensive AND/OR search for combinatorial optimization in graphical models

In this paper we explore the impact of caching during search in the context of the recent framework of AND/OR search in graphical models. Specifically, we extend the depth-first AND/OR Branch-and-Bound tree search algorithm to explore an AND/OR search graph by equipping it with an adaptive caching scheme similar to good and no-good recording. Furthermore, we present best-first search algorithms for traversing the same underlying AND/OR search graph and compare both algorithms empirically. We focus on two common optimization problems in graphical models: finding the Most Probable Explanation (MPE) in belief networks and solving Weighted CSPs (WCSP). In an extensive empirical evaluation we demonstrate conclusively the superiority of the memory intensive AND/OR search algorithms on a variety of benchmarks.     

AND/OR search spaces for graphical models

The paper introduces an AND/OR search space perspective for graphical models that include probabilistic networks (directed or undirected) and constraint networks. In contrast to the traditional (OR) search space view, the AND/OR search tree displays some of the independencies present in the graphical model explicitly and may sometimes reduce the search space exponentially. Indeed, most algorithmic advances in search-based constraint processing and probabilistic inference can be viewed as searching an AND/OR search tree or graph. Familiar parameters such as the depth of a spanning tree, treewidth and pathwidth are shown to play a key role in characterizing the effect of AND/OR search graphs vs. the traditional OR search graphs. We compare memory intensive AND/OR graph search with inference methods, and place various existing algorithms within the AND/OR search space.     

Evaluating the impact of AND/OR search on 0-1 integer linear programming

AND/OR search spaces accommodate advanced algorithmic schemes for graphical models which can exploit the structure of the model. We extend and evaluate the depth-first and best-first AND/OR search algorithms to solving 0-1 Integer Linear Programs (0-1 ILP) within this framework. We also include a class of dynamic variable ordering heuristics while exploring an AND/OR search tree for 0-1 ILPs. We demonstrate the effectiveness of these search algorithms on a variety of benchmarks, including real-world combinatorial auctions, random uncapacitated warehouse location problems and MAX-SAT instances.     

监督学习模型指导的函数级编译优化参数选择方法研究

基于机器学习的迭代编译方法可以在对新程序进行迭代编译时,有效预测新程序的最佳优化参数组合。现有方法在模型训练过程中存在优化参数组合搜索效率较低、程序特征表示不恰当、预测精度不高的问题。因此,基于机器学习的迭代编译方法是当前迭代编译领域内的一个研究热点,其研究挑战在于学习算法选择、优化参数搜索以及程序特征表示等问题。基于监督学习技术,提出了一种程序优化参数预测方法。该方法首先通过约束多目标粒子群算法对优化参数空间进行搜索,找到样本函数的最佳优化参数;然后,通过动静结合的程序特征表示技术,对函数特征进行抽取;最后,通过由函数特征和优化参数形成的样本构建监督学习模型,对新程序的优化参数进行预测。分别采用k近邻法和softmax回归建立统计模型,实验结果表明,新方法在NPB测试集和大型科学计算程序上实现了较好的预测性能。     

Divergent exploration in design with a dynamic multiobjective optimization formulation

Formulation space exploration is a new strategy for multiobjective optimization that facilitates both divergent exploration and convergent optimization during the early stages of design. The formulation space is the union of all variable and design objective spaces identified by the designer as being valid and pragmatic problem formulations. By extending a computational search into the formulation space, the solution to an optimization problem is no longer predefined by any single problem formulation, as it is with traditional optimization methods. Instead, a designer is free to change, modify, and update design objectives, variables, and constraints and explore design alternatives without requiring a concrete understanding of the design problem a priori. To facilitate this process, we introduce a new vector/matrix-based definition for multiobjective optimization problems, which is dynamic in nature and easily modified. Additionally, we provide a set of exploration metrics to help guide designers while exploring the formulation space. Finally, we provide an example to illustrate the use of this new, dynamic approach to multiobjective optimization.     

Incremental Design of a Data Warehouse

A data warehouse (DW) can be seen as a set of materialized views defined over remote base relations. When a query is posed, it is evaluated locally, using the materialized views, without accessing the original information sources. The DWs are dynamic entities that evolve continuously over time. As time passes, new queries need to be answered by them. Some of these queries can be answered using exclusively the materialized views. In general though new views need to be added to the DW.In this paper we investigate the problem of incrementally designing a DW when new queries need to be answered and possibly extra space is allocated for view materialization. Based on an AND/OR dag representation of multiple queries, we model the problem as a state space search problem. We design incremental algorithms for selecting a set of new views to additionally materialize in the DW that: (a) fits in the extra space, (b) allows a complete rewriting of the new queries over the materialized views, and (c) minimizes the combined new query evaluation and new view maintenance cost. Finally, we discuss methods for pruning the search space so that efficiency is improved.     

Dynamic Grover search: applications in recommendation systems and optimization problems

In the recent years, we have seen that Grover search algorithm (Proceedings, 28th annual ACM symposium on the theory of computing, pp. 212–219, 1996) by using quantum parallelism has revolutionized the field of solving huge class of NP problems in comparisons to classical systems. In this work, we explore the idea of extending Grover search algorithm to approximate algorithms. Here we try to analyze the applicability of Grover search to process an unstructured database with a dynamic selection function in contrast to the static selection function used in the original work (Grover in Proceedings, 28th annual ACM symposium on the theory of computing, pp. 212–219, 1996). We show that this alteration facilitates us to extend the application of Grover search to the field of randomized search algorithms. Further, we use the dynamic Grover search algorithm to define the goals for a recommendation system based on which we propose a recommendation algorithm which uses binomial similarity distribution space giving us a quadratic speedup over traditional classical unstructured recommendation systems. Finally, we see how dynamic Grover search can be used to tackle a wide range of optimization problems where we improve complexity over existing optimization algorithms.     

基于OBDD的含圈与或图搜索算法研究*

与或图搜索是人工智能领域一项一定范围内通用的问题求解技术。基于传统数据结构的与或图表示技术极大地限制了与或图搜索算法可求解问题的规模。本文在Mahanti等提出的含圈与或图理论框架基础上,给出了基于OBDD的含圈与或图符号表示方法,并提出了一种求解含圈与或图最小代价解图的符号搜索算法。实验结果表明：该算法在处理大规模含圈与或图时具有明显优势。     

On minimization of the number of branches in branch-and-bound algorithms for the maximum clique problem

When searching for a maximum clique in a graph G, branch-and-bound algorithms in the literature usually focus on the minimization of the number of branches generated at each search tree node. We call dynamic strategy this minimization without any constraint, because it induces a dynamic vertex ordering in G during the search. In this paper, we introduce a static strategy that minimizes the number of branches subject to the constraint that a static vertex ordering in G must be kept during the search. We analyze the two strategies and show that they are complementary. From this complementarity, we propose a new algorithm, called MoMC, that combines the strengths of the two strategies into a single algorithm. The reported experimental results show that MoMC is generally better than the algorithms implementing a single strategy.     

Framework for computationally efficient optimal crop and water allocation using ant colony optimization

A general optimization framework is introduced with the overall goal of reducing search space size and increasing the computational efficiency of evolutionary algorithm application to optimal crop and water allocation. The framework achieves this goal by representing the problem in the form of a decision tree, including dynamic decision variable option (DDVO) adjustment during the optimization process and using ant colony optimization (ACO) as the optimization engine. A case study from literature is considered to evaluate the utility of the framework. The results indicate that the proposed ACO-DDVO approach is able to find better solutions than those previously identified using linear programming. Furthermore, ACO-DDVO consistently outperforms an ACO algorithm using static decision variable options and penalty functions in terms of solution quality and computational efficiency. The considerable reduction in computational effort achieved by ACO-DDVO should be a major advantage in the optimization of real-world problems using complex crop simulation models.     

Graphical models for optimal power flow

Optimal power flow (OPF) is the central optimization problem in electric power grids. Although solved routinely in the course of power grid operations, it is known to be strongly NP-hard in general, and weakly NP-hard over tree networks. In this paper, we formulate the optimal power flow problem over tree networks as an inference problem over a tree-structured graphical model where the nodal variables are low-dimensional vectors. We adapt the standard dynamic programming algorithm for inference over a tree-structured graphical model to the OPF problem. Combining this with an interval discretization of the nodal variables, we develop an approximation algorithm for the OPF problem. Further, we use techniques from constraint programming (CP) to perform interval computations and adaptive bound propagation to obtain practically efficient algorithms. Compared to previous algorithms that solve OPF with optimality guarantees using convex relaxations, our approach is able to work for arbitrary tree-structured distribution networks and handle mixed-integer optimization problems. Further, it can be implemented in a distributed message-passing fashion that is scalable and is suitable for “smart grid” applications like control of distributed energy resources. Numerical evaluations on several benchmark networks show that practical OPF problems can be solved effectively using this approach.     

Design of graph-based evolutionary algorithms: a case study for chemical process networks

This paper describes the adaptation of evolutionary algorithms (EAs) to the structural optimization of chemical engineering plants, using rigorous process simulation combined with realistic costing procedures to calculate target function values. To represent chemical engineering plants, a network representation with typed vertices and variable structure will be introduced. For this representation, we introduce a technique on how to create problem specific search operators and apply them in stochastic optimization procedures. The applicability of the approach is demonstrated by a reference example. The design of the algorithms will be oriented at the systematic framework of metric-based evolutionary algorithms (MBEAs). MBEAs are a special class of evolutionary algorithms, fulfilling certain guidelines for the design of search operators, whose benefits have been proven in theory and practice. MBEAs rely upon a suitable definition of a metric on the search space. The definition of a metric for the graph representation will be one of the main issues discussed in this paper. Although this article deals with the problem domain of chemical plant optimization, the algorithmic design can be easily transferred to similar network optimization problems. A useful distance measure for variable dimensionality search spaces is suggested.     

Dynamic combinatorial optimisation problems: an analysis of the subset sum problem

The field of evolutionary computation has traditionally focused on static optimisation problems. Recently, many new approaches have been proposed that adapt traditional evolutionary algorithms to the dynamic domain to deal with the task of tracking high-quality solutions as the search space changes over time. These novel algorithms are subsequently evaluated on a wide range of different optimisation problems, including well-specified benchmark generators. However, due to a lack of theoretical results, as well as a general lack of references to actual real-world scenarios, it is not entirely clear whether these benchmarks capture any of the characteristics found in NP-hard dynamic optimisation problems. In this paper, we extensively analyse the properties of the NP-hard (dynamic) subset sum problem. In particular, we highlight the correlation between the dynamic parameters of the problem and the resulting movement of the global optimum. It is shown by empirical means that the degree to which the global optimum moves in response to the underlying dynamics is correlated only in specific cases. Furthermore, the role of the representation used to encode the problem, as well as the impact of the formulation of the objective function on the dynamics are also discussed.     

基于改进多嵌入空间的实时语义数据流推理

将语义数据流处理引擎与知识图谱嵌入表示学习相结合,可以有效提高实时数据流推理查询性能,但是现有的知识表示学习模型更多关注静态知识图谱嵌入,忽略了知识图谱的动态特性,导致难以应用于实时动态语义数据流推理任务。为了使知识表示学习模型适应知识图谱的在线更新并能够应用于语义数据流引擎,建立一种基于改进多嵌入空间的动态知识图谱嵌入模型PUKALE。针对传递闭包等复杂推理场景,提出3种嵌入空间生成算法。为了在进行增量更新时更合理地选择嵌入空间,设计2种嵌入空间选择算法。基于上述算法实现PUKALE模型,并将其嵌入数据流推理引擎CSPARQL-engine中,以实现实时语义数据流推理查询。实验结果表明,与传统的CSPARQL和KALE推理相比,PUKALE模型的推理查询时间分别约降低85%和93%,其在支持动态图谱嵌入的同时能够提升实时语义数据流推理准确率。     

Disseminating streaming data in a dynamic environment: an adaptive and cost-based approach

In a distributed stream processing system, streaming data are continuously disseminated from the sources to the distributed processing servers. To enhance the dissemination efficiency, these servers are typically organized into one or more dissemination trees. In this paper, we focus on the problem of constructing dissemination trees to minimize the average loss of fidelity of the system. We observe that existing heuristic-based approaches can only explore a limited solution space and hence may lead to sub-optimal solutions. On the contrary, we propose an adaptive and cost-based approach. Our cost model takes into account both the processing cost and the communication cost. Furthermore, as a distributed stream processing system is vulnerable to inaccurate statistics, runtime fluctuations of data characteristics, server workloads, and network conditions, we have designed our scheme to be adaptive to these situations: an operational dissemination tree may be incrementally transformed to a more cost-effective one. Our adaptive strategy employs distributed decisions made by the distributed servers independently based on localized statistics collected by each server at runtime. For a relatively static environment, we also propose two static tree construction algorithms relying on apriori system statistics. These static trees can also be used as initial trees in a dynamic environment. We apply our schemes to both single- and multi-object dissemination. Our extensive performance study shows that the adaptive mechanisms are effective in a dynamic context and the proposed static tree construction algorithms perform close to optimal in a static environment.     

Destination Driven Motion Planning via Obstacle Motion Prediction and Multi-State Path Repair

This paper presents a real-time navigating system named Destination Driven Navigator for a mobile robot operating in unstructured static and dynamic environments. We have designed a new obstacle representation method named Cross-Line Obstacle Representation and a new concept work space to reduce the robot's search space and the environment storage cost, an Adapted Regression Model to predict dynamic obstacles' motion, Multi-State Path Repair rules to quickly translate an infeasible path into feasible one, and the path-planning algorithm to generate a path. A high-level Destination Driven Navigator uses these methods, models and algorithms to guide a mobile robot traveling in various environments while avoiding static and dynamic obstacles. A group of experiments has been conducted. The results exhibit that the Destination Driven Navigator is a powerful and effective paradigm for robot motion planning and obstacle avoidance.     

U-curve: A branch-and-bound optimization algorithm for U-shaped cost functions on Boolean lattices applied to the feature selection problem

This paper presents the formulation of a combinatorial optimization problem with the following characteristics: (i) the search space is the power set of a finite set structured as a Boolean lattice; (ii) the cost function forms a U-shaped curve when applied to any lattice chain. This formulation applies for feature selection in the context of pattern recognition. The known approaches for this problem are branch-and-bound algorithms and heuristics that explore partially the search space. Branch-and-bound algorithms are equivalent to the full search, while heuristics are not. This paper presents a branch-and-bound algorithm that differs from the others known by exploring the lattice structure and the U-shaped chain curves of the search space. The main contribution of this paper is the architecture of this algorithm that is based on the representation and exploration of the search space by new lattice properties proven here. Several experiments, with well known public data, indicate the superiority of the proposed method to the sequential floating forward selection (SFFS), which is a popular heuristic that gives good results in very short computational time. In all experiments, the proposed method got better or equal results in similar or even smaller computational time.     

概率图模型推理方法的研究进展

近年来概率图模型已成为不确定性推理的研究热点,在人工智能、机器学习与计算机视觉等领域有广阔的应用前景.根据网络结构与查询问题类型的不同,系统地综述了概率图模型的推理算法.首先讨论了贝叶斯网络与马尔可夫网络中解决概率查询问题的精确推理算法与近似推理算法,其中主要介绍精确推理中的VE算法、递归约束算法和团树算法,以及近似推理中的变分近似推理和抽样近似推理算法,并给出了解决MAP查询问题的常用推理算法;然后分别针对混合网络的连续与混合情况阐述其推理算法,并分析了暂态网络的精确推理、近似推理以及混合情况下的推理;最后指出了概率图模型推理方法未来的研究方向.     

ACS算法在矩形件优化排料中的应用

矩形件优化排料是一类具有NP完全难度的组合优化问题。有关的优化问题可用与或树来描述,这样就把矩形件优化排料问题变换为寻找一棵面积比率最大的二叉树。用ACS算法实现这种树搜索,是把一定数量的人工蚂蚁分布在与或树的根节点,人工蚂蚁间通过使用信息素相互交流,完成从与或树到二叉树的选择,从而得到矩形件优化排料问题的优化解。     

Rollout strategies for sequential fault diagnosis

Test sequencing is a binary identification problem wherein one needs to develop a minimal expected cost testing procedure to determine which one of a finite number of possible failure sources, if any, is present. The problem can be solved optimally using dynamic programming or AND/OR graph search methods (AO/sup */, CF, and HS). However, for large systems, the associated computation with dynamic programming or AND/OR graph search methods is substantial, due to the rapidly increasing number of OR nodes (denoting ambiguity states) and AND nodes (denoting tests) in the search graph. In order to overcome the computational explosion, the one-step or multistep lookahead heuristic algorithms have been developed to solve the test sequencing problem. In this paper, we propose to apply rollout strategies, which can be combined with the one-step or multistep lookahead heuristic algorithms, in a computationally more efficient manner than the optimal strategies, to obtain solutions superior to those using the one-step or multistep lookahead heuristic algorithms. The rollout strategies are illustrated and tested using a range of real-world systems. We show computational results, which suggest that the information-heuristic based rollout policies are significantly better than other rollout policies based on Huffman coding and entropy.