直接搜索模拟退火法在水污染控制系统规划中的应用-申玮

直接搜索-模拟退火法在水污染控制系统规划中的应用申玮1,郭宗楼1,刘国华2(11浙江大学生物系统工程与食品科学学院,浙江杭州310027;21浙江大学建筑工程学院,浙江杭州310027)摘要:在研究新近发展起来的模拟退火算法及其各种改进算法的基础上,提出并构造了一种水污染控制规划的以记忆为基础的直接搜索-模拟退火算法(DSA),并将其应用于新疆乌鲁木齐水磨河排放口最优化处理规划中,在满足水质要求的同时,得到了更优的全局最优解。DSA具有编程简单、易实现、运算效率高、运用方便、结果稳定等优点,为水污染控制系统规划提供了一个新的方法,具有很好的应用前景。关键词:直接搜索-模拟退火算法;水污染控制;最优规划中图分类号:X522文献标识码:A文章编号:1001-6791(2004)04-0445-03收稿日期:2003-04-25;修订日期:2003-07-22基金项目:国家863计划资助项目(2001AA242121);教育部博士点基金资助项目(1999049306)作者简介:申玮(1976-),女,新疆阿克苏人,讲师,硕士,主要从事水环境科学规划与控制等研究。E-mail:swslsl@yahoo1com1cn在水污染控制系统规划中,其关键是求模型目标函数的优化解问题。由于目标函数一般是非线性问题,通常采用3类方法处理:¹将目标函数分段线性化,用线性规划技术对其求解,这种方法一般难以得到满意的最优解;º直接采用非线性规划方法求解,结果往往只能得到局部最优解;»动态规划方法,由于它是在时间过程中,依次分阶段决策,规划成本高而且效果不理想。所以无论是线性规划、非线性规划还是动态规划方法都难以完全满足系统规划要求。近年来,遗传算法、模拟退火等全局最优化新型随机非数值优化算法为水污染控制系统规划提供了新途径。遗传算法是基于达尔文的生物进化规律的一种群体优化算法,它同时从多个状态出发,通过选择、交叉、变异等手段,不断地向最优解逼近;而模拟退火法是基于热力学原理建立起来的随机优化算法,它在优化结果解的精度和优化速度上优于遗传算法[1,2]。但遗传算法存在种群退化,模拟退火法也存在收敛速度慢等不足,一些学者在深入研究的基础上对上述两种算法进行了改进,特别是在模拟退火算法方面取得了喜人的成果。如将POWELLS算法与模拟退火相结合构造的混合优化算法,通过缩小搜索区域,改善了优化解的精度[3]。还有一种改进后的自适应模拟退火算法,它通过依据算法搜索过程中的进展信息,将邻域搜索与温度控制有机结合,从而动态地确定温度参数的变化和对不同的邻域施加的搜索次数,该算法能独立于初始温度的选择,具有更强的鲁棒性(Robust)[4]。但以上这些算法改进没有从根本上改进模拟退火算法的运算效率和稳定性。本文基于对模拟退火算法的分析以及对各种模拟退火的改进算法的综合,构造了一种水污染控制规划的直接搜索-模拟退火算法(DirectSearch-SimulatedAnnealingAlgorithm,DSA),经过水污染控制系统规划的大量实验测试,能够显著地改进模拟退火算法的运算效率及其稳定性,给水污染控制规划提供了新的途径。1DSA算法的思想与描述以记忆为基础的DSA算法不同于其他改进模拟退火算法,其最主要的特点在于它采用了一组工作点而不是仅仅一个工作点,而且新算法在执行过程中不需要对原有各部分功能优化。DSA算法的基本思想是:考虑优化求解minf(x)时,首先从一个包含N个点和其目标值的集合A和初始点x开始(x作为初始Markov链的起点),集合A中的N个点与初始点x均是在定义域内随机生成,集合A中目标第15卷第4期2004年7月水科学进展ADVANCESINWATERSCIENCEVol115,No14Jul1,2004函数最好值为fl;目标函数最差值为fh;在控制参数t0下,由当前点x的邻域产生下一个点y,如果f(y)[fh,则y被接受为当前点,否则y仅以exp[-(f(y)-fh)/t0]被接受;如果y点被接受,则y和f(y)取代集合A中的最差点与fh并在集合A中重新找出新的fh和fl,重复上述过程直至Markov链终止,然后减小控制参数t0的值,重复上述过程,如此反复,直至满足某个停止准则时算法终止。其中,在控制参数为t0时,其Markov链的长度为Ldt,如果f(y)