• Large scale evolutionary optimization using cooperative coevolution


    0、论文背景

    本文提出了一个新的合作协同进化框架,能够优化大规模的不可分离问题。在问题分解和协同演化中引入了一种随机分组方案和自适应加权方法。采用了一种新的微分进化算法来代替传统的进化算法

    Yang Z, Tang K, Yao X. Large scale evolutionary optimization using cooperative coevolution[J]. Information sciences, 2008, 178(15): 2985-2999.

     1、具有分组和自适应加权的CC框架

    该框架的关键步骤如下:

    • 设置 i = 0 ,开始一个循环。
    • 将一个n维的对象向量随机分割成m个子分量(s维),n = m * s。
    • 使用EA优化第 i 个子组件。
    • 如果 i < m,i++,回到步骤3。
    • 对每个子组件施加一个权重。优化当前总体中最好、最差和随机成员的权重向量。
    • 如果满足停止条件,则停止;否则,转到下一个循环的步骤1。

    该方法与之前的CC最大的区别就是:

    • 动态分组(随机分组)
    • 框架在每个周期后使用自适应加权进行子组件之间的共适应。

    自适应加权策略背后的动机是:在所有子组件相互依赖时,对它们提供协同适应。这个优化问题的维数比原始问题要低得多(m<

    1.1 EACC-G的工作原理和效果

     可分离函数的定义k{1,n}" role="presentation">k{1,n}

    \left.\begin{array}{l} \mathbf{x} \in S, \quad \mathbf{x}=\left(\mathbf{x}_{\mathbf{1}}, \ldots, \mathbf{x}_{\mathbf{k}}, \ldots, \mathbf{x}_{\mathbf{n}}\right) \\ \mathbf{x}^{\prime} \in S, \quad \mathbf{x}^{\prime}=\left(\mathbf{x}_{\mathbf{1}}, \ldots, \mathbf{x}_{\mathbf{k}}^{\prime}, \ldots, \mathbf{x}_{\mathbf{n}}\right) \end{array}\right\} \Rightarrow f(\mathbf{x})<f\left(\mathbf{x}^{\prime}\right)

    可以推出:

    \left.\begin{array}{ll} \forall \mathbf{y} \in S, & \mathbf{y}=\left(\mathbf{y}_{1}, \ldots, \mathbf{x}_{\mathbf{k}}, \ldots, \mathbf{y}_{\mathbf{n}}\right) \\ \forall \mathbf{y}^{\prime} \in S, & \mathbf{y}^{\prime}=\left(\mathbf{y}_{\mathbf{1}}, \ldots, \mathbf{x}_{\mathbf{k}}^{\prime}, \ldots, \mathbf{y}_{\mathbf{n}}\right) \end{array}\right\} \Rightarrow f(\mathbf{y})<f\left(\mathbf{y}^{\prime}\right) 

    那么该函数就是可分离函数,否则则不是。

    下面展示了在EACC-G中同时优化两个相互作用的变量的概率的一个简单例子。

    首先,在每个单独的循环中,EACC-G将xi" role="presentation">xixj" role="presentation">xj分配到同一个子组件的概率:

    p=\frac{\left(\begin{array}{c} m \\ 1 \end{array}\right)}{m^{2}}=\frac{1}{m}

    Pr" role="presentation">Pr为EACC-G有r次循环xi" role="presentation">xixj" role="presentation">xj分配到单个子组件的概率:

    p_{r}=\left(\begin{array}{c} N \\ r \end{array}\right) p^{r}(1-p)^{N-r}=\left(\begin{array}{c} N \\ r \end{array}\right)\left(\frac{1}{m}\right)^{r}\left(1-\frac{1}{m}\right)^{N-r}

    在至少k个循环中,设Pk" role="presentation">Pk为EACC-G将xi" role="presentation">xixj" role="presentation">xj分配到单个子组件的概率:

    P_{k}=\sum_{r=k}^{N} p_{r}=\sum_{r=k}^{N}\left(\begin{array}{c} N \\ r \end{array}\right)\left(\frac{1}{m}\right)^{r}\left(1-\frac{1}{m}\right)^{N-r} .

    给定 n = 1000,s = 100,总循环数为50,我们可以得到:

    \begin{aligned} P_{1} &=\sum_{r=1}^{N} p_{r}=1-p_{0}=1-\left(1-\frac{1}{m}\right)^{N} \\ &=1-\left(1-\frac{1}{10}\right)^{50}=0.9948 \\ P_{2} &=\sum_{r=2}^{N} p_{r}=1-p_{0}-p_{1}=0.9662 . \end{aligned} 

    P1和P2表明,EACC-G在至少一个或两个周期内优化相互作用变量方面具有相对较高的概率。换句话说,EACC-G使用简单分组策略下捕获变量相互依赖是非常有效的

    2、新的CC框架下的SaNSDE

    有关SaNSDE以及实现,请参照博客:SaNSDE

    新的CC框架下的SaNSDE算法流程图如下图所示:

     3、算法的实现和简单实验

    本文验证函数是CEC2008测试函数,二者总的函数估值次数均大概在2500000次。

    SaNSDE实验设计代码:

    1. clear;clc;clearvars;
    2. addpath('CEC2008\');
    3. % 初始化变量维度,种群数,最大迭代次数,搜索区间,F,CR
    4. dim = 500;
    5. popsize = 100;
    6. maxIteration = 25000;
    7. LB = -100 * ones(1, dim);
    8. UB = 100 * ones(1, dim);
    9. CR = 0.9;
    10. % 估值次数:100*25000
    11. [globalBest3, globalBestFitness3, FitnessHistory3] = SaNSDE(popsize, maxIteration,dim, LB, UB, @(x)benchmark_func(x,3));
    12. plot(FitnessHistory3);

    DECC_G:

    1. clc;clear;clearvars;
    2. addpath('CEC2008\');
    3. global initial_flag
    4. NS = 100; % 种群数
    5. dim = 500; % 种群维度
    6. s = 5; % 子空间的数目,设定为5,10
    7. % 搜索区间:f1[-100,100],f2[-100, 100],f3[-100,100],f4[-5,5],f5[-600,600],f6[-32,32],f7[-1,1],每一维搜索区间一样
    8. upper_bound = [100,100,100,5,600,32,1];
    9. lower_bound = [-100,-100,-100,-5,-600,-32,-1];
    10. best_yh = [];
    11. for func_num = 3
    12. initial_flag = 0; % 使initial_flag==0满足此条件,换一个函数initial_flag重置为0
    13. % 生成num_initial个种群,并获得其评估值
    14. sample_x = lhsdesign(NS, dim).*(upper_bound(func_num) - lower_bound(func_num)) + lower_bound(func_num).*ones(NS, dim);
    15. sample_y = benchmark_func(sample_x,func_num);
    16. [best_y, bestIndex] = min(sample_y); %获取全局最小值以及对应的种群
    17. best_x = sample_x(bestIndex,:);
    18. for i0 = 1 : 50 %迭代50次
    19. index = randperm(dim); %随机划分子空间
    20. for i1 = 1 : s
    21. index1 = index(((i1 - 1) * (dim / s) + 1) : (i1 * (dim / s)));
    22. sub_x = sample_x(:,index1);
    23. sub_x = SaNSDE1(sub_x, sample_y, best_x, index1, 70,dim / s, lower_bound(func_num), upper_bound(func_num), @(x)benchmark_func(x,func_num));%100*70
    24. sample_x(:,index1) = sub_x;
    25. sample_y = benchmark_func(sample_x,func_num); %100
    26. [best_y, bestIndex] = min(sample_y); %获取全局最小值以及对应的种群
    27. best_x = sample_x(bestIndex,:);
    28. end
    29. [worse_y, worseIndex] = max(sample_y); %获取全局最大值以及对应的种群
    30. randIndex = randi(NS);
    31. while randIndex == bestIndex || randIndex == worseIndex
    32. randIndex = randi(NS); % 随机获取一个值
    33. end
    34. % 权重向量的搜索范围[-5,5]
    35. [sample_x(worseIndex,:),sample_y(worseIndex,:)] = NSDE(sample_x(worseIndex,:), NS, 50, s, -5, 5, 0.9, @(x)benchmark_func(x,func_num));% 50*100
    36. [sample_x(bestIndex,:),sample_y(bestIndex,:)] = NSDE(sample_x(bestIndex,:), NS, 50, s, -5, 5, 0.9, @(x)benchmark_func(x,func_num));
    37. [sample_x(randIndex,:),sample_y(randIndex,:)] = NSDE(sample_x(randIndex,:), NS, 50, s, -5, 5, 0.9, @(x)benchmark_func(x,func_num));
    38. [best_y, bestIndex] = min(sample_y); %获取全局最小值以及对应的种群
    39. best_x = sample_x(bestIndex,:);
    40. best_yh = [best_yh;best_y];
    41. end
    42. end
    43. plot(best_yh);
    1. function [x1 , globalBestFitness] = NSDE(x,popsize, maxIteration,dim, LB, UB, CR, Fun)
    2. % 种群的初始化和计算适应度值
    3. Sol(popsize, dim) = 0; % Declare memory.
    4. Fitness(popsize) = 0;
    5. for i = 1:popsize
    6. Sol(i,:) = LB+(UB-LB).* rand(1, dim);
    7. for i0 = 1 : dim
    8. ind = ((i0 - 1) * (size(x,2) / dim) + 1) : i0 * (size(x,2) / dim);
    9. x(1,ind) = x(1,ind) .* Sol(i,i0);
    10. end
    11. Fitness(i) = Fun(x(1,:));
    12. end
    13. % 获得全局最优值以及对应的种群向量
    14. [fbest, bestIndex] = min(Fitness);
    15. globalBest = Sol(bestIndex,:);
    16. globalBestFitness = fbest;
    17. % 开始迭代
    18. for time = 1:maxIteration
    19. for i = 1:popsize
    20. % 突变
    21. r = randperm(popsize, 3); %在1~pop中随机选择5个数组成一个数组
    22. r1 = rand();
    23. if r1 > 0.5
    24. pd = makedist('tLocationScale','mu',0,'sigma',1,'nu',1);
    25. F = random(pd,1,1);%生成1个柯西随机数
    26. else
    27. F = normrnd(0.5,0.5);%生成1个高斯随机数
    28. end
    29. mutantPos = Sol(r(1),:) + F * (Sol(r(2),:) - Sol(r(3),:));
    30. % 交叉
    31. jj = randi(dim); % 选择至少一维发生交叉
    32. for d = 1:dim
    33. if rand() < CR || d == jj
    34. crossoverPos(d) = mutantPos(d);
    35. else
    36. crossoverPos(d) = Sol(i,d);
    37. end
    38. end
    39. % 检查是否越界.
    40. crossoverPos(crossoverPos>UB) = UB;
    41. crossoverPos(crossoverPos
    42. for i1 = 1 : dim
    43. ind = ((i1 - 1) * (size(x,2) / dim) + 1) : i1 * (size(x,2) / dim);
    44. x(1,ind) = x(1,ind) .* crossoverPos(1,i1);
    45. end
    46. evalNewPos = Fun(x(1,:));% 将突变和交叉后的变量重新评估
    47. % 小于原有值就更新
    48. if evalNewPos < Fitness(i)
    49. Sol(i,:) = crossoverPos;
    50. Fitness(i) = evalNewPos;
    51. end
    52. end
    53. [fbest, bestIndex] = min(Fitness);
    54. globalBest = Sol(bestIndex,:);
    55. for i2 = 1 : dim
    56. ind2 = ((i2 - 1) * (size(x,2) / dim) + 1) : i2 * (size(x,2) / dim);
    57. x(1,ind) = x(1,ind2) .* globalBest(1,i2);
    58. end
    59. globalBestFitness = fbest;
    60. x1 = x(1,:);
    61. end
    62. end
    1. function sub_x = SaNSDE1(sub_x, sample_y, best_x, index1, maxIteration,dim, LB, UB, Fun)
    2. % 获得全局最优值以及对应的种群向量
    3. [~, bestIndex] = min(sample_y);
    4. globalBest = sub_x(bestIndex,:);
    5. % 策略学习初始化值的设置
    6. p1 = 0.5;p3 = 0.5;
    7. ns1 = 0;ns2 = 0;nf1 = 0;nf2 = 0;
    8. fns1 = 0;fns2 = 0;fnf1 = 0;fnf2 = 0;
    9. CRm = 0.5;
    10. CRQ = normrnd(CRm,0.1,[size(sub_x,1),1]);
    11. CRRecord = [];
    12. RecRecord = [];
    13. % 开始迭代
    14. for time = 1:maxIteration
    15. for i = 1:size(sub_x,1)
    16. % 突变
    17. if rand() >= p3
    18. pd = makedist('tLocationScale','mu',0,'sigma',1,'nu',1);
    19. F = random(pd,1,1);%生成1个柯西随机数
    20. tag1 = 1;
    21. else
    22. F = normrnd(0.5,0.3);%生成1个高斯随机数
    23. tag1 = 2;
    24. end
    25. if rand() <= p1
    26. r = randperm(size(sub_x,1), 3); %策略1
    27. mutantPos = sub_x(r(1),:) + F * (sub_x(r(2),:) - sub_x(r(3),:));%在1~pop中随机选择3个数组成一个数组
    28. tag0 = 1;
    29. else
    30. r = randperm(size(sub_x,1), 2); %策略2
    31. mutantPos = sub_x(i,:) + F * (globalBest - sub_x(i,:)) + F * (sub_x(r(1),:) - sub_x(r(2),:));
    32. tag0 = 2;
    33. end
    34. % 交叉
    35. jj = randi(dim); % 选择至少一维发生交叉
    36. CR = CRQ(i,1);
    37. for d = 1:dim
    38. if rand() < CR || d == jj
    39. crossoverPos(d) = mutantPos(d);
    40. else
    41. crossoverPos(d) = sub_x(i,d);
    42. end
    43. end
    44. % 检查是否越界.
    45. crossoverPos(crossoverPos>UB) = UB;
    46. crossoverPos(crossoverPos
    47. % 小于原有值就更新,同时更新ns1,ns2,nf1,nf2
    48. best_x(:,index1) = crossoverPos;
    49. evalNewPos = Fun(best_x);% 将突变和交叉后的变量重新评估
    50. if evalNewPos < sample_y(i)
    51. if tag0 == 1
    52. ns1 = ns1 + 1;
    53. elseif tag0 == 2
    54. ns2 = ns2 + 1;
    55. end
    56. if tag1 == 1
    57. fns1 = fns1 + 1;
    58. elseif tag1 == 2
    59. fns2 = fns2 + 1;
    60. end
    61. CRRecord = [CRRecord;CR];
    62. RecRecord = [RecRecord;(sample_y(i) - evalNewPos)];
    63. sub_x(i,:) = crossoverPos;
    64. sample_y(i) = evalNewPos;
    65. else
    66. if tag0 == 1
    67. nf1 = nf1 + 1;
    68. elseif tag0 == 2
    69. nf2 = nf2 + 1;
    70. end
    71. if tag1 == 1
    72. fnf1 = fnf1 + 1;
    73. elseif tag1 == 2
    74. fnf2 = fnf2 + 1;
    75. end
    76. end
    77. end
    78. [~, bestIndex] = min(sample_y);
    79. globalBest = sub_x(bestIndex,:);
    80. % F,策略的学习
    81. if mod(time,50) == 0
    82. p1 = (ns1 * (ns2 + nf2)) / (ns2 * (ns1 + nf1) + ns1 * (ns2 + nf2));
    83. ns1 = 0;ns2 = 0;nf1 = 0;nf2 = 0;
    84. p3 = (fns1 * (fns2 + fnf2)) / (fns2 * (fns1 + fnf1) + fns1 * (fns2 + fnf2));
    85. fns1 = 0;fns2 = 0;fnf1 = 0;fnf2 = 0;
    86. end
    87. % CR的更新
    88. if mod(time,25) == 0
    89. wk = RecRecord ./ sum(RecRecord);
    90. CRm = sum(wk .* CRRecord);
    91. CRRecord = [];
    92. RecRecord = [];
    93. end
    94. if mod(time,5) == 0
    95. CRQ = normrnd(CRm,0.1,[size(sub_x,1),1]);
    96. end
    97. end
    98. end

    f1,SaNSDE和CCEA_G:

     f2,SaNSDE和CCEA_G:

     

     f3,SaNSDE和CCEA_G:

     

    从上面简单看出,CCEA_G有着不小的优势。

    如有错误,还望批评指正。 

  • 相关阅读:
    Web前端大作业—里约热内卢奥运会(html+css+javascript)
    Python实战|「甜点消消」游戏数据分析过程
    一篇文章带你搞定Java封装
    浙大恩特客户资源管理系统CustomerAction.entphone;.js 接口任意文件上传漏洞复现 [附POC]
    linux安全--Nginx与Tomcat实现负载均衡
    Unity --- 文本的使用
    盘点检索任务中的损失函数
    C现代方法(第18章)笔记——声明
    4_hytrix_信号量_线程池
    @Autowired 多个相同类型Bean的自动注入
  • 原文地址:https://blog.csdn.net/qq_42148307/article/details/127834700