启发式优化算法综述
一、启发式算法简介
1、定义
由于传统的优化算法如最速下降法，线性规划，动态规划，分支定界法，单纯形法，共轭梯度法，拟牛顿法等在求解复杂的大规模优化问题中无法快速有效地寻找到一个合理可靠的解，使得学者们期望探索一种算法:它不依赖问题的数学性能，如连续可微，非凸等特性; 对初始值要求不严格、不敏感，并能够高效处理髙维数多模态的复杂优化问题，在合理时间内寻找到全局最优值或靠近全局最优的值。于是基于实际应用的需求，智能优化算法应运而生。智能优化算法借助自然现象的一些特点，抽象出数学规则来求解优化问题，受大自然的启发，人们从大自然的运行规律中找到了许多解决实际问题的方法。对于那些受大自然的运行规律或者面向具体问题的经验、规则启发出来的方法，人们常常称之为启发式算法（Heuristic Algorithm）。
为什么要引出启发式算法，因为NP问题，一般的经典算法是无法求解，或求解时间过长，我们无法接受。因此，采用一种相对好的求解算法，去尽可能逼近最优解，得到一个相对优解，在很多实际情况中也是可以接受的。启发式算法是一种技术，这种技术使得在可接受的计算成本内去搜寻最好的解，但不一定能保证所得的可行解和最优解，甚至在多数情况下，无法阐述所得解同最优解的近似程度。
启发式算法是和问题求解及搜索相关的，也就是说,启发式算法是为了提高搜索效率才提出的。人在解决问题时所采取的一种根据经验规则进行发现的方法。其特点是在解决问题时,利用过去的经验,选择已经行之有效的方法，而不是系统地、以确定的步骤去寻求答案，
以随机或近似随机方法搜索非线性复杂空间中全局最优解的寻取。启发式解决问题的方法是与算法相对立的。算法是把各种可能性都一一进行尝试，最终能找到问题的答案，但它是在很大的问题空间内，花费大量的时间和精力才能求得答案。启发式方法则是在有限的搜索空间内，大大减少尝试的数量，能迅速地达到问题的解决。
2、发展历史
启发式算法的计算量都比较大，所以启发式算法伴随着计算机技术的发展，才能取得了巨大的成就。纵观启发式算法的历史发展史：
40年代：由于实际需要，提出了启发式算法（快速有效）。
50年代：逐步繁荣，其中贪婪算法和局部搜索等到人们的关注。
60年代: 反思，发现以前提出的启发式算法速度很快，但是解得质量不能保证，而且对大规模的问题仍然无能为力（收敛速度慢）。
70年代：计算复杂性理论的提出，NP问题。许多实际问题不可能在合理的时间范围内找到全局最优解。发现贪婪算法和局部搜索算法速度快，但解不好的原因主要是他们只是在局部的区域内找解，等到的解没有全局最优性。由此必须引入新的搜索机制和策略。
Holland的遗传算法出现了（Genetic Algorithm）再次引发了人们研究启发式算法的兴趣。
80年代以后：模拟退火算法（Simulated Annealing Algorithm），人工神经网络（Artificial Neural Network），禁忌搜索（Tabu Search）相继出现。
最近比较火热的：演化算法（Evolutionary Algorithm）, 蚁群算法（Ant Algorithms），拟人拟物算法，量子算法等。
二、启发式算法类型
1、类型简介
大部分的算法都是仿生演变而来，如下：仿动物类的算法：粒子群优化，蚁群算法，鱼群算法，蜂群算法等；仿植物类的算法：向光性算法，杂草优化算法等；仿人类的算法有：遗传基因算法，和声搜索算法，神经网络；以及其他的理论成熟并被广泛使用的算法如：模拟退火算法、禁忌搜索等等
①、粒子群算法
粒子群优化算法的基本思想是通过群体中个体之间的协作和信息共享来寻找最优解．粒子群算法源于复杂适应系统（Complex Adaptive System,CAS）。CAS理论于1994年正式提出，CAS中的成员称为主体。比如研究鸟群系统，每个鸟在这个系统中就称为主体。主体有适应性，它能够与环境及其他的主体进行交流，并且根据交流的过程“学习”或“积累经验”改变自身结构与行为。整个系统的演变或进化包括：新层次的产生（小鸟的出生）；分化和多样性的出现（鸟群中的鸟分成许多小的群）；新的主题的出现（鸟寻找食物过程中，不断发现新的食物）。
设想这样一个场景：一群鸟在随机的搜索食物。在这个区域里只有一块食物，所有的鸟都不知道食物在那。但是它们知道自己当前的位置距离食物还有多远。那么找到食物的最优策略是什么？最简单有效的就是搜寻目前离食物最近的鸟的周围区域。
②、蚁群算法
蚁群算法(ant colony optimization, ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。
蚂蚁在运动过程中，会留下一种称为信息素的东西，并且会随着移动的距离，播散的信息素越来越少，所以往往在家或者食物的周围，信息素的浓度是最强的，而蚂蚁自身会根据
信息素去选择方向，当然信息素越浓，被选择的概率也就越大，并且信息素本身具有一定的挥发作用。蚂蚁的运动过程可以简单归纳如下：
1当周围没有信息素指引时，蚂蚁的运动具有一定的惯性，并有一定的概率选择其他方向；
2当周围有信息素的指引时，按照信息素的浓度强度概率性的选择运动方向；
3找食物时，蚂蚁留下家相关的A信息素，找家时，蚂蚁留下食物相关的B信息素，并随着移动距离的增加，洒播的信息素越来越少；
4随着时间推移，信息素会自行挥发；
由上面4点原则构成蚁群算法的核心规则。
③、遗传基因算法
遗传算法（Genetic Algorithm）又叫基因进化算法，或进化算法。生物只有经过许多世代的不断进化（evolution,演化），才能更好地完成生存与繁衍的任务。遗传算法也遵循同样的方式，需要随着时间的推移不断成长、演化，最后才能收敛，得到针对某类特定问题的一个或多个解。
遗传算法是一种基于自然选择和群体遗传机理的捜索算法，它模拟了自然选择和自然遗传过程中的繁殖、杂交和突变现象。标准的遗传算法包括四个组成部分：
1) 编码（产生初始种群）。在利用遗传算法求解问题时，首先要确定问题的目标函数和解变量，然后对解变量进行编码，遗传算法的所有操作都是基于这种实际变量的编码。编码是遗传算法的一个重要环节。它不仅决定了染色体的组织方式，还影响到交叉、变异算子的执行方式。不同的编码策略对遗传算法的运行效率有较大的影响。问题的编码一般应满足完备性、健全性和非冗长性H个原则，完备性是指问题空间中的所有点都能成为GA编码空间中点的表现型；健全性是指GA编码空间中染色体必须对应问题空间中的某一潜在解；非
冗长性是指染色体和潜在解必须一一对应PS1。对于一个特定的问题，如何设计出一种高效的编码方式是遗传算法所面临的难题之一，遗憾的是，研究者们至今也没能找到一种通用的编码策略。目前，工程优化中多采用两种常用的编码方式，即二进制编码Psi和实数编码PD1。二进制编码的染色体是由一个二值集合｛0,1｝所组成的二进制符号串。作为GA算法的标准编码方式，该编码方式尤其适用于能用二值向量描述的优化问题，如化学反应P11、多用途过程规划P3和最优水流参数评估Psi等；实数编码是指个体的每个基因值用某一范围的一个浮点数表示，个体的编码长度等于其决策变量（设计变量）的个数。这种编码方式适用于精度要求较高的遗传算法中，便于较大空间的遗传搜索：改善了遗传算法的计算复杂性，提高了运算效率；便于遗传算法和经典优化算法的混合使用：目前基于实数编码的遗传算法也被广泛用于优化问题中，如多目标优化IW，凸轮轮廓设汁等。
2) 选择操作。选择是指从群体中选择优良的个体并淘汰劣质个体的操作。它建立在适应度评估的基础上，遼应度楚大的个体，被选择的可能性就越大，它的吁孙＂在下一代的个数就越多。选择出来的个体被放入配对库中。目前常用的选择方法有轮盘赌方法、最佳个体保留法、期望值法和排序选择法等。
3）交叉操作。交叉是指两个父代个体的部分结构加W替换重组而生成新个体的操作，目的是为了能够在下一代产生新的个体。通过交叉操作，遗传算法的搜索能力得W提高。交叉是遗传算法获取新优良个体最重要的手段，按照一定的交叉概率在配对库中随机地选取两个个体进行交叉，交叉的位置也是随机确定的。
4）变异。变异就是很小的变异概率随机地改变群体中个体的某些基因的值。变异操作中位置选取的基本过程如下：产生一个在0~1之间的随机数，如果小于Pm则进行变异操作。
④、模拟退火
模拟退火算法来源于固体退火原理，是一种基于概率的算法，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。
模拟退火算法新解的产生和接受可分为如下四个步骤：
第一步是由一个产生函数从当前解产生一个位于解空间的新解；为便于后续的计算和接受，减少算法耗时，通常选择由当前新解经过简单地变换即可产生新解的方法，如对构成新解的全部或部分元素进行置换、互换等，注意到产生新解的变换方法决定了当前新解的邻域结构，因而对冷却进度表的选取有一定的影响。
第二步是计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生，所以目标函数差的计算最好按增量计算。事实表明，对大多数应用而言，这是计算目标函数差的最快方法。
第三步是判断新解是否被接受,判断的依据是一个接受准则，最常用的接受准则是Metropolis准则: 若ΔT<0则接受S′作为新的当前解S，否则以概率exp(-ΔT/T)接受S′作为新的当前解S。
第四步是当新解被确定接受时，用新解代替当前解，这只需将当前解中对应于产生新解时的变换部分予以实现，同时修正目标函数值即可。此时，当前解实现了一次迭代。
可在此基础上开始下一轮试验。而当新解被判定为舍弃时，则在原当前解的基础上继续下一轮试验。
模拟退火算法与初始值无关，算法求得的解与初始解状态S(是算法迭代的起点)无关；模拟退火算法具有渐近收敛性，已在理论上被证明是一种以概率l 收敛于全局最优解的全局优化算法；模拟退火算法具有并行性。
2、设计良好的启发式算法
上述的启发式算法都有一个共同的特点：从随机的可行初始解出发，才用迭代改进的策略，去逼近问题的最优解。他们的基本要素：
1）随机初始可行解；
2）给定一个评价函数（常常与目标函数值有关）；
3）邻域，产生新的可行解；
4）选择和接受解得准则；
5）终止准则。
但在启发式算法中，局部最优值的陷入是无法避免。启发式，本质上是一种贪心策略，这也在客观上决定了不符合贪心规则的更好（或者最优）解会错过。
那么如何避免陷入局部最优呢？随机。
具体实现手段上，可以根据所采用的启发式框架来灵活地加入随机性。比如遗传里面，可以在交叉变异时，可以在控制人口策略中，也可以在选择父本母本样本时；禁忌里面，可以在禁忌表的长度上体现，也可以在解禁策略中使用，等等。这些都要结合具体问题特定的算例集，需要反复尝试摸索才行。参数的敏感性是一个问题，建议不要超过3个参数，参数越不敏感越好。不同算例集用不同种子运行多次（100次左右才有统计意义），统计平均性能即可。需注意全局的随机重启通常来说不是一个好办法，因为等于主动放弃之前搜索结果，万不得已不要用，或者就是不用。
三个原则应该把握：越随机越好；越不随机越好；二者平衡最好。
越随机越好没有随机性，一定会陷入局部最优。为了获得更大的找到最优解的期望，算法中一定要有足够的随机性。具体体现为鲁棒性较好，搜索时多样性较好。算法的每一步选择都可以考虑加入随机性，但要控制好概率。比如，某个贪心策略下，是以概率1做某一动作，可以考虑将其改为以概率0.999做之前的操作，以剩余概率做其他操作。具体参数
设置需调试。越不随机越好随机性往往是对问题内在规律的一种妥协。即没有找到其内在规律，又不知道如何是好，为了获得更好的多样性，逼不得已加入随机。因此，对给定问题的深入研究才是根本：分辨出哪些时候，某个动作就是客观上能严格保证最优的——这点至关重要，直接决定了算法性能。最好的算法一定是和问题结构紧密相连的，范范地套用某个启发式的框架不会有出色的性能。当然，如果不是追求性能至上，而是考虑到开发效率实现成本这些额外因素，则另当别论。二者平衡最好通常情况下，做好第一点，可以略微改善算法性能；做好第二点，有希望给算法带来质的提高。而二者调和后的平衡则会带来质的飞跃。贪心是“自强不息”的精进，不放过任何改进算法的机会；多样性的随机是“厚德载物”的一分包容，给那些目前看似不那么好的解一些机会。调和好二者，不偏颇任何一方才能使算法有出色的性能。要把握这种平衡，非一朝一夕之功，只能在反复试验反思中去细细品味。
三、本领域应用：基于深度神经网络的自然语言情感分析
1.深度神经网络
神经网络领域最早是由心理学家和神经学家开创的，旨在开发和测试神经的计算机模拟。粗略地说，神经网络是一组连接的输入/输出单元，其中每个连接都与一个权重相关联。在学习阶段，通过调整这些权重，能够预测输入元组的正确类标号。由于单元之间的连接，神经网络学习又称连接者学习（Connectionist Learning）。
神经网络需要很长的训练时间，对于有足够长训练时间的应用更为合适。需要大量的参数，通常主要靠经验确定，如网络拓扑结构。神经网络常常因为可解释性差而受到批评。例如，人们很难解释网络中学习的权重和“隐含单元”的符号意义。
然而，神经网络的优点包括其对噪声数据的高承受能力，以及对未经训练的数据模式分类能力。在缺乏属性和类之间的联系的知识时可以使用它们。不像大部分决策树算法，它们
非常适合连续值的输入和输出。神经网络算法是固有并行的，可以使用并行技术来加快计算过程。
有许多不同类型的神经网络和神经网络算法，最流行的神经网络算法是后向传播，它在20世纪80年代就获得了声望。
图1 神经网络结构图
上图描述的是一个目前研究最为成熟Shallow 结构的神经网络（只含有单层隐藏层神经元的结构）。第一层为输入层(input layer )，第二层称为隐藏层( hidden layer )，最后一层为输出层( output layer )。神经元之间都是由低层出发，终止于高层神经元的一条有向边进行连接，每条边都有自己的权重。每个神经元都是一个计算单元，如在Feed-forward neural network 中，除输入层神经元外，每个神经元为一个计算单元，可以通过一个计算函数f(x) 来表示，函数的具体形式可以自己定义，现在用的较多的是感知器计算神经元，如果你对感知器有所了解的话，理解起来会容易很多。可以计算此时神经元所具有的能量值，当该值超过一定阀值的时候神经元的状态就会发生改变，神经元只有两种状态，激活或未激活。在实际的人工神经网络中，一般是用一种概率的方式去表示神经元是否处于激活状态，可以用h(f) 来表示，f 代表神经元的能量值，h(f) 代表该能量值使得神经元的状态发生改变的概率有多大，能量值越大，处于激活状态的概率就越高。到这部分你已经接触到了关于神经网络的几个基本术语，下面用更加规范的符号来表示，神经元的激活值(activations) f(x) ，表示计算神经元的能量值, 神经元的激活状态h(f) ，h 表示激活函数。
激活函数有好几种形式，这里列举两种如下：
深度神经网络有三个主要环节：第一，用无监督方式训练系统，即用大量未标注样本逐层提炼，无导向自动形成特征。这一过程类似于人通过眼、耳等感官系统接收图像、声音信息后，自动在脑中形成不同类别信息印象。第二，调准。这一过程用一些己标注样本对特征分类，并根据分类结果进一步调整系统参数，优化系统在区分不同类别信息上的性能。第三，测试，用系统未见识过的样本数据检验系统学习效果，例如样本正确分类率、质量评估与主观评估关联度等。
2.自然语言处理之情感分析
在自然语言处理领域中，其中一个重要的子研究模块为情感分析。情感分析，也称为观点挖掘，指的是分析说话者在传达信息时所隐含的情况状态、态度、意见进行判断或者评估。目前，情感分析的主要研究方法还是一些基于机器学习的传统算法，例如，SVM、信息熵、CRF等。这些方法归纳起来有3类：有监督学习、无监督学习和半监督学习。而当前大多数基于有监督学习的研究取得了不错的成绩。但有监督学习依赖于大量人工标注的数据，而且由于人的主观理解不同，样本标注的标注很难确立，也很难保证标注样本的质量。相反的，无监督学习不需要人工标注数据训练模型，降低标注的代价。
3.深度神经网络下的微博文本情感分析
微博是手机短信、社交网站、博客等的集成者，它正在从各个方面渗透并影响人们的生活，包括大量的信息传播、飞快的信息发现，以及与世界的连接等。因而吸引了很多学者对微博的研究。而分析和监测微博短文本内容中所包含的情感信息，可以了解大众对热点事件的关注程度和情感变化，从而能够辅助评估和掌握热点事件的发展状况.然而，由于微博的短文本上下文信息数据是有限的，因而对于研究其情感具有挑战性。为了能更有效地解决这
一任务，需要更加严谨的方式从微博帖子的短句子消息中抽取出信息。
对于一篇博客，整篇的情感倾向性一般较明确，其中正向情感表示褒义类：赞扬、喜悦、歌颂等；负向情感表示贬义类：贬斥、悲哀、嫉妒等。而篇章的每个句子的情感倾向性可能不同，因此本文提出的研究方案是使用深度学习中的卷积神经网络（Convolutional Neural Networks，CNN）避免显式特征提取，而隐式地从训练数据中进行学习。
https://www.doczj.com/doc/759733608.html,N模型情感分类过程
现采用卷积神经网络CNN进行情感分析的分类器训练。
卷积神经网络是一个多层的神经网络，每层都是一个变换（映射），常用卷积convention 变换和pooling池化变换，每种变换都是对输入数据的一种处理，是输入特征的另一种特征表达；CNN网络结构主要由三部分组成：输人层、隐层和输出层。隐层主要分为2类：（1）卷积层，用于提取特征；（2）下采样层，用于特征优化选取。图2所示为卷积神经网络用于对训练样本进行卷积的工作流程。
图2卷积网络工作流程
给定一个微博短文本句子，ChrSeCNN为每个情感标签计算分值τ∈T，为了计算每一个短文本句子的分值，该网络将每个汉字在句子中的序列作为输入，并通过一个序列的层，抽取出特征。该网络抽取的特征是从汉字级到句子级进行抽取。文中提出的神经网络主要包含两个卷积层，这使得它能够处理任意长度的汉字和短文本句子。
①、初始表示层
网络的第一层将词组转换成文字实值特征向量，用以捕捉这个词组的形态、句法和语义信息。使用了一个固定大小的词组Cva，而且认为词组是一个固定大小的汉字构成的词汇Cwd。给定一个句子由n个汉字v{}1，v2，…，vn组成，每个汉字vn被转换成一个向量un=[]rva;rwva。它由两个子向量组成，分别是vn的词组级嵌入向量，rva∈Ｒdva和汉字级级嵌入向量rwva∈Ｒcl0u。词组级嵌入向量为了捕捉句法和语义信息，汉字级嵌入向量为了捕捉形态和形状信息。
②、网络训练
网络是通过在训练集合D上最小化否定相似来进行训练的。给定一个句子y，对于每个情感标签τ∈T，设置网络参数θ，计算出一个分值sθ()yτ。为了将这些分值转换为给定句子标签的条件概率分布并且设置网络参数θ，应用式(6)对所有标签τ∈T的分值进行计算。
③、实验
实验数据准备采用COAE2013发布的标准数据和COAE2014的标注数据，其中随机选取COAE2014的标注数据中的5000句作为训练数据，其余4000句作为测试数据。将训练语料，标注出正向情感倾向微博1210句，负向情感倾向微博1320句和中性情感倾向微博2470句。另外从官方COAE2013标准标注结果中处理得到了带情感倾向的微博语料约1500句，共计训练语料为微博6500句。文中以平均正确率、平均召回率和宏平均值作
为评价指标。为了验证文中方法的有效性，设计了三组实验，分别与层次结构的多策略方法、词典与机器学习的方法和文中提出的方法对微博短文本进行情感分析并对比。
实验结果标明加入卷积的神经网络结果模型中，情感极性分析判断更加准确，该模型对于微博短文本的情感分析明显有了较大程度的提升。
表1 实验结果
1.引言 优化设计英文名是optimization design，从多种方案中选择最佳方案的设计方法。它以数学中的最优化理论为基础，以计算机为手段，根据设计所追求的性能目标，建立目标函数，在满足给定的各种约束条件下，寻求最优的设计方案。 第二次世界大战期间，在军事上首先应用了优化技术。1967年，美国的R.L.福克斯等发表了第一篇机构最优化论文。1970年，C.S.贝特勒等用几何规划解决了液体动压轴承的优化设计问题后，优化设计在机械设计中得到应用和发展。随着数学理论和电子计算机技术的进一步发展，优化设计已逐步形成为一门新兴的独立的工程学科，并在生产实践中得到了广泛的应用。通常设计方案可以用一组参数来表示，这些参数有些已经给定，有些没有给定，需要在设计中优选，称为设计变量。如何找到一组最合适的设计变量，在允许的范围内，能使所设计的产品结构最合理、性能最好、质量最高、成本最低（即技术经济指标最佳），有市场竞争能力，同时设计的时间又不要太长，这就是优化设计所要解决的问题。一般来说，优化设计有以下几个步骤：①建立数学模型。②选择最优化算法。③程序设计。 ④制定目标要求。⑤计算机自动筛选最优设计方案等。 2.数学模型 优化设计的数学模型是对优化设计工程问题的数学描述，它包含设计变量、目标函数和设计约束三个基本要素。 2.1设计变量 2.1.1基本参数 a、定义：在设计过程中进行选择变化并最终确定的各项独立参数称为设计变量。 b、说明：在设计选择过程中，这些设计变量是变量，但它们一旦被确定后，设计对象也 就完全确定了。最优化设计是研究怎样合理地优选这些设计变量的一种现代设计 方法。在设计过程中，凡根据设计要求事先给定的，不是设计变量而是设计常量。 2.1.2设计方案的表现形式 a、设计空间：由n个设计变量为坐标所组成的时空间称作设计空间。 b、设计变量的表示法 （1）坐标表示法：一维问题→一个设计变量→数轴上的一个点 二维问题→两个设计变量→平面直角坐标系上的向量 三维问题→三个设计变量→空间直角坐标系的向量
2.098/15.093J Recitation 9 Xuan Vinh Doan 2004,10,11 1、启发式算法 整数规划一般是不容易得到最优解的。启发式算法可以在合理的计算时间内得到较优的可行解。局域搜索启发式算法应用广泛。局域搜索的一般步骤如下： 1、 从一个初始可行解出发 2、 找出相邻的可行解 3、 从相邻的可行解中找出更好的可行解 一般地，局域搜索启发式算法会得到一个局部最优解，而这个局部最优解有时就是全局最优解。算法的好与坏都决定于步骤3。 1.1模拟退火方法 相邻元素是随机选择的，选上的概率为 ， n p 1=∑∈N n n p 。移动的决策取决于 目标成本和退火概率： ()()()()()()?????=??x p x c y c e x p p y T x c y c y xy φ 其中温度梯度是根据一定的规则选择的，比如t C t T log )(=或，。 t Ca t T =)(1πa 1.2 其它方法 其它局域搜索式方法还有很多，具体问题有相应的方法。如：禁忌搜索、遗传算法（略有不同），蚁群优化法也是一种。 1、 禁忌搜索的组成部分：禁忌表（移动的列表或移动的特征的列表），集中化（好的解），多样化（不好的解）。 2、遗传算法的组成部分：染色体（解的表示法），选择、交叉、变异。 3、蚁群优化：信息素轨迹和启发式愿望（收敛速度）。
2、 动态规划 2.1 动态规划要素 1、（最重要的）状态变量 . k x 2、控制（或决策）变量 ，k u )(k k x U u ∈。 3、随机变量. k w 4、状态转移方程),,(1k k k k k u x f x ω=+ 5、附加费用。 )),,()((1 1k k k N i k N N W u x g x g E ω∑?=+2.2 Bellman 最优化原理 这里我们想要分个阶段来求出总的最小费用。最后阶段的费用为。在第k 阶段状态为下，决定控制变量,使从第阶段到最后的总费用最小。按下面的递推公式： N )(N N x g k x k u k ()(){}))),,((),,(min 1k k k k k k k k k w x U u k k w u x f J w u x g E x J k k k +∈+= 得到全局最小值为。 )(00x J 一般的，一个递归公式需两个元素： 1. 初始条件 f f =02. 递归公式 )(1k k k f g f =+ 2.3 例题 背包问题 根据不同的状态定义，递推公式有两种： 1. 为最优费用，w 为重量限制。则要找到： )(w F )(w F ()i i w w if F min 0π=ω ()(){}i i i i m i w w if p w w F w F min max ,1φ+?== 2. 当时，令为最优费用，为重量限制。则要找到： 1=i )(w Fi w )(w Fm ()()0,0000πw if w F w if w F ?∞=≥= ()()(){} 0,max 111φw if p w w F w F w F i i i i i ++++?=
基于仿真的优化方法综述 作者：东汪定伟 1 引言 人们对复杂事物和复杂系统建立数学模型并进行求解的能力是有限的，目标函数和约束条件往往不能以明确的函数关系表达，或因函数带有随机参、变量，导致基于数学模型的优化方法在应用于实际生产时，有其局限性甚至不适用。基于仿真的优化(Simulation Based Optimization，SBO)方是在这样的背景下发展起来的。 随着优化问题越来越复杂，对优化对象的评价只能通过仿真获得的统计指标来实现。这时，SBO是复杂优化问题的惟一选择。近年来，SBO已成为国际上最热的研究方向。 虽然SBO已经在很多领域得到了应用，但是当前对于SBO的理论研究并不完善，算法仍在不断探索和改进中，新的研究成果不断出现。 2 SBO的研究概况及分类 综观最优化的发展过程，大约经过了以下几个阶段： ①1940～1970年数学规划阶段一目标和约束是解析函数。②1970-2000年智能优化阶段一目标和约束放宽为含有判断逻辑的计算机程序。③2000年一未来基于仿真的优化(SBO)阶段一用大量仿真的统计数据来进行性能评价。 有些学者对SBO做了一些综述工作。Andradottir从连续事件和离散事件两个方面，对SBO 技术作了总结；Azadivar从单目标优化和多目标优化的角度对SBO方法作了论述；在国，湘龙等认为SBO是非枚举地从可能值中找到最佳输入变量值，使得输出结果为最优或满意解的过程。王凌等按照优化方法的不同，对SBO及其改进和应用作了综述。 随着对SBO方法研究的深入，SBO在复杂工程系统的设计优化、供应链和物流系统、制造系统及社会经济系统等领域得到了应用。总结当前的研究和应用情况，可以看出，基于仿真的优化是仿真方法和优化方法的结合，是借助仿真手段实现系统的优化的一种优化方法。
文化结构的产品设计方法综述产品设计师通过以用户为主体的设计方法，归纳出产品设计的几大重要因素组成的体系（产品—人—环境）。其细分为：（1）用户相关的使用、心理等用户（人）核心体系；（2）产品本身所具备的功能品质等产品体系；（3）产品外环境所承载的品牌、潮流等因素的环境体系。层次化结构则将该体系由表至里进行了区分与归纳。 层次化结构的构成 产品设计中，以汽车造型设计为主要特征代表的形态设计派的设计宗旨是从外观造型的线条、曲面、空间体上打造设计哲学理念，或是简洁、或是优雅、或是灵动、或是强悍，这些风格一旦被塑造定型并确定了它的文化性质，即成为了某个品牌某个风格的一种文化语言，有时，这些风格与传统文化的某些特征具有相同之处或者如出一辄，此时，设计便可相通。有时，设计师试图通过在产品表面贴纹样而提高产品的文化底蕴，笔者认为这仅仅是产品设计的一个最简单的途径，也仅仅是文化传承的最浅层次，容易被认为是“俗套的设计”，因此其层次关系有待深入挖掘。层次化知识结构，将其解析为：基于层次构架与互通性的传统文化精神与产品设计的知识结构。层次上的构架包括：表层、中层、内层、核层。表层内容：传统文化表现为纹样符号，而产品设计的表现为图形美化装饰；中层内容：传统文化表现为风格样式，而产品设计表现为形态样式；内层内容：传统文化表现为行为习惯，产品设计表现为方式、功能；核层内容：传统文化表现为精神与文化内涵，产品设计表现为品牌形象、理念、品质内涵。朴素简洁
的无印良品CD播放器无印良品CD播放器产品设计，通过一根拉绳操作音乐播放与停止，裸露的旋转CD盘面给人简单而美妙的观感。此设计无疑是对产品与文化深层次的挖掘与表现的设计构思。如此设计需要大胆与锐利的目光，传统文化中没有CD播放器，而CD播放器的操作一直都被认定为有几个按钮的操作方式。笔者认为，这样的设计并非仅仅对风格的追求，并非因为风格的框架所决定的，而是对文化与产品层次挖掘的成果。无印良品的产品包装以简单朴素为特色风格，使用环保的无漂白纸张作为商品袋，给人以新鲜、纯粹的感觉[3]。从表1可知，该产品的设计是通过对产品进行深入挖掘，发现了文化的对等性，而将两者融合，最终在产品的外观中体现出融合的结果，这是文化在现代化产品设计上应用的典型例子。装饰华丽的诺基亚“回纹”手机曾盛极一时的诺基亚回纹系列手机，可谓文化（符号）与产品结合的经典，无论是纹样还是材质，无论是触感还是交互，这款手机的设计都给人强烈的文化刺激。虽然曾有人质疑其过于花哨的外表，但没有人怀疑它的商业成功。多少年后的今天，从另外一个新的视角去看，这款产品的设计，在设计手法上表达了“文化”的哪个方面、层面？用户体验设计的经典——iPhone手机目前依然风靡全球的苹果iPhone手机以独特的操作体验、简练的形式给人眼前一亮的感觉，使用过的人无不被这种技术和设计带来的操作体验而折服。iPhone手机的成功更多的是对产品的理解，同时在工业设计上对用户为中心的PHE设计体系的客观分析。 基于文化应用层次化结构的产品设计方法
启发式优化算法
Heuristic Optimization Algorithm
理论与应用 Theory & Application
内容纲要
? ?
优化问题与优化算法 常用的启发式优化算法
模拟退火算法 ? 遗传算法 ? 粒子群优化算法 ? 混合策略优化算法
?
?
讨论
优化问题
?
组合式优化问题
? ? ? ?
七桥问题 最短路径问题 公路连接问题 旅行商问题 无约束函数优化问题 有约束函数优化问题 函数优化+组合优化
?
函数优化问题
? ?
?
混合优化问题
?
七桥问题
?
Euler在1736年访问Konigsberg时，他发现Konigsberg城中有 一条名叫Pregel的河流，河上建有七座桥如图所示: 市民有 趣的消遣活动是星期六作一次走过所有七座桥的散步，每 座桥只能经过一次而且起点与终点必须是同一地点。
Impossible Task!
最短路径问题 SPP－shortest path problem
?
?
?
货柜车司机奉命在最短的时间内将一车货 物从甲地运往乙地。 从甲地到乙地的公路网纵横交错，因此有 多种行车路线，这名司机应选择哪条线路 呢？ 假设货柜车的运行速度是恒定的，那么这 一问题相当于需要找到一条从甲地到乙地 的最短路。
公路连接问题
?
?
某一地区有若干个主要城市，现准备修建 高速公路把这些城市连接起来，使得从其 中任何一个城市都可以经高速公路直接或 间接到达另一个城市。 假定已经知道了任意两个城市之间修建高 速公路成本，那么应如何决定在哪些城市 间修建高速公路，使得总成本最小？
国内外沥青路面设计方法综述 周利,蔡迎春,杨泽涛 (郑州大学环境与水利学院,郑州450002) 摘要:当前世界各国众多的沥青路面设计方法,可概括地分为2类:一类是以经验或试验为依据的经验法;一类是以力学分析为基础,考虑环境、交通条件以及材料特性为依据的力学-经验法。简要介绍目前国内外典型设计方法(CBR法、A ASHT O法、S HEL L法、A I法及国内方法),并比较其优缺点,针对现行设计方法,特别是我国设计方法,提出改进意见。 关键词:沥青路面;设计方法;综述 文章编号:1009-6477(2007)04-0036-04中图分类号:U416.217文献标识码:B S ummary of Dome stic&Overseas Asphalt Paveme nt Design M ethod Zhou Li,Cai Y ingc hun,Y ang Zetao 沥青路面是在柔性基层、半刚性基层上,铺筑一定厚度的沥青混合料作为面层的路面结构。以沥青路面为主的柔性路面设计理论与方法研究已有近百年的历史,其发展历程经历了古典法、经验法和力学-经验法3个阶段。当前世界各国众多的沥青路面设计方法大体为后面2种,即以工程使用经验或试验为依据的经验法和以力学分析为基础,考虑环境、交通条件以及材料特性为依据的力学-经验法。为了更好地借鉴前人的研究成果,有助于指导今后设计方法的研究,本文简要介绍目前国内外几种典型的设计方法:(1)经验法的代表方法:CBR法和A AS HTO法;(2)力学-经验法的典型代表:AI法和SHEL L法;(3)我国2004规范(报批稿)采用的设计方法,并作简单评价。 1国外沥青路面设计方法 国外的沥青路面设计方法,可分为经验法和力学-经验法2大类[1]。 1.1经验法 经验法主要通过对试验路或使用道路的实验观测,建立路面结构、荷载和路面性能三者间的经验关系。最为著名的经验设计方法有美国加州承载比(CBR)法和美国各州公路和运输工作者协会(AA SHT O)柔性路面设计法。 1.1.1CBR法[2-3] CBR法是以CBR值作为路基土和路面材料(主要是粒料)的性质指标,通过对已损坏或使用良好的路面的调查和CBR测定,建立起路基土CBR-轮载-路面结构层厚度3者之间的经验关系。利用此关系曲线,可以按设计轮载和路基土CBR值确定所需的路面层总厚度。路面各结构层的厚度,按各层材料的CBR值进行当量厚度换算。不同轮载的作用按等弯沉的原则换算为设计轮载的当量作用。此方法设计过程简单、概念明确,适用于重载、低等级的路面设计,所提出的C BR指标已作为路面材料的一种参数指标得到了广泛应用。如日本的路面设计经验法(T A法)就是以CB R法为基础制定的。 1.1.2AA SHT O法[2,4-5] A AS HTO法是在1958)1962年间A AS HO试验路的基础上建立的。整理试验路的试验观测数据,得到了路面结构-轴载-使用性能三者间的经验关系式。路面结构中的路基土采用回弹模量表征其性质,路面结构层按各层材料性质的不同转换为用一个结构数(S N)表征。AAS HT O方法提出了现时服务能力指数(PSI)的概念,以反映路面的服务质量。PS I是一个由评分小组进行主观评定后得到的指标,它与路面实际状况(坡度变化、裂缝面积、车辙深度、修补面积)之间建立经验关系式,提出了轴载换算的概念和公式,考虑了结构的可靠度和排水条件的影响,这些思想对后来世界各国的设计思想产生了很大的影响。 1.2力学-经验法 力学-经验法首先分析路面结构在荷载和环境作用下的力学响应(应力、应变、位移),利用在力学 公路交通技术2007年8月第4期Technology of Highw ay and Transport Aug.2007No.4 收稿日期:2007-01-10
结构优化方法研究综述 结构优化方法研究综述 【摘要】建筑结构优化对建筑整体的稳定性、可靠性、耐久性有非常重要的作用。文章针对建筑结构优化设计的主要因素，以及结构优化的方法等方面做简要的分析，以提高建筑结构的整体的稳定性、耐久性等性能。 【关键词】结构设计；结构优化；结构类型 0引言 建筑结构优化，即在一些建筑结构的设计方案中选取最优的或最适宜的设计方案，它参照数学中的模型最优化原理应用到建筑工程结构设计方案的优化比选中。研究发现，建筑结构在使用过程中是否稳定、耐久、合理等，主要决定于在建筑结构设计时选定的结构类型是否最优、是否最符合工程结构的需要。对于同一座建筑工程项目，不同的结构设计师知识储备不同，因此可能会设计出不同的结构类型、结构体系，但经过结构方案的优化、从而选取最优化的结构类型，提高建筑结构的使用寿命、稳定性能。 1建筑结构优化的主要因素 1.1荷载设计 研究发现，任何一座建筑结构都需要受到水平力和竖向荷载的作用，同时建筑还要承受较大的风荷载、地震力的作用等。当建筑结构的整体高度比较低时，由结构本身的重力引起的竖向荷载对结构的作用比较明显，而水平荷载作用在结构上，产生的内力和位移比较小，往往在计算时不考虑水平荷载的作用；若在较高层建筑设计中，虽然所受到的竖向荷载仍对结构产生较大程度的影响，但水平荷载对建筑结构本身的影响比竖向荷载产生的影响更加强烈。研究表明，随着建筑结构整体高度的逐渐增加，水平荷载对建筑结构产生的影响越将会越来越大，因此，在建筑结构高度较高时，结构所承受的水平荷载对结构的影响则不可忽视。 1.2选取结构类型较轻的
在建筑结构优化过程中，要尽量选取结构体较轻的。在现代结构优化设计中，设计人员越来越重视选用轻质高强材料，从而做大程度上减轻整体结构的自重。由于在多层建筑结构中，水平荷载对结构产生的影响处于较次要地位，结构所承受的主要荷载是竖向荷载。由于多层建筑楼层较少，整体高度相对比较低，结构自重相对来说较轻，对材料的强度要求不是特高。 但随着建筑结构高度的增加，在较多的楼层作用下，结构产生的自重荷载则会比较大，使得建筑结构对基础产生较大的竖向荷载，同时在水平荷载的作用下，结构的竖向构件（柱）中会产生较大的水平剪力和附加轴力。为了使得结构满足刚度和强度的要求，通常采取加大结构构件的截面尺寸，但是加大构件的截面尺寸会使得结构的整体自重增加。因此在高层建筑结构首先应该考虑如何减轻结构的自重。 研究表明，当在高层或超高层建筑结构优化设计时，选用结构强度高、自重较轻的钢结构、高强混凝土结构可以很大程度上减小建筑结构的自重。 1.3 侧向位移 据相关资料表明，建筑结构的侧向位移随着建筑高度的增加而逐渐增大，因此，在建筑结构的优化设计中，对层数较少、高度较低的结构，可以不考虑其侧向位移对结构的影响。但随建筑结构高度的增加，整体结构的侧移对结构产生的影响则不可忽视。 研究表明，由于水平荷载对结构作用产生的侧移随着建筑高度的增加而逐渐增大，且侧移量与结构高度成一定的关系。 在进行高层建筑结构优化设计时，既需要充分考虑建筑结构整体是否具有足够的承载能力，能否承受风荷载的冲击作用，又要求结构具有足够的抗侧移性能，当建筑结构受到较大的水平力作用下，其可以很好地控制产生过大的侧移量，确保结构整体的稳定性能。 与低层或多层建筑相比，高层建筑结构的刚度稍微差一些，在发生地震灾害时，结构的侧向变形更大。为了确保高层建筑结构在进入塑性阶段后，结构整体仍具有较强的抗侧移性能，保持结构的稳定性，则需要在高层建筑结构的构造上采取合适的措施，确保结构具有足够的延性，从而满足结构的刚度要求。
＊)国家自然科学基金项目(10471045)、广东省自然科学基金(04020079)、华南理工大学自然科学基金(B13-E5050190)。吴广潮 讲师,博士研究生,研究领域为算法设计与分析,数据库与信息处理;黄 翰 博士研究生,研究领域为进化计算方法的理论基础,进化计算方法的优化设计及其应用。 计算机科学2008V ol .35№.3 基于离散数字编码的蚁群连续优化算法＊) 吴广潮1,2 黄 翰2 (华南理工大学数学科学学院 广州510640)1 (华南理工大学计算机科学与工程学院 广州510640) 2 摘 要 本文提出了一种基于离散编码的蚁群连续优化算法(CA CO -D E ),用于求解连续优化问题。以往蚁群算法(A CO )的研究,以求解离散优化问题为主,较少涉及连续优化问题。与经典的A CO 算法不同,CACO -DE 将有限精度的实数转化为一个数字串,数字串的每位取0到9之间的数字,从而实现了用离散编码描述实数的效果。CA CO -DE 延用了经典A CO 算法的框架,并加入了特殊的选择机制、信息素更新方式和局部搜索策略。测试实验结果表明:CA -CO -DE 比以往同类算法求解速度更快且精度更高。关键词 蚁群算法,连续优化,离散数字编码 Ant Colony Continuous Optimization Based on Discrete Numerical Encoding W U G uang -Chao 1,2 H U AN G Han 2 (School of M athematical S cien ces ,S ou th China University of Tech nology ,Guangzhou 510640)1 (S chool of Computer S cien ce and En gineering ,S outh China Univers ity of Technology ,Gu angz hou 510640) 2 A bstract T he pr esented paper pro po ses an ant colony algo rithm fo r continuo us o ptimization (CA CO -DE ).A CO alg o -rithms are alway s used fo r discr ete o ptimizatio n problem s ,but rar ely fo r continuous o ptimiza tion .CA CO -DE is de -sig ned based o n the numerical encoding in which each real numbe r is chang ed into a string made up of character s {0,…,9}.T he leng th o f enco ding depends on the accuracy and dimension of the so lutio n .A r tificial ants construct so lutio ns being guided by a hig h dimensio n phero mone v ector .T he f ramewo rk of the proposed algo rithm is similar to the cla ssi -cal ACO except for the upda ting rule a nd local sear ch stra teg y .So me pr elimina ry re sults o btained o n benchmar k pro b -lems sho w that the new method can so lv e co ntinuous o ptimizatio n problem s faster than o the r a nt and no n -a nt methods .Keywords A nt co lo ny alg o rithm ,Co ntinuous optimizatio n ,Discre te numerical encoding 1 引言 蚁群算法(ACO )[1] 是由M .Do rig o 及其同伴在上世纪90年代提出的一种仿生算法,用于求解如旅行商问题[2]之类的组合优化问题。目前,A CO 算法的应用已经扩展到解决多种优化问题,如:V ehicle Ro uting [3]、Q uadra tic assig nment [3]、Qo S [4]、Job sho p [5]等,但这些问题几乎都是离散优化问题。 与遗传算法、粒子群算法和进化规划算法不同,ACO 算法求解连续优化问题的设计研究较少。第一种求解连续函数优化问题的蚁群算法为Co ntinuous A CO (CA CO )算法[6],其主要思想是将连续区间分段,离散化后区间段视为T SP 问题中的城市。CA CO 算法虽然实现了A CO 算法求解连续优化问题0的突破,但是求解效果并不理想。后期又对CACO 算法作了些改进[7,8],提高了求解的精度,但是改进的程度有 限。后来相应又有A PI [9]和CIAC [10]。另外两种算法出现,取得了一定的改进效果,但这些算法加入了遗传算法等其他计算工具的策略,只是用了A CO 算法的框架而已。最新的算法还有基于正态分布的ACO 算法[11],然而这种算法也需要将区间分段离散化,从而会出现两个缺点:1.算法求解精度有限;2.算法求解的计算复杂度较高,需要花费较多的函数评估次数。 作为改进,本文在文[12]基础上提出了一种新型的求解连续优化问题的A CO 算法:基于离散编码的蚁群算法(CA -CO -DE )。实验结果表明:CACO -D E 比以往其他ACO 算法 求解的效果更好,而且速度更快。 2 AC O 算法基本思想介绍 自然界蚂蚁在其经过的路径上会留下某种生物信息物质(信息素),该物质会吸引蚁群中的其它成员再次选择该段路径。食物与巢穴之前较短的路径容易积累较多的信息素,因而使得更多的蚂蚁选择走该段路径,最终几乎所有的蚂蚁都集中在最短路径上完成食物的搬运。M .Do rigo 等从此现象中抽象出路径选择和信息素积累的数学模型,作为蚁群算法的核心;并通过对蚂蚁寻找最短路径的计算机模拟,实现了对TS P 问题的求解[2]。 按M .Do rigo 的设计[3],蚁群算法的基本框架如图1所示 。 图1 蚁群算法(A CO )的基本框架 一般情况下,A CO 算法可以分为三个部分:生成解(Co n -structA ntsSo lutio ns ),更新信息素(U pdatePhero mone s )和附 加策略(DaemonA ctions )。 · 146·
现代机械设计理论及方法大作业及考试题 一、提交一份现代机械设计理论与方法理论及实际应用综述报告要求：阐述五种以上现代设计方法，参考文献不低于10篇，其中必须包含有英文参考文献。 二、完成现代机械设计理论与方法开卷试题，试卷题目如下： 1、采用系统化设计流程说明某公司今年需要投资研发一款新型汽车的整个设计流程。（20） （1）请具体阐述采用何种工作方法，如何去完成汽车的规划设计过程？ 答：首先需要通过市场调研，了解现有汽车的性能特点及市场上不同消费阶层客户对汽车功能、外观、能耗、及性价比的期望，然后与设计、营销人员共同分析讨论研究，明确所设计汽车的类别、目的和任务，最后结合实际现有生产能力的情况策划出生产汽车的品种样式，为后续工作做准备。 （2）请具体阐述采用何种工作方法，如何去完成汽车的方案设计过程？ 答：根据前一阶段制定的设计汽车类别和任务要求，利用系统化设计方法确定所设计汽车的总功能，然后将该总功能分解成为单个的分功能（功能元），然后利用物理数学知识及创造技法对该功能元求解，以得到最佳原理解，再通过最佳原理解的组合得到不同的设计方案。最后再根据对汽车的设计任务要求选择最佳设计方案。 （3）请具体阐述采用何种工作方法，如何去完成汽车的技术设计过程？ 答：根据方案设计阶段确定的汽车设计方案，召集设计人员初步设计出汽车的设计总图，然后对汽车进行可靠性设计、造型设计和工艺设计，以定性设计出汽车的结构，再选取汽车不同部件的材料、尺寸，通过对汽车进行价值设计、有限元设计、优化设计和动态设计，以定量设计汽车的具体结构尺寸。最后，请专家对这一阶段设计的汽车进行技术评价分析。
（4）请具体阐述采用何种工作方法，如何去完成汽车的施工设计过程？ 答：首先根据对汽车的前期设计和评价分析，对汽车进行总体设计，即通过专家系统、CAD/CAM 等技术设计出汽车的装配图，然后对汽车的零部件进行具体设计，即通过机械制造技术、装配、检验等方法确定汽车具体零部件的图纸，最后编写汽车设计的技术文件，图纸校正和汇总，以得到汽车最终设计说明书。 2、用系统化设计方法分析并提出垃圾清洁系统（车）的总体方案；用一种评价方法进行评价，得出合理方案，并建立该系统优化数学模型。 (20分) 答：首先，通过问卷调查等方式明确垃圾清洁车的总功能——压缩运输物料；然后，对其进行功能分解：压缩运输物料分为压缩物料和运输物料，而压缩物料又分为传动和压缩，运输物料分为传动和移位；再对分功能求解，通过垃圾清洁车的形态学得到具体的分功能解；最后方案组合，从得到的垃圾清洁车众方案中通过评价分析选取出效率高、承载能力强、生产及使用环境友好的垃圾清洁车，即最佳方案。 现代社会垃圾清洁车的生产要求成本低，使用要求寿命长且维修方便。因此采用技术——经济评价法来对垃圾清洁车的设计方案进行评价。 技术——经济评价法即对设计方案就经济和技术方面进行评价，求出加权相对价值，再进行综合比较。 （1）获得垃圾清洁车的技术评价Wt 垃圾清洁车的技术评价目标是求方案的技术价Wt ，就是求出垃圾清洁车的各项技术性能评价指标的评分值和加权系数乘积之和与最高分值的比值： max 1p q p W n i i i t ∑-= 其中，i p 是各项技术评价指标的评分值；i q 是各项评价技术指标的加权系数，11=∑-n i i q ；max p 是最高分。 （2）获得垃圾清洁车的经济评价Wt 垃圾清洁车的经济评价目标是求方案的经济价Ww ，就是求出垃圾清洁车的理想生产成本与实际生产成本的比值：
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/759733608.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 #
开料介绍以及启发式算法研究 目前针对PCB行业没有存在可以异形拼版的软件。但是有部分软件可以满足此功能都是应用在其他的行业，如果钢材切割，玻璃。五金之类的行业，这个些行业与PCB的拼版要求有很多工艺上的不一致。比如在钢材比较注重实际的利用率，玻璃行业在留下余料的时候需要考虑加工上的一些可行性。还有就是卷材行业有也类似应用。 下面针对启发式算法做些了初步的探讨 算法分析 问题说明： 一般的开料算法可以简单的表示成如下数学语言： 开料问题是寻找平面最优布局的优化问题，即将一系列二维不规则零件P1，P2，…Pn 合理地排放在原料板 B 中，使材料的利用率（使用面积总和／占用得原料板面积）最高，并满足下面的约束条件； l）料Pi，Pj 互不重叠：i，j＝l，2，…n。 2）料Pi 必须放在原料板B 中：i＝1，2，…n。 3）满足一定的排样要求。 4）满足加工的便捷以及可能性。 开料问题可以从两个方面加以说明，一个是开料过程中的几何问题，主要是针对规则或者不规则形状的零件，如何确定物料的最佳排放位置，检测物料位置的合理性以及相关算法。 另一个是物料的调度问题，即如何从参加物料的物料库中选出最优的物料零件，如何得到一个优化的物料排样顺序。无论是几何问题还是调度问题，都是非常复杂的问题。这种复杂性一方面来源于物料形状的不规则性，同时也与参与物料零件的多样性以及零件的批量、生产周期、排样方向性要求等有关。这些因素相互没有明确逻辑关系，也很难达到一个预期的全局最优解。在很多情况下，得到的结果都是局部最优解或者是次优解，当然如果只是针对PCB行业，在物料的多样性比其他的开料可能相对比较简单些，一般不会有太多的料需要进行一起拼版，一般针对开料优化搜索算法有启发式搜索算法、人工神经网络算法、模拟退火算法、遗传算法或者他们的组合来解决开料问题。也有这些算法的结果进行比较与分析，以寻求一种最好的优化算法。然而，研究结果表明这些开料算法的开料效率运行时间极长，利用率没有手工开料的高。也有开始从料的形状着手，通过求解任意多边形的临界多边形（NFP）来研究开料问题。目前的
启发式算法研究小结 0.探究启发式算法的缘由 在选《管理优化决策》这门课的时候，我抱着很强的好奇心和巨大的求知欲，试图尝试在这门课上学到我感兴趣的知识点以及确定我今后极有可能的研究领域和大方向。很幸运的是，我找到了。为什么这么说呢？就在我选择博士专业内选修课和专业外选修课的同时我发现了管理优化决策这门课和计算机学院那边开的选修课——《启发式优化》（由吕志鹏教授讲授），有很多是相通的，发现管理界尤其是在管理科学与工程方向和计算机技术应用领域所探究的问题出奇的一致，已经很难分清，哪个是管理方面的问题，哪个是计算机技术应用的范围了。正如各位都知道的是，由于选修课最终确定前一个月是可以去试听的，然而我并没有因为两者看上去内容有些相似就匆忙退选。通过对这两门课的内容进行比较，它给了我很大的触动，也带给我巨大的好奇，到底是管理方面的研究越来越偏向运用计算机等其他学科的知识和工具，还是计算机应用研究的方面越来越偏向实际的管理优化问题了呢？亦或者两个学科的边界正在走向模糊？我想学科交叉和融合的这一说法对于我来说可能并不是很新鲜，但这的确是我亲身经历的一种美妙体验和发现。它带给我新奇的同时也无疑给了我值得我深思几点的启示： 首先，众所周知，管理学科作为一门交叉的新兴学科，它的方法和工具都是依托和借助其他领域和学科而来的，它本身并没有或者几乎没有一个完完整整的只属于管理学科的方法和工具，几乎是其它学科的知识演变而来的，这就是我们所知道的学科交叉和学科融合；然而管理领域和传统计算机研究等领域的视角并不完全一样，其中对于计算机领域的研究者们而言，他们不但在乎启发式算法是否能够解决问题、效率是否大幅提高（而管理领域的专家们更在乎这点，能用第一，好用第二，或者说管理专家们更在乎第一点——问题能够得到的解决，至于第二点就不是那么迫切。而对计算机领域的向专家们而言，可以说两者都非常重要、要求非常苛刻），更在乎它所表现出来的优越特性（就时间、空间复杂度以及算法求解过程中保持一定的集中性和分散性而言的）。然而当管理领域的学者们求解类似问题，一般来说都是和我们生活中的管理者经常遇到且直接和的决策相关的问题，因为由于管理者的决策质量好坏会往往直接导致企业和团体的效率和绩效和高低，进而导致企业和组织的竞争力强弱，所以一般企业或者个人都是基于一定的价值诉求来解决管理问题，进而提高工作效率。由于管理者们非常了解生活中并不存在完完全全的理性人和完全信息，因此他们很难也极少去尝试寻找最优解，找到满意解就可以了，这一点和启发式算法的设计思想不谋而合（由于
现代设计方法综述及在灌注桩抽芯钻机上的应用 摘要：现代设计是传统设计活动的延伸和发展，是传统设计的深入、丰富和完善。随着计算机技术等现代高新技术的高速发展以及设计实践经验的逐步积累，设计工作包括机械产品的设计过程产生了质的飞跃，这种有别于传统设计方法的新兴理论与方法称为现代设计。现代设计方法以计算机辅助设计技术为主体，以满足产品的质量、性能、时间、成本、价格等综合效益最优为目的，它不仅指设计方法的更新，也包含了新技术的引入和产品的创新，既是新兴理论，亦是相关高新技术。本文亦对现代设计方法在灌注桩抽芯钻机设计上的应用，从而更好地理解其在现代设计上重要作用。 关键词：现代设计；现代设计方法；发展趋势；灌注桩抽芯钻机 1 现代设计的由来 设计是把一种计划、规划、设想通过视觉的形式传达出来的活动过程，是具有高级思维能力的人的本能。人类为了适应生存环境和发展自身，出现了各种精神上和物质上的需求，为了满足这些需求，人们需要通过创造性的思维产生构思，并采取一定的技术途径实现这些构思，改造世界，创造文明，创造物质财富和精神财富，这个过程就是设计。因此，可以说从人类诞生之日，就孕育了设计的萌芽，设计活动就是人类文明的创造活动，它不论是在精神财富还是在物质财富的创造中都起到了重要作用。人类最基础、最主要的创造活动是造物。设计便是造物活动进行预先的计划，可以把任何造物活动的计划技术和计划过程理解为设计。 随着工业革命的到来，生产方式发生了巨大变化，促使人们加强了设计基础理论和各种专业产品设计的研究，以提高设计水平；同时还加强了零件的标准化、部件的通用化以及产品的系列化研究，以进一步提高设计的速度、质量，降低设计成本。在计算机出现以前，人们就已经把各种产品设计的经验总结成有关的设计理论、设计步骤和设计手册等，这种设计通常称之为传统设计。 随着科学技术的发展和人们需求的不断提高，促使设计的内涵和外延不断深化和扩展。从20世纪60年代末开始，设计领域相继出现了一系列新的设计思想、理论与方法，使设计变得更加科学、理性和高效，为了与之前相对经验的、感性的、以人工为主的传统设计相区别，人们称之为“现代设计”。 2 现代设计方法 现代设计方法是随着当代科学技术的飞速发展和计算机技术的广泛应用而在涉及领域发展起来的一门新兴的多元交叉学科。它是以设计产品为目标的一个总的知识群体的总称。目前它的内容主要包括：优化设计、可靠性设计、计算机辅助设计、工业艺术造型设计、虚拟设计、疲劳设计、三次设计、相似性设计、模块化设计、反求工程设计、动态设计、有限元法、人机工程、价值工程、并行工程、人工神经元计算方法等。在运用他们进行工程设计时，一般都以计算机作为分析、计算、综合、决策的工具。本文以计算机辅助设计、优化设计、可靠性设计、有限元法、工业艺术造型设计、设计方法学、三次设计等为例来说明现代设计方法的基本内容与特点。 2.1 计算机辅助设计 计算机辅助设计（Computer Aided Design)，简称CAD。他是把计算机技术引入设计过程并用来完成计算、选型、绘图及其他作业的一种现代设计方法。计