《基于遗传算法和双层结构的优化研究及其应用》由会员分享，可在线阅读，更多相关《基于遗传算法和双层结构的优化研究及其应用（87页珍藏版）》请在金锄头文库上搜索。
1、 6 基于遗传算法和双层结构的 优化研究及其应用 摘 要 在组合优化问题中 有不少问题需要在复杂而庞大的搜索空间中寻找最优解或次优解在计算此类问题时若不能利用问题的固有知识来缩小搜索空间则会产生搜索空间的组合爆炸Combinatorial Explosion因此研究能在搜索过程中自动获取和积累有关搜索空间的知识并自适应地控制搜索过程从而得到优化解的通用搜索算法一直是令人瞩目的课题理论上这类问题可通过对离散变量的有限运算步骤求得最优解但随着问题规模的扩大计算步骤会多得难以想象若离散变量数为 n组合最优化问题便成为 en数量级当 n 很大 时组 合 最 优 化 问 题 则 成 为 实 际 上 无
2、法 求 严 密 解 的NP(Non-deterministic Polynomial)完全问题 对于求解规模较大的组合优化问题虽然有各种不同的方法但无论从实用性还是求解效率上来说 基于生物进化机制的随机搜索算法遗传算法都具有相当的优越性 热交换网综合Heat Exchanger Networks Synthesis是已知的几百个 NP 完全问题中的一个在许多工业过程特别是石化化工生产过程中换热网络是一种最常用的能量交换系统它通过对冷物流和热物流进行适当的匹配用热流加热冷流用冷流冷却热流从而7 满足相应物流的温度要求 最大限度地减少辅助加热或者冷却设备的负荷提高系统热回收能力因此换热网络设计操作
3、的优劣直接影响到系统能耗的大小以及企业效益的好坏 解决这个问题涉及到如何优化网络结构以及分配相应的热负荷 本文在对热交换网综合进行深入分析的基础上提出了其本质上是一个匹配组合优化的新观点并结合矩阵模型建立了一种遗传算法与传统数学规划相结合的双层结构优化策略在上层用改进遗传算法对网络结构进行演化得出候选集合然后下层算法利用数学规划对候选集合中的个体作适应值评价即对热负荷进行最优分配并把结果返回到上层算法中根据仿真结果以及与相关文献的比较证明了此策略的有效性 关键词 组合优化遗传算法热交换网络综合双层结构 8 OPTIMIZATION BASED ON GENETIC ALGORITHMS AND
4、 TWO-LEVEL FRAMEWORK ABSTRACT In combinatorial optimization field Many of these problems call for optimal or sub-optimal solution in a very complex and large search area. Combinatorial explosion can happen if no procedure is taken to shrink the search area via original problems information. So it ha
5、s been a hot topic to find a general search method, which can adaptively control the search process by acquiring and accumulating the information about the search space. Theoretically, limited computation steps on discrete variables can solve this kind of problems. But as the size increases, the ste
6、ps required will be more than our expectation. Specifically, if the size of discrete variables is n, then corresponding combinatorial optimization will be of complexity magnitude of en; if n becomes very great, optimization would turn into a non-deterministic polynomial complete problem and cannot b
7、e solved precisely. Though there are many different solutions to this problem, GA based on mechanism of biologic evolution is preferred in terms of practicability and efficiency. Heat exchanger networks (HEN) synthesis is one of hundreds of NP complete problems. In many industrial processes, heat ex
8、changer networks are most popular utilities to recover the energy. In this system, hot streams could be cooled and cold ones heated by proper matches between them, and each stream acquires its desirable outlet temperature 9 as a result. Then the extra load of assistant coolers or heaters is cut down
9、 greatly and the energy recovery capacity of factory is improved in this way. Therefore, the synthesis of HEN is important to the minimum cost and maximum profit of certain enterprise. HEN synthesis involves two main issues: the structure optimization and heat load distribution. Based on intensive a
10、nalyses of previous works on this area, this paper considers HEN synthesis as a typical combinatorial optimization of matches, and proposes a two-level optimization strategy based on improved evolutionary algorithm and mathematical programming: at the upper level, HEN structures are evolved in EA an
11、d then, the candidates produced are evaluated using programming method at the lower level of this two-level strategy. Finally, the results obtained in this emluator are compared with those of related papers, and the validity of this strategy is demonstrated. KEY WORDS combinatorial optimization, gen
12、etic algorithms, heat exchanger networks synthesis, two-level framework strategy 上海交通大学 学位论文原创性声明 本人郑重声明所呈交的学位论文是本人在导师的指导下独立进行研究工作所取得的成果 除文中已经注明引用的内容外本论文不包含任何其他个人或集体已经发表或撰写过的作品成果对本文的研究做出重要贡献的个人和集体 均已在文中以明确方式标明 本人完全意识到本声明的法律结果由本人承担 学位论文作者签名马际成 日期2004 年 1 月 19 日 4 上海交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留使
13、用学位论文的规定同意学校保留并向国家有关部门或机构送交论文的复印件和电子版允许论文被查阅和借阅 本人授权上海交通大学可以将本学位论文的全部或部分内容编入有关数据库进行检索可以采用影印缩印或扫描等复制手段保存和汇编本学位论文 保密在 年解密后适用本授权书 本学位论文属于 不保密 请在以上方框内打 学位论文作者签名 马际成 指导教师签名王豪 日期2 0 0 4 年 1 月 1 9 日 日期2 0 0 4 年 1 月 1 9 日 上海交通大学硕士学位论文 -第 1 页 - 1 第一章 绪 论 1 . 1 引言 分层结构组合优化的研究近些年来一直是学术界和工程界讨论的热点 从理论上讲分层组合优化是一类
14、典型的存在有限个解的离散优化问题在规划决策资源分配调度等问题中应用相当广泛它所优化的对象是一些离散的变量所组成的某个集合如工序路线匹配资源等同样具有目标函数或者约束条件等优化问题的一般结构组合优化问题通常带有大量的局部极值点,往往是有约束条件的高度非线性的 NP 完全问题由于本身的组合特性其求解计算量往往随着问题规模的增大而呈指数增长因此在问题规模较大时传统的穷尽搜索算法遇到了难以克服的计算量指数爆炸的困难精确地求解组合优化问题的全局最优解一般是不可能的 解决能源的合理利用已经成为我国推进现代化经济建设的战略重点之一作为耗能大户的过程系统工业包括化工炼油建材冶金等在内更是首当其冲换热网络综合H
15、eat Exchanger Network Synthesis是过程系统工业中经常遇到的一类优化问题在上世纪六十年代就已经作为过程综合Process Integration的一个子问题而引起重视由于能耗问题是决定企业经济效益的一个重要因素 因此换热网络综合逐渐成为石化和化工企业进行热能回收的关键措施并直接影响到企业的经济效益而且从数学模型上看热交换网综合可以归于上述组合优化中的匹配问题 因此它不但与实际工业应用直接相关而且是一个具有足够复杂性的工程研究对象可用来检验和评价新的优化技术因此具有重要的实用价值和理论意义 作为热能工程的一个重要研究对象 换热网络最初的设计思想主要基于热力学原理其中以
16、 Linnhoff 教授提出的夹点分析法pinch design method最为著名12同时也有学者提出了基于数学规划方法的热交换网综合34在这种方法中HEN 被描述为一个混合整数非线性规划mixed-integer non-linear programming, MINLP 的数学模型 人工智能方法也被应用到换热网络综合问题中56取得了较好的效果近年来基于遗传算法的随机优化方法以其良好的鲁棒性和普适性引起学者的极大兴趣并取得了很多应用成果90 年代Stair上海交通大学硕士学位论文 -第 2 页 - 2 等人把遗传算法应用于过程综合的研究中78取得了成功而 Androulakis 则重点针对换热网络这个子问题进行了研究9Lewin 等提出一种利用矩阵描述换热网络
