基于聚类分解的WCDMA基站布局规划算法

针对大规模WCDMA无线网络基站布局规划问题，提出一种基于聚类分解的分层算法．在聚类分解中，以测试点信号增益矩阵构造聚类分解数据，并给出了收敛判定函数和相似度计算方法．在分层算法中，首先用K均值聚类将原问题分解为K个子规划问题，然后对各子问题求解整数规划问题，最后对各子问题的基站布局结果进行全局调整．仿真计算验证了该算法的有效性．     

加权约束满足问题的改进RDS符号代数决策图求解算法*

加权约束满足问题(WCSP)是一类约束最优化问题.文中基于RDS思想,从减少RDS分解的子问题个数及提高各个子问题的求解效率入手,提出WCSP的改进RDS符号代数决策图(ADD)求解算法.通过改进最多约束变量的变量选择法,引入RDS变量引导原问题的子问题分解,进而减少RDS中分解的子问题个数.利用变量的后向度,进一步改进子问题的分解方法.为提高各个子问题的求解效率,利用桶消元算法并结合ADD操作消去子问题中的非RDS变量,进而减少子问题中的变量个数,提高深度优先分支界定法的下界.在大量随机生成的测试用例上的实验证明文中算法的优越性.     

基于协同进化博弈的多学科设计优化

复杂系统的设计问题可以非层次分解为并行的多个子空间优化设计问题。多学科优化的迭代过程可看成子空间博弈的过程。各冲突子目标协商一致条件下,子空间合作博弈的均衡点能达成原系统的整体最优,并给出协同进化算法求解博弈的Nash均衡点的计算框架。以某型民用客机的总体优化设计为例,将其分解成气动和重量两个子空间优化。设计变量不重叠地分布于各子空间,两冲突子目标分配相同权值,线性加权组合而形成的单目标作为各子空间共同的优化目标。计算结果表明此方法是有效的。     

基于动态约束网络的约束优化分解

约束网络通过对较大规模的任务和问题的分解，传递了并行工程产品开发过程中的各多功能小组之间必然存在的相互制约、相互依赖的关系。在任务和问题简单分解的过程中，由于所得到的子问题之间通常是不能完全独立的，因而只能在有限程度上降低难度、简化问题。在分析了约束求解的研究现状和不足的基础上，提出了一种基于动态约束的约束优化分解方法，使得各个子任务、子问题间的关系得到进一步的分解，从而在满足原要求的基础上，得到优化的结果。     

复杂并行机调度问题基于分解的优化算法

针对纺织生产过程中广泛存在的带特殊工艺约束的大规模并行机调度问题，提出了一种基于分解的优化算法。首先将原调度问题分解为机台选择和工件排序两个子问题，然后针对机台选择子问题提出一种进化规划算法，并采用一种具有多项式时间复杂度的最优算法求解工件排序子问题，以得到问题特征信息（即每台机器对应拖期工件数的最小值），该问题特征信息用以指导进化规划算法的迭代过程。不同规模并行机调度问题的数值计算结果及实际制造企业应用效果表明，本文提出的算法是有效的。     

利用分治技术的智能推理

一、引言“分治”技术是一种分解-合成技术,即对于复杂的不能直接求解的问题,将该问题分割成几个子问题,分别求解子问题,然后合成子问题的解,以获取整个问题的解。若分割出的子问题仍不易求解,则继续分解子问题,一直到可以直接求解为止。因此,这是一个递归模式。同样,人工智能在求解难题时,常常将难题分解为较为简单的子问题,然后合成各个子问题的解决方案,形成一个整体方案。本文通过描述分治技术在基于类比推理、基于事例推理以及基于原型推理的应用,表明了该技术在智能推理中的有效性和灵活性。     

浅析动态规划的技巧和窍门

我们知道,动态规划是计算机编程中十分常用的一种算法。它的基本思想是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。值得注意的一点是,经分解得到的子问题往往不是相互独立的。那么动态规划算法中有哪些技巧以及窍门可以帮助我们更加顺利地解决问题呢?笔者就用几个OnlineJudge网站上的一些比较有代表性的题目作为例子,结合自己的一点心得体会,向读者讲授这些技巧和窍门。     

启发式列生成算法求解带恶化效应的同构并行机调度问题

针对实际生产中广泛存在的一类带恶化效应的同构并行机调度问题,以最小化最大完工时间为优化目标,构建该问题的整数规划模型,并提出一种启发式列生成算法(HCGA)进行求解.在HCGA中,首先,利用Dantzig-Wolfe分解方法,将原问题分解为一个主问题(MP)和多个子问题;然后,设计启发式算法获得初始列,其中每列为一台机器上的一个调度方案,基于初始列构建限制主问题(RMP)模型;接着,设计快速有效的动态规划算法求解子问题,以得到需添加至RMP的列集,同时,考虑传统列生成算法收敛速度较慢,设计一系列方法来加速列生成过程;最后,基于所获取的MP线性松弛解,设计深潜启发式算法确定原问题的整数解.HCGA与商用求解器GUROBI的对比实验结果表明,HCGA可在较短时间内获得更优的解.     

基于智能反射面辅助与无线中继的无人机协作通信系统优化算法

针对采用智能反射面（RIS）辅助与解码转发中继的无人机协作通信系统,研究了RIS反射相位、无人机部署位置和无线中继传输时隙联合优化算法。首先根据协作系统传输协议,建立了以最大化系统端到端信息传输可达速率为目标的资源分配联合优化问题。该问题非凸,为此提出一个交替优化算法,将该非凸问题分解为分别对RIS反射相位、无人机部署位置和协作中继传输时隙进行优化的三个子问题。其中RIS反射相位优化子问题和无人机部署位置优化子问题仍非凸,为此,分别采用半定松弛方法和提出一种基于连续凸逼近的局部区域优化方法进行求解,通过三个子问题的交替和迭代优化得到原问题的次优解。仿真结果验证了提出的联合优化算法获得的系统端到端信息传输可达速率优于其他的基准方案,并发现无人机应部署靠近中继或RIS的上方,其结果与系统的信噪比、RIS的反射元件数量以及RIS和中继所处地理位置等因素有关。     

基于分布式优化的协同干扰任务分配研究

为保证目标区域干扰覆盖和最小能量消耗的优化目标,建立协同干扰任务分配模型。在分布式协同优化框架下,将集中式任务分配问题,转换为各个虚任务区内小规模的分布式优化问题,采用分解-协调优化模式和启发式遗传算法相结合的方法,实现对各个子区域优化问题的二次迭代求解。仿真结果表明,分布式协同优化方法能够有效降低协同干扰任务分配问题的求解规模,避免“维数灾”,具有可行性。     

约束满足问题的预处理方法研究

搜索控制问题是大多数人工智能问题求解面临的一个根本间题,而约束满足是解决这一问题的常用方法之一它源于机器视觉领域中的情景标识任务,如今在人工智能的众多领域(如规划、调度、时序推理)中获得了广泛的应用,受到了人工智能界的高度重视.在近几期的UCAI和AAAI等国际人工智能会议上这方面的内容均占有一定的比重,《A币ficial In-telligence》杂志曾于1992年出了一期约束满足问题的专辑     

Constraint Lingo: towards high‐level constraint programming

Logic programming requires that the programmer convert a problem into a set of constraints based on predicates. Choosing the predicates and introducing appropriate constraints can be intricate and error prone. If the problem domain is structured enough, we can let the programmer express the problem in terms of more abstract, higher‐level constraints. A compiler can then convert the higher‐level program into a logic‐programming formalism. The compiler writer can experiment with alternative low‐level representations of the higher‐level constraints in order to achieve a high‐quality translation. The programmer can then take advantage of both a reduction in complexity and an improvement in runtime speed for all problems within the domain. We apply this analysis to the domain of tabular constraint‐satisfaction problems. Examples of such problems include logic puzzles solvable on a hatch grid and combinatorial problems such as graph coloring and independent sets. The proper abstractions for these problems are rows, columns, entries, and their interactions. We present a higher‐level language, Constraint Lingo, dedicated to problems in this domain. We also describe how we translate programs from Constraint Lingo into lower‐level logic formalisms such as the logic of propositional schemata. These translations require that we choose among competing lower‐level representations in order to produce efficient results. The overall effectiveness of our approach depends on the appropriateness of Constraint Lingo, our ability to translate Constraint Lingo programs into high‐quality representations in logic formalisms, and the efficiency with which logic engines can compute answer sets. We comment on our computational experience with these tools in solving both graph problems and logic puzzles. Copyright © 2004 John Wiley & Sons, Ltd.     

一个约束可满足性问题的演化算法求解

约束可满足性问题是一大类常出现于现实应用中的复杂问题，因其繁多的约束条件而出名。本文针对一个经典的约束可满足性问题——斑马属谁问题．基于演化算法的框架进行求解。我们采用矩阵的表示方式．并设计了相应的杂交和变异算予。实验表明．演化算法能高效地解决该问题。     

Dynamic constraint satisfaction problems over models

In early phases of designing complex systems, models are not sufficiently detailed to serve as an input for automated synthesis tools. Instead, a design space is constituted by multiple models representing different valid design candidates. Design space exploration aims at searching through these candidates defined in the design space to find solutions that satisfy the structural and numeric design constraints and provide a balanced choice with respect to various quality metrics. Design space exploration in an model-driven engineering (MDE) context is frequently tackled as specific sort of constraint satisfaction problem (CSP). In CSP, declarative constraints capture restrictions over variables with finite domains where both the number of variables and their domains are required to be a priori finite. However, the existing formulation of constraint satisfaction problems can be too restrictive to capture design space exploration in many MDE applications with complex structural constraints expressed over the underlying models. In this paper, we interpret flexible and dynamic constraint satisfaction problems directly in the context of models. These extensions allow the relaxation of constraints during a solving process and address problems that are subject to change and require incremental re-evaluation. Furthermore, we present our prototype constraint solver for the domain of graph models built upon the Viatra2 model transformation framework and provide an evaluation of its performance with comparison to related tools.     

Multiobjective and multi-physics topology optimization using an updated smart normal constraint bi-directional evolutionary structural optimization method

To date the design of structures using topology optimization methods has mainly focused on single-objective problems. Since real-world design problems typically involve several different objectives, most of which counteract each other, it is desirable to present the designer with a set of Pareto optimal solutions that capture the trade-off between these objectives, known as a smart Pareto set. Thus far only the weighted sums and global criterion methods have been incorporated into topology optimization problems. Such methods are unable to produce evenly distributed smart Pareto sets. However, recently the smart normal constraint method has been shown to be capable of directly generating smart Pareto sets. Therefore, in the present work, an updated smart Normal Constraint Method is combined with a Bi-directional Evolutionary Structural Optimization (SNC-BESO) algorithm to produce smart Pareto sets for multiobjective topology optimization problems. Two examples are presented, showing that the Pareto solutions found by the SNC-BESO method make up a smart Pareto set. The first example, taken from the literature, shows the benefits of the SNC-BESO method. The second example is an industrial design problem for a micro fluidic mixer. Thus, the problem is multi-physics as well as multiobjective, highlighting the applicability of such methods to real-world problems. The results indicate that the method is capable of producing smart Pareto sets to industrial problems in an effective and efficient manner.     

约束分解技术回顾与展望

约束满足问题是一个强有力的知识表示框架,可以有效地解决许多问题。由于约束满足问题一般情况下是NP难度的问题,因此通过约束分解来降低计算的开销具有十分重要的意义。主要描述约束分解在约束满足问题中的地位、经典的分解技术和约束分解技术的发展历史,然后简要地分析这些分解技术。介绍了关于约束分解研究的最新状况,并描述、分析和总结其主要求解思想。最后根据存在的问题与不足提出了下一步的工作方向和研究思路。     

An interactive fuzzy multi-objective optimization method for engineering design

The coupling of performance functions due to common design variables and uncertainties in an engineering design process will result in difficulties in optimization design problems, such as poor collaboration among design objectives and poor resolution of design conflicts. To handle these problems, a fuzzy interactive multi-objective optimization model is developed based on Pareto solutions, where the metric function and some additional constraints are added to ensure the collaboration among design objectives. The trade-off matrix at the Pareto solutions was developed, and the method for selecting weighting coefficients of optimization objectives is also provided. The proposed method can generate a Pareto optimal set with the maximum satisfaction degree and the minimum distance from ideal solution. The favorable optimal solution can be then selected from the Pareto optimal set by analyzing the trade-off matrix and collaborative sensitivity. Two examples are presented to illustrate the proposed method.     

Introduction to planning, scheduling and constraint satisfaction

Planning, scheduling and constraint satisfaction are important areas in artificial intelligence (AI). Many real-world problems are known as AI planning and scheduling problems, where resources must be allocated so as to optimize overall performance objectives. Therefore, solving these problems requires an adequate mixture of planning, scheduling and resource allocation to competing goal activities over time in the presence of complex state-dependent constraints. Constraint satisfaction plays also an important role to solve real-life problems, so that integrated techniques that manage planning and scheduling with constraint satisfaction remains necessary. This special issue on Planning, Scheduling and Constraint Satisfaction compiles a selection of papers of CAEPIA’2007 workshop on Planning, Scheduling and Constraint Satisfaction and COPLAS’2007: CP/ICAPS 2007 Joint Workshop on Constraint Satisfaction Techniques for Planning and Scheduling Problems. This issue presents novel advances on planning, scheduling, constraint programming/constraint satisfaction problems (CSPs) and many other common areas that exist among them. On the whole, this issue mainly focus on managing complex problems where planning, scheduling, constraint satisfaction and search must be combined and/or interrelated, which entails an enormous potential for practical applications and future research. Furthermore, this issue also includes a complete survey about constraint satisfaction, planning, scheduling and integration among these areas.     

Filtering algorithms for the multiset ordering constraint

Constraint programming (CP) has been used with great success to tackle a wide variety of constraint satisfaction problems which are computationally intractable in general. Global constraints are one of the important factors behind the success of CP. In this paper, we study a new global constraint, the multiset ordering constraint, which is shown to be useful in symmetry breaking and searching for leximin optimal solutions in CP. We propose efficient and effective filtering algorithms for propagating this global constraint. We show that the algorithms maintain generalised arc-consistency and we discuss possible extensions. We also consider alternative propagation methods based on existing constraints in CP toolkits. Our experimental results on a number of benchmark problems demonstrate that propagating the multiset ordering constraint via a dedicated algorithm can be very beneficial.