英语原文共 12 页，剩余内容已隐藏，支付完成后下载完整资料
基于Niched Pareto遗传算法改进的
多目标施工进度优化利用
Kyungki Kim1,John Walewski, Ph.D., M.ASCE2 and Yong K. Cho, A.M.ASCE
摘 要：施工进度计划必须满足多个经常发生冲突的项目目标。虽然早期的一些方法试图根据几个标准生成最优调度，但它们的大多数优化过程被分割成多个步骤。由于缺乏同步优化，只能搜索有限的替代解决方案，无法确定目标之间的一些权衡。摘要提出了一种基于工期最小化、成本最小化和资源波动性最小化三个目标的最优施工进度搜索方法。采用多目标优化(MOO)方法来生成考虑所有这些目标的调度方案。为了实现同步优化，我们提出了一种新的数据结构，它可以同时根据所有目标计算解决方案的性能。改进了一种Niched Pareto遗传算法(NPGA)，简化了优化过程。然后在已有的案例研究中实现了该优化方法。结果表明，与现有模型相比，该方法具有探索和生成更大范围解决方案的能力。确定了这三个目标之间的权衡，讨论了局限性和进一步的研究需要。DOI: 10.1061 /(第3期)me.1943 - 5479.0000374。copy;2015美国土木工程师学会。
关键词：遗传算法;施工进度;优化;多目标优化;成本;持续时间;资源水平。
介绍
为使建设项目顺利交付，应组织并管理多学科项目的参与者向项目完成的目标努力。为此，根据项目参与者的不同目标和不同的项目条件制定施工计划。有了这些协调的施工进度，以及预测的性能，决策者可以做出明智的决策，满足与项目成本、工期和资源利用等相关的多种需求。传统的调度方法主要有关键路径法(critical path method, CPM)、项目评估与评审技术、平衡线等。虽然每种技术都有其目的和缺点需要克服，但本研究主要关注于解决与CPM相关的现有缺陷。由于这些调度技术使用不同的启发式，因此本文的研究结果将不适用于CPM以外的其他技术。
CPM是最著名的调度方法之一，旨在实现更大的活动协调。在20世纪50年代末CPM发明之前，现有的建筑规划体系存在着一些缺陷，如缺乏协调和过度简化，促使发明了一种方法来实现项目活动的高度协调(Kelley和Walker 1959)。当时，各项目小组都有各自的计划和时间表，因此，详细的计划和时间表是根据整个项目的概算和过去的经验拟订的。另一方面，CPM将一个项目分解成几个活动，并在时间表中以图形形式表示它们，以计算项目总持续时间的合理估计(Leu和Yang 1999b)。自CPM发展以来，它在许多建筑工程中得到了广泛的应用，并在传统CPM的基础上发展了其他调度技术。然而，生成一系列最优调度方案仍然具有挑战性。一个实际的施工进度计划需要满足各种项目目标，例如:
- 施工工期最小化
- 建筑成本的最小化
3.尽量减少施工过程中资源利用的变化
大多数建设项目是复杂的，建设计划涉及许多活动。因此，手动生成多个调度解决方案具有挑战性，因此可以获得次优解。
早期基于CPM的调度优化方法试图根据这些目标生成最优调度选项，并进一步确定目标之间的现有权衡。然而，作者对这些方法的回顾表明，大多数现有的调度优化过程被分割成几个步骤，每个步骤按照一个或两个目标进行优化。例如，在根据成本和持续时间对计划进行优化之后，然后根据资源均衡对计划进行优化。分段过程的主要缺点是不可能同时考虑所有目标进行优化。由于这一缺陷，在优化过程中可以探索有限的可能性，不能进行一些权衡确定为优化的结果。本文提出了一种基于CPM的施工进度优化方法，通过多准则同时优化施工进度，克服了上述缺点。本文所考虑的优化目标仅限于前面提到的三个目标——最小化持续时间、成本和资源使用的波动。
在下一节中，将回顾现有的基于CPM的调度优化技术，并讨论其缺陷。在此基础上，提出了同时进行优化的施工进度优化方法。在下一节中，该方法将应用于现有的案例研究。最后一节讨论了本研究的结果和未来研究的方向。
相关的工作
本节将介绍现有的基于CPM的调度优化技术，重点介绍启发式方法。
基于CPM的施工调度技术
如前言所述，开发CPM是为了克服现有项目规划和调度系统的不足。然而，根据英国和埃及的一项调查(Allam 1988)，将原始CPM的分析方法应用到实际项目中，由于其算法的复杂性，被认为是具有挑战性的。因此，在CPM技术的基础上发展了先进的方法。
这些方法可以分为分析方法(数学-数学)和启发式方法(Leu和Yang 1999a, b)。分析方法的目的是计算最优调度，确保准确性，而启发式方法试图根据预定义的标准，如成本和持续时间(Gray 1981;Kurtulus和Davis 1982)。作为一种分析方法，数学规划公式是由Easa(1989)和Harris(1990)开发和讨论的。这些数学方法只适用于具有少量活动的小型项目，因为创建数学公式的计算成本很高。
由于分析方法的局限性，基于CPM的技术的大多数进展都是在启发式方面取得的。尽管分析和启发式方法有自己的优点和缺点,启发式方法表现出更好的性能,因此是用于多目标调度由于多个优势(低浓缩铀和阳1999 a,b)。启发式模型可以轻松地解决复杂的问题,因为他们简单的格式和简单的应用程序(勒姆1988;Leu和Yang 1999a)。此外，启发式方法能够在多目标问题中生成广泛的最优(或接近最优)解，从而支持决策过程。由于复杂的施工计划涉及许多活动和目标，处理多属性问题的能力是解决复杂施工计划问题的重要组成部分。此外，由于多属性调度方法集成了各种需求，因此它使生成的调度选项更加适用。下面的小节将对现有的启发式施工调度优化方法进行技术回顾。
启发式的施工进度优化方法
Senouci和Eldin(2004)开发了一种单目标遗传算法(GA)，该算法生成一个调度解决方案在资源和工期限制下的最低项目成本。表示调度解决方案的数据结构由活动持续时间和开始日期及其与其他活动(开始到结束、结束到开始、开始到开始和结束到结束)的关系组成。虽然模型中包含了多种资源限制和时间成本的权衡，但这种方法不能深入了解各种调度可能性，因为它只根据一个目标生成一个解决方案，并且假设其他因素保持不变。
Senouci和Al-Derham(2008)提出了一种多目标遗传算法(MOGA)来同时最小化项目持续时间和项目总成本。建筑材料、工作人员和加班结合起来创造了资源利用的选择。虽然该模型可以确定建设成本和工期之间的最优(或接近最优)权衡，但资源均衡并不是一个目标。Leu和Yang (1999b)利用基于GA的搜索技术提出了资源约束下的多目标调度模型。Leu和Yang (1999a)还提出了一种综合了时间成本权衡模型、有限资源分配模型和资源均衡模型的计算多准则调度优化模型。尽管与以前的模型相比，这是一个高级模型，但它也未能确定目标(资源均衡到成本和资源均衡到持续时间)之间的权衡。他们随后在之前的方法中添加了一个决策支持系统，通过提供优化结果来帮助调度决策者(Leu et al. 2000)。但是，无法确定资源均衡程度与其他目标之间的关系仍然没有解决。
El-Rayes和Dho(2009)提出了两种资源均衡指标来最小化资源波动的负面影响。然而，度量标准是在确定活动持续时间之后应用的，因此这种方法没有能力将成本持续时间权衡集成到其资源均衡功能中。Dho和El-Rayes(2011)提出了一种多目标调度方法，确定了资源利用最大化和持续时间最小化之间的权衡。但是，由于与不断变化的活动期间有关的费用和期间没有综合起来，因此无法确定建筑费用与其他目标之间的关系。Ozcan-Deniz等人(2011)提出了一种以时间、成本和环境影响为目标的调度优化方法。虽然本研究整合了三个目标，但由于每个活动的成本、持续时间和全球变暖潜力可以在数据准备阶段确定，而不是在优化过程中计算，因此可以使用简单的染色体结构。当考虑资源均衡而不是全球变暖潜力时，由于活动持续时间对资源均衡的影响，不能使用这种简化的数据结构。
这种同时进行成本、工期和资源均衡优化的能力不足，可以从施工调度优化启发式方法的最新发展中发现(Bettemir和Rifat 2014;Menesi和Hegazy 2014)。只有少数目标被集成到优化过程中。
现有启发式调度优化方法的技术局限性
过去，为了解决多准则调度问题，开发了许多多目标启发式算法。尽量减少工期、成本和资源使用的波动是需要优化的广泛接受的目标。以往的研究试图将这些调度标准集成到优化过程中，但没有一项研究成功同时考虑这三个条件的调度可能性。相反,他们遵循顺序步骤,安排第一次优化的施工时间和成本,由此而来的时间表然后优化资源水平(低浓缩铀和阳1999 a,b)。同样,当施工进度使用传统的CPM,创建资源水平没有发生,直到一个时间表选项和短时间内找到低成本(Kelly和沃克1959)。在基于时间-成本权衡分析的基础上，建立一组调度选项后，开始人工提线，进行资源平滑，直到得到所需的资源曲线。
图1所示 当前的(a和b)和期望的(c)解决方案空间探索
这种分段优化的主要缺点是生成的调度解决方案可能不是最优的。图1比较了分段优化(a、b)和期望的同步优化(c)，在图1(a)中，首先根据成本和持续时间生成最佳的解决方案，然后只对生成的解决方案进行资源均衡。由于考虑到持续时间和成本，对调度解决方案的搜索仅限于最初找到的解决方案，因此可以探索有限的调度可能性。但是，成本-持续时间权衡的解决方案在资源均衡方面的性能可能较差，因此必须在优化过程中探索初始权衡之外的解决方案，以便根据所有标准找到解决方案。在图1(b)中，与图1(a)相比，白色所示的解决方案具有更好的资源均衡性能。必须识别它们，因为它们具有类似的成本持续性能，但具有更好的资源均衡性能。虽然这些解决方案有可能是最优的，但是由于在成本和持续时间上的低性能，它们被排除在片段化过程的第一步的优化之外。此外，由于这种碎片化，无法确定资源均衡和其他目标之间的平衡关系是优化的结果。为了避免这种情况，必须同时为这三个目标优化调度问题。然后可以探索更大的调度可能性，并且可以确定目标之间的所有权衡，如图1(c)所示。
由于这种局限性是由分段优化过程造成的，在找到成本-持续时间的权衡后进行资源均衡，本研究旨在提出一种启发式优化方法来克服这一缺陷。本文提出的新方法可以同时生成最优调度或近似最优调度
根据多个目标(最小持续时间、成本和资源使用的波动)，从而对可能的最佳解决方案进行彻底的探索。
提出了优化模型
本节提出了一个多准则施工进度优化模型。本文方法的局限性在于，调度是在资源无限可用的前提下创建的。在实际情况中，由于资源通常是有限的，而且不容易获得，因此用这种假设创建的时间表通常是不可行的。因此，本文讨论了未来的研究，即在资源受限的情况下，必须开发什么样的数据结构来执行这种调度。下一节“目标函数”将描述三个目标函数，下一节将详细介绍本研究如何修改Niched Pareto Genetic Algorithm (NPGA)来解决优化问题。NPGA是一种遗传算法。
目标函数
本研究的优化目标是在三个重要调度准则下实现施工进度同步优化，这是以往的方法所没有达到的。目标是最小化项目持续时间、成本和资源使用的波动。为了定量评价，在Eqs中将其作为目标函数进行表述。(1)-(3)。总工期是一个目标函数，表示关键路径上的整个施工工期。额外成本计算因加快施工而产生的额外工程成本。资源均衡指数(RLI)是一个目标函数，它显示了项目的资源分配在整个项目期间是如何偏离平均资源使用的。
改进的Niched Pareto遗传算法
为了将这三个目标函数合并到一个优化阶段，对NPGA进行了修改。在“Niched Pareto Genetic Algorithm”一节中，介绍了MOGA方法之一的传统NPGA。下一节“建议的优化过程”概述了NPGA修改。然后，“染色体结构”一节提出了一种染色体结构来评估三个目标的解决方案。接下来的两个小节分别描述了目标空间规范化和外部存档。
图2. Pareto domination tournament of niched Pareto genetic algorithm
Niched Pareto遗传算法
许多实际问题，包括构建调度，都有多个属性。多属性问题的解不是线性扩展的，具有多个局部极大极小值。带有约束和权重的遗传算法被用作组合多个属性的工具。然而，这些方法对惩罚函数和权重因子的变化非常敏感。被广泛使用的比赛选择，尽管它的好处，如编码的效率和调整比赛大小的方便，解决方案在人口趋于收敛到一个统一的解决方案经过大量的代迭代(Miller和Goldberg 1995)。因此，需要克服这个缺陷的MOGA来找到解决方案。
NPGA的目的是生成称为帕累托最优解的最优解，同时保持解的多样性(Deb和Goldberg 1989)。NPGA通过寻找帕累托前沿的非支配解决方案来确定冲突目标之间的最佳权衡。NPGA避免收敛到一个点，并通过帕累托支配锦标赛和在非领域边界上共享等机制维护多个解决方案。使用帕累托支配锦标赛是因为需要更多的支配压力和对这种压力的控制，才能知道一个人的真正支配排名。NPGA的采样方案如图2所示。
该过程的共享目标是将解决方案分布在搜索空间中的不同局部最优解上。共享距离内的单个解决方案会降低其他解决方案的适应度。因此，收敛发生在一个小生境内。共享距离可以通过“将搜索空间划分为若干个大小相等的超空间，这些超空间与所搜索的optima的数量相等”来确定(Deb和Goldberg 1989)。这种NPGA的选择机制可以防止在代运行后产生类似的解决方案，从而得到
全文共16310字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[2922]
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
