精华内容
下载资源
问答
  • 本篇笔记对数学建模中常见的多目标规划问题提供了解法:在建立传统的多目标规划的常用模型的基础上,使用智能优化算法对多目标规划问题进行求解,通过Pareto Front直观展现非劣解的分布情况,以解决传统的多目标规划...

    摘要

    本篇笔记对数学建模中常见的多目标规划问题提供了解法:在建立传统的多目标规划的常用模型的基础上,使用智能优化算法对多目标规划问题进行求解,通过Pareto Front直观展现非劣解的分布情况,以解决传统的多目标规划问题将多目标转化为单目标问题带来的只有单一解的问题。并结合一些伪代码,流程图对遗传算法算法本身进行了分析,阅读了一定的材料之后给出利用自己写的简单的具有“变异算子”,“交叉算子”,“选择算子”的代码完成对飞机巡航路线的设计。最后利用Matlab的gamultiobj函数实现对布置的课后作业的求解。
    关键词:多目标规划;智能优化算法;遗传算法;Pareto Front

    一、多目标规划及其非劣解

    1. 概念:
      研究多于一个的目标函数在给定区域上的最优化,称为多目标规划。通常记作:MOP(multi-objective-programming)。
      要注意的是多目标规划的目标之间是相互冲突的(不然就不是多目标),是不能将多个目标合并成为一个统一的目标来求解的,这是判断一个问题是否是多目标规划问题的关键。例如:设计一辆汽车,既要安全(重量大),又要省油;设计一种导弹,既要射程远,又要节约燃料。这样的各个目标之间是冲突的,才能被称为多目标规划问题。
      建模时要注意,多目标求解的目标数尽量保持在2~3个比较合适,目标数量过多会给我们的求解带来困难。

    2. 多目标规划模型的组成:
      (1) 两个以上的目标函数
      (2) 若干个约束条件

    3. 多目标规划模型的主要描述形式:
      在这里插入图片描述
      式中X=[x_1,x_2,…,x_n ]^T为决策变量。我们把
      在这里插入图片描述
      可以写成:s.t. x∈Ω 其中x=(x_1,x_2,…,x_n)所在的空间Ω称为决策空间,F(x)所在的空间称为目标空间
      缩写形式:
      Max⁡(min)Z=F(X)----(1)
      s.t. ϕ(X)≤G

      若有n个决策变量,k个目标函数,m个约束方程,则

    • Z=F(x)-----k维函数变量
    • ϕ(X)-----m维向量函数
    • G-----m维常数向量
    1. 多目标规划的非劣解
      多目标规划问题,不能只顾一个目标函数的最优,而不顾其他的目标函数。多目标规划需要作出复合选择:
      (1) 目标函数的选择
      (2) 决策变量的选择
      衡量某一个方案的好坏无法用一个指标来衡量,需要多个目标进行比较,这些目标有时不是很协调,甚至是对立的。
      在这里插入图片描述
      由上图(假设要求f1和f2都达到最大):1和2比较,1的f2指标大于2的f2指标,但2的f1指标大于1的f1指标,于是二者的较优性无法比较,即无法确定这两个方案的优劣。
      而在各个方案之间,显然,4比1好,3比2好,5比4好,7比3好……
      而对于方案5,6,7之间则无法比较优劣性,且没有比他们更好的其他方案,所以他们被称为多目标规划问题的非劣解,或者Pareto最优解,而其他的解被称为劣解。
      定义1:
      对于最小化问题,一个向量u=(u_1,u_2,…,u_m)支配(优于)另一个向量v=(v_1,v_2,…,v_m),当且仅当u_i≤v_i, i=1,2,…,m,并且存在j∈1,2,3,…,m,u_j<v_j
      定义2:
      对于任意的两个自变量向量x_1,x_2∈Ω,如果下列条件成立:
      在这里插入图片描述
      那么向量f_1 (x_1 ),f_2 (x_1 ),…,f_m (x_1),支配(优于)向量f_1 (x_2 ),f_2 (x_2 ),…,f_m (x_2),则称x_1支配x_2。
      定义3:
      如果Ω中没有支配(优于)x的解,则x是问题的一个pareto最优解,(非劣解,有效解,非支配解)。
      Pareto最优解的全体被称为Pareto最优解集。Pareto最优解集在目标函数空间的像集被称为Pareto Front(Pareto 前沿,阵面)。
      当目标函数处于冲突状态时,就不会存在使所有目标函数同时达到最大或最小值的最优解,有可能一个解在目标上最好,而在另一个目标上是最差。于是我们只能寻求非劣解(又称非支配解或帕累托解)。

    二、多目标规划及其求解方法

    对于多目标规划的解法,这里主要介绍两类:传统的多目标解法和智能优化算法,其中智能优化算法目前是国际上比较流行的多目标规划的求解方法,算法已经被Matlab集成。

    1. 传统解法——多目标规划转换为单目标规划
      ① 效用最优化模型
      思想:规划问题的各个目标函数可以通过一定的方式进行求和运算。这种方法将一系列的目标函数与效用函数建立相关关系,各目标之间通过效用函数协调,使多目标规划问题转化为传统的单目标规划问题:
      在这里插入图片描述
      是与各目标相关的效用函数的和函数。
      在用效用函数作为规划目标时,需要确定一组权值λ来反映原问题中各目标函数在总体目标中的权重,即:
      在这里插入图片描述
      其中,权重值和为1:
      在这里插入图片描述
      ② 罚款模型(理想点法)
      思想: 规划决策者对每一个目标函数都能提出所期望的值(或称满意值);通过比较实际值f_i与期望值f*_i之间的偏差来选择问题的解,其数学表达式如下:
      在这里插入图片描述
      其中λ_i是与第i个目标相关的权重。
      ③ 约束模型
      理论依据 :若规划问题的某一目标可以给出一个可供选择的范围,则该目标就可以作为约束条件而被排除出目标组,进入约束条件组中。
      假如,除第一个目标外,其余目标都可以提出一个可供选择的范围,则该多目标规划问题就可以转化为单目标规划问题:
      在这里插入图片描述
      ④ 目标达到法
      首先将多目标规划模型化为如下标准形式:
      在这里插入图片描述
      在求解之前,先给出与目标函数相对应的一组理想化的期望目标f_i^* (i=1,2,3,…,k),每一个目标对应的权重系数为:ω_i^* (i=1,2,3,…,k),再设γ为一松弛因子,那么多目标规划模型转换为:
      在这里插入图片描述
      用目标达到法求解多目标规划的计算过程,可以通过调用Matlab软件系统优化工具箱中的fgoalattain函数实现。

    2. 智能优化算法求解
      ① 传统算法与智能优化算法的比较:
      在上述的传统的算法中,整体的思想都是将多目标规划转化为但目标规划问题,如果要得到多个解的话,就要进行多次的运行,无法得到pareto最优解集,整体上的效率并不高。而智能优化算法能在一次运行过程中找到Pareto最优解集中的多个解,且不限于Parato前沿解集的形状和连续性,易于解决不连续的,凹的Pareto前沿。
      ② 基于精英策略的快速非支配排序遗传算法(NSGA-II)
      (1)算法概述
      遗传算法( Genetic Algorithm , GA) 是借鉴生物界自然选择和群体进化机制形成的一种全局寻优算法。为方便理解,首先从宏观角度了解遗传算法。
      在遗传算法中,将问题空间的决策变量通过一定的编码方法转换为遗传空间中的个体。将目标函数转化成为一定的适应值,这个适应值将作为评价个体优劣的依据。
      在这里插入图片描述
      遗传算法中涉及到三个算子:选择算子,交叉算子和变异算子,这三个算子模拟了种群遗传和变异产生后代,并且适者生存的过程。其中选择算子反映了“适者生存”,通过种群个体的“适应值”判断个体能否被加入交配池进行交配产生“子代个体”。交叉算子则是模拟种群产生个体的过程,互相交换“染色体”完成产生下一代的过程,而这里的染色体可以理解为编码的序列,具体的我们下面会通过一个例子进行说明。最后变异算子则是较小概率的改变个体的“染色体序列”,实现新个体的出现。
      在这里插入图片描述
      需要说明的是遗传算法中需要确定的参数有:编码串长度、种群大小、交叉和变异概率。编码串长度由优化问题所要求的求解精度决定。种群大小表示种群中所含个体的数量 ,种群较小时,可提高遗传算法的运算速度 ,但却降低了群体的多样性,可能找不出最优解;种群较大时 ,又会增加计算量 ,使遗传算法的运行效率降低。一般取种群数目为20~100。交叉操作是遗传算法中产生新个体的最主要的方法,所以交叉的概率应该设定得比较大,保证种群能进行充分的交配,但若过大可能破坏群体的优良模式。一般取 0. 4~0. 99。变异概率也是影响新个体产生的一个因素,变异概率小 ,产生新个体少;变异概率太大 ,又会使遗传算法变成随机搜索。一般取变异概率为0. 0001~0. 1。遗传算法常采用 的收敛判据有:规定遗传代数;连续几次得到的最优个 体的适应值没有变化或变化很小等。
      下面我们给出遗传算法的流程图,说明遗传算法的主要流程:
      在这里插入图片描述
      首先,建立一个随机的种群规模大小为 N 的初始种群P_0,并初始化计数器 t=0。然后对种群 P_t进行遗传操作产生子代种群Q_t,将P_t和Q_t合并产生R_t,并对具有 2N 规模的种群R_t进行非劣分类操作,并生成下一代种群P_(t+1)。
      进化代数计数器 t 加 1 并判断 t 是否大于最大进化代数 MaxGen。如果是,那么该算法结束;否则,继续进化。如此循环,直到进化到指定的最大进化代数。
      每一个个体都有其对应的适应值,正如每一个决策变量都有其对应的目标函数值。非劣分类操作的原则即是根据上述的由优化问题的目标函数对应转换成的个体的适应值来进行筛选。在进行非劣分类排序时需要保存的值有两个S_p和n_p。S_p对应的被个体p支配的集合,n_p对应个体p被多少个其他的个体所支配,保存这个被其他个体的个数,即是n_p。这个过程也被称为“快速非支配排序算法”的过程。
      我们以需求目标最小值来描述“快速非支配排序算法”过程:
      在这里插入图片描述
      首先找出n_p=0的所有点,即这些点不被任何点所支配,并且保存这些点的S_p,将这些点标记为Pareto等级①。不考虑等级①的点(即图中蓝色的点,或者说删除这些点),在剩余的点中继续寻找n_p=0的点,标记为Pareto等级②……以此类推分完所有的等级。其中①中的解是最好的,也就是前面所提到的精英解集,它只支配其他解而不被其他任何解支配,②中的个体只被 ①不被其它解支配,依次类推。
      但在实际的操作中,并不需要完成对所有的等级的分类——由于整个种群R_t的种群大小为2N,新种群P_(t+1)的N个位置不能容纳所有的非劣等级。当考虑被允许的最后一个等级中的解时,该非劣等级可能存在比新种群剩下位置更多的个体。在这种情况下,使用密度估计的方法从最后一等级选择位于该等级较稀疏区域的个体填充满新种群。这里着重要指出的是R_t的非劣分类和P_(t+1)填充过程可以一起执行。这样,对每一个非劣等级先看它的大小,看它是否 能被新种群容纳,如果不能,那么就不必再进行非劣分类,这样能减少该算法的运行时间。
      在这里插入图片描述
      b. 拥挤选择算子以及交叉算子与变异算子的实现
      拥挤距离的定义
      在上述的“快速非支配排序算法”的叙述中,我们提到了“密度估计”,需要选择较为“疏松”的个体填充P_(t+1)中不足的个体数量。这样是为了使Pareto Front宽广度和均匀度更加合理。
      拥挤距离:第i个个体的拥挤距离定义为第i+1和i-1个体的所有目标函数值的差的和。第一个和最后一个个体的距离设为无穷大——
      在这里插入图片描述
      拥挤选择算子
      下面给出拥挤距离的求解算法: 第一步:对该层(等 Pareto 排序值)的所有点排序,排序结果如上图所示。
      对于两个目标函数值的而言,先选择其中一个目标函数 然后按照该目标函数值从小到大的顺序进行排列,按式(3)计算距离,进而可以用下面的第三步计算拥挤距 离,至到累积完所有的目标函数。
      第二步:每个点的拥挤距离d_i初始化为 0;
      在这里插入图片描述
      伪代码如下:

    1.	def crowding_distance_assignment( I )  
    2.	        nLen = len( I )        #I中的个体数量  
    3.	    for i in I:  
    4.	        i.distance = 0    #初始化所有个体的拥挤距离  
    5.	    	   for objFun in M:        #M为所有目标函数的列表  
    6.	           I = sort( I, objFun )    #按照目标函数objFun进行升序排序  
    7.	           I[0] = I[ len[I]-1 ] =#对第一个和最后一个个体的距离设为无穷大  
    8.	            	for i in xrange( 1, len(I) - 2 ):  
    9.	                 I[i].distance = I[i].distance + ( objFun( I[i+1] ) - objFun( I[i-1] ) )/(Max(objFun()) - Min(objFun()) )  
    
    

    在这里插入图片描述
    在这里插入图片描述
    c. 交叉算子
    d. 变异算子
    (4) 在Matlab中的使用
    在Matlab中可以通过函数gamultiobj函数来进行基于快速非支配排序精英策略的遗传算法。
    具体使用格式

    1.	gamultiobj - Find Pareto front of multiple fitness functions using genetic algorithm  
    2.	  
    3.	    This MATLAB function finds x on the Pareto Front of the objective functions  
    4.	    defined in fun.  
    5.	  
    6.	    x = gamultiobj(fun,nvars)  
    7.	    x = gamultiobj(fun,nvars,A,b)  
    8.	    x = gamultiobj(fun,nvars,A,b,Aeq,beq)  
    9.	    x = gamultiobj(fun,nvars,A,b,Aeq,beq,lb,ub)  
    10.	    x = gamultiobj(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon)  
    11.	    x = gamultiobj(fun,nvars,A,b,Aeq,beq,lb,ub,options)  
    12.	    x = gamultiobj(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,options)  
    13.	    x = gamultiobj(problem)  
    14.	    [x,fval] = gamultiobj(___)  
    15.	    [x,fval,exitflag,output] = gamultiobj(___)  
    16.	    [x,fval,exitflag,output,population,scores] = gamultiobj(___)  
    
    
    1. 用遗传算法求解最优解问题
      例1:
      已知敌方100个目标的经度、纬度如表1所示。
      在这里插入图片描述
      在这里插入图片描述
      下面给出模拟遗传算法的Matlab代码
    1.	function primerRun(routeData)  
    2.	%%-------------------数据初始化-------------------------------------  
    3.	sj0=routeData;          %完成经纬度的加载  
    4.	x=sj0(:,1:2:8);         %提取纬度  
    5.	x=x(:);  
    6.	y=sj0(:,2:2:8);         %提取经度  
    7.	y=y(:);  
    8.	sj=[x y];               %经纬度组成向量  
    9.	mylocation=[70,40];     %我方经纬度  
    10.	sj=[mylocation;sj;mylocation];   
    11.	sj=sj*pi/180;           %转化为弧度  
    12.	distance=zeros(102);    %二维距离数组初始化为0  
    13.	%二维数组计算出地图上任意两点的距离  
    14.	for i=1:101  
    15.	    for j=i+1:102  
    16.	        distance(i,j)=6370*acos(cos(sj(i,1)-sj(j,1))*cos(sj(i,2))*cos(sj(j,2))+sin(sj(i,2))*sin(sj(j,2)));  
    17.	    end  
    18.	end  
    19.	distance=distance+distance';  
    20.	  
    21.	%%-----------------------改良圈算法得到一个较优解----------------------  
    22.	N=50;   %一个种群有50个个体,这个精度由问题的精确性给出,这里取50  
    23.	g=100;  %进化代数定义为进化10024.	rand('state',sum(clock));   %matlab随机数为伪随机数,这里定义一个种子,初始化随机发生器  
    25.	for k=1:N   %改良圈算法初始化种群  
    26.	    c=randperm(100);    %产生1~100的一个全排列  
    27.	    c1=[1,c+1,102];     %生成初始圈  
    28.	    for t=1:102         %修改圈  
    29.	        flag=0;         %退圈标志  
    30.	        for m=1:100  
    31.	            for n=m+2:101  
    32.	                if distance(c1(m),c1(n))+distance(c1(m+1),c1(n+1))<distance(c1(m),c1(m+1))+distance(c1(n),c1(n+1))  
    33.	                    c1(m+1:n)=c1(n:-1:m+1);  
    34.	                    flag=1;  
    35.	                end  
    36.	            end  
    37.	        end  
    38.	        if flag==0  
    39.	            J(k,c1)=1:102;  
    40.	            break;  %记录下较好的解后跳出循环  
    41.	        end  
    42.	    end  
    43.	end  
    44.	J(:,1)=0;  
    45.	J=J/102;            %转换为染色体编码  
    46.	%%---------------------------------------------遗传算法主体---------------------------------------  
    47.	for k=1:g   %循环进行种群交配  
    48.	    A=J;    %得到亲代的初始的染色体  
    49.	    c=randperm(N);%产生一个1~50的全排列,作为初始的染色体交换对象  
    50.	    %------------------------------------交叉操作-----------------------------------------------  
    51.	    for i=1:2:N  
    52.	        F=2+floor(100*rand(1));     %保证圈的起始点和终点不变的条件下,产生要进行染色体交换的地址  
    53.	        temp=A(c(i),[F:102]);       %中间变量保存值  
    54.	        A(c(i),[F:102])=A(c(i+1),[F:102]);  %交叉操作  
    55.	        A(c(i+1),F:102)=temp;  
    56.	    end  
    57.	    by=[];  
    58.	    %-----------------------------------变异操作-----------------------------------------  
    59.	    %循环保证by非空  
    60.	    while ~length(by)  
    61.	        by=find(rand(1,N)<0.1);      %返回向量或者矩阵中不为0的元素的位置索引  
    62.	    end  
    63.	    B=A(by,:);%产生变异操作的初始染色体  
    64.	    for j=1:length(by)  
    65.	        bw=sort(2+floor(100*rand(1,3)));    %产生变异操作的三个索引  
    66.	        B(j,:)=B(j,[1:bw(1)-1,bw(2)+1:bw(3),bw(1):bw(2),bw(3)+1:102]);%交换位置  
    67.	    end  
    68.	    G=[J;A;B];%父代和子代的种群合在一起  
    69.	    [SG,ind1]=sort(G,2);  
    70.	    num=size(G,1);  
    71.	    long=zeros(1,num);%路径长度的初始值  
    72.	    for j=1:num  
    73.	        for i=1:101  
    74.	            long(j)=long(j)+distance(ind1(j,i),ind1(j,i+1));  
    75.	        end  
    76.	    end  
    77.	    [slong,ind2]=sort(long);%对路径长度由小到大排序  
    78.	    J=G(ind2(1:N),:);%优胜劣汰  
    79.	end  
    80.	path=ind1(ind2(1),:),flong=slong(1)  
    81.	xx=sj(path,1);  
    82.	yy=sj(path,2);  
    83.	plot(xx,yy,'-o'); 
    
    

    在这里插入图片描述

    三、多目标规划应用实例(例题)

    例一:
    某厂生产A和B两种型号的摩托车,每辆车平均生产时间和利润分别为A种:3小时,100元;B种:2小时,80元。该厂每周生产时间为120小时,但可加班48小时,加班时间生产每辆车的利润为:90元(A种),70元(B种),市场每周需要A,B两种车各30辆以上,问如何安排每周的生产计划,在尽量满足市场需求的条件下使利润最大,加班时间最少,建立数学模型,并求解分析。
    解:提取题目信息绘制表格:
    在这里插入图片描述
    设:

    • f_1利润,f_2:加班时间
    • x_1----正常时间生产A型号的件数
    • x_2----加班时间生产A型号的件数
    • x_3----正常时间生产B型号的件数
    • x_4----加班时间生产B型号的件数

    建立下面的数学模型:
    在这里插入图片描述
    由于智能优化算法涉及到算子的选择问题,以及终止代数的不同,运行了多次后这里给出某一次运行得到的解:
    在这里插入图片描述
    在这里插入图片描述
    上图为Pareto Front图像,横轴Objective_1为第一个目标,即加班时间;纵轴Objective_2为第二个目标,即工厂利润。
    其中主要的三个拐点已经标记出,由上图我们可以看到加班时间最小化与利润最大化之间是存在冲突的,和多目标规划定义符合。
    利用Matlab代码求解后得到上图所示的Pareto front。由图像可知:当加班时间在45小时时,收益达到最大值12100元,而当加班时间小于1.5小时时,利润变动变化较小,基本保持在1000元左右。对于其他的情况,工厂决策者可以根据工厂实际情况进行方案选择。
    求解代码如下:

    1.	function y=example1Fun(x)  
    2.	y(1)=-100*x(1)-90*x(2)-80*x(3)-70*x(4);  
    3.	y(2)=0*x(1)+0*x(3)+3*x(2)+2*x(4);  
    
    
    1.	clear  
    2.	clc  
    3.	fitnessfcn=@example1Fun;  
    4.	nvars=4;  
    5.	lb=zeros(1,4);  
    6.	ub=[];  
    7.	A=[-1,-1,0,0;0,0,-1,-1;3,2,0,0;0,3,0,2];  
    8.	b=[-30,-30,120,48]';  
    9.	Aeq=[];  
    10.	beq=[];  
    11.	options=gaoptimset('paretoFraction',0.3,'populationsize',200,'generations',300,'stallGenLimit',200,'TolFun',1e-10,'PlotFcns',@gaplotpareto);  
    12.	[x,fval]=gamultiobj(fitnessfcn,nvars,A,b,Aeq,beq,lb,ub,options) 
    
    

    例2:
    某工厂共有工人300名,生产A,B,C,D四种产品,要求每人每周平均生产时间在40~48小时内,C为国防用产品,每周至少生产150件,而每周至多可以提供能源20吨标准煤。其他数据如下表:

    在这里插入图片描述
    问如何安排每周的生产,才能使纯利润最高,而能耗最少?试建立数学模型并求解。
    解:设利润函数为f_1,能耗函数为f_2。A,B,C,D四种产品分别生产x_1,x_2,x_3,x_4件。
    在这里插入图片描述
    利用Matlab代码求解后得到下图所示的Pareto front。由图像可知:当煤耗量达到17.71t时所获得的利润也达到了最大值14240元;当煤耗量在14.45t~14.33t之间波动时,最大利润波动不大;当煤耗量达到最小14.06t时,利润值也达到了10510元。
    对于其他的情况,我们给出相应的决策变量以及对应的决策空间的解,管理者可以根据工厂的实际情况进行相应的选择。
    在这里插入图片描述
    Matlab代码如下:

    1.	function y=example2Fun(x)  
    2.	y(1)=-10*x(1)-20*x(2)-12*x(3)-14*x(4);  
    3.	y(2)=0.01*(1.5*x(1)+2*x(2)+1.8*x(3)+1.1*x(4));  
    
    
    1.	clear   
    2.	clc  
    3.	fitnessfcn=@example2Fun;  
    4.	nvars=4;  
    5.	A=[13,13.5,14,15;-13,-13.5,-14,-15;1.5,2,1.8,1.1];  
    6.	b=[48*300 -40*300 2000]';  
    7.	Aeq=[];  
    8.	beq=[];  
    9.	lb=[0,0,150,0];  
    10.	ub=[270 240 460 130];  
    11.	options=gaoptimset('paretoFraction',0.3,'populationsize',200,'generations',300,'stallGenLimit',200,'TolFun',1e-10,'PlotFcns',@gaplotpareto);  
    12.	[x,fval]=gamultiobj(fitnessfcn,nvars,A,b,Aeq,beq,lb,ub,options)  
    
    

    决策变量取值以及对应解空间:
    在这里插入图片描述在这里插入图片描述

    展开全文
  • 群体智能动态优化算法及其应用综述[A survey of swarm intelligence for dynamic optimization: Algorithms and applications]摘要一.前言二.动态优化2.1动态优化问题2.2离散空间与连续空间2.3应用2.4测试2.5基准...

    A survey of swarm intelligence for dynamic optimization: Algorithms and applications

    摘要

    群体智能算法,包括蚁群优化、粒子群优化、蜜蜂启发算法、细菌觅食优化、萤火虫算法、鱼群优化等,已被证明是解决平稳环境下复杂优化问题的有效方法。大多数SI算法都是为了解决平稳优化问题而发展起来的,因此它们能有效地收敛于(近似)最优解。然而,现实世界中的许多问题都有一个随时间变化的动态环境。对于这种动态优化问题(DOPs),传统的SI算法一旦收敛到一个解,就很难跟踪到变化的最优解。在过去的二十年中,由于其自适应能力,使用SI算法对DOPs进行寻址的兴趣越来越大。本文综述了国际单位制动态优化(SIDO)的研究进展,主要集中在离散、连续、约束、多目标和分类问题以及实际应用中。此外,本文还重点研究了集成在SI算法中的动态变化增强策略、SIDO中使用的性能度量和基准生成器。最后,对该课题未来的发展方向提出了一些思考。
    关键词:群体智能,动态优化,蚁群优化,粒子群优化

    一.前言

    群体智能是一类重要的优化方法。SI是一个系统的性质,在这个系统中,与环境局部交互作用的主体的集体行为导致连贯的功能性全局模式的出现。与进化算法(EAs)不同,SI算法的灵感来源于简单的行为和智能体之间的自组织交互,如蚁群觅食、鸟类群集、动物放牧、细菌生长、蜜蜂、鱼类教育等。SI一词最早由Beni[1]在细胞机器人系统中使用,在该系统中,简单的智能体通过邻域交互来组织自己,后来在[2,3,4]中建立起来。
    目前主流的算法有蚁群算法(ACO)和粒子群算法(PSO)。较不流行的SI算法包括人工蜂群(ABC)[7]、细菌觅食优化(BFO)[8]、萤火虫算法(FA)[9,10]、人工鱼群优化(AFSO)[11]和许多其他算法。最初,SI算法是为平稳优化问题设计的。然而,现实世界中的许多优化问题都受到动态环境的影响。动态优化问题(DOP)可能会发生变化在目标函数、约束条件、问题实例中,Pareto前沿或集(在动态多目标优化问题中)引起最优值的变化。因此,DOPs比平稳优化问题更具挑战性,因为需要对变化的最优值进行重复优化[12]。
    动态优化领域与EAs、knownas进化动态优化(EDO)密切相关[12]。然而,在不同的dop上应用SI算法已经成为人们越来越感兴趣的问题。江户受到了广泛的关注,有几项调查[13,12,14,15]和几本书[16,17,18,19,20],而SI动态优化(SIDO)并没有受到太多的关注,除了一些在[14]中对PSO和在[15]中作为江户调查的子部分的ACO的非常简短的评论。本文的目的是扩展对蚁群算法和粒子群优化算法的这些评论,并对现有的与SIDO相关的工作进行全面的综述,其中也包括不太流行和最新的SI算法。本次调查的重点将是根据应用对SI算法进行分类,并回顾与SI算法集成以应对动态变化的策略。DOPs主要分为离散空间问题和连续空间问题,并对它们的应用作了进一步的分类。本文还回顾了SI所解决的实际问题,以及SIDO的性能测量和基准生成器。
    论文的其余部分安排如下。第二节简要介绍了DOPs的概念,描述了离散DOPs和连续DOPs的区别及其应用。此外,还描述了SIDO中常用的基准生成器和性能度量。第3节简要介绍了不同的SI算法。第4节回顾了SIDO的算法和应用,SIDO按问题的类别排列,即离散、连续、约束、多目标和分类问题。第5节回顾了使用SI算法的实际应用。第六部分对本文进行了总结,并对SIDO未来的研究问题和方向进行了总结。

    二.动态优化

    2.1动态优化问题

    DOP可以直观地定义为一系列需要优化的静态问题实例[21]。“动力性”的两个主要方面由环境变化的频率和幅度来定义。前者和后者的参数分别对应于问题环境变化的速度和程度。其他方面包括动态变化的可预测性、可探测性和时间联系[22,23]。前两个方面分别对应于在执行期间是否可以预测或检测动态变化,后一个方面对应于现在作出的处理动态变化的决策是否依赖于任何先前的决策。
    环境变化可能涉及目标函数(或考虑动态多目标问题时的函数[24,25])、输入变量、问题实例和约束(例如,动态约束优化[26])。形式上,DOP可以定义如下:
    DOP=optimizef(x,t)subject to X(t)⊆S,t∈T (1)
    其中S是搜索空间,t是时间,f:S×T→R是给每可能的解x∈S赋值(即R)的目标函数并且X(t)是在时间t时的x∈X(t)⊆S的可行解集。每个可行解x由优化变量x={x_1…,x_n}。每个解x∈X(t)有一组邻域N(x)⊆X(t),其中N(x)是一个将邻域赋给x的函数。局部最优解是最小化问题的f(x^’,t)≤f(x,t)),∀ x∈N(x)或最大化问题的f(x^’,t)≥f(x,t)),∀ x∈N(x)的可行解。

    2.2离散空间与连续空间

    在搜索空间X(t)的定义上有不同的优化问题类别。本文考虑了两类基本问题:
    (1)离散优化问题,其中所有的优化变量都是离散的,取值x∈D_i={v_i1,…,v_iD },i=1,…,n
    (2)连续优化问题,其中所有的优化变量都是连续的,取值x∈D_i⊆R,i=1,…,n
    离散优化问题与连续优化问题的主要区别在于离散优化问题具有有限的搜索空间。更准确地说,它们的特征是一组有限的变量值,例如,限制为值0和1的二进制值或从一组有限元素中提取的对象。不同的是,连续优化问题中的每一个变量值都可以假设无穷多个值,例如实数。由于计算机本质上是数字的,所以表示离散变量是直接的。相反,表示连续变量需要施加一定的限制,因为不可能表示无限多的值。
    在不提供免费午餐(NFL)的情况下,任何在计算机系统中运行的优化问题都包含一个有限域,因此,可以认为是离散的。NFL的另一种方法表明,理论如此成立用于任意域和共域。相比之下,其他的研究[29,30]表明NFL定理不适用于连续域,尽管它的软形式NFL适用于可数无限域。然而,在[31]中,证明了NFL确实在连续域中成立,因为[29,30]中作者的结论是从他们施加的人工约束中得出的,该人工约束考虑的函数是可测量的。附加的人工约束被施加,但可测量性足以使NFL变得微不足道。
    然而,处理离散和连续问题的方法通常不同。例如,在离散问题的情况下,在开始优化过程之前预先定义了可用值集。因此,适当的个体必须选择可能的最佳值组合以找到解决方案。在连续出现问题的情况下,这种方法可能没有效率。相反,求解器通常使用实值变量的灵活浮点表示。这样,就可以更有效地找到具有所需精度的解决方案。

    2.3应用

    离散优化问题和连续优化问题都有广泛的应用,稍后将分别在表2和表3中进行总结。在运输、调度、管理、生产、设施控制等领域,大多数实际问题都包含有限个可能的解。因此,它们可以表示为离散优化问题。
    例如,许多现实世界中的网络环境优化问题,如道路系统、社会网络、电信网络、铁路网络等,往往是用加权图来建模的。由加权图建模的基本离散优化问题是旅行商问题(TSP)。TSP在路径问题和调度问题中有着广泛的应用,如车辆路径问题(VRP),它在运输、货物配送和物流等领域有着密切的联系。VRP中的弧路由问题,即容量分配问题,在现实世界中也有许多应用,如盐路由优化问题、城市垃圾收集问题和除雪问题。
    不同的是,持续优化中的应用排除了计算金融中的实际问题,可以用于医学研究的人工神经网络诊断,道路系统交通预测,语音和面部识别,并预测天气或客户需求。而且,它可能包括最佳形状的设计,例如机翼,涡轮机,发动机,发电厂等。

    2.4测试

    跟踪运动最优(TMO)的目的是在任何时刻找到环境的最优解。研究人员在TMO中从不同的角度看待他们的算法[32]。一些研究者更关注系统的极端行为,特别是系统所能做的最好的,例如修改的离线性能[33,17],集体平均适应度[34],最好的变化前性能[35,36]。不同的是,其他研究人员希望观察“一个算法找到的解离移动最优值有多近”[37,38]。因此,测量要求在动态变化期间已知全局最优值,例如离线误差[39]、平均得分[40]、精度[41]和基于算法找到的解与全局最优值之间的距离的其他测量[42,43]。其他人则关注能够将总体描述为一个整体的度量,例如平均性能或平均健壮性[44]。
    最近,DOPs的一个新视角被建立,称为鲁棒优化超时(robust optimization over time,ROOT),其目标是找到随时间而鲁棒的解序列[45]。特别是,当一个解决方案的质量在给定的时间间隔内可以被环境变化所接受时,该解决方案是随时间而健壮的。关于SI算法,到目前为止,TMO主要用于所有这些算法。相比之下,ROOT只用于PSO算法[46]。当使用PSO[47]和ACO[48,49]处理问题不确定性时,鲁棒优化被认为是有用的,例如,减少计算工作量。
    除了涉及算法性能的度量之外,其他度量还涉及算法的行为。常见的例子有:解的多样性[50,51,52,39]、稳定性[53,41]、反应性[41]、稳健性[44]、交叉熵[54]、peakcover[17]和λ-分支[55]2。为了评价算法对可行区域的跟踪和定位能力,提出了其他性能指标,如:可行时间比、最优区域跟踪指标、局部搜索覆盖、约束条件评价次数等。此外,对现有的测量结果进行了修改动态约束优化问题,如:用峰值覆盖来计算每个周期中唯一可行区域的个数,用离线误差来将最优误差视为正态,但如果没有可行解,则考虑当前最差可能值[56]。
    当然,以上所有DOPs的测量都假设一个单一的目标。处理多个对象时使用不同的度量,例如:间距[57]、超体积比[58]、S-和FS度量[59]、精度[60]、稳定性[60]、可变空间世代距离[61]和最大传播[61]。

    截图来自A survey of swarm intelligence for dynamic optimization: Algorithms and applications

    2.5基准生成器

    基准生成器是DOPs中必不可少的工具,因为SIDO和动态优化中可用的理论工作有限[62,63]。它们使研究人员能够开发和评估DOPs的新算法,更重要的是将它们与现有算法进行比较。
    2.5.1动态的产生
    构造动态测试问题的一个简单方法是在会导致环境变化的不同静态实例之间切换[64]。按照此方法生成动态环境的基准问题是为单个问题指定的。在其他一些情况下,研究人员更喜欢创建自己定制的基准问题,这些问题的目标是模拟一些现实世界的场景(65、66、37、67、68、69),这些场景又是针对特定问题,甚至是问题的特定实例开发的。
    已经有人提出了几个能量曲线动态基准生成器,用于重新塑造适应度环境(对于连续问题)或将搜索过程移动到适应度环境的不同位置(对于离散问题)。综合调查见[13,14]。可能最常用的DOP基准生成器是:(1)移动峰值基准(MPB)[4];(2)广义动态基准生成器(GDBG)[40];(3)二进制编码问题的异或(XOR)DOP生成器[70];(4)置换编码问题的动态基准生成器(DBGP)[71]。前两个基准生成器在连续域中工作,它们使用参数可调的函数来模拟移动的地形。考虑到连续空间可以建模为“圆锥体场”[72],那么每个圆锥体可以单独调整以表示不同的动力学。图1显示了分别属于MPB和GDBG的两个案例的适应度景观。
    由于连续空间具有无穷多个变量值,因此在开发求解复杂数学函数的基准时会受到某些限制。MPB[4]是在连续空间中测试算法性能的主要基准之一。MPB问题中的每个峰值都是一个coneshape。这将是一个容易的算法,以开发一个局部的最佳健身景观。克服像MPB和DF1[72]这样的DOPs的限制(类似的带有MPB的基准生成器),GDBG基准由Li等人开发。[40],最初是为2009年IEEE DOPs进化计算竞赛而提出的。与MPB问题相比,GDBG有一个更复杂的适应度环境,这是因为搜索空间中存在大量的旋转优化。在GDBG基准测试中,有6个基本测试函数,每个测试函数有8种变化类型,分别是小步变化、大步变化、随机变化、混沌变化、递归变化、带噪声的递归变化、维数变化和峰数变化。在[45]中,修改了MPB以生成根问题。在TMO的原始MPB中,所有峰值都以相同的频率和严重性发生变化,而在根的改进MPB中,每个峰值都有自己的频率和严重性。
    在离散的空间中,景观是模糊的,并且不参考优化算法就无法定义[63]。通常,定义离散/组合优化问题的组件会被修改,并且专门针对该问题。对于动态TSP(DTSP),当发生更改时,可以替换/删除节点[66],或者可以增加/减少弧的权重[65、21]。动态VRP(DVRP)的动态变化可能会在弧线的重量上发生[33],或者可能会发现新客户[67]。当动态作业车间调度问题(DJSSP)执行期间有新作业到达时,动态变化就会发生[73,74]。动态背包问题(DKP)的变化可能发生在商品的价值和重量以及背包的容量上,或直接作用于目标函数[75]。通过根据二进制模板将值从“ 0”翻转为“ 1”,反之亦然,XOR DOP可以为任何二进制编码的问题生成DOP,这是离散问题的特殊情况。通过交换问题实例的节点,DBGP可以为任何经置换编码的路由问题生成DOP [55、76]。
    MPB,GDBG,DBGP,XOR DOP基准生成器和所有其他上述基准均假定无约束和单一目标优化问题。 最近,提出了用于连续动态约束优化[77、78、26、14]和连续动态多目标优化[25、61、79、80、81、82、83、84、85]的基准生成器。 但是,离散空间下的约束和多目标优化尚未引起人们的广泛关注并且值得将来考虑。
    2.5.2讨论
    对于连续空间中的基准,大多数基准采用以下形式来生成景观:f(x,t)=maxgi(x,t)。 这种方法简单明了。 但是,它有两个缺点。 首先,它在计算上效率低下。 为了评估解决方案,我们必须计算每g的目标值,然后找到最佳目标值作为解决方案的目标值。 其次,如果某些峰被较高的峰覆盖,则这些峰可能是不可见的。 此外,这些基准缺乏实际问题的方案。
    对于离散空间中的基准,通常会修改问题实例的变量,例如代表问题的加权图G=(C,L,t)的节点或弧。 尽管实际情况是使用大多数基准测试生成的,但是在动态变化期间,全局最优值尚不清楚。 因此,如果所有比较的算法都无法达到最佳效果,则将无法观察到。 一种解决方案是将搜索过程移到景观的其他位置,而不是更改它,例如,使用可以生成动态环境的DBGP(用于置换编码的问题)和XOR DOP(用于二进制编码的问题) 而不影响全局最优值。 基本上,修改了问题实例的编码,而不是搜索空间。 但是,为了进行基准测试,牺牲了真实场景的能力。

    三.群体智能算法

    3.1简要说明

    在国际单位制中,元启发式的领域是混乱的,因为有许多“新颖的”元启发式基本上是重复现有的元启发式[87]或甚至没有受到自然或群体的启发,例如烟花爆炸所激发的烟花算法[88]。然而,本文只关注表1中列出的应用于DOPs的SI元启发式方法。
    一般来说,所有的SI算法都是为表1中定义的不同优化问题域专门开发的。例如,ACO是为离散空间开发的,而表1中的其余算法是为连续空间开发的。这些算法的共同特点它们的灵感来源于自然、基于人口和迭代。他们的不同之处,除了他们的行为灵感,在于搜索空间被“代理人”探索和利用的方式[89]。
    在这里插入图片描述

    3.1.1 蚁群优化(ACO)

    蚁群算法的灵感来自真实蚂蚁的觅食行为。蚂蚁的目标是在它们的巢穴和食物来源之间找到最短的路径。ACO元启发式基于几个构造步骤和一个动态内存结构,该结构包含有关先前获得的结果质量的信息[90,91]。每只蚂蚁代表一个潜在的问题解决方案。一种基于已有信息素路径和先验启发信息的概率解构造方法。当所有蚂蚁完成前向模式时,它们会切换到后向模式,在后向模式中,共享的信息素表会相应地更新,也就是说,解的质量越好,信息素沉积的越多。
    有两个主要的ACO框架,即基于蒸发的[92,93]和基于人口的[66]。它们的区别在于信息素的更新方式。基于蒸发的框架将信息素路径逐渐减少一个恒定的量,以消除以前任何糟糕的老“决定”。基于种群的框架使用一个种群,当从种群中移除一个解决方案时,该种群直接移除信息素路径。

    3.1.2粒子群优化(PSO)

    PSO首先在[86]中被引入来解决连续优化问题。每个粒子代表问题的一个潜在解决方案。更准确地说,每个粒子分别由一个速度和位置向量组成,它们根据粒子的最佳迄今位置和群的最佳迄今位置进行更新。
    PSO算法主要有全局最优和局部最优两种模型。它们的区别在于每个粒子的邻域结构。在全局最优模型中,粒子的邻域由整体暖场中的粒子组成,它们之间共享信息。相反,在局部最优模型中,粒子的邻域由几个混合粒子定义。Poli等人。[94]指出,全局最优模型比局部最优模型收敛速度快,而前者陷入局部最优的概率比后者高。不同PSO变化的调查可以在[95,96]中找到。
    这两种模型都被使用,但由于它们的特点,使用的方式不同。全局最优模型通常用于多群算法[97、98、99],而局部最优模型通常用于单群算法[100、101、102]。

    3.1.3人工蜂群(ABC)

    蜜蜂启发算法的发展主要有:ABC算法、蜜蜂群体优化算法、蜜蜂系统、蜜蜂婚姻过程优化算法、蜜蜂交配优化算法、虚拟蜜蜂算法、蜜蜂算法和蜂巢算法。不同发展的调查可以在[103,104,105]中找到。在本文中,我们主要关注的是ABC算法,尤其是DOPs中的ABC算法[105]。特别是,ABC算法模拟了真实蜜蜂群体的行为[7]。传统的ABC算法由食物源组成,而每个食物源代表问题的潜在解决方案。食物来源由三组蜜蜂更新:雇佣的、旁观者的和侦察蜂。
    蜜蜂:雇佣的,旁观者和侦察蜂。在使用蜜蜂阶段,蜜蜂寻找新的解决方案。特别是,每只蜜蜂都会从原来的位置产生一个新的候选食物源位置。如果发现含有更多花蜜的食物来源,即新的解决方案比当前的解决方案更适合,则更新它们。接下来,在旁观者蜜蜂阶段,根据从所使用的蜜蜂阶段确定的适应度确定相对概率。然后,旁观者蜜蜂选择一个解决方案,其中最适合的解决方案有较高的概率被旁观者蜜蜂选择。在那之后,旁观者的蜜蜂和被雇佣的蜜蜂有同样的行为。最后,如果被抛弃,侦察蜂会随机重新分配解决方案,例如,它们已经有一段时间没有更新。

    3.1.4细菌觅食优化算法

    BFO算法的灵感来自于细菌觅食中复杂的有组织活动以及细菌在不同环境中的生存[8106107]。一个BFO算法由几个细菌组成,它们代表优化问题的解,由三个过程组成:趋化、繁殖和消除扩散。
    在趋化作用中,随机方向的细菌代表翻滚,与上一步相同方向的细菌代表奔跑。接下来在繁殖过程中,所有的细菌都被分类,只有一半的适者生存。然后,存活的细菌被分成两个相同的细菌,形成新的细菌。最后,在消除扩散过程中,随机选择一个细菌在搜索空间中移动到不同的随机位置。尽管此操作在执行期间保持多样性,但它可能会干扰优化过程,从而在复制过程的几个步骤之后执行。

    3.1.5人工鱼群优化(AFSO)

    鱼类启发算法有一些现有的发展。关于发展的详细描述见[108]。本文以应用于DOPs的真实鱼群在水体中的觅食行为为灵感,研究了AFSO。在AFSO中,每一条人工鱼通过三种主要行为寻找一个具有更多食物来源(更好的适应度)的位置(解决方案):猎物、鱼群和跟随。捕食行为是由人工鱼在不考虑其他群体成员的情况下完成的。更准确地说,在鱼的视觉范围内,比水流更好的目标位置被认为是随机的。
    群体行为是一种群体行为,在群体的所有成员中都有如下表现。每一条人工鱼在其视觉范围内由许多邻居组成。如果视野的中心位置更好,那么它会向中心位置移动;否则,猎物的行为会再次发生。类似地,执行跟随行为,但人工鱼将在其视觉范围内向更好的邻居位置移动,而不是向中心位置移动。否则,猎物的行为会再次发生。基本上,当人工鱼不能移动到一个更好的位置时,被捕食的行为被执行。如果算法达到停滞行为,则从整个人工鱼群中随机选择一些人工鱼并随机设置。记录到目前为止人工鱼的最佳位置(即溶液)。

    3.1.6萤火虫算法(FA)

    FA的灵感来自萤火虫的闪光模式和行为[9,10]。FA基于三个假设:
    1.所有的萤火虫都能被其他的萤火虫吸引;
    2.每只萤火虫的吸引力与其他萤火虫的亮度成正比;
    3.景观问题决定了萤火虫的亮度。
    因此,一只不太亮的萤火虫会向一只更亮的萤火虫移动。否则,如果萤火虫找不到更亮的萤火虫,它会随机移动。每只萤火虫的发光与其溶液的质量成比例,而溶液的质量和它的吸引力决定了它对群体中其他成员的吸引力。
    3.2适应不断变化的环境
    由于所有的SI算法最初都是为平稳优化问题设计的,所以它们有一个共同的特性:收敛性,即它们被设计成快速而精确地收敛到最优解。相比之下,DOPs需要重复优化和跟踪运动最优值。然而,当一个算法收敛时,由于分集丢失问题,它的自适应能力会丧失。因此,通过增加/保持分集来解决分集丢失问题是非常重要的。然而,这并不意味着高水平的多样性将导致更好的性能[12,55]。这是因为太多的随机化可能会干扰优化过程。
    在DOPs中,SI算法的另一个重要方面是促进知识转移。自然,知识可以通过使用SI算法从先前优化的环境中转移,例如,通过ACO的信息素跟踪,通过ABC和AFSO的食物源,通过FA和BFO分别定位萤火虫和细菌。然而,当发生动态变化时,可能不足以快速恢复。另一方面,如果传递过多的知识,可能会使优化过程接近于一个差的局部最优解而陷入困境。
    对于不同的dop,增强的SI算法已经被证明是有效的。集成到SI算法中的增强策略的主要思想是实现知识转移和多样性维护的良好平衡,如图2所示。此外,这两个因素也是相互冲突的,因为如果不保持多样性,那么算法将不会非常灵活地利用任何转移的知识。
    在这里插入图片描述

    四.群体智能动态优化

    在本节中,将针对各类问题审查处理动态变化的主要国际单位战略,具体如下:
    动态离散优化中的SI;
    动态连续优化中的SI;
    动态约束优化中SI;
    动态多目标优化中的SI;
    动态分类中的SI.
    由于前两类已经被广泛研究过,它们被进一步分类为应用程序(见表2和表3)和策略类型:(a)改变后增加多样性,(b)在执行期间保持多样性,(c)内存方案,(d)多重填充3方法和(e)杂交。剩下的课程是目前SIDO的趋势,他们的研究也很有限。

    4.1动态离散优化中的SI

    许多离散优化问题,无论是在平稳环境还是在动态环境中,都是NP难问题,也就是说,人们强烈认为它们在多项式计算时间内无法求解到最优性[109]。动态版本的几个流行的离散优化问题已经解决了使用国际单位制方法。
    从表2中可以看出,ACO主要用于离散/组合问题。通常,这些问题使用加权图G=(C,L)表示,其中C是一组组件,L是一组链接。例如,对于DTSP或DVRP,信息素路径τ_ij映射有问题的组成部分和链接,以表示在组成部分(节点)i之后访问组成部分(节点)j的可取性。类似地,DJSSP中的信息素线索是指在操作i之后直接选择操作j的可取性。对于二进制编码的问题,信息素线索与组件可以采取的两个可能的选择相关。对于DKP,信息素轨迹τ_i仅与组件相关联,并且指添加项i的可取性。因此,当发生动态变化时,一些当前的信息素踪迹将与新环境的特征不兼容,而另一些则将包含有用的信息,这些信息可用于将优化快速地引导到搜索空间的有希望的区域。
    为解决这一问题提出了几项战略,分类如下。

    4.1.1改变后增加多样性

    DOPs中的许多策略依赖于动态变化的检测。检测通常是通过重新评估一个解决方案来执行的,每当其适应度发生变化时,就会检测到动态变化。每当检测到变化以增加多样性时,该类别中的策略执行操作。

    1. 完全重新启动。每当检测到DTSP和DVRP的变化时,ACO算法的信息素轨迹都会以相等的量重新初始化[44、55、65]。这相当于完全重新启动算法,从头优化每个动态更改。由于算法的初始阶段具有很强的探索性,多样性显著增加。然而,所有先前获得的知识都被摧毁了。
    2. 部分重新启动。其他策略的目的只是简单地增加多样性,并在发生变化时保持所获得的知识。例如,Guntsch和Middendorf[54,111]提出了使用本地信息的部分重启策略,例如,考虑到实际发生动态变化的地方的η-策略和τ-策略,例如,为DTSP添加/删除哪些城市。这两种策略的目的都是为了使信息素路径在更靠近被攻击区域的地方得到更高程度的重新初始化。这对应于算法的部分重新启动,因为知识得到了维护,可以加快优化过程。然而,除了检测变化周期外,还需要检测变化的位置。它可能并不总是可用,或者需要大量的计算工作来检测它们。为djsp提出了一种类似的通过信息素路径的部分重启策略[136,73]。
      Angus和Hendtlass[110]使用了旧的信息素轨迹,并根据DTSP的最大信息素轨迹值按比例进行了修改。同样,Eyckelhof和Snoek[65]提出了一种“震动技术”来调节先前的信息素轨迹。利用对数公式对所有信息素路径进行修正,其中接近初始信息素值的信息素值被轻微地扣除,而较高的信息素值被严重地扣除。粒子群优化算法中也采用了同样的振荡技术,该算法使用信息素表作为粒子的通信拓扑[118,119]。然而,这些结果并不像ACO算法那样有希望,ACO算法对图问题更有效。
      上述策略直接通过信息素轨道进行修改。Incontrast,Rand andRiolo[75]使用解构主义技术修复了DKP之前环境的最佳解决方案,因为这种改变变得不可行。在修复过程中,信息素的路径会受到溶液变化的间接影响。这样,就保留了以前环境的部分知识。对于同一个问题,但不同类型的动态变化不影响问题的表现,Baykaso˘glu和Ozsoydan[137]通过在动态变化发生时部分重新启动一部分种群,增强了FA的多样性。
      Montemanni等人。[67]通过将工作日划分为时间片来处理DVRP。基本上,动态问题被分解为一系列静态问题,分别由蚁群算法优化。前一个静态问题的信息素守恒被用来防止从零开始下一个优化问题。使用时间切片,不需要检测变化。但是,算法的性能取决于预定义的时间片数。在[122]中提出了类似的ACO方法,在[135]中提出了PSO方法。Khouadjia等人提出了更多使用时间切片的PSO变化。[128129]。每一个粒子都会跟踪它的最佳解,然后用来形成下一个时间片的初始群。相比之下,[133]中的下一个时间片的初始群由给定半径内的上一个全局最优定义。
      在这里插入图片描述

    4.1.2执行期间保持多样性

    一些策略不一定需要检测变化来增加多样性。在执行过程中保持多样性。实际上,未经修改的ACO算法被应用于DJSSP[74]和二进制编码问题[138,76]。因为信息素蒸发有助于忘记未使用的信息素轨迹,所以当发生动态变化时,它有助于适应过程。另一种方法是从信息素路径中收集统计信息,以检测停滞并重新初始化信息素路径[139]。这种方法被用于上述带有DTSP信息素矩阵的PSO[121]。
    基于信息素蒸发效应,在优化过程中对DTSP和DVRP的信息素蒸发速率ρ进行了自适应[55],加快了自适应速度。其思想是在算法接近停滞行为时提高蒸发率,以更快地消除信息素痕迹。由于自适应方法需要固定的步长;后来提出了自适应蒸发率来解决这个问题[116]。特别地,蒸发率被离散为8个与信息素轨迹相关联的值。蚂蚁负责在每次迭代中选择适当的速率。
    Ankerl和H¨ammerle[125]分别自适应控制信息素路径和启发信息权重的α和β参数。每个蚂蚁使用一组不同的参数,这些参数最初是相同的。这种方法使蚂蚁能够探索搜索空间的不同位置,从而保持多样性。Liu[117]修改了蚁群算法的决策规则,而不是调整控制参数。将基于秩的非线性选择压力函数集成到决策规则中。虽然集成增强了多样性,但它会引入需要优化的新参数。
    与ACO相结合的一个非常流行的策略是移民计划[55,21,112,113,33,127]。一般的想法是引进外来蚂蚁,随机或利用以前环境中最好的蚂蚁来储存信息素的踪迹。这样,多样性得以保持。然而,如果有太多的随机移民被迁移,他们可能会干扰优化过程。

    4.1.3内存方案

    从以前的环境转移知识的另一种方法是使用外部存储器。通常,有希望的解决方案存储在内存中,并在发生动态更改时重用。同样,这种类型的策略需要检测变化来更新内存,甚至修复内存。
    DTSP最流行的ACO之一是基于种群的ACO(P-ACO)[66]。P-ACO保存了用于更新信息素的最佳蚂蚁的记忆。当一个动态变化发生时,记忆中的蚂蚁被启发式地修复,从而信息素值被修改。同样,对于上述的η-策略和τ-策略,启发式修复需要改变的位置。
    基于内存的移民者ACO[37,21,33]使用有限大小的内存来存储几个先前优化过的环境中的最佳代表性解决方案。这个想法是基于目前最好的记忆来产生移民蚂蚁,以同时传递知识和增加多样性。

    4.1.4多总体方法

    使用单独的种群可以自然地增加和保持多样性。其思想是将不同的种群分配到搜索空间的不同区域。
    针对DTSP[36]和DVRP[123,124]提出了一种多群体蚁群算法,其中每个群体使用一个单独的信息素表,试图最大化搜索区域。虽然没有采用显式的方法将菌落划分到不同的区域,但实验结果表明,该方法比单一菌落蚁群算法具有更好的性能。相比之下,在[114115]中提出了多克隆ACO,其中不同的群体(称为种姓)使用相同的信息素表。每个种姓使用不同的参数设置,这些参数设置对应于每个种姓的不同行为,可以覆盖搜索空间的不同位置。在粒子群优化算法中,DVRP采用了类似的思想[120]。
    对于粒子群算法,提出了一种基于岛模型的多群算法。来自不同群体的粒子有规律地迁移到其他群体以保持多样性。文献[134]中引入了一种不同的多群算法,这种算法只在新环境到来时才进行通信。

    4.1.5杂交

    这类策略更强调SI算法与局部搜索方法的混合。通常,由局部搜索增强的算法,称为模因算法,在增加计算时间的代价下,可以提供更好的解决方案。其思想是让主算法为局部搜索提供初始解进行优化。但是由于局部搜索算子产生了长时间的开发,算法需要保持多样性。
    上面描述的P-ACO在[44,126]中得到了改进,其中基于简单和自适应逆的几个局部搜索步骤被应用于迭代最佳蚂蚁。此外,当存储在内存中的所有蚂蚁都相同时,触发的随机移民进入内存会增强多样性。最近,在文献[35]中提出了另一种基于模因的蚁群算法,它在发现新的最优解时使用局部搜索。每当算法进入停滞行为时(通常是由于局部搜索),信息素轨迹被重新初始化为最大值以保持多样性。

    4.2动态连续优化中的SI

    第2.5节描述的MPB是连续空间中DOPs最广泛使用的问题。解决这一问题的关键思想(以及一般的多模态问题,如GDBP)是在搜索空间中定位和跟踪所有峰值(局部最优)。当发生变化时,其中一个局部最优可能成为全局最优。其他时变函数包括Sphere、Ackley、Griewanks、Rastrigin、Rosenbrock、Schwefel,其中从指数分布中选择的随机值在每个维度上加/减。球面和二维Rosenbrock函数是单峰的,而其余的函数是多模的,就像MPB和GDBP一样。其他时变单峰函数包括抛物线函数。
    从表3可以看出,PSO主要用于连续问题。群中的每个粒子都有自己的局部环境知识。如果知识有助于解决动态变化时的问题,它将通过粒子之间的简单相互作用在粒子之间快速传递。这样,粒子的位置将(本质上)更新为全局最优。类似地,其他的SI算法可以帮助解决这个问题,但是使用不同的交互。然而,所有的SI算法在某些方面可能需要一些改进,以摆脱以前的收敛最优,并有效地跟踪新的。
    为解决这一问题提出了若干战略,这些战略分为以下几节。

    4.2.1改变后增加多样性

    类似地,对于上面相应的离散优化范畴,这一范畴中的策略依赖于变化的检测。
    在[198199]中,一种传统的粒子群优化算法被应用于反映简单单峰适应度景观的时变抛物函数。当发生动态变化时,部分填充被随机初始化。

    4.2.2在执行过程中保持多样性

    这类策略使用不同的技术在执行过程中显式地保持多样性,这些技术进一步分组如下。

    1. 特殊机制。受到原子场的启发,Blackwell等人。[97]提出了一种多电荷点群优化算法(mCPSO)和多量子群优化算法(mQSO)。在mCPSO中,每个粒子群中的一部分粒子,称为“带电”粒子,相互排斥并围绕中性粒子旋转。在mQSO中,“量子”粒子在最佳粒子周围随机移动。两种算法都通过重新初始化性能最差的群来改进,只要所有群都收敛以保持多样性[164]。Li等人。[150]将量子粒子(来自mQSO)集成到SPSO以提高其适应能力。此后,SPSO和mQSO在检测到动态变化后通过将粒子转换为量子粒子进行一次迭代而得到进一步改进[146]。[164]中引入的量子原理也应用于物种形成FA(SFA)算法[179]和ACO的连续变化[190]。
      另一个例子是动态环境的BFO [174],其中,每重复执行一次趋化性,每重复执行f_r一次再现,并且每当发生动态变化时执行消除分散。这样,细菌将散布到搜索空间,例如进行探索。
    2. 个人选择。Daneshyari和Yen[145]修改了粒子选择和替换机制,以便选择最多样化的粒子(以Hamming距离测量),并替换位置相近的粒子。Tang等人。[173]提出了一种动态BFO(DBFO),它使用更灵活的选择方案来保持多样性,其中在繁殖期间的选择是以概率的方式进行的,其方式类似于oneusedinas。在[195]中,amodifiedABC(MABC)被提出,它将蜜蜂之间的通讯限制在只有更近的蜜蜂之间。
    3. 操作员选择。提出了一种基于粒子群算法的memetic算法[144],该算法通过自适应选择两个局部搜索算子来保持多样性。
    4. 随机化。Kojima等人。[196]将动态ABC(DABC)算法应用于动态Rastring函数和Rosenbrock函数,在每个搜索阶段使用独立的食物源,在使用阶段采用cauchy分布。
      相比之下,这一类的其他策略则侧重于在优化过程中调整个体的邻域以隐式地保持多样性。例如,由Parrott和Li[102165]提出的基于物种形成的粒子群优化算法(SPSO),在每次迭代中都根据其适应度和距离的某些原则对粒子群进行自适应。在SPSO中,粒子群的数量和大小通过构造一个有序的粒子列表进行自适应调整,并根据其适应度进行排序,空间上紧密的粒子加入到粒子群中。speciationschemewas在物种形成FA(SFA)算法[179]中选择创建子群。
      类似地,PSO[166,101]中引入了由物理学分支导出的复合概念。与SPSO中的“适者优先”原则不同,swarms是基于“最坏优先”原则构建的,但每个复合粒子由三个固定粒子组成。此后,提出了一个相反的版本,其中一个子群是根据“适者为本”原则生成的[167]。
      Janson和Middendorf[162]提出了一种基于动态树的邻域结构的分区层次PSO(PH-PSO)。每个粒子被放置在树的一个节点上,粒子根据它们的适应度按层次排列。Chen等人。[169]在优化过程中,使用蜜蜂生命周期方法根据局部适应度景观动态调整群体大小。Parsopoulos和Vrahatis[193]提出了一种具有收缩因子的统一PSO算法,该算法结合了全局和局部最优PSO变量。
      此外,ACO变量取代了传统的连续离散概率分布,应用于不同的时变函数[191]和GDBG[184185]。通过设置较高的蒸发率,ACO的变化可以适应第4.1节所述的变化。

    4.2.3内存方案

    如上所述,存储方案旨在从先前的搜索转移“有用”的知识,以加速当前的搜索。这种方案也有助于保持多样性。
    要实现内存方案,通常需要外部存档。当检测到动态变化或在三岛模型中发现峰值时,使用存档总体存储良好的解决方案[141]。当差分ABC算法[197]和改进的ABC算法[171]的所用bee阶段发生变化时,最佳解决方案保存在存档中。历史驱动的SFA(HdSFA)[180]算法使用两种类型的存储器:负责存储有关当前环境的信息的短期存储器和负责存储有关先前环境的信息的长期存储器。PSO[181]采用了相同的存储方案。最近,SPSO增强了存储不同物种粒子的记忆能力[168]。

    4.2.4多总体方法

    多群算法是一种分而治之的策略。对每个群体在不同的区域进行搜索意味着搜索空间被划分为多个子空间,每个群体负责搜索一个子空间。这样做,它有几个优点[200]。首先,由于群体在不同区域进行搜索,可以保持全球的多样性。其次,可以同时跟踪多个最优解。第三,任何基于单群方法的方案都可以很容易地扩展到多群方案。根据群的数量,多群策略可以分为以下几类。

    1. 群的静态(或固定)数量。这组策略可以进一步分为两类:竞争型和协作型。对于竞争类型,群体之间相互竞争,即不允许在同一区域内搜索。相反,在协作类型中,允许群在同一区域内搜索并相互协作,即它们可以共享信息。布莱克威尔的mCPSO和mQSO[164]属于竞争类型。每个群都有一个排除半径,以防止子群相互重叠。其他算法也采用了mQSO中排除原理的类似思想,如多swarmmodified AFSO(MAFSO)[176,177]、多swarm FA算法[178,182,183]、多BFO(MBFO)算法[175]、多swarm ABC[188]和k均值聚类ABC(CABC)[189]。一种典型的协同型多暖算法是协同进化群优化(CESO)[157],其中两个异构群相互协作。这两个群体分别遵循拥挤差分进化(CDE)[201]和PSO模型。前者负责保持多样性,后者负责跟踪全局最优解。类似地,在[192155]中采用了双群方法。文[154]中提出了一种带有附加群的进化群协作算法(ESCA)。在ESCA中,使用了三个群并在彼此之间共享信息。
    2. 群的动态数量。根据创建子群的方式,这类策略可以进一步分为两个模型:重组和拆分模型。重组模型通过特定的方式重组个体,每次迭代或当满足特定的标准时,例如基于物种形成的PSO(SPSO)[102,165]和随机重组的多群swarmPSO[194]。Li和Yang[14999]提出的聚类PSO(CPSO)算法在检测到变化时,采用层次聚类方法生成子群。为了避免变化检测,CPSO后来改进了一个新版本,称为CPSOR[98],当粒子总数下降到阈值比率时,随机粒子被引入并聚集成新的群。分裂模型通常在满足某一准则时,通过从一个主群分裂产生子群,例如快速多群优化(FMSO)算法[159]。FMSO从父群开始。每当最好的粒子变得更好时,就会生成一个子群,其中包含最好的粒子和与最好的粒子在给定距离内的粒子。在多群PSO群的自适应数量。为了通过多群方案有效地解决DOPs问题,一个关键问题是调整群的数目[200163164]。对于optima数量不断变化的DOPs来说,这个问题变得更具挑战性。基本思想是在当前群聚时增加群聚,在群聚过多时移除群聚。Blackwell[163]提出了自适应多群优化算法(SAMO),这是第一种基于种群数量的自适应方法。它开始于一个单独的自由群体(例如,一个不收敛的群体)。自由的蜂群逐渐转变成聚集的蜂群。当收敛群的半径小于给定的收敛半径rconv时,对其进行识别。如果没有自由群,则随机生成一个新的自由群。这样,种群数量就能够根据当前种群的状态自适应地变化。文[148]提出了一种自适应多群优化算法(AMSO),它根据两个连续的“检查点”之间的群数差异来调整群数。提出了一种多群AFSO算法[172],当父群发现新的峰值时,生成子群。这群孩子追踪山峰的位置。最近,使用一个收集算法行为变化的启发式信息的数据库对群的数量进行了调整,以更好地跟踪多个最优值。Nseef等人。[170]提出了一种多群体ABC算法。根据动态变化强度自适应地保持菌落数。
      群的自适应数量。为了通过多群方案有效地解决DOPs问题,一个关键问题是调整群的数目[200163164]。对于optima数量不断变化的DOPs来说,这个问题变得更具挑战性。基本思想是在当前群聚时增加群聚,在群聚过多时移除群聚。Blackwell[163]提出了自适应多群优化算法(SAMO),这是第一种基于种群数量的自适应方法。它开始于一个单独的自由群体(例如,一个不收敛的群体)。自由的蜂群逐渐转变成聚集的蜂群。当收敛群的半径小于给定的收敛半径rconv时,对其进行识别。如果没有自由群,则随机生成一个新的自由群。这样,种群数量就能够根据当前种群的状态自适应地变化。文[148]提出了一种自适应多群优化算法(AMSO),它根据两个连续的“检查点”之间的群数差异来调整群数。提出了一种多群AFSO算法[172],当父群发现新的峰值时,生成子群。这群孩子追踪山峰的位置。最近,使用一个收集算法行为变化的启发式信息的数据库对群的数量进行了调整,以更好地跟踪多个最优值。Nseef等人。[170]提出了一种多群体ABC算法。根据动态变化强度自适应地保持菌落数。
    3. 群的自适应数量。为了通过多群方案有效地解决DOPs问题,一个关键问题是调整群的数目[200163164]。对于optima数量不断变化的DOPs来说,这个问题变得更具挑战性。基本思想是在当前群聚时增加群聚,在群聚过多时移除群聚。Blackwell[163]提出了自适应多群优化算法(SAMO),这是第一种基于种群数量的自适应方法。它开始于一个单独的自由群体(例如,一个不收敛的群体)。自由的蜂群逐渐转变成聚集的蜂群。当收敛群的半径小于给定的收敛半径rconv时,对其进行识别。如果没有自由群,则随机生成一个新的自由群。这样,种群数量就能够根据当前种群的状态自适应地变化。文[148]提出了一种自适应多群优化算法(AMSO),它根据两个连续的“检查点”之间的群数差异来调整群数。提出了一种多群AFSO算法[172],当父群发现新的峰值时,生成子群。这群孩子追踪山峰的位置。最近,使用一个收集算法行为变化的启发式信息的数据库对群的数量进行了调整,以更好地跟踪多个最优值。Nseef等人。[170]提出了一种多群体ABC算法。根据动态变化强度自适应地保持菌落数。

    4.2.5杂交

    与不同领域知识的杂交,如遗传算法、差分进化或其他元启发式方法,如微生物生命、模糊、细胞自动机等,也是一个重要的研究课题。
    1.与其他领域知识的杂交。例如,多策略集成PSO(MEPSO)[161]使用高斯局部搜索和差分变异进行探索和开发。PSO算法中引入了动态宏变异算子[160]。基于PSO的memetic算法[142]使用了环形拓扑结构和模糊认知。在[143]中还使用了具有多个局部搜索的模糊认知。改进的mQSO算法(mQSOE)[186]使用ACO中使用的蒸发机制来惩罚每个文章过去创建的最佳位置的适应度值。
    2. 与其他元启发式方法的杂交。Hashemi和Meybodi[140156]提出了一种PSO与元胞自动机的混合模型来解决DOPs问题,其中搜索空间嵌入了元胞自动机并被分割成若干个单元。每个单元只允许包含指定数量的粒子,以防止多样性丢失。Rezazadeh等人。[153]提出了11种自适应PSO算法。该算法采用模糊C-均值机制对排除半径和惯性权重参数进行自适应。Karimi等人。从微生物生命中获得灵感的微粒,可以再生新的婴儿微粒来代替旧的微粒。
    4.3动态约束优化中的SI
    动态约束优化问题具有挑战性,因为它们常常影响算法解的可行性。刘[77]将该问题转化为一系列不同时期的静态约束优化问题。每一个设计的静态问题都基于原始目标及其约束条件,分配一个个体适应度函数。然后将粒子群优化算法应用于每个设计问题,而无需考虑粒子的可行性。实验结果表明,该算法能够在一组基准问题上找到最优解。
    不同的是,Dewan和Nayak[202]使用基于惩罚的函数和PSO来处理不可行的粒子,而针对可行粒子引入了新类型的粒子进行局部搜索。该算法在已知的基准集上进行了测试,并与其他算法的结果进行了比较。PSO算法的结果与EAs算法相比具有很强的竞争力。
    Yin和Sun[203]提出了一种基于广义动态约束满足策略的自适应变异PSO(AMPSO)算法。AMPSO中的变异算子根据一个自适应变化的变异概率,应用于群体的活动粒子(例如,在多次迭代中没有进展的粒子)或不太适合的粒子。
    Bu等人。[56]应用SPSO的变量和一组策略来定位和跟踪可行区域。这些策略包括:基于梯度的修复、自适应局部搜索、约束处理、记忆和预测策略。

    4.4动态多目标优化中的SI

    动态多目标优化问题比单目标优化问题更具挑战性,因为需要跟踪一组Pareto最优解,而不是一个单一的最优解。Wei和Wang[204]提出了一种基于超矩形搜索的PSO算法。该算法利用超矩形搜索来近似预测下一个最优解。在一个已知的基准集上的实验结果表明,PSO能够有效地定位和跟踪Pareto最优解集。
    不同的是,Wei和Jia[205]将一种新的点选择策略与PSO相结合,生成下一个时间间隔的初始群,作为一种重启策略。此外,还引入了一种基于吸引的局部搜索算子来利用群体的信息。
    提出了一种多群PSO算法,其中每个群独立求解单个目标函数,并与其他群通信以传递知识[206207]。为了保持多样性,每当哨兵粒子检测到动态变化时,一定比例的蜂群会重新初始化。

    4.5动态分类中的SI

    将动态连续优化中提出的几种PSO算法,如QPSO、CPSO和CCPSO,应用于训练分类问题中的有监督前馈神经网络[208209]。动态变化训练发生在决策边界,称为概念漂移。由于神经网络的训练是一个连续优化问题,因此直接应用了上述算法。实验结果表明,QPSO、CPSO和CCPSO算法的分类误差比采用重启和梯度下降算法(如反向传播算法)的PSO算法好。

    4.6讨论

    每一种适应动态环境的策略都有其优点和局限性。例如,分集保持/增加策略可以很好地解决分集丢失问题,但分集增加的最佳频率很难确定,也很难设计有效的分集保持机制。内存方案能够帮助算法快速适应新的环境,但在发生重大变化的环境中却没有帮助。多群策略能够保持全局水平上的多样性,但最优群数和每个群的搜索区域很难配置。
    由于上述不同策略的优势和局限性,在大多数研究中通常会考虑多种策略。例如,在许多多群算法中,通常使用分集保持和存储策略来提高性能。无论采用何种策略,在处理环境变化时都应考虑知识转移与多样性保持的平衡。

    五.SI在动态环境中的实际应用

    在本节中,将对SIDO中出现的实际应用程序进行回顾,并将其分为离散应用程序和连续应用程序。“现实世界的应用程序”与表2和表3中讨论的应用程序之间的区别是相当任意的[210]。在本文中,表2和表3中讨论的应用集中在那些旨在模拟现实世界问题或环境(例如,多目标或约束处理)的著名模型上。这样的模型可以提供这样的应用程序是否可以在现实世界中工作的指示。另一方面,下面几节讨论的实际应用程序侧重于在某些行业中使用的应用程序或在实际数据上进行测试的应用程序。

    5.1离散应用

    蚁群算法在网络路由领域得到了广泛的研究。通常,网络中的路由问题被定义为定义路径流以转发传入的数据流量,从而使整个网络性能最大化的问题。根据12个网络的处理和传输组件的特性、业务流模式和预期交付的性能,可以定义不同类型的路由问题。主要有两类已应用ACO的网络路由问题:有线,例如有线尽力而为网络[211、212、213、214、215]和有线服务质量(QoS)网络[216、217、218、214、219、220]以及无线,例如移动自组织网络[221、222、223、224、225]。通信算法仅仅依赖于蚁群算法的自适应能力。
    Liu等人。[226]提出了一种基于AFSO的组播路由协议,解决了QoS网络的时延和带宽约束问题。仿真结果表明,AFSO在实时多媒体传输网络中具有良好的性能和鲁棒性。还研究了移动ad hoc网络的ABC算法[227,228]和对等网络的PSO算法[229,230]。
    Vogel等人。[231]提出了一种ACO算法来处理生产系统中的动态变化。维护位置操作信息素矩阵以存储操作。每当新作业到达时,信息素值都会重新初始化。他们在实际数据采集上的实验表明,所提出的ACO方法优于手动方法和传统的优先级规则方法。相比之下,ACO方法的性能优于EA方法。
    Silva和Runkler[68]使用传统的ACO算法解决了提款机问题。基本上,问题是,一家现金物流公司需要根据其资金水平为法兰克福一家特定银行的多台提款机装满现金容器。结果表明,考虑到取款机与取款机之间的距离,蚁群算法能够在最短的运行时间内自动调用解。但是,没有与任何其他自动或手动方法进行比较。
    Nakrani和Tovey[232]使用了一种新的bee算法(例如,蜜蜂算法开发)在internet服务器群中进行动态服务器分配。在他们的模型中,觅食蜜蜂和花朵补丁分别表示internet服务器群中的服务器和HTTP动态请求队列。他们在一个拥有两台和三台虚拟服务器的主机中心(hosting center)的案例中的实验结果表明,蜜蜂算法由于其自适应能力,比其他传统算法表现得更好,特别是在高度动态和不可预测的互联网环境中。
    Triwate和Luangpaiboon[233]应用了bee算法(例如,bee算法开发)来最小化动态多区域调度系统的不平衡,其中每个bee代表一个调度模式。模拟研究基于泰国当地运输公司的真实数据。作者的结论是,bee算法在小问题上很快达到最优,但在中、大问题上需要更多的时间。
    韦德等人。[234]使用bee算法(例如,BeeHive算法开发)在交通堵塞和拥挤程度较低的道路上对车辆进行路线规划,以最小化运输时间。考虑了德国东部鲁尔区的拓扑道路数据,生成了几个交通场景。与传统的最短路径算法(如Dijkstra算法)的比较表明,蜂窝算法具有更好的拥塞处理能力。这是因为蜂巢算法考虑了问题的时间链接,动态地在不同的路径上选择车辆,而Dijkstra算法总是选择最短的路径。作者表明,经过一段时间后,基于Dijkstra的路由会出现严重的拥塞,而基于Bee的路由仍然是无拥塞的。
    Sulaiman等人。[235]用FA求解了配电网中分布式发电机组的最优配置和规模问题。实验采用IEEE 69总线分布式测试系统。研究结果表明,确定分布式发电机组的最佳位置和尺寸,可以降低系统的功率损耗,改善系统的电压分布。此外,将所提出的FA与EA进行比较,结果具有可比性。
    Teodorovi’c和Dell’Orco[236]将带有模糊逻辑的bee算法(例如,蜂群优化开发)应用于骑乘匹配问题。问题是在给定的时间段内优化车辆和乘客的路线和调度。这种应用中的不确定性是由乘客可能造成的延误或交通拥挤引起的。作者考虑了来自意大利小城市特兰尼的97名旅行者的乘车需求。该算法的结果是非常有前途的。
    加西亚等人。[237]利用蚁群算法解决了具有避障功能的移动机器人的路径规划问题。工作空间(搜索空间)被离散为50×50个节点的矩阵,移动机器人可以在其中导航和建立路径。粒子群算法用于移动障碍物的相同问题[238]。
    Li等人。[239]将离散型粒子群算法应用于协作OFDMA系统中的资源分配问题,以最大化多业务下所有移动台的平均效用。利用相邻帧之间的相关性来传递知识。结果表明,知识转移显著降低了计算复杂度,在效用最大化方面取得了较好的效果。
    Hsu[240]将粒子群优化算法与基于事件的启发式算法相结合,同时解决了两个重要的海滨作业规划问题,即泊位分配和码头起重机分配问题。该方法的核心思想是支持起重机内部变量的分配,而不是时不变的。这样,就可以利用码头起重机的分配,因为它们可以进行相应的调整。
    伊顿等人。[241]当列车发生延误时,使用ACO在交叉口和车站重新安排列车。在原不可行调度的基础上,利用路径保持算法生成了一个新的可行调度。

    5.2连续应用

    动态经济调度问题已被BFO[242]、PSO[243、244、245、246]、FA[247]、AFSO[248]和ABC算法[249、250、251、252、253]等SI算法广泛研究。此外,混合SFLA算法[254]的性能优于基于PSO和ABC的算法。DED问题的主要目标是在不同时违反一系列安全和效率约束的情况下降低电力系统的运行成本。
    Niknam等人。[255]使用蜜蜂算法(例如蜜蜂交配优化开发)来求解动态最优功率流4,并最小化系统总发电成本。提出的bee算法不同于bee算法的原始发展,因为它使用变异算子来增加种群多样性。在14、30和118总线测试系统上的实验结果表明,这种变异提高了传统bee算法的质量。
    Tang等人。[256257]提出了一种求解动态负荷下最优潮流问题的BFO算法。BFO的复制过程使用基于轮盘赌方法的选择方案来保持多样性。为了避免太多的随机性,没有考虑分散和消除过程。实验采用IEEE 30和118总线测试系统。将该算法与传统的BFO算法和PSO算法在三种不同的负载变化水平上进行了比较,显示了良好的性能。
    Takano等人。[258]使用ABC算法在动态灾害环境中协调救援人员,例如地震发生后的城市。算法被修改为只与附近的蜜蜂通信。在机器人对焦模拟系统上的实验表明,ABC可以快速地救出所有的受害者。
    采用FA[259]和PSO[260]对自动调压系统的比例积分微分控制器进行了整定。控制器的优化整定是基于实际电力系统运行的时变性。通过比较最近的FA算法和PSO算法,发现前者比后者更具鲁棒性。BFO[261]也被用于控制器的调谐,比EA更加健壮和高效。
    Gomes[262263]使用PSO和FA算法作为结构质量优化的引擎。形状和尺寸的结构优化被认为是高度非线性的。该问题包含可能影响适应度函数的动态约束。因此,惩罚函数技术被用来处理违规行为。考虑了三个10、37和128桁架杆结构的算例,结果表明FA算法的性能略低于PSO算法,但这两种SI算法的性能都优于传统的优化方法。
    ACO和ABC被应用于动态负载平衡问题[264]。该问题的主要目标是在系统之间找到工作负载的最佳分配,例如减少繁忙资源的负载并将其转移到空闲资源。在一个由四台机器组成的集群和Amazon EC2云上的实验研究表明,ABC比ACO和其他传统算法更快。
    应用BFO算法确定了二维移动障碍物空间中从当前位置到目标位置的最短可行路径[265]。该算法能够避开障碍物并找到一条通向目标位置的路径。类似地,PSO算法也证明了它们能够通过避开移动障碍物来规划机器人的最优路径[266267268]。
    给水管网污染源辨识问题是一个非线性规划问题。该问题的目的是根据到目前为止的观测数据来寻找污染物的位置和时间历程。Liu等人。[269]使用基于多群的PSO算法来解决这个问题。

    六.结论和今后的工作

    本文试图对SIDO在多个web搜索引擎中的相关工作进行综述。SIDO最重要的应用分为连续问题和离散问题。对用于增强SI算法以应对动态变化的策略进行了分组和广泛讨论。此外,本文还回顾了SIDO的现实问题。
    本文的综述如下。搜索是从五个公认的科学数据库进行的,即IEEExplore5、科学指导6、SpringerLink 7,scopus8和Google scholar9为ACO使用“蚁群优化”和(“动态环境”或“动态优化”或“动态函数”或“时变”或“动态问题”或“动态路由”或“动态调度”或“动态多目标”或“动态约束”)等术语。同样的搜索格式被用在粒子群优化的粒子群优化算法中,同样的搜索格式也被用在其他的粒子群优化算法中。检索到的书目包括期刊文章、会议论文、书籍章节和技术报告。然后,将结果分类为:(a)图3中的SI算法和(b)图4中的发布年份。
    从图3可以看出,与SIDO中的其他SI算法相比,ACO和PSO引起了更多的关注。这是很自然的,因为它们比其他SI算法提出得更早。这也可能是他们比最近提出的SI算法更有效的情况。这是因为在许多情况下,SI算法使用这些算法的核心组件。例如,在ABC、AFSO、FA和BFO算法中,粒子群优化算法引入的粒子局部最优位置分量在许多情况下被用作增强策略。从图4可以看出,SIDO领域大致在2001年开始增长,到2009年逐渐增长。从那时起,这一领域在出版物数量上有起有落。
    一般来说,所有的SI算法都主要应用于它们最初发展起来的相应平稳优化问题的动态版本。例如,ACO主要用于建模的动态离散问题因为它是一个图搜索算法。此外,当环境变化相似时,集成到不同SI算法中的增强策略通常会提高它们的性能。最后,在处理DOPs时,局部搜索算子是SI算法的核心组成部分。SI算法执行全局优化,并且它们的输出不精确。因此,局部搜索算子可以显著提高输出的质量。然而,在SI算法中集成局部搜索的方式必须不会显著增加计算时间或浪费评估[35]。
    在这里插入图片描述

    虽然SIDO的研究显示出了显著的增长,但它仍有几个方面可以为进一步发展SIDO领域做出贡献,总结如下:
    1.实验协议:由于目前还没有达成一致的计算实验协议,可能有必要为不同的问题类别定义不同的实验协议,例如连续、离散和约束问题,因为所用方法和搜索空间的不同特点。
    2. 基准生成器:动态多目标和动态约束优化领域还很年轻。使用的大多数基准生成器只是静态实例的扩展。可能有必要开发基准生成器,特别是针对这些最新领域,以比较开发的新算法。
    3. 避免变化检测:通过重新评估个体的变化检测方法不能总是保证成功检测,特别是在变化不影响适应度环境中当前解决方案的情况下。这种情况可能发生在动态环境中,其中一部分健身景观发生变化。此外,这种检测方法永远不会在有噪声的动态环境中工作,因为噪声会被误解为每次重新评估操作中的变化。因此,为了更有效地处理变更,需要避免变更检测。
    4. 模拟现实世界的情景:考虑动态优化中吸引较少兴趣的其他研究领域,并模拟许多现实世界的情景,如约束DOPs、动态多目标问题甚至动态约束多目标问题,将是有趣的。
    5. 考虑到其他的前瞻性:跟踪移动最优(TMO)框架通常用于SIDO来处理DOPs。最近,一种新的DOPs视角被建立,称为随时间鲁棒优化(robust optimization over time,ROOT),其目标是找到随时间鲁棒的解链[46]。特别是,当一个解决方案的质量在预定义的时间间隔内可以被不断变化的环境所接受时,该解决方案是健壮的。实际上,调度问题和车辆路径问题都具有时间链接性。因此,TMO框架可能不是最好的选择,因为当前提高性能的决策可能会影响将来的性能。因此,从长远来看,整体性能可能会降低。到目前为止,ROOT只与PSO集成。
    6. 算法选择:到目前为止,在过去的30年里,已经有很多SI算法被提出。对于一个具体的问题,大多数读者都不知道该选择什么样的算法。这是因为做出正确的选择又是一个优化问题。经验、线索和基于错误的选择仍然是做出选择的主要方式。因此,寻找最适合于给定问题或具有某种性质的问题的正确算法,也是SIDO未来感兴趣的课题。
    7. 理论发展:通常,由于SI算法或一般的元启发式算法的数学挑战,DOPs中算法的性能是通过经验而不是理论来分析的。虽然已有理论研究,但研究领域还很有限。为了深入了解SI算法在DOPs中工作的原因和方式,SIDO的理论发展应该得到显著的提高。

    展开全文
  • 岗位描述负责公司智能配送算法的开发。基于先进运筹优化理论结合实际场景和一线业务需求,联接信息系统,开发适合本公司的智能分单和路径规划算法。负责智能配送算法的落地并不断迭代...
        

    640?wx_fmt=png


    岗位描述


    1. 负责公司智能配送算法的开发。基于先进运筹优化理论结合实际场景和一线业务需求,联接信息系统,开发适合本公司的智能分单和路径规划算法。

    2. 负责智能配送算法的落地并不断迭代,保证实际应用的有效性与高效率。在算法应用的过程中不断收集一线的反馈,并及时、客观地分析反馈内容,不断改进算法,消除理论和实际的差距,保证算法可用性的同时提升算法性能。

    3. 利用现有海量数据进行数据分析与处理,在此基础上不断优化模型设计、调整参数、加速计算效率。


    职位要求


    1. 管理科学、工业工程、计算机、数学或相关专业硕士及以上学历,有优秀运筹学和数学建模基础优先,有物流、供应链相关行业工作经验优先;

    2. 熟悉常见的运筹学问题(如 TSP 问题、 VRP 问题、 设施选址问题、 网络优化问题等)的建模;了解领域内常用算法,包括启发式算法(如遗传算法、神经网络算法、领域搜索算法等)和精确求解算法(如分支定价算法、切平面算法、列生成算法等);

    3. 编程基础扎实,熟练使用 python;具备一定数据库、网络爬虫、Linux 系统操

      作基础;熟悉常用优化求解器(如 CPLEX、 GUROBI 等)的使用;

    4. 具备较强的业务理解能力和数学建模能力、算法实现能力;

    5. 具备较强责任心和学习能力,积极主动。


    其他


    工作地点: 清华大学-大马鹿智慧物流实验室(北京市海淀区双清路 77 号双清大厦)。

    待遇面议,能者从优。


    有意者请将简历投递至邮箱:mxy008@ddchuansong.com

    邮件命名方式:投递职位-姓名


    附公司简介


    大马鹿(原名叮咚传送),成立于 2016 年,由名企高管、学术精英等复合高素质团队发起创立,致力于打造基于智能算法调度的同城极速低价物流。公司目前处于 A+轮融资,已获经纬中国、梅花创投、洪泰基金等数家知名机构投资。公司拥有自主算法研发团队和物流运营团队逾五百人,已开拓了北京、上海、深圳等一线城市,并于 2018 年与清华大学工业工程系合作成立智慧物流实验室。公司以推动新一代城市物流体验为使命,利用自身技术优势,创立了结合 AI的城市中去仓化、智能调度的新型同城配送模式。大马鹿是利用“互联网技术+智能算法”实现同城 2-5 小时极速、低价、安全、精准送达的智能物流平台。货品实时的路径推送、透明化的载运人、灵活的用户路由更改、可追溯的异常拦截等, 给用户更加安心、便捷的服务体验。


    大马鹿旨在打造成一家在新零售背景下的业内一流的新型物流服务提供商, 帮助众多电商平台在优化物流配送成本的同时提升 4-6 倍的物流时效,让更多的消费者享受到 “半日达”、“限时达”、“准时达”等超高性价比的物流服务体验。


    640?wx_fmt=png640?wx_fmt=jpeg

    展开全文
  • 在此背景下,确保人工智能的核心——深度学习算法具有可靠的安全性和鲁棒性至关重要。 然而,近年来研究者发现,深度学习模型存在着易受对抗样本攻击的安全隐患。攻击者可以通过向良性数据中添加特定的扰动,生成...

    2020-05-19 19:52:46

     

    任奎:人工智能算法安全浅析——深度学习中的对抗攻击与防御

    任奎

    随着计算机产业发展带来的计算性能与处理能力的大幅提高,人工智能在音视频识别、自然语言处理和博弈论等领域得到了广泛应用。在此背景下,确保人工智能的核心——深度学习算法具有可靠的安全性和鲁棒性至关重要。

     

    然而,近年来研究者发现,深度学习模型存在着易受对抗样本攻击的安全隐患。攻击者可以通过向良性数据中添加特定的扰动,生成对抗样本。附加轻微扰动的对抗样本不会影响人类的判断,却会使深度学习模型产生错误结果。同时,对抗攻击在自动驾驶等场景中的成功实施更加表明了对抗攻击在现实世界中的可行性。因此 有关对抗攻击和对抗防御技术的研究,引起了机器学习和安全领域研究者越来越多的关注。

     

    本文将围绕深度学习对抗攻击和对抗防御领域中最前沿的研究成果,探讨对抗攻击和防御技术的理论基础、经典算法,以及在工业领域的实际部署等研究与应用前沿。

     

    深度学习的对抗性攻击技术

     

    根据攻击者可获得的信息不同,可将威胁模型划分成白盒、灰盒和黑盒攻击三类(见图1)。白盒攻击下,攻击者可以获得目标模型的全部信息;灰盒攻击下,攻击者仅可获取模型的结构信息但无法获得模型参数,有模型的查询权限;黑盒攻击下,攻击者仅拥有模型的查询权限。多数攻击算法都是为白盒模型设计的,但是由于对抗样本在模型之间具有一定的传递性,它们同样适用于灰盒模型和黑盒模型。

    任奎:人工智能算法安全浅析——深度学习中的对抗攻击与防御

    图 1 对抗攻击的爆发

     

    任奎:人工智能算法安全浅析——深度学习中的对抗攻击与防御

     

     

    上述提到的攻击算法中,攻击者要为每个样本分别生成其对应的对抗扰动,该对抗扰动不会在良性样本之间传递。那么是否存在一种通用的扰动,使附加该扰动的良性样本都可以欺骗某一特定神经网络?通用对抗攻击算法通过使用所有良性样本对全局扰动进行迭代更新,从而生成对大多样本有效的统一扰动。在每次迭代中,对于附加了当前扰动无法欺骗模型的良性样本,将会为其求解一个类似于L-BFGS的优化问题,以找到该样本得以欺骗模型所需的最小附加扰动。这一附加扰动将被添加到当前全局扰动中,对全局扰动进行一次更新。最终,附加该全局扰动的大多数良性样本均可欺骗神经网络。实验表明,这种简单的迭代算法可以有效地攻击深度神经网络,例如CaffeNet、GoogleNet、VGG和ResNet等。出乎意料的是,这种可在不同样本中传递的扰动同时可以应用到其他不同模型中,例如在VGG上 制作的通用扰动在其他模型上也可以达到53%以 上的攻击成功率。

     

    尽管PGD和C&W等对抗攻击算法在数字领域非常有效,但将其扩展到物理世界仍然需要克服两个关键问题。第一个问题是,环境噪声和自然变化将破坏数字空间中计算出的对抗性扰动。例如模糊、噪声和JPEG编码等会对对抗性攻击的破坏率超过80%。第二个问题是,在现实世界中,攻击者仅能在特定物体上添加扰动,而无法对整个环境中的背景添加扰动。Athalye等提出了EoT算法来解决第一个问题。EoT算法不直接使用理想数字域中计算出的梯度用于生成对抗扰动,而 是在样本上添加了一组随机噪声,然后对加入这些噪声的样本计算梯度,用这些梯度的平均值生成对抗扰动。在基于梯度的攻击算法(如FGSM和PGD)中采用这种平均梯度,可以提高生成的对抗样本的鲁棒性。Eykholt等提出了一种掩模变换来分离背景和目标,从而可以将对抗性扰动限制在目标区域内,解决了第二个问题。该方法成功地在现实世界的交通标志上生成了可打印的对抗性扰动,其总体攻击成功率达到80%以上。

     

    除了图片分类任务,如图1所示图像分割、3D识别、音频识别和强化学习等工业领域也会受到对抗攻击的影响。

     

    在3D识别领域,PointNet、PointNet++和 DGCNN等基于点云的分类分割模型已被证明易受到对抗攻击的影响。Zheng等提出了基于丢弃点云中关键点的攻击方法。该方法通过将点移动到点云的质心,近似计算每个点对分类结果的贡献,然后通过丢弃具有较大贡献的点来欺骗神经网络。随着一定数量的高贡献点被丢弃,PointNet、PointNet++和DGCNN的分类精度显著降低。

     

    在音频识别领域,Carlini和Wagner通过对C&W损耗函数的优化,成功地构建了高质量的音频对抗性样本。对于任何音频信号,只要在DeepSpeech上对音频信号的1%进行对抗性干扰,即可在其对应的文本翻译中最多影响50个单词。

     

    在文本识别领域,Liang等提出了针对文本 分类任务的攻击策略。攻击者首先确定影响分类结果最重要的文本项,然后对这些重要文本项采用插入、删除、交换、字符替换和单词替换等扰动措施。实验表明,这种攻击可以成功地欺骗一 些基于DNN的文本分类器。

     

    深度学习的对抗性防御技术

     

    对抗防御可以分为启发式防御和可证明式防御两类。启发式防御算法由研究者通过实验获得,它们在实践中可以做到对一些特定的对抗攻击算 法具有良好的防御性能,但没有对防御性能给出理论性保障;可证明式防御通过理论证明,可以计算出在特定对抗攻击算法攻击下模型的最低准确度。

     

    对抗训练试图通过将对抗样本纳入训练阶段来提高模型的鲁棒性,是目前为止性能最好的启发式防御算法。Goodfellow等首先提出对抗训练,他们使用良性样本和通过FGSM算法生成的对抗样本一起训练神经网络,用于增强神经网络的鲁棒性;接着,提出了使用由PGD算法生成的对抗样本进行对抗训练的方法。根据实验结果,PGD对抗训练可在MNIST、CIFAR-10和ImageNet等多个数据集上,在各种L∞攻击下获得最高的准确 度。但是,由于生成PGD对抗样本需要大量计算成本,因此PGD对抗训练不是一种有效率的防御措施。FGSM算法可以和随机启动结合,这样能高效地生成更多对抗样本用于对抗训练,从而提高模型鲁棒性。为了解决模型易受到黑盒攻击问题,提出了集成对抗训练方法。该方法首先训练多个具有不同网络结构模型,然后同时针对这些不同的模型生成对抗样本,并将其用于对抗训练。这种方法增加了用于对抗训练的对抗样本的多样 性,从而增强了针对从其他模型转移过来的对抗样本的鲁棒性。Lee等提出使用生成对抗网络进行对抗训练,其中生成器用于生成对抗样本,这些生成器生成的对抗样本将与良性样本一起用于训练鲁棒分类器。虽然没有给出理论证明,但研究表明对抗训练在现阶段是对抗攻击最有效的防御手段之一。

     

    随机化也是启发式防御的一种,它通过在模型训练或使用阶段加入随机操作,从而减轻对抗性扰动对模型性能的影响。Xie等在图像输入神经网络前先对图像进行随机变换,从而减轻对抗扰动的效果。这种方法在黑盒攻击下获得了卓越性能,但在白盒攻击中可被EoT算法成功攻击。

     

    去噪属于启发式防御,它的主要目的是减轻或去除对抗扰动,从而降低对抗扰动的功能。去噪防御根据降噪目标不同,可以分为输入降噪和特征降噪两类。输入降噪试图从输入中部分或完全消除对抗扰动。Xu等采用减少色彩深度和模糊图像的方法对图像进行压缩,降低图片自由度,从而消除对抗扰动。通过比较模型对于原始图片与压缩后的图片预测结果的差异,来判断原始输 入是否是对抗样本。Shen等使用生成对抗网络对输入数据进行去噪。该方法将训练一个用于去噪的生成器,其输入是良性样本或对抗样本,其输出是经去噪后的样本。Meng等使用自动编码器技术对输入数据进行去噪。

     

    以上所有介绍的防御都是启发式防御,这意味着这些防御的有效性只在实验上得到验证,而没有在理论上得到证明,如果无法计算理论上的错误率,这些启发式防御可能会被未来的新攻击所打破。因此许多研究者致力于探索可证明的防御方法,在一类定义明确的攻击下,这些方法始终能保持一定的准确性。目前有代表性的可证明式算法有基于半正定规划的可证明式防御、基于对偶方法的可证明式防御、分布稳健性证明、稀疏权重DNN、基于KNN的防御,以及基于贝叶斯模型的防御等。然而根据现有的实验结果,可证明式防御措施的实际性能仍然比对抗训练的性能差很多。

     

    开放性问题与未来发展

     

    在对抗攻击与对抗防御的研究领域中,仍有许多尚未解决的挑战。

     

    首先,对抗样本背后的因果关系这一问题并未得到回答。早期对这一问题的研究将对抗样本的出现归因于模型结构和学习方法,研究者认为适当的策略和网络结构将显著提高对抗样本的鲁棒性。研究者沿着这种思路尝试过一些探索,特别是与模糊梯度相关的研究,然而实际上这可能是一种不太合理的研究方向。相反,最近的研究发现,对抗样本的出现更可能是数据维度较高和 训练数据不足导致的。

     

    任奎:人工智能算法安全浅析——深度学习中的对抗攻击与防御

     

     

    最后,是否存在稳健又高效率的对抗防御算法?我们仍然没有发现一种防御技术能够很好地平衡防御效果和运算效率。在有效性方面,对抗性训练表现出最好的性能,但计算成本很高。在效率方面,许多基于随机和去噪的防御系统的配置只需几秒钟。然而,最近的许多论文表明这些防御方法并没有他们声称的那样有效。可证明防御理论上为实现对抗防御指明了一条道路,但其 准确性和有效性都远远不能满足实际要求。

     

    对于该领域的未来发展,我们认为对抗攻击的研究趋势主要包括两个方向。第一个是设计更有效、更强大的攻击用来评估新兴的防御系统,这个方向的重要性很直观,我们希望在潜在攻击者之前评估所有的风险。第二个是实现物理世界中的对抗攻击。以前对该研究主题的主要疑问是那些对抗性攻击是否会对物理世界形成真正 威胁。一些研究人员怀疑由于某些环境因素的影响,最初在数字空间中设计的对抗性攻击将无效。Athalye等首先向良性样本中添加随机的噪音模拟物理世界的环境因素,并计算这些噪音样本上产 生的梯度期望,进而实现物理世界的对抗攻击。Eykholt等进一步考虑了掩膜和制造误差从而实现了交通标志的对抗性扰动,这些都验证了物理对抗样本的存在。

     

    在防御方面,由于大多数启发式防御都无法防御自适应白盒攻击,因此研究者开始关注可证明的防御,这种防御是指无论攻击者采用哪种攻击方式,可证明防御都可以在一定程度下保证防御性能。但是到目前为止,可扩展性是目前大多数可证明防御所普遍具有的问题。例如区间界分析是最近流行的证明式防御方法,但是它不能扩展到非常深的神经网络和大型数据集。这主要是因为,攻击算法只要针对某一类防御生效即可, 然而一个有效的防御算法则需要去防御所有可能的攻击手段。

     

    结束语

     

    近两年来,针对深度学习算法的对抗攻击和防御技术迅速发展。然而,对于对抗样本的成因、一般鲁棒边界的存在等理论问题还没有找到答案,需要深入研究。不仅如此,在实际安全应用中,还没有一套有效且通用的对抗防御技术框架与方法,目前的对抗性训练防御技术,在实际部署中计算成本仍然太高。许多启发式防御仍缺乏进一步验证,还不能抵御自适应性白盒攻击者的攻击。简而言之,要达到有效防御目标,不仅需要深度 学习算法安全性理论的突破,还需要将系统框架、安全测试、环境适配等多个方面的安全技术相结合,才能推动深度学习对抗性安全的跨越式发展。

     

    (参考文献略)

     

    选自《中国人工智能学会通讯》

    2020年 第10卷 第4期 人工智能与安全专题

    展开全文
  • 鹰眸安全帽识别系统智能分析和拓扑图 鹰眸安全帽识别系统主要用于石化、煤炭、建筑等行业的作业区域,也可用于对作业规范性要求较高的电力、铁路等行业。系统的核心理念是运用当前先进的DEEP LEARNING算法识别视频...
  • 目录一、阿里云天池(一)算法大赛(二)创新应用大赛(三)程序设计大赛(四)学习赛(五)可视化大赛(六)诸神之战二、和鲸社区三、2020华为精英挑战赛四、百度之星五、2020腾讯广告算法大赛六、FlyAI竞赛七、...
  • 进化多目标优化算法学习综述

    千次阅读 2019-03-13 17:19:23
    最初,多目标优化问题→通过加权等方式转化为单目标问题→用数学规划求解。 这样每次只能得到一种权值下的最优解。而且MOP的目标函数、约束函数可能是非线性、不可谓、不连续的,传统的数学规划效率低,并且它们...
  • 本书介绍电力系统问题的综合优化方法和算法,以及它们在MATLAB中的代码编写。 This book presents integrated optimization methods and algorithms for power system problems along with their codes in MATLAB. ...
  • 购物网站用算法来为你推荐商品,点评网站用算法来帮你选择餐馆,GPS 系统算法来帮你选择好的路线,公司用算法来选择求职者……当机器最终学会如何学习时,将会发生什么? 不同于传统算法,现在悄然主导我们生活的...
  • 2020年9月10日,Top Talk邀请到了清华大学自动化系莫一林副教授,请他带来题为《信息物理系统中的安全控制算法设计》的分享。本文系分享内容的文字实录,希望能对大家有所帮助或者启发。 莫一林:现任清华大学自动...
  • 深思:外卖背后的人工智能算法揭秘

    千次阅读 2020-10-09 12:51:38
    这些通过高科技技术打造的人工智能外卖平台,既可以实时收集海量的配送数据,又可以通过人工智能机器学习算法,不断优化派单,压缩配送时间,提升配送效率。 技术革命带来的变革与进步是显而易见的,根据大数据统计...
  • 学习人工智能算法,你必须掌握的32个算法

    万次阅读 多人点赞 2018-06-13 16:07:13
    感谢并转自 点击打开链接奥地利符号计算研究所(Research Institute for Symbolic Computation,简称RISC)的Christoph Koutschan博士在自己的页面上发布了一篇文章...1、A* 搜索算法——图形搜索算法,从给定起点...
  • 机器人足球人工智能算法分析

    千次阅读 2006-06-29 14:00:00
    所以最近没事,又思考了一下机器人足球的人工智能算法。机器人足球和五子棋游戏的主要联系是:都需要随时分析整个棋盘/球场的状态,并作出最合适的反应;主要区别是:五子棋游戏是回合制的,而机器人足球是“即时”...
  • ISC 2017中国互联网安全大会举办了人工智能安全论坛。 我们把论坛总结成为一系列文章,本文为系列中的第二篇。作者: 肖奇学1, 许伟林2, 李康1 (1. 来自 360 Team Seri0us 团队, 2. 美国弗吉尼亚大学)“逃逸攻击就是...
  • 他认为,未来企业真正需要的不再是单个算法或者解决方案,而是可以基于自身数据,自动生成AI能力的企业AI核心系统。演讲中,胡时伟还分享了企业构建自主AI能力的最佳路径。以下为演讲全文,略有删减:随着AI技术的...
  • 基于并行遗传算法的无人驾驶(自动驾驶)避障算法安全性研究 无人驾驶系统,本质上分为输入(环境感知 标志车辆行人图像识别 车辆定位) 行为决策(导航路径规划 避障等) 输出(车辆控制 ),而行为决策里,最...
  • 基于麻雀搜索算法优化的Elman神经网络数据预测 - 附代码 文章目录基于麻雀搜索算法优化的Elman神经网络数据预测 - 附代码1.Elman 神经网络结构2.Elman 神经用络学习过程3.电力负荷预测概述3.1 模型建立4.基于麻雀...
  • 基于物品的协同过滤算法实现图书推荐系统

    万次阅读 多人点赞 2019-09-14 21:20:24
    本文首先介绍了推荐系统的发展历史,及目前常用的几种推荐算法的介绍与比较,然后以基于物品的协同过滤算法为基础,详细介绍图书推荐系统的构建。在该系统中,主要功能分为用户功能和图书推荐功能...
  • 浅谈端上智能之计算优化

    万次阅读 多人点赞 2019-11-05 22:11:05
    一、背景 - 边缘智能 人工智能(Artificial intelligence)的迅速发展正在改变世界。以深度学习(Deep learning)为驱动力和代表的第三波AI浪潮,正在变革和赋能金融、制造、农业、交通、医疗、零售、教育等众多行业...
  • 实验三 分类算法实验 ...在本实验中,我手工实现了所有算法,包括朴素贝叶斯,决策树ID3算法,决策树C4.5算法,决策树CART算法,人工神经网络BP算法,支持向量积SVM的SMO算法,并且对决策树的三个算法决策树结果进
  • 信息安全第五篇(国密加密算法

    万次阅读 2018-07-23 18:54:48
    国密即国家密码局认定的国产密码算法。主要有SM1,SM2,SM3,SM4。密钥长度和分组长度均为128位。 SM1:该算法是国家密码管理...采用该算法已经研制了系列芯片、智能 IC 卡、智能密码钥匙、加密卡、加 密机等安全产...
  • 前 言  智能家居又称智能住宅,正朝着具备无线远程...采用无线方式构建灵活便捷的智能家居安全监控系统,成为当前的研究热点。  目前,应用于智能家居的无线通信技术主要包括: Ir2DA红外线技术、蓝牙技术和ZigBee
  • 人工智能之搜索策略-A*算法进阶

    万次阅读 2016-01-11 17:32:52
    另一种极端情况是,一个单纯的运动系统(movement-only system)将不会搜索一条路径(最初的“路径”将被一条直线取代),取而代之的是在每一个结点处仅采取一个步骤,同时考虑周围的环境。同时使用路径搜索...
  • 算法思想:在强调数据结构的重要性后,其中算法思想也是不容忽略:分治算法:归并排序、快速排序……贪心算法:最小生成树……动态规划:最短路径……递归搜索:树形结构……以上所举的例子可以看出数据结构和算法...
  • 针对于应急通信领域需要快速部署,并要求成本最低的特点,随着近年智能技术的不断发展,其中近年来发展起来粒计算能够有效切快速的优化空间布局。本文将基于粒计算的基本理论和思想 , 将空间中的各个系留低空气球...
  • 前沿 文章目录前沿开源地址[算法学习资料: AI_Tutorial](https://github.com/cbamls/AI_Tutorial)开源相关LuceneSolrElasticLucidWorks中文分词大公司阿里百度京东美团点评...人工智能、AI架构、搜索系统、推荐系统...
  • 【推荐算法】今日头条推荐系统原理

    万次阅读 多人点赞 2018-01-24 17:24:46
    本次分享将主要介绍今日头条推荐系统概览以及内容分析、用户标签、评估分析,内容安全等原理。 一、系统概览 推荐系统,如果用形式化的方式去描述实际上是拟合一个用户对内容满意度的函数,这个函数
  • 嵌入式系统与人工智能

    千次阅读 2019-02-28 09:57:35
    工业4.0(又名工业物联网)和智能工厂等当前的技术趋势正在深刻地改变工业价值创造过程,其特点是更高程度的数字化,连通性和自动化。 所有涉及的组件,包括机器,机器人,传输和处理系统,传感器和图像采集设备,...
  • A*启发式搜索算法详解 人工智能

    千次阅读 2016-02-01 01:46:27
    A*启发式搜索算法详解 人工智能 转自:http://dev.gameres.com/Program/Abstract/Arithmetic/AmitAStar.mht 我们尝试解决的问题是把一个游戏对象(game object)从出发点移动到目的地。路径搜索(Pathfinding)的目标是...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 58,990
精华内容 23,596
关键字:

安全系统智能优化算法