基于罚函数遗传算法的水土保持土方调配优化.pdf

第2 6 卷第4期2023年8 月扬州大学学报（自然科学版）Journal of Yangzhou University(Natural Science Edition)Vol.26No.4Aug.2023基于罚函数遗传算法的水土保持土方调配优化霍正刚，王子旸，查晓庭，张森森，陆孟瑶（扬州大学建筑科学与工程学院，江苏扬州2 2 512 7）摘要：为得到合理的土方调配设计，确定最佳的土方调配路径和数量，减少劳动强度，降低成本和缩短工期，采用管理运筹学的线性规划方法，以最低运费为目标函数，建立土方优化平衡模型，并通过含罚函数的遗传算法，消除等式约束，得到该模型的最优解.计算结果表明，与优化前的土方调配相比，该方法能够更准确地找到最优解，为类似的土方调配提供良好的技术支持.关键词：土方调配；水土保持；线性规划；遗传算法中图分类号：TU712.1D0I:10.19411/j.1007-824x.2023.04.012文献标志码：A文章编号：10 0 7-8 2 4X(2023)04-0067-06随着中国城市化进程的快速发展，如何平衡规模不断扩大的城市建设和城市的水土保持已成为城市规划和建设过程中需解决的问题之一，而环境友好、资源友好型的工程项目有利于我国经济的持续发展.水土保持项目涉及场平工程、土石坝工程、路堤工程和地下工程等，这些工程均须考虑土方的调配问题，包括地上与地下之间的调配、不同场地间的调配等.目前，土方调配问题通常归结为管理运筹学中的运输问题，并将土方调配优化模型问题转化为线性关系，以线性规划为基础建立理论框架，运用数学方法得到最优解.景明等1采用LINGO工具对大型土方调运问题进行线性规划求解，所得结果较为准确；Artun等2 通过垂直优化的单纯形法求解线形规划模型，较大幅度地降低了优化后的成本；Karimi等31考虑到土方挖填区体积和单价的模糊性，提出一种土方调配模糊线性规划模型；Liu等4建立具有模糊参数和约束的全系数模糊线性规划土方分配模型，有效克服了传统土方分配方法的不足；Wan等5利用线性规划模型，采用表格运算法对土方调配进行优化，最小元素法确定初始运输方案，并通过闭路法优化方案，最终得到最小土方运费的方案.这些研究成果显示，线性规划因采用严格的数学方法建模，故不管是表格法还是表上作业法其计算量均较大，且计算时易陷入局部最优解.Katebi等6 采用一种稳健优化方法对传统道路施工中土方调配的规划模型进行修正，使该模型具有较好的鲁棒性；Villar等7 利用ICOM（i n t e l l i g e n t me t h o d o f o p t i mi z e dmass compensation)方法对经典的土方挖掘和填充过程进行优化，该方法能有效降低土方挖掘与填充的成本；Akgul等8 运用无人机和全球卫星导航系统，提高了土方计算中网格的分辨率，使土方调配精度大幅提高；Shehadeh等9基于进化多目标方法提出一种新型优化系统，使时间和成本分别下降了14.35%和9.50%.这些方法的优点是计算方便，但在模型的解释性上不如线性规划，计算结果的准确性也存在不足.本文以某水土保持项目为研究对象，拟采用线性规划法并结合罚函数基因遗传算法对该水土保持土方调配进行快速优化，为解决类似土运问题提供参考.1土方调配模型1.1基本假设本文建立的土石方调配模型基于以下几个假设：收稿日期：2 0 2 2-0 7-0 8.*联系人，E-mail:.基金项目：江苏省科技厅资助项目（BY2020703).引文格式：霍正刚，王子旸，查晓庭，等基于罚函数遗传算法的水土保持土方调配优化扬州大学学报（自然科学版），2023,26(4):67-72.681）土方之间的运输路线按照最短直线距离进行.由于土方调配工程中施工现场地形的不规则性和不一致性，通常采用面积中心或几何中心计算两个区域之间的距离.2）每个工段既可以是挖区也可以是填区，各挖填区的土方量已知，且满足挖填总体平衡，忽略挖填土方的临时变更量.3）因实际工况中，中转场地只是起到临时存储作用，并不影响最终土方调运区域之间的调配关系，故不考虑中转场地的影响。1.2变量参数符号及含义土方调配的费用组成主要由单位体积综合单价、运距及土方调配量构成，表1给出了本文模型中各参数的符号及含义，变量符号W:/m3Xi;/m3Cy/(元 m-3)C%/(元m-3)C;/(元m-3)C;/(元 m-3.km-1)S;/kmPij1.3综合单价土方调配综合单价的经验公式为1o1C，=C十P，（CS；十C,）.但在确定的项目中，因C,是与运输量无关的定值函数，其数值由项目组给定，故C，可视为一个常量11.1.4目标函数及求解1.4.1目标函数及其约束条件在同一工段内进行挖掘和填筑时，因不涉及运输调配量，故有X，二0；而各工段间的距离在设计阶段已经确定，故S；为常量.因此，总运费的线性规划函数(1)则土方调配模型的目标函数F(X,)=min(f(X,)/C,)=min(,Z,-,X,X S,)其约束条件为Z.X,=W,i=1,2,n;Z,X,=T,j=1,2,m;(X,0,i=1,2,.,n;j=1,2,m.1.4.2带罚函数的目标函数为解决遗传算法求解土方调运过程中的约束优化问题时可能存在不可行解产生偏离可行域的解和遗传因子作用于可行解后产生不可行解的问题12，本文采用罚函数使其转化为无约束问题后再求解.此时，无约束带罚函数的目标函数(4)其中k为惩罚因子.当X，取值符合约束等式条件时，罚函数p（X，）不起作用或作用很小；当X，取值不符合约束等式条件时，p（X，）起作用，此时g（X，）增大，适应度变小，不易被复制而遗传给下一代.因此，式（3）中的等式约束利用罚函数变成无约束形式，令约束函数扬州大学学报（自然科学版）表1变量符号及含义Tab.1TThe variable symbol and meaning含义挖区i已挖出的土方量从i区运输到i区的土方量由挖区i到填区j土石方的开挖单价由挖区i到填区j土石方的运输单价由挖区i到填区j土石方的填筑单价由挖区i到填区j土石方的综合单价由挖区i到填区i土石方的运输距离由挖区i到填区土石方的膨胀因数f(X,)=Z,Z-C,X,S;,g(X,)=f(X,)/C+kp(X,),第2 6 卷变量符号含义T:/m填区i需要填筑的土方量F(Xi,)目标函数g(Xi,)带罚函数的目标函数p(Xi)罚函数h(Xi)等式约束条件函数Q(Xi;)适应度函数d适应度函数上限保守预估值(2)(3)第4期本文将约束函数的平方和作为罚函数，即p(X,）=湾 h（X,）.1.4.3适应度函数适应度函数13 反映个体对优化目标的符合程度，即个体适应度越高越符合目标要求.考虑到本研究中的目标函数为最小化问题，故采用倒数的方式将目标函数转变为适应度函数.同时，为使适应度函数取值在（0,1)区间内，故最终适应度函数定义为Q（X，）=1/（1十d十g（X，），则有Q（X）=1/1+d+(2Z,X,S;+k2h(X,).1.4.4遗传算法求解目标函数遗传算法是一种模拟自然界优胜劣汰、适者生存的算法14.其本质是一种排序的算法或是一种选优的算法，图1给出了这种算法的步骤.但是传统的遗传算法运算量较大，收敛速度较慢，且当调配数目达到一定程度时易陷入局部最优而不能得到最优解.为解决这些问题，本文在目标函数上引人罚函数15，此时线性规划问题的求解步骤为：1）确定所需种群数量的大小.本文实例中选取初始种群大小为30，并以各区域间调运土方量X作为基因编码个体16，用二进制编码将个体基因编码成一个二进制符号串，其中每一个符号串代表一条染色体.为避免初始种群远离全局最优解编码空间，根据土方量变动区间随机生成初始种群.2）定义一组优化函数.以总运费的线性规划函数式(1)为优化函数，式（2)为目标函数，加人罚函数及其他限制参数得到适应度函数.3）计算各个体的适应度.以0.6 0 的交叉率对个体进行基因交叉操作，以0.0 1的变异率对子代个体进行变异操作.为提高子代中适应度高的个体的比例，采用轮盘赌法17 选择个体.4）对新产生的子代个体进行适应度计算，并进行种群的更新.5）满足终止条件时算法终止，并对原始编码信息根据编码的方向进行二进制解码，输出最终结果，即区域间调运土方量X2仿真实验2.1工项目简介扬州市某居住项目土方施工区分为建筑物区、道路广场区、绿化区.其中，建筑物区包含基础开挖工段W1/TI、场地平整工段W2/T、场地清淤工段Ws/Ts；道路广场区分为管线施工段W4/T4、场地平整工段Ws/Ts、场地回填工段W。/T 6；绿化区分为绿化覆土工段W,/T7、绿地开挖工段W/Ts、绿地回填工段W。/T。.根据设计方提供的数据，此项目的开挖及回填的土方量如表2 所示.表3给出了不同工段间的运输距离S;霍正刚等：基于罚函数遗传算法的水土保持土方调配优化h.(X,)=Z,-,X,-W,i=1,2,m;hu+;(X,)=,X,-T,j=1,2,n.计算个体适应度是否满足终止条件否选择个体，进行复制操作选择个体，进行交叉操作选择个体，进行变异操作生成新的种群图1遗传算法流程图Fig.1The flow chart of genetic algorithm69(5)(6)编码，产生初始种群开始构建目标函数、适应度函数立引人罚函数是输出最佳个体结束70施工段Wi/TiW2/T2W3/T31234567892.2模型简化与约束矩阵2.2.1变量及罚函数个数简化如果i区域挖方量W，为0.0 0 m，则所有从i区域调运出的X，为0.0 0 m.同理，若i区域填方量T，为0.0 0 m，则所有调往i区域的X，为0.0 0 m，且挖填自给区域的X=0.00m，故该项目的未知变量X，可从8 1个简化至12 个，约束等式从18 个简化为7 个.此时，简化后的罚函数为p(X,)=(X1s+X1s+X1+X1s-7.10)2+(X3s+X3s+X37+X3s-1.90)2+(X9s+Xgs+Xg7+Xgs-1.68)2+(X15+X35+X95-0.45)+(X16+X36+X962.96)2+(X17+X37+X971.25)2+(X18+X38十Xg8一6.0 3）.适应度函数则化简成由12 个变量及7 个约束等式求平方和的复合函数，使函数的求解更方便.2.2.2参数设置惩罚系数k=30.00；带罚函数的目标函数Q(X;)=1.48X15+1.70X16+1.21X17+1.30X1s+1.10X3+1.39X36+1.27X37+1.40X3s+1.33Xgs+1.36X9+0.71Xg+0.53Xgs+30.00p(X,);约束条件为W=（7.10,0.0 0,1.9 1,0.52,0.0 0,0.0 0,0.0 0,0.0 0,1.6 8)，T=（0.0 0,0.0 0,0.0 0,0.52，0.45,2.96,1.25,6.03,0.00)；隐含条件为X,0.2.3纪结果与分析2.3.1仿真结果运用MATLAB中遗传算法工具箱，输入带罚函数的目标函数，下限设置为Zeros12,1)，种群规模设为2 0 0 代.图2 为优化过程的运行曲线.从图2 可以看出，遗传算法在迭代30 次后曲线趋于平稳，染色体随迭代次数的增加差异较小，表明已经找到最优解.在最优条件下该项目的土方调用结果为：Xis=4.30103m，X1s=1.7 7 10 4m，X1z=6.7 0 10 3m，X1s=4.2 310 4m，X36=8.10X103m,X37=3.70X103m,X3s=6.9010m,Xg=3.70X10m,Xgz=2.00X103m,Xgg=1.11X104 m.2.3.2不同算法结果比较假设运输的综合单价为1.0 0 元m-3km-1，不同算法中各区域运输距离一致.1）表上作业法图3为该项目实际工程的传统表上作业法求解调运结果.根据式（2)将传统算法扬州大学学报（自然科学版）表2 各施工段开挖填筑土方量Tab.2EExcavation and filling earthwork amount of each construction section土方量7.10/0.000.00/0.001.91/0.00Tab.3Transportation distance between different sections Si120.000.350.00第2 6 卷104m3施工段土方量WA/T40.52/0.52Ws/Ts0.00/0.45Wo/T60.00/2.96表3不同工段间的运输距离Sij340.361.430.271.340.000.990.00施工段Wi/T7W/T8W。/T,561.481.701.371.581.101.390.600.680.000.500.00土方量0.00/1.250.00/6.031.68/0.00781.211.301.241.371.271.401.101.161.111.261.071.260.000.620.00km91.351.441.551.221.331.360.710.530.00第4期下土方调配量与距离矩阵点乘求和，表上作业的运输规划按照图3的箭头方向调运，则运费总和为13.94万元.此法不能通过有关条件简化工作，计算工作量大而繁杂。2）M A T LA B自带线性规划工具箱算法函数写成调用格式，等式约束矩阵选取W、T，下限为L=Zeros(12,0）,线性规划优化函数为X,faval=linprog(g（X,),0,0,W,T,L)，运行自带线性工具箱，得X=（0.45,2.9 6,1.2 5,2.44,0.0 0,0.0 0,0.0 0，1.91，0.0 0，0.0 0，0.0 0，1.6 8）.取对应的距离矩阵S=(1.48,1.70,1.21,1.30,1.10,1.39,1.27,1.40,1.33，1.36，0.7 1，0.53)进行点乘求和，得到总费用为13.94万元，结果与表上作业法一致.该算法由计算机完成，故计算速度更快，人为误差更少.3）罚函数遗传算法根据公式（2）将带罚函数遗传算法结果的变量值与运输距离矩阵点乘求和，得运费总和为13.75万元.计算结果表明，罚函数遗传算法结果优于传统表上作业法和线性规划工具箱结果，且收敛速度更快.上述仿真结果表明，与表上作业法比较，罚函数遗传算法避免了手工计算，可以通过具体问题条件简化方程，能快速且准确地得到最优解；与MATLAB自带线性规划工具箱比较，罚函数遗传算法所得调运费用结果优于线性规划工具箱.因此，在复杂问题上，采用罚函数遗传算法优化线性规划问题时求解速度更快，规划质量的结果更精确。3结论对于复杂问题，遗传算法在求解速度和质量上均远超常规方法.仿真实验过程表明，遗传算法只是一种近似算法，在运用的过程中需要巧妙的构思来简化变量数量，利用罚函数避免不可行解或可行域外的解.总之，罚函数遗传算法为计算约束优化问题提供了一条可行的途径，通过合理规划和合理搭配，实现了一定的经济价值.参考文献：1景明，白中科，崔艳，等。基于线性规划和数字高程模型的排土场复垦土方调配优化J金属矿山，2 0 13，42(2):130-134.2ARTUN A,BADENKO V,VOLKOVA Y,et al.Minimizing earthwork volumes by optimizing vertical align-ment with linear programming algorithm JJ.E3S Web Conf,2020,224:03028.3KARIMI S M,MOUSAVI S J,KAVEH A,et al.Fuzzy optimization model for earthwork allocations with im-precise parameters JJ.J Constr Eng Manage,2007,133(2):181-190.4LIU Ning,CUI Bo,ZHONG Denghua.Fuzzy earthwork dynamic allocation and optimization for construction ofhigh concrete faceRockfill damJJ.Trans Tianjin Univ,2012,18:426-431.霍正刚等：基于罚函数遗传算法的水土保持土方调配优化30405060708090100选代次数/次图2 遗传算法运行曲线Fig.2 Genetic algorithm running curve项目分区工段建筑物区基础开挖场地平整场地清淤道路广场区管线施工场地平整场地回填绿化区绿化覆土绿地回填绿地开挖小计图3表上作业法土方平衡图（10 4m）Fig.3Earth balance diagram for table operation method7125320151050-5010 20挖方7.101.910.521.6811.21填方1.910.520.520.450.452.962.961.251.252.446.031.6811.21725WAN Honghao,XU Tinghua.The application of table operations method in earthwork blending JJ.ApplMechMater,2012,204/208:463-466.6KATEBI A,PISHVAEE M S,MOHEBALIZADEH A,et al.Towards developing a robust optimization modelof earthwork allocations in roadway projects JJ.Iran J Sci Technol Trans Civ Eng,2023,47:2507-2520.7VILLAR Y,MENENDEZ M,FERNANDEZ Z,et al.Sustainable earthworks:optimization with the ICOMmethodJI.EnergRep,2020,6:404-419.8AKGUL M,YURTSEVEN H,GULCI S,et al.Evaluation of UAV-and GNSS-based DEMs for earthwork vol-umeJ.ArabJSciEng,2018,43:1893-1909.9SHEHADEH A,ALSHBOUL O,TATARI O,et al.Selection of heavy machinery for earthwork activities:amulti-objective optimization approach using a genetic algorithm JJ.Alex Eng J,2022,61(10):7555-7569.10EASA S M.Selection of roadway grades that minimize earthwork cost using linear programming JJ.TranspnRes A,1988,22A(2):121-136.11MOREB A A.Linear programming model for finding optimal roadway grades that minimize earthwork cost JJ.EurJOperRes,1996,93:148-154.12FOGEL,DAVID B.A comparison of evolutionary programming and genetic algorithms on selected constrainedoptimization problems JJ.Simulation,1995,64(6):397-404.13IBRAHIM H,ABURUKBA R O,EL-FAKIH K.An integer linear programming model and adaptive geneticalgorithm approach to minimize energy consumption of cloud computing data centers JJ.Comput Elect Eng,2018,67:551-565.14KATOCH S,CHAUHAN S S,KUMAR V.A review on genetic algorithm:past,present,and future JJ.MultimedToolsAppl,2021,80:8091-8126.15TAHERANPOUR N,TALEBI S.Development of a new efficient method using genetic algorithm for increas-ing of fuel rod life timeJ.Prog Nucl Energy,2021,131:103600.16FALLAH M K,FAZLALI M,DANESHTALAB M.A symbiosis between population based incremental learn-ing and LP-relaxation based parallel genetic algorithm for solving integer linear programming models JJ.Com-puting,2023,105:1121-1139.17张琛，詹志辉。遗传算法选择策略比较J计算机工程与设计，2 0 0 9，30（2 3）：547 1-547 4，547 8。扬州大学学报（自然科学版）第2 6 卷Optimization of conservation earthwork allocationbased on genetic algorithm with penalty functionHUO Zhenggang*,WANG Ziyang,ZHA Xiaoting,ZHANG Sensen,LU Mengyao(School of Architectural Science and Engineering,Yangzhou University,Yangzhou 225127,China)Abstract:In order to obtain a reasonable earthwork allocation design,determine the optimal pathand quantity of earthwork allocation,reduce labor intensity,reduce costs and shorten the construc-tion period,this paper first uses the linear programming method of management operations researchto establish the earthwork optimization balance model,and formulate the objective function to cal-culate the overall minimum freight.Then,based on the objective function,a genetic algorithm withpenalty function is used to eliminate equality constraints,and the optimal solution of the model isobtained through simulation calculation.The research results indicate that compared with the earth-moving allocation before optimization,the proposed method can find the optimal solution moreaccurately and provide good technical support for similar earthwork allocation.Keywords:earthwork allocation;water and soil conservation;linear programming;genetic algorithm（责任编辑秋实）