1.引言 优化设计英文名是optimization design，从多种方案中选择最佳方案的设计方法。它以数学中的最优化理论为基础，以计算机为手段，根据设计所追求的性能目标，建立目标函数，在满足给定的各种约束条件下，寻求最优的设计方案。 第二次世界大战期间，在军事上首先应用了优化技术。1967年，美国的R.L.福克斯等发表了第一篇机构最优化论文。1970年，C.S.贝特勒等用几何规划解决了液体动压轴承的优化设计问题后，优化设计在机械设计中得到应用和发展。随着数学理论和电子计算机技术的进一步发展，优化设计已逐步形成为一门新兴的独立的工程学科，并在生产实践中得到了广泛的应用。通常设计方案可以用一组参数来表示，这些参数有些已经给定，有些没有给定，需要在设计中优选，称为设计变量。如何找到一组最合适的设计变量，在允许的范围内，能使所设计的产品结构最合理、性能最好、质量最高、成本最低（即技术经济指标最佳），有市场竞争能力，同时设计的时间又不要太长，这就是优化设计所要解决的问题。一般来说，优化设计有以下几个步骤：①建立数学模型。②选择最优化算法。③程序设计。 ④制定目标要求。⑤计算机自动筛选最优设计方案等。 2.数学模型 优化设计的数学模型是对优化设计工程问题的数学描述，它包含设计变量、目标函数和设计约束三个基本要素。 2.1设计变量 2.1.1基本参数 a、定义：在设计过程中进行选择变化并最终确定的各项独立参数称为设计变量。 b、说明：在设计选择过程中，这些设计变量是变量，但它们一旦被确定后，设计对象也 就完全确定了。最优化设计是研究怎样合理地优选这些设计变量的一种现代设计 方法。在设计过程中，凡根据设计要求事先给定的，不是设计变量而是设计常量。 2.1.2设计方案的表现形式 a、设计空间：由n个设计变量为坐标所组成的时空间称作设计空间。 b、设计变量的表示法 （1）坐标表示法：一维问题→一个设计变量→数轴上的一个点 二维问题→两个设计变量→平面直角坐标系上的向量 三维问题→三个设计变量→空间直角坐标系的向量
本论文中用到的优化方法主要是零阶方法和一阶方法。 1 零阶优化方法（又称子问题逼近方法） 该方法仅需要因变量的数值，而不需要其导数信息；因变量（目标函数及状态函数）首先通过最小二乘拟合值近似，而约束极小化问题用罚函数转换成无约束问题，极小化过程在近似的罚函数上进行迭代，直至获得解得收敛。 由于该方法建立在目标函数及状态变量的近似基础上，故需要一定量的初始设计变量数据。初始数据可根据其它优化工具和方法直接生成，或随机生成。方法的第一步把极小化约束问题用近似方法描述每一个因变量，即 对目标函数，有 ?()()f f X f X ε=+ 对状态变量，有 ?()()?()()?()()g h w g X g X h X h X w X w X εεε=+=+=+ 具体的近似形式可取为有变量交叉项的全二次多项式。如对目标函数， 0 ?n n n i i ij i j i i j f a a x b a x =++∑∑∑ 近似表达的实际形式(即表达式中的系数)随迭代过程而变。一次迭代过 程中，近似表达式中的系数i a ，ij b 由加权最小二乘技术确定。如对目标函数， 最小二乘技术可描述为对其误差范数取极小来获得，即: ^2() ()()1min () n j j j j E f f αφ==-∑ 式中，()j φ =与设计变量J 相关的权系数； n α=现行设计集合数 权系数按下述方法之一确定： 有较小目标函数的那些设计集合有较高的权系数(基于目标函数)； 接近最佳设计的设计集合有高权值(基于设计变量值)； 可行设计集合权值高，而不可行设计集合权值低(基于可行性)； 基于上述三类权值的综合： 可取所有权值为1，即 ()1j φ=。 由上式知，需要一定量的设计集合来形成近似，否则需产生随机设计集合，即 当2n n α<+时，生成随机设计集合； 当2n n α≥+时，计算近似式（n 为设计变量维数）。 b ）极小化问题近似 由上述对函数的近似化，约束极小化问题可重写为：
智能计算读书报告（二） 智能优化算法 姓名：XX 学号：XXXX 班级：XXXX 联系方式：XXXXXX
一、引言 智能优化算法又称为现代启发式算法，是一种具有全局优化性能、通用性强、且适用于并行处理的算法。这种算法一般具有严密的理论依据，而不是单纯凭借专家的经验，理论上可以在一定时间内找到最优解或者近似最优解。所以，智能优化算法是一数学为基础的，用于求解各种工程问题优化解的应用科学，其应用非常广泛，在系统控制、人工智能、模式识别、生产调度、VLSI技术和计算机工程等各个方面都可以看到它的踪影。 最优化的核心是模型，最优化方法也是随着模型的变化不断发展起来的，最优化问题就是在约束条件的限制下，利用优化方法达到某个优化目标的最优。线性规划、非线性规划、动态规划等优化模型使最优化方法进入飞速发展的时代。 20世纪80年代以来，涌现出了大量的智能优化算法，这些新颖的智能优化算法被提出来解决一系列的复杂实际应用问题。这些智能优化算法主要包括：遗传算法，粒子群优化算法，和声搜索算法，差分进化算法，人工神经网络、模拟退火算法等等。这些算法独特的优点和机制，引起了国内外学者的广泛重视并掀起了该领域的研究热潮，并且在很多领域得到了成功地应用。 二、模拟退火算法（SA） 1. 退火和模拟退火 模拟退火算法(Simulated Annealing，SA)最早的思想是由N. Metropolis 等人于1953年提出。1983 年,S. Kirkpatrick 等成功地将退火思想引入到组合优化领域。它是基于Monte-Carlo迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法从某一较高初温出发，伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。模拟退火算法是一种通用的优化算法，理论上算法具有概率的全局优化性能,目前已在工程中得到了广泛应用，诸如VLSI、生产调度、控制工程、机器学习、神经网络、信号处理等领域。 模拟退火算法是通过赋予搜索过程一种时变且最终趋于零的概率突跳性，从而可有效避免陷入局部极小并最终趋于全局最优的串行结构的优化算法。 模拟退火其实也是一种贪心算法，但是它的搜索过程引入了随机因素。模拟
浙江大学 博士学位论文 一种新型的智能优化方法—人工鱼群算法 姓名：李晓磊 申请学位级别：博士 专业：控制科学与工程 指导教师：钱积新 2003.1.1
加，，Ｚ掌博士学位论文一ＩＩＩ－ 摘要 （优化命题的解决存在于许多领域，对于国民经济的发展也有着巨大的应用前景。随着优化对象在复杂化和规模化等方面的提高，基于严格机理模型的传统优化方法在实施方面变得越来越困难。厂吖 本文将基于行为的人工智能思想通过动物自治体的模式引入优化命题的解决中，构造了一种解决问题的架构一鱼群模式，并由此产生了一种高效的智能优化算法一人工鱼群算法。 文中给出了人工鱼群算法的原理和详细描述，并对算法的收敛性能和算法中各参数对收敛性的影响等因素进行了分析；针对组合优化问题，给出了人工鱼群算法在其中的距离、邻域和中心等概念，并给出了算法在组合优化问题中的描述；针对大规模系统的优化问题，给出了基于分解协调思想的人工鱼群算法；给出了人工鱼群算法中常用的一些改进方法；给出了人工鱼群算法在时变系统的在线辨识和鲁棒ＰＩＤ的参数整定中两个应用实例ｊ最后指出了鱼群模式和算法的发展方向。 ｆ在应用中发现，人工鱼群算法具有以下主要特点： ?算法只需要比较目标函数值，对目标函数的性质要求不高； ?算法对初值的要求不高，初值随机产生或设定为固定值均可以； ?算法对参数设定的要求不高，有较大的容许范围； ?算法具备并行处理的能力，寻优速度较快； ?算法具备全局寻优的能力； 鱼群模式和鱼群算法从具体的实施算法到总体的设计理念，都不同于传统的设计和解决方法，同时它又具有与传统方法相融合的基础，相信鱼群模式和鱼群算法有着良好的应用前景。∥ ／ 关键词人工智能，集群智能，动物自治体，人工鱼群算法，ｆ优∥ ，ｌ／。７
一、优化算法及其应用 1.简介 共轭梯度法（Conjugate Gradient ）是介于最速下降法与牛顿法之间的一个方法，它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算Hesse 矩阵并求逆的缺点，共轭梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一。 在各种优化算法中，共轭梯度法是非常重要的一种。其优点是所需存储量小，具有步收敛性，稳定性高，而且不需要任何外来参数。 2.算法原理 共轭梯度法是利用目标函数梯度逐步产生共轭方向作为线搜索方向的方法，每次搜索方向都是在目标函数梯度的共轭方向，搜索步长通过一维极值算法确定。 设二次函数为1 ()2T T f X C b X X AX =++，其中C 为常数，,b X 为n 维列向 量，A 为对称正定矩阵，用共轭梯度法求()f X 的极小点： 共轭梯度法探索的第一步是沿负梯度方向。即()k X 点按()()()k k S f X =-?方向找到(1)k X +，然后沿着与上一次探索方向()k S 相共轭的方向(1)k S +进行探索直达到最小点*X 。 令()(1)(1)()k k k k S f X S β++=-?+。 上式的意义就是以原来的负梯度()()()k k f X S -?=的一部分即()k k S β，加上新的负梯度()(1)k f X +-?，构造(1)k S +。 在上式中k β的选择，应使n 维欧氏空间n E 中的两个非零向量()k S 与(1)k S +关于矩阵A 共轭。即 (1)() (0,1,2,...1)T k k S AS k n +??==-?? 因 1()2 T T f X C b X X AX =++ ，故有()f X b AX ?=+ 若令 ()()()()k k k g f X b AX =?=+ ()(1)(1)(1)k k k g f X b AX +++=?=+
M ac hi neBuil di ng Auto m atio n,D ec2007,36(6):5~6,9 现代优化设计方法的现状和发展趋势 王基维1,熊伟2,李会玲1,汪振华3 (1.宁波职业技术学院,浙江宁波315800;2.湖南生物机电职业技术学院,湖南长沙410126; 3.南京理工大学,江苏南京210094) 摘要:优化设计是近年来发展起来的一门新学科,为机械设计提供了一种重要的科学设计方 法。优化设计在解决复杂设计问题时,能从众多设计方案中寻到尽可能完美或最适宜的设计 方案。对现代优化设计方法进行了概括和总结,展望了现代优化设计的发展方向和发展趋势。 关键词:优化设计;机械设计;发展趋势 中图分类号:T H122文献标识码:B文章编号:167125276(2007)0620005202 Develop ing T rend on M odern O pt im a l Design M ethods WANG J i2wei1,XI ONG W ei2,LI H u i2li ng1,WANG Zhen2hua3 (1.Ni ngbo Voca ti on Te chno l ogy C o ll e ge,N i n gbo315800,C h i na; 2.Huna n B i o l ogy Me c ha ni c a la nd E l e c tri c a lP ro f e ss i ona lTe chno l ogy C o ll ege,C ha ngsha410126,C h i na; 3.Na n ji ng Un i ve rs ity o f S c i e nc e a nd Te chno l o gy,Na n ji ng210094,C h i n a) Abstr ac t:As a new d i s c i p l i ne,o p tm i a l de s i gn p rov i de s an m i p o rtan t sc i en tifi c de s i gn m e t h od f o r e ng i nee https://www.doczj.com/doc/4e12110883.html, i ng op tm i a ld es i gn, t he y can fi nd o ut a nea rl y pe rf e ct o r op tm i um des i gn s ch em e fr om l o ts o f feas i b l e ap p r o ache s.T he p ape r s um m a ri ze s t he de ve l o p i ng trend a nd d ir e cti o n o f t he m ode rn op tm i a l des i gn m e t hod s. K ey word s:op tm i a ld es i g n;m a ch i n e des i gn;de ve l o p t re nd 0引言 机械设计与制造是机械工程领域中最重要的内容,而机械设计又是机械制造的前提。优化设计(opti m a l de2 si gn)是近年来发展起来的一门新的学科,优化设计为机械设计提供了一种重要的科学设计方法,在机械设计上起着重要的作用,使得在解决复杂设计问题时,能从众多的设计方案中寻到尽可能完美的或最适宜的设计方案[1]。实践证明,在机械设计中采用优化设计方法,不仅可以减轻机械设备质量,降低材料消耗与制造成本,而且可以提高产品的品质和工作性能[2]。文中初步论述了机械优化设计方法的发展现状和趋势。 优化设计方法[3]是数学规划和计算机技术相结合的产物,它是一种将设计变量表示为产品性能指标、结构指标或运动参数指标的函数(称为目标函数),然后在产品规定的性态、几何和运动等其它条件的限制(称为约束条件)的范围内,寻找满足一个目标函数或多个目标函数最大或最小的设计变量组合的数学方法。优化设计方法已成为解决复杂设计问题的一种有效工具。 1优化设计方法及应用现状 优化设计的基础和核心是优化理论和算法。迄今为止,己有上百种优化方法提出,这里重点介绍以下几种优化方法[4,5]。 a)线性逼近法:线性逼近法SLP是将原非线性问题转化为一系列线性优化问题,通过求解线性优化问题得到原问题的近似解。根据形成线性优化的方法不同,可以得到不同的线性逼近法。常用的线性逼近法有近似规划法和割平面法; b)遗传算法[2,6,14]:遗传算法GA(genetic a l gorith m s)是一种基于生物自然选择与遗传机理的随机搜索算法。它是1962年首先由美国密执安大学的J.H.H olland教授提出、随后主要由他和他的一批学生发展起来的[7],并在1975年的专著中作了介绍,首先提出了以二进制串为基础的基因模式理论,用二进制位串来模拟生物群体的进化过程。进化结束时的二进制所对应的设计变量的值即为优化问题的解。GA方法的主要优点是具有很强的通用优化能力,它不需要导数信息,也不需要设计空间或函数的连续性条件,其优化搜索具有隐性并行性,可以多点同时在大空间中作快速搜索,因此有可能获得全局最优解。由于G A有着其他优化算法不可比拟的优点,因此,GA的应用非常广泛,取得大量研究应用成果。在结构优化设计方面的如离散结构的遗传形状优化设计[8]、悬臂扭转结构和梁结构的优化设计[9]、桁架和薄壁的结构优化问题[10]等。在文献[11]中对平面四杆机构的遗传优化设计进行了研究。文献[12]介绍了一个用于ZL40装载机的直齿圆锥齿轮差速器的优化设计问题,用GA中的实数编码进行优化求解,取群体大小为50,交叉率为0.2,变异率为0.5,经过120代的进化并经圆整后得到最优解。文献[15]中通过把机械方案设计过程看作是一个状态空间的求解问题,用遗传算法控制其搜索过程,完善了新的遗传编码体系,为了适应新的编码体系重新构建了交叉和变异等遗传操作,并利用复制、交换和变异等操作进行一次次迭代,最终自动生成一组最优的设计方案。 此外,G A还应用在函数优化、机械工程、结构优化、电工、神经网络、机器学习、自适应控制、故障诊断、系统工程调度和运输问题等诸多领域中[13]; #5 #
经典优化算法：单纯形法、椭球算法(多项式算法)，内点法、无约束的优化算法包括：最速下降法（steepest）、共轭梯度法、牛顿法（Newton Algorithm）、拟牛顿法（pseudo Newton Algorithms）、信赖域法。约束优化算法包括：拉格朗日乘子法（Augmented Lagrangian Algorithms），序列二次规划（ＳＱＰ）等 现代：遗传算法、蚁群算法、模拟退火算法、禁忌搜索、粒子群算法、现代优化算法是人工智能的一个重要分支，这些算法包括禁忌搜索（tabu search)、模拟退火(simulated annealing)、遗传算法(genetic algorithms)人工神经网络(nearal networks)。 贪婪算法和局部搜索、模拟退火算法（Simulated Annealing Algorithm），人工神经网络（Artificial Neural Network），禁忌搜索（Tabu Search）相继出现。最近，演化算法（Evolutionary Algorithm）, 蚁群算法（Ant Algorithms），拟人拟物算法，量子算法、混合算法 经典优化算法和启发式优化算法都是迭代算法，但是，它们又有很大区别：1.经典算法是以一个可行解为迭代的初始值，而启发式算法是以一组可行解为初始值；2.经典算法的搜索策略为确定性的，而启发式算法的搜索策略是结构化和随机化；3.经典算法大多都需要导数信息，而启发式算法仅用到目标函数值的信息；4.经典算法对函数性质有着严格要求，而启发式算对函数性质没有太大要求； 5.经典算法的计算量要比启发式算法小很多。比如，对于规模较大且函数性质比较差的优化问题，经典算法的效果不好，但一般的启发式算法的计算量太大。 优化算法的主要由搜索方向和搜索步长组成。搜索方向和搜索步长的选区决定了优化算法的搜索广度和搜索深度。经典优化算法和启发式优化算法的区别主要是由其搜索机制不同造成的。经典算法的搜索方向和搜索步长是由局部信息（如导数）决定的所以只能对局部进行有效的深度搜索，而不能进行有效广度搜索，所以经典的优化算法很难跳出局部最优。启发式优化算法，为了避免像经典优化算法那样陷入局部最优，采用了相对有效的广度搜索，不过这样做使得在问题规模较大的时候计算量难以承受。 纵观优化算法的发展，完美的算法是不存在的。我们评价算法好坏的标准： （１）算法收敛速度； （２）算法使用范围（普适性）；
研究生课程论文及评阅书 （2013—2014学年下学期） 论文题目：几种现代优化算法的比较研究课程名称：智能优化方法及应用 任课教师：周永权 授课时间：2014年2月日至2014年6月日 学号：2013081203402 姓名：吴丽佳 专业名称：计算机应用技术 所在学院：信息科学与工程学院
课程论文格式要求 1．课程论文一律使用标准A4复印纸打印，以左侧为准装订成册，本页装订在封面的背面。 2．课程论文格式按照《广西民族大学学报》论文的格式要求实行。 3．论文打印的格式要求： （1）论文标题（使用黑体二号加黑；一级标题、二级标题、三级标题分别使用宋体三号、四号及小四号并加黑）； （2）摘要、关键字（需使用宋体小四号）； （3）正文（使用宋体小四号，行距23磅）； （4）参考文献（使用宋体五号）。 4．“任课教师的评语”放在最后，单独一页。
几种现代优化算法的比较研究 摘要：现代最优化算法比较常见的有遗传算法、粒子群算法、群体复合形进化算法、鱼群算法、模拟退火算法和蚁群算法。文章主要是对遗传算法、粒子群算法和鱼群算法三个算法的优化性能进行比较。首先介绍了三个算法的基本思想和算法优化过程，以此可以了解三种算法有着自身的特点和优势，促进理解后面不同的优化结果和改进方向。文章中，将三种算法分别对这三个函数用VC编出程序，得出优化结果，再针对结果分析算法。三个典型函数特点各不同，但对算法的优化能力要求都比较高，在不同方面考验了算法的收敛和爬山功能。最后，通过分析三个函数的九个优化结果，提出这三种算法的优点和不足，并列出改进措施。从分析结果可以看出遗传算法要优于另两种算法，并且其改进的余地也是最大的，粒子群算法的优化结果次之，鱼群算法的优化结果相对来说是最差的，但三种算法都可以进行改进以达到更好的优化结果。 关键词：优化；遗传算法；粒子群算法；鱼群算法；比较 Abstract: Modern optimization includes genetic algorithm, particle swarm algorithm, multi-complex algorithm, fish school algorithm, Simulated Annealing algorithm and ant colony algorithm. The paper mainly compares the optimization abilities of genetic algorithm, particle swarm algorithm and fish school algorithm. Firstly, the article introduces the basic ideas and the optimization processes of the three algorithms, from which the characteristics and advantages of the three algorithms will be found out, after that, the optimization results and the ways of improvements behind will be understood easily. Secondly, the three algorithms program with VC for the three functions, so get the results of optimization and analyze them. The three representative functions have specialties from each other, but they have one same point which is having much more demands on the algorithms, which tests the abilities of astringency and mountain climbing. At last, through analyzing the nine optimization results of three functions, the paper explains the advantages and the disadvantages of the three algorithms, and puts forward the improvement means. From the conclusion, genetic algorithm is much better than the other two optimization algorithms, and its room of improvement is the most maximum in the three algorithms too. The article also
现代设计方法论文课题名称：现代设计—优化设计 班别：卓越交Y131 姓名：刘xx 学号; 2013002070xx 2015年7月
摘要：优化设计是在计算机广泛应用的基础上发展起来的一项新技术,是根据最优化原理和方法综合各方面因素,以人机配合方式或“自动探索”方式,在计算机上进行的半自动或自 动设计,以选出在现有工程条件下的最佳设计方案的一种现代设计方法。其设计原则是最优设 计:设计手段是电子计算机及计算程序;设计方法是采用最优化。 关键词：优化方法；数学模型；优化应用；MATLAB 一·现代设计——优化设计 优化设计主要包括两部分内容，一是优化设计的建模技术；另一是优化设计问题的求解 技术。如何将一个实际的设计问题抽象成一个优化设计问题，并建立起符合实际要求的优化 设计数学模型，这是优化技术的关键。建立实际问题的优化数学模型，不仅需要掌握优化设 计方法的基本理论，更重要的是要具有该设计领域的设计经验。 目前，它的内容主要包括优化设计、可靠性设计、设计方法学、计算机辅助设计、动态 设计、有限元法、工业艺术造型设计、人机工程、并行工程、价值工程、反求工程设计、模 块化设计、相似性设计、虚拟设计、疲劳设计、三次设计等。在运用它们进行工程设计时， 一般都以计算机作为分析、计算、综合、决策的工具。这些学科汇集成了一个设计学的新体 系，即现代设计方法。 设计的思想和方法一方面不断地影响着人类的生活与生产，推动社会的进步；另一方面又 受到社会发展的反作用，不断变化和更新。实际上所谓的“传统设计”和“现代设计”都只 是相对的概念。人们把当前认为先进的那部分系统称为现代的，而其余的自然成为传统的， 若干年后，目前先进的被新发展的东西所取代，而成为传统。从人类生产的进步来看，整个 设计进程大致经历了四个阶段。 1直觉设计阶段。既从自然现象中直接获得启示，或是全凭人的直观感受来设计，制作。2经 验设计阶段。3半理论半经验设计阶段。4现代设计阶段。电子计算机技术的发展和应用，使 设计工作产生了革命性的突变。 现代设计是面向市场面向用户的设计。首先，好的产品始于先进的设计理念和对市场需求 的深刻了解以及贯穿整个设计过程中的以人为本的信念。其次，设计要求对产品进行全寿命 周期设计。即在设计过程中要考虑设计，制造，安装，运行，维修和报废等每一个阶段中用 户的需求。也就是，设计不仅要实现产品的基本功能要求，还应该体现人性化和环境友好的 先进设计思想。此外，设计对象从最初的单一功能产品变为越来越复杂的系统。功能更加先 进和全面，因此需要在设计时运用集成，综合，系统的方法与技术来解决设计问题。 与传统设计相比，有如下一些特点。 1传统设计中灵感和经验的成分占有很大的比例。思维带有很大的被动性。但是，今天技
1.遗传算法 遗传算法（Genetic Algorithms, GA）是由美国密歇根大学的John H.Holland教授及其学生于20世纪60年代末到70年代初提出的。在1975年出版的《自然与人工系统的自适应性》一书中，Holland系统地阐述了遗传算法的基本原理和方法，提出了对遗传算法的理论发展极为重要的模板理论。 遗传算法基本思想： 遗传算法是根据问题的目标函数构造一个适值函数，对于有多个解构成的种群进行评估、遗传运算、选择，经多代繁殖，获得适应值最好的个体作为问题的最优解。具体描述如下。 1)产生初始种群 遗传算法是一种基于群体寻优的方法，算法运行时是以一个种群在搜索空间进行搜索。一般是采用随机方法产生一个初始种群。也可以采用其他方法构造一个初始种群。 2)根据问题的目标函数构造适值函数 在遗传算法中使用适值函数来表征种群中每个个体对其生存环境的适应能力，每个个体具有一定的适应值。适应值是种群中个体生存机会的唯一确定值。适值函数直接决定着群体的进化行为。适值函数基本上依据优化的目标函数来确定。为了能够直接将适值函数与群体中的个体优劣相联系，在遗传算法中适应值规定为非负，并且在任何情况下总是希望越大越好。 3)根据适应值的好坏不断选择和繁殖 在遗传算法中自然选择规律的体现就是以适应值的大小决定的概率分布来进行计算选择。个体的适应值越大，该个体被遗传到下一代的概率越大；反之，个体适应值越小，该个体被遗传到下一代的概率越小。被选择的个体两两进行繁殖，繁殖产生的个体组成新的种群。这样的选择和繁殖的过程不断重复。 4)若干代后得到适应值最好的个体即为最优解 在若干代后，得到适应值最好的个体所对应的解即被认为是问题的最优解。 遗传算法构成要素： a)种群和种群大小 种群是有染色体构成的。每个个体就是一个染色体，每个染色体对应着问题的一个解。种群中个体的数量称为种群大小或种群规模。种群规模通常采用一个不变的常数。一般来说种群规模越大越好，但是种群规模增大也将导致运算时间的增大。在一些特殊情况下，群体规模也可能采用与遗传代数相关的变量，以获取更好的优化效果。 b)编码方法（Encoding Scheme） 编码方法也称为基因的表达方法。在遗传算法中，种群中每个个体，即染色体是由基因构成的。所以染色体与要优化的问题的解如何进行对应，就需要通过基因来进行表示，即染色体进行正确的编码(一般用二进制编码)。正确地对染色体进行编码来表示问题的解是遗传算法的基础工作，也是最重要的工作。 c)遗传算子（Genetic Operator） 遗传算子包括交叉（Crossover）和（Mutation）。遗传算子模拟了每一代中创造后代的繁殖过程，是遗传算法的精髓。 交叉是最重要的遗传算子，它同时对两个染色体进行操作，组合二者的特性产生新的后代。交叉最简单的方式是在双亲的染色体上随机地选择一个断点，将断点的右段相互交换，从而形成两个新的后代。这种方式对于二进制编码最适合。遗传算法的性能很大程度上取决于采用的交叉运算的方式。 交叉率定义为各代中交叉产生后代数与种群中个体数的比。显然，较高的交叉率将达到更大的解空间，从而减小停止在非最优解上的机会；但交叉率过高，会因过多搜索不必要的
第二十三章 现代优化算法简介 §1 现代优化算法简介 现代优化算法是80年代初兴起的启发式算法。这些算法包括禁忌搜索（tabu search ），模拟退火（simulated annealing ），遗传算法（genetic algorithms ），人工神经网络（neural networks ）。它们主要用于解决大量的实际应用问题。目前，这些算法在理论和实际应用方面得到了较大的发展。无论这些算法是怎样产生的，它们有一个共同的目标－求NP-hard 组合优化问题的全局最优解。虽然有这些目标，但NP-hard 理论限制它们只能以启发式的算法去求解实际问题。 启发式算法包含的算法很多，例如解决复杂优化问题的蚁群算法（Ant Colony Algorithms ）。有些启发式算法是根据实际问题而产生的，如解空间分解、解空间的限制等；另一类算法是集成算法，这些算法是诸多启发式算法的合成。 现代优化算法解决组合优化问题，如TSP （Traveling Salesman Problem ）问题，QAP （Quadratic Assignment Problem ）问题，JSP （Job-shop Scheduling Problem ）问题等效果很好。 本章我们只介绍模拟退火算法，初步介绍一下蚁群算法，其它优化算法可以参看相关的参考资料。 §2 模拟退火算法 2.1 算法简介 模拟退火算法得益于材料的统计力学的研究成果。统计力学表明材料中粒子的不同结构对应于粒子的不同能量水平。在高温条件下，粒子的能量较高，可以自由运动和重新排列。在低温条件下，粒子能量较低。如果从高温开始，非常缓慢地降温（这个过程被称为退火），粒子就可以在每个温度下达到热平衡。当系统完全被冷却时，最终形成处于低能状态的晶体。 如果用粒子的能量定义材料的状态，Metropolis 算法用一个简单的数学模型描述了退火过程。假设材料在状态i 之下的能量为)(i E ，那么材料在温度T 时从状态i 进入状态j 就遵循如下规律： （1）如果)()(i E j E ≤，接受该状态被转换。 （2）如果)()(i E j E >，则状态转换以如下概率被接受： KT j E i E e )()(- 其中K 是物理学中的波尔兹曼常数，T 是材料温度。 在某一个特定温度下，进行了充分的转换之后，材料将达到热平衡。这时材料处于状态i 的概率满足波尔兹曼分布： ∑∈--==S j KT j E KT i E T e e i x P )()()( 其中x 表示材料当前状态的随机变量，S 表示状态空间集合。 显然
现代优化计算方法的发展历程 【摘要】：对具有代表性的现代优化计算方法：遗传算法、人工神经网络、模拟退火算法的产生、发展进行了详细的叙述，并对它们的应用领域和研究方向做了细致的介绍，最后对三种算法分别作了总结和展望。 【关键词】：遗传算法；人工神经网络；模拟退火算法；组合优化 随着20世纪80年代初期遗传算法、人工神经网络、模拟退火、禁忌搜索算法的兴起，科学工作者对这些算法的模型、理论和应用技术等一系列问题进行着深入的研究，并将这些算法统称为现代人优化算法。 1. 遗传算法 1.1 遗传算法的产生和发展 遗传算法是近年来迅速发展起来的一种全新的随机搜索与优化算法，其基本思想是基于Darwin 的进化论和Mendel 的遗传学说。该算法由密歇安大学教授Holland 及其学生于1975 年创建。其主要特点是采取群体搜索策略和在群体中个体之间进行信息交换，利用简单的编码技术和繁殖机制来表现复杂的现象，不受搜索空间的限制性假设的约束，不要求诸如连续性，导数存在和单峰等假设。此后，遗传算法的研究引起了国内外学者的关注。 1.2 遗传算法的应用领域和研究方向 遗传算法是多学科结合与渗透的产物，已经发展成一种自组织、自适应的综合技术，广泛应用在计算机科学、工程技术和社会科学等领域。其研究工作主要集中在基础理论、分布并行遗传算法、分类系统、遗传神经网络、进化算法。 1.3 遗传算法的展望 遗传算法的长期发展是一个不断跳跃的过程。做为一个优秀的老资格算法它的实用价值绝对值得肯定，但它也存在一些无法摆脱的算法局限性。例如遗传算法不能保证在多项式时间内找到NP完全问题的最优解，而它经常能找到组合问题很好的次优解。但可喜的是，新世纪的计算机数字时代遗传算法已经引起了计算机界人士的广泛注意。当今计算机科学的各个领域几乎都显示出向并行计算过渡这一趋势。在这场变革中，一个鼓舞人心的结果就是信的应用领域不断发展，诸如格子气流体,神经网络和遗传算法，这些领域的研究从一开始就是基于并行处理。遗传算法的实际应用效能将会扮演越来越重要的角色。在遗传算法的研究过程中还将会出现新的困难，但是人们不得不正视大量的研究成果为此研究领域所展示的巨大潜力。 2. 人工神经网络
智能优化方法作业PSO算法实验报告 课程名称：智能优化方法作者姓名： 专业：控制工程
目录 第一章问题描述 (1) 第二章算法设计 (1) 2.1解及目标函数的表达 (1) 2.1.1种群的编码 (1) 2.1.2初始种群的产生 (1) 2.1.3评价函数的构造 (1) 2.2 POS速度迭代公式 (2) 2.3粒子的更新 (2) 2.4惯性权重的调整 (3) 2.5停止准则 (3) 第三章算法实现及分析 (3) 3.1编译环境及界面介绍 (3) 3.2 matlab中GUI界面打开的3种方式 (4) 第四章算法分析 (5) 4.1 默认参数下的运行结果 (5) 4.2种群大小对算法的影响 (6) 4.3 最大迭代次数对算法的影响 (8) 4.4 实验得出的“最优”参数 (9)
第一章 问题描述 无约束5维的Rosenbrock 函数可以描述如下： ∑-=+-+-=112221))1()(100()(min n i i i i x x x x f （1） 其中，5,...2,1],30,30[=-∈i x i 。 要求按PSO 算法思想设计一个该问题的求解算法，并利用计算机语言实现设计的算法。将实验报告和程序代码（带有详细注释）。 第二章 算法设计 2.1解及目标函数的表达 2.1.1种群的编码 显然对于一个粒子个体可以用一个含有5个元素的一维数组进行表示。对于一个种群这里使用pop_size×5的二维数组进行表示。其中pop_size 为种群大小。 2.1.2初始种群的产生 初始种群的各个粒子均采用均匀随机产生的方式，即粒子每一位都是-30到30上的随机数。同样粒子的速度也是-40到40上的随机数。这里设置速度在-40到40内是因为限定速度的最大值为40。 2.1.3评价函数的构造 这里直接采用解的函数值作为评价函数，评价函数值越小认为该解越好。评价函数如下： ∑-=+-+-=112221))1()(100()(min n i i i i x x x x f （2） 其中，5,...2,1],30,30[=-∈i x i 。
1.直接搜索法。它只利用目标函数值构成的搜索方法，如POWELL，单纯形法； 2.梯度法。它需要有目标函数及其导数的解析式。 对于非线性的显函数，且变量数较少或中等的问题，用复合形法或罚函数法（其中尤其是内点罚函数法）的求解效果一般都比较理想，前者求得全域最优解的可能性较大。建议当找不到一个可行的初始点时，才用外点罚函数法。在用罚函数法解优化问题时，必须选用一个合适的无约束优化方法。如果目标函数的一阶和二阶偏导数易于计算（用解析法），且设计变量不是很多（如n ≤20）时，建议用拟牛顿法；若n>20，且每一步的Hessian 矩阵求解变得很费时时，则选用变尺度法较好。若目标函数的导数计算困难（用解析法）或者不存在连续的一阶偏导数，则用Powell共轭方向法效果是最好的。对于一般工程设计问题，由于维数都不很高（n<50），且函数的求导计算都存在不同程度的困难，因此用内点罚函数法调用Powell无约束优化方法求序列极小化。 优化设计：它是以数学规划理论为基础，以电子计算机为辅助工具的一种设计方法。它首先将设计问题按规定的格式建立数学模型，并选择合适的优化方法，选择或编制计算机程序，然后通过电子计算机自动获得最优设计方案。 两类优化方法： 1.直接法：直接计算目标函数值，比较目标函数值，并以之作为迭代、收敛根据的方法。 2.求导法：以多变量函数极值理论为基础，利用目标函数的性态，并以之作为寻优、迭代、收敛根据的方法。 综合设计法： 以程序设计、优化技术、仿真技术及自动绘图技术的综合为基础，以计算机工作站为工具，将工业设计方法提高到更新的阶段，使产品设计，换代、创新更趋于自动化，并展示了有可能向智能化发展的前景。 优化问题的分类： 按照目标函数的性质和约束条件可分为无约束问题和有约束问题。 无约束问题按照目标函数包含的单变量或多变量来分类。（直接搜索法：它只利用目标函数值构成的搜索方法，如POWELL法，单纯形法等。梯度法：它需要有目标函数及其导数的解析式。） 有约束问题有三类： 1.线性目标函数和线性约束（线性规划，整数规划） 2.非线性的目标函数和线性约束（二次规划，凸规划，线性分式规划） 3.非线性目标函数和非线性约束条件（变换法，线性逼近法，直接搜索法） 建立数学模型有哪三个基本步骤？ 1）识别要确定的未知变量，并用代数符号表示它们。2）识别目标或判别标准，并将其表示为要最大化或最小化的函数。 3）识别问题的约束条件或限制，并将它们表示成未知变量的线性或非线性的等式或不等式组。 。优化设计的数学模型一般由设计变量、目标函数和约束条件三个基本要素组成。其含义为在一定的约束条件下，追求目标函数的极小值（或极大值）,而求得一组设计变量值。 。设计变量与设计空间：设计变量的个数决定了设计空间的维数，设计空间的维数又表征设计的自由度，设计变量越多，则设计的自由度越大，可供选择的方案越多，设计越灵活，但难度亦越大，求解越复杂。通常在保证必要的设计精度的前提下，设计变量应尽可能取少些。 。约束条件可分为边界约束和性能约束。在二维设计空间中，不等式约束条件的可行域，是各约束线所围的平面，比较直观。三维和三维以上的设计问题，约束条件是曲面或超曲面，约束曲面围成的可行域，是多曲面或超越曲面围成的空间。 。等值线有哪些特点：不同值的等值线不相交；除极 值点外，等值线在设计空间内不会中断；等值线反映 了目标函数的变化规律，愈内层的等值线，其函数值 愈小，其中心点为极值点；等值线间隔越密，表示该 处函数变化率越大；极值点附近的等值线近似椭圆 族，极值点为中心点。 。线性规划与非线性规划有何区别？ 当目标函数F(x)和约束条件都是设计变量的线性函 数时，列出这种数学模型并求解的过程，称为线性规 划，只有一个公用算法，称为“单纯形法”。在所有 的优化模型中，线性规划应用的最广。如果目标函数 F(x)和约束条件中有一个或多个是设计变量的非线 性函数时，列出这种数学表达式并求解的过程，称为 非线性规划。解非线性规划问题有许多算法。 。什么是约束条件？约束条件和可行域有何关系？等 式约束和不等式约束有何区别与联系？ 设计变量的取值范围有限制或必须满足一定的条件， 这种对设计变量取值的限制称为约束条件。 不等式约束条件将设计空间划分为可行域和非可行 域，设计方案只能在可行域内选取。 等式约束条件只允许设计方案在可行域的等式约束 线（或面）上选取。 不等式约束将设计变量限制在一个区间或区域，约束 不严格；而等式约束设计变量限制在一个点、线或面 上，约束严格。 等式约束起到降低自由度的作用，有一个等式约束可 以降低一个设计自由度，一个等式约束可以用两个不 等式约束表示。 。约束极值点存在的条件：库恩-塔克条件：一个约 束极值点存在的必要条件为目标函数的梯度可表示 成诸约束面梯度纯属组合的负值。其几何意义为：起 作用约束的梯度矢量，在设计空间构成一个锥体，目 标函数的负梯度应包含在此锥体内。这个条件是约束 优化问题极值的必要条件，而不是充分条件。只有当 目标函数为凸函数，约束函数也是凸函数时，即凸规 划问题时，其局部最优点就是全局最优点，刚库恩- 塔克条件是该极值的必要充分条件。 。数值方法：根据目标函数值的变化规律，以适当的 步长沿着能使目标函数值下降的方向，逐步向目标函 数值的最优点进行探索，逐步逼近目标函数的最优 点，直至达到最优点。 。常用迭代终止准则有哪三种？ 1）点距准则：当设计变量在相邻两点之间的移动距 离以充分小时，可以相邻两点的矢量差的摸作为终止 迭代的判据。 2) 值差准则：当相邻两点目标函数之差已达到充分 小时，可用两次迭代的目标函数之差作为终止判据 3）梯度准则：当迭代点逼近极值点时，目标函数在 该点的梯度已达到充分小时，可用梯度的模作为终止 判据。 0.618法的基本思想：0.618法又称黄金分割法，要 求定义区间[a,b]上的函数为单峰值函数通过不断割 舍左端或右端的一部分，逐步把区间缩小之至极小点 所在区间到给定误差范围内，从而得到近似的最优 解，并且每次缩短的新区建长度与元区间长度的比值 始终是一个常数。 。二次插值法的基本思想是:在选定的单峰区间内选 一点，连同两端点，利用这三点的函数值构成一个二 次多项式，作为原函数的近似，求近似二次多项式的 极小点作为原函数的近似最优点。 。Powell法在每一轮形成新的搜索方向时会存在何 种问题导致不收敛？如何修正？ Powell法在每一轮形成新的搜索方向替换原来矢量 组中的第一个方向形成新的搜索方向组，可能存在新的方向 组线性相关的情况，从而导致算法不收敛的问题。修正 方法：选代过程中，形成一个新的方向后，先判别一下新方 向是否有效，如果有效则替换原来的搜索方向组中的第一个 搜索方向，否则，不替换，仍然按原来的方向组搜索。 。梯度法的基本原理和特点是什么 1）梯度法的基本原理：梯度法又称最速下降法，基本原理是 在迭代点附近采用使目标函数值下降最快的负梯度方向作为 搜索方向，求目标函数的极小值。 2）梯度法的特点：迭代计算简单，只需求一阶偏导数，所占 用存储单元少，对初始点要求不高，在接近极小点位置时收 敛速度很慢。 1.共轭梯度法的特点是什么？ 在梯度法靠近极值点收敛速度减慢的情况下，共轭梯度法可 以通过构造共轭方向，使其收敛速度加快，具有一次收敛速 度，使得计算过程简便，效果又好：在每一步迭代过程中都 要构造共轭方向，比较繁琐。 2.为什么选项用共轭方向作为搜索方向可以取得良好的 效果？ 选用共轭方向作为搜索方向可以取得良好的效果，主要是由 共轭方向的性质所决定。 共轭方向的性质为: 对于n维正定二次型函数，从任意初始 点出发，依次沿着与矩阵A为共轭的n个线性无关的方向进 行一维搜索，则能在第n或第n步以前达到极小点。 3.变尺度法：为了得到既快速收敛的性质，又能避免计 算二阶导数矩阵及其逆矩阵，减少计算工作量。 变尺度矩阵必须是对称正定矩阵，才能保证变尺度算法的搜 索方向是函数值下降的方向，而且从一次迭代到另一次迭代 是变化的，故称变尺度矩阵。 4.有约束优化方法根据对约束条件的处理方法不同，可 分为直接法和间接法两大类。 直接法的基本思想是设法使每一次的迭代点都能在可行域 内，并逐步降低目标函数值，直至最后得到一个在可靠域内 的约束最优解。即在迭代过程中，搜索方向和迭代步长都要 经过可靠性和适用性条件的检查。属于直接法的有：复合形 法、简约梯度法等。间接法的基本思想是把有约束问题通过 一定形式的变换，转化成无约束优化问题，然后用无约束方 法求解，属于此类常见的有罚函数法等。 5.简述复合形法的优化过程的基本原理。 复合形法的优化过程为：在可行域内选择是个设计点，作为 初始复合形的顶点，构造一个多面体；然后对多面体各顶点 的函数值逐个进行比较，目标函数最大的为坏点，按照一定 规则去掉坏点而代以新点，构成一个新的多面体；依次步骤 进行多次，使复合形的位置逐步调向邻近最优点，最后以顶 点中目标函数值最小的点，作为近似最优点而得到解。 特点：由于在迭代计算中不必计算目标函数的导数，也不用 一维搜索，所以程序结构比较简单，适用性较广。对设计变 量增加，维数高或约束条件多的优化问题，为了得到较好的 新顶点，往往要向中心点多次收缩，因而计算效率显著降低。 6.简约梯度法：解决线性约束非线性规划问题。 7.简述罚函数法的基本原理，罚函数法分为哪几种？ 基本思想是把一个有约束的问题转化为一系列无约束问 题求解，逐渐逼近于目标函数的最优值。 在原目标函数中添加一些与约束函数有关的项，形成一个 新的目标函数以取代原目标函数，然后用无约束融洽优化 方法求新目标函数的最优解。 有内点法、外点法、混合法。 内点罚函数法、外点罚函数法及混合罚函数法的基本思想： 内点罚函数法：是把新目标函数定义于可行域内，因此其初 始点和后面产生的迭代点序列也必然在可行域内，这种方法 是求解不等式约束最优化问题的一种十分有效的方法，但不 能处理等式约束。 缺陷：一是不能处理等式约束问题，因为在边界上新目标函 数的函数值无穷大，迭代点无法达到；二是初始点必须在可