参数化弧相容约束传播

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

Knapsacks约束的弧相容改进算法

通过修改背包约束弧相容算法的数据结构,将点阵图改为有向图,解决了原背包约束弧相容算法中存在冗余计算和无效操作的问题,加快了算法对问题的求解效率.对比实验结果表明:在面对同一类问题时,因为数据结构更复杂,改进算法的初始化时间虽增加,但求解时间提高了20%~50%;在面对求解难度较高的问题时,改进算法能更好地缩减求解问题的时间.     

一种笛卡尔积压缩的负表约束上表缩减算法

利用笛卡尔积压缩方法可有效减小负表约束规模的原理, 提出一种在压缩负表上维持广义弧相容的高效算法STRC-N, 以解决负表约束维持弧相容过程中遍历所有元组导致效率低的问题. 实验结果表明, 当压缩负表上压缩率较大时, 得益于表规模的减小, 新算法相对于主流的负表约束处理算法效率更高, 性能更好, 从而实现了对负表约束处理算法的改进.     

约束满足问题求解及ILOG SOLVER系统简介

首先综述求解约束满足问题的基本算法和搜索策略, 然后介绍ILOG SOLVER求解系统提供的类和函数的基本组成, 并给出用该系统求解的两个地图着色示例.     

加强的混合遗传算法求解能力约束弧路径问题

为了在可接受的时间里求解具有NP-hard性质的能力约束弧路径问题(CARP),提出了加强的混合遗传算法(EHGA). 该算法是在遗传算法框架里嵌入加强的局域搜索算子来强化搜索,充分发挥了遗传算法的全局搜索能力和加强的局域搜索算子的局域搜索能力. 同时,在进行种群替代时,二元锦标赛替代被提出,并使用了种群管理来保持种群的多样性.测试了标准CARP算例,并给出了算法效果比较. 结果表明,加强的混合遗传算法胜出一般的Memetic算法,是有效的求解CARP的方法.     

一种面向变量传播的弧一致性算法

在AC-3算法的基础上,提出了采用面向变量的约束传播机制新的弧一致性算法(Improved-AC3),算法(Improved-AC3)完全脱离附加的数据结构,使得程序的空间复杂度非常小,也避免了新算法在维护数据结构上的开销,是一种空间复杂度优先的通用弧一致性算法.新算法对于通用弧一致性算法的改进效果是明显的,是对现有弧一致性算法的提高和完善,使其实用性更好,应用前景更宽.     

多起始点进化算法在容量约束弧路径问题上的应用

容量约束弧路径问题(CARP)是一类NP难的组合优化问题,通常采用启发式算法求解,计算时间较长.本文在竞争模因算法基础上采用多点同时搜索,构造了多点进化算法(MSEA).算法由多个初始解开始,同时进行局部搜索与遗传进化,再将结果合并,得到最终的解.在29个基准数据集上的数值试验表明,该算法可行有效,并可以节省大量计算时间.     

一种基于Minmax算法的混合MIMIC算法

将Minmax算法与MIMIC算法相结合,提出一种基于Minmax算法的混合MIMIC算法.该算法不再利用传统的约束保持法和可行规则法处理约束条件,而是结合Minmax算法的思想将约束问题转化为无约束问题,并利用MIMIC算法对无约束问题求解.数值试验结果表明:该算法能收敛到满足约束条件的全局最优解,并且具有很强的全局搜索能力,为解决非线性约束优化问题提供了一种新的有效途径.     

基于分布式约束满足的产品配置研究

针对分布式网络化产品配置的特点,将产品配置问题抽象为约束满足问题进行研究.为解决配置知识共享及配置知识的语义表达问题,采用本体驱动的面向对象的思想构建产品配置约束网络结构模型,将该模型转化为分布式约束满足问题(Distributed Constraint Satisfaction Problem,DCSP)求解模型,从而可以准确、完全地描述产品零部件的结构及设计知识,并采用异步弱授权回溯算法进行约束求解,大大提高了求解的搜索效率和准确性.最后给出模型在水泵产品配置设计过程中的实际应用.     

基于记忆策略的动态分解约束多目标进化算法

针对现有面向多目标优化问题的约束处理方法存在求解效率不足,基于分解策略的多目标进化算法受到约束限制导致求解性能低的问题,提出一种基于记忆策略的动态分解约束多目标进化算法.本文首先引入具有记忆功能的归档集,改进基于短暂忽略非容许解的约束处理方法,提高算法的求解鲁棒性.然后结合基于分解的多目标进化算法,设计一种动态分配搜索...     

无环配置问题研究

基于约束的配置问题提出一种无回溯搜索算法,通过弧相容技术将所有不相容的值删除,指导用户进行产品配置,并对其正确性进行了证明.探讨了将目前两种主流计算冲突解释方法应用到无环配置问题的可行性.     

稀疏二元约束满足问题的环割集粒子群算法

提出了一个基于环割集的粒子群算法求解稀疏二元约束满足问题,把环割集和粒子群算法结合在一起,利用环割集减少粒子群算法中粒子的维数。用随机的稀疏二元约束满足问题进行实验,结果表明改进后的粒子群算法是有效的,迭代次数约为原算法的十分之一,运行时间比原算法运行时间少约7倍。     

Consistent Algorithm for Multi-value Constraint with Continuous Variables

Mature algorithms for the Constraint Satisfaction Problem (CSP) of binary constraint with discrete variables have already been obtained for the application. For the instance of multi-value constraint with continuous variables, the approach will be quite different and the difficulty of settling will aggrandize a lot. This paper presents the algorithm for realizing global consistency of continuous variable. And this algorithm can be applied to multi-value constraint.     

Introduction

ＩｎｔｒｏｄｕｃｔｉｏｎＴｈｅＣｏｎｓｔｒａｉｎｔＳａｔｉｓｆａｃｔｉｏｎＰｒｏｂｌｅｍ（ＣＳＰ）ｗａｓｆｉｒｓｔｄｅｖｅｌｏｐｅｄｆｏｒｓｅｔｌｉｎｇｔｈｅｃｏｎｓｔｒａｉｎｔｂｅｔｗｅｅｎｄｉｓｃｒｅｔｅｖａｒｉａｂｌｅｓ．Ｍａｎｙａｌｇｏｒｉｔ...     

基于SFLA-PSO算法的几何约束求解

为提高求解几何约束问题的效率和收敛性,将几何约束问题等价为求解非线性方程组问题。并将约束问题转化为一个优化问题,采用基于混洗蛙跳（SFLA：Shuffled Frog Leaping Algorithm）和粒子群优化（PSO：Particle Swarm Optimization）算法求解该问题。SFLA-PSO算法采用将SFLA和PSO二者相结合的方法,利用PSO算法进行族群局部搜索,利用SFLA的多种群的进化方法进行族群的混选,相互取长补短,以达到收敛速度快和全局搜索的目的。实验表明,该方法可以提高几何约束求解的效率和收敛性。     

多学科协同优化方法的分析与改进

深入分析了标准协同优化、动态松弛协同优化和两阶段协同优化方法的几何特性,进而比较了各自的优化特性.针对协同优化对初始点敏感的问题,通过增加总体一致性约束的方法,提出了基于先验约束法的SGO方法.针对设计变量数量级相差较大的协同优化问题,为了提高学科间的一致性,给出了基于加权方法的学科间一致性约束表示式.最后,通过悬臂梁...     

结合Separator的约束满足问题树分解方法

基于树分解的回溯搜索算法, 结合separator分解算子提出一种新的搜索算法BTD⁺-MAC. 该算法在搜索时, 优先选择separator中的变量进行相容性检查和实例化, 由于树宽度的减小能提高约束传播的效率, 进而提高问题求解效率. 对几组benchmark问题进行测试, 测试结果表明, 该算法在问题求解效率上超过了MAC3rm算法和BTD-MAC算法.