A model synthesis method based on single building facade

In this paper we present a convenient building model synthesis method. It aims at obtaining new user-defined building models through seamless stitching after synthesis of each single building facade. During the optimization process of synthesis of each single building facade, we utilize model structure analysis method to obtain the smallest structural units and the constraint graph among them, transforming complicated three-dimension (3D) synthesis problem into two-dimension (2D) constraint graph synthesis problem. Then we construct a global energy function and minimize it through iterative optimization with expectation maximization algorithm, in order to obtain new objective constraint graph. During stitching process, in order to get complete model synthesis result, we replace objective constraint graph with structural unit to transform synthesis back into 3D space, and achieve automatic stitching between neighboring construction units and neighboring facades by using the connection point sets of structural units in original samples. The experiment results demonstrate our method can generate building models of absolutely different styles quickly and efficiently based on single or multiple samples, while maintaining the continuity and visual integrity of result models well.     

大规模图推荐模型的快速优化机制

推荐系统在帮助用户从海量数据中发现自己感兴趣的信息时能起到重要作用。近些年来,深度学习在计算机视觉等诸多领域卓有成效,吸引了越来越多推荐系统领域学者的关注。推荐系统结合图神经网络等深度学习方法取得了令人瞩目的效果。然而,现存的许多方法主要关注在如何用深度学习模型来设计推荐系统的架构,却少有工作关注推荐系统的优化框架,尤其是从优化框架方面提升推荐系统的训练效率。因此随着模型的日益复杂,训练模型的时间代价也越来越大。
本工作中,我们试图从优化框架方面提升大规模图推荐模型的训练效率。推荐系统中最主流的模型优化框架为贝叶斯个性化排序（Bayesian personalized ranking,BPR）,其潜在假设是目标用户对于已交互的物品的喜好程度强于未交互的物品,然后通过最大化用户对感兴趣物品和不感兴趣物品的评分差来实现。然而,BPR优化器的瓶颈在于模型参数的学习效率低下,在计算资源有限,且用户的兴趣要具有时效性等现实因素下,极大限制了主流图推荐模型在工业场景中的应用。究其原因,BPR优化器需要每个训练样本对单独经过非线性激活函数,这样元素级别的运算无法转化为矩阵操作等并行计算的形式,进而未能发挥GPU的并行加速性能。受平方误差损失函数在结合推荐任务时,对矩阵化操作较为友好的启发,我们设计了一种快速非采样优化器FGL,可广泛适用于主流图推荐模型。经过一系列理论推导与转换,FGL有效规避了损失函数中复杂度较高的计算项,极大提升了模型的训练效率。以经典矩阵分解模型和最先进的图神经网络模型LightGCN为代表,本文在四个基准数据集上进行了大量的实验。实验结果表明,FGL优化器在保证推荐准确度下,其训练效率相比于BPR获得了数量级层面的加速,表明FGL在现实工业场景中具有很大的应用潜力。     

一种Spark环境下的高效率大规模图数据处理机制

本文针对现有的图处理和图管理框架存在的效率低下以及数据存储结构等问题,提出了一种适合于大规模图数据处理机制。首先分析了目前的一些图处理模型以及图存储框架的优势与存在的不足。其次,通过对分布式计算的特性分析采取适合大规模图的分割算法、数据抽取的优化以及缓存、计算层与持久层结合机制三方面来设计本文的图数据处理框架。最后通过PageRank和SSSP算法来设计实验与MapReduce框架和采用HDFS作持久层的Spark框架做性能对比。实验证明本文提出的框架要比MapReduce框架快90倍,比采用HDFS作持久层的Spark框架快2倍,能够满足高效率图数据处理的应用前景。     

卷烟生产线柔性优化调度模型研究

Through analyzing technological process of cigarette producing line and utilizing the basic idea of modern graph theory, the connected network system based on continuous material flow is drawn from cigarette producing line. The thought of flexible optimization schedule is proposed and the optimization schedule models of cigarette producing line are created. Then their visualized example is given. These optimization schedule models have already been used for actual cigarette producing schedule and they have direction meaning for instructing manager at producing ground to carry on optimization schedule.     

Graph products for configuration processing of space structures

In this paper four undirected graph products and four directed graph products are presented for the formation of structural models. The undirected products are extensively used in graph theory and combinatorial optimization, however, the directed products defined in this paper are more suitable for the formation of practical structural models. Here, the directed and undirected products are employed for the configuration processing of space structures. This application can easily be extended to the formation of finite element models.     

Belief propagation algorithms for finding the probable configurations over factor graph models

In this article, we study the belief propagation algorithms for solving the multiple probable configurations (MPC) problem over graphical models. Based on the loopy max-product methodology, we first develop an iterative belief propagation mechanism (IBPM), which aims to find the most probable configurations facing with the existence of multiple solutions. In applications ranging from low-density parity-check codes to combinatorial optimization one would like to find not just the best configurations but rather than the summary of all possible explanations. Not only can this problem be solved by our proposed loopy message-passing algorithm (LMPA), we also prove that, for tree factor graph models, this LMPA guarantees fast convergence. Moveover, we subsequently present a low-complexity approach to simplifying the message integration operation throughout the whole belief propagation circulation. Simulations built on various settings demonstrate that both IBPM and LMPA can accurately and rapidly approximate the MPC in acyclic graph with hundreds of variables.     

基于图论的高校排考算法

提出了一种基于图论的考场安排算法及一系列优化策略.考场安排足考务管理活动的重要环节,考场安排结果的优劣直接决定了考务活动能否正常顺利的进行.对高校的考场安排问题进行了分析、抽象,通过建立静态冲突图将时间安排转化为图论的图着色问题来解决排考时间的冲突问题并在此基础上提出了多种对结果的优化策略以保证排考结果的合理性.通过在...     

Aesthetics-based Graph Layout for Human Consumption

Automatic graph layout is an important and long-studied problem. The basic straight-edge graph layout problem is to find spatial positions for the nodes of an input graph that maximize some measure of desirability. When graph layout is intended for human consumption, we call this measure of desirability an aesthetic. We seek an algorithm that produces graph layouts of high aesthetic quality not only for general graphs, but also for specific classes of graphs, such as trees and directed acyclic graphs. The Aesthetic Graph Layout (AGLO) approach described in this paper models graph layout as a multiobjective optimization problem, where the value of a layout is determined by multiple user-controlled layout aesthetics. The current AGLO algorithm combines the power and flexibility of the simulated annealing approach of Davidson and Harel (1989) with the relative speed of the method of Fruchterman and Reingold (1991). In addition, it is more general, and incorporates several new layout aesthetics to support new layout styles. Using these aesthetics, we are able to produce pleasing displays for graphs on which these other methods flounder.     

Protein Folding in Simplified Models With Estimation of Distribution Algorithms

Simplified lattice models have played an important role in protein structure prediction and protein folding problems. These models can be useful for an initial approximation of the protein structure, and for the investigation of the dynamics that govern the protein folding process. Estimation of distribution algorithms (EDAs) are efficient evolutionary algorithms that can learn and exploit the search space regularities in the form of probabilistic dependencies. This paper introduces the application of different variants of EDAs to the solution of the protein structure prediction problem in simplified models, and proposes their use as a simulation tool for the analysis of the protein folding process. We develop new ideas for the application of EDAs to the bidimensional and tridimensional (2-d and 3-d) simplified protein folding problems. This paper analyzes the rationale behind the application of EDAs to these problems, and elucidates the relationship between our proposal and other population-based approaches proposed for the protein folding problem. We argue that EDAs are an efficient alternative for many instances of the protein structure prediction problem and are indeed appropriate for a theoretical analysis of search procedures in lattice models. All the algorithms introduced are tested on a set of difficult 2-d and 3-d instances from lattice models. Some of the results obtained with EDAs are superior to the ones obtained with other well-known population-based optimization algorithms.     

面向对象数据库中基于有向图的联系代数

本文提出了基于基有向图的联系代数，并给出了一个优化联系代数表达的算法。本文所提出的改进较其原形式能 更精确地反映面向对象模型的实质，更有利于对象的查询处理与优化。     

A systematic approach to constructing incremental topology control algorithms using graph transformation

Communication networks form the backbone of our society. Topology control algorithms optimize the topology of such communication networks. Due to the importance of communication networks, a topology control algorithm should guarantee certain required consistency properties (e.g., connectivity of the topology), while achieving desired optimization properties (e.g., a bounded number of neighbors). Real-world topologies are dynamic (e.g., because nodes join, leave, or move within the network), which requires topology control algorithms to operate in an incremental way, i.e., based on the recently introduced modifications of a topology. Visual programming and specification languages are a proven means for specifying the structure as well as consistency and optimization properties of topologies. In this paper, we present a novel methodology, based on a visual graph transformation and graph constraint language, for developing incremental topology control algorithms that are guaranteed to fulfill a set of specified consistency and optimization constraints. More specifically, we model the possible modifications of a topology control algorithm and the environment using graph transformation rules, and we describe consistency and optimization properties using graph constraints. On this basis, we apply and extend a well-known constructive approach to derive refined graph transformation rules that preserve these graph constraints. We apply our methodology to re-engineer an established topology control algorithm, kTC, and evaluate it in a network simulation study to show the practical applicability of our approach.     

多媒体信号处理的数学理论前沿进展

深度学习模型广泛应用于多媒体信号处理领域,通过引入非线性能够极大地提升性能,但是其黑箱结构无法解析地给出最优点和优化条件。因此如何利用传统信号处理理论,基于变换/基映射模型逼近深度学习模型,解析优化问题,成为当前研究的前沿问题。本文从信号处理的基础理论出发,分析了当前针对高维非线性非规则结构方法的数学模型和理论边界,主要包括：结构化稀疏表示模型、基于框架理论的深度网络模型、多层卷积稀疏编码模型以及图信号处理理论。详细描述了基于组稀疏性和层次化稀疏性的表示模型和优化方法,分析基于半离散框架和卷积稀疏编码构建深度/多层网络模型,进一步在非欧氏空间上扩展形成图信号处理模型,并对国内外关于记忆网络的研究进展进行了比较。最后,展望了多媒体信号处理的理论模型发展,认为图信号处理通过解析谱图模型的数学性质,解释其中的关联性,为建立广义的大规模非规则多媒体信号处理模型提供理论基础,是未来研究的重要领域之一。     

Learning Physically Based Humanoid Climbing Movements

We propose a novel learning‐based solution for motion planning of physically‐based humanoid climbing that allows for fast and robust planning of complex climbing strategies and movements, including extreme movements such as jumping. Similar to recent previous work, we combine a high‐level graph‐based path planner with low‐level sampling‐based optimization of climbing moves. We contribute through showing that neural network models of move success probability, effortfulness, and control policy can make both the high‐level and low‐level components more efficient and robust. The models can be trained through random simulation practice without any data. The models also eliminate the need for laboriously hand‐tuned heuristics for graph search. As a result, we are able to efficiently synthesize climbing sequences involving dynamic leaps and one‐hand swings, i.e. there are no limits to the movement complexity or the number of limbs allowed to move simultaneously. Our supplemental video also provides some comparisons between our AI climber and a real human climber.     

进化策略的一种改进及其在蛋白质结构预测中的应用

进化策略算法是一种模拟自然界生物进化过程的全局优化方法。本文将一种改进的进化策略算法应用于蛋白质三维HPNX非格模型,较成功地预测了蛋白质序列1RPB、1BPI和1UBQ的折叠趋势,说明了三维HPNX非格模型比简化HP非格模型更能准确地描述蛋白质的折叠情况,同时表明了进化策略算法用于蛋白质结构预测问题是可行的、有效的。     

Optimization of Computations in the System of Computer Simulation fSim

A computational model of the simulation system fSim is constructed in terms of graph theory. The problem of transition from multi-level models to one-level ones is considered. The principles of construction of simulation models supported by fSim under conditions of distributed computations are described. Based on the droop vector method and heuristic methods, algorithms of optimization in distributed computing systems are considered.     

拉丁超立方体抽样遗传算法求解图的二划分问题

图的二划分问题是一个典型的NP-hard组合优化问题, 在许多领域都有重要应用. 近年来, 传统遗传算法等各种智能优化方法被引入到该问题的求解中来, 但效果不理想. 基于理想浓度模型的机理分析, 利用拉丁超立方体抽样的理论和方法, 对遗传算法中的交叉操作进行了重新设计, 并在分析图二划分问题特点的基础上, 结合局部搜索策略, 给出了一个解决图二划分问题的新的遗传算法, 称之为拉丁超立方体抽样遗传算法. 通过将该算法与简单遗传算法和佳点集遗传算法进行求解图二划分问题的仿真模拟比较, 可以看出新的算法提高了求解的质量、速度和精度.     

An algorithm based on ant colony optimization for the minimum connected dominating set problem

Ant colony optimization is a well established metaheuristic from the swarm intelligence field for solving difficult optimization problems. In this work we present an application of ant colony optimization to the minimum connected dominating set problem, which is an NP-hard combinatorial optimization problem. Given an input graph, valid solutions are connected subgraphs of the given input graph. Due to the involved connectivity constraints, out-of-the-box integer linear programming solvers do not perform well for this problem. The developed ant colony optimization algorithm uses reduced variable neighborhood search as a sub-routine. Moreover, it can be applied to the weighted and to the non-weighted problem variants. An extensive experimental evaluation presents the comparison of our algorithm with the respective state-of-the-art techniques from the literature. It is shown that the proposed algorithm outperforms the current state of the art for both problem variants. For comparison purposes we also develop a constraint programming approach based on graph variables. Even though its performance deteriorates with growing instance size, it performs surprisingly well, solving 315 out of 481 considered problem instances to optimality.     

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.     

特殊斜线型包装盒的三维成型研究

目前采用基于盒型拓扑图的方法可以实现包装平面图的三维成型,但无法解决折叠角度非默认90°情况下的正确三维成型问题。通过对平面盒型拓扑结构的立体建模,建立了折叠角度与包装盒尺寸大小之间的关系,实现了折叠角度的参数化,从而解决了特殊盒型结构进行三维成型时折叠角度的准确性问题。