论文部分内容阅读
计划评审技术(Program Evaluation and Review Technique,PERT)是在给定的系统项目中对潜在任务进行分析的一种方法。其建立的目的是为了简化大而复杂项目的计划和分配任务的时间。随着现代技术的不断发展与完善,基于计划协调技术的管理方式将成为企业、生产车间信息化建设的一个重要方式。其基本实现原理是首先用网络形式来描述一个项目计划中的各个工作(任务、活动、过程、工序)的相互关系和先后顺序,然后通过计算找出项目中的关键工作和关键路线,并且通过不断的递归选择方案,最终得到最优方案来并付诸实施,在计划执行过程中进行有效的监督和控制,保证合理地使用人力、财力、物力,快、多、好、省地完成既定项目。
在日常的生产活动中通常完成一项任务可以采用多种施工方式和组织方案,不同的方法完成同一工作必然会有不同的持续时间和费用。因此,对于由多项工作组成的整个工程项目而言,就可能出现不同总工期和总费用的方案。费用优化就是指从这些方案中确定一个最优或最满意的方案实现工期和费用的优化目标。针对工期一费用优化的研究可以追溯到20世纪60年代初期,由于在任何一个项目中,实施者都希望可以寻求到一种工期最短费用最低的最佳方案出来,以降低成本提高效率。
因此,工期-费用的优化问题对管理人员来说,有着十分重要的影响作用。其包含根据计划要求的工期,规划出最低需花费用；和根据最低费用要求,寻求最佳完成工期。当项目工期可在某个允许时间范围内取值时,项目费用可能会随工期的缩短而减少,但是在有些情况下工期取值于另一个范围时,项目费用可能会随工期的缩短而增加。
目前,针对工期费用优化问题的研究主要方法有网络计划技术、数学规划法和遗传算法等。网络计划技术和数学规划法来求解工期一费用优化问题都有着不同程度的问题。网络计划技术是通过使用特定的规则来缩短或者延长各个工作的需花时间,但这并不能保证解的最优性；另一方面,数学规划法需要大量的计算,并且也不能保证解的最优性。在大部分的实际工程项目中,有着几百个工作,需要花费时间和费用呈离散关系,这两种方法来解决都显露出低效率的寻优能力。与上述方法相比,遗传算法在解决问题时更有优势。但是遗传算法自身的一些特点对解决问题有一定影响,比如遗传算法需要设置较多算子,这些算子的设定受编程者个人经验值影响较大。针对以上不足,本文将基因表达式算法应用于网络计划的工期一费用优化问题之中,以求寻找一种更精确、更全面,求解效率更高的优化方法。
基因表达式编程(Gene Expression Programming,GEP)[16]是进化计算家族中的新成员。作为一种高效、通用的自适应式随机搜索算法,取得了很好的实际应用效果,它已经成为目前研究热点[21-24]。作为一种新型的演化算法,基因表达式算法通过模拟生物演化过程与机制来求解了优化问题及搜索问题的一类自组织、自适应人工智能技术,是一种模拟自然界遗传进化规律的仿生学算法。GEP算法的变异过程是使用定长的线性符号串,而评估过程则采用ET(Exp ression Tree)表达式树的形式,因此才能综合遗传算法GA的简单线性染色体的思想和遗传程序设计GP中使用的大小和形状不同的分叉结构的思想,具有染色体简单、线性和紧凑、易于进行遗传操作等优点。
一般适应度函数控制着进化过程中的进化方向,伴随着进化代数的增加,个体的适应度也越高,而交叉率和变异率是始终保持不变的,这将影响收敛性能、进化速度和适应值的精度,所以这里提出一种具有自适应性的交叉率和变异率。当进化过程中进化代数的逐渐升高,由保留策略法保留下来的个体适应度也越高,为避免早熟现象的产生,这里采用的方法是逐代增大交叉率和变异率,从而使进化过程在进化算法运行的后期能继续产生有意义的搜索空间,避免产生收敛早熟的现象,使算法具有更好的收敛性和运算精度。即进化过程中设计交叉率和变异率随着进化代数地增加而自适应地增加,即V=k1n,C=k2n,(其中V为变异率,C为交叉率,k1为进化代数对变异率的影响因子,k2为进化代数对交叉率的影响因子,n为进化代数)。随着进化代数的增加,将自适应地增加V、C。
本文尝试将GEP算法运用到计划评审技术中,基于GEP算法的染色体结构简单、紧凑、线性和易于进行遗传操作等优点,将其应用到工期费用的具体问题中进行优化处理,会较原始的遗传算法更快收敛到最优解。针对原算法不易从局部最优解中跳出的问题,对GEP进行了较深入的研究,由于交叉率和变异率不随迭代种群的代数增加而增加,因此才影响了算法的收敛性能、进化速度和适应值精度等问题。对GEP优化算法进行改进,在适应度函数处增加自适应功能,使由保留策略法保留下来的个体适应度随着进化代数的逐渐升高而升高,避免了早熟现象的产生,使进化过程在进化算法运行的后期能继续产生有意义的搜索空间,让算法具有更好的收敛性和运算精度。
实验证明,本改进后的GEP算法确实在收敛速度和避免早熟现象上较原遗传算法有更好的效果。