基于模拟退火算法的可靠性优化

上商航天　２０（１２年第２期　文章编号１００６　ｌ６３０ｔ２００２）０２—００２１　０３　ＡＥＲ　ＡｆＦ　ＳＨＡＮ（　ＨＡ　基于模拟退火算法的可靠性优化　高　尚　（华东船舶Ｘ－业学院电子与信息乐　江苏镇江２１２００３）　摘要：建立了可靠性冗哥｝扰化模型，分折了各种扰化方击的扰缺点　采用模拟退盘算法解决了此问题，通过　实例路出了算法　井与启发式算法作了比较，结果表明该方法比较有效　关键词：模拟退Ｉ足算法；可靠性；优化；启发式算法　中围分类号：ＴＢＩ１４　３　文献标识码：Ａ　Ｏｐｔｉｍｉｚａｔｉｏｎ　ｏｆ　Ｓｙｓｔｅｍ　Ｒｅｌｉａｂｉｌｉｔｙ　Ｂａｓｅｄ　ｏｎ　Ｓｉｍｕｌａｔｅｄ　Ａｎｎｅａｌｉｎｇ　Ａｌｇｏｒｉｔｈｍ　ＧＡＯ　Ｓｈａｎｇ　（Ｉ）ｅｐｔ　ｏｆ　Ｅｌｅｃｔｒｏｎｉｃｓ　ａｎｄ　Ｉｎｆｏｒｍａｔｉｏｎ，Ｅａｓｔ　Ｃｈｉｎａ　Ｓｈｉｐｂｕｉｌｄｉｎｇ　Ｉｎｓｔｉｔｕｔｅ．Ｚｈｅｎｊｉａｎｇ　Ｊｉａｎｇｓｕ　２１２００３，Ｃｈｉｎａ　Ａｂｓｔｒａｃｔ：Ａ　ｒｅｄｕｎｄａｎｃｙ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｍｏｄｅｌ　ｉｓ　ｇｉｖｅｎ　ｉｎ　ｔｈｉｓ　ｐａｐｅｒ．Ｍａｎｙ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｍｅｔｈｏｄｓ　ｔｏ　ｓｏｌｖｅ　ｏｐｔｉｍｕｍ　ｍｏｄｅｌ　ａｎｄ　ｔｈｅｉｒ　ａｄｖａｎｔａｇｅｓ　ａｎｄ　ｓｈｏｒｔａｇｅｓ　ａｌｙｅ　ａｎａｌｙｚｅｄ　Ａ　ｓｉｍｕｌａｔｅｄ　ａｎｎｅａｌｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｐｕｔ　ｆｏｒｗａｒｄ　ｃ￣ｍｌｐａｒｉｎｇ　ｗｉＩｈ　ｈｅｕｒｉｓｔｉｃ　ａｌｇｏｒｉｔｈｍ，ａｎｄ　ｉｔｓ　ｅｆｆｅｃｔｉｖｅｎｅｓｓ　ｌ５　ｉｌｌｕｓｔｒａｔｅｄ　Ｋｅｙｗｏｒｄｓ：Ｓｉｍｕｌａｔｅｄ　ａｎｎｅａｌｉｎｇ　ａｌｇｏｒｉｔｈｍ；Ｒｅｌｉａｂｉｌｉｔｙ；Ｏｐｔｉｍｉｚａｔｉｏｎ；Ｈｅｕｒｉｓｔｉｃ　ａｌｇｏｒｉｔｈｍ　０　号Ｉ舌　可靠性问题是系统设计、研究和运行过程中必　须考虑的关键因素之一。由于设计时受到包括费　．＝１，２，・一，（ｉ＝１，２，一－，　ｊ　式中：ｃ　为系统费用；Ｒ　为系统可靠度；ｃ　为第ｉ　种部件的单价；．／２，为第ｚ子系统冗余第ｉ种部件的　用、重量、体积、功耗等各种因素的限制，因而系统可　靠性最优问题引起了广泛的重视并得到了充分的研　个数，且ｚ　≥ｌ；Ｒ　（，３２　）为第ｉ子系统冗余＿ｒ．个部件　时的第ｉ子系统的可靠度，且Ｒ．（　．）　ｌ一（１一　Ｐ　）　；　为第ｉ种部件的可靠度；Ｒ　为系统要达到　的预定的可靠度。　究。有许多改进系统可靠性的方法，但实践证明，比　较好的要算冗余这一方法　这里冗余是指在原部件　基础上并联同一部件。　ｌ冗余优化模型　假设系统由　个独立子系统组成，在每个子系　统中使用同一种部件（图１），冗余优化模型为　＇１ｌ：　岛岛国　，Ｅ＝－ＩＩ母Ｊ　ｌ＿　ＩＩ　ｊＩ　ｌＩ母ｊＩｍｉｎＣ　＝∑ｆ　ｓ．ｔ　Ｒ　＝Ｉ　Ｒ　（　）≥Ｒ　０　图ｌ串．并联系统　Ｆｉｇ　ｔ　Ｓｅｒｉｅｓ－ｐａｒａｌｌｅｌ　ｓｙｓｔｅｍ　系统冗余可靠性优化方法较多，文献［２：中作了－　收藕日期：２００１，１０　２９；修圊日期：２００１一ｌ２．¨　作者筒舟：高尚（１９７２），男、硕士．讲师，从事武器系统分　综述，推荐了十几种方法，但在用于大规模非线性规　划问题时，仅有少数算法被证明是有效的，没有哪一　种算法被证明比其他的算法更优越。文献［４］给出　析、系统工程理论与优化研究。　维普资讯 http://www.cqvip.com

上海航天　ＡＦＲＯＳＰＡＣＥ　ＳＨＡＮＧＨＡ　２帅２年第２朝　许多优化模型。启发式算法虽简单直观，但启发　ｍｉｎｉ（Ｊｘｊ　式信息不易找，而且有点盲目性；整数规划得到的是　ｓ．ｔ　ｇ　（Ｘ）≥０（　＝Ｊ．２，…，Ⅳ　）　整数解，但为了应用整数规划，把非线性目标函数和　模拟退火算法的一般框架　如下：　约束条件转化成线性形式，则是一项困难的任务；动　给定起、止“温度”＿ｒ、＿ｒ　和退火速度　，模拟参　态规划存在着维数“灾难”问题，并且对三个以上约　数初始化Ｘ　束问题，求解相当困难；极大值原理求解三个以上约　ｗｈ　ｌｅ（＿ｒ＞Ｔｎ）ｄｏ　柬问题也是困难的；几何规划只限于求解可用泊松　在ｘ　的邻域内模拟产生随机扰动ＡＸ；　函数形式表述的问题；序列无约束极小化方法、修正　计算扰动所引起的目标函数（能鼍）值的变化　的单纯形序列搜索、广义的拉格朗日函数法在用于　ｂＥ；　、、　大型非线性规划问题中被证明是有效的方法，虽然　若△Ｅ≤Ｏ，接受薪值；否则若ｅｘｐ（一ｂＥ／＇／’）＞　解是非整数，但是解决非冗余问题很有效。对于同　ｒａｎｄ（０，１）（ｒａｎｄ（０，１）表示ｏ～１之间的随机数），则　时确定最优部件数和可靠度的问题，是一类混合整　也接受新值，否则就拒绝；　数非线性问题．解决这类问题很困难。文献［２］推荐　确定新的参数值，若扰动被接受，则ｘ　一　１　了将Ｈｏｏｋｅ和Ｊｅｅｖｅｓ等人提出的模式搜索法与Ａｇ—　ＡＸ，否则Ｘ０一ｘ０；　ｇａｒｗａ［等人提出的启发式算法组合起来的方法　这　若接受新值，降温Ｔ—　Ｔ、，否则不降温；　种方法首先假设部件的可靠度，然后用启发式算法　Ｅ『ｌｄ　确定最优冗余数，最后用Ｈｏｏｋｅ和Ｊｅｅｖｅｓ的模式搜　索法来进行序列搜索。这里首先采用启发式算法来　求解，然后再采用模拟退火算法来求解，最后作一比　３启发式算法　采用启发式算法解这个问题，其思路如下：从　较。　（　１，　，，…，　）＝（１，１，－－，１）出发，然后每一步在　某个位置上加一个同种部件，直到系统可靠度大于　２模拟退火算法　或等于预定的可靠度Ｒ　为止。至于在每一步究竟　模拟退火算法思想最早由Ｍｅｔｒｏｐｏｌｉｓ在１９５３　在哪个位置上加一个部件．以保证上述算法得到的　年提出，１９８３年Ｋｉｒｋｐａｔｒｔｃｋ等成功地将退火思想引　结果是最优的，原则是选取Ｉ）　（　）＝［１ｎＲ　（５／＂　＋１）　入组合优化领域　模拟退火算法用于优化问题的出　一ｌｎＲ　（　）］／ｃ　（ｉ＝１，２，，一，ｎ）中最大的Ｄ　（∞）　发点是基于物理中固体物质的退火过程与一般优化　（即Ｄ　（ｚ　）＝ｍａｘ　Ｄ　（　）　）。下一步将在第ｉ。个　问题的相似性。算法的基本思想是从一结定解开始　的．从邻域中随机产生另一个解，接受准则允许目标　子系统的位置上加一个第ｉ　种部件。　函数在有限范围内变坏，它由一控制参数ｆ决定，其　作用类似于物理过程中的温度　。对于控制参数ｔ　４模拟退火算法与启发式算法的比较　的每一取值，算法持续进行“产生新解一判断一接受　已知５种部件的可靠度和费用分别为Ｐ．＝　或舍弃”的迭代过程。对应着固体在某一恒定温度下　０　９６、Ｐ２＝０　９３、Ｐ３＝０　８５、　４＝０．８０、　ｓ＝０　７５、　ｌ　趋于热平衡的过程。经过大量的解变换后，可以求　＝３元、ｃ２＝１２元、ｃ　＝８元、ｃ４＝５元、Ｃ５＝ｌ０元，要　得给定控制参数值时优化问题的相对最优解。然后　求Ｒ　＝０　９。其模拟退火算法的步骤为：　减小控制参数　的值，重复执行上述迭代过程。当　（１）结定起、止“温度”Ｔ＝１０　０００、Ｔ　＝１和退　控制参数逐渐减小并趋于零时，系统亦越来越趋于　火速度ｎ＝０．９，模拟参数初始化ｘｎ（４，４．４，４，４），　平衡状态，最后系统状态对应于优化问题的整体最　＝（Ｏ．９６，Ｏ　９３，Ｏ　８５，０　８，０　７５），Ｃ＝（３，１２，８，５，　优解。该过程也称冷却过程。由于固体退火必须缓　１０）；　慢降温，才能使固体在每一温度下都达副热平衡，最　（２）若Ｔ＞Ｔｏ，转（３），否则算法停止，输出ｘ（【；　终趋于平衡状态。因此，控制参数的值必须缓慢衰　（３）计算目标函数值ＣＳ０＝ＣＸ　：；　减，才能确保模拟退火算法最终趋于优化问题的整　（４）随机产生变量　．，若ｒａｎｄ（０，１）≥０　５，则　体最优解　ｏ７Ｌ＂　一　＋１，否则　一　一ｌ，此时变量记为Ｘ１；　对于一般优化问题：　（５）判断是否满足约束条件，若满足转（６），否　维普资讯 http://www.cqvip.com

■ｌ　２００２吓第２瑚　高　尚基于模拟退＾算法的町靠性优化　２３　刚转（４）；　统级数”比较大时，采用模拟退火算法比较台适，　（６）计算目标函数（　＝（、ｘ　ＡＥ＝ＣＳ１　若△Ｅ≤０，接受新值，　．．卜　１，１、一口Ｉ、，转　（２），否则若ｅｘｐ（一ＡＥ／Ｔ）＞ｒａｎｄ（０．１），也接受新　并且可以得到全局最优解。当　比较小时，启发式　算法比较方便，但它只能得到“满意解”，不一定是全　局最优解。　值，ｘｎ—ｘｌ，丁一口Ｔ，转（２）；否则转（４）；　运行程序得到最优解（２，２，２，３，２），此时总费用　为８ｌ元。这需要说明一下，运行结果可能不一定相　同　但结果一定在这解的附近，是一个满意解。图２　是模拟退火算法的过程，纵坐标为最小费用，横坐标　为迭代算迭代次数。　雹　靠　０　５０　１００　１５０　２００　２５０　选代次数　图２模拟退火算法的计算过程　Ｆｉｇ　２（￣ｔ　Ｌｅｕｌａｔｉｎｇ　ｐｒｏｃｅｓｓ　ｏｆ　ｓｉｍｕｌａｔｅｄ　ａｎｎｅａ［ｉｎｇ　ａｌｇｏｒｉｔｈｍ　采用启发式算法每步的结果如表ｌ所示，计算　过程如图３所示　图中横坐标为迭代算迭代次数，　左侧纵坐标为费用，右侧纵坐标为可靠性。　从模拟退火算法和启发式算法的计算过程来　看、模拟退火算法从可行域中寻求最优解，而启发式　算法是初始点不在可行域内，逐步满足要求。当系　表１　启发式算法每步结果　Ｔａｂ一１　Ｅａｃｈ　ｓｔｅｐ　ｒｅｓｕｌｔ　ｏｆ　ｈｅｕｒ￣ｔｉｃ　ａｌｇｏｒｉｔｈｍ　步骤　Ｒ．　１　ｌ　３８　０　４５５　３　２　１　４３　０　５４６　３　３　１　５３　１　２　２　０　７８５　４　５　２　３　６４　０　８ｌ６　９　２　２　６９　０　８４４　１　７　１　２　３　８ｌ　Ｏ　９０３　２　图３启发式算法计算过程　Ｆｉｇ　３　Ｕａ　Ｌｃｕｌａｔｌｎｇ　ｐｒｃｏｅｓｓ　ｏｒ　ｈｅｕｒｉｓｔｉｃ　ａ［ｇｏｒｌｔｈｍ　５结束语　模拟退火算法比启发式算法的解空问更大些．　并且可以从局部最优的“陷阱’’中跳出　更能求得优　化问题的整体最优解，又不失简单性和通用性。因　此对大多数优化问题而言　模拟退火算法要优于局　部搜索算法　所得近似最优解的质量也比局部搜索　算法好。　可靠性优化问题是一个非线性整数混台规划问　题，特别当系统级数很大时　用模拟退火算法解决可　靠性优化问题确实有效　并能得到全局最优解　参考文献　［１］曹晋华、程侃可靠性数学引论［Ｍ］北京：科学出版　社、１９８６　［２］ＴＩＬＬＭＡＮ　Ｆ　Ａ，ＨＷＡＮＧ［’Ｌ　ＫＵＯ　Ｗ系统可靠性　最优化［Ｍ　刘炳章，洋北京：同防Ｔ、　出版社．　ｉ９８８　．３］刑文循　谢金星现代优化汁算方法［Ｍ］北京：清华大　学出版社，１　９９９　：４］　高　尚可靠性优化方法　Ｊ］上海航天，２００ｌ，ｌ　８（３）　［５］张德富，顾卫刚　沈　平一种解旅行商问题的并行模　拟退火算法ｌＭ］计算机研究与发展，Ｉ９９５．（２１　【６　ｊ　ＡＡＲＴＳ　Ｅ，ＫＯＲＳＴ　Ｊ　Ｓｉｍｕｌａｔｅｄ　ａｎｎｅａｌｉｎｇ　ａｎｄ　ｂｏｌｔｚ　㈨ｎ　ｍａｃｈｉｎｅ［Ｍ：ｊｏｈｎ　Ｗｉｌｅｙ＆ｓ０　Ｎｅｗ　Ｙｏｒｋ　Ｉ９８９