优化算法 | Gaining Sharing Knowledge based Algorithm ...

RecursiveFrog · 发表于 2022-9-18 08:33

今天为各位讲解Gainingsharing knowledge based algorithm（GSK），为什么讲解这个算法呢，因为自适应GSK算法（Adaptive Gaining-Sharing Knowledge Based Algorithm，AGSK）是CEC2020比赛的优胜算法。在讲解性能强悍的AGSK算法前，有必要先理解GSK的基本思想，而后再向深刻理解AGSK算法迈进。
<hr/>1.GSK算法基本思想

GSK算法的灵感来源于人在一生中获取和共享知识的过程，这个过程分为两个阶段：
1）初级获取和共享知识阶段，即人一生的前中期。在这一阶段，相比于通过大型网络（如工作、社交、朋友等）获取知识，人们更多地会通过小型网络（如家人、邻居、亲戚等）获取知识。虽然这一阶段的人们想法、观点尚未成熟，但是他们努力尝试分享自己的观点。
2）高级获取和共享知识阶段，即人一生的中后期。这一阶段的人们通常会通过大型网络（如工作、社交、朋友等）获取知识，比如，这一阶段的人们通常喜欢成功学，相信成功者的观点，以使他们避免失败。这一阶段的人们思想十分成熟，他们会积极向他人分享自己的观点，期望帮助他人能从自己的分享中受益。
<hr/>2.GSK算法数学描述

在了解GSK算法基本思想后，接下来对GSK算法进行数学描述：
假设第i个体x_i=(x_{i1},x_{i2},...,x_{iD}),i=1,2,...,N的适应度值为f_i,i=1,2,...,N，其中D为问题维数，N为种群数目。下图可以清晰地展示两个阶段个体中初级部分和高级部分的变化情况。

从上述分析过程和上图中可以看出，初级要素数目和高级要素数目是变化的，则个体中初级要素数目的计算公式如下：
D(\text { juniorphase })=(\text { problemsize }) \times\left(1-\frac{G}{G E N}\right)^k \\
个体中高级要素数目的计算公式如下：
D(\text { seniorphase })=\text { problemsize }-D(\text { juniorphase }) \\
其中，D(\text { juniorphase })表示初级要素数目，D(\text { seniorphase})表示高级要素数目，problemsize表示问题维数，GEN表示总迭代次数，G表示当前迭代次数，k(k>0)表示知识学习率。
<hr/>3.GSK算法基本步骤

如GSK基本思想所阐述的一样，GSK算法也分为初级和高级获取与共享知识两个阶段。
01 | 初级获取和共享知识阶段

假设求解函数最小值问题，在这一阶段，更新x_i,i=1,2,...,N的方法如下：
（1）将种群中的个体按照适应度值从小到大的顺序进行排序，排序结果如下：x_{\text {best }}, \ldots \ldots, x_{i-1}, x_i, x_{i+1}, \ldots \ldots x_{\text {worst }}
（2）x_i,i=1,2,...,N的更新公式如下：
x_i^{n e w}= \begin{cases}x_i+k_f \times\left[\left(x_{i-1}-x_{i+1}\right)+\left(x_r-x_i\right)\right] & f\left(x_i\right)>f\left(x_r\right) \\ x_i+k_f \times\left[\left(x_{i-1}-x_{i+1}\right)+\left(x_i-x_r\right)\right] & f\left(x_i\right) \leq f\left(x_r\right)\end{cases} \\
其中x_i^{n e w}为更新后的个体，x_r为随机选择的个体，k_f为知识因素参数。初级获取和共享知识阶段算法伪代码如下，其中k_r为知识比率：

02 | 高级获取和共享知识阶段

假设求解函数最小值问题，在这一阶段，更新x_i,i=1,2,...,N的方法如下：
（1）将种群中的个体按照适应度值从小到大的顺序进行排序，然后将排序后的个体分成3类，即最佳个体、中等个体、最差个体，其中最佳个体占比p，最差个体占比p，中等个体占比1-2p，通常取p=0.1。
（2）x_i,i=1,2,...,N的更新公式如下：
x_i^{n e w}= \begin{cases}x_i+k_f \times\left[\left(x_{pbest}-x_{pworst}\right)+\left(x_m-x_i\right)\right] & f\left(x_i\right)>f\left(x_m\right) \\ x_i+k_f \times\left[\left(x_{pbest}-x_{pworst}\right)+\left(x_i-x_m\right)\right] & f\left(x_i\right) \leq f\left(x_m\right)\end{cases} \\
其中x_i^{n e w}为更新后的个体，x_{pbest}为最佳个体中随机选择的个体，x_{pworst}为最差个体中随机选择的个体，x_{m}为中等个体中随机选择的个体，k_f为知识因素参数。高级获取和共享知识阶段算法伪代码如下，其中k_r为知识比率：

03 | GSK算法伪代码及流程图

<hr/>4.GSK算法MATLAB代码

GSK算法MATLAB代码链接为：https://www.mathworks.com/matlabcentral/fileexchange/73730-gaining-sharing-knowledge-based-algorithm，各位也可在优化算法 | Gaining Sharing Knowledge based Algorithm（附MATLAB代码）提取代码。
以求解CEC2017为例，GSK算法文件夹共包含如下文件：

主函数GSK.m代码如下所示：
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%Gaining-Sharing Knowledge Based Algorithm for Solving Optimization
%%Problems: A Novel Nature-Inspired Algorithm
%% Authors: Ali Wagdy Mohamed, Anas A. Hadi , Ali Khater Mohamed
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

clc;
clear all;

format long;
Alg_Name=&#39;GSK&#39;;
n_problems=30;
ConvDisp=1;
Run_No=51;

for problem_size = [10 30 50 100]

max_nfes = 10000 * problem_size;
rand(&#39;seed&#39;, sum(100 * clock));
val_2_reach = 10^(-8);
max_region = 100.0;
min_region = -100.0;
lu = [-100 * ones(1, problem_size); 100 * ones(1, problem_size)];
fhd=@cec17_func;
analysis= zeros(30,6);
for func = 1 : n_problems
      optimum = func * 100.0;
      %% Record the best results
      outcome = [];
      fprintf(&#39;\n-------------------------------------------------------\n&#39;)
      fprintf(&#39;Function = %d, Dimension size = %d\n&#39;, func, problem_size)
      dim1=[];
      dim2=[];
      for run_id = 1 : Run_No
         bsf_error_val=[];
         run_funcvals = [];
         pop_size = 100;
         G_Max=fix(max_nfes/pop_size);

         %% Initialize the main population
         popold = repmat(lu(1, :), pop_size, 1) + rand(pop_size, problem_size) .* (repmat(lu(2, :) - lu(1, :), pop_size, 1));
         pop = popold; % the old population becomes the current population

         fitness = feval(fhd,pop&#39;,func);
         fitness = fitness&#39;;

         nfes = 0;
         bsf_fit_var = 1e+300;

         %%%%%%%%%%%%%%%%%%%%%%%% for out
         for i = 1 : pop_size
            nfes = nfes + 1;
            %%    if nfes > max_nfes; exit(1); end
            if nfes > max_nfes; break; end
            if fitness(i) < bsf_fit_var
                  bsf_fit_var = fitness(i);
            end
            run_funcvals = [run_funcvals;bsf_fit_var];
         end

         %%%%%%%%%%%%%%%%%%%%%%%% Parameter settings%%%%%%%%%%
         KF=0.5;% Knowledge Factor
         KR=0.9;%Knowledge Ratio
         K=10*ones(pop_size,1);%Knowledge Rate

         g=0;
         %% main loop
         while nfes < max_nfes
            g=g+1;
            D_Gained_Shared_Junior=ceil((problem_size)*(1-g/G_Max).^K);
            D_Gained_Shared_Senior=problem_size-D_Gained_Shared_Junior;
            pop = popold; % the old population becomes the current population

            [valBest, indBest] = sort(fitness, &#39;ascend&#39;);
            [Rg1, Rg2, Rg3] = Gained_Shared_Junior_R1R2R3(indBest);

            [R1, R2, R3] = Gained_Shared_Senior_R1R2R3(indBest);
            R01=1:pop_size;
            Gained_Shared_Junior=zeros(pop_size, problem_size);
            ind1=fitness(R01)>fitness(Rg3);

            if(sum(ind1)>0)
                  Gained_Shared_Junior (ind1,:)= pop(ind1,:) + KF*ones(sum(ind1), problem_size) .* (pop(Rg1(ind1),:) - pop(Rg2(ind1),:)+pop(Rg3(ind1), :)-pop(ind1,:)) ;
            end
            ind1=~ind1;
            if(sum(ind1)>0)
                  Gained_Shared_Junior(ind1,:) = pop(ind1,:) + KF*ones(sum(ind1), problem_size) .* (pop(Rg1(ind1),:) - pop(Rg2(ind1),:)+pop(ind1,:)-pop(Rg3(ind1), :)) ;
            end
            R0=1:pop_size;
            Gained_Shared_Senior=zeros(pop_size, problem_size);
            ind=fitness(R0)>fitness(R2);
            if(sum(ind)>0)
                  Gained_Shared_Senior(ind,:) = pop(ind,:) + KF*ones(sum(ind), problem_size) .* (pop(R1(ind),:) - pop(ind,:) + pop(R2(ind),:) - pop(R3(ind), :)) ;
            end
            ind=~ind;
            if(sum(ind)>0)
                  Gained_Shared_Senior(ind,:) = pop(ind,:) + KF*ones(sum(ind), problem_size) .* (pop(R1(ind),:) - pop(R2(ind),:) + pop(ind,:) - pop(R3(ind), :)) ;
            end
            Gained_Shared_Junior = boundConstraint(Gained_Shared_Junior, pop, lu);
            Gained_Shared_Senior = boundConstraint(Gained_Shared_Senior, pop, lu);


            D_Gained_Shared_Junior_mask=rand(pop_size, problem_size)<=(D_Gained_Shared_Junior(:, ones(1, problem_size))./problem_size);
            D_Gained_Shared_Senior_mask=~D_Gained_Shared_Junior_mask;

            D_Gained_Shared_Junior_rand_mask=rand(pop_size, problem_size)<=KR*ones(pop_size, problem_size);
            D_Gained_Shared_Junior_mask=and(D_Gained_Shared_Junior_mask,D_Gained_Shared_Junior_rand_mask);

            D_Gained_Shared_Senior_rand_mask=rand(pop_size, problem_size)<=KR*ones(pop_size, problem_size);
            D_Gained_Shared_Senior_mask=and(D_Gained_Shared_Senior_mask,D_Gained_Shared_Senior_rand_mask);
            ui=pop;

            ui(D_Gained_Shared_Junior_mask) = Gained_Shared_Junior(D_Gained_Shared_Junior_mask);
            ui(D_Gained_Shared_Senior_mask) = Gained_Shared_Senior(D_Gained_Shared_Senior_mask);

            children_fitness = feval(fhd, ui&#39;, func);
            children_fitness = children_fitness&#39;;

            for i = 1 : pop_size
                  nfes = nfes + 1;
                  if nfes > max_nfes; break; end
                  if children_fitness(i) < bsf_fit_var
                     bsf_fit_var = children_fitness(i);
                     bsf_solution = ui(i, :);
                  end
                  run_funcvals = [run_funcvals;bsf_fit_var];

            end

            [fitness, Child_is_better_index] = min([fitness, children_fitness], [], 2);

            popold = pop;
            popold(Child_is_better_index == 2, :) = ui(Child_is_better_index == 2, :);

            % fprintf(&#39;NFES:%d, bsf_fit:%1.6e,pop_Size:%d,D_Gained_Shared_Junior:%2.2e,D_Gained_Shared_Senior:%2.2e\n&#39;, nfes,bsf_fit_var,pop_size,problem_size*sum(sum(D_Gained_Shared_Junior))/(pop_size*problem_size),problem_size*sum(sum(D_Gained_Shared_Senior))/(pop_size*problem_size))

         end % end while loop

         bsf_error_val = bsf_fit_var - optimum;
         if bsf_error_val < val_2_reach
            bsf_error_val = 0;
         end

         fprintf(&#39;%d th run, best-so-far error value = %1.8e\n&#39;, run_id , bsf_error_val)
         outcome = [outcome bsf_error_val];

         %% plot convergence figures
         if (ConvDisp)
            run_funcvals=run_funcvals-optimum;
            run_funcvals=run_funcvals&#39;;
            dim1(run_id,:)=1:length(run_funcvals);
            dim2(run_id,:)=log10(run_funcvals);
         end
         %%%%%%%%%%%%%%%%%%%%%%%%%%%
      end %% end 1 run

      %% save ststiatical output in analysis file%%%%
      analysis(func,1)=min(outcome);
      analysis(func,2)=median(outcome);
      analysis(func,3)=max(outcome);
      analysis(func,4)=mean(outcome);
      analysis(func,5)=std(outcome);
      median_figure=find(outcome== median(outcome));
      analysis(func,6)=median_figure(1);

      file_name=sprintf(&#39;Results\\%s_CEC2017_Problem#%s_problem_size#%s&#39;,Alg_Name,int2str(func),int2str(problem_size));
      save(file_name,&#39;outcome&#39;);
      %% print statistical output and save convergence figures%%%
      fprintf(&#39;%e\n&#39;,min(outcome));
      fprintf(&#39;%e\n&#39;,median(outcome));
      fprintf(&#39;%e\n&#39;,mean(outcome));
      fprintf(&#39;%e\n&#39;,max(outcome));
      fprintf(&#39;%e\n&#39;,std(outcome));
      dim11=dim1(median_figure,:);
      dim22=dim2(median_figure,:);
      file_name=sprintf(&#39;Figures\\Figure_Problem#%s_Run#%s&#39;,int2str(func),int2str(median_figure));
      save(file_name,&#39;dim1&#39;,&#39;dim2&#39;);
end %% end 1 function run

file_name=sprintf(&#39;Results\\analysis_%s_CEC2017_problem_size#%s&#39;,Alg_Name,int2str(problem_size));
save(file_name,&#39;analysis&#39;);
end %% end all function runs in all dimensions
5.GSK算法实例验证

以求解CEC2017第6个测试函数为例，该函数为Shifted and Rotated Schaffer’s F7 Function：
F_6(\boldsymbol{x})=f_{20}\left(\mathbf{M}\left(\frac{0.5\left(\boldsymbol{x}-\boldsymbol{o}_6\right)}{100}\right)\right)+F_6 * \\
该函数具有4个特性：多模态、不可分离、不对称、局部最优点数量巨大，该函数图像如下：

当求解问题维数为10维时，求解结果如下，求解最优值为600，已经达到全局最优值：

参考文献
[1] Mohamed A W, Hadi A A, Mohamed A K. Gaining-sharing knowledge based algorithm for solving optimization problems: a novel nature-inspired algorithm[J]. International Journal of Machine Learning and Cybernetics, 2020, 11(7): 1501-1529.
[2] https://www.mathworks.com/matlabcentral/fileexchange/73730-gaining-sharing-knowledge-based-algorithm
<hr/>OK，今天就到这里啦，各位可点击下方图片留言，下方图书为作者撰写书籍，助力各位快速入门智能优化算法。

<hr/>咱们下期再见
近期你可能错过了的好文章

新书上架 | 《MATLAB智能优化算法：从写代码到算法思想》
优化算法 | 灰狼优化算法（文末有福利）
优化算法 | 鲸鱼优化算法
遗传算法（GA）求解带时间窗的车辆路径（VRPTW）问题MATLAB代码
粒子群优化算法（PSO）求解带时间窗的车辆路径问题（VRPTW）MATLAB代码

知乎 | bilibili | CSDN：随心390

		自动登录	找回密码
密码			立即注册

优化算法 | Gaining Sharing Knowledge based Algorithm ...

本帖子中包含更多资源