约束满足型智能规划算法研究

蒋 敏，张立行，魏振华

(火箭军工程大学，西安 710025)

约束满足型智能规划算法研究

蒋 敏，张立行，魏振华

(火箭军工程大学，西安 710025)

为解决约束满足型任务规划问题具有约束条件多、计算复杂的问题，建立了约束满足型任务规划模型，根据模型特点，借鉴遗传算法和禁忌搜索算法的优缺点，对遗传算法进行改进，通过把遗传算法和禁忌搜索算法进行融合，形成了遗传禁忌搜索融合算法，通过对比分析进行性能比较，显示该算法能够显著地提高计算效率，减少计算成本，是解决约束满足型任务规划的高效可行的智能算法。

约束满足型；智能规划；进化算法；GTSA

0 引言

约束满足型问题(constraint satisfaction problem, CSP)是计算机科学和人工智能研究的核心问题之一，日常生活中的组合优化、车间调度问题都可描述为约束满足型问题[1]，该问题包含许多相互关联的活动，其中每个工序都有确定的持续时间和给定的资源需求，资源的数量是有限的，会随着时间而变化[2-3]。资源之间存在差异性，不能完全相互替代。该类型问题的解是在满足各个活动的前后约束和资源约束条件下，确定项目中各个活动的开始时间和对应资源，使得该问题在某项要求的指标上达到最优[4-5]。

约束满足型任务规划问题(constraint satisfaction and mission plan problem，CSMPP)可以看成约束满足型问题和任务规划的组合，即要求满足所有约束条件下的任务完成目标取得最优值[6-8]。约束满足型任务规划问题本身具有约束条件多、计算复杂的特点。同时，由于任务规划需要考虑众多约束条件，求最优解变得非常困难。解决任务满足型规划问题必须首先解决处理约束条件和表达规划结果两个问题[9-12]：

1) 处理约束条件。由于进化算法对所研究问题约束条件的处理能力有限，主要依赖于适应度计算。因此必须给予约束条件合适的表达形式，并将其很好地融入算法。

2) 表达规划结果。对于不同的算法，特别是融合算法，需要寻找合适的规划结果(也就是路径群落)的表示方式。一方面有助于路径群落的初始化，提高算法效率；同时能为进化算法提供启发知识，避免搜索的盲目性。

目前对约束满足型任务规划问题的优化方法主要有：网络图法、数学规划方法、启发式优化方法、智能优化方法[13]。从上述文献中得知：项目任务数目越庞大，任务间逻辑关系越复杂的问题越显示出遗传算法的寻优效率，但遗传算法执行到一定阶段后向最优解的收敛速度缓慢。基于上述考虑，为了更好地解决约束满足型任务规划问题，本文采用GTSA方法对问题进行研究。

1 约束规划问题建模

一个典型的约束满足型任务规划问题可以描述成一个三元组P={B,Z,Y}。

其中：B为变量集，B={b1,b2,…,bn}。

Z为任务值域集，Z={z1,z2,…,zn}，zi为变量vi的值域。

Y为约束条件集，Y={y1,y2,…,ym}，每个约束zj与B的一个子集相关，即yj=表示一个约束关系，其中bsub是约束中包含的变量，bsub=bj1×bj2×…×bjn；R是与变量相关的值域；R=zj1×zj2×…×zjn，即每个约束关系确定了它所涉及的变量定义域笛卡尔积的一个子集。约束体现了变量集合中各变量之间的逻辑关系，限制了变量的可能赋值。

2 智能规划求解算法

2.1 遗传禁忌搜索融合策略

遗传禁忌搜索融合策略主要包括两个部分内容：首先，遗传禁忌搜索融合策略机制上的有效融合。遗传算法本质上为概率分布的智能优化算法，适应度大的个体将以较大的概率进行下一次循环操作，进而实现对全局的优化，但也容易陷入局部最优；而禁忌搜索算法通过禁忌表来实现状态间的替换操作，具有一定的突跳性，可有效避免搜索过程中陷入局部最优，但搜索效率较低，全局搜索能力较差。对遗传禁忌两种算法进行机制上有效的融合，可增强全局搜索能力，也能够增强局部搜索能力。其次，将遗传算法与禁忌搜索算法有效结合，呈串行结构，可以有效提高搜索速度，遗传算法的遗传操作得到的可行解能够提供禁忌搜索算法较好的初始解，使得算法具有更好的爬山能力；与此同时，禁忌搜索算法生成的可行解能够优化遗传算法中的种群质量，使得算法搜索速度更快。

由此可见，在理论上遗传禁忌搜索相融合所形成的GTSA算法具有更好的全局搜索和局部搜索能力，是一种比遗传算法和禁忌搜索算法更佳的融合算法。

2.2 遗传禁忌搜索融合算法

根据以上分析，能够得到遗传禁忌搜索算法的实现步骤，如图1所示，具体如下：

1)随机产生一个初始种群P(0)，种群规模为N，禁忌表设为φ。

图1 遗传禁忌搜索算法流程框图

2)计算P(k)里各个个体适应度。

3)判断是否满足相应的收敛准则，如果满足收敛准则，输出相应结果；如果不满足收敛准则，转到4)。

4)令m=0。

5)比较适应度大小，通过概率进行遗传操作，在P(k)里选择两个染色体。

6)如果此时的交叉概率Pc>ξ∈[0,1]，那么对所选染色体进行交叉操作，并生成两个临时染色体；相反，则将选择的父代染色体作为临时染色体。

7)以变异概率Pm对临时染色体进行变异操作，生成的新染色体置于P(k+1)中，且令m=m+2。

8)如果m

9)运用邻域函数计算当前解的全部邻域解，生成邻域解集，而后根据需求确定一定的候选解。

10)判断生成的候选解能否满足特赦准则。若能满足，那么用此解作为当前解，并更替初始禁忌表中的禁忌对象，并生成当前最优解，而后跳转至2)；相反，则跳转至11)。

11)判断相应候选解集所对应的禁忌属性，将解集中的非禁忌对象所对应的最优状态作为新的当前解，且用相应的禁忌对象更替初始禁忌表中的相应元素，并跳转至2)。

3 对比分析

为了检验本文提出的GTSA算法的优越性，运用car和rec类Flow Shop调度中的15个典型问题[14-15]使GTSA与GA、TS算法展开对比分析。各参数设置如下：初始种群规模：300，交叉概率：Pc=0.9，变异概率：Pm=0.01，迭代次数：MaxGen=300，计算次数：Num=3；最大循环次数：H=100，W2=1，tmin=5，tmax=10。计算结果如表1所示。

从以上结果能够看出：GTSA算法普遍优化质量较高，从图2与图3可以看出，在Car与Rec类问题上，GTSA算法最终计算的结果以及各类偏差情况均要好于GA，且对于绝大部分问题而言，GTSA算法的BRE、WRE、ARE值均较小，这也证明GTSA算法具有更好的鲁棒性；在求解所需时间上，GTSA算法也明显优于TS与GA算法，如图4所示。因此，本文所设计的GTSA算法是一种性能优良的求解约束规划问题的算法。

表1 3种调度算法的计算结果

注： C*为问题的最优解；BRE为最大偏差；WRE为最小偏差；ARE为平均偏差。

表2 3种不同算法对Car 和Rec类问题的偏差平均值

表3 不同算法消耗时间平均值

图2 3种不同算法优化Car和Rec问题的最小偏差

图3 3种不同算法优化Car和Rec问题的平均偏差

图4 不同算法消耗时间比较

4 结束语

本文主要研究了约束满足型任务规划智能算法。首先分析了约束满足型任务规划问题及相关算法存在的不足之处，然后，建立了约束满足型任务规划模型，根据模型特点，借鉴遗传算法和禁忌搜索算法的优缺点，对遗传算法进行改进，通过把遗传算法和禁忌搜索算法进行融合，形成了遗传禁忌搜索融合算法，通过对比分析进行性能比较，显示该算法能够显著的提高计算效率，减少计算成本，可应用于任务规划领域，是解决约束满足型任务规划问题的高效可行的智能算法。

[1]王秦晖. 约束满足及其分布式求解和应用研究[D]. 北京：中国科学技术大学, 2013.

[2]邢立宁，陈英武. 任务规划系统研究综述[J]. 火力与指挥控制，2011, 31(4): 15-18.

[3]杨轻云. 约束满足问题与调度问题中离散粒子群算法研究[D].长春：吉林大学, 2011.

[4]王 凌. 车间调度及其遗传算法[M].北京: 清华大学出版社, 2008.

[5]孙自广. 基于改进遗传算法的机器人路径规划[J]. 自动化与仪表，2009(06): 5-7.

[6]金希东. 李 治. 遗传-灾变算法及其在神经网络和控制系统中的应用[J]. 控制理论与应用，2012，12(3)：255-260.

[7]王丽薇. 遗传算法的收敛性研究[J]. 计算机学报，2013，10(6), 794-797.

[8]张超勇. 基于自然启发式算法的作业车间调度问题理论与应用研究[D]. 武汉：华中科技大学, 2010.12.

[9]姚倡锋. 复杂零件异地协同制造资源优化配置技术研究[D].西安：西北工业大学，2012.

[10]胡庆夕. 并行环境下基于层次与特征技术的设备资源模型研究[J]. 中国机械工程，2014，10(11)：1231-1234.

[11]朱启林，甘 泓，游进军,等. 基于规则的水资源配置模型应用研究[J]. 水利水电技术. 2009,4(3): 28-32.

[12]刘朝华, 章 兢, 李小花，等. 免疫协同微粒群进化算法的永磁同步电机多参数辨识模型方法[J]. 自动化学报, 2012, 38(10): 1698-1708.

[13]张 浩, 张铁男, 沈继红,等. 混沌粒子群算法及其在结构优化决策中的应用[J]. 控制与决策, 2010,23(8): 857-862.

[14]王 全. 混合遗传算法及其改进[J]. 安徽建筑工业学院学报: 自然科学版, 2011,7(4): 59-62.

[15]赵 卫. 模拟退火遗传算法在车间作业调度中的应用[J]. 计算机仿真, 2011,28(7): 361-364.

Research on the Constraint Satisfaction Type of IntelligencePlanning Algorithm

Jiang Min, Zhang Lixing, Wei Zhenhua

(College of Rocket Force Engineering University, Xi'an 710025 China,China)

For solving the constraint satisfaction type of mission planning problems is with more constraints and computationally complex, the paper builds the constraint satisfaction type of mission planning model.According to the characteristics of the model, drawing on the advantages and disadvantages of genetic algorithms and tabu search algorithm, genetic algorithm is improved. By genetic algorithm and tabu search algorithm integrated, form the genetic tabu fusion algorithm. According to comparing analysis, it can be shown that the new algorithm can significantly improve the computational efficiency, reduce computing costs, which is feasible and efficient to solve the constraint satisfaction type of mission planning.

constraint satisfaction type; intelligent planning; evolutionary algorithm; GTSA

2016-08-26；

2016-09-10。

蒋 敏(1992-)，女，山东广饶人，在读研究生，主要从事通信工程方向的研究。

1671-4598(2016)12-0218-03

10.16526/j.cnki.11-4762/tp.2016.12.063

TN99

A