GPP问题的骨架分析与启发式算法设计

图的划分问题(GPP)是具有广泛应用背景的典型NP-难解问题,高效启发式算法一直是该领域的研究热点.作为设计启发式算法的有力工具,GPP的骨架分析存在理论分析结果匮乏、骨架规模过小等缺陷.文中采用构造偏移GPP实例的技巧,不仅在理论卜证明了获取GPP的骨架是NP-难解的,并且利用一般GPP实例与偏移实例的关系,实现了骨架规模的提高.在此基础上,文中对于目前求解GPP问题最好的算法之一的IBS进行了改进,提出了基于偏移实例的IBS算法(BI-IBS).算法BI-IBS首先构造偏移GPP实例,然后再利用局部最优解交集对它进行归约,最后再求解归约后的规模更小的新实例.实验结果表明,BI-IBS比现有算法在解的质量上有了较显著的提高.文中的工作较完善地解决了GPP的骨架研究存在的问题,所采用的构造偏移实例的技巧对于其它NP-难解问题的骨架理论分析及启发式算法设计亦具有较高的参考价值.     

求解QAP问题的近似骨架导向快速蚁群算法

QAP(quadratic assignment problem)问题是经典的组合优化问题之一,广泛应用于许多领域中.针对QAP问题,提出了一种新的蚁群算法--近似骨架导向的快速蚁群算法(ABFANT).该算法的基本原理是通过对局部最优解的简单相交操作得到QAP问题实例的近似骨架(approximate-backbone),利用这些近似骨架可以极大地缩小QAP问题的搜索空间,而同时不降低搜索的性能,最后对这个缩小后的搜索空间,直接用当前求解QAP问题最好的启发式算法之一-快速蚁群算法(FANT)求解得到问题的解.在QAPLIB中的典型实例上的实验结果表明,近似骨架导向的快速蚁群算法明显优于快速蚁群算法.此外,指出基于近似骨架的算法思想可以很容易地被移植到其他求解QAP问题的启发式算法中.     

TSP问题的脂肪计算复杂性与启发式算法设计

旅行商问题(traveling salesman problem,简称TSP)是经典的NP-难解组合优化问题之一,求解它的高效启发式算法一直是计算机科学研究的热点.脂肪作为描述TSP结构特征的新工具,对启发式算法设计具有重要意义.目前,TSP问题的脂肪研究还处于初始阶段,缺乏理论分析结果及相关的启发式算法.首先分析了TSP问题的脂肪计算复杂性,通过构造偏移实例的技巧,证明了获取TSP的脂肪是NP-难解的,即在P(NP的假设下,不存在算法可以在多项式时间内获得完整脂肪.在此基础上,通过分析TSP问题局部最优解与脂肪的关系,给出了求解TSP问题的元启发式算法--动态候选集搜索(dynamic candidate set search,简称DCSS)算法.利用该算法,改进了目前求解TSP问题最好算法之一的LKH.TSPLIB典型实例的实验结果表明,改进后的算法在解的质量上有较为明显的提高.新的基于脂肪的启发式算法对于求解其他NP-难解问题具有一定的参考价值.     

二次分配问题的粒子群算法求解

文章采用了一种新的算法,即粒子群算法(PSO)去解决二次分配问题(QAP),构造了该问题的粒子表达方法,建立了此问题的粒子群算法模型,并对不同的二次分配问题算例进行了实验,结果表明:粒子群算法可以快速、有效地求得二次分配问题的优化解,是求解二次分配问题的一个较好方案。PSO算法在很多连续优化问题中已经得到较成功的应用,而在离散域上的研究和应用还很少。文章应用PSO算法解决QAP问题是一种崭新的尝试,它对于将PSO算法应用于离散问题,特别是组合优化问题无疑具有启发性,并为进一步深入研究奠定了基础。     

翻转距离星树问题的计算复杂度和近似算法

讨论基于基因组翻转距离的星型进化树问题的算法和复杂性.首先证明星树问题是NP-难解的,再证明该问题不存在绝对近似求解算法,最后给出一个求解星树问题的常数近似算法,近似性能比为2.     

三阶段拉格朗日启发式算法求解带同时取送货的绿色车辆路径问题

针对带同时取送货的绿色车辆路径问题,以最小化带碳排放费用的配送成本为优化目标,建立混合整数规划模型,并提出一种结合数学规划方法与启发式算法的三阶段拉格朗日启发式算法进行求解.第1阶段,利用拉格朗日松弛技术得到该问题的拉格朗日对偶模型;第2阶段,设计一种改进的次梯度算法迭代求解该对偶模型,同时引入修复机制,将每次迭代所得下界对应的解修复为原问题较高质量的可行解,并在下次迭代中利用该可行解更新次梯度方向和步长;第3阶段,设计一种启发式局部搜索算法,对第2阶段得到的可行解进行优化,进一步改进解的质量,以得到原问题的近似最优解.实验表明,所提出算法能够获得问题的一个优质解,同时提供一个紧致下界,用以定量评估解的质量.     

针对QAP问题的改进型蚁群优化算法研究

本文结合二次分配问题(quadratic assignment problem,QAP)的特点,通过分析传统蚂蚁算法在解决QAP问题时收敛过快,精度不高的缺点,提出一种以ACS(ant colony system)为基础的改进蚁群算法――信息素迭代累积ACS(ACS with accumu-lated pheromone by iteration,ACS_API)。新方法通过对定义启发式信息和信息素更新规则的改进,扩大了搜索空间,从而避免过早收敛,陷入局部最优解中。该算法已应用于QAP标准测试数据,并通过与另外两种先前提出的改进蚂蚁算法(HAS_QAP,ACO_GLS)的比较分析得出了它在算法精度和执行时间上的优势。     

基于自适应蚁群算法的车辆路径问题研究

车辆路径问题(VRP)是物流研究领域中一个具有重要理论和现实意义的问题．蚁群算法是一种新型的模拟进化算法,可以很好地解决旅行商问题(TSP)．在分析VRP与TSP区别的基础上,构造了求解VRP的自适应蚁群算法．指出可行解问题是蚁群算法的关键问题,并重点对该问题进行了研究,提出了近似解可行化等解决策略．实验结果表明,自适应蚁群算法性能优良,能够有效地求解VRP问题．     

基于粗糙集的无向图最小支配集启发式算法

图的最小支配集在许多领域有广泛应用,但其求解是一个NP问题.针对现有近似求解算法的复杂度和精度有待改进的问题,基于粗糙集理论提出一种低复杂度、高精度的最小支配集启发式求解算法.首先,利用图的邻接矩阵构造诱导决策表,证明了图的最小支配集与其诱导决策表的最小属性约简等价.然后,提出一种启发式的最小支配集近似算法.该方法采用前向和后向搜索机制,有效提高了最小支配集求解的近似精度;采用累积策略计算诱导决策表的正域,有效降低了计算复杂度.最后,在公用数据集上与典型算法进行了实验对比分析,结果表明该算法在运行效率方面具有明显优势,能得到更高精度的近似最小支配集,且输出结果具有较好的稳定性.     

基于OpenMP求解QAP的并行粒子群优化算法

提出了一种基于OpenMP求解QAP的并行粒子群优化算法.该算法将遗传算法的交叉策略引入PSO算法中,同时采用禁忌搜索算法作为局部搜索算法.在QAPLIB实例上的测试结果表明,并行PSO算法在所有测试实例上都获得了超线性加速比,且运行结果优于串行算法.     

黑白插画中的黑与白

在艺术语言中,黑色和白色是两个最简单的颜色。尽管黑白不像其他颜色那样绚丽多彩,但黑白本身的简约与概括是其他颜色所比不了的,两种颜色之间的互补,形成了简洁而特殊的艺术语言。黑与白是色彩的极至,以黑白入画,以黑白入情,更以黑白入理。黑白插画通过黑、白造型的巧妙变化以及点、线、面的组合来表现形象,简洁的画面、完美的构成、丰富的形态表达了对生活、对生命积极向上的情感。     

赏析电影海报的色彩构图与艺术魅力

电影海报已发展出了商业招贴范畴之外的独特的艺术性,相较于单纯的广告,它更接近电影本身的延伸,以一个固定的画面来表现整部电影的主题,用凝固的视角来观察故事的走向。色彩包括彩色与黑白灰是电影海报最重要的元素之一,色彩的运用很大程度上决定了海报的风格倾向.     

“五个一工程”获奖图书《熊猫史诗》装帧有感

第十一届精神文明建设"五个一工程"(2007～2009)获奖图书《熊猫史诗》是一本描写大熊猫的长篇纪实文学,作者以诗一般的语言、渊博的生态学知识讲述了大熊猫的故事,我为该书所作的装帧设计中,也采用大熊猫这个黑白物种的颜色作基调,黑色的封面背景、黑色的书、黑色的封底、黑色的勒口……在一片黑色中,封面图形——两个可爱的大熊猫露出了白色的脑袋。整个装帧设计显得简洁、醒目,既符合书籍的主题和内涵,又迎合现代的审美情趣,我的设计也得到了作者和编辑的认可。     

浅析黑白装饰设计的创意原理

由于装饰画的主题是以黑白形体的巧妙组合来充分地表现,作者需在黑白装饰及造型的特定的局限中体现自身的悟性和创作动力,但这也是黑白装饰画区别其他艺术形式的特质因素。而点、线、面就成为作者表达观念和创作意图的符号,并在黑白装饰设计中得以确立自己独特的造型语言。     

江南传统民居建筑色彩的成因

民居建筑是在特定文化空间与特定地理环境内产生的独特文化现象。是民族智慧与审美的结晶。民居建筑的规模、结构、装饰的形成演变,是其民族文化发展历程的缩影。建筑与民族文化之间是互为因果的关系。"黑瓦白墙"作为江南传统民居中具有代表性的古典建筑风格,尤具有独特的文化内涵。本文以此为立足点,透过文化属性与地理环境等因素来探析江南传统民居建筑色彩的成因。     

神秘的黑白装饰符号——比亚兹莱的黑白插图分析

在新艺术风格流行的时期,比亚兹莱的黑白插图精致、对比鲜明,充满东方符号的怪诞感,强烈的装饰感,以及他插图中的动、植物神秘的纹样以及优美的充满魔幻气氛的线条,使他的作品一经问世就激起了不小的波澜,并且成为新艺术风格和"颓废主义"的主要体现者。     

灌溉黑白——极色的魅力

所谓"先看颜色后看花"、"七分颜色三分形"的说法都是在描述色彩在整个视觉世界中的重要性。而黑白两色作为色彩的两极,更有着不可忽视的特殊作用。它们之间的对比既强烈有效,又微妙而耐人寻味,不可因为它们"无彩"而有所忽略或局限。     

Android用户隐私保护系统

随着移动互联网的快速发展,手机作为移动互联的重要终端其所受的安全威胁已不亚于传统PC。文章针对目前手机用户的隐私信息(如通讯信息、短信息、通话记录、相册、文件等)泄露这一用户最为关心的问题,在目前主流的手机操作系统Android OS下设计并实现一个用户隐私保护系统。其主要研究和解决Android系统下的恶意进程识别和隐私数据加密两个问题,通过设计黑白名单授权访问隐私数据和实时监控每个进程以及用AES、MD5等算法加密隐私数据,从而达到保护用户隐私的目的。     

博弈算法在黑白棋中的应用

计算机博弈是一种对策性游戏,是人工智能的主要研究领域之一,它涉及人工智能中的搜索方法、推理技术和决策规划等。目前广泛研究的是确定的、二人、零和、完备信息的博弈搜索。文中通过一个黑白棋程序的设计,将生成的博弈树节点的估值过程和对博弈树搜索过程相结合,采用传统的Alpha-Beta剪枝和极大-极小原则方法给出了博弈程序设计的核心内容:包括博弈树搜索和估值函数两个方面,提出了对原算法的一种改进,该算法提高了搜索速度。实验结果验证了算法的有效性。     

一种复合的双引擎智能垃圾邮件过滤方法

研究了几种常用的垃圾邮件过滤算法,分析了这几种方法在邮件过滤应用中各自的优缺点.根据这几种算法的优缺点,对它们进行改良与结合,并增加了通过查看发出的邮件内容进行自动学习的机制;同时针对中英文垃圾邮件采用不同的学习算法,从而建立一个适用中英文环境的垃圾邮件过滤方法.实验表明,该方法的效率和性能达到了较好的水平.