Smoothed Analysis of Partitioning Algorithms for Euclidean Functionals

Euclidean optimization problems such as TSP and minimum-length matching admit fast partitioning algorithms that compute near-optimal solutions on typical instances. In order to explain this performance, we develop a general framework for the application of smoothed analysis to partitioning algorithms for Euclidean optimization problems. Our framework can be used to analyze both the running-time and the approximation ratio of such algorithms. We apply our framework to obtain smoothed analyses of Dyer and Frieze’s partitioning algorithm for Euclidean matching, Karp’s partitioning scheme for the TSP, a heuristic for Steiner trees, and a heuristic for degree-bounded minimum-length spanning trees.     

一个多目标优化演化算法的收敛性分析框架

由于演化算法求解多目标优化问题所得结果是一个优化解集——Pareto最优集,而现有的演化算法收敛性分析只适合针对单目标优化问题的单个。用有限马尔科夫链给出了演化算法求解多目标优化问题的收敛性分析框架,并给出了一个分析实例。     

Branch-and-Bound Methods for Euclidean Registration Problems

In this paper, we propose a practical and efficient method for finding the globally optimal solution to the problem of determining the pose of an object. We present a framework that allows us to use point-to-point, point-to-line, and point-to-plane correspondences for solving various types of pose and registration problems involving euclidean (or similarity) transformations. Traditional methods such as the iterative closest point algorithm or bundle adjustment methods for camera pose may get trapped in local minima due to the nonconvexity of the corresponding optimization problem. Our approach of solving the mathematical optimization problems guarantees global optimality. The optimization scheme is based on ideas from global optimization theory, in particular convex underestimators in combination with branch-and-bound methods. We provide a provably optimal algorithm and demonstrate good performance on both synthetic and real data. We also give examples of where traditional methods fail due to the local minima problem.     

A Runtime Analysis of Evolutionary Algorithms for Constrained Optimization Problems

Although there are many evolutionary algorithms (EAs) for solving constrained optimization problems, there are few rigorous theoretical analyses. This paper presents a time complexity analysis of EAs for solving constrained optimization. It is shown when the penalty coefficient is chosen properly, direct comparison between pairs of solutions using penalty fitness function is equivalent to that using the criteria ldquosuperiority of feasible pointrdquo or ldquosuperiority of objective function value.rdquo This paper analyzes the role of penalty coefficients in EAs in terms of time complexity. The results show that in some examples, EAs benefit greatly from higher penalty coefficients, while in other examples, EAs benefit from lower penalty coefficients. This paper also investigates the runtime of EAs for solving the 0-1 knapsack problem and the results indicate that the mean first hitting times ranges from a polynomial-time to an exponential time when different penalty coefficients are used.     

A Framework for Certified Boolean Branch-and-Bound Optimization

We consider optimization problems of the form (S, cost), where S is a clause set over Boolean variables x ₁?...?x _n , with an arbitrary cost function \(\mathit{cost}\colon \mathbb{B}^n \rightarrow \mathbb{R}\), and the aim is to find a model A of S such that cost(A) is minimized. Here we study the generation of proofs of optimality in the context of branch-and-bound procedures for such problems. For this purpose we introduce \(\mathtt{DPLL_{BB}}\), an abstract DPLL-based branch-and-bound algorithm that can model optimization concepts such as cost-based propagation and cost-based backjumping. Most, if not all, SAT-related optimization problems are in the scope of \(\mathtt{DPLL_{BB}}\). Since many of the existing approaches for solving these problems can be seen as instances, \(\mathtt{DPLL_{BB}}\) allows one to formally reason about them in a simple way and exploit the enhancements of \(\mathtt{DPLL_{BB}}\) given here, in particular its uniform method for generating independently verifiable optimality proofs.     

欧氏平面上NP-hard优化问题多项式时间近似方案设计技术

一、引言 欧氏空间中的组合优化问题均带有深远应用背景.这类问题的求解算法研究在计算机科学中占有重要位置.TSP问题、STEINER树问题、k-median 问题是三个经典的NP-Hard类组合优化问题[1～3],它们在欧氏平面上的求解算法广泛应用于网络可靠控制、集成电路设计、网络布局等领域.特别对TSP问题,虽然科学家们投入了大量的工作,但近三十年来没有取得实质性进展,而Arora等在1996-1998年应用相同的技术相继给出了上述问题在欧氏空间中的近似方案,使人们对该类问题的认识前进了一大步.     

基于时空全局优化的视频修复

提出一种基于样本的视频修复算法,将视频修复问题看作是嵌入到时空视频体中的一个三维图的离散的全局优化问题,可有效地修复视频中较大破损的区域.首先建立待修复视频的马尔科夫随机场(MRF),然后设置新的目标函数,将修复问题转化为马尔科夫随机场的多标号问题,使待修复区域与其周围区域在颜色的相似性和运动的相似性保持一致性.进而提出了灵巧置信传播求解算法,有效求解此目标函数,大大降低了标准置信传播算法的时空复杂度.还提出了与视觉相关的像素权值的概念,使得算法能更好地按照视觉合理性计算时空块的相似度.对复杂动态场修复结果实验表明,较现有算法,文中算法能更好地修复出显著结构和运动信息.     

A Capable Neural Network Framework for Solving Degenerate Quadratic Optimization Problems with an Application in Image Fusion

This paper presents a dynamic optimization scheme for solving degenerate convex quadratic programming (DCQP) problems. According to the saddle point theorem, optimization theory, convex analysis theory, Lyapunov stability theory and LaSalle invariance principle, a neural network model based on a dynamic system model is constructed. The equilibrium point of the model is proved to be equivalent to the optimal solution of the DCQP problem. It is also shown that the network model is stable in the Lyapunov sense and it is globally convergent to an exact optimal solution of the original problem. Several practical examples are provided to show the feasibility and the efficiency of the method.     

几种溃坝问题的SPH方法数值模拟

光滑粒子流体动力学(Smoothed Particle Hydrodynamics,SPH)法是近二十年来发展起来的一种纯的拉格朗日无网格粒子方法.由于它计算空间导数时不需要使用网格并且具有自适应性质,从而避免了高维拉氏网格法中的网格缠结和扭曲的麻烦,被广泛地应用到了各种领域.通过介绍SPH方法并结合浅水波方程,引入处理边界问题常用的虚粒子方法.利用SPH方法结合虚粒子的方式讨论了对于溃坝问题中常见的漂浮物和障碍物的模拟,并通过数值实验的方式证明了此方法在模拟复杂流体运动上的可行性,为SPH方法的进一步发展和广泛应用奠定了基础.     

求解约束优化问题的协同进化教与学优化算法

对约束优化问题,为了避免罚因子和等式约束转化为不等式约束时引入的约束容忍度参数所带来的不便,本文在基本教与学优化（Teaching-learning-based optimization,TLBO）算法中加入了自我学习过程并提出了一种求解约束优化问题的协同进化教与学优化算法,使得罚因子和约束容忍度随种群的进化动态调整.对7个常见测试函数的数值实验验证了算法求解带有等式和不等式约束优化问题的有效性.     

欧氏Steiner最小树问题的智能优化算法

欧氏平面内连接固定原点的最小树长问题，即欧氏Steiner最小树问题，为组合优化中的NP难题，因此合理的方法是寻找启发式算法。该文给出了两种智能优化算法——模拟退火法和蚂蚁算法。首先概述智能优化算法并将中面划分成网格，然后分别介绍两种算法的原理及实现过程，最后通过一系列计算实验，测试了算法的运行性能，获得了较好的效果。     

A GIS-Based Optimization Framework for Competitive Multi-Facility Location-Routing Problem

In a dynamic market setting, firms need to quickly respond to shifting demographics and economic conditions. In this paper, we investigate the problem of determining the optimum set of locations for a firm, which operates a chain of facilities under competition. We consider the objective of maximizing profit, defined as gross profit margin minus logistics costs. We propose a location-routing model where revenue is realized according to probabilistic patronization of customers and routing costs are incurred due to vehicles serving the open facilities from a central depot. We propose a hybrid heuristic optimization methodology for solving this model. The optimal locations are searched for by a Genetic Algorithm while an integrated Tabu Search algorithm is employed for solving the underlying vehicle routing problem. The solution approach is tested on a real dataset of a supermarket chain. The results show that the location decisions made by the proposed methodology lead to increased market share and profit margin, while keeping logistics costs virtually unchanged. Finally, we present a GIS-based framework that can be used to store, analyze and visualize all data as well as model solutions in geographic format.     

A Generic Framework for Constrained Optimization Using Genetic Algorithms

In this paper, we propose a generic, two-phase framework for solving constrained optimization problems using genetic algorithms. In the first phase of the algorithm, the objective function is completely disregarded and the constrained optimization problem is treated as a constraint satisfaction problem. The genetic search is directed toward minimizing the constraint violation of the solutions and eventually finding a feasible solution. A linear rank-based approach is used to assign fitness values to the individuals. The solution with the least constraint violation is archived as the elite solution in the population. In the second phase, the simultaneous optimization of the objective function and the satisfaction of the constraints are treated as a biobjective optimization problem. We elaborate on how the constrained optimization problem requires a balance of exploration and exploitation under different problem scenarios and come to the conclusion that a nondominated ranking between the individuals will help the algorithm explore further, while the elitist scheme will facilitate in exploitation. We analyze the proposed algorithm under different problem scenarios using Test Case Generator-2 and demonstrate the proposed algorithm's capability to perform well independent of various problem characteristics. In addition, the proposed algorithm performs competitively with the state-of-the-art constraint optimization algorithms on 11 test cases which were widely studied benchmark functions in literature.     

基于稀疏框架的静态污点分析优化技术

当前,隐私数据保护是信息系统安全的重要研究挑战,对应用程序进行隐私泄露检测是隐私泄露保护的有效方案.污点分析技术可以有效地对应用程序进行保密性和完整性的安全检测,提前报告出潜在的隐私泄露风险.然而,当前高敏感度的静态污点分析还存在开销过高的问题.通过对目前主流的污点分析工具FlowDroid进行深入分析,发现其污点分析计算中大量无关联污点传播是导致开销过高的重要原因,统计实验表明无关联传播占比高达85.2%.针对这一问题,尝试利用近年来一种有效的程序分析优化手段——稀疏优化——的方法,对静态污点分析中无关联的传播进行消除,达到时间和空间的开销优化.创新地将经典的数据流分析框架扩展成稀疏的形式,在此基础上提供了基于稀疏优化的污点分析方法.最后实现了工具FlowDroidSP,实验表明:FlowDroidSP在非剪枝模式下相比原FlowDroid具有平均4.8倍的时间加速和61.5%的内存降低.在剪枝模式下,具有平均18.1倍的时间加速和76.1%的内存降低.     

一个用于数据并行语言计算划分的时序优化模型

一个程序中数据并行语句的计算划分(CP)对该程序的运行性能有决定性的作用.尽管人们对这一问题已经进行了广泛的研究,但这些研究的重点都集中在如何提高被选择计算划分的空间局部性上.针对并行循环结构的计算划分问题,提出了一个时序优化模型.在该模型中,一个计算划分被表示成一个有向图,在把并行语句中的操作映射到各个处理器的同时,给出了被分配到不同处理器上的操作之间的相关性.对于一条数据并行语句,时序优化模型对它的每个计算划分选择方案分别采用多种有效的优化策略进行优化;并综合考虑各个计算划分选择方案的负载平衡性、处理器间的操作依赖性、数据访问的空间局部性和时间局部性四个方面的因素,估算每个方案的执行效率;最后从这些方案中选择一个执行效率最优的方案作为该语句的计算划分.作者已在HPF编译器p-HPF采用时序优化模型实现了对FORALL结构的支持.实验结果表明,该模型具有非常好的通用性,对不同领域多种数据并行问题均取得了理想的加速比.同时,只需略微改动,该模型也可用于其他类型数据并行语句的计算划分.     

应用于矢量量化的改进粒子群优化算法

针对粒子群优化算法(PSO)应用于矢量量化时,最优粒子对与其对应维度距离较大的粒子缺乏有效指导问题,提出适用于矢量量化的改进粒子群优化算法(IPSO_VQ).该算法通过建立粒子与榜样粒子的维度映射关系,以基于映射关系的维度学习代替对应维度学习关系,使粒子相关维度间的学习有一定相关性,增强算法局部搜索能力.同时,借鉴广泛学习粒子群优化(CLPSO)算法中的广泛学习思想,并将其应用于基本PSO中的全局最优位置学习部分,通过对多个粒子的广泛学习,增加种群的多样性.实验结果表明该算法有效避免种群早熟收敛,从而使解码恢复图像获得更高的主客观质量.     

基于多核平台的多线程动态优化框架

动态优化是计算系统虚拟化的重要支撑技术之一.本文通过对DynamoRIO、Jrpm等单核平台上典型动态优化系统的分析,总结出传统动态优化机制在多核平台下面临的问题与挑战,据此提出一种面向多核平台的多线程动态优化框架,分析其组织结构和工作原理,并通过实验验证了该框架的可行性.     

无线网络优化问题探析

本文基于无线网络优化原理、技术特征探讨了优化建设发展中面临的挑战问题,探析了无线网络优化的科学发展趋势,对完善优化建设效果,构建集中的无线网络优势平台全面开展优化工作有积极有效的促进作用。     

一种基于HLA的协同优化计算框架

提出了一种基于高层体系结构的协同优化计算框架(Collaborative Optimization Framework Based on HLA,COF-HLA).分析了多学科设计优化计算框架的功能和特点,并从支持代码复用、并行计算、数据分发管理等方面分析了高层体系结构的各种服务在协同优化计算框架中的作用;论述了该框架的联邦设计、对象类设计以及数据分发机制,总结了该框架所具有的特点和优势.该框架利用数据分发管理服务,可以极大地降低分布式计算时的网络通讯量,提高了整个协同优化计算的效率.     

求解全局优化问题的混合智能算法

把序列二次规划作为遗传算法的一个局部搜索算子,嵌入到实数编码遗传算法中,构成一种基于序列二次规划和实数编码遗传算法的高效的混合智能算法。该方法充分利用序列二次规划法的强局部搜索能力和遗传算法的全局收敛性,使得混合算法的全局收敛性得到改善并且减少了计算量。数值实验结果表明,混合算法是高效可靠的。