本期介绍一种新的启发式算法——长城建造算法（Great Wall Construction Algorithm,GWCA）。该算法于 2021年最新发表在JCR1区，中科院1区期刊Expert Systems With Applications。
3. 长城建造算法（GWCA）
长城是以城墙为主体，融合了众多城池、关隘、敌楼等设施的综合性防御体系（Waldron，1990），始建于西周时期。作为中国古代首个军事工程，它也是世界七大奇迹之一（Jing，2015）。考古学家发现，长城的建造方法随着时间推移不断发展演变。在长城修建过程中，工匠的管理是核心问题。由于当时硬件设施匮乏，且长城建造大量采用夯土材料（Waldron，1990），其建造流程经过了不断优化。本节将详细阐述长城的建造方式、算法的灵感来源以及所提出的长城建造算法。
3.1 长城的建造方式
关于长城的建造方法，不同学者持有不同观点。其中，一种被广泛认可的方法是：人们借助工具将夯土不断运送到山区，进而修建防御设施（Jing，2015；Yang，2018）。据史料记载，秦始皇修建长城时动用了约 100 万劳工，这一数量占当时全国人口的二十分之一（Jing，2015）。在缺乏先进工具的情况下，仅依靠工匠（包括奴隶、苦力、泥瓦匠、木匠和监工等）施工，长城的建造工期从原本的 10 年延长到了 20 年甚至更久。
除了工程施工本身的挑战外，先进的人员管理机制和施工管理方法也不可或缺。在长城建造过程中，还需考虑工匠的饮食、住宿、薪酬发放以及工作安排等后勤问题。综上可见，长城建造过程对后勤保障有着极高的要求。
3.2 算法灵感来源
如前所述，参与长城建造的工匠包括士兵、苦力和木匠等，他们由皇帝委派的工头（emperor's agent）统一领导。在工头的监督下，工匠们负责搬运各自分配到的石料，并定期向工头汇报工作进展，每位工匠都需完成各自的任务。图 2 展示了工头和工匠等不同角色在建造过程中的作用关系。
图2. 皇帝代理人与工人的主观感知。
施工场地的每位工匠都有明确的工作位置。工头会根据工匠的任务汇报来安排后续工作，表现优秀的工匠有机会晋升为工程师，从而享受更优厚的待遇。因此，工匠们会通过竞争提升排名，以获得更好的福利，工匠之间的竞争关系如图 3 所示。此外，在搬运夯土的过程中，工匠会因体力消耗而需要休息。若某工匠感到疲惫，就会被精力充沛的工匠替换。为提高施工效率，需要不断补充新的劳动力。除了排名竞争，工匠之间还存在技能竞争，因为每个人都能在工作中积累经验和专业知识。在长城建造过程中，工匠们会根据所学知识发明新工具，这些工具能帮助他们更便捷地将材料运送到山顶 —— 也就是长城的修建位置。值得注意的是，山体的坡度和地形复杂度会对工匠的移动速度产生影响。
3.3 所提算法（GWCA）的框架
假设施工场地内散落着夯土，工匠需将这些夯土搬运到指定的安装位置，且每堆夯土的初始位置和搬运成本已知。首先收集并分析所有工匠的任务汇报，然后将工匠划分为工程师、苦力和士兵三类。在搬运过程中，山路的崎岖程度和坡度会影响工匠的搬运速度。此外，由于每位工匠的工作效率存在差异，通过替换工匠可以达到缩短工期的效果。因此，工头会招募新工匠来替换效率低下的工匠。算法 1 给出了 GWCA 的伪代码，图 4 展示了该算法的流程图。该算法遵循以下规则：
- 长城的施工地点位于山顶。
- 假设从山脚到山顶仅有一条通路。
- 在 GWCA 中，山路与水平面的夹角是变化的。
- 算法的解由工匠的位置决定，因为工匠负责搬运石料。
- 山路的复杂程度会影响工匠的移动速度。
- 施工过程中可能会更换部分工匠。
下一小节将详细介绍算法各部分的数学模型。
3.4 数学模型与算法细节
经验丰富的工匠往往能获得最佳工作成效。在长城建造场景中，皇帝会从所有在场工匠中挑选最优秀的工匠担任项目经理。因此，工匠们会向优秀工匠学习，以提升自身工作效率，而效率低下的工匠则会被淘汰。这一优化过程构成了 GWCA 算法的核心逻辑，图 3 展示了这种竞争模式的整体模型。在施工开始前，每位工匠会被分配不同的任务角色，包括工程师、士兵和苦力：工程师使用手推车等工具提高工作效率；士兵负责监督工匠，会主动靠近距离自己最近的工匠并进行监督；苦力则负责搬运石块等重物。最后，项目经理会在完成阶段性施工进度后，淘汰效率低下的工匠。几乎所有元启发式算法都会通过一系列操作生成新解，以下将分别介绍工程师、苦力、士兵的移动数学模型以及工匠淘汰机制的数学模型。
图3. 工人间的竞争。
本小节将在斜坡场景下模拟工匠的移动过程。假设工匠沿山坡移动，为简化分析，调整坐标轴使山坡方向与坐标轴平行。工匠的受力分析如图 5 所示，同时对工匠的重力进行分解分析。
图4. GWCA算法流程图
图5. 工人受力示意图
3.4.1 初始化阶段
在 GWCA 算法中，工匠的位置被视为候选解\(Lac_n\)
，每个候选解由若干决策变量\(Po_i^j\)
构成。这两部分的数学表达式如下：
其中，d
表示每个候选解中的决策变量数量，n
表示工匠数量（即候选解数量）。
在优化初始阶段，\(Po_i^j\)
通过逻辑混沌映射生成混沌序列，以随机确定优化问题中决策变量的初始值。决策变量\(Po_i^j\)
的初始位置在搜索空间内随机确定，数学表达式如下：
其中，\(Po_i^j(0)\)
表示工匠初始位置的初始值；cxl
为逻辑混沌序列；\(UB_j\)
和\(LB_j\)
分别表示第j
个决策变量的上界和下界；\(Rand(0,1)\)
为区间\([0,1]\)
内的随机数。
下文中将建立工匠任务分配的数学模型，分别用\(E_i\)
、\(L_i\)
和\(S_i\)
表示工程师、苦力和士兵的数学模型。此外，工匠之间为获得更优厚的福利会存在竞争关系。
3.4.2 工程师移动的数学模型（ exploitation，开发过程）
如前所述，工头会挑选部分工匠担任工程师。工程师能熟练使用工具搬运石料，从而提高工作效率。工程师会与效率最高的工匠（对应最优候选解）展开竞争，相关数学公式如下：
此外，R
的最终作用效果通过乘以区间\([-1,1]\)
内的随机整数实现：当该整数为正时，工程师向领导者位置靠近；为负时，则远离领导者位置。工程师的位置更新模型如图 6 所示。通过上述操作，GWCA 算法能让搜索主体根据\(E_{best}\)
、\(S_{best}\)
和\(L_{best}\)
（分别表示工程师、士兵、苦力中的最优者，统称为 “领导者”）的位置更新自身位置。然而，仅通过这些操作，GWCA 算法容易陷入局部解停滞状态。
图6. 工程人员移动细节
表示第t
次迭代中山路的地形复杂度；\(H(t)\)
表示第t
次迭代中第i
个工匠与山顶的高度差。\(H(t)\)
和\(C(t)\)
的数学模型如下：
3.4.3 士兵移动的数学模型（exploration，探索过程）
公式（9）为士兵的速度表达式，公式（10）表示士兵相对于前一位置的位移。士兵会主动靠近距离自己最近的工匠并监督其工作，其移动状态如图 7 所示。工匠主要根据\(E_{best}\)
、\(S_{best}\)
和\(L_{best}\)
的位置进行搜索：在寻找领导者时，工匠们会相互分散以扩大搜索范围；在替换领导者时，工匠们会向新领导者汇聚。为对这一过程进行数学建模，引入符号函数\(\text{sign}\)
来确定士兵的下一个位置，这一机制体现了 GWCA 的探索能力，用于全局搜索。如图 7 所示，当\(\text{sign}(f(ide)-f(i)) = 1\)
时，工匠向领导者靠近；当\(\text{sign}(f(ide)-f(i))=-1\)
时，工匠远离领导者。
图7. 士兵移动细节示意图
需要注意的是，适应度函数的下降过程是非线性的。此外，为了强调不仅在迭代初期，而且在迭代后期都能保持探索能力，特意要求速度\(v_i(t)\)
在整个迭代过程中始终提供随机值。这一特性在局部优化停滞（尤其是迭代后期）的情况下非常有用。GWCA 中另一个有助于探索的组件是随机数\(R_3\)
和\(R_4\)
。在 GWCA 中，\(R_1\)
、\(R_2\)
、\(R_3\)
和\(R_4\)
为工匠提供随机权重，这些参数使 GWCA 在整个优化过程中表现出更强的随机性，从而促进探索并避免陷入局部最优。
3.4.4 苦力移动的数学模型
工头将除工程师和士兵之外的所有工匠归为苦力。由于苦力体力较弱，无法独立完成夯土搬运任务，因此采用接力方式搬运夯土：苦力们从山脚到山顶排成一列，将装有夯土的篮子依次传递，这样每位苦力只需行走较短的距离。公式（11）为苦力移动的数学模型，苦力的搬运过程如图 2 所示，其运动模型如图 8 所示。
图8. 劳工移动细节
3.4.5 工匠角色模型的选择机制
目前，许多元启发式算法会定义多个模型来生成新解，且算法中的每个搜索主体都必须重复执行所有这些模型。与之不同的是，在 GWCA 算法中，每次迭代时会为每个工匠随机选择并执行三种预定义模型（即工程师、士兵、苦力的移动模型）中的一种。换句话说，上述所有移动行为都是工匠在实际建造过程中的真实行为，且这些行为在同一时间（同一迭代）只会发生一种。因此，如图 9 所示，通过均匀分布的随机过程来确定每次迭代中工匠的行为模式。
图9. 决策移动模型选择流程
综上，GWCA 的搜索过程始于在搜索空间中随机生成一组工匠（候选解）。在迭代过程中，工匠会根据\(E_{best}\)
、\(S_{best}\)
和\(L_{best}\)
的位置估计领导者的可能位置，每个候选解会更新自身与领导者之间的距离。通过随机切换工程师、士兵和苦力三种工作模式，GWCA 实现了探索与开发的平衡控制。最终，当满足终止条件时，GWCA 算法停止运行。
CEC2017效果如下：
需要的小伙伴可以通过以下方式获取源代码：
1. 加我免费获取代码！！！
VX: huohuo7998
2. 开源网站下载：
https://github.com/guangian/Great-Wall-Construction Algorithm-a-novel-meta-heuristic-algorithm-for-global-optimization
算法定制，文章辅导，算法辅导请私信我哦！
参考文献：Guan, Z., Ren, C., Niu, J., Wang, P., & Shang, Y. (2023). Great Wall Construction Algorithm: A novel meta-heuristic algorithm for engineer problems. Expert Systems with Applications, 233, 120905.