求凸多边形直径的算法

本文提出求平面凸多边形直径的一种算法，该算法至多需要ｎ－１次比较、ｎ次求距离运算，其中ｎ是凸多边形的顶点数。     

平面内直线度误差的一种精确评定新方法

针对给定平面内直线度误差优化评定存在的逼近算法复杂、迭代评定结果不够准确、不能与多种直线度误差测量仪器配合使用等问题,提出一种新的符合最小包容区域原理的快速精确算法--凸多边形截距法。该方法依据计算几何中的凸壳理论,将不同类型测量仪器的测量数据转换为坐标值,以首尾连线将测点分区,依据斜率大小构造凸多边形,以截距最大值对应的点与直线得出符合相间准则的3个特征点,通过剪移转换求出直线度误差。实验结果表明,所提出的算法简单、精确、易于计算机自动数据处理,具有评定精度高、运算速度快的特点。     

带时间窗的车辆路由问题的改进遗传算法

提出了一种改进的遗传算法,使用了一种新的染色体编码方式,和与之对应的启发式交叉算子,同时采取了竞争选择的淘汰机制,通过对Solomon提出的100个点的标准算例的计算验证,证明了该算法能够很好地解决各类带时间窗的车辆路由问题,通过和混和遗传算法的比较,证明了该算法在计算时间、收敛速度上都有大的优势.该算法计算得到的解在总行驶距离相差不大的情况下使用车辆数较少.     

凸多边形星图识别算法

为解决星敏感器中较大视场快速、可靠的星图识别,提出了以凸多边形为基元、完全不依赖于星等的星图识别算法。对给定的视场,挑选其中较亮的恒星,依其坐标排序,然后采用由平面上的点生成凸多边形的算法,就能得到唯一的、以恒星为顶点的凸多边形。为验证星图识别算法的有效性,建立了导航星数据库,其储存单元为凸多边形的边和相邻边的夹角,共有3832个边数不等的凸多边形。在CPU为33MHz 的PC104上仿真结果表明:在任意视场中,生成凸多边形的时间小于5ms,基于凸多边形的星图识别成功率高于99%,并具有较强的鲁棒性。     

计算两凸多边形的并集多边形及其面积的计算机算法与实现

提出计算两平面凸多边形的并集(多边形)及其面积的计算机算法，并对算法实现给出详细的计算过程。程序实现中，文中将算法分为判定点是否在多边形内部、求两多边形交点、求并集多边形及其面积三部分。引入利用向量叉积符号判定三角形的方向，进而判别平面上一点是否在凸多边形内的方法，简化了计算。还进一步提出了运用“区间分割”求两相交线段交点的新颖方法。     

基于凸多边形的直线度误差评定方法

提出了用凸多边形来评定直线度误差的方法.该方法根据凸集的定义由测量数据构造凸多边形,不断剔除凸多边形的顶点直至剩余3点,这3点满足直线度最小区域条件.此方法计算简单,易于实现.     

Delaunay-固定距离滑动邻域Kriging算法

地质统计学中的Kriging 算法是利用空间变异结构进行插值预报的算法,作为一种区域性算法,邻近点的选择是Kriging 算法实际应用中无法回避的重要问题。文章结合温度场计算的实际应用详细分析了Kriging 邻近点选择中需要考虑的原则,并采用Delaunay 三角划分搜索和固定距离搜索相结合的邻近点搜索策略,提出一种利用变程的Delaunay-固定距离滑动邻域算法。通过温度场数据的计算结果证明新算法在精确度上优于普通固定半径的滑动邻域Kriging 算法。     

自由边界平面连通域的Voronoi图生成方法研究

平面连通域的Vorono,图被广泛应用于许多领域,常用的分治法等算法实现较为复杂,影响了其应用范围在凸多边形中轴算法的基础上,提出一种建立自由边界平面连通域的Voronoi图的新方法.通过求解相邻边界元素的平分线,计算出相邻平分线的交点,由距离最小的平分线交点实现Voronoi图边的增长,最终建立完整的平面单连通域的Voronoi图.同时,还介绍了平面多连通域的内外边界的Voronoi图的合并算法.     

基于GPU和CPU协同处理实现的Canopy算法探索

提出一种基于GPU(图形处理器)和CPU协同处理实现来提高聚类算法Canopy的计算效率的优化方案。利用GPU高效的并行性和灵活的可编程性等特点,将Canopy聚类算法中比较耗时的距离计算及与阈值T1,T2的比较步骤交由GPU处理,算法其余步骤仍由CPU处理,理论上提高算法速度。     

用节约法解决带有时间窗的满载车辆调度问题

建立了具有时间约束的满载VSP问题的线性规划模型,给出了一种基于节约值比较的旨在最小化成本的启发式算法.该算法将满载车辆路线分为三种基本结构,即两点往返、多点连续实载、多点间隔实载,将车辆固定成本和变动成本同时加入到节约值计算中,根据路线结构计算更新节约值,在考虑时间约束的基础上参考节约值最大或机会节约值最大两种策略选择任务连接,得出车辆调度路线.经算例证明,该算法求得优化的调度路线.     

Optimal subgradient methods: computational properties for large-scale linear inverse problems

This paper studies the computational properties of the optimal subgradient algorithm (OSGA) for applications of linear inverse problems involving high-dimensional data. First, such convex problems are formulated as a class of convex problems with multi-term composite objective functions involving linear mappings. Next, an efficient procedure for computing the first-order oracle for such problems is provided and OSGA is equipped with some prox-functions such that the OSGA subproblem is solved in a closed form. Further, a comprehensive comparison among the most popular first-order methods is given. Then, several Nesterov-type optimal methods (originally proposed for smooth problems) are adapted to solve nonsmooth problems by simply passing a subgradient instead of the gradient, where the results of these subgradient methods are competitive and totally interesting for solving nonsmooth problems. Finally, numerical results with several inverse problems (deblurring with isotropic total variation, elastic net, and \(\ell _1\)-minimization) show the efficiency of OSGA and the adapted Nesterov-type optimal methods for large-scale problems. For the deblurring problem, the efficiency measures of the improvement on the signl-to-noise ratio and the peak signal-to-noise ratio are used. The software package implementing OSGA is publicly available.     

A novel discrete element method based on the distance potential for arbitrary 2D convex elements

A new 2‐dimensional discrete element method, which is able to simulate a system involving a large number of arbitrary convex elements, is proposed. In this approach, a novel distance potential function is defined using a normalized format of the penetrated distance between contact couples, while a holonomic and precise algorithm for contact interaction is established, accounting for the influence of the tangential contact force. Furthermore, the new contact detection algorithm is well suited for nonuniform blocks unlike the common no binary search method that requires uniform elements. The proposed method retains the merit of the combined finite‐discrete element method and avoids its deficiencies. Compared with the existing finite‐discrete element method, the distance potential function has a clear physical meaning, where the calculation of contact interaction avoids the influence of the element shape. Accordingly, the new method completely gets rid of the restraint of uniform element type and can be applied to arbitrary convex elements. The new method is validated with well‐known benchmark examples, and the results are in very good agreement with existing experimental measurement and analytical solutions. Finally, the proposed method is applied to simulate the Tangjiashan landslide.     

An Improved Whale Optimization Algorithm for Feature Selection

Whale optimization algorithm (WOA) is a new population-based metaheuristic algorithm. WOA uses shrinking encircling mechanism, spiral rise, and random learning strategies to update whale’s positions. WOA has merit in terms of simple calculation and high computational accuracy, but its convergence speed is slow and it is easy to fall into the local optimal solution. In order to overcome the shortcomings, this paper integrates adaptive neighborhood and hybrid mutation strategies into whale optimization algorithms, designs the average distance from itself to other whales as an adaptive neighborhood radius, and chooses to learn from the optimal solution in the neighborhood instead of random learning strategies. The hybrid mutation strategy is used to enhance the ability of algorithm to jump out of the local optimal solution. A new whale optimization algorithm (HMNWOA) is proposed. The proposed algorithm inherits the global search capability of the original algorithm, enhances the exploitation ability, improves the quality of the population, and thus improves the convergence speed of the algorithm. A feature selection algorithm based on binary HMNWOA is proposed. Twelve standard datasets from UCI repository test the validity of the proposed algorithm for feature selection. The experimental results show that HMNWOA is very competitive compared to the other six popular feature selection methods in improving the classification accuracy and reducing the number of features, and ensures that HMNWOA has strong search ability in the search feature space.     

Ant colony optimisation with parameterised search space for the job shop scheduling problem

The job-shop scheduling problem (JSSP) is known to be NP-hard. Due to its complexity, many metaheuristic algorithm approaches have arisen. Ant colony metaheuristic algorithm, lately proposed, has successful application to various combinatorial optimisation problems. In this study, an ant colony optimisation algorithm with parameterised search space is developed for JSSP with an objective of minimising makespan. The problem is modelled as a disjunctive graph where arcs connect only pairs of operations related rather than all operations are connected in pairs to mitigate the increase of the spatial complexity. The proposed algorithm is compared with a multiple colony ant algorithm using 20 benchmark problems. The results show that the proposed algorithm is very accurate by generating 12 optimal solutions out of 20 benchmark problems, and mean relative errors of the proposed and the multiple colony ant algorithms to the optimal solutions are 0.93% and 1.24%, respectively.     

基于BELLHOP模型的水下多目标跟踪算法研究

针对高频主动声呐的深海多目标跟踪问题,提出了基于BELLHOP模型的无迹卡尔曼滤波-高斯混合概率假设密度(Unscentesd Kalman Filter-Gaussian Mixture-Probability Hypothesis Density, UKF-GM-PHD)水下多目标跟踪算法。该算法首先利用BELLHOP射线声学模型,计算出本征声线、目标信号的幅度、相位及时延信息,以此构造目标回波信号并叠加高斯白噪声。然后,由回波信号计算得到目标相对于观测站的距离、方位角和俯仰角信息,作为目标跟踪系统中的量测信息。最后利用提出的UKF-GM-PHD多目标跟踪算法,实现高频主动声呐非线性系统的多目标跟踪。仿真结果表明,在深海高频主动声呐条件下,文章提出的UKF-GM-PHD多目标跟踪算法较传统高斯混合概率假设密度(Gaussian Mixture Probability Hypothesis Density, GM-PHD)方法,明显降低了目标丢失率,并且最优子模式指派统计量(Optimal Sub-Patter Assignment, OSPA)距离也更小,跟踪效果更好。     

Algorithm for decomposition of binary morphological convex structuring elements based on periodic lines

Abstract

This paper presents a new and simple algorithm for decomposing a convex structuring element into dilations of periodic lines with a union of a residue component. The algorithm proposed in this paper is based on the boundaries of convex structuring elements and the properties of dilations. Besides simplicity of the algorithm, the advantage of the method is that periodic lines possess a faster implementation of the corresponding dilations and erosions. The examples of optimal decomposition demonstrate that the algorithm offers a low complexity of morphological operators. The results indicate that the present decomposition algorithm is more robust when compared with other algorithms.     

A note on resource allocation scheduling with group technology and learning effects on a single machine

In this article, single-machine group scheduling with learning effects and convex resource allocation is studied. The goal is to find the optimal job schedule, the optimal group schedule, and resource allocations of jobs and groups. For the problem of minimizing the makespan subject to limited resource availability, it is proved that the problem can be solved in polynomial time under the condition that the setup times of groups are independent. For the general setup times of groups, a heuristic algorithm and a branch-and-bound algorithm are proposed, respectively. Computational experiments show that the performance of the heuristic algorithm is fairly accurate in obtaining near-optimal solutions.     

面向快递同城运输的车辆路径问题研究

为降低运输成本,研究了快递同城运输中的车辆路径问题。建立多车型,含时间窗约束、容量约束、车辆限行约束,并考虑错峰交货的,以最小化运输成本为目标的混合整数规划模型。提出以点到点集的距离之和作为邻域搜索优先指标的构造性启发式算法,设计了基于“路径−车型对”的列生成算法,初始列由启发式算法求得。实验结果显示,对于120个点的大规模问题,列生成算法只需175秒就能得到近似最优解,验证了该算法的有效性及对一定规模内快递同城运输问题的适用性。     

车载可补货无人配送小车配送路径研究

无人配送小车由于不适合长距离运输,可与货车搭配完成“最后一公里”配送任务以增加服务范围,这对车辆路径优化问题提出了新的挑战。针对配送小车数量有限、城市配送货物量大且货车停靠限制的特点,提出无人配送小车可补货的大车-小车路径优化问题,即一辆货车搭载多台无人配送小车,由无人配送小车给客户送货,无人配送小车可在货车处补充货物并执行多行程配送。构建以总配送距离最短为目标的整数规划模型,针对此模型设计混合遗传大邻域搜索算法,在遗传算法基础上增加大邻域搜索算法对个体优化。在算法优化过程中先优化小车路径,再在小车路径基础上优化大车路径。数值实验表明,对于小规模问题,所提算法最多花费CPLEX求解时间的6%便获得最优解;在改造的Solomon数据上,所提算法相对于遗传算法平均有95.5%的计算结果优势,相对于大邻域搜索算法平均有7.2%的计算结果优势,且数据量越大,优势越大。     

抑制微光波前传感器随机噪声的方法研究

在自适应光学系统微光波前传感器中采用像增强器后，高帧频CCD输出的图像中会产生严重的随机噪声，影响光斑质心计算精度，从而使自适应光学系统波前探测精度降低。本文根据微光波前传感器中CCD输出图像的特点对中值滤波，均值滤波，自相关，延时相关等多种方法进行了仿真和实验比较，并提出了一系列评价方法。研究表明延时相关算法是最佳选择。