|||
针对线性规划(LP)对NP问题的解决的有限性,NP问题复杂度增加的时候就引出了启发式算法对问题的求解。对RCPSP问题是典型的NP问题,针对这个问题结合了很多流行的算法,简要的介绍。
1.基于优先权规则的启发式算法
基于不同的优先权规则从可安排活动集合中选择活动,常用的优先权规则主要有:最大分级位置权重规则、最迟完成时间规则、最多紧后活动规则、最迟开始时间规则、最小松弛规则。另外还有扩展出多通道算法,如:多重优先权规则启发式算法、前向-后向进度安排启发式算法、抽样性启发式算法、适应性启发式算法等等。
2.超启发式算法
该类算法将项目进度表述为一组编码,利用超启发式策略对编码进行搜索优选后,再转化为进度安排。进度安排常用的表述方式有活动列表、随机键、转移向量、进度设计、直接表述。
求解RCPSP常用的启发式策略有模拟退火、禁忌搜索、遗传算法等。
①模拟退火:从某个初始解开始,一个邻点通过对当前解的扩展来生成。如果邻点好于当前解则被接受;否则,它以一定的概率被接受,接受概率依赖于该解变坏的程度以及当前的温度参数。随着算法的进行,温度被逐步降低以减小接受坏的邻点的概率。达到规定的温度后算法终止,最后固定下来的解即为满意解。
②禁忌搜索:对于所有邻点解进行评价并选择其中最好的一个进行进一步的搜索。为了避免搜索返回刚刚离开的局部最优点而形成循环,通过建立一个禁忌列表来限制向某些邻点的移动。这种禁忌状态在某种特定的条件下也可以被重新激活。
③遗传算法(GA):并行地考虑解的一个集合或群体, 在已生成的初始群体的基础上, 新的解通过交叉和/或变异操作来获得。在新解生成后,适应度通常用所求解问题的目标函数来表示最高的解“生存”下来构成下一代,而其余的解通过所谓的选择机制被淘汰,从而使解的质量不断得到改善。优点在于采用启发式群体随机搜索的方法,在搜索的过程中不易陷入局部最优。但是其缺陷是局部搜索能力较差并容易早熟收敛。
其他类型的启发式算法如蚁群算法(ACO)、可变邻点搜索技术等。超启发式算法被普遍认为是在性能、可扩展性和易于实现性等方面权衡后的最佳方法。目前学者们研究资源受限项目调度问题最常用的方法。
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-8-28 09:20
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社