史上最全ISIGHT优化算法

wangzhkk

　　ISIGHT软件是一款高度智能的软件机器人，为用户提供了高效、全面、强大、丰富、快捷、灵活、方便的优化集成平台，可以和市面上绝大多数工程软件、有限元分析软件、三维软件、办公软件、数值计算软件、数据库等进行集成，实现产品设计、仿真、优化的全流程，尤其是ISIGHT提供了非常全面的优化算法，下面我们就来一探究竟!

　　ISIGHT的优化算法分为四大类，分别为直接搜索法、梯度优化算法、全局优化算法、多目标优化算法，如下图所示。每种类都提供了大量的高效优化算法，各算法之间相互补充，各有所长，大大扩展了ISIGHT的优化能力。




　　全局优化算法
　　优势：
　　适应性强：只评价设计点，不计算任何函数的梯度;
　　具有全局性：能求解全局最优解，避免了集中在局部区域的搜索;

　　缺点：
　　相比数值优化算法，全局探索法的计算量比较大;

　　l MIGA算法
　　Isight中的MIGA多岛遗传算法本质上是日本Doshisha大学知识工程系(Department of KnowledgeEngineering)的M. Kaneko, M. Miki, T. Hiroyasu等人对并行分布遗传算法(PDGAs, ParallelDistributed Genetic Algorithms)的改进，它具有比传统遗传算法更优良的全局求解能力和计算效率。遗传算法(GA，Genetic Algorithm)是Holland在60年代提出的，主要借助生物进化过程中“适者生存”的规律，模仿生物进化过程中的遗传繁殖机制，对优化问题解空间的个体进行编码(二进制或其他进制)，然后对编码后的个体种群进行遗传操作(如：选择、交叉、变异等)，通过迭代从新种群中寻找含有最优解或较优解的组合。

　　l ASA算法
　　模拟退火算法(Simulated Annealing,简称SA)和遗传算法有很多相似之处，他们都需要从旧的设计点通过变异产生新的设计点。模拟退火算法比遗传算法简单，因为它每次在搜索空间中只检查一个设计点，而遗传算法检查一组设计点(一个种群)。
　　SA的思想最早由Metropolis等提出，通过模拟退火过程，将组合优化问题与统计力学中的热平衡问题类比，从初始点开始每前进一步就对目标函数进行一次评估，只要函数值下降，新的设计点就被接受，反复进行，只到找到最优点。函数值上升的点也可能被接受，这样能够避免找到的是局部最优点。是否接受函数值上升点是依据Metropolis 判据决定的，它是温度的函数，温度高则更容易接受。伴随温度参数的不断下降，结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部优解能概率性的跳出并最终趋于全局最优。
　　SA对离散变量的组合优化问题和连续变量函数的极小化问题都获得了很大成功。经过多年的研究，SA算法有多种改进算法，比如：加温退火法、记忆模拟退火法等。Isight中的ASA自适应模拟退火算法是Ingber等人提出的改进算法，它具有比传统SA算法更优良的全局求解能力和计算效率。

　　PSO算法
　　粒子群优化(Particle SwarmOptimization, PSO)，又称微粒群算法，是由Kennedy和 Eberhart等于1995年开发的一种演化计算技术，最初是为了研究鸟群捕食的行为。PSO算法采用了演化计算的原则：1.从一组随机种群开始初始化;2.通过更新种群代搜索最优解;3.进化依赖于前面的种群。
　　PSO采用粒子群在解空间中追随最优粒子进行搜索，而不再有遗传算法的交叉和变异操作。因此相对遗传算法而言，PSO的优势在于简单容易实现，并且没有太多参数需要调整。

　　l Pointer算法
　　Pointer优化器是Isight提供的智能自动优化专家。Pointer优化器会自动捕捉设计空间的信息，自动组合四种优化算法形成一个最优的优化策略，在一定给程度上大大降低了工程师的使用门槛，特别适合于那些对设计空间不太了解、对算法使用不太了解的设计者。
　　Pointer包括四个方法的组合：线性单纯形法(linear simplex)、序列二次规划法(sequential quadraticprogramming (SQP))、最速下降法(downhill simple)和遗传算法(genetic algorithms)。
　　线性单纯形法适合与解决线性问题;序列二次规划法适合于解决光滑的问题，具有非常好的收敛性和数值稳定性;最速下降法适合于非光滑的问题，它一般从约束边界开始计算，而且具有非常高的效率;遗传算法适合于全局的，非光滑的，不连续的优化问题，但是它的计算比较耗时。

　　多目标优化算法
　　优势：
　　能够对多目标函数的优化问题给出有效的优化解;
　　可对凹陷解集进行有效求解;
　　缺点：
　　有些情况下，非劣解较多，不好选择;
　　一般优化时间较长;

　　NSGA-II算法
　　NSGA-Ⅱ，作为1994年发布的NSGA(Non-Dominated Sorting Genetic Algorithm)的改良版，由K.Ded，S.Agrawal等在2000年提出。NSGA-Ⅱ优点在于探索性能良好。在非支配排序中，因为接近Pareto前沿的个体被选择，使Pareto前进能力增强。
　　导入了“拥挤距离”和“拥挤距离排序”的方法，在具有同样的Pareto顺序的层内，可以对个体进行排序，称为拥挤距离排序。拥挤距离排序中不会削除frontier的端头部分，所以Pareto前沿不会收束一部分的领域里。
　　进化过程中，将当前父代群体进行交叉和变异得到子群体，将两个群体合并。在目标空间中按照Pareto最优关系将群体中个体两两按其目标函数向量进行比较，将群体中所有个体分成多个依次控制的前沿层。在属于不同的Pareto层的情况下，利用评价Pareto优越性来评价个体的优劣。属于同一个Pareto层的个体，具有更大的拥挤距离的个体更优秀。
　　在NSGA-Ⅱ中，作为交叉和突然变异的运算机制使用叫做SBX(Simulated Binary crossover)的方法。根据SBX方法生成子个体：交叉运算。

　　NCGA算法
　　NCGA方法是由最早的GA(GeneticAlgorithm)算法发展而来，它视各目标同等重要，通过排序后分组进行交叉的方法实现“相邻繁殖”的机制，从而使接近于Pareto前沿的解进行交叉繁殖的概率增大，加速了计算收敛过程。NCGA步骤如下：
　　第1步 初始化：令t=0,，设置第一代个体P0，种群数为N，计算个体对应的适应值函数，计为A;
　　第2步 另t=t+1，Pt=At-1
　　第3步 排序：个体Pt按向聚集的目标值的方向进行排序;
　　第4步 分组：个体Pt根据上述排序分为若干组，每组由两个个体组成;
　　第5步 交叉和变异：在每一组中执行交叉和变异操作，由两个父代个体产生两个子代个体，同时父代个体被删除;
　　第6步 重组：所有子代个体组成一组新的Pt;
　　第7步 更新：将At-1与Pt组合，按环境选择(Envirment selection)机制，从2N个个体中，选出其中的N个个体;
　　第8步 终止：如果满足终止条件，则终止优化程序，否则返回至第2步。

　　AMGA算法
　　AMGA算法在进化过程之外设立一个存档(Archive)，用于保存进化过程中的非支配个体及相应的多目标函数值，方法如下：
　　1. 通过支配关系选择出当前代种群X(t)中的非支配个体X*;
　　2. 将X*与档案A(t)中的个体放在一起进行比较：若X*被档案A(t)中的个体所支配，则X*不能进入档案A(t);若X*与档案A(t)中的个体无支配关系，则X*进入档案;若X*支配档案A(t)中的某些个体，则X*进入档案，并剔除那些被支配的个体。档案A(t)中的个体在进化过程中保持支配地位。
　　3. 当准则终止时，档案A(t)中的解集即为所要求的Pareto最优解集的近似解集。

　　l PE算法
　　由于传统多目标遗传算法(包括NSGA-II、NCGA、AMGA等)在整个设计空间搜索Pareto最优解，需要通过大量的迭代获得高精度的Pareto前沿，从而限制了其解决复杂、大规模多目标优化问题的能力。

　　PE算法(ParetoExplorer)是树优公司和美国eArtius公司联合为Isight开发的高效全局多目标探索算法组件。PE算法包含的四个子算法，其中的HMGE算法是由遗传算法和梯度算法两部分构成的全局优化策略：首先，用多目标遗传算法获得非支配解集，然后对每一个非支配解，寻找能够同时改进所有目标函数的梯度方向(多目标梯度探索法MGE，Multi-GradientExploration)继续精确收敛到局部Pareto解。



转自：http://mp.weixin.qq.com/s?__biz= ... AAbXykw485yQ0y6O#rd