ACS is a kind of ant colony optimiz

ACS is a kind of ant colony optimization (ACO) algorithms which were originally proposed by Colorni et al. (1991) as a meta-heuristic scheme to locate nearoptimal solutions. As reported by Dorigo and Stützle (2004), an ant system (Dorigo et al. 1992) being the most primitive ACO algorithms was applied in solving the travel salesmen problem. Then, several extensions of the ant system including the ACS, elitist ant system, maxmin ant system, and so on were inspired to improve its performance (Zhang et al. 2007). A comparison of various ACO algorithms have been conducted by Dorigo and Stützle (2004), which concludes that the performance of ACS is superior to the other ACO algorithms in terms of it convergence speed and processing time. By avoiding premature stagnation and improving the search speed, both the quality of solutions and the time required could be improved by using ACS.
In this paper, an automated ACS-based TCO model is introduced and its performance is compared with other modeling techniques. The paper first highlights the development environments being used for building the model. The components of the ACS-based TCO model along with their functions and operation are then introduced. Finally, the model is validated through a case study and the results of comparison are summarized.
2.Modelling environment
Before the ACS-based TCO model was developed, it is necessary to determine which programming language is the most suitable for building up the optimization model and user interface. The prime consideration was readiness of the programming language to interact with a dedicated scheduling tool and database package in a simple and direct manner. This is especially important if the model is to appeal to the planners and project managers who are not too familiarized with programming. In this research, Microsoft Project
was chosen as the scheduling tool due to its widespread usage in the construction field. As for the package for data storage, Microsoft Excel
was used because data can be exported to or imported from Microsoft Project
for analysis easily.
Various development platforms such as FORTRAN
, Visual Basic
, Java
, Visual C
, and Visual Basic for Application
(VBA) were compared. While all these programming languages are equally powerful and applicable, VBA offers the best integration and interaction with Microsoft Project
and the database. Therefore, data in Microsoft Excel
can be used by VBA for analysis while the results generated by VBA can be plugged to Microsoft Project
so as to identify the critical path and compute the overall project duration without the needs for complicated coding. Consequently, VBA was selected as the language for developing the optimization model and the user interface.
3.The prototype model
The codes in VBA were compiled as a macro program and integrated with Microsoft Project
, and a new tab known as “T/C Analysis” has been added to the menu bar in Microsoft Project
. User can simply invoke the newly developed functions, i.e. “Data Input”, “Optimization”, and “Data Output” through the pull down menu in Microsoft Project
. To start the analysis, user is required to enter the project data and those data as required for ACS modeling through the “Data Input” module. Acknowledging that it is possible that the time or cost may be fixed, user may choose amongst different optimization strategies to suit the actual need. Should the “Time-Cost Optimization” option be chosen, a multi-objective time-cost optimization will be conducted. Alternatively, the “Total Cost Minimization” or “Time Minimization” would result in the minimization of either the total cost (i.e. the sum of direct cost and indirect cost) or the shortest overall duration respectively. Finally, the results are made available to the user through “Data Output” for checking and confirmation.
3.1. Data input module
The input variables for the ACO-based TCO model include the following:
1.The logical sequence of the activities in the project, or in other words the network of the project.
2. An estimation of the values for the time and cost of each activity including the best-guess, minimum, and maximum time and cost. For the units for the time and cost, “days” and “$” are used. Other units can also be considered, but attention should be paid to the unit of indirect cost being based on the time and direct cost. For example, if “day” and “$” are the units for the time and direct cost, the indirect cost should be determined by “$/day”.
3. An estimation of the indirect cost which should be a fix value per day.
To illustrate how data is inputted into the proposed model, a simple discrete TCO problem as derived from Liu et al. (1995) is adopted. The project data consisting of seven activities (Table 1) is entered into Microsoft Project
by the user. Along with the project data is up to five alternative time-cost options for each activity, and this information is inputted into Microsoft Excel
for subsequent analysis. Apart from that, user is required to enter other data into model through the user interface (Fig. 1), and this information includes the indirect cost for the project, the number of iterations and the reward factor for the ACS algorithm. In this case example, the indirect cost is set as $1,500/day while the number of iterations and reward factor are given as 40 and 20 respectively.
Table 1. Details for the case example (Liu et al. 1995)



3.2. Optimization module
The ACS-based consists of four main phases, which could be described briefly as following.
Phase 1 – parameters initializing
During this phase, the parameters for ACS including the number of ants and the pheromone (
0), evaporation rate, and other parameters shall be initialized.
Phase 2 – solution construction
The probability for ant k to select option j is established according to the selection rule as shown in Eq. 1:


where: pij(k,t) is the probability that option (i,j) is chosen by ant k for activity i at iteration t;
ij(t) is the pheromone value of the option (i,j) being left by the ants in iteration t, indicating the attractiveness of the option (i,j) for ant k; ij represents a heuristic function which evaluates the utility of choosing option (i,j); and  and  are the weights of
ij and ij, which were determined in Phase 1. Phase 3 – pheromone updating After one solution is generated, local updating is conducted on the options being visited as follows:

ij (t) = (1− )
ij (t −1) +  
0 , (2)

where
0 is the initial pheromone value for each option and is the evaporation rate.
When an entire iteration is finished, global updating would be performed to the iteration-best options (i.e. the options visited by the best ant with the least fitness value in the current iteration) following the following global updating rules:

ij (t) = (1− z)
ij (t −1) + z 
; (3)

= R fbest-iter , (4)

where: z is the evaporation rate in the global-updating process; R is a constant representing the pheromone reward factor; and fbest-iter is the fitness value of the best ant in this iteration.
Phase 4 – algorithm stopping
Certain number of iterations would be adopted as the stopping criteria for the proposed model which can be determined by the user.
Readers are referred to Ng and Zhang (2008) for further details of the four phases mentioned above in particular the pheromone updating process.
Furthermore, as demonstrated by Ng and Zhang (2008), MAWA is an effective way to solve the multiobjective problems, such approach would be applied in the current model. Hence, the fitness function for the kth solution (in an ACS model, the fitness for the kth ant in the current iteration) can be represented as follows:

max max t t c c t max min c max min t t c c f (k) w z z (k) w z z (k) z z z z − + − + = + − + − +



, (5)

where zt(k) and zc(k) are the time and cost value of ant k respectively; and  is a positive random number between 0 and 1.
3.3. Output module
After the evaluation, the following information will be provided to the user through the data output module:
1.The optimum solution(s) of the optimization, which is/are indeed the most optimum value(s) for the total time and cost of a project. For the time-cost optimization, they would prefer to have a series of globally non-dominated solutions. However, when it comes to time and cost optimization, the shortest time and the minimal total construction cost respectively are the most important findings they would like to know.
2. The time and cost options being used for all the activities to generate each of the globally nondominated solution would be extremely useful, as planners can make use of the solutions to derive programs in the Microsoft Project
platform.
A summary of all the parameters being entered will be shown to the users for checking when the “Parameter Summary” option in menu is selected. Should the user satisfy with the input data, they can view the results of optimization which include the Pareto solutions for the optimization as well as the evolution process of the time and cost according to the iteration when they select the “Result Box” option. Taking the results shown in Fig. 1 as an example, there are three globally non-dominated solutions as listed in the left-hand side of the text box (Fig. 1a). Besides, the iter-best solutions (i.e. the best solution in each iteration) are also listed (Fig. 1b) to reflect the convergence of solutions.
a)Solutions at Pareto front
b) The evolution process
Fig. 1. The results of optimization generated by the ACS-based TCO model
3.4. Revised program in project
Should the user wish to schedule the project according to any one of the globally non-dominated solutions as identified, he/she can simply select the number of the solutions in the right box and click the “Schedule It” button. For instance, when Pareto solution number 2 is selected (se

結果 (中文) 1:

ACS 是一种蚁群算法 （ACO） 算法，最初作为元启发式的计划，以找到松驰的解决方案提出了由 Colorni 等人 （1991 年）。据多里戈和 Stützle （2004 年），蚁群系统 （虎视眈眈等人，1992年） 是最原始的蚁群优化算法应用于求解旅行推销员问题。然后，启发的蚁群系统包括 ACS，精英蚂蚁系统，极小极大蚂蚁系统，以及等等的几个扩展来提高其性能 （张等人，2007年）。虎视眈眈的 Stützle （2004 年），其中的结论 ACS 的性能优于其他蚁群优化算法在这方面进行了比较各种蚁群优化算法的收敛速度和处理时间。通过避免过早停滞和提高搜索速度，可以通过使用 ACS 改进解的质量和所需的时间。在本文中，自动化的基于 ACS 的 TCO 介绍了模型和它的性能相比其他建模技术。本文首先强调被用于构建模型在开发环境。然后介绍了基于 ACS 的 TCO 模型以及它们的功能和操作的组件。最后，通过案例分析验证了该模型，总结了比较的结果。2.建模环境建立了基于 ACS 的 TCO 模型之前，有必要确定哪种编程语言是最适合建立的优化模型和用户界面。首要的考虑是编程语言准备与专用的调度工具和数据库软件包以简单和直接的方式进行交互。这一点尤其重要，如果是呼吁规划人员和项目经理都不太熟悉编程模型。在此研究中，微软的项目被评为日程排定工具由于其广泛应用在建筑领域。对于数据存储的包，Microsoft Excel 是使用，因为数据可以导出到或导入从 Microsoft Project 分析很容易。如 fortran 语言、 Visual Basic、 Java、 Visual C 和 Visual Basic 应用程序 （VBA） 的各种开发平台进行了比较。虽然所有这些编程语言同样功能强大和实用，VBA 提供最佳的整合和微软的项目与数据库的交互。因此，在 Microsoft Excel 中的数据可用于 VBA 的分析而生成 VBA 的结果可以插入到 Microsoft Project 以查明的关键路径，计算项目的总工期，无需复杂的编码。因此，VBA 被选为开发优化模型和用户界面的语言。3.原型模型在 VBA 中的代码被编译为宏程序和与 Microsoft Project，集成在一起并称为"T/C 分析"的新选项卡已添加到 Microsoft Project 中的菜单栏。用户可以简单地调用新开发的功能，即"数据输入"、"优化"和"数据输出"拉通过 Microsoft Project 中的下拉菜单。若要开始分析，要求用户通过"数据输入"模块建模的 ACS 作为所需输入的项目数据，这些数据。确认它可能的可以固定的时间或成本，用户，可能之间不同的优化策略选择，以配合实际需要。应选择"时间-费用优化"选项，将会进行多目标的工期-成本优化。另外，"总成本最小化"或"时间最小化"会导致最小化总成本 （即直接成本和间接成本总和） 或总工期最短的分别。最后，结果是向提供用户通过"数据输出"进行检查和确认。3.1.数据输入模块基于蚁群算法的总体拥有成本模型的输入的变量包括以下内容：1.逻辑顺序的活动，在项目中，或在其他词语的网络项目。2.估计值的时间和成本的每一项活动，包括最佳猜测，最小和最大的时间和成本。对于时间和成本的单位，使用"天"和"$"。也可以考虑其他单位，但应注意单位基于时间和直接成本的间接费用。例如，如果"一天"和"$"是单位时间和直接成本，间接成本应由"美元/天"确定。3.估计的间接成本应该是每一天一个固定值。为了说明如何将数据输入到该模型，一个简单的离散的总体拥有成本问题派生从刘等人 （1995 年） 采用。项目数据组成的七个活动 (表 1) 和 Microsoft Project 的用户进入。及其所在的项目数据达五个备选时间成本为每个活动，并为后续的分析到 Microsoft excel 中输入此信息。此外，要求用户输入其他数据模型通过用户界面 （图 1），而此信息包括项目、 迭代次数和 ACS 算法的奖励因素的间接成本。在这种情况下的示例中，间接成本设置为小时 ￥ 0 而迭代和奖励因子的数量分别为 40 和 20 给出。表 1。(刘等人，1995 年） 的情况示例的详细信息3.2.优化模块基于 ACS 的包括四个主要的阶段，可以简述如下。阶段 1 — — 参数的初始化在此阶段，ACS 包括数量的蚂蚁和信息素 (0) 的参数应初始化蒸发速率和其他参数。阶段 2 — — 解的构造根据情商 1 中所示的选择规则，建立了蚂蚁 k 选择选项 j 的概率：在这里： pij(k,t) 是选项 (i，j) 由活动的蚂蚁 k 我在选取迭代 t ； 概率ij(t) 是选项 (i，j) 的信息素值被留下的蚂蚁在迭代 t，指示的吸引力的选项 (i，j) 的蚂蚁 k ；ij 表示一个启发式函数，计算该实用程序的选择 (i，j) ；和，ij 和 ij，确定了在第 1 阶段的重量。阶段 3 — — 信息素更新后一种解决方案生成的本地更新进行访问，如下所示的选项：ij (t) = (1−) ij （t − 1) + 0，（2）0 为每个选项的初始信息素值何地的蒸发率。完成整个迭代后，将向迭代最好选项 （即访问的当前迭代中最小的健身价值的最佳蚂蚁选项） 执行全局更新以下以下全局更新规则：ij (t) = (1− z) ij （t − 1) + z ；(3) = R fbest iter，(4)在哪里： z 是蒸发速率在全局更新过程中 ；R 是一个常数，表示信息素奖励因子 ；和 fbest iter 是这个迭代中最好的蚂蚁的健身价值。阶段 4 — — 算法停止一定的迭代次数，将通过作为模型，可以由用户确定的停止标准。请读者参看吴和张 （2008 年） 为四个阶段的进一步细节上述特别是对信息素更新过程。此外，吴和张 （2008 年） 所示，椰树是有效的方法来解决多目标问题，这种方法会在当前模型中。因此，泰熙解决方案 （在 ACS 的模型，对于当前迭代中的第 k 个蚂蚁健身) 健身功能可以归纳为如下：最大最大 t t c c t 最大温度最大值最小 t t c 进行 (k) w z z (k) w z z (k) z z z z − + − + = − − +，（5）在那里 zt(k) 和 zc(k) 是时间和成本的蚂蚁 k 值分别 ；和是一个积极的随机数，介于 0 和 1 之间。3.3.输出模块经过评估，将通过数据输出模块为用户提供以下信息：1.优化，这是的确是最最佳值的总时间和费用项目的最佳解决方案。时间-费用优化中，他们宁愿要有一系列的全球范围内的非支配解。然而，当它来的时间和成本的最优化，最短的时间和最小的总建设成本分别是最重要的发现，他们很想知道。2.时间和成本的选项，用于各项活动来生成每个全局非支配解的极为有用，将规划师可以使用解决方案来推导出程序中的 Microsoft Project 平台。检查当在菜单中的"参数摘要"选项被选中时，将向用户显示正在输入的所有参数的摘要。用户应满足这样的输入数据，则可以优化的结果，其中包括的帕累托优化解 》 以及演化过程的时间和成本根据迭代时查看他们选择"结果框"选项。考虑如图 1 所示的结果，有三个全球非支配解所列左侧的文本框中 （图 1a）。此外，iter 最佳解决方案 （即在每个迭代中最佳解决方案） 也是列出 （图 1b），以反映解的收敛性。a) 解决方案在 Pareto 前沿b） 演化过程图 1。由基于 ACS 的 TCO 模型生成优化的结果3.4.订正程序项目中如果用户希望安排根据全球非支配任何的解一个项目，确定，他/她在右边的框中选择解的个数，即可单击"日程安排它"按钮。例如，当帕累托解 2 号是选定 （se

結果 (中文) 3:

ACS是一种蚁群优化（ACO）算法是由科洛尼等人最初提出的。（1991）作为一种新的启发式搜索方法找到最佳的解决方案。由Dorigo和STützle报道（2004），蚂蚁系统（Dorigo等人。1992）是最原始的蚁群算法应用于求解旅行商问题。然后，的蚁群系统包括ACS的几个扩展，精英蚂蚁系统，最大最小蚂蚁系统，等等的启发，以提高其性能（Zhang et al。2007）。不同的蚁群算法的比较已经由Dorigo和STützle进行（2004），这表明ACS的性能优于其他蚁群算法以其收敛速度和处理时间。避免过早停滞和提高搜索速度，两者的质量解决方案和所需的时间可以通过ACS改进。
在本文中，介绍了一个自动化的基于ACS的TCO模型及其性能与其他建模方法相比。本文首先集锦开发环境被用于构建模型。ACS的组件基于TCO模型以及它们的功能和操作的介绍。最后，通过案例对模型进行验证和比较结果总结。
2.modelling环境
以前开发的基于ACS的TCO模型，要确定哪种编程语言是最适合建立优化模型和用户界面。首要考虑的是编程语言和一个专用的调度工具和一个简单而直接的方式封装的数据库交互的准备。如果模型是呼吁规划师和项目经理谁都不太熟悉编程，这是特别重要的。在这项研究中，微软项目
作为调度工具由于其广泛的应用在建筑领域。作为存储数据包，微软Excel
是因为数据可以出口或从微软项目分析
轻松导入。
各种开发平台如FORTRAN

，Visual Basic，Java
，Visual C++和Visual Basic应用程序
，
（VBA）进行比较。而所有这些编程语言同样强大和适用，VBA提供了最好的集成和交互与微软项目
和数据库。因此，在
微软Excel数据可以使用VBA进行分析而产生的结果通过VBA可以插微软项目
以便识别关键路径，计算整个项目的时间而不需要复杂的编码。因此，VBA为开发用户界面的优化模型为语言。
3.样机模型
VBA代码被编译为一个宏程序，微软
集成项目，和一个新的标签被称为“T / C分析”中增加了在微软项目
菜单栏。用户可以简单地调用新开发的功能，即“数据输入”，“优化”，和“数据输出”通过下拉菜单项目
微软。开始分析，要求用户输入的项目数据和这些数据所需的ACS建模通过“数据输入”模块。他承认这是可能的，时间和成本可以是固定的，用户可以选择在不同的优化策略，以适应实际需要。如果“时间成本优化”选项被选中，一个多目标的时间成本优化将进行。另外，“总成本最小化”或“时间最小化”会导致的总成本最小化（即直接成本和间接成本之和）或短的总时间为。最后，结果是可通过“数据输出”检查和确认用户。
3.1。数据输入模块
基于TCO模型的蚁群算法的输入变量包括：
项目的活动1.逻辑顺序，或者说项目的网络。
2。对于每个活动包括最好的时间和成本估计的猜测值，最小和最大的时间和成本。为单位的时间和成本，“天”和“$”的使用。其他单位也可以考虑，但要注意间接成本和直接成本的基础上的时间单位。例如，如果“天”和“$”为单位的时间和直接成本，间接成本应该由“美元/天”。
3。间接成本的，应该是每天固定值的估计。
说明数据输入到模型中，一个简单的离散TCO问题来自刘等人。（1995）采用。包括七个活动项目的数据（表1）由用户进入微软项目
。随着项目的数据高达五的替代选择为每个活动的时间成本，并将此信息输入到微软Excel
后续分析。除此之外，要求用户输入其他数据模型通过用户界面（图1），这些信息包括该项目的间接成本，迭代次数和ACS算法的报酬要素。在这种情况下，间接费用为1500美元/天，而迭代和奖励因子数为40和20。
表1。对于案例的细节（Liu et al.。1995）



3.2。优化模块
ACS的主要分为四个部分，可以简要描述如下。
1期–参数初始化
在此阶段，ACS包括蚂蚁的数量和信息素的参数（
0），蒸发率，和其他参数进行初始化。
2期–解决建设
蚂蚁K选择J建立根据选择规则如公式1所示的概率：


其中：Pij（k，t）是期权的概率（我，J）的活动我在迭代T蚂蚁K选择；
ij（t）是期权价值的信息素（I，J）被迭代T蚂蚁离开，指示该选项的吸引力（I，J）蚂蚁K； ij表示启发式功能的评价选择选项的效用（I，J）；和和是
ij ij和权重，这在1期确定。在生成一个解决方案3期–更新信息素，局部更新是对选项进行访问：

ij（t）=（1−）
ij（t− 
1）0，（2）

哪里
0是每个选项的初始信息素的值和蒸发速率。
在整个迭代完成后，将进行全球更新迭代的最佳选择（即通过在当前迭代最小适应值最好的蚂蚁访问选项）以下全局更新规则：

ij（t）=（1−Z）
ij（t−1）Z 
；（3）

= R  fbest ITER，（4）

其中：Z是全球更新过程中的蒸发速率；R是一个常数表示信息素的奖励因子；和fbest ITER是在迭代中最好的蚂蚁的健身价值。
4期–算法停止
迭代一定次数将作为该模型可由用户确定的停止准则。
读者简称NG和Zhang（2008）对上述具体信息素更新过程的四个阶段的进一步细节。
此外，由吴和张证明（2008），万华是解决多目标问题的一种有效方法，这种方法可以应用于当前的模型。因此，对于k解的适应度函数（在ACS模型，健身在当前迭代k蚂蚁）可以表示如下：

最大T T C C C T最大最小最大最小T T C C f（k）W Z Z（K）W Z Z Z Z Z Z（K）−−=−−



，（5）

，ZT（K）、ZC（K）的时间和蚂蚁K分别成本价值；和是0和1之间的一个积极的随机数。
3.3。评估后输出模块
，以下信息将提供通过数据输出模块的用户：
1。最佳的解决方案（S）的优化，这是确实的最佳值（S）对于一个项目的总成本和时间。对于时间成本优化，他们宁愿有一系列全局非劣解。然而，当涉及到时间和成本优化，在最短的时间和最低的总建设成本分别是最重要的结果，他们想知道
2。时间和成本的方案被用于所有的活动产生的全球非支配解将是非常有用的，作为规划师可以利用该解决方案中的项目
微软平台程序。
所有输入参数的摘要将显示用户查询时在菜单“参数汇总”选项。用户应满足输入数据，他们可以查看结果的优化，包括优化的帕累托解以及演化过程的时间和成本，根据迭代时选择“结果框”选项。在图1所示为例的结果，有三个全局非劣解在文本框的左边列出（图1A）。除了，ITER的最佳解决方案（即最佳的解决方案，在每一次迭代）也上市（图1B）反映解的收敛性。一个在帕累托面前
）
B方案）的演变过程
图1。基于TCO模型的
3.4 ACS生成的优化结果。修改后的方案在项目
如果使用者希望项目进度根据全局非劣解所确定的任何一个，他/她可以简单地选择在右箱的解的个数和点击“计划”按钮。例如，当帕累托解2号是选择（SE