基于AC与LmaxRPC的自适应约束传播求解算法

在现有自适应约束求解方法基础上,提出一种新的自适应约束传播求解算法ADAPTAC-LmaxRPC.该算法能根据约束的不同特性,在传播能力强但开销高的LmaxRPC与传播能力弱却开销低的AC之间自适应地切换进行约束传播.多个Benchmark实例类上的测试实验数据表明,ADAPTAC-LmaxRPC算法有效地平衡了求解效率和算法开销之间的矛盾,大幅度提高了约束求解的效率.     

参数化弧相容约束传播

为进一步提高约束满足问题求解算法的效率,对约束传播过程进行了分析,并使用变量论域缩减比例对弧相容传播深度进行参数化描述,同时提出了一个约束传播程度可以控制的弧相容传播算法,研究了在不同参数下约束求解算法的效率。该算法在“明月1.0”架构下实现。实验结果表明,约束传播程度是影响算法求解效率的一个重要因素,通过调整控制参数可以使算法效率提高3~4倍。     

基于权值加密的隐私安全分布式约束满足问题求解

隐私安全的分布式约束满足问题(distributed constraint satisfaction problem,DisCSP)求解算法可以很好地满足信息敏感的分布式组合求解问题的需要,为了获得更好的求解效率,提出了一种基于权值加密的隐私安全DisCSP的求解算法,对DisCSP问题中的约束基于不同的隐私权值进行加密求解;不需要增加额外的agent进行隐私约束的一致性检查,实现分布式的安全求解策略;对于可能出现的推理信息,用随机选择策略来避免信息泄漏.试验表明,该算法可以减少信息的传递量和计算的复杂性,因而具有更好的求解效率.     

混合业务下基于能效准则的基站开/关选择策略

为提升无线系统的能效,针对用户随时间的潮汐变化特点,文中提出了一种通过基站开关切换提升系统能效的方法——基于能效准则的基站开/关选择策略,将用户业务分为恒定比特率业务和可变比特率业务,在满足恒定比特率业务的约束下最大化能源效率.文中采用改进的自适应遗传算法来求解此约束优化问题,即基站开关状态用二进制编码,通过设计的选择、交叉、变异实现迭代寻优.仿真结果表明:文中提出的改进遗传算法收敛速度快,能有效对抗染色体群体的早熟问题;在满足恒定比特率用户需求的前提下,文中策略可有效地提升无线系统的能效,其性能接近穷举算法.     

基于蚁群算法的并行任务分配与调度

蚁群算法是近年出现的一种新启发式算法,在求解NP完全问题中具有较大优势.针对如何在满足任务约束关系的条件下用蚁群算法求解任务分配与调度问题,首先对任务的分配与调度问题建立数学模型,然后在满足子任务之间的约束关系的条件下用蚁群算法求出最优解,最后把用蚁群算法与遗传算法的最优解进行比较.通过仿真实验表明,蚁群算法比遗传算法在任务分配与调度求解中有较高的解的质量,但蚁群算法的求解速度要慢于遗传算法.     

多约束装配线平衡问题的知识驱动系统控制启发式算法

针对一类以加强边要求、位置要求和消极区域要求为约束,以最小化装配线节拍和不满足弱位置要求操作的项数为目标,生产调度领域中普遍存在的第2类多约束装配线平衡问题,基于各类约束的特征以及它们之间相互耦合的关系等知识,系统设计各类约束得到满足的整体主动控制启发式规则,提出一种知识驱动系统控制启发式算法,对问题进行有效求解,获得...     

再制造系统能力约束下拆卸批量计划优化方法

针对再制造系统中能力约束下的拆卸批量计划问题,应用两阶段启发式遗传算法进行了优化求解.首先对再制造产品结构进行了描述,建立了再制造系统中能力约束下的拆卸批量计划优化模型;其次在不考虑能力约束情况下应用遗传算法求解出初始的拆卸批量计划,其中,染色体编码采用拆卸决策变量来表示,同时对适应度函数进行了线性变换,设计了具有自适应的交叉概率和变异概率;然后应用转移算法对初始得到的批量计划进行了修正,使其符合拆卸能力的约束.大量随机算例的仿真实验说明所提出的算法不论在寻找最优解方面还是在求解速度和稳定性方面,都要大大优于精确算法,能够较好地解决实际生产中面临的拆卸批量计划问题.     

求解度约束最小生成树的一种启发式方法

针对网络设计和优化中度约束最小生成树问题,提出了一种基于贪心思想的启发式算法求解度约束最小生成树.在最小生成树的基础上,将超过度约束的顶点降低度数使之满足度约束条件.经大量数据测试并与其他算法进行比较,表明了该算法的有效性和通用性.     

一种遗传算法求约束优化问题的新方法

为了更好的解决约束优化问题,介绍了利用遗传算法求解约束优化问题的一般方法,在分析传统方法的基础上提一种遗传算法求解约束优化问题的新方法,将约束优化问题分成两步:首先不考虑目标函数,把约束优化问题转换为一个约束满足问题来处理,获得一个可行解;然后对目标函数和已满足约束的条件进行优化,最终获得一个最优解。还对该方法在不同问题下作了分析,证明了该方法对求解有约束优化问题有良好性能。     

用一种改进遗传算法求解带时延约束的组播路由问题

提出一种改进的遗传算法,用以求解带时延约束的组播路由问题.该算法综合考虑了路由费用和路由时延,并给出了一种适应度评价函数,在算法中采用了最佳个体保留、自适应交叉以及非线性排序选择等多种优化机制.仿真结果表明,该算法是可行的,有效的.     

Efficient Heuristic Variable Ordering of OBDDs

Introduction　　Orderedbinarydecisiondiagrams(OBDDs)[1]areefficientrepresentationsofBooleanfunctions.However,thesizeofOBDDsdependsheavilyonvariableordering[1].HowtofindasatisfyingvariableorderisthuscrucialtotheapplicationofOBDDs[211].HeuristicanddynamicmethodsarewidelyusedinorderingthevariablesforOBDDs.Heuristicmethodsusetheinformationimpliedinthecircuitstructure,whiledynamicmethodsimprovethevariableordergraduallyongivenOBDDs.Althoughadynamicmethodmaygivebetterresults,itsruntimedepen…     

网络可靠度BDD分析中2种边排序策略的性能比较

网络可靠度二元决策图（BDD）分析过程包含边排序、BDD生成和可靠度评估3个步骤,其中BDD生成和可靠度评估的计算复杂度和BDD尺度线性相关,而BDD尺度取决于边排序．因此,边排序问题是研究网络可靠度BDD分析的核心．在实现广度优先和深度优先2种边排序策略的基础上,针对规则网络（N＊N型和M＊N型）,比较了这2种策略的分析性能．实验数据表明：1）规则网络中广度优先边排序策略优于深度优先边排序策略;2）当M〉N时,广度优先边排序策略在M＊N型网络中的性能表现优于与之等价的N＊M型网络．这些结论为设计更优的启发性边排序策略提供了重要依据．     

基于循环取料的不确定越库调度模型与算法

研究运输时间不确定环境下基于循环取料的越库调度问题.对问题建立不确定情况下求解该问题的混合整数规划模型;提出2阶段启发式算法和基于禁忌搜索算法的改进算法来获得近似最优解;通过在小规模和大规模情形下进行数值实验,验证了启发式算法的有效性.     

基于构造的布局启发方法

布局问题属于ＮＰ完全问题已知被研究多年,关于它的求解方法多为启发式方法,本文在分析了布局问题特性的基础上,提出了一种基于构造的布局启发方法,该方法既考虑到布局总问题的不干涉的约束及又考虑了其它的布局约束,从而更加全面,准确地指导布局求解的进行,本文还首次提出了“虚容器”的概念,从而使定序函数和定位函数的计算易于进行。     

遗传算法参数自适应控制的新方法

根据遗传算法参数自适应控制方法的不同分类,采用基于启发式规则的参数控制方法对遗传算法的种群数进行了宏观调控和微观调控。并采用不同特点的模糊控制器分别控制交叉率和变异率,使种群数、交叉率和变异率都能够随进化的实际情况发生自动调整,形成了一种新的种群数变化的模糊自适应遗传算法。实验数据表明这种算法能够有效防止遗传算法早收敛,同时也说明对参数进行自适应控制能够使遗传算法性能大大提高。     

大规模项目调度问题的分解和协调优化方法

为了解决大规模有资源约束的项目调度问题,提出一种串行分解和并行分解相结合的项目逐层分解方法,以便克服精确算法求解时间不可接受,而启发式算法解的质量较差的问题。根据该分解方法特点,提出基于采样选择的启发式协调方法,以及基于分枝定界方法的精确底层调度的子项目协调优化算法,并通过仿真分析了关键参数的选取。仿真结果表明,该算法解的平均质量明显优于相关启发式算法,并且求解时间能够满足工程上的要求,能够有效地提高大规模项目调度问题的求解质量,具有实用价值。     

时变需求订货批量问题的相关策略

根据EOQ和时变需求量把计划期内各时间段分为常态时间段和非常态时间段,提出求解时变需求订货批量问题的相关策略·从理论上分析了独立策略、非常态独立策略与几种相关策略的性能,得到了相关策略的最优结构·提出了基于相关策略的启发式算法求解计划期初是常态时间段的订货批量问题·该启发式对计划期内有多个常态时间段的EOQ问题比SM有效·     

一个并发约束程序设计语言的定义与实现

设计实现了并发约束程序设计语言COPS.该语言结合约束对象、不确定性计算及约束储仓技术,采用基于并发约束模型的推理控制和基于优先度的规则选择策略,将说明性的知识表示、系统化和启发式的推理搜索能力以及合理的确定性计算开销统一起来.系统在电路建模、专家决策等领域的初步应用表明了该语言对构造基于约束的知识系统的适用性.COPS的出现为复杂智能问题的解决提供了可能性.     

工期约束条件下资源均衡问题的研究综述

阐述了工期约束条件下资源均衡问题的研究发展过程,从解析法、传统的启发式算法到智能类算法和最新的微粒群算法,这些算法的产生提高了计算效率,提升了优化效果,在工程管理中发挥重要作用。优化算法之间的结合,优势互补,将成为今后的一个重要研究方向。     

面向大数据的超启发式SVM的网络安全框架研究

大数据环境下,为了提高支持向量机(support vector machines, SVM)在网络安全应用环境下的性能,提出了面向大数据的超启发式SVM网络安全框架。所提超启发式SVM框架由SVM和超启发式框架组成,超启发式框架的作用是生成配置参数,并将其发送到SVM,SVM使用生成的配置来解决给定的问题,然后将成本函数发送到超启发式框架。超启发式框架分为高层策略和低层启发式,高层策略具有搜索性能,可以控制选择低层启发式并生成新的SVM配置;低层启发式算法构成了一组特定于问题的启发式算法,使用不同的规则实现对SVM配置搜索空间的探索。该框架自适应地集成了基于分解和基于Pareto方法的优点,近似SVM配置的Pareto集,解决了启发式框架的优化问题。实验结果表明,所提框架性能优于其他算法,说明框架的有效性。