精华内容
下载资源
问答
  • 智能优化算法
    千次阅读
    2019-08-05 21:04:02

    1、简介

    人们总是能从大自然中得到许多启迪,从生物界的各种自然现象或过程中获得各种灵感,由此提出了许多能够解决复杂函数优化的启发式算法,主要分为演化算法和群体智能算法。

    演化算法是一种模拟生物进化的随机计算模型,通过反复迭代,那些适应能力强的个体被存活下来,比如遗传算法,进化规划,进化策略等。

    群体智能算法是通过观察社会生物群体的各种行为得到启发而提出的一种新型的生物启发式计算方法,比如蚁群、鸟群、狼群、鱼群、萤火虫群等。

    2、演化算法

    遗传算法(Genetic Algorithm,GA:是基于Darwin进化论和Mendel的遗传学说的随机化自适应搜索算法,最先由美国Michigan大学的Holland教授于1975年提出。由于采用了类似物种进化过程中基因的选择、交叉和编译等操作手段,使得遗传算法在本质上成为一类非确定性算法,具有全局搜索能力,特别适用于多峰值函数的优化问题。遗传算法思想是从代表问题可能潜在解集的一个种群开始,一个种群由经过基因编码的一定数目的个体组成,初始种群生产之后,按照适者生存和优胜略汰的原理,逐代演化生产出越来越好的近似解。每一代,根据问题域中个体的适应度挑选个体,并借助自然遗传学的遗传算子进行交叉和变异,产生出代表新的解集的种群。这过程将导致种群像自然进化一样,后代种群比前代更加适应环境,末代种群中的最优个体经过编码可以作为问题的近似解。在人工智能研究中,人们认为遗传算法、自适应系统、细胞自动机、混沌理论与人工智能一样,都是对今后的计算技术有重大影响的关键技术。

    差异演化算法(Differential Evolution, DE:是一种基于群体差异的演化算法,该算法是RainerStorn和KennedyPrice在1996年为求解切比雪夫多项式而提出,随后在各个领域得到了广泛应用。差异演化是基于实数编码的进化演化算法,它的群体结构类似于遗传算法,与遗传算法的主要区别在变异操作上,差异演化的变异操作是基于染色体的差异向量进行,其余操作和遗传算法类似。由于差异演化的关键步骤变异操作是基于群体的差异向量信息来修正各个体的值,随着进化代数的增加,各个体之间的差异化信息在逐渐缩小,以至于后期收敛速度变慢,甚至有时会陷入局部最优点。

    3、群体智能算法

    群体智能优化算法统一框架模式:

    群体智能优化算法是一类基于概率的随机搜索进化算法,各个算法之间存在结构、研究内容、计算方法等具有较大的相似性。因此,群体智能优化算法可以建立一个基本的理论框架模式:

    Step1:设置参数,初始化种群;

    Step2:生成一组解,计算其适应值;

    Step3:由个体最有适应着,通过比较得到群体最优适应值;

    Step4:判断终止条件示否满足?如果满足,结束迭代;否则,转向Step2;

    各个群体智能算法之间最大不同在于算法更新规则上,有基于模拟群居生物运动步长更新的(如PSO,AFSA与SFLA),也有根据某种算法机理设置更新规则(如ACO)。

    统一框架下的群体智能优化算法,可以根据优化对象的特性只能地选择适合的更新规则,进行运算得到理想的优化结果。

     蚁群算法(Ant Colony, ACO:是模拟真实的蚁群秘觅食过程寻求最短路径的原理,由意大利学者Dorigo等在20世纪90年代首先提出。最初的蚁群算法成为蚂蚁系统,对于旅行商问题(TSP)及二次分配问题(QAP)等取得了较好效果,经过改进后成为蚂蚁算法或蚁群算法。蚁群算法吸收了蚂蚁群体行为的典型特征:一是能觉察小范围区域内情况,并能判断出是否有食物或其他同类的信息素轨迹;而是释放自己的信息素;三是所遗留的信息素会随时间而逐步减小。蚁群算法通过候选解组织群体的过程来寻求最优解,这个过程包括适应阶段和协作阶段。在适应阶段,各候选解根据积累的信息不断调整自身的结构;在协作阶段各候选解间通过信息交流,以便产生系能更好的解。

     人工神经网络(Artificial Neural Network,ANN:1943年心理学家McCulloch和数学逻辑学家Pitts在研究生物神经的基础上,首先利用数理逻辑提出了第一个简单的ANN模型,开创了了ANN研究的先河。该算法是大脑及其活动的一个理论化的数学模型,由大量的处理单元相互连接而成,是神经元联结形式的数学抽象,是一个大规模的非线性自适应模型。人工神经网络具有高速的运算能力、很强的自学能力、自适应能力和非线性映射能力以及良好的容错能力,特别适用于处理需要同时考虑多种因素和条件的,不精确和模糊的信息处理问题,因此广泛应用于模式识别、图像处理、信号及信息处理、系统优化和智能控制等,特别是近期非常火热的神学学习算法是多层神经网络的应用。

     人工免疫算法(Artificial Immune Algorithm,AIA:免疫系统是哺乳动物抵御外来有害物质侵害的防御系统,动物一生处于复杂多变、充满伤害的自然环境中,但是它们能够平安无事地进行正常的生命活动,其原因是免疫系统在起着重要作用。人工免疫算法正是基于生物免疫抗体产生记忆系统的学习机理的产物。20世纪90年代初,Bersini和Varela首次实用AIA来解决实际问题。该算法是继遗传算法以来又一种具有广阔应用前景的方胜优化算法。

    粒子群优化算法(Particles warm optimization algorithm, PSO):最早是在1995年由Kennedy和Eberhart提出的一种基于智能启发的全局优化技术演化计算方法,起源于生物学家对鸟群觅食过程行为的观察研究,具有易理解、易实现、全局搜索能力强等特点备受科学工程领域的极大关注。 设想这样一个场景:一群鸟在随机搜索食物,在这个区域里只有一块食物,所有的鸟都不知道食物在哪里,但是他们当前的位置离食物还有多元。那么找到食物的最优策略是什么呢,最简单有效的搜索目前离食物最近的鸟的周围区域。PSO算法中,每个优化问题的潜在解都是搜索空间中的一只鸟,称之为“微粒”,所有的微粒都有一个被优化的函数决定的适应值,每个微粒海有一个速度决定他们飞翔的方向和距离,然后微粒们就追随当前最优微粒在解空间中搜索。PSO算法初始化为一群随机微粒(随机解),然后通过迭代找到最优解,在每次迭代中,微粒通过跟踪两个“极值“来更新自己。第一个就是微粒本身所找到的最优解,这个解成为个体极值;另一个极值是整个种群目前找到的最优解,这个极值是全局极值。

    灰狼优化(Grey wolf optimization,GWO:狼是一种非常有智慧的动物,它们在捕食食物的时候往往不是单独行动,而是由几匹狼组成小队。狼群搜索算法就是基于狼群的这种捕食行为提出的一种新的群智能算法。(1)考虑到狼群中领头狼领导决策的现象,又提出了基于领导者策略的狼群搜索算法,该算法思想源于狼群个体之间存在相互竞争,从而推选出狼群中最为精壮的狼作为狼群的领导者,然后在领导者的带领下获取猎物,这样使得狼群能够更加有效地捕获到猎物。狼群在领导者狼的带领下通过不断搜索,捕获猎物,该过程对于优化问题,最终可找到全局最优解。(2)考虑到狼群中严格的等级制度,提出了一种强化狼群等级制度的灰狼优化(GWObased on strengthening the hierarchy of wolves, GWOSH)算法。该算法为灰狼个体设置了跟随狩猎和自主探索两种狩猎模式,并根据自身等级情况来控制选择狼群的狩猎模式。在跟随狩猎模式中,灰狼个体以等级高于自身的灰狼的位置信息来指引自己到达最优解区域;而在自主探索模式中,灰狼个体会同时审视等级高于自身的灰狼的位置信息和自身位置信息,并基于这些信息自主判断猎物的位置,同时两种更新模式都将引入优胜劣汰选择规则来确保种群的狩猎方向。

    人工萤火虫群优化算法(Glowworm Swarm Optimization,GSO):是模拟自然界萤火虫群觅食或求偶行为而设计出的一种新型仿生群智能优化算法。由K.N.Krishnanad和D.Ghose于2005年提出一种新型群智能优化算法,近年来,人工萤火虫群优化算法越来越受到人们的关注,逐渐成为计算智能领域一个新的研究热点,该算法已成功应用于传感器的噪声测试、多模函数优化、模拟机器人、多信号源跟踪与定位和有害气体泄露定位等方面,均表现出良好的性能。

    人工鱼群算法(Artificial Fish-Swarm Algorithm,AFSA):是由李晓磊等在2002年提出的,源于对鱼群运动行为的研究,是一种新型的智能仿生优化算法.在基本的AFSA算法中,主要是利用了鱼群的觅食、聚群和追尾行为,从构造单条鱼的底层行为坐骑,通过鱼群中各个体的局部寻优,达到全局最优值在群体中突显出来的目的。它具有较强的鲁棒性、优良的分布式计算机制、易于和其他方法结合等优点.目前对该算法的研究、应用已经渗透到多个应用领域,并由解决一维静态优化问题发展到解决多维动态组合优化问题.

     布谷鸟搜索算法(RC-SSCS)布谷鸟搜索(CS)是Yang等于2009年提出的一种新兴生物启发算法。CS算法通过模拟某些种属布谷鸟的寄生育雏习性有效地求解最优化问题。某些种属的布谷鸟将自己的卵偷偷地产入宿主巢穴,由于布谷鸟后代的孵化时间比宿主的幼雏早,孵化的幼雏会本能地破坏同一巢穴中其它的卵,并发出比宿主幼雏更响亮的叫声。很多宿主通过后代的叫声大小判断其健康程度,而健康后代获得的食物较多,进而拥有更高的存活率,在某些情况下,宿主也会发现巢穴中的陌生卵。这时,宿主将遗弃该巢穴,并选择其它地方重新筑巢。在与宿主不断的生存竞争中,布谷鸟的卵和幼雏叫声均朝着模拟宿主的方向发展,以对抗宿主不断进化的分辨能力。

    混合跳蛙算法(Shuffled Frog Leaping Algorithm, SFLA:在一片湿地中生活着一群青蛙,湿地内离散地分布着许多石头,青蛙通过寻求不同的石头进行跳跃去找到食物较多的地方,每个青蛙通过寻找不同的石头提高自己寻找食物的能力,而青蛙个体之间通过思想的交流实现信息的交换。混合跳跃青蛙,是带子群体的青蛙群。每只青蛙都有自己的文化,为了达到自己的目标努力,并定义为问题的一个解。湿地的整个青蛙群体被分为不同的子群体,每个子群体有自己的文化,执行局部搜索策略。在子群体中的每个个体有着自己的文化,并且影响着其它个体,并随着子群体的进化而进化。当子群体进化到一定阶段后,各个子群体之间再进行思想的交流实现子群体间的混合运算,一直到所设置的条件满足为止。

     -------------------------------------

    参考文献:

    王辉, 钱锋. 群体智能优化算法[J]. 化工自动化及仪表, 2007, 34(5):7-13.

    王艳玲, 李龙澍, 胡哲. 群体智能优化算法[J].计算机技术与发展,2008, 18(8):114-117.

    张永韡, 汪镭, 吴启迪. 动态适应布谷鸟搜索算法[J].控制与决策,2014(4):617-622.刘明广. 差异演化算法及其改进[J].系统工程,2005, 23(2):108-111.

    王闯. 人工鱼群算法的分析及改进[D].大连海事大学,2008.

    钟一文. 智能优化方法及其应用研究[D].浙江大学,2005.

    更多相关内容
  • 基于元学习的推荐算法选择优化框架实证.pdf
  • 为了提高多目标优化算法的求解性能,提出一种启发式的基于种群的全局搜索与局部搜索相结合的多目标进化算法混合框架.该框架采用模块化、系统化的设计思想,不同模块可以采用不同策略构成不同的算法.采用经典的改进非...
  • 本篇文章介绍了,在java中使用简单的demo实例告诉你优化算法的强大。需要的朋友参考下
  • 编程语言轻松实现蚁群优化算法。 它包含元启发式中存在的公共元素,以允许算法设计者重用公共行为。 使用 Isula,只需几行代码即可解决 Ant Colony 的优化问题。 伊苏拉在行动 如果您不熟悉该框架,可以从经典的旅行...
  • 基于元学习推荐的优化算法自动选择框架与实证分析.pdf
  • 天鹰优化算法(Aquila Optimizer,AO)由Laith Abualigah等人于2021年提出,该算法的灵感来自天鹰在自然界中捕捉猎物的行为。 天鹰是深棕色的,脖子后面有浅金棕色的羽毛。幼天鹰主要在尾巴上有白色,通常,它们的...

    一、算法简介

    天鹰优化算法(Aquila Optimizer,AO)由Laith Abualigah等人于2021年提出,该算法的灵感来自天鹰在自然界中捕捉猎物的行为。
    天鹰是深棕色的,脖子后面有浅金棕色的羽毛。幼天鹰主要在尾巴上有白色,通常,它们的翅膀上有轻微的白色痕迹。天鹰利用其速度和敏捷性与坚固的脚和大而锋利的爪子相结合,抓住各种猎物,主要是兔子,野兔,深海,土拨鼠,松鼠和其他地面动物。天鹰使用四种狩猎方法:
    在这里插入图片描述

    第一种方法是用垂直弯腰高空翱翔,用于狩猎飞行中的鸟类。天鹰在地面上高空升起,一旦它探索了猎物,天鹰就会进入一个长而低角度的滑翔,随着翅膀的进一步关闭,速度会上升。天鹰需要在其猎物上方有一个高度特征,才能使这种方法取得成功。天鹰在交战之前,翅膀和尾巴展开,脚向前推以抓住猎物。

    第二种方法是进行短滑翔攻击的轮廓飞行,这被认为是天鹰最常使用的方法。其中天鹰在地面上以低水平上升,无论猎物是在奔跑还是在飞行,猎物都会被近距离追捕。这种方法有利于狩猎地松鼠,繁殖松鸡或海鸟。

    第三种方法是低空飞行,缓慢下降攻击。在这一点上,天鹰低落到地面,接下来对猎物进行猛烈的攻击。天鹰选择它的受害者,并落在猎物的脖子和背部,然后试图穿透。这种狩猎方法用于狩猎行动缓慢的猎物,如响尾蛇,刺猬,狐狸和任何没有逃生反应的猎物。

    第四种方法是行走和捕捉猎物,天鹰在陆地上行走并试图拉动猎物。它用于将大型猎物(即鹿或羊)的幼崽拉出覆盖区域。

    二、算法原理

    天鹰优化算法的优化过程用4种方法表示:垂直弯腰高空翱翔选择搜索空间,高空飞行在分叉搜索空间内探索,在收敛搜索空间内慢速下降攻击,步行捕获猎物。

    2.1全局搜索

    天鹰识别猎物区域,并通过垂直弯腰的高空翱翔飞行选择最佳狩猎区域。天鹰广泛地从高空翱翔,以确定搜索空间的区域,猎物在哪里。
    在这里插入图片描述在这里插入图片描述
    在这里插入图片描述

    2.2局部探索

    当天鹰从高空翱翔发现猎物区域时,会在目标猎物上方盘旋,然后发动攻击。这种方法称为短滑翔攻击式的轮廓飞行。
    在这里插入图片描述在这里插入图片描述

    2.3全局开采

    当猎物区域被准确确定,并且天鹰准备好着陆和攻击时,天鹰会垂直下降,进行初步攻击以试探猎物的反应。这种方法称为低空飞行与缓慢下降攻击。天鹰利用目标的选定区域来接近猎物并进行攻击。
    在这里插入图片描述
    在这里插入图片描述

    2.4局部开采

    当天鹰接近猎物时,天鹰会随机运动攻击猎物。这种方法称为步行捕获猎物。
    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述

    三、算法描述

    在这里插入图片描述
    在这里插入图片描述

    四、多目标天鹰优化算法MOAO

    将天鹰优化算法的优良策略与多目标优化算法框架结合形成多目标天鹰优化算法(MOAO),为了验证所提的MOAO的有效性,将其在46个多目标测试函数(ZDT1、ZDT2、ZDT3、ZDT4、ZDT6、DTLZ1-DTLZ7、WFG1-WFG10、UF1-UF10、CF1-CF10、Kursawe、Poloni、Viennet2、Viennet3)上实验。

    4.1 部分实验结果

    ZDT1:

    在这里插入图片描述

    ZDT2:

    在这里插入图片描述

    ZDT3:

    在这里插入图片描述

    ZDT4:

    在这里插入图片描述

    DTLZ5:

    在这里插入图片描述

    DTLZ6:

    在这里插入图片描述

    Viennet3:

    在这里插入图片描述

    4.2源代码见评论区

    展开全文
  • 用matlab实现了标准粒子群算法,遗传算法,以及粒子群遗传算法的结合算法。可直接运行
  • 基于改进粒子群优化算法的钢框架抗震优化设计.pdf
  • 之前的研究的是有关多目标优化的方向,期间涉及到二次规划问题最优求解,以及kkt条件相关的知识。在研究启发式方法的同时也涉及到与传统优化方法的比较。因此在这里总结一些运筹向常见的问题, TSP、VRP、设施选址...


      之前的研究的是有关多目标优化的方向,期间涉及到二次规划问题最优求解,以及kkt条件相关的知识。在研究启发式方法的同时也涉及到与传统优化方法的比较。因此在这里总结一些运筹向常见的问题。如旅行商问题TSP、车辆路径规划VRP、设施选址问题、网络优化、物流调度等。
      然后介绍优化领域内的常用算法如遗传算法、粒子群算法、分支定界法、动态规划法、贪心算法。
      最后介绍谷歌DeepMind用神经网络求解MIP的方法。

    1、常见问题介绍

      (1)TSP旅行商问题:一个商人从一点出发,经过所有点后返回原点。它需要满足:除起点和终点外,所有点当且仅当经过一次;起点与终点重合;所有点构成一个连通图。要求:得到这个商人经过所有点的最短路程。
      (2)VRP车辆路径规划问题:对一系列装卸货点进行适当的路径规划,在满足约束条件(客户需求、车辆载重和容积、车型、车辆行驶里程、配送时间窗、配送中心数量等限制)和目标最优化(路程最短、成本最低、使用车辆数最少、配送时间最快等)下,将客户的配送需求从配送中心送达客户点,或从客户点送回配送中心。
      (3)设施选址问题:自20世纪60年代初期以来,在运筹学中一直占据着中心位置。它来自于工厂、仓库、超市、学校、医院、图书馆、火车站、代理服务器、传感器等位置的确定问题。
      (4)网络最优化问题:是一类特殊的组合最优化问题。应用图论理论,通过网络的拓扑结构及其性质,对网络进行研究,并且以计算机算法寻求网络中的最短路、最大流等。
      (5)物流调度:物流调度是指车辆分配情况的掌控及司机及车上货物跟踪。物流调度主要是指在物流过程中,物流公司根据待发货物的重量,去向,规格,加急程度等对所属的车辆和人员进行合理的安排调度。

    2、常用算法

      (1)遗传算法:该算法通过数学的方式,利用计算机仿真运算,将问题的求解过程转换成类似生物进化中的染色体基因的交叉、变异等过程。在求解较为复杂的组合优化问题时,相对一些常规的优化算法,通常能够较快地获得较好的优化结果。遗传算法已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。
      (2)粒子群算法:PSO中优化问题的每个解都是搜索空间中的一只鸟。我们称之为“粒子”。所有的粒子都有一个由被优化的函数决定的适应值(fitnessvalue),每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。
      (3)分支定界法:基本思想是对有约束条件的最优化问题的所有可行解(数目有限)空间进行搜索。该算法在具体执行时,把全部可行的解空间不断分割为越来越小的子集(称为分支),并为每个子集内的解的值计算一个下界或上界(称为定界)。在每次分支后,对凡是界限超出已知可行解值那些子集不再做进一步分支。这样,解的许多子集(即搜索树上的许多结点)就可以不予考虑了,从而缩小了搜索范围。这一过程一直进行到找出可行解为止,该可行解的值不大于任何子集的界限。因此这种算法一般可以求得最优解。
      (4)动态规划法:基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。若用分治法来解这类问题,则分解得到的子问题数目太多,有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,这样就可以避免大量的重复计算,节省时间。我们可以用一个表来记录所有已解的子问题的答案。
      (5)贪心算法:贪心算法的特点是一步一步地进行,常以当前情况为基础根据某个优化测度作最优选择,而不考虑各种可能的整体情况,省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪心算法采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择,就将所求问题简化为一个规模更小的子问题,通过每一步贪心选择,可得到问题的一个最优解。虽然每一步上都要保证能获得局部最优解,但由此产生的全局解有时不一定是最优的,所以贪心算法不要回溯。

    3、 DeepMind用神经网络求解MIP

      混合整数规划(MIP)是一类 NP 困难问题,来自 DeepMind、谷歌的一项研究表明,用神经网络与机器学习方法可以解决混合整数规划问题。
      混合整数规划(Mixed Integer Program, MIP)是一类 NP 困难问题,旨在最小化受限于线性约束的线性目标,其中部分或所有变量被约束为整数值。混合整数规划的形式如下:
    在这里插入图片描述
      MIP 已经在产能规划、资源分配和装箱等一系列问题中得到广泛应用。人们在研究和工程上的大量努力也研发出了 SCIP、CPLEX、Gurobi 和 Xpress 等实用的求解器。这些求解器使用复杂的启发式算法来指导求解 MIP 的搜索过程,并且给定应用上求解器的性能主要依赖于启发式算法适配应用的程度。
      DeepMind、谷歌的研究者展示了机器学习可以用于从 MIP 实例数据集自动构建有效的启发式算法。该研究证明,机器学习可以构建针对给定数据集的启发式算法,其性能显著优于 MIP 求解器中使用的经典算法,特别是具有 SOTA 性能的非商业求解器 SCIP 7.0.1。该研究将机器学习应用于 MIP 求解器的两个关键子任务:(1)输出对满足约束的所有变量的赋值(如果存在此类赋值)(2)证明变量赋值与最优赋值之间的目标值差距边界。
       源代码并未公开,论文可自行在以下地址查看。
    在这里插入图片描述

    展开全文
  • 基于文化框架的随机粒子群优化算法.pdf
  • 科研、工程和管理中的很多问题都可以转化为优化问题。应用于这些优化问题的各种方法...基于奥卡姆剃刀原则,摒弃了复杂的操作算子的概率调优规则,用一个简单的框架来组织核心算子,从而达到许多组合算法的搜索效果。
  • 随机方差减少算法:深度学习的 SVRG 和 SAGA 优化算法的实现。 随机梯度 (SGD) 是通过神经网络进行反向传播最常用的优化算法,因为它的成本比梯度下降要小。 但是,它的收敛速度非常慢,并且需要降低学习率才能收敛...
  • 一个框架看懂优化算法 一一个框架看懂优化算法 说到优化算法入门级必从 SGD 学起老司机则会告诉你更好的还有 AdaGrad / AdaDelta 或者直接无脑用 Adam 可是看看学术界的最新 paper却发现一众大神还在 用着入门级的 ...
  • 基于Hadoop框架的大数据集连接优化算法
  • 大数据-算法-批量数据优化处理框架的设计和实现.pdf
  • 基于直觉模糊Memetic框架的双粒子群混合优化算法.pdf
  • 框架局部算法的分布式约束优化问题中。 关于 该软件包提供了开发迭代逼近最佳响应算法求解DCOPs和一些算法实现了模块化的框架。 [1] DSA-A(分布式随机算法,变体A)[1,3] DSAN(分布式模拟退火)[2] JSFP-I...
  • 提出了随机粒子群优化算法(rPSO),并将其与标准PSO纳入到文化算法(CA)框架中,建立了基于文化框架的随机粒子群优化算法(CA-rPSO)。该算法以rPSO作为信念空间的进化算法,以PSO作为群体空间的进化算法,形成了两者...
  • 针对混沌蚂蚁群优化算法(CASO) 容易陷入局部极值和精度低的缺陷, 从认知学角度进行分析, 将创造性思维(CT) 引入CASO 算法, 提出了一种带创造性思维的混沌蚂蚁群优化算法(CTCASO). 基于CT 过程的“四阶段”模型, 构建...
  • 优化算法综述

    千次阅读 2021-06-30 21:21:03
    遗传算法(GA)、帝国竞争算法(ICA)、 粒子群优化(PSO) 局部优化 模拟退火(SA)、贪婪算法(Greedy)、 邻域搜索(NS) 是否精确算法 精确算法 线性规划(LP)、分支定界法 ...

    优化算法综述

    依据分类具体算法
    1全局优化 遗传算法(GA)、帝国竞争算法(ICA)、 粒子群优化(PSO)
    局部优化 模拟退火(SA)、贪婪算法(Greedy)、 邻域搜索(NS)
    2精确算法线性规划(LP)、分支定界法(BB)
    模拟进化算法v
    群体仿生类算法、又称为群体智能优化算法GA、PSO
    数学规划方法: 动态规划(DP)、线性规划、整数规划、 混合整数规划、 分支定界法、 割平面法
    v
    v
    启发式算法(Heuristic Algorithms)v
    元启发式算法(Meta-Heuristic Algorithms)v

    数学规划法

    数学规划法:通常将多目标问题转化为单目标问题来解决。

    精确算法(exact algorithm)

    精确算法:通常将待解决的优化问题转换为数学规划问题,进行精确求解。如:分支定界法BB)。

    • 优点:在问题规模较小时,精确算法能在合理的时间内找到问题的最优解
    • 缺点:但当问题规模较大时(是NP-Hard问题),精确算法的计算复杂度高,求解时间呈指数级增长,不能容忍(指数爆炸)。

    启发式 VS. 元启发式

    问题描述:现实中很多问题的优化都可以建模为基于序列的组合优化,如旅行商问题(TSP)、排产问题、各类资源分配问题等。寻找最优序列的问题是NP难问题(NP-Hard问题)(其解空间为n!)。

    解决这类问题常用的方法有两种:

    • (1)一种方法是启发式算法,启发式算法是基于问题本身的规则得到较好的可行解,本质是贪心算法(贪婪算法,greedy)。这种方法速度较快,但因与问题本身联系紧密(problem specific, problem dependent),导致其通用性较差。
    • (2)另一种方法是元启发式算法,例如遗传算法、禁忌搜索算法、蚁群算法、模拟退火算法等都是元启发式算法。这类方法从生物进化、物理、化学等过程中受到启发,得到一种解空间的搜索策略,因其搜索策略独立于问题本身(problem independent),因此通用性强。元启发式这类算法有两个最本质的操作:①选择操作(从当前种群中选出优秀的个体,选择的策略有精英保留、轮盘赌、锦标赛等);②改变操作(如交叉、变异、灾变操作等,它们本质上都是从一个可行解改变为另一个可行解,用来扩大搜索范围,避免陷入局部最优)。(详见:元启发式算法常用操作详解:https://bbs.huaweicloud.com/blogs/195717)

    启发式算法

    启发式策略(heuristic)是一类在求解某个具体问题时,在可以接受的时间和空间内能给出其可行解(或近优解),但又不保证求得最优解(以及可行解与最优解的偏离)的策略的总称。
    许多启发式算法是相当特殊的,它依赖于某个特定问题。启发式策略在一个寻求最优解的过程中能够根据个体或者全局的经验来改变其搜索路径,当寻求问题的最优解变得不可能或者很难完成时(e.g. NP-C问题),启发式策略就是一个高效的获得可行解(即近优解)的办法。

    启发式算法包括:包括构造型方法、局部搜索算法、松弛方法、解空间缩减算法、贪婪策略、随机化贪婪策略、近邻策略、最大饱和度策略等。

    元启发式算法

    元启发式策略(Meta-heuristic)则不同,元启发式策略通常是一个通用的启发式策略,它们通常不借助于某种问题的特有条件,从而能够运用于更广泛的方面元启发式是启发式策略的增强改进版,它是随机算法与局部搜索算法相结合的产物。“元”可以理解为一个哲学概念,大概是“事物的本原”。

    元启发式策略通常会对搜索过程提出一些要求,然后按照这些要求实现的启发式算法便被称为元启发式算法。许多元启发式算法都从自然界的一些随机现象取得灵感(e.g. 模拟退火、遗传算法、粒子群算法)。现在元启发式算法的重要研究方向在于防止搜索过早得陷入局部最优,已经有很多人做了相应的工作,例如禁忌搜索(tabu)和非改进转移(模拟退火)。

    元启发式算法是相对于最优化算法提出来的,一个问题的最优化算法可以求得该问题的最优解,而元启发式算法是一个基于直观或经验构造的算法,它可以在可接受的花费(指计算时间和空间)下给出问题的一个可行解(近优解),并且该可行解与最优解的偏离程度不一定可以事先预计。

    元启发式算法(Meta-heuristic)是基于计算智能的机制求解复杂优化问题最优解满意解(近优解)的方法,有时也被称为智能优化算法(Intelligent optimization algorithm),智能优化通过对生物、物理、化学、社会、艺术等系统或领域中相关行为、功能、经验、规则、作用机理的认识,揭示优化算法的设计原理,在特定问题特征的引导下提炼相应的特征模型,设计智能化的迭代搜索型优化算法。

    常见的Meta-Heuristic Algorithms(有基于个体基于群体两类):
    一、基于个体(Single solution-based heuristics)
    1、模拟退火(Simulated Annealing,SA)
    2、禁忌搜索(Tabu Search,TS)
    3、变邻域搜索(Variable Neighborhood Search)
    4、自适应大规模领域搜索(Adaptive Large Neighborhood Search)
    二、基于群体(Population-based heuristics)
    1、遗传算法(Genetic Algorithm,GA)
    2、蚁群优化算法(Ant Colony Optimization,ACO)
    3、粒子群优化算法(Particle Swarm Optimization,PSO)
    4、差分进化算法(Differential Evolution, DE)
    4、人工蜂群算法(ABC)、人工鱼群算法、狼群算法等
    5、人工神经网络算法(ANN)

    另外还有:免疫算法、蛙跳算法、帝国竞争算法(Imperialist Competitive Algorithm,ICA)、和声搜索算法、分布估计算法、Memetic算法、文化算法、灰狼优化算法、人工免疫算法、进化规划、进化策略、候鸟优化算法、布谷鸟搜索算法、花朵授粉算法、引力搜索算法、化学反应优化算法、头脑风暴优化算法(Brain Storm Optimization Algorithm,BSO)等等。

    附:元启发式算法时间表(部分)
    在这里插入图片描述

    What is the difference between heuristics and meta-heuristics?

    • 启发式算法和元启发式算法,一般都是用来解决NP-H问题,目的是求得组合优化问题的近优解可行解满意解),但不一定是最优解。【它们和最优化算法相对应,最优化算法是用来求得问题的最优解的。】
    • 启发式算法是 problem dependent(依赖于问题的,与问题有关)或者叫 problem specific(面向特定问题的,与特定问题有关),故适应面窄; 而元启发式算法是problem independent(与问题无关的),元启发法是与问题无关的技术,可以应用于广泛的问题适用范围广
    • 启发式方法利用问题相关信息来找到特定问题的"足够好"的解决方案,根据给定问题制定启发式规则,故与该问题特性有关;而元启发式方法则像设计模式一样,是一般的算法思想,可以应用于各种各样的问题,与问题无关
    • 复杂性方面,启发式算法简单,就是用简单策略(如:贪婪策略、随机化贪婪策略、近邻策略、最大饱和度策略)构造可行集的过程。而元启发式则是一种高层次的多个算法模块的聚合算法。

    有段英文可以读读,理解一下:
    A locally optimal solution is better than all neighbouring solutions. A globally optimal solution is better than all solutions in the search space. A neighbourhood is a set of solutions that can be reached from the current solution by a simple operator. A neighbourhood is a subset of the search space. (局部最优解、全局最优解与邻域的概念)
    A heuristic is a rule of thumb method derived from human intuitions. For example, we can use the nearest neighbour heuristic to solve the TSP problem and use the maximal saturation degree heuristic to solve the graph colouring problem.(其次,我们可以利用启发式算法搜索并得到一个局部最优解(不保证是全局最优解))
    Meta-heuristics are methods that orchestrate an interaction between local improvement procedures and higher-level strategies to create a process capable of escaping from the local optima and performing a robust search in the solution space. Single-point meta-heuristics include Simulated Annealing, Tabu Search, and Variable Neighbourhood Search. Population-based meta-heuristics include Genetic Algorithm, Ant Colony Optimization, and Particle Swarm Optimization.(最后,我们可以利用元启发式算法更好地探索解空间,从而避免算法陷入局部最优)

    多目标智能优化算法

    多目标进化算法(Multi-Objective Evolutionary Algorithm,MOEA),如:增强多目标灰狼优化算法、多目标粒子群优化算法多目标遗传算法NSGA-Ⅱ算法(即带有精英保留策略的快速非支配多目标优化算法,是一种基于Pareto最优解的多目标优化算法,是多目标遗传算法的一种)。

    多目标优化算法,它主要针对同时优化多个目标(两个及两个以上)的优化问题,这方面比较经典的算法有NSGAII算法、MOEA/D算法以及人工免疫算法等。这部分内容的介绍已经在博客《[Evolutionary Algorithm] 进化算法简介》进行了概要式的介绍,有兴趣的博友可以进行参考(2015.12.13)-Poll的笔记。

    模拟进化算法与传统的精确算法(确定性算法)的区别

    1. 模拟进化算法的作用对象是由多个可行解组成的集合(种群),而非单个可行解
    2. 模拟进化算法只利用目标函数(或适应度函数)的适应值信息(fitness value),而无需使用梯度等其它辅助信息;
    3. 模拟进化算法利用概率机制非确定性迭代过程描述。
    4. 正是这些有别于确定型方法的特征,决定了模拟进化算法应用的广泛性、描述的简单性、本质上的并行性及良好的鲁棒性。

    优化算法分类

    1. 启发式优化算法:一个基于直观或经验构造的算法,在可接受的花费(指计算时间和空间)下给出待解决组合优化问题每一个实例的一个可行解,该可行解与最优解的偏离程度不一定事先可以预计.意思就是说,启发式算法是根据经验或者某些规则来解决问题,它求得的问题的解不一定是最优解,很有可能是近似解(或近优解)。这个解与最优解近似到什么程度,是不能确定的。相对于启发式算法,最优化算法或者精确算法(比如说分支定界法、动态规划法等则能求得最优解)。而元启发式优化算法(Meta-heuristic Algo.)是启发式算法中比较通用的一种高级一点的算法,主要有遗传算法、禁忌搜索算法、模拟退火算法、蚁群算法、粒子群算法、变邻域搜索算法、人工神经网络、人工免疫算法、差分进化算法等。这些算法可以在合理的计算资源条件下给出较高质量的解(最优解或近优解)。
    2. 仿生算法:基于仿生学的算法,是一类模拟自然生物进化或者群体社会行为的随机搜索方法的统称.由于这些算法求解时不依赖于梯度信息,故其应用范围较广,特别适用于传统方法难以解决的大规模复杂优化问题.主要有:遗传算法、人工神经网络、蚁群算法、蛙跳算法、粒子群优化算法等.这些算法均是模仿生物进化、神经网络系统、蚂蚁寻路、鸟群觅食等生物行为,故叫仿生算法
    3. 智能计算:也称为计算智能,群体智能算法。包括遗传算法、模拟退火算法、禁忌搜索算法、进化算法、蚁群算法、人工鱼群算法,粒子群算法、混合智能算法、免疫算法、神经网络、机器学习、生物计算、DNA计算、量子计算、模糊逻辑、模式识别、知识发现、数据挖掘等.智能计算是以数据为基础,通过训练建立联系,然后进行问题求解.

    所以说,你接触的很多算法,既是仿生算法,又是启发式算法,又是智能算法,这都对!只是分类方法不同而已。

    算法介绍

    帝国竞争算法(Imperialist Competitive Algorithm,ICA)

    帝国竞争算法(ICA)是Atashpaz-Gargari和Lucas于2007年提出的一种基于帝国主义殖民竞争机制的进化算法,属于社会启发的随机优化搜索方法。目前,ICA已被成功应用于多种优化问题中,如调度问题、分类问题和机械设计问题等。

    帝国主义竞争算法,借鉴了人类历史上政治社会殖民阶段帝国主义国家之间的竞争、占领、吞并殖民殖民地国家从而成为帝国国家的演化,是一种全局性的优化算法。该算法把所有初始化的个体都称作国家,按照国家势力分成帝国主义国家及殖民地两种,前者优势大于后者。

    其实,从另一个角度来看,ICA可以被认为是遗传算法(GA)的社会对应物。ICA是基于人类社会进化的过程,而GA是基于物种的生物进化过程。二者其实有异曲同工之妙。

    不过话说回来,大多数群体仿生类算法都有异曲同工之妙。

    分支定界法(Branch and Bound, BB)

    For instance, since the space of possible solutions is still too vast, a branch and bound type algorithm is proposed to further decimate the number of potential solutions to evaluate.
    例如,由于可行解的参数空间很大,一种分支限界算法被用来减少需要考察的可行解的数目。

    Branch and bound (BB or B&B) is an algorithm design paradigm for discrete and combinatorial optimization problems, as well as general real valued problems. A branch-and-bound algorithm consists of a systematic enumeration of candidate solutions by means of state space search: the set of candidate solutions is thought of as forming a rooted tree with the full set at the root. The algorithm explores branches of this tree, which represent subsets of the solution set. Before enumerating the candidate solutions of a branch, the branch is checked against upper and lower estimated bounds on the optimal solution, and is discarded if it cannot produce a better solution than the best one found so far by the algorithm.

    NSGA-Ⅱ算法

    NSGA(Non-dominated Sorting Genetic Algorithm,非支配排序遗传算法)、NSGA-II(带精英策略的快速非支配排序遗传算法),都是基于遗传算法的多目标优化算法,是基于pareto最优解讨论的多目标优化。

    NSGA-Ⅱ算法,即带有精英保留策略的快速非支配多目标优化算法,是一种基于Pareto最优解的多目标优化算法。
    NSGA-Ⅱ算法是进化算法中的一种,进化算法是在遗传算法的基础上改进而来的,所以,你得先弄懂遗传算法是什么。

    NSGA-Ⅱ是最流行的多目标遗传算法之一,它降低了非劣排序遗传算法的复杂性,具有运行速度快,解集的收敛性好的优点,成为其他多目标优化算法性能的基准。

    NSGA-Ⅱ算法是 Srinivas 和 Deb 于 2000 年在 NSGA 的基础上提出的,它比 NSGA算法更加优越:它采用了快速非支配排序算法,计算复杂度比 NSGA 大大的降低;采用了拥挤度和拥挤度比较算子,代替了需要指定的共享半径 shareQ,并在快速排序后的同级比较中作为胜出标准,使准 Pareto 域中的个体能扩展到整个 Pareto 域,并均匀分布,保持了种群的多样性;引入了精英策略,扩大了采样空间,防止最佳个体的丢失,提高了算法的运算速度和鲁棒性。

    NSGA-Ⅱ就是在第一代非支配排序遗传算法的基础上改进而来,其改进主要是针对如上所述的三个方面:

    1. 提出了快速非支配排序算法,一方面降低了计算的复杂度,另一方面它将父代种群跟子代种群进行合并,使得下一代的种群从双倍的空间中进行选取,从而保留了最为优秀的所有个体;
    2. 引进精英策略,保证某些优良的种群个体在进化过程中不会被丢弃,从而提高了优化结果的精度;
    3. 采用拥挤度和拥挤度比较算子,不但克服了NSGA中需要人为指定共享参数的缺陷,而且将其作为种群中个体间的比较标准,使得准Pareto域中的个体能均匀地扩展到整个Pareto域,保证了种群的多样性。

    这个算法是本人接触科研学习实现的第一个算法,因此想在这里和大家分享一下心得。 讲解的很详细,读个大概,有个思路和印象即可,不必深究。
    site:https://blog.csdn.net/qq_40434430/article/details/82876572/

    遗传算法(Genetic Algorithm, GA)

    遗传算法(Genetic Algorithm,简称GA)是一种最基本的进化算法,它是模拟达尔文生物进化理论的一种优化模型,最早由J.Holland教授于1975年提出。

    遗传算法中种群分每个个体都是解空间上的一个可行解,通过模拟生物的进化过程,从而在解空间内搜索最优解。

    禁忌搜索算法(Tabu Search,TS)

    遗传算法是具有全局搜索能力的算法,但是传统遗传算法求解调度问题并不是很成功,主要原因在于它的局部搜索能力较差,且容易早熟收敛。而禁忌搜索(Tabu Search, TS)是一种优秀的局部搜索算法。因此,可以结合遗传算法(GA)和禁忌搜索算法(TS)两者的优点,将“适者生存”的遗传准则嵌入到多起点的禁忌搜索算法中,构成混合遗传禁忌搜索算法(GATS)。

    由于遗传算法和禁忌搜索算法具有互补的特性,因此混合遗传禁忌搜索算法GATS)在性能上能够超越它们单独使用时的性能。

    文化基因算法(Memetic Algorithm,MA)

    文化基因(Meme)的概念是由Hawkins于1976年提出的,Pablo Moscato于1989年提出了Memetic Algorithm。Memetic Algorithm,是基于群体的计算智能方法与局部搜索相结合的一类算法的总称。文化基因算法的简单介绍。

    在这里插入图片描述

    文化基因算法(Memetic Algorithm,简称MA),也被称为是“密母算法”(Meme),它是由Moscato在1989年提出的。文化基因算法MA是一种基于种群的全局搜索和基于个体的局部启发式搜索的结合体,它的本质可以理解为:

    MA= GA + Local Search

    即MA算法实质上是为遗传算法(全局搜索算法)加上一个局部搜索(Local Search)算子。局部搜索算子可以根据不同的策略进行设计,比如常用的爬山机制、模拟退火、贪婪机制、禁忌搜索等。

    在这里插入图片描述
    在这里插入图片描述
    Pablo Moscato认为:在遗传算法(GA)中,变异操作可以看作是含有一定噪声的爬山搜索,实际上模拟遗传编码和自然选择的过程不应包含变异操作,因为在文化进化的过程中,在众多的随机变化步骤中得到一个正确的、可提高整体性能的一步进展是非常困难的,只有此领域的拥有足够的专业知识的精通者们,才有可能创造新的进展,并且这样的事情发生的频率是很低的。 因此,文化基因的传播过程应是严格复制的,若要发生变异,那么每一步的变异都需要有大量的专业知识支撑,而每一步的变异都应带来进展而不是混乱,这就是为什么我们观察到的文化进化速度要比生物进化速度快得多的原因。 对应于模拟生物进化过程的遗传算法,Moscato提出了模拟文化进化过程的文化基因算法,文化基因算法用局部启发式搜索来模拟由大量专业知识支撑的变异过程。因此说,文化基因算法是一种基于种群的全局搜索和基于个体的局部启发式搜索的结合体

    文化基因算法的这种全局搜索和局部搜索的结合机制,使其搜索效率在某些问题领域比传统遗传算法快几个数量级,可应用于广泛的问题领域并得到满意的结果。 很多人将文化基因算法看作混合遗传算法、 遗传局部搜索或是拉马克式进化算法。实际上,文化基因算法提出的只是一种框架、 是一个概念在这个框架下,采用不同的搜索策略可以构成不同的文化基因算法。如全局搜索策略可以采用遗传算法、 进化策略、 进化规划等,局部搜索策略可以采用爬山搜索、模拟退火、贪婪算法、禁忌搜索、导引式局部搜索等。 这种全局与局部的混合搜索机制显然要比单纯在普通个体间搜索的进化效率高得多

    机器学习中的最优化模型

    我们每个人都会在我们的生活或者工作中遇到各种各样的最优化问题,比如每个企业和个人都要考虑的一个问题“在一定成本下,如何使利润最大化”等。最优化方法是一种数学方法,它是研究在给定约束之下如何寻求某些因素(的量),以使某一(或某些)指标达到最优的一些学科的总称。随着学习的深入,博主越来越发现最优化方法的重要性,学习和工作中遇到的大多问题都可以建模成一种最优化模型进行求解,比如我们现在学习的机器学习算法,大部分的机器学习算法的本质都是建立优化模型,通过最优化方法对目标函数(或损失函数)进行优化,从而训练出最好的模型。常见的最优化方法有梯度下降法牛顿法和拟牛顿法共轭梯度法最速下降法等等。

    梯度下降法(Gradient Descent)

    牛顿法和拟牛顿法(Newton’s method & Quasi-Newton Methods)

    共轭梯度法(Conjugate Gradient)

    拉格朗日乘数法(Lagrange Multiplier Method)

    详见:[Math & Algorithm] 拉格朗日乘数法

    展开全文
  • 采用该优化算法分别对一单跨8层框架和双跨5层框架结构进行离散变量的质量优化设计,并与细菌觅食算法的计算结果进行了比较.计算结果表明改进的细菌觅食算法应用在结构优化中具有较好的收敛速度和精度,可应用于工程...
  • 最近需要用到遗传算法优化一些东西,最初是打算直接基于某些算法实现一个简单的函数来优化,但是感觉单纯写个非通用的函数运行后期改进算子或者别人使用起来都会带来困难,同时遗传算法基本概念和运行流程相对固定...
  • 基于包簇框架的云计算能耗优化算法.pdf
  • 智能优化算法:海鸥优化算法-附代码

    万次阅读 多人点赞 2020-07-23 14:24:01
    2019智能算法:海鸥优化算法-附代码 摘要:本文简单介绍智能优化算法-海鸥优化算法 1.原理 海鸥是遍布全球的海鸟,海鸥种类繁多且大小和身长各不相同。 海鸥是杂食动物,吃昆虫、鱼、爬行动物、两栖动物和蚯蚓等。 ...
  • 贝叶斯框架下去雾算法优化,诸杏子,苏红旗,近年来,由于雾霾天气的频繁出现,图像的户外视觉系统受到了严重的影响,导致图像质量严重退化,影响了图像的特征判断和识别。在
  • 基于MapReduce框架的并行蚁群优化聚类算法.pdf
  • 针对多维背包问题(MKP) NP-hard、约束强的特点, 提出一种高效的蚁群-拉格朗日松弛(LR) 混合优化算法. 该算法以蚁群优化(ACO) 为基本框架, 并基于LR 对偶信息定义了一种MKP效用指标. ACO使得整体算法具有全局搜索能力...
  • 针对确定性全局优化算法极高的计算复杂度以及随机性全局优化算法可靠性较低的问题, 在群体进化算法框架下, 结合抽象凸理论, 提出一种基于抽象凸下界估计的群体全局优化算法. 首先, 对整个初始群体构建抽象凸下界估计...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 260,235
精华内容 104,094
关键字:

优化算法的框架