基于值序的二元约束满足问题粒子群算法

提出了一个基于最小冲突启发式值序的二元约束满足问题粒子群算法，利用值序对值的选取方式代替随机选择的盲目搜索方式，使群体在探索解空间的时候，选择有希望能找到全局解的地方搜索。使用随机约束满足问题的实验表明，改进后的算法比原算法能以更快的速度收敛到全局解，无论在迭代次数还是运行时间上均能数倍提高算法的效率。     

基于元胞粒子群算法的数控切削参数优化

针对数控切削参数优化问题的非线性和多约束性质,采用一种元胞粒子群算法（CPSO）进行优化。在基本粒子群算法（PSO）思想的基础上,引入邻居的概念,以搜索解空间的局部信息,并将粒子的信息交流范围扩展到种群外部,从而能搜索到更有希望的解空间;在罚函数机制的基础上,引入标志变量记录粒子是否曾经满足过所有约束条件,根据标志变量进行粒子个体极值与种群全局极值的更新。通过比较CPSO算法与其他算法取得的结果,验证该算法解决数控切削参数优化问题的有效性和优越性。     

加权约束满足问题的符号ADD求解算法

加权约束满足问题(WCSP)是一类软约束满足问题。给出WCSP的代数决策图(ADD)描述,以及基于ADD的两种符号求解算法。首先,通过对变量和变量域值的二进制编码,给出软约束图的ADD表示。其次,将分支定界搜索算法与桶消元算法及符号ADD技术相结合,在静态变量序下,利用结点一致性预处理技术,对WCSP问题进行符号ADD求解。通过引入有向弧一致性计数技术提高符号ADD算法的搜索下界,对符号ADD求解算法作了改进。最后,对大量随机生成的测试用例进行实验分析。结果表明,文中算法在性能上明显优于带有存在有向弧一致性或结点一致性预处理技术的具有前向检查功能的深度优先分支定界搜索算法。     

一种求解二元约束满足问题自适应粒子群算法

提出了一种求解二元约束满足问题的自适应粒子群算法（SAPSO）,其中每个粒子具有两种状态,定义了一个反应粒子活跃程度的变量以决定粒子所属的状态。为了平衡粒子不同进化阶段的开发和探测能力,在SAPSO中引入了随着每个粒子的进化状态和粒子群的进化状态动态改变的惯性权重。利用自适应的选取方式代替随机选择的盲目搜索方式,使群体在解空间搜索时,能够自适应地去探索新的区域,选择有希望找到更优解的地方搜索。使用随机约束满足问题的实验表明,改进后的算法比原算法（PS-CSP）能以更快的速度收敛到全局解。算法的效率大约提高两倍,平均迭代次数大约为原来的一半。     

多UCAV 任务分配的混合遗传算法与约束处理

针对多UCAV协同作战任务分配问题，建立了多目标整数规划模型，提出了基于整数编码的混合遗传算法．将约束分为全局约束和局部约束，根据局部约束将决策变量分为自由变量和非自由变量，仅对非自由变量进行编码，减少了染色体变化要素．设计了交叉算子和变异算子，以提高个体的约束满足率．以UCAV的SEAD任务为想定进行仿真，实验结果表明，该混合遗传算法可有效解决大规模整数规划问题，在求解效率和约束满足率上比标准遗传算法有显著提高．     

一种基于粒子群算法求解约束优化问题的混合算法

通过将粒子群算法(PSO)与差别进化算法(DE)相结合，提出一种混合算法PSODE，用于求解约束优化问题．PSODE是在PSO算法中适当引入不可行解，将粒子群拉向约束边界，加强对约束边界的搜索，同时与DE算法结合以加强搜索能力．基于典型高维复杂函数的仿真表明，该算法简单高效，鲁棒性强．     

一种基于熵的OBDD变量排序算法

有序二叉决策图（OBDD）是一种有效表示布尔函数的数据结构，其大小依赖于所采用的变量序。熵是定量描述布尔函数中变量重要性的一种方法。基于变量的熵值分析了高质量变量序的特征，给出了一种基于熵的OBDD变量排序算法。实验结果表明：该算法与模拟退火算法和遗传算法结果相当。时间仅为相应算法的80．84％和29．79％。     

基于量子粒子群优化的多波束卫星联合资源分配算法

当使用元启发式算法求解多波束卫星联合资源分配问题时,时延约束和容量约束会导致计算复杂度增大,且算法难以收敛。对此,通过在目标函数中引入惩罚机制,在无效解的目标函数值加入了惩罚值,使得算法的优化解自适应地满足这两个约束。在此基础上,提出了基于量子粒子群优化的联合资源分配算法。仿真结果表明,惩罚策略的引入解决了应用元启发式算法时,难以处理时延约束和容量约束的问题,而带有惩罚机制的量子粒子群算法在分配公平性指数、总系统容量上均优于已有联合分配算法。     

基于约束满足的热轧批量计划模型与算法

将热轧批量计划问题作为一个约束满足问题处理，建立不确定计划数的VRPSTw约束满足模型．在求解过程中．先用约束满足的一致性技术过滤变量的值域，收缩搜索空间；然后用变量选择和值选择构造轧制计划的解．为变量赋值之后，实施约束传播，保证每块板坯只被访问一次并动态禁止子回路．在已有的解的基础上，应用基于禁忌的k-opt互换改进解的质量．数据实验证明模型和算法是有效的．     

核函数K-粒子滤波算法研究

针对粒子滤波易出现粒子退化这一问题,引入核函数K,提出一种核函数K粒子滤波算法.根据粒子滤波中重采样得到的粒子集合的概率特征,设计合适的核密度K(·)和核带宽h,使得真实的后验概率密度与对应的K估计之间的均方误差均值最小.通过设计的核函数模拟离散分布重建它的连续分布,然后从后验分布的连续近似中重新获得重采样粒子,从而保证粒子的多样性,抑制粒子退化.将提出的KPF算法与PF算法应用到单变量非静态增长模型和SINS/SAR组合导航系统中,通过仿真验证结果表明,提出的KPF算法能改善滤波性能,进一步提高解算精度.     

The distributed constraint satisfaction problem: formalization andalgorithms

We develop a formalism called a distributed constraint satisfaction problem (distributed CSP) and algorithms for solving distributed CSPs. A distributed CSP is a constraint satisfaction problem in which variables and constraints are distributed among multiple agents. Various application problems in distributed artificial intelligence can be formalized as distributed CSPs. We present our newly developed technique called asynchronous backtracking that allows agents to act asynchronously and concurrently without any global control, while guaranteeing the completeness of the algorithm. Furthermore, we describe how the asynchronous backtracking algorithm can be modified into a more efficient algorithm called an asynchronous weak-commitment search, which can revise a bad decision without exhaustive search by changing the priority order of agents dynamically. The experimental results on various example problems show that the asynchronous weak-commitment search algorithm is, by far more, efficient than the asynchronous backtracking algorithm and can solve fairly large-scale problems     

Static and dynamic structural symmetry breaking

We reconsider the idea of structural symmetry breaking for constraint satisfaction problems (CSPs). We show that the dynamic dominance checks used in symmetry breaking by dominance-detection search for CSPs with piecewise variable and value symmetries have a static counterpart: there exists a set of constraints that can be posted at the root node and that breaks all the compositions of these (unconditional) symmetries. The amount of these symmetry-breaking constraints is linear in the size of the problem, and yet they are able to remove a super-exponential number of symmetries on both values and variables. Moreover, we compare the search trees under static and dynamic structural symmetry breaking when using fixed variable and value orderings. These results are then generalised to wreath-symmetric CSPs with both variable and value symmetries. We show that there also exists a polynomial-time dominance-detection algorithm for this class of CSPs, as well as a linear-sized set of constraints that breaks these symmetries statically.     

A novel global harmony search algorithm for reliability problems

Inspired by the swarm intelligence of particle swarm, a novel global harmony search algorithm (NGHS) is proposed to solve reliability problems in this paper. The proposed algorithm includes two important operations: position updating and genetic mutation with a small probability. The former enables the worst harmony of harmony memory to move to the global best harmony rapidly in each iteration, and the latter can effectively prevent the NGHS from trapping into the local optimum. Based on a large number of experiments, the proposed algorithm has demonstrated stronger capacity of space exploration than most other approaches on solving reliability problems. The results show that the NGHS can be an efficient alternative for solving reliability problems.     

Discrete particle swarm optimization based on estimation of distribution for polygonal approximation problems

The polygonal approximation is an important topic in the area of pattern recognition, computer graphics and computer vision. This paper presents a novel discrete particle swarm optimization algorithm based on estimation of distribution (DPSO-EDA), for two types of polygonal approximation problems. Estimation of distribution algorithms sample new solutions from a probability model which characterizes the distribution of promising solutions in the search space at each generation. The DPSO-EDA incorporates the global statistical information collected from local best solution of all particles into the particle swarm optimization and therefore each particle has comprehensive learning and search ability. Further, constraint handling methods based on the split-and-merge local search is introduced to satisfy the constraints of the two types of problems. Simulation results on several benchmark problems show that the DPSO-EDA is better than previous methods such as genetic algorithm, tabu search, particle swarm optimization, and ant colony optimization.     

迭代粒子群算法及其在间歇过程鲁棒优化中的应用

针对无状态独立约束和终端约束的间歇过程鲁棒优化问题，将迭代方法与粒子群优化算法相结合，提出了迭代粒子群算法．对于该算法，首先将控制变量离散化，用标准粒子群优化算法搜索离散控制变量的最优解．然后在随后的迭代过程中将基准移到刚解得的最优值处，同时收缩控制变量的搜索域，使优化性能指标和控制轨线在迭代过程中不断趋于最优解．算法简洁、可行、高效，避免了求解大规模微分方程组的问题．对一个间歇过程的仿真结果证明了迭代粒子群算法可以有效地解决无状态独立约束和终端约束的间歇过程鲁棒优化问题．     

带偏向性轮盘赌的多算子协同粒子群优化算法

针对粒子群优化算法在处理高维、大规模、多变量耦合、多模态、多极值属性优化问题时易早熟收敛等性能和技术瓶颈,基于粒子群优化算法行为学习算子和3种不同学习偏好的差分变异算子,建立带偏向性轮盘赌的多算子选择与融合机制,提出一种带偏向性轮盘赌的多算子协同粒子群优化算法MOCPSO.MOCPSO针对迭代粒子群榜样粒子集,首先通过对迭代种群及其榜样粒子集优劣分组,同时采用轮盘赌分别为每组榜样粒子集选配不同学习偏好的变异算子,并为每组榜样粒子适配差分基向量和最优基向量,预学习并优化迭代种群及其榜样粒子,以权衡算法的全局探索和局部开发;然后通过合并所有子种群,并结合粒子群优化算法行为学习算子,指导迭代种群状态更新,以提高算法的全局收敛性;最后结合精英学习策略,对群体历史最优进行高斯扰动,以提高算法的局部逃生能力,保障算法收敛的多样性.实验结果表明,MOCPSO算法与5种先进的同类型群智能算法在求解CEC2014基准测试问题上具备竞争力,且有更强的优化特性.     

Structural decompositions for problems with global constraints

A wide range of problems can be modelled as constraint satisfaction problems (CSPs), that is, a set of constraints that must be satisfied simultaneously. Constraints can either be represented extensionally, by explicitly listing allowed combinations of values, or implicitly, by special-purpose algorithms provided by a solver. Such implicitly represented constraints, known as global constraints, are widely used; indeed, they are one of the key reasons for the success of constraint programming in solving real-world problems. In recent years, a variety of restrictions on the structure of CSP instances have been shown to yield tractable classes of CSPs. However, most such restrictions fail to guarantee tractability for CSPs with global constraints. We therefore study the applicability of structural restrictions to instances with such constraints. We show that when the number of solutions to a CSP instance is bounded in key parts of the problem, structural restrictions can be used to derive new tractable classes. Furthermore, we show that this result extends to combinations of instances drawn from known tractable classes, as well as to CSP instances where constraints assign costs to satisfying assignments.     

Algorithms for Distributed Constraint Satisfaction: A Review

When multiple agents are in a shared environment, there usually exist constraints among the possible actions of these agents. A distributed constraint satisfaction problem (distributed CSP) is a problem to find a consistent combination of actions that satisfies these inter-agent constraints. Various application problems in multi-agent systems can be formalized as distributed CSPs. This paper gives an overview of the existing research on distributed CSPs. First, we briefly describe the problem formalization and algorithms of normal, centralized CSPs. Then, we show the problem formalization and several MAS application problems of distributed CSPs. Furthermore, we describe a series of algorithms for solving distributed CSPs, i.e., the asynchronous backtracking, the asynchronous weak-commitment search, the distributed breakout, and distributed consistency algorithms. Finally, we show two extensions of the basic problem formalization of distributed CSPs, i.e., handling multiple local variables, and dealing with over-constrained problems.     

一个基于最小冲突修补的动态约束满足求解算法

约束满足问题是人工智能中一个重要的研究方向,近年来,对动态变化的约束满足问题的研究逐渐成为该领域的热点.在目前该领域最流行的LC算法基础上,引入禁忌搜索策略,提出了一个基于最小冲突修补的算法Tabu_LC.算法在每次冲突调整时将所有冲突变量看成一个整体,并采用分支定界搜索策略求解冲突变量组成的子问题,极大地提高了求解效率.同时,在约束求解系统"明月1.0"架构下给出了算法的具体实现,并针对大量随机问题进行了对比实验.结果表明,Tabu_LC算法在求解效率和解的质量上都明显优于LC算法.     

Symmetry Breaking Constraints for Value Symmetries in Constraint Satisfaction

Constraint satisfaction problems (CSPs) sometimes contain both variable symmetries and value symmetries, causing adverse effects on CSP solvers based on tree search. As a remedy, symmetry breaking constraints are commonly used. While variable symmetry breaking constraints can be expressed easily and propagated efficiently using lexicographic ordering, value symmetry breaking constraints are often difficult to formulate. In this paper, we propose two methods of using symmetry breaking constraints to tackle value symmetries. First, we show theoretically when value symmetries in one CSP correspond to variable symmetries in another CSP of the same problem. We also show when variable symmetry breaking constraints in the two CSPs, combined using channeling constraints, are consistent. Such results allow us to tackle value symmetries efficiently using additional CSP variables and channeling constraints. Second, we introduce value precedence, a notion which can be used to break a common class of value symmetries, namely symmetries of indistinguishable values. While value precedence can be expressed using inefficient if-then constraints in existing CSP solvers, we propose efficient propagation algorithms for implementing global value precedence constraints. We also characterize several theoretical properties of the value precedence constraints. Extensive experiments are conducted to verify the feasibility and efficiency of the two proposals.