改进的遗传算法优化二维不规则图形排样

针对大规模零件和不规则石材下料优化排样问题,提出了改进的遗传算法优化排样方法.采取二进制与十进制混合编码的策略,既克服了单独使用二进制编码时,编码串太长且操作不方便的不足,又解决了十进制编码中相近的编码方案获得的材料利用率却相去甚远的问题;通过计算矢量图形的相似度,从而对图形群体进行分类,降低了遗传算法的时间复杂度.实验结果表明,该优化排样算法在时间复杂度和空间占有率上均优于传统的遗传算法优化排样.     

遗传算法在矩形件优化排样中的应用

遗传算法是一种全局优化的数值计算方法。与传统优化算法相比,它对函数的要求不高,一般不会陷入局部最优解,更适应于求解大规模离散化问题。该文将遗传算法应用于工程问题的一个典型离散优化问题矩形件优化排样。通过该算法可以找出高效率的排样加工方法。设计结果能广泛应用于各零件的排样加工实例。     

基于遗传算法的大规模矩形件优化排样

大规模矩形件优化排样是一个典型的组合优化问题，属于NP-hard问题．实际工程中对一个排样方案一般有满足“一刀切”的工艺要求，“一刀切”要求增加了对排样的约束．提出的优化算法，将矩形匹配分割算法作为遗传算法染色体的解码器实现一个排样方案，用遗传算法进行排样方案的全局搜索．算例比较表明，该算法可以求得满足“一刀切”约束的最优解．     

混合算法的邻域结构变更研究及在排样问题上的应用

本文研究了全局搜索算法和局部搜索算法的混合机制,设计了基于邻域搜索和遗传算法的混合搜索算法。该算法结合了遗传算法的全局搜索特性和邻域局部贪婪搜索特性;在分析排样问题碰靠过程特征的基础上,构建了排样问题邻域假设,当邻域假设满足时,遗传算法+邻域搜索能很好发挥作用;当不能判断邻域结构是否满足邻域假设时,提出了建立遗传算法+匹配变邻域的搜索算法,该算法兼顾了组合优化中邻域搜索的局部搜索无效的情况,实现了匹配的变邻域混合算法在排样优化问题中的应用。实例结果标明,排样图形不一样,其求解难度不一样,该算法均搜索到了更好的排样模式,验证了算法的有效性。     

基于改进遗传算法的二维图形优化排样方法

在数控加工过程中,加工图形的排样优化对于提高原材料利用率,节约生产成本具有实际应用价值。采用改进的遗传算法解决这一问题,将普通的遗传算法与改进的交叉,变异算子相结合,并将最优个体保存策略融入算法,扩大了搜索空间,提高了传统遗传算法的搜索能力。在最低水平线算法基础上提出了基于水平轮廓线的最大匹配算法,在有效避免盲目升高水平轮廓线的同时,提高了最低水平线的利用率。将其与改进的遗传算法相结合,综合了两种算法的优点,很好地解决了二维矩形件优化排样问题。试验结果表明,该算法能够起到良好的优化效果。     

基于包容矩形的优化排样算法及实现

毛坯优化排样问题是CAD技术结合冲模设计领域的一大课题。论文在多边形顶点算法的基础上,提出了基于包容矩形的优化排样算法。该算法只需在初始毛坯图的包容矩形内进行计算,即可得到排样的步距、料宽等关键参数;在预排样时不用进行传统排样算法所作的等距放大处理,避免了由此引起的图形自交干涉和排样误差增大的问题。并且在Inventor9平台上运用VisualC++对该算法予以实现,开发出效率高、实用性强、运行可靠的冲裁模智能排样系统。     

矩形件排样问题的遗传算法求解

本文研究了求解矩形件正交排样优化问题的遗传算法。同时，将矩形件正交排样问题转化为一个排列问题，提出了求一个排列所对应的排样图的下台阶算法（改进的ＢＬ算法）将下台阶算法与遗传算法相结合，用于矩形件排样问题的求解，给出了该算法的实现。用该算法对文献中的两个算例进行了求解，结果表明该算法获得了比ＢＬ算法更好的解，是一种较为行之有效的方法。     

面向制造业的智能排样辅助系统研究及实现

针对传统的人工排样效率低,难以得到高质量排样方案的问题。在整合现有智能优化算法的基础上,利用嵌入式系统软硬件技术设计了智能排样辅助系统。硬件采用S3C2410 ARM9微处理器,软件采用面向对象的设计方法,通过UML(统一建模语言)语言来描述及MFC(微软基础类库)的文档视图模式来实现。设计的智能排样辅助系统对矩形材料的数据读入、优化计算、智能排样取得了良好的效果,同时也指出了设计中有待进一步完善的问题。     

实用异形件优化排样系统的研究与开发

对于多种不规则零件的优化排样,综合利用冲裁件排样中的图形识别和图形分析处理技术和拒形件的排样优化技术,在对它们作一些合理的改造后,有机地组合构造出多种不规则需件的5种排样算法。然后在保证可排性的条件下,将这些排样零件按不同的寻化规则排放到板材上去。为此研究开发了一些必要的许多图形处理技术,以保证算法的实现。这些算法具有优化效果好、自动化程度高、并且速度快等特点。因此在实际应用中,一般能为用户提供一个求解的效果接受率高或具有极好参考价值的解。在此基础上制作了一套操作方便、简单、快速的种不规则零件优化排样系统。     

混合算法在排样问题上的应用研究

结合全局搜索算法和局部搜索算法的互补特性,研究设计了串行和镶嵌两种混合模式,实现了基于邻域搜索和遗传算法的混合算法;在分析排样问题中图形碰靠的相关性特征的基础上,构建了排样问题的邻域假设和匹配邻域结构,基于混合算法获得了排样问题的优化解;实例结果标明,该算法在搜索到了更好的排样模式,验证了算法的有效性。     

Drawing graphs by eigenvectors: theory and practice

The spectral approach for graph visualization computes the layout of a graph using certain eigenvectors of related matrices. Two important advantages of this approach are an ability to compute optimal layouts (according to specific requirements) and a very rapid computation time. In this paper, we explore spectral visualization techniques and study their properties from different points of view. We also suggest a novel algorithm for calculating spectral layouts resulting in an extremely fast computation by optimizing the layout within a small vector space.     

改进的矩形毛坯三块排样方式及其算法

致力于改进矩形毛坯三块排样方式的生成算法,采用三种策略缩小解的搜索范围,并将该算法与线性规划相结合形成排样方案生成算法,用于求解大规模矩形毛坯排样问题.通过实验证明,与二阶段、T形、两段、三阶段排样算法相比,排样方案生成算法生成的排样方案虽然板材利用率稍低,但排样方案简单,能够简化切割工艺.     

基于改进人工蜂群算法的体声波滤波器自动布局

针对体声波（BAW）滤波器布局中芯片面积利用率低、设计周期长、制造成本高等问题,提出了一种基于改进人工蜂群算法的BAW滤波器自动布局方法。首先构建了自动布局的评价模型,通过结合利用圆形容器的顺序布局和基于旋转角度编码的聚拢布局来简化自动布局的难度;同时采用了一种改进人工蜂群算法去搜寻BAW滤波器的最优顺序布局和聚拢布局方案;最后,结合多组BAW滤波器的设计案例验证自动布局算法的有效性,其布局有效面积占比提升约17%,整体布局呈方形,且完成滤波器的自动布局仅需30 min。结果表明在保证BAW滤波器性能的前提下,算法可有效提升芯片面积利用率、大幅缩减滤波器的设计周期。     

一种基于继承次序与相关度的布图算法

在层次图边交叉最小化问题上,常规启发算法或者时间复杂度大或者布图效果不佳。基于Sugiyama布图算法模式,提出了一种交叉数减少算法,并从布局与布线两个主要方面介绍了其实现过程。两层图上的实验表明,该算法具有较好的性能,一定程度上克服了时间复杂度与效果的矛盾。     

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.     

A tabu search based approach for graph layout

This paper describes an automated tabu search based method for drawing general graph layouts with straight lines. To our knowledge, this is the first time tabu methods have been applied to graph drawing. We formulated the task as a multi-criteria optimization problem with a number of metrics which are used in a weighted fitness function to measure the aesthetic quality of the graph layout. The main goal of this work is to speed up the graph layout process without sacrificing layout quality. To achieve this, we use a tabu search based method that goes through a predefined number of iterations to minimize the value of the fitness function. Tabu search always chooses the best solution in the neighbourhood. This may lead to cycling, so a tabu list is used to store moves that are not permitted, meaning that the algorithm does not choose previous solutions for a set period of time. We evaluate the method according to the time spent to draw a graph and the quality of the drawn graphs. We give experimental results applied on random graphs and we provide statistical evidence that our method outperforms a fast search-based drawing method (hill climbing) in execution time while it produces comparably good graph layouts. We also demonstrate the method on real world graph datasets to show that we can reproduce similar results in a real world setting.     

FMR:基于FR的快速多层次算法

图可视化技术是可视化研究的重要内容,近年来大图的绘制问题一直是图可视化 技术的焦点。为此,提出了一种快速多层次算法用于解决大图绘制问题。采用多层次方法作为 算法的框架,以 FR 力导向算法的变体结合质心算法以及四叉树空间分解等方法对单层布局进 行优化。另外,还使用了约束规范化和能量模型 2 种加速方法。实验表明,该算法具有高效的 性能和良好的布局效果。其效率非常高,在单核 CPU 下,可以在大约 5 s 内很好地绘制出 10 000 个顶点的图。并与几种经典的算法进行了比较,也证明了该算法的有效性和实用性。此外,该 算法易于实现,可被轻易推广到其他布局算法上,以加速其运算。     

基于多重注意力机制的图神经网络股市波动预测方法

股票市场是金融市场关键组成部分,因此对股票市场波动的研究对合理化控制金融市场风险、提高投资收益提供了重要支持,一直以来都是学术界和相关业界的关注焦点,然而,股票市场会受到各种因素的影响。面对股票市场中多源化、异构化的信息,如何高效挖掘、融合股票市场的多源异构数据具有挑战性。为了充分解释不同信息及信息间相互作用对于股票市场价格波动的影响,提出一种基于多重注意力机制的图神经网络来预测股票市场的价格波动。首先,引入关系维度构建股票市场交易数据和新闻文本的异构子图,并利用多重注意力机制实现图数据的融合;其次,通过图神经网络门控循环单元（GRU）进行图分类,在此基础上完成对股票市场中上证综合指数、沪深300指数、深证成份指数这三个重要指数波动的预测。实验结果表明,从异构信息特性角度,相较于股票市场交易数据,股市新闻信息对于股票价格影响存在滞后性;从异构信息融合角度,所提方法与支持向量机（SVM）、随机森林、多核k-means （MKKM）聚类等算法相比,预测准确率分别提升了17.88个百分点、30.00个百分点和38.00个百分点,并进行了模型交易策略的量化投资模拟。     

基于动态分割与合一的排样算法

提出一种于动态分割与合一的优化排样算法,基本思想是分割之后,尽量将相邻的余料合并成较大的余料参与下一轮排祥,这不仅增加了排祥大件的可能性,而且也增加排样优化的机会,同时减少零件之间的空隙余料碎片,从而提高了切割速度。     

Bin packing and related problems: General arc-flow formulation with graph compression

We present an exact method, based on an arc-flow formulation with side constraints, for solving bin packing and cutting stock problems—including multi-constraint variants—by simply representing all the patterns in a very compact graph. Our method includes a graph compression algorithm that usually reduces the size of the underlying graph substantially without weakening the model.Our formulation is equivalent to Gilmore and Gomory׳s, thus providing a very strong linear relaxation. However, instead of using column-generation in an iterative process, the method constructs a graph, where paths from the source to the target node represent every valid packing pattern.The same method, without any problem-specific parameterization, was used to solve a large variety of instances from several different cutting and packing problems. In this paper, we deal with vector packing, bin packing, cutting stock, cardinality constrained bin packing, cutting stock with cutting knife limitation, bin packing with conflicts, and other problems. We report computational results obtained with many benchmark test datasets, some of them showing a large advantage of this formulation with respect to the traditional ones.