离散变量结构优化方法研究现状及趋势

李彦苍，赵丽娜

(河北工程大学土木工程学院，河北邯郸056038)

在实际结构设计中，有时出现某些或全部设计变量只能取限定离散值的情况［1]。例如，钢筋混凝土结构构件的截面尺寸需要模数制的原则，钢结构构件的截面需要考虑型钢表或截面要求和特定组的离散值。采用平常的优化设计方法，必须通过处理所得解以满足工程设计规范和各项技术标准，但这种经过连续变量优化方法处理后得到的离散结果不一定可行或最优［2]。因此，建立适合离散变量结构优化设计的方法是很有工程实用价值的［3]。

本文介绍了离散变量结构优化设计理论及设计方法的新成果，并对其发展及研究方向做出展望，指出了各离散变量结构优化方法在使用过程中的优缺点，并提出蚁群算法是一个有发展前途的离散变量结构优化方法。

1 离散变量结构优化设计特点

由于设计变量具有离散性，所以离散变量结构优化设计数学模型中目标函数和约束函数具有不连续的特点，这样就使得连续变量优化模型转化为不可微的、非凸规划模型，可行域变成可行集，连续变量优化中的许多有效的解析数学算法和优化条件对此也无效，如各种梯度算法中的敏度分析法，K－T条件，各对偶算法等。

离散变量结构优化设计的难点在于［5]:

(1)解析数学对此无能为力。在数学上，离散变量优化问题属于组合优化问题，即从所有可能的组合中寻找最优解。此问题随设计变量个数的增加，组合数随其呈指数增加，遂出现“组合爆炸”的现象。若在寻找最优解过程中搜索的组合个数不能用明确的多项式表示，称这种问题为NP困难问题。NP困难问题的难度在于随着设计变量个数的增加，组合个数迅速增加［6－7]。对于大规模问题指数时间算法所花的时间是巨大的，甚至难以解决。

(2)在形状优化中主要包括截面变量的优化，另外还有形状(坐标)变量优化。同时处理性质不同的两类变量优化不光工作量大，难度也较大。

(3)拓扑优化与形状优化近似，除截面变量优化外，还有拓扑(结点间有、无杆件连接)变量的优化。在处理不同性质的两类变量优化困难下，还有杆件删除，尤其是杆件恢复策略，若只有杆件的删除而无杆件的恢复策略，通常情况得不到最优拓扑解。

(4)布局优化包括截面、形状和拓扑三类性质的变量优化，很明显同时处理三类不同性质的变量困难更大，计算工作量也增大较多。

(5)结构类型优化，这是最高层次的优化，难度也最大，迄今未见有关文献。

2 离散变量结构优化方法

离散变量结构优化设计方法可分为三种:精确算法、近似算法、启发式算法［8]。文献［8－9]对传统的优化设计方法如枚举法、分支定界法、圆整法、割平面法、隐枚举法、罚函数法、巴拉斯法、离散复合形法、整数梯度法等方法做了介绍和评价。这里主要介绍最近几年新兴起来的算法。

2.1 遗传算法

遗传算法是根据生物进化理论抽象出来的一种随机、并行和自适应的优化算法，包括选择、交叉和变异等过程［10]。其基本思想是，将设计变量编码表示成染色体，染色体群通过复制、杂交和变异等过程，不断进化并收敛到求解问题的最优解。对全局信息有效利用和隐含并行性是该法的两大特点，特别是对目标函数、设计变量及可行域无特殊要求的特点，使得该方法的适用范围较广，天然适用于传统寻优方法解决不了的复杂和非线性问题，对于离散变量的优化较有效［11]。张明辉等［12]采用遗传算法对结构进行形状优化，并给出了适应度函数的确定方法及对应力约束和几何约束的处理方法。

遗传算法在离散变量结构优化设计中表现了其独特的优势外，在结构优化设计中该算法最大的劣势在于结构重分析次数过大，搜索效率偏低，还容易出现过早收敛等问题。对此，许多专家学者通过深入研究提出了各种改进的遗传算法。如分层遗传算法，跨世代异物种重组大变异(CHC)算法，自适应遗传算法，Messy遗传算法，并行遗传算法，基于小生境技术的遗传算法等，还出现遗传算法与其他算法(如相对差商法、混沌算法、梯度算法等)相复合，形成混合遗传算法［3，13]。这些改进的遗传算法已在离散变量结构优化研究中得到大量应用，并取得了一定的成效［14－15]。相信在今后遗传算法会得到更大的发展。

2.2 模拟退火法

模拟退火法是基于固体物质退火过程原理及蒙特卡罗迭代求解策略的一种随即寻优算法，其思想来源于统计力学。在模拟固体退火过程中，由一组参数控制算法的进程，这组参数被命名为冷却速度进度表，在此进程中算法通过Metropolis接受准则不断选择可行点。并且概率突跳法使得算法避免陷入局部最优解，所以得到全局最优解的机会增大。其中重要的参数有温度衰减参数和寻优步长，两者都作用于寻优的速度和精确度［16]。因为用不着任何梯度信息和 Hessian矩阵，所以该算法对解决离散变量优化设计问题较有效［17]。

为进一步提高经典模拟退火算法的性能，相关学者提出一些改进方法。都志辉等［18]提出一种混合SPMD模拟退火算法，使得算法的求解速度明显加快;高齐圣等［19]提出一种改进的模拟退火算法;高占远［20]将单纯形法与模拟退火算法结合并提出改进措施，都具有较好的求解效率和全局优化能力。

2.3 人工神经网络

人工神经网络属于一种较新的启发式搜索方法，它主要是通过Hopfield［21]神经网络对结构进行优化设计。非静定三杆结构的优化和焊接结构的优化问题就是Dhingra通过Hopfield神经网络来解决的;陆今桂［22]利用Hopfield神经网络模型对离散变量结构优化问题进行研究。李兴旺［23]等人通过深入研究人工神经网络在工程结构优化设计中的应用，提出适用于工程结构优化的人工神经网络模型，并用数值仿真证明该方法优于其他方法。此外还有人提出了混沌神经网络模型，模糊神经网络模型等，发展到今天已存在上百种神经网络模型。

2.4 禁忌搜索法

禁忌搜索算法是针对在优化过程中局部搜索容易陷入局部最优解而无法得到全局最优解的问题而提出的。其主要思想是在搜索过程中标记搜索到的局部最优解对象，并在进一步的搜索过程中尽量避开它们，从而保证有不同的有效搜索路径 ［5，24] 。

算法的搜索过程分为三步［25]:产生设计点的局部范围，接受容许的设计，对Tabu表更新。Glover对该算法作了详细介绍［26]，Bland作了补充并应用于桁架的优化设计［27]。禁忌搜索法常与其他方法结合使用，例如，遗传算法、神经网络等，目的是克服某种单纯算法的弱点［28]。

2.5 蚁群算法

生物学家发现生物界中的蚂蚁群在寻找食物的路径上会释放一种蚂蚁特有的分泌物－信息素，一定范围内的蚂蚁能够感受到这种物质，并且倾向于朝着浓度较高的路径方向移动，蚂蚁的这种行为被相关学者称为是一种信息正反馈现象。由于此种生物现象的启发，意大利学者 Marco Dorigo于1992年在他的博士论文中提出蚁群优化(Ant Colony Optimization，ACO)［29－30]，该算法最早成功地用于解决著名的旅行商问题［31]。

ACO算法的主要特点概括为［32]:采用分布式控制，不存在中心控制;个体的交互作用表现为群体的复杂行为;每个个体只能感知局部信息，无法直接获得整体信息;个体可以改变环境并进行间接通讯;采用改进全局搜索方法求解全局最优解;求解时不需要问题具有严格数学性质;个体通过相互交换信息来提高适应环境的能力;具有潜在并行性，能同时搜索多个点。

经过十几年的发展，蚂蚁算法有诸多改进［33－42]，经过各种数值仿真结果的检验表明，该算法在组合优化方面具有诸多优越性，可以作为求解组合最优化问题的新型通用启发式方法，但也有相关文献资料表明该算法还存在有待改进的地方［43－48]。

总结以上，蚁群算法是近几年逐渐发展起来的一种随机优化方法，该算法优化的优点主要表现在:①可行解选择机制;②信息素更新机制;③群体协作机制，这样的操作过程使蚁群算法具有很强的发现较优解的能力。因此，该算法不仅可用于求解单目标优化问题，还可用于求解多目标优化问题。在组合优化中已展现出其独特的优点，并且蚁群算法还具有易于操作、便于与其他方法相复合的特点，由此可见，蚁群算法是一很有发展前途的启发式算法。

2.6 其他方法

目前，进行离散变量结构优化设计研究工作的人很多，如郭鹏飞等人提出了基于离散变量结构优化的斐波那契遗传算法、拟满应力设计法［1，49];董锦坤等人提出的单向搜索算法［50];李永梅等人把近似满应力设计方法和相对差商法结合起来形成离散变量结构优化两级算法［51]。另外还有基于生物免疫系统的免疫算法，它由免疫学理论和观察到的免疫功能、原理和模型启发而设计;2004年李泉永、龚雨兵把基于社会性动物(蚁群、蜂群、鸟群等)的自组织行为(觅食、迁徙、筑巢等)的群搜索算法应用于离散变量结构优化中［52]。2006年王希云、刘瑞芳研究了粒子群算法在离散变量结构优化中的应用［53]。2007年张梅凤、邵诚、甘勇等探讨了人工鱼群优化算法在离散变量结构优化中的应用［54]。很多学者都在尝试将这些智能算法运用到结构优化设计中来，但由于它们的应用探索还处于起步阶段，还有许多方面没考虑到。因此，这些新兴算法的设计也有许多有待改进之处。

3 离散变量结构优化设计发展展望

从离散变量结构优化的发展方向，我们认为还有以下几个方面:

(1)针对具体问题时:我们现在所考虑的模型可能和实际问题的模型有差异，怎样把现有的研究成果应用到具体问题中，结合工程实际问题进行离散变量结构优化设计的研究，是优化研究人员应该关注的一个方向。

(2)多目标问题:在现实中，有的优化问题具有多个优化目标，由于这些目标之间相互矛盾、相互约束，难以同时得到最优结果，这就出现了多目标优化问题。因此，从寻求协调各项指标关系的方向进行多目标离散变量结构优化的研究，以求得更加符合实际的结构是非常有意义的研究课题。

(3)可靠性方面:结构的可靠性逐步成为判断现代结构优化设计的重要因素，基于结构可靠性的离散变量结构优化设计的研究应该是未来的一个重要研究方向。

(4)发展高层次的结构优化设计方法:在形状(几何)、拓扑、布局优化方面应加大研究的力度。

(5)将研究理论较成熟的启发式算法(如遗传算法、人工神经网络等)与计算机科学中运用的优化方法相复合，目的是寻求精确度高、收敛效果较快速平稳的启发式算法，以应用到离散变量结构优化设计中。

(6)在发展结构优化设计软件方面加大研究力度，以便于优化设计应用技术范围的扩大。

4 结语

由于设计变量离散的特点，使得离散变量结构优化设计问题研究起来有一定的困难，而其在实际工程中又具有深远的应用前景，因此，对离散变量结构优化设计的研究是一个内容广泛、值得深入进行的方向，离散变量结构截面优化设计是研究离散变量结构优化设计问题的基础。离散变量优化设计属于NP困难问题，加之需要迭代运算，使得结构重分析次数巨大，所以优化算法的计算效率、收敛速度成为选用优化算法首先考虑的方面。由于到目前为止还没有一种精确的数学算法能够解决NP困难问题，因此，解决离散变量结构截面优化设计问题首先要寻找精度高、收敛速度快的启发式算法，新兴的蚁群算法在这方面逐步显示其优势。考虑到实际工程应用的需要，离散变量结构优化设计还应满足结构设计规范要求的各种条件以及工程规范中的各种约束限制。虽然目前对离散变量结构优化设计的研究已经取得了不少的研究成果，但仍然需要进行更深入的研究。

［1] 郭鹏飞，韩英仕，魏英姿.离散变量结构优化设计的拟满应力设计方法［J] .工程力学，2000，17(1):94－98.

［2] 郭鹏飞，韩英仕.离散变量结构优化设计的拟满应力遗传算法［J] .工程力学，2003，20(2):95－99.

［3] 张延年，刘斌，郭鹏飞.基于混合遗传算法的建筑结构优化设计［J] .东北大学学报，2003，24(10):985－988.

［4] HAN Y S，GUO P F.A Hybrid genetic algorithm for structural optimization with discrete variables［C] //Proceedings of the First China－Japan－Korea Joint Symposium on Optimization of Structural and Mechanical System.Xi’an:Xidian University Press，1999，157 －164.

［5] 孙焕纯，柴山，王跃方.离散变量结构优化设计发展、现状及展望［J] .力学与实践，1997，19(4):7－11.

［6] 周书敬，薄涛，史三元.混合算法在轻钢结构优化中的应用［J] .河北工程大学学报:自然科学版，2011，28(2):71－74.

［7] PAPADIMITRIOU C H.组合最优化－算法和复杂性［M] .北京:清华大学出版社，1988.

［8] 孙焕纯，柴 山，王跃方.离散变量结构优化设计［M] .大连:大连理工大学出版社，2002.

［9] 李京涛，何丽丽，高瑞贞，等.改进遗传算法在桁架拓扑优化中的应用［J] .河北工程大学学报:自然科学版，2009，26(3):19－21.

［10] 王小平，曹立明.遗传算法―理论、应用与软件实现［M] .西安:西安交通大学出版社，2002.

［11] RYOO J，HAJELA P.Handling variable string lengths in GA －based structural topology optimization［J] .Structural and Multidisciplinary Optimization，2004，26(5):318－325.

［12] 张明辉，王尚锦.遗传算法在结构形状优化中的应用［J] .机械科学与技术，2001，20(6):824－826.

［13] 谭 虓，刘自山，李凌宇.基于模拟退火遗传算法的IIR数字滤波器参数优化设计［J] .四川理工学院学报:自然科学版，2011，24(4):426－430.

［14] 刘立民，潘 伟，庞彦军，等.多阶段复合型遗传算法的结构及性能研究［J] .河北工程大学学报:自然科学版，2010，27(2):107－112.

［15] 王红霞，高瑞贞，张京军.基于不动点理论的改进遗传算法［J] .河北工程大学学报:自然科学版，2010，27(3):100－103.

［16] 康立山，谢 云，尤矢勇，等.非数值并行算法――模拟退火算法［M] .北京:科学出版社，1997.

［17] 钟太勇，彭先萌.模拟退火算法在药物动力学参数反演中的应用［J] .四川理工学院学报:自然科学版，2011，24(2):175－177.

［18] 都志辉，李三立，吴梦月，等.混合SPMD模拟退火算法及其应用［J] .计算机学报，2001，24(1):256－265.

［19] 高齐圣，张嗣癫，潘德惠，等.参数设计的模拟退火并行计算法［J] .系统工程理论与实践，2002，5(8)，41－44.

［20] 高占远.改进的单纯形模拟退火算法［J] .南阳师范学院学报，2007，6(3):30－32.

［21] HOPFIELD J.Neural networks and physical systems with emergent collective computer abilities［J] .Proc Natl Acad Sci，1982，79(6):2554 －2558.

［22] 陆金桂.基于人工神经网络及多级技术的结构优化与实践［D] .武汉:华中理工大学，1997

［23] 李兴旺，满广生.神经网络方法在结构优化计算中的应用［J] .人民长江，2002，33(9):33－35.

［24] 刘清海，赵文清，丁予展.禁忌搜索离散化技术［J] .起重运输机械，2001，12(5):11－13.

［25] 王凌.智能优化算法及其应用［M] .北京:清华大学出版社，2002.

［26] GLOVER F.Tabu search，part II［J] .ORSA J Comp，1990(2):4－32.

［27] BLAND J A.Discrete variable optimal structural design using Tabu search［J] .Structural Optimum，1995，10:87－93.

［28] 罗海林，霍达.离散变量桁架结构拓扑优化的遗传禁忌搜索算法［J] .河南科学，2005，23(6):909－911

［29] BLUM C.Ant colony optimization:introduction and recent tends［J] .Physics of Life Reviews，2005，2(4):353－373.

［30] DORIGO M，VITTORIO M，ALBERTO C.The ant system:optimization by a colony of cooperating agents［J] .IEEE Transactions on Systems，1996，26(1):29－41.

［31] 劳眷.蚁群算法求解TSP问题若干改进策略的研究［J] .科学技术与工程，2009，9(9):2 459－2 462.

［32] COLORNI A，DORIGO M，MANIEZZO V，et al.Ant system for job － shop scheduling.Belgian［J] .Oper Res Statist Comput Sci，1994，34:39 －53.

［33] 杨洁，杨胜，曾庆光.基于信息素强度的蚁群算法［J] .计算机应用，2009，29(3):865－869.

［34] 段海滨，王道波，朱家强.蚁群算法理论及应用研究的进展［J] .控制与决策，2004，19(12):1 322－1 340.

［35] 杨中秋，张延华，郑志丽.基于改进蚁群算法对最短路径问题的分析与仿真［J] .沈阳化工学院学报，2009，23(2):150－153.

［36] 李士勇.蚁群算法及其应用［M] .哈尔滨:哈尔滨工业大学出版社，2004.

［37] 孙焘，王秀坤，刘业欣.一种简单蚂蚁算法及其收敛性分析［J] .小型微型计算机系统，2003，21(8):1524－1526.

［38] 吴庆洪，张纪会，徐心和.具有变异特征的蚁群算法［J] .计算机研究与发展，1999，36(10):1240－1245

［39] 丁建立，陈增强，袁著祉.基于自适应蚂蚁算法的动态最优路由选择［J] .控制与决策，2003，18(6):751－753.

［40] MARCO D，CHRISTIAN B.Ant colony optimization theory:A survey［J] .Theoretical Computer Science，2005，344:243 －278.

［41] GAMBARDEILA L M，DORIGO M，MIDDENDORF M.Guest editorial:special section on ant colony optimization［J] .IEEE Transactions on Evolutionary Computation，2002，6(4):317－319.

［42] 曾黄麟，黄 艳.基于信息最大覆盖率蚁群算法的Rough集属性优化约简［J] .四川理工学院学报:自然科学版，2011，24(4):452－456.

［43] 胡祥培，丁秋雷，李永先.蚁群算法研究评述［J] .管理工程学报，2008，22(2):74－79.

［44] 杨剑锋.蚁群算法及其应用研究［D] .浙江:浙江大学，2007.

［45] 陈吴.蚁群优化算法的原理及其应用［J] .湖北大学学报:自然科学版，2006，28(4):350－352.

［46] STUTZLE T，HOOS H.Max－min ant system［J] .Future Generation Computer Systems Journal，2000，16(8):889－914.

［47] HUANG K L，LIAO C J.Ant colony optimization combined with taboo search for the job shop scheduling problem［J] .Computers＆Operations Research，2008，35:1030－1046.

［48] DONATI A V，MONTEMANNI R，CASAGRANDE N，et a1.Time dependent vehicle routing problem with a multi ant colony system［J] .European Journal of Operational Research，2008，185:1174－1191.

［49] 郭鹏飞.离散变量结构优化的斐波那契遗传算法［J] .辽宁工学院学报，2003，23(4):1－4.

［50] 张延年，刘剑平，刘 斌，等.改进单向搜索遗传算法的工程结构优化设计［J] .力学季刊，2005，26(2):293－298.

［51] 李永梅，张毅刚.考虑结构整体稳定性的单层网壳优化设计［J] .建筑结构，2006，36(4):77－80.

［52] 李泉永，龚雨兵.离散变量结构优化中的一种有效仿生算法［J] .现代制造工程，2004(5):32－34.

［53] 王希云，刘瑞芳.混沌粒子群算法及其在桁架结构优化设计中的应用［J] .太原科技大学学报，2006，27(6):478－480，485.

［54] 张梅凤，邵诚，甘勇，等.基于变异算子与模拟退火混合的人工鱼群优化算法［J] .电子学报，2007，34(8):1381－1385.