1、研究生课程（论文类）试卷2 0 1 4 /2 0 1 5 学年第 一 学期课程名称： 课程代码： 论文题目： 学生姓名： 专业学号： 学院： 课程（论文）成绩：课程（论文）评分依据（必填）：任课教师签字： 日期： 年 月 日课程（论文）题目：简述最优化方法及应用内容：摘要：最优化方法作为研究各种系统的优化途径及方案，为决策者提供科学决策的依据。该文简单叙述了最优化方法及其处理问题的步骤和在各领域的应用，并详细介绍了最优化方法中的一种遗传算法，论述了遗传算法的基本原理和特点，为了特别说明其特点还进行了举例说明。关键词：最优化方法；遗传算法在生产过程、科学实验以及日常生活中，人们总希望用最少的人力
2、、物力、财力和时间去办更多的事，获得最大的效益，在管理学中被看作是生产者的利润最大化和消费者的效用最大化，如果从数学的角度来看就被看作是“最优化问题”。在最优化的研究生教学中我们所说的最优化问题一般是在某些特定的“约束条件”下寻找某个“目标函数”的最大(或最小)值，其解法称为最优化方法。最优化方法（也称做运筹学方法）是近几十年形成的，它主要运用数学方法研究各种系统的优化途径及方案，为决策者提供科学决策的依据。最优化方法的主要研究对象是各种有组织系统的管理问题及其生产经营活动。最优化方法的目的在于针对所研究的系统，求得一个合理运用人力、物力和财力的最佳方案，发挥和提高系统的效能及效益，最终达到系
3、统的最优目标。实践表明，随着科学技术的日益进步和生产经营的日益发展，最优化方法已成为现代管理科学的重要理论基础和不可缺少的方法，被人们广泛地应用到公共管理、经济管理、工程建设、国防等各个领域，发挥着越来越重要的作用。本章将介绍最优化方法的研究对象、特点，以及最优化方法模型的建立和模型的分析、求解、应用。主要是线性规划问题的模型、求解（线性规划问题的单纯形解法）及其应用运输问题；以及动态规划的模型、求解、应用资源分配问题。简单点，从数学意义上说从数学意义上说，最优化方法是一种求极值的方法，即在一组约束为等式或不等式的条件下，使系统的目标函数达到极值，即最大值或最小值。从经济意义上说，是在一定的人
4、力、物力和财力资源条件下，使经济效果达到最大（如产值、利润），或者在完成规定的生产或经济任务下，使投入的人力、物力和财力等资源为最少。不同类型的最优化问题可以有不同的最优化方法，即使同一类型的问题也可有多种最优化方法。反之,某些最优化方法可适用于不同类型的模型。最优化问题的求解方法一般可以分成解析法、直接法、数值计算法和其他方法。解析法：这种方法只适用于目标函数和约束条件有明显的解析表达式的情况。求解方法是：先求出最优的必要条件，得到一组方程或不等式，再求解这组方程或不等式，一般是用求导数的方法或变分法求出必要条件，通过必要条件将问题简化，因此也称间接法。直接法：当目标函数较为复杂或者不能用变
5、量显函数描述时，无法用解析法求必要条件。此时可采用直接搜索的方法经过若干次迭代搜索到最优点。这种方法常常根据经验或通过试验得到所需结果。对于一维搜索(单变量极值问题)，主要用消去法或多项式插值法；对于多维搜索问题(多变量极值问题)主要应用爬山法。数值计算法：这种方法也是一种直接法。它以梯度法为基础，所以是一种解析与数值计算相结合的方法。其他方法：如网络最优化方法等。一、最优化方法的发展简史公元前500年古希腊在讨论建筑美学中就已发现了长方形长与宽的最佳比例为1.618,称为黄金分割比。其倒数至今在优选法中仍得到广泛应用。在微积分出现以前，已有许多学者开始研究用数学方法解决最优化问题。例如阿基米
6、德证明：给定周长，圆所包围的面积为最大。这就是欧洲古代城堡几乎都建成圆形的原因。但是最优化方法真正形成为科学方法则在17世纪以后。17世纪，I.牛顿和G.W.莱布尼茨在他们所创建的微积分中，提出求解具有多个自变量的实值函数的最大值和最小值的方法。以后又进一步讨论具有未知函数的函数极值，从而形成变分法。这一时期的最优化方法可以称为古典最优化方法。第二次世界大战前后，由于军事上的需要和科学技术和生产的迅速发展，许多实际的最优化问题已经无法用古典方法来解决，这就促进了近代最优化方法的产生。近代最优化方法的形成和发展过程中最重要的事件有： 以苏联.康托罗维奇和美国G.B.丹齐克为代表的线性规划；以美国
7、库恩和塔克尔为代表的非线性规划；以美国R.贝尔曼为代表的动态规划；以苏联.庞特里亚金为代表的极大值原理等。这些方法后来都形成体系，成为近代很活跃的学科，对促进运筹学、管理科学、控制论和系统工程等学科的发展起了重要作用。在第二次世界大战以前, 处理最优化问题的数学方法主要是古典的微分法和变分法。二次大战中, 由于生产与军事上的需要,提出了大量不能用上述古典方法解决的问题, 从而产生了“ 运筹学” , 它包括如线性规划、非线性规划、动态规划等最优化方法。此后, 最优化方法不断得到丰富和发展。特别从六十年代以来, 由于近代科学技术和生产发展的需要, 以及电子计算技术的飞速发展, 使最优化方法进入了一
8、个蓬勃发展的新时期, 不仅方法如雨后春笋般涌现, 而且应用也日益广泛, 成为近代应用数学的一个重要分支。随着炼油及化工生产的大型化和复杂化, 使得一个决策的好坏, 往往会带来重大的经济后果。因此必须事先进行周密的分析和计算，力求得到最优的方案。大型快速电子计算机的出现，使一些过去只能定性地或粗略地分析比较的问题，如今已能借助电子计算技术寻求其最优解了。因此最优化方法在炼油和化工中的应用前途十分宽广。它不仅在生产过程的研究开发、规划设计、投资建设和操作控制中，而且在生产企业的计划安排、产品分配、物资调运和经济分析中都可以发挥一定的作用。可以预料, 在我国向四个现代化进军的新长征中, 它将会发挥更
9、大的作用。二、用最优化解决问题的工作步骤用最优化方法解决实际问题，一般可经过下列步骤：提出最优化问题，收集有关数据和资料；建立最优化问题的数学模型,确定变量,列出目标函数和约束条件；分析模型，选择合适的最优化方法；求解，一般通过编制程序，用计算机求最优解；最优解的检验和实施。上述 5个步骤中的工作相互支持和相互制约，在实践中常常是反复交叉进行。2.1 目标函数与约束条件凡是最优化问题, 都有要达到“最优”的目标, 把它写成数学形式称为目标函数,这里以J来表示, 它是n个独立变量ui（i=1,2、n) 的函数, 简记为J=f（u） （2-1-1）其中，u=（u1，u2，、un）T （2-1-2）
10、即u为n维列向量。当u的各分量ui( i=1，2,、 n )为一组特定的数值时, 称为一个“决策”( 因场合的不同也称为设计或控制)。实际上有些决策在技术上是不现实的或明显地不合理的,甚至是违反安全而不允许的。因此变量u的取值范围通常都有一个限制,这种限制称为约束条件。当以不等式表示时,称为不等式约束；当以等式表示时,称为等式约束。满足约束条件的点的全体集合,构成了该问题的可行域,记为R。R中的任意点,虽然不一定是最优解,但至少是可行的。当然,最优解应是可行解,如果它存在的话,必在可行域内。若R包括其边界上的所有点,称R 为闭域；若R的边界有一部分不属于它,称R为开域。三、最优化方法的应用最优
11、化一般可以分为最优设计、最优计划、最优管理和最优控制等等四个方面。最优设计:世界各国工程技术界,尤其是飞机、造船、机械、建筑等部门都已广泛应用最优化方法于设计中，从各种设计参数的优选到最佳结构形状的选取等，结合有限元方法已使许多设计优化问题得到解决。一个新的发展动向是最优设计和计算机辅助设计相结合。电子线路的最优设计是另一个应用最优化方法的重要领域。配方配比的优选方面在化工、橡胶、塑料等工业部门都得到成功的应用,并向计算机辅助搜索最佳配方、配比方向发展(见优选法)。最优计划:现代国民经济或部门经济的计划，直至企业的发展规划和年度生产计划，尤其是农业规划、种植计划、能源规划和其他资源、环境和生态
12、规划的制订,都已开始应用最优化方法。一个重要的发展趋势是帮助领导部门进行各种优化决策。最优管理：一般在日常生产计划的制订、调度和运行中都可应用最优化方法。随着管理信息系统和决策支持系统的建立和使用，使最优管理得到迅速的发展。最优控制：主要用于对各种控制系统的优化。例如，导弹系统的最优控制，能保证用最少燃料完成飞行任务,用最短时间达到目标;再如飞机、船舶、电力系统等的最优控制，化工、冶金等工厂的最佳工况的控制。计算机接口装置不断完善和优化方法的进一步发展，还为计算机在线生产控制创造了有利条件。最优控制的对象也将从对机械、电气、化工等硬系统的控制转向对生态、环境以至社会经济系统的控制。3.1 遗传
13、算法 本文主要讲述最优化方法中的一种即遗传算法。 在自然界,由于组成生物群体中各个体之间的差异,对所处环境有不同的适应和生存能力,遵照自然界生物进化的基本原则,适者生存、优胜劣汰,将要淘汰那些最差个体,通过交配将父本优秀的染色体和基因遗传给子代,通过染色体核基因的重新组合产生生命力更强的新的个体与由它们组成的新群体。在特定的条件下,基因会发生突变,产生新基因和生命力更强的新个体；但突变是非遗传的, 随着个体不断更新,群体不断朝着最优方向进化,遗传算法是真实模拟自然界生物进化机制进行寻优的。在此算法中,被研究的体系的响应曲面看作为一个群体，相应曲面上的每一个点作为群体中的一个个体,个体用多维向量
14、或矩阵来描述, 组成矩阵和向量的参数相应于生物种组成染色体的基因,染色体用固定长度的二进制串表述,通过交换、突变等遗传操作,在参数的一定范围内进行随机搜索,不断改善数据结构,构造出不同的向量,相当于得到了被研究的不同的解,目标函数值较优的点被保留,目标函数值较差的点被淘汰。由于遗传操作可以越过位垒，能跳出局部较优点,到达全局最优点。3.2 遗传算法的起源与发展遗传算法( Genetic Algorithm, GA) 是模拟自然界生物进化机制的一种算法, 即遵循适者生存、优胜劣汰的法则, 也就是寻优过程中有用的保留, 无用的则去除。在科学和生产实践中表现为, 在所有可能的解决方法中找出最符合该问
15、题所要求的条件的解决方法, 即找出一个最优解。这种算法是1960 年由Holland 提出来的，其最初的目的是研究自然系统的自适应行为, 并设计具有自适应功能的软件系统。它的特点是对参数进行编码运算, 不需要有关体系的任何先验知识, 沿多种路线进行平行搜索, 不会落入局部较优的陷阱, 能在许多局部较优中找到全局最优点, 是一种全局最优化方法。近年来, 遗传算法已经在国际上许多领域得到了应用。1985年召开了第1届有关遗传算法的国际会议, 第1部关于这方面的专著在1989 年问世。遗传算法是一种有广泛应用前景的算法, 但是它的研究和应用在国内尚处于起步阶段。3.3 遗传算法的基本步骤一般把Hol
16、land1975年提出的GA称为传统的GA，它的主要步骤如下：1、编码。GA在进行搜索之前先将解空间的数据表示成遗传空间的基因型串结构数据，这些串结构数据的不同组合便构成了不同的点。2、初始群体的生成。随机产生几个初始串结构数据，每个串结构数据称为一个个体，N个个体构成一个群体。GA以这N个串结构数据作为初始点开始迭代。3、适应性值评估检测。适应性函数表明个体或解的优劣性，问题不同，适应性函数的定义方式也不同。4、选择。选择的目的是为了从当前群体中选出优良的个体，使它们有机会作为父代为下一代繁殖子孙。进行选择的原则是适应性强的个体为下一代贡献一个或多个后代的概率大，选择实现了达尔文的适者生存原
17、则。5、交叉。交叉操作是遗传算法中最主要的遗传操作。通过交叉操作可以得到新一代个体，新个体组合了其父辈个性的特性，交叉体现了信息交换的思想。6、变异。变异首先在群体中随机选择一个个体，对于选中的个体以一定的概率随机地改变串结构中某个串的值。同生物界一样，GA中变异发生的概率很低，通常取0.0010.01之间。变异为新个体的产生提供了机会。3.4 遗传算法的特点遗传算法作为一种快捷、简便、容错性强的算法,在各类结构对象的优化过程中显示出明显优势:1、搜索过程不直接作用在变量上, 而是作用于参数集进行了编码的个体上。此编码操作,使得遗传算法可直接对结构对象(集合,序列,矩阵,树,图,链和表)进行操
18、作。2、搜索过程是从一组解迭代到另一组解,采用同时处理群体中多个个体的方法,这就降低了陷人局部最优解的可能性,并易于并行化。3、遗传算法采用概率的变迁规则来指导搜索方向, 不采用确定性搜索规则。4 对搜索空间没有任何特殊要求, 只利用性信息，不需要导数等其他辅助信息，适应范围更广。3.5 遗传算法的应用GA是一种通用的优化算法,其编码技术和遗传操作比较简单,优化不受限制性条件的约束,其搜索过程是从问题解的一个集合开始的,而不是从单个个体开始的，具有隐含并行搜索特性,也就大大减小了陷人局部极小值的可能。正是由于其具有以上突出的优点,遗传算法几乎渗透到从工程到社会科学的各个领域。遗传算法可处理连续
19、变量参数的优化问题,特别是适用于复杂非线性问题的处理。可用于NMR脉冲形状分析、RNA核苷酸测定、DNA构象分析、分子识别和设计、变量选择等,在分析化学、环境科学、机械设计中的应用也非常广泛。结构分析在有机化学和药物化学领域中的应用是非常广泛的,遗传算法主要应用在需要分子三维构像信息的时候,这在合成新的有机化合物和药物、充分合理地利用天然资源具有重要的意义,邓勃对这方面的应用作了简要的评述。侯廷军等对遗传算法在计算机辅助药物分子设计中的应用做了系统阐述。蔡文生等提出一种采用整数编码和基于节点基因交换方式的遗传算法,并应用于化学结构图的同态研究。遗传算法在一组随机生成的表示目标结构与查询结构节点
20、间映射关系的整数串中进行逐步优化,直到找出与查询结构匹配的映射,从而实现化学结构图的同态匹配。卢佩章等将遗传算法引入色谱峰解析程序,结合色谱峰模型及峰形经验公式实现了恒温色谱图的全自动解析。陈闽军等提出了一种基于遗传算法的色谱指纹峰配对识别方法, 该方法根据色谱指纹图谱峰分布特性初选出若干标定峰, 将其存入一个候选标定峰库, 同时根据这些候选标定峰从待测指纹图谱中选出相应的候选标定峰, 以遗传算法对指纹峰进行识别。四、结合本专业对最优化方法的理解4.1 最优设计能源问题仍是当前世界的热点问题，世界上很多问题都是由能源问题引起，所以能源研究不仅可以避免我们的子孙后代遭受没有能源的生活，还关乎着世
21、界的和平与发展。据统计，冷冻和空调行业占据了很大一部分能源，根据国际制冷协会提供的数据，每年世界上大约有15%的电能是用来驱动冷冻和空调设备。这是一个相当惊人的数字，也为科技工作者尽快找到解决办法敲响了警钟。因此对换热器的最优设计也随之成了专业的热点问题，肋片管、螺纹管成了优化设计换热器一个重要的方向。4.2 最优控制理工科的学生应该都知道，实验是完成一项科研必不可少的步骤，而实验数据的处理却是个复杂、繁琐的问题，特别是实验组数比较多的情况下，处理起来更加麻烦。基于这个问题计算机编程无不失为一个最优的控制方法。五、结语本文简述了最优化方法及其应用，阐述了遗传算法的基本步骤及其特点，并进行了举例
22、分析。本文的研究得到了如下的结论，遗传算法不是最优化的唯一方法，为了用最少的人力、物力、财力和时间去办更多的事，获得最大的效益，人们应该去研究和探索更多的最优化方法。遗传算法也不是一种单纯的优化算法，不是传统的确定性的计算工具, 复杂问题, 特别是动态的复杂问题的求解也不能(或不可能)是确定性的,应建立新的评价标准；遗传算法的理论正在深入,应用日趋广泛,但它仅是生物进化系统的简单近似模拟,其本身的发展也是不断进化的过程,理论研究需要引入新的数学工具、吸收生物学的最新成果,应用研究的成败依赖于对遗传算法和其所解决问题的深刻理解。参考文献：1 沈忠耀 最优化方法及其应用 石油炼制（1980）.2 沈忠耀 最优化方法及其应用 石油炼制（1980）.3 中国科学院教学研究所，“优选法”，科学出版社（1975）.4 徐学文 中国科学院计算中心 最优化方法简介.5 刘庄 李有道 基础知识讲座 最优化计算方法.6 席裕庚 控制理论与应用 遗传方法综述（1996）7 李华昌 谢淑兰 易忠胜 遗传算法的原理与应用（2005）8 许斗 钱峰 遗传算法的应用研究进展（2003）9 王春水 肖学柱 陈汉明 计算机仿真 遗传算法的应用举例（2005）7
