Xin Yao, Yong Liu and Guangming Lin, “Evolutionary programming made faster,” in IEEE Transactions on Evolutionary Computation, vol. 3, no. 2, pp. 82-102, July 1999, doi: 10.1109/4235.771163.

Introduction

The disadvantage of classical EP (CEP) is the low convergence on multimodal problems. The new EP proposed in this paper uses the Cauchy mutation which outperforms the Gaussian mutation.

When the optimal decision solution is very far from current solution, CEP can be very good. And Fast Evolutionary Programming (FEP) is opposite because Cauchy Distribution is a kind of long-tailed distribution, thus some extreme offspring can be obtained.

Classical Evolutionary Programming

The self-adaptive mutation is usually better.

Basic Steps

1
2
3
4
5
function pop = Initialization(popsize,lb,ub,n)
    x = lb+(ub-lb)*rand([popsize,n]);
    eta = 3*ones([popsize,n]); % 初始值为3
    pop = [x, eta];
end
1
2
3
4
5
6
7
function fitness = Evaluation(pop, objective, n)
    popsize = size(pop,1);
    fitness = zeros(1,popsize);
    for k = 1:popsize
        fitness(k) = objective(pop(k,1:n));
    end
end
1
2
3
4
5
6
7
8
9
function child = CreateNew(parent, n, lb, ub)
    tau1 = 1/(sqrt(2*sqrt(n)));
    tau2 = 1/sqrt(2*n);
    x = parent(1:n) + parent(n+1:end).*randn(1,n);
    x = boundData(x, lb, ub);
    normrand = randn;
    eta = parent(n+1:end).*exp(tau2*normrand+tau1*randn(1,n));
    child = [x,eta];
end
1
2
3
4
5
6
7
8
9
10
function newpop = Selection(pop, q, mu, fitness)
    popsize = size(pop,1);
    wins = zeros(1, popsize);
    for k = 1:popsize
        opponents = randperm(popsize,q);
        wins(k) = sum(fitness(k)<=fitness(opponents)); % 最小化问题
    end
    [~, index] = sort(wins, 'descend');
    newpop = pop(index(1:mu),:);
end

Fast Evolutionary Programming

以下内容更新于2023年3月13日

The only difference of FEP and CEP is the mutation step:

1
x = parent(1:n) + parent(n+1:end).*trnd(1,n,d);

Based on the advantages of Gaussian Distribution and Cauchy Distribuion, an Improved Fast Evolutionary Programming (IFEP) combines the two distributions. In IFEP, each individual in parent population will produce two different distribution offsprings. All the parents and children will participate in the tournamnt selection. The specific process can be illustrated as follows:

一些想法

写这篇博客的初衷，是因为一门课程的缘故，这门课程的一次Assignment需要对一系列单目标问题进行优化，而提供的参考文献恰恰是这篇论文。

最初的想法是对这篇文章提出的CEP和FEP进行复现，如同前面的代码一样，无非是几个for循环，加上随机数和一些矩阵运算，这个过程是非常迅速的，可以在短短几个小时完成，但是最后的结果却与论文给出的结果相差甚远。

论文中没有提到的一点，是对于步长变量eta的下界设定。事实上，随着演化的进行，eta的值会逐渐减小，最终趋向于0。此时如果设定一个固定的下界（比如1e-3），结果将会大为改观。

当我尝试对IFEP进行改进，想到的最主要的方法也是通过动态调整eta的下界，或者改变Gaussian和Cautch两种分布的组合方式。但是最后的结果仅仅能说差强人意，这种缺乏理论研究的不确定性，让我对演化计算的前景再次陷入深深的忧虑。

在这次Assignment发布以后，提供的唯一一篇参考文献即是这篇论文，于是我发现了一个有趣的现象，无论是周围的同学往年的学长，似乎都陷入了一个死胡同。我们竭尽心力想要在IFEP的基础上进行改进，但恕不知无论是FEP、CEP还是IFEP，其本身的性能就非常羸弱。

在PlatEMO上面，我粗略测试了所有单目标优化算法的性能，在没有下界设定的FEP，性能甚至与传统的遗传算法GA都相距甚远。其中结果最优秀的是IMODE，根本方法是使用了多种DE的operator，每种operator种群大小可以动态调整。无论是DE还是PSO，我都是能够表示赞同的，因为它们利用了类似梯度的信息。以此反观EP，目前为止我都没有明白，为什么所有的EP仅仅使用了变异算子，而缺乏交叉，并且这种变异是随机性的瞎搜索，没有任何先验知识。

最后，提供的测试代码写得真的烂，使用这么多for循环，助教们是完全不会MATLAB矩阵运算吗。电脑都是单核吗，写一个parfor不行吗，我每次改完算法做测试都要十多分钟。

不过这次Assignment让我学到最多的，是如何做假设检验，我觉得对于这一点还可以单独写一个博客。