精华内容
下载资源
问答
  • 进化计算

    千次阅读 2020-04-28 03:05:49
    进化算法 进化算法,也被成为是演化算法...与传统的基于微积分的方法和穷举方法等优化算法相比,进化计算是一种成熟的具有高鲁棒性和广泛适用性的全局优化方法,具有自组织、自适应、自学习的特...

    进化算法
    进化算法,也被成为是演化算法(evolutionaryalgorithms,简称EAs),它不是一个具体的算法,而是一个“算法簇”。进化算法产生的灵感借鉴了大自然中生物的进化操作,它一般包括基因编码,种群初始化,交叉变异算子,经营保留机制等基本操作。与传统的基于微积分的方法和穷举方法等优化算法相比,进化计算是一种成熟的具有高鲁棒性和广泛适用性的全局优化方法,具有自组织、自适应、自学习的特性,能够不受问题性质的限制,有效地处理传统优化算法难以解决的复杂问题(比如NP难优化问题)。

    1. 选择阶段
      选择的过程主要是为选出优质的后代用作下一次的迭代。在个体集合中,每个个体有自己被选中的概率,下面介绍几种选择的方法
      通常来说我们选用轮盘赌的方式。每个个体通过适应度函数得到他们的适应度的值,然后得到在所有个体中被选中的百分比,放入轮盘中,如下图所示,11号个体就没有可能被选中。
      第二张图是我们常用的线段抽样的方法,每个个体的线段长度和各自的适应度的值有关,基本概念和轮盘赌类似。在这里插入图片描述
      第三种是local选择,在这个选择方式中,每个个体被限定在特定的结构内,彼此相连,这个结构可以是全封闭的环形,三角形等。有一维的,二维的,也有三维的。如下图所示。每个population之间隔有一定的距离,较小的团体之间隔离的距离越大。同时邻居的大小决定了传播的速度。这也就意味着人多的团体可能更快的陷入局部最小值问题。所以我们通常对较小的社区使用本地选择。还有比赛选择等

    2. 在选择完成后我们就需要重组和交叉。
      在上面选择出优秀的个体后将它们结合,形成新的个体,这个个体将整合父母包含的信息。重组的方式有很多种,离散重组。先随机选择两个父代个体,然后将其分量进行随机交换,构成子代新个体的各个分量,从而得出如下新个体。
      第二个是中值重组。这种重组方式也是先随机选择两个父代个体,然后将父代个体各分量的平均值作为子代新个体的分量,构成的新个体为。最后混杂重组。这种重组方式的特点在于父代个体的选择上。混杂重组时先随机选择一个固定的父代个体,然后针对子代个体每个分量再从父代群体中随机选择第二个父代个体。也就是说,第二个父代个体是经常变化的。至于父代两个个体的组合方式,既可以采用离散方式,也可以来用中值方式,甚至可以把中值重组中的1/2改为[0,1]之间的任一权值。

    3. 变异就是在每个分量上面加上零均值、某一方差的高斯分布的变化产生新的个体。这个某一方差就是变异程度。变异程度并不是一直不变化的,算法开始的时候变异程度比较大,当接近收敛后,变异程度会开始减小。

    这结束一个轮回然后重新开始选择步骤。

    3.2 遗传算法
    遗传操作是模拟生物基因的操作,他的任务就是根据个体适应度对其施加一定的操作,从而实现优胜劣汰的进化过程.从优化搜索的角度来看,遗传操作可以使问题的解逐代优化,逼近最优解,遗传操作包括以下三个基本遗传算子:选择、交叉、变异.选择和交叉基本上完成了遗传算法的大部分搜索功能,变异增加了遗传算法找到最优解的能力.

    3.1、选择

    选择是指从群体中选择优良个体并淘汰劣质个体的操作.它建立在适应度评估的基础上.适应度越大的个体,被选中上的可能性就越大,他的“子孙”在下一代中的个数就越多,选择出来的个体就被放入配对库中.目前常用的选择方法有轮赌盘方法、最佳个体保留法、期望值法、排序选择法、竞争法、线性标准化法.

    3.2、交叉

    交叉就是指把两个父代个体的部分结构加以替换重组而生成新的个体的操作,交叉的目的是为了在下一代产生新的个体,通过交叉操作,遗传算法的搜索能力得到了飞跃性的提高.交叉是遗传算法获取优良个体的重要手段.交叉操作是按照一定的交叉概率在匹配库中随机的选取两个个体进行的,交叉位置也是随机的,交叉概率一般取得很大,为0.6~0.9.
    在这里插入图片描述

    3.3、变异

    变异就是以很小的变异概率Pm随机地改变种群中个体的某些基因的值,变异操作的基本过程是:产生一个[0,1]之间的随机数rand,如果rand<Pm,则进行变异操作.变异操作本身是一种局部随机搜索,与选择、交叉算子结合在一起,能够避免由于选择和交叉算子而引起的某些信息永久性丢失,保证了遗传算法的有效性,使遗传算法具有了局部随机搜索能力,同时使得遗传算法能够保持群体的多样性,以防出现未成熟收敛.在变异操作中,变异概率不宜取得过大,如果Pm>0.5,遗传算法就退化为了随机搜索.
    在这里插入图片描述

    另一个关键点基因编程,基因编程与遗传算法有明显的不同,遗传算法结局问题是会产生一个字符串作为染色体,而基因编程则是产生一个结局方案的计算机程序。基因编程结局问题出要分为四个步骤, 首先初始化随机种群和确定问题。其次运行种群里的每一个程序,通过适应度函数评判各自解决问题的效果。然后创建新的程序种群。这个新的种群包括了在前面表现好的程序,变异以后的程序以及交叉后的程序。最后再找到新种群里最好的程序作为输出。那么基因编程里的交叉和变异算子也与遗传算法里的有所不同。在传统的遗传算法里我们是将父母染色体进行交叉编程一个新的染色体,但在基因编程里我们的两个父母程序可以通过交叉产出两个新的程序。如下图所示。相同的变异算子也有两种可能的突变,对单个程序可能会产生单个终端的突变也有可能退一个子功能的突变。

    展开全文
  • 进化计算课件

    2015-09-18 19:14:26
    很好的进化计算课件,适合入门研究者,包括进化算法,遗传算法
  • 基于进化计算的兴趣建模
  • 进化计算-进化算法

    千次阅读 2019-11-18 19:52:18
    从今天开始,将进入另一类智能优化算法——进化计算(Evolutionary Computation),这些算法更多的是基于达尔文的《进化论》相关理论进行算法的设计。进化算法(Evolutionary Algorithms,EAs)通常包括遗传算法...

    在这里插入图片描述

    获取更多资讯,赶快关注上面的公众号吧!

    第十七章 进化算法

    从今天开始,将进入另一类智能优化算法——进化计算(Evolutionary Computation),这些算法更多的是基于达尔文的《进化论》相关理论进行算法的设计。进化算法(Evolutionary Algorithms,EAs)通常包括遗传算法(Genetic Algorithms,GA)遗传规划(Genetic Programming,GP)进化策略(Evolution Strategies)进化规划(Evolutionary Programming)。由于这些算法都是借鉴生物界的进化与遗传的机理,相对容易理解和实现,因此常用于解决复杂的工程技术问题。在介绍进化算法的用途和概念之前,先了解一下生物学中进化与遗传的概念。

    17.1 生物的进化与遗传

    17.1.1 生物的进化

    地球上的生物都是经过长期进化而形成的,根据达尔文的自然选择学说,地球上的生物具有很强的繁殖能力,在繁殖过程中,大多数生物通过遗传,使物种保持相似的后代;部分生物由于变异,后代会出现明显差别,甚至会形成新的物种。随着生物不断繁殖,数量不断增加,而自然界中生物赖以生存的资源却是有限的,因此生物间存在激烈的竞争以求生存,更能适应环境的个体得以生存,而不适应者就会被淘汰。
    进化算法就是借用生物进化的规律,通过繁殖-竞争-再繁殖-再竞争,实现优胜劣汰,一步一步地逼近问题的最优解,进化算法中的“进化”二字就是由此而来。

    17.1.2 遗传物质

    绝大多数生物的遗传物质是DNA(脱氧核糖核酸),DNA一种高分子化合物,可以传递遗传信息,组成DNA的基本单位是脱氧核苷酸,由于细胞里的DNA大部分在染色体上,因此遗传物质的主要载体就是染色体。
    控制生物遗传的物质单元称为基因,它是有遗传效应的DNA片段。每个基因含有成百上千个脱氧核苷酸。它们在染色体上是线性排列的,这种排列顺序就代表了遗传信息。
    在进化算法中,为了形成具有遗传物质的染色体,就用不同字符自称的字符串表达所研究的问题,这种字符串就相当于染色体,其上的字符就相当于基因。

    17.1.3 遗传方式

    生物的主要遗传方式是复制。遗传过程中,父代的遗传物质DNA分子被复制到子代,以此传递遗传信息。
    生物在遗传过程中还会发生变异。变异的方式有3种:基因重组、基因突变和染色体变异。基因重组是重新组合控制物种性状的基因、基因突变是指基因分子结构的改变。染色体变异是指染色体在结构或数量上的变化。
    进化算法中,仿效生物的遗传方式,主要有复制、交叉、变异这3中遗传操作。

    17.2 进化算法应用

    在科学探索自然规律和工程制造实用产品的过程中,往往会遇到许多问题,优化问题便是其中之一。
    对于优化问题,希望在变量的定义域内找到最优解,给定笛卡尔三维坐标系下的可微实值函数f(x,y,z),其梯度为f=(fxi,fyj,fzk) \nabla f=\left(\frac{\partial f}{\partial x} \mathbf{i}, \frac{\partial f}{\partial y} \mathbf{j}, \frac{\partial f}{\partial z} \mathbf{k}\right) ,其中ijk为三个方向上的单位向量。 f\nabla f的方向是函数f上升最快的方向,其模衡量上升快慢的程度。因此优化问题看起来很简单,可以从任意初始点开始,通过梯度导引搜索,直到找到梯度接近0的点。

    不幸的是,这只适用于某些类型的问题。对于组合优化,没有微分的定义;对于多目标优化,我们面对的是一个向量函数f,通常在定义域中没有一个点的多个目标值都优于其他点;对于约束优化,沿梯度搜索可能收敛于一个违反某些约束的解。即使在可微无约束优化中,梯度也可能不起作用。让我们以Griewank函数为例:

    minf(x1,x2)=x12+x224000cos(x1)cos(x22)+1(1) \min f({x_1},{x_2}) = \frac{{{x_1}^2 + {x_2}^2}}{{4000}} - \cos ({x_1})\cos \left( {\frac{{{x_2}}}{{\sqrt 2 }}} \right) + 1\tag 1

    很容易发现,该函数的全局最优解是x=y=0。在定义域(-30≤x1,x2≤30)内该函数的图形如图1所示。

    该函数存在非常多的局部最优解(即多峰),以至于通过随机生成初始解的梯度方法会很大概率的陷入其中。

    约束优化、多峰优化、多目标优化和组合优化这四类问题为优化的核心,也是运筹学领域的热门主题。研究人员提出了许多解决这些问题的方法,其中,进化算法具有独特的性能,受到越来越多的关注。

    在这里插入图片描述

    图1 Griewank函数

    17.3 进化算法特点

    物种的自然进化可以看作是一个学习如何适应环境和优化物种适应性的过程。所以在设计优化或学习算法时,可以模仿现代遗传学“适者生存”的观点。

    EAs是用于任务优化或学习的具有进化能力的算法,主要有三个特点:

    1. 基于种群:EAs对一组称为种群的解进行操作,从而以并行的方式优化或学习问题。
    2. 面向适应度:种群中的每个解称为个体,每个个体有自己的基因表达,称为编码,性能评估为其适应度值。EAs更偏好于选择适应度值更优的个体,这是算法优化和收敛的基础。
    3. 变异驱动:个体将经历许多变异操作来模拟遗传基因的变化,这是搜索解空间的基础。

    17.4 结论

    遗传算法是进化算法中较为简单且应用最广泛的算法,在生产调度领域也有很多学术研究,下一章内容将以更加生动有趣的图解遗传算法来介绍选择、交叉、变异等遗传算法基本操作,从而帮助不太了解遗传算法的读者快速掌握。

    展开全文
  • 针对目前交互式进化计算存在的局部搜索能力不强、效率低下等问题, 将分层的思想引入交互式进化计算, 提出了分层交互式进化计算. 给出了算法实施的关键问题, 分析了算法的效率. 将其应用于服装设计, 通过算例...
  • 分布式进化计算 这是用于并行和分布式进化计算(PDEC)的不断增长的论文清单。 系统搜索 出版物 起始年份 EC与PDEC 搜索者 自然 2015年 欧共体 冯明扬,张有奎,段其琦 研究支援 深圳NSF研究项目(从2021年到2023年...
  • 计算智能3--进化计算

    千次阅读 2018-04-26 10:34:58
    计算智能—进化计算进化计算包括:遗传算法(geneticalgorithms,GA)进化策略(evolutionstrategies)进化编程(evolutionaryprogramming)遗传编程(geneticprogramming)进化计算的基本原理• 随机自适应的全局搜索算法...

    计算智能—进化计算

    进化计算包括:

    • 遗传算法(geneticalgorithms,GA)
    • 进化策略(evolutionstrategies)
    • 进化编程(evolutionaryprogramming)
    • 遗传编程(geneticprogramming)

    进化计算的基本原理

    •    随机自适应的全局搜索算法

    –  (Holland霍兰德)

    •    自然界的“自然选择”和“优胜劣汰”

    –  (Darwin达尔文)

    •    生物遗传学说(交叉+变异)

    –  ( GregorJohann Mendel格里果·约翰·孟德尔)

    遗传算法(并行+合作)

    1. 遗传算法是模仿生物遗传学自然选择机理,通过人工方式所构造的一类随机自适应全局优化搜索算法,是对生物进化过程进行的一种数学仿真,是进化计算的最重要的形式。
    2. 遗传算法为那些难以找到传统数学模型的难题指出了一个解决方法。
    3. 进化计算和遗传算法借鉴了生物科学中的某些知识,这也体现了人工智能这一交叉学科的特点。

    1.霍兰德的遗传算法通常称为简单遗传算法(SGA)。

    2.编码与解码

    3.适应度函数

    4.遗传操作

    1、编码与译码

    • 进化计算求解问题的第一步是对问题的可能解进行编码,目的是为了有效地执行遗传操作。
    • 编码是一个从问题的解空间到编码空间的映射。
    • 如许多应用问题结构很复杂,但可以化为简单的位串形式编码表示,变换为位串形式编码表示的过程叫编码;将问题结构而相反将位串形式编码表示变换为原问题结构的过程叫译码。
    • 借用生物的术语,把位串形式的解的编码表示叫染色体基因型(基因表达),或叫个体
    • 原问题结构即一个染色体解码后所对应的解称为表现型
    • 编码空间也称为基因型空间或搜索空间。
    • 解空间也称为表现型空间
    • 进化算法不是直接作用在问题的解空间上,而是交替地作用在编码空间和解空间上。
    • 编码空间对个体进行遗传操作,在解空间对问题的解进行评估

    例如:数值型的参数编码可以用长度为L的二进制串表示。

    如x取值是[1,64]之间的整数,可以用6位二进制编码表示。其对应关系:

    种群规模越大,性能越高,效率越差

    例:货郎担问题(Travelling Salesman Problem,简记为TSP):设有n个城市,城市i和城市j之间的距离为d(i,j) i, j=1,...,n.TSP问题是要找遍访每个域市恰好一次的一条回路,且其路径总长度为最短。

         对TSP可以按一条回路城市的次序进行编码,比如码串134567829表示从城市1 开始,依次是城市3,4,5,6,7,8,2,9,最后回到城市1。一般情况是从城市w1开始,依次经过城市w2,……,wn,最后回到城市w1,我们就有如下编码表示:   w1 w2 …… wn

    由于是回路,记wn+1= w1。它其实是1,……,n的一个循环排列。要注意w1,w2 ,……,wn是互不相同的。

     

    2.适应度函数—》评价总群中的个体谁最优秀

      为了体现染色体的适应能力,引入了对问题中的每一个染色体都能进行度量的函数,叫适应度函数。通过适应度函数来决定染色体的优、劣程度,它体现了自然进化中的优胜劣汰原则。对优化问题,适应度函数就是目标函数。TSP的目标是路径总长度为最短,路径总长度的倒数就可以为TSP的适应度函数

     

    其中wn+1= w1。适应度函数要有效反映每一个染色体与问题的最优解染色体之间的差距,一个染色体与问题的最优解染色体之间的差距小,则对应的适应度函数值之差就小,否则就大。适应度函数的取值大小与求解问题对象的意义有很大的关系。

    原则1:越优秀的个体,适应度函数值越大

    原则2:对于任一个体,适应度函数值大于0

    对于有些问题不能直接用原始问题做适应度函数

     

    3、遗传操作

    l  简单遗传算法的遗传操作主要有三种:选择(selection)、交叉(crossover)、变异(mutation)。改进的遗传算法大量扩充了遗传操作,以达到更高的效率。

    选择操作也叫复制操作,根据个体的适应度函数值所度量的优、劣程度决定它在下一代是被淘汰还是被遗传。一般地说,选择将使适应度较大(优良)个体有较大的存在机会,而适应度较小(低劣)的个体继续存在的机会也较小。

    选择操作

    ——从旧的种群中选择适应度高的染色体,放入匹配集(缓冲区),为以后染色体交换、变异,产生新的染色体作准备。

    选择方法——适应度比例法(转轮法)

    按各染色体适应度大小比例来决定其被选择数目的多少。

    某染色体被选的概率:Pi(选择概率)

    xi 为种群中第i个染色体,

     

    第k个个体的累加概率之和:(qk=qk-1+pk)

    选择操作具体步骤

    产生0-1的随机数r(均匀产生N)qk-1<=r<=qk,则选择第k个个体进入交配池

    举例1

    具有6个染色体的二进制编码、适应度值、选择概率、累加值。


    交叉操作

    复制不能产生新个体,交叉产生新个体

    N=10,Pc=0.7(交叉概率>=0.7,平均一代又NxPc=7个个体进行交叉

    变异

    变异操作的简单方式是改变数码串的某个位置的数码

    总群中的基因座的数目:NxL

    变异概率:Pm(0.01-.03,<0.1)

    则平均一代中有NxLxPm个基因座发生变异

     

    变异过程:

    变异是随机的

    产生NxL个随机数,若第i个随机数在0-Pm之间,则第i个基因座发生变异

    i个基因座---》第i/L+1条染色体的i%L基因座突变

     

    遗传算法的求解步骤

    (1) 初始化群体;--》随机产生长度为L的染色体(二维数组)

    (2) 计算群体上每个个体的适应度值;个体(基因型)--》表现型—》代入适应度函数—》求出适应度值

    (3) 按由个体适应度值所决定的某个规则选择将进入下一代的个体;(轮转法)

    (4) 按概率Pc进行交叉操作;

    (5) 按概率Pm进行突变操作;

    完成了一代,产生了新的一代

    (6) 若没有满足某种停止条件,则转第(2)步,否则进入下一步。

    (7) 输出群体中适应度值最优的染色体作为问题的满意解或最优解。

     

    遗传算法适合寻找全局最优,不宜找到局部最优,故常和单点寻优相结合。


     


    展开全文
  • 将免疫思想同思维进化计算相结合,提出一种新的基于多种群的自适应免疫进化算法(IABM),算法定义了选择,记忆,克隆,超变异D,抑制5种基本算子.试验结果表明该算法具有高效的收敛速度,并能收敛到全局最优点.与多种群遗传...
  • 钟表匠:钟表匠进化计算框架
  • 资源名称:人工神经网络与模拟进化计算资源截图: 资源太大,传百度网盘了,链接在附件中,有需要的同学自取。
  • 此对基于进化计算的神经网络设计和实现的研究内容及进展情况进行综述, 讨论了网络实现的关键问 题, 包括网络权重的进化训练, 网络结构进化设计, 学习规则进化选取以及进化操作算子设计等, 并分析 了相关的...
  • EinsteinQuestionSolver:如何用进化计算解决爱因斯坦问题
  • 在过去的十年中,数据挖掘技术和信息个性化取得了显着... 这些技术之一是进化计算(EC),它可以优化和改进各种应用中的RS。 这项研究调查了出版物的数量,侧重于某些方面,例如推荐技术,评估方法和所使用的数据集。
  • 计算智能:人工神经网络 模煳系统 进化计算 第二版,经典中文版教材
  • 提出一种基于遗传算法的进化计算模型(ECM ). 在ECM 的种群中, 每个成员都根据其适应度值不同程度 地影响着种群的进化. ECM 定义了个体对进化的影响因子, 并以个体的影响因子为参数定义了个体的形成算子. 分 ...
  • 进化计算 针对“CómputoEvolutivo”主题的进化计算算法 禁忌搜索 推销员旅行问题的实施。 提供了Jupyter笔记本以获取更多详细信息和示例。 运行main.py以执行。 模拟退火 背包问题的实现。 Jupyter Notebook提供...
  • 提出了一种新的模拟进化计算,它模仿新宇宙进化理论中膨胀、收缩两种模式交互作用,推动宇宙进步的过程。膨胀操作提高了种群的多样性和进化算法克服局部收敛的能力,收缩操作吸取了不同群体的优良特性,改善了算法的...
  • 动态进化计算综述,王洪峰,汪定伟,现实世界中的问题是动态的,目前关于进化算法的研究大多还主要局限于静态优化问题,然而很多对于这类时变的优化问题通常并不是要
  • 《计算智能:人工神经网络 模煳系统 进化计算 第二版》
  • 群体智能和进化计算-介绍

    千次阅读 2019-11-14 11:12:21
    文章目录第一章 群体智能和进化计算1.1 群体智能1.1.1 自组织1.1.2 分工进化计算1.2.1 进化计算成员1.3 讨论1.4 结束语参考文献 第一章 群体智能和进化计算 优化问题存在于科学、工程和工业的各个领域。在许多情况下...

    在这里插入图片描述

    获取更多资讯,赶快关注上面的公众号吧!

    第一章 群体智能和进化计算

    优化问题存在于科学、工程和工业的各个领域。在许多情况下,此类优化问题,特别是在当前场景中,涉及各种决策变量、复杂的结构化目标和约束。通常,经典或传统的优化技术在以其原始形式求解此类现实优化问题时都会遇到困难。由于经典优化算法在求解大规模、高度非线性、通常不可微的问题时存在不足,因此需要开发高效、鲁棒的计算算法,无论问题大小,都可以对其进行求解。从自然中获得灵感,开发计算效率高的算法是处理现实世界优化问题的一种方法。从广义上讲,我们可以将这些算法应用于计算科学领域,尤其是计算智能领域。计算智能(CI)是一组受自然启发的计算方法和途径,用于解决复杂的现实世界问题。CI主要包括模糊系统(Fuzzy Systems,FS)、神经网络(Neural Networks,NN)、群体智能(Swarm
    Intelligence,SI)和进化计算(Evolutionary Computation,EC)。计算智能技术具有强大、高效、灵活、可靠等诸多优点,其中群体智能和进化计算是计算智能的两个非常有用的组成部分,主要用于解决优化问题。本部分内容主要关注各种群体和进化优化算法。

    1.1 群体智能

    单词“Swarm”指的是一群无序移动的个体或对象,如昆虫,鸟,鱼。更正式地讲,群体可以看作是相互作用的同类代理或个体的集合。通过建模和模拟这些个体的觅食行为,研究人员已经开发了许多有用的算法。“群体智能”一词是由Beni和Wang[1]在研究移动机器人系统时提出的。他们开发了一套控制机器人群的算法,然而,早期的研究或多或少地都利用了鸟类的群居行为。例如,1987年Reynolds[2]开发了一套程序,使用个体行为来模拟鸟类或其他动物的觅食行为。

    群体智能是一门研究自然和人工系统的学科,由许多个体组成,这些个体基于社会实体间分散的、集体的和自组织的的合作行为进行协调,如鸟群、鱼群、蚁群、动物放牧、细菌生长和微生物智能。群体的成员必须是活跃的、动态的和简单的(没有或几乎没有对周围环境的固有知识)。在群体内部,由于这种协作行为,出现了一种比随机搜索更好的搜索策略,所得到的智能搜索策略一般称为群体智能。Bonabeau等人[3]对群体智能的一个广为接受的定义是,由简单的个体组成的群体所产生的集体智慧。

    在80年代后期的前期工作基础上,90年代先后开发出了两种成功的算法,分别是1992年的蚁群优化算法[4]和1995年的粒子群优化算法[5]。直到90年代中期,由于种群利用、随机性和应用领域的相似性,群体智能方法一直被认为是进化计算方法。然而,由于SI和EC的基本理念存在着一些内在的差异,SI在今天有了自己的身份。SI试图模拟简单代理的集体和协同行为,而EC则受到生物进化的启发。SI作为一种优化算法,由于其简单、有效的特点,在解决实际问题中得到了广泛的应用。

    Karaboga[6]给出了群体智能的充分性条件。Karaboga认为,当且仅当群体智能满足自组织分工两个条件时,一组同类智能体才能表现出群体智能。

    1.1.1 自组织

    这是一个起初是无序的群体,通过群体中个体间的局部相互作用,使运动变得有序的过程。Bonabeau等人[3]将自组织分为四种策略:

    • 正反馈:这是从输出系统中提取的信息,并传递给输入系统,以促进适当结构的形成。正反馈为群体智能提供多样性。

    • 负反馈:用于平衡正反馈,稳定集体模式。负反馈指的是群体智能中的利用。

    • 波动:这些与系统的随机性有关。波动在这一过程中提供了新的情况,有助于摆脱停滞。

    • 多重交互:这提供了向社会中多个个体学习的方式,并提高了群体的整体智能。

    1.1.2 分工

    分工有助于不同的专业个体同时执行不同的任务,使的群体能够处理搜索空间中变化的情况。下面列出的是一些常用和成功的群智能算法:

    • 粒子群优化(Particle Swarm Optimization,PSO)[5]

    • 蜘蛛猴优化(Spider Monkey Optimization,SMO)[7]

    • 人工蜂群算法(Artificial Bee Colony Algorithm,ABC)[6]

    • 蚁群优化(Ant Colony Optimization,ACO)[4]

    • 细菌觅食优化(Bacterial Foraging Optimization,BFO)[8]

    • 萤火虫算法(Firefly algorithm)[9]

    粒子群优化(PSO)的灵感来源于鸟类的群集或鱼群的聚集,人工蜂群优化(ABC)的灵感来源于蜜蜂的觅食行为,蚁群优化(ACO)的灵感来源于蚂蚁的觅食行为,细菌觅食优化(BFO)的灵感来自于大肠杆菌和黄原胶等细菌的群体觅食;萤火虫算法(Firefly Algorithm, FFA)的灵感来自萤火虫的闪烁行为,而蜘蛛猴优化(Spider Monkey Optimization, SMO)的灵感来自蜘蛛猴的觅食行为。

    通过文献检索发现,在这些算法中,PSO和蚁群算法是最常用的。因此,可以简要地讨论这两种算法。

    粒子群优化(PSO)是受鸟群或鱼群的社会行为启发而产生的,于1995年由Kennedy和Eberhart[5]提出。通常,一群鸟没有领头,它们通过合作试错的方式来寻找食物,跟随群体中与食物源位置最接近的个体移动,其他个体则通过与已经拥有更好位置的个体沟通来同时更新他们的位置,重复这个过程,直到找到最佳的食物源。粒子群优化是由许多个体组成,这些构成一个群体,每个个体称为一个粒子,表示多维搜索空间中的一个位置或可能的候选解。

    蚁群优化(ACO)[4]是群体智能第一个成功的例子,该算法用于在图中寻找最优路径。蚁群优化算法的灵感来自蚂蚁寻找巢穴与食物源之间最短路径的能力(图1)。蚂蚁初始时随机开始觅食,一旦蚂蚁找到食物源,它将按原路返回巢穴,并在路上留下信息素。这种信息素的浓度可以引导其他蚂蚁寻找食物,当其他蚂蚁发现信息素时,它们会沿着这条路径前进,其概率与信息素的浓度成正比。现在,如果其他蚂蚁也能找到食物源,它们也会在返回巢穴时留下信息素。随着越来越多的蚂蚁找到了路径,信息素的浓度也越来越高。信息素也会随着时间的推移而衰减,因此与较短的路径相比,较长的路径会有更多的衰减蒸发。蚁群算法在求解离散优化问题中得到了广泛的应用。旅行商问题、机器人路径规划、最小生成树、数据挖掘、分类、调度问题等都体现了蚁群算法在提供有效解决方案方面的优势。

    进化计算

    植物、动物、鸟类等生物在不断地进化,使自己适应动态的环境。与其他候选人相比,那些足够强壮(更适应环境)的候选人更有可能产生能够存活下来的后代。达尔文进化论和自然选择法则是这种进化的原因,进化计算的灵感就是来自于生物进化。很难确切地说明什么时候第一次使用进化原理来解决计算问题。然而,为了给出一些概念,在这里引用De
    Jong等人[10]的描述,“有关使用进化过程解决计算机问题的最早描述之一出现在Friedberg[11]和Friedberg等人[12]的文章中。这代表了机器学习的一些早期工作,并描述了使用进化算法用于自动编程,即寻找计算给定输入输出函数的程序的任务。”想了解更多关于进化计算的历史,读者可以直接参考到De
    Jong等人的成果[10]。

    在这里插入图片描述

    图1 蚂蚁如何找到离巢穴最近的路径

    进化计算(EC)主要用于求解优化问题。进化计算是一系列基于生物进化原理(如自然选择和遗传)的问题解决技术的统称。这些算法试图找到全局最优解。在很短的时间内,这些技术已经在包括工程、科学和农业在内的各个领域的许多问题上得到了应用。EC在搜索过程中模拟了自然选择过程。该类算法从随机生成一组潜在解开始,然后通过迭代更新这些可能的解得到一个新的种群。更新是通过迭代应用选择、交叉和变异操作来完成的。这个过程随机丢弃不好的解,并进化出更适合(更好)的解。通过这些操作,期望所改进的解将一代一代(迭代)地变得更好。

    1.2.1 进化计算成员

    有很多不同的算法都属于EC,如遗传算法(GAs)[13]、遗传规划(GP)[14]、进化规划(EP)[15]和进化策略(ES)[16]。除GP外,EC的其他成员解决优化问题。另一方面,GP通常会找到能够解决给定问题的程式。遗传算法的进化基于达尔文适者生存原则,个体的编码通常是作为二进制向量来完成的,而如前所述,GP虽然使用了与遗传算法相同的适者生存原则,但进化个体是程式。进化规划的灵感来自于自然选择的进化论:另一方面,ES是一种基于适应和进化思想的搜索技术,它将个体编码作为实数向量。另一方面,差异进化与遗传在繁殖机制上是不同的。虽然DE与其他进化算法有许多相似之处,但它的显著不同之处在于,当前种群的距离和方向信息用于指导搜索过程。首先应用变异产生一个试探向量,然后在交叉算子内使用该试探向量产生一个后代,而在一般EA中,却是先应用交叉算子,再应用变异算子。此外,差分变异步长也受当前种群个体间差异的影响,而EA变异则是按照某种概率分布进行采用。

    EC的一些非常显著的特征是:它们可以解决非常不结构化的问题,我们只需要有一种方法来评估解的质量(适合度),而不需要目标函数的可微性。通常,进化算法被指计算上非常耗时,不适合解决非常大规模的问题。尽管这在一般情况下没毛病,但最近的一项突破带来了巨大的希望。最近的一项研究[17]表明,自定义进化算法可以处理涉及十亿个变量的整数线性规划问题。

    1.3 讨论

    这两种方法(SI和EC)背后的哲学主要植根于自然物体的生物学行为。这两种方法都受到自然现象的启发,也都是寻找最优解的搜索策略。群集智能是一种研究群居昆虫或动物在极少规则下的集体行为。进化算法是基于自然选择和遗传进化思想的自适应启发式搜索算法。

    在群体智能中,群体中的个体成员是同一的,随着时间的推移,这种同一性会以移动的形式保留下来。但在进化算法中,种群成员会消亡并被后代取代。SI算法的灵感来自于鸟类、鱼类和蚂蚁等群体的觅食行为,在这些群体中,成员更新自己的位置只是为了适应环境。另一方面,进化算法是基于达尔文适者生存的原则。在这些算法中,利用交叉、变异等自然运算符产生新的子代来代替整个种群。

    我们在上一节关于进化计算的讨论结束时,提到了应用EC解决了一个涉及十亿个变量的整数线性规划问题,这可能是任何优化方法处理过的最大的实际约束优化问题。在[17]中,作者提出了一种非常快速的基于种群的获取近似最优解的方法。这个成功的故事显然说明了EC可能还没有以正确的方式得到充分地探索研究,它强大到足以解决真正的大规模问题,因此有必要进行更多的研究,并且研究这样的算法是很重要的,因为随着先进技术的发展,会产生更多不同性质的数据,研究人员/实践者试图解决更复杂的高计算量的大规模问题。对于此类问题,传统的优化算法有时会变得不合适。此外,在大多数优化问题中,复杂系统都是用复杂的多维函数来建模的,有时不适合使用经典的优化技术。众所周知,经典或传统的优化技术在解决实际优化问题时存在一定的局限性,这主要是由于这些技术固有的解决机制,它们的效率也很大程度上取决于问题的维数以及凸或非凸等求解空间的结构。例如,单纯形法只能用于求解具有线性约束的线性目标函数,但是,当前场景中的大多数优化问题都涉及各种决策变量和复杂的结构化目标和约束(线性或非线性),因此,传统的或数学的优化程序通常是不易于求解。如果我们对这些问题进行建模,使它们能够用经典方法解决,那么几乎可以肯定,我们将不得不对精确表达进行折衷,进而降低了解的质量。由于经典优化算法在求解大规模复杂优化问题时的局限性,基于群体智能和进化计算的算法已成为研究热点。这些技术非常有效且灵活,只需要简单修改就可以适应特定的问题需求。需要强调的是,这里并不是说EC是一种万能的方法,总是能优于经典方法,而应该是当情况需要时才会使用基于EC的方法,也就是说如果经典优化方法能有效解决,当然优先使用。例如,如果需要求解具有线性约束的二次优化问题或合理大小的线性规划问题,就必须使用经典方法,因为这些方法具有良好的数学性质和收敛结果。

    1.4 结束语

    对于一些复杂的优化问题,EC算法和SI算法是较好的选择,因为它们对目标的数学性质和约束条件(如凸性、连续性或显式定义)要求不高。这些方法使用随机方法,可以应用于更广泛的问题。但是,这种适用性伴随着代价,即全局最优的概率收敛性。此外,这些算法有时也无法在当前状态下在搜索空间的探索和利用之间取得适当的平衡。通常,指导搜索过程的参数的选择会变得很困难,结果可能在很大程度上取决于这些选择。考虑到这些限制,在群体智能和进化算法方面其实有很大的改进空间。为了使这些算法高效、准确、可靠,这些领域的改进和开发是一个持续不断的过程。

    高计算能力的可用性促使人们利用EC和SI更有效地解决复杂的问题。群体算法和进化算法可以为解决这类问题提供工具。没有免费午餐定理告诉我们,没有单一的算法可以被指定为最佳算法,只要它经过足够多的问题的测试,总是会激励研究人员开发新的计算智能算法。群体算法和进化算法也被广泛地与其他机器学习方法融合。近年来,基于群体算法或进化算法的深度学习显示出其作为一种非常有前途的机器学习算法[13]的潜力。在此我们注意到,当目标函数复杂、不可微、非凸时,EC和SI具有一定的优势。然而,也存在数据挖掘问题,除了问题的复杂表示之外,涉及的数据量可能非常大(例如,在大气科学、卫生保健、天体物理学和社交媒体中)。在大数据时代,利用EC和SI来挖掘这样的数据集,可能会给研究人员带来巨大的挑战。这当然并不意味着没有改进的余地,而是表明我们需要在这些领域进行更多的研究工作。

    参考文献

    1. Beni, G. and J. Wang, Swarm Intelligence in Cellular Robotic Systems.
      Robots and Biological Systems: Towards a New Bionics? 1993, Berlin: Springer.

    2. Reynolds, C., Flocks, Herds, and Schools: A Distributed Behavioral Model.
      ACM SIGGRAPH Computer Graphics, 1987. 21: p. 25-34.

    3. Bonabeau, E., M. Dorigo, and G. Theraulaz, Swarm intelligence: from natural
      to artificial systems
      . 1999: Oxford University Press, Inc. 307.

    4. Dorigo, M., Optimization, Learning and Natural Algorithms (in Italian).

    5. Kennedy, J. and R. Eberhart. Particle swarm optimization. in Proceedings
      of ICNN’95 - International Conference on Neural Networks
      . 1995.

    6. Karaboga, D., An Idea Based on Honey Bee Swarm for Numerical Optimization,
      Technical Report - TR06.
      Technical Report, Erciyes University, 2005.

    7. Bansal, J.C., et al., Spider Monkey Optimization algorithm for numerical
      optimization.
      Memetic Computing, 2014. 6(1): p. 31-47.

    8. Passino, K.M., Biomimicry of bacterial foraging for distributed optimization
      and control.
      Ieee Control Systems Magazine, 2002. 22(3): p. 52-67.

    9. Yang, X.-S. Firefly Algorithms for Multimodal Optimization. in Stochastic
      Algorithms: Foundations and Applications
      . 2009. Berlin, Heidelberg: Springer
      Berlin Heidelberg.

    10. De Jong, K., The Handbook of Evolutionary Computation. 1999.

    11. M. Friedberg, R., A learning machine: Part I. Ibm Journal of Research and
      Development - IBMRD, 1958. 2: p. 2-13.

    12. Friedberg, R.M., B. Dunham, and J.H. North, A Learning Machine: Part II.
      IBM Journal of Research and Development, 1959. 3(3): p. 282-287.

    13. E. Goldberg, D., Genetic Algorithm in Search, Optimization, and Machine
      Learning.
      Addison-Wesley, Reading, Massachusetts, 1989. xiii.

    14. Banzhaf, W., et al., Genetic Programming ∼ an Introduction: On the
      Automatic Evolution of Computer Programs and Its Applications. Morgan Kaufmann
      .

    15. J. Fogel, L., A.J. Owens, and M.J. Walsh, Artificial Intelligence through
      Simulated Evolution
      . 1966.

    16. Beyer, H.-G. and H.-P. Schwefel, Evolution strategies – A comprehensive
      introduction.
      Natural Computing, 2002. 1(1): p. 3-52.

    17. Deb, K., C. Myburgh, and Acm, Breaking the Billion-Variable Barrier in
      Real-World Optimization Using a Customized Evolutionary Algorithm
      . Gecco’16:
      Proceedings of the 2016 Genetic and Evolutionary Computation Conference. 2016.
      653-660.

    展开全文
  • 进化计算是近年来信息科学、人工智能与计算机科学的研究热点,是人们解决棘手问题的有力工具。阐述了进化计算的基本结构、理论、方法与算法,详细论述了遗传进化的主要操作如选择、重组或交叉、变异、迁移、并行实现...
  • 该项目是Android进化计算算法实现的原型。 我们,汤姆·伯纳德(Tom BERNARD)和乌戈·比切(Ugo PICHE)被要求在法国Polytech'Paris-UPMC工程师学校中作为我们电子与计算机科学的一部分来进行此项目。 我们要感谢...
  • 中科大-自然计算与应用-课程ppt(人工神经网络、进化计算
  • 基于粒子群优化和两次穿越的改进量子进化计算
  • 提出了一种基于模糊模拟进化计算的人体局域网低能量聚类方法。 为了减少通信能耗,我们还设计了一个模糊控制器来动态调整交叉和变异的概率。 通过使用所提出的方法进行聚类仿真基于粒子群优化的方法和基于量子进化...
  • JCLEC是用Java开发的通用进化计算框架。 它的一些主要功能是:多层体系结构,高度可重用且可与其他系统集成,易于使用以及许多已实现的算法和操作
  • 进化计算浅析--论文

    2010-01-01 15:02:12
    在计算机上模拟进化过程的方法称为进化计算进化计算包括遗传算法、进化策略和遗传编程,所有这些方法通过运用选择、突变和复制等步骤来模拟进化。
  • 进化计算评论 注意:如果未指定,则来自Hod幻灯片的所有参考 “无免费午餐”定理 在所有问题上,没有一种算法比其他任何算法都普遍具有更好的性能 算法的改进使其在某些问题上变得更好而在其他问题上变得更糟 使用...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,713
精华内容 1,485
关键字:

进化计算