英语原文共 20 页，剩余内容已隐藏，支付完成后下载完整资料
带附加约束的增量图绘制问题的启发式算法
摘 要
信息可视化是计算机科学中的一个相关课题，其中图形已经成为一种标准的表示模型，图形绘制也成为一个成熟的领域。在这一背景下，边交叉最小化是一个被广泛研究的问题，因为它对于获得可读的图表示具有重要意义。在本文中，我们主要研究所谓的增量式图形绘制问题，即在获得同一图形的连续图形时，尽量保存用户的心理图形。特别地，我们最大限度地减少了边交叉的数量，同时满足了针对先前图形的顶点位置的一些约束。我们提出了启发式方法，以便在图形绘制应用程序所需的较短计算时间内获得该优化问题的高质量解。我们还提出了一个数学规划公式，并得到了中小型实例的最优解。我们的大量实验表明，无论是相比CPLEX方法得到的最优解，还是组合优化中著名的黑匣子求解器LocalSolver得到的启发式解，我们的正解都具有一定的优越性。
关键词：启发式；元启发式方法；组合优化；图形绘制
目录
第1章 引言
当图表的元素(顶点和边)杂乱无章地放置时，就很难对其进行分析，因为缺乏了基本的美学标准。图形绘制问题在于以一种易于阅读的组织方式来创建给定图形的表示。图形绘制领域的主题范围从视觉感知到算法或模型，它目前构成了计算机科学中一个成熟的领域(例如，参见Kaufmannamp;Wagner，2001)。俗话说，一张图片胜过千言万语，在这里可以改编并补充说，如果图片是自动生成的，而不是人工生成的，那就更好了。
图表绘图文献(参见Battista、Eades、Tamassia和Tollis，1998)报告了一些表示顶点的标准，例如点、圆或方框，以及更重要的表示边的标准：直线、多边形和正交路径或三元曲线。图表绘图资源(论文、软件、会议过程)通常根据这些不同类型的表示进行分类，也称为绘图约定规范。在本文中，我们关注的是层次表示，它们也被称为分层图，其中有向无环图是通过将顶点排列在一系列等距的直线(称为层)上来表示的，这种方式使得绘制为直线的所有边都指向相同的方向。应该注意的是，使用层次表示并不限制我们的工作范围，因为有几种方法可以将有向无环图转换为层次图，最著名的是Sugiyama，Tagawa和Toda(1981)的过程。表1列出了分层图的一些应用。
表格 1一些层次图的实际应用
|
领域 |
参考文献（略） |
表示的数据 |
|
工作流程可视化 |
由项目组执行的工作。 |
|
|
软件工程 |
计算机程序中的子例程之间的调用关系。 |
|
|
数据库建模 |
系统内部的数据连接、处理和存储。 |
|
|
生物信息学 |
具有多种功能成分的结构化分子 |
|
|
流程建模 |
组织业务流程的分析性展示或图解 |
|
|
网络管理 |
一组生产性操作 |
|
|
VLSI电路设计 |
新型半导体芯片的集成电路(IC)设计。 |
|
|
决策图 |
逻辑综合和循环 |
虽然一般说来，对图形表示质量的感知是相当主观的，但边交叉最小化是一种公认的获得可读性图形的方法。有可读性概念的其他美学标准包括：弯曲、长度和面积最小化、角度最大化、匀称和聚类(参见Kaufmann and Wagner(2001)的详细描述)。在这篇文章中，我们以边相交最小化为目标，因为它作为一种审美标准很重要，而且在启发式优化方面存在困难(这是一个NP完全问题，即使当图形只有两层时也是如此，参见Gareyamp;Johnson，1983)。最小化层次有向无环图(Hierarchical Directed Acyclic Graph, HDAG)中的边交叉问题通常被看作是寻找每层顶点的最优排序问题(Martiacute;amp;Estruch，2001)
图形已经成为项目管理、生产计划或CAD等领域的基本建模工具，其中项目结构的改变会导致类似的连续图形的绘制。所谓的绘画心理图反映了用户利用图形中的元素创建心理结构框架的能力。当在图形中添加或删除元素时，用户必须调整他的心理结构图以熟悉新图形。动态图形绘制领域正是致力于最大限度地减少此工作。如在Branke(2001)中所描述的，考虑到图形只被稍微修改，应用图形绘制方法从头开始重新绘图是非常低效的，并且可能提供完全不同的图形，从而导致用户要付出巨大努力重新熟悉新图形。因此，在这种情况下需使用处理动态或增量图形的模型。
为了说明增量问题，我们考虑图1中的层次图，它显示了一个含有50个顶点和5个层的图的边交叉最小化问题的最优解。它是用CPLEX通过求解此问题的经典数学公式（如第3节所示）得到的。现在，我们通过添加20个顶点(每层4个)及其关联边来在图上增加内容。图2显示了新图的边交叉最小化问题的最优解，其中新增加的顶点和边用虚线表示。
虽然图2中的交叉数目是最小的，为99个，但是这个新的绘图是从头开始创建的，没有考虑图1原始绘图中顶点的位置。例如，第一层中的顶点 6在图1中的位置7，但在图2中它在位置10。由此可见，图2没有保持用户熟悉图1时的心理图。因此，根据动态绘图规范(Branke，2001)，我们建议在减少新图的交叉次数的同时保持原本存在的顶点靠近图1中的原位置。
关于增量式图形绘制的文献很少。我们在下一节将报告它们的主要贡献。特别是，对于层次图，以前的工作只保留了原始顶点的相对位置(Martiacute;，Martiacute;nez-Gavara，Saacute;nchez-Oro，amp;Duarte，2018)。正如接下来会看到的，这可能会导致糟糕的增量绘图(即，绘图的心理图形没有正确保留)。在这篇文章中，我们考虑了一个稳健的模型，当最小化一系列图中的边交叉数目时，同时约束原始顶点的相对位置和绝对位置。通过这种方式，我们可以帮助用户在处理连续发生变化的图形时保留他的心理图。特别地，我们的模型限制了原始顶点相对于它们在初始绘图中的位置的相对位置(如Martiacute;et al.，2018年)，并且还将它们的绝对位置限制在其初始位置的短距离内(如Battista等人，1998在正交图的应用中)。
据我们所知，这是首次在分层图的增量图中将这两个约束都考虑到。本文提出了一种数学规划公式来获得中型实例的最优解，还提出了基于GRASP和禁忌搜索的启发式方法来获得大型实例的高质量解。此外，我们采用著名的LocalSolver黑盒优化器来解决此问题。并对这四种方法进行了实证比较。
这里的研究不仅仅是解决特定的优化问题。禁忌搜索和GRASP可以被认为是两类重要的元启发式方法的代表求解流程：基于记忆的方法和无记忆的方法。记忆结构的显式使用构成了大量智能求解器的核心，包括禁忌搜索( Glover amp; Laguna, 1997 )或路径重连优化算法( Ribeiro amp; Resende, 2012 )。另一方面，我们也可以发现一些成功的元启发式算法，如模拟退火(Kirkpatrick，Gelatt，amp;Vecchi，1983)或GRASP(Festaamp;Resende，2009)，它们的原始设计中没有记忆结构。继之前关于启发式优化的论文(Martiacute;nez-Gavara，Campos，Grego，La-Guna，amp;Martiacute;，2015)之后，这里我们试图回答该领域的一个悬而未决的问题：使用记忆的设计更好，还是凭借半随机的设计更好？本文在解决增量图绘制问题时，对这两种设计（基于记忆的设计和半随机设计）进行了比较。
考虑到我们正在引入一个新的问题，我们对它进行了修改，并在第二节中修改了类似的问题。然后，在第三节中，我们提出了一个数学规划公式。我们论文的主要贡献在第4节中描述，在那里我们应用元启发式方法来获得这个问题的高效解决方案。论文最后用一个很大的计算实验来评价我们方法的优点，并得出了第7节中的相关结论。
第2章 动机和问题背景
增量式绘图是图形表示中一个非常重要的领域，我们可以找到许多突出这个问题的参考文献，或者更准确地说，是这一系列问题。请读者参考North(1996)，Diehl和Gouml;rg(2002)，或Pinaud，Kuntz，还有Lehn(2004)。图表绘制教科书(Battista等人，1998)是该领域的参考资料，它用了整整一章来介绍增量结构。增量技术的应用范围也很广，从在线问题，如从属网络或在线广告，到企业管理中众所周知的项目管理图。然而，尽管它的重要性和现实意义不言而喻，但目前仅有几种增量式图形绘制模型，并且我们认为它们并不是完全令人满意的。在本节中，我们将回顾增量图绘制的背景，包括之前在软件和学术领域中所做的努力。我们讨论了现有层次图模型的局限性，以及我们的建议是如何克服它们的。
在从属网络中，个体和群体用顶点表示，边表示个体和群体对这些群体的隶属关系。这些网络通常会随新的组和成员有组织的添加而及时变化。当添加时，希望新布局既美观又保持动态稳定性(即，它很好地符合绘图顺序)。在对在线广告(Antonellis，Molina，amp;Chao，2008)的查询中可以发现类似的情况，这些查询必须被表示为用于分析的图形序列。查询和广告(Ad)之间的链接指示该查询已被用来到达该特定广告。这类图表自然是动态的，因为用户不断地提交查询，而且公司还包括新的广告
目前，存在各种各样的用于图形表示的软件。例如，Ellson，Gansner，Koutsofios，North，Woodhull，(2001)是一个自由、灵活的软件，可通过易于使用的Web版本访问。与大多数竞争对手一样，它增加了优化标准，以获得美观的图样。我们在图3中说明了这一点，图3显示了Graphviz如何能够为简单的分层图获得清晰且美观的布局。
但是，该软件不能很好地表达具有动态性的对象和关系。实际上，每当向网络中添加新的顶点和边时，该软件都不支持识别增量元素，而是从头开始绘制图形。例如，在同样由Graphviz获得的图4中，我们可以观察到在图3的图中添加一组新的顶点和连接如何导致完全不同的表示，从而“破坏”读者的心理图。
近年来，在科学文献中，为解决增量式作图问题进行了一些努力。所提出的启发式算法能够解决大型实例，但所得到的图纸在心里图形方面存在缺陷，这可以从以下项目管理的实例中观察到。在这些项目中，任务用顶点表示，它们的优先级关系用边来表示。在大型项目的开发过程中会发生许多更改，这些更改必须反映在相关的图形或图表中。动态图形绘制是项目经理的一种需求，随着项目的发展，他们需要一系列稳定的图形。该项目通常表示为分层或层状的图形，它构成了我们增量图形绘制模型适用性的一个很好的例子。图5显示了一个中型项目上的这样一个图表的表示。因为它是一个有6层的大图，所以我们做了一些简化来画它。具体来说，我们不包括第一个顶点，它代表项目的开始。它将被分配在左侧部分(可称作在层0中)，并连接到第一层中的所有顶点。同样地，我们不表
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[237151]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
