用遗传算法求函数最大值二:选择、交叉和变异

选择

选择(或复制)操作决定哪些个体可以进入下一代。这里采用轮盘赌法选择,这种方法比较容易实现。

在轮盘赌法中,设种群大小为n,其中个体i的适应值是f_i,则i被选择的概率为:

p_i = \frac{f_i}{\sum_{j=1}^{n} f_i}

显然,个体适应值越大,被选择的概率越大。

轮盘赌法具体步骤如下:

  1. 计算f_{sum}p_i
  2. 产生(0,1)的随机数rand,求s=rand×f_sum 。
  3. \sum_{i=1}^k f_i \geqslant s中最小的k,该k被选中。
  4. 多次操作,直到得到指定个个体。

代码实现如下:

function [newpop] = selection(pop, fitvalue)
% 选择,轮盘赌方法,最大化问题
% pop       input  种群
% fitvalue  input  适应度值
% newpop    output 选择后的种群
totalfit = sum(fitvalue);
fitvalue = fitvalue / totalfit;
fitvalue = cumsum(fitvalue);
[n, l] = size(pop);
newpop = zeros(n, l);
rnumber = sort(rand(n,1));
fitindex = 1;
newindex = 1;
while newindex <= n
    if rnumber(newindex) < fitvalue(fitindex)
        newpop(newindex,:) = pop(fitindex,:);
        newindex = newindex + 1;
    else
        fitindex = fitindex + 1;
    end
end
end

交叉

这里采用单点交叉的方法,假设有两个个体:

X1 = 010*0110
X2 = 101*0001

在*交叉,得到两个子代:

Y1 = 0100001
Y2 = 1010110

实现代码如下:

function [newpop] = crossover(pop, pc)
% 交叉
% pop       input  种群
% pc        input  变异概率
% newpop    output 新种群
[n, l] = size(pop);
newpop = zeros(n, l);
for i = 1:2:n-1   % 最少需剩余一行
    if rand < pc
        cpoint = round(rand * l);
        newpop(i, :) = [pop(i, 1:cpoint), pop(i+1, cpoint+1:l)];
        newpop(i+1, :) = [pop(i+1, 1:cpoint), pop(i, cpoint+1:l)];
    else
        newpop(i, :) = pop(i,:);
        newpop(i+1, :) = pop(i+1,:);
    end
end
end

变异

对于本问题的二进制编码,变异是指将染色体中的某一位进行反转,代码如下:

function [newpop] = mutation(pop, pm)
% 变异
% pop           input  种群
% pm            input  变异概率
% newpop        output 变异之后的新种群
[n, l] = size(pop);
newpop = zeros(n, l);
for i = 1:n
    newpop(i, :) = pop(i, :);
    if rand < pm
        mpoint = round(rand * l);
        if mpoint <= 0
            mpoint = 1;
        end
        if any(newpop(i, mpoint)) == 0
            newpop(i, mpoint) = 1;
        else
            newpop(i, mpoint) = 0;
        end
    end
end
end

最优个体

下面的函数得到种群中最优个体的索引:

function bestindex = bestindividual(pop, fitvalue, opt)
% 得到种群中最优的个体的索引
% pop               input  种群
% fitvalue          input  适应度值
% opt               input  操作模式:'min'求最小值,'max'求最大值
% bestindex         output 最优个体索引
if strcmp(opt, 'min')
    [~, bestindex] = min(fitvalue);
else
    [~, bestindex] = max(fitvalue);
end
end

发表评论

电子邮件地址不会被公开。 必填项已用*标注