遗传算法

算法介绍

遗传算法（Genetic Algorithm，GA）最早是由美国的 John holland于20世纪70年代提出,该算法是根据大自然中生物体进化规律而设计提出的。是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。

算法过程

遗传算法的过程如下：

代码及说明

代码的选择操作采用了精英保留策略。

为了防止当前群体的最优个体在下一代发生丢失，导致遗传算法不能收敛到全局最优解，De Jong在其博士论文中提出了“精英选择(elitist selection or elitism)”策略，也称为“精英保留”(elitist preservation)策略。该策略的思想是，把群体在进化过程中迄今出现的最好个体(称为精英个体elitist)不进行配对交叉而直接复制到下一代中。这种选择操作又称为复制(copy)。

在进行适应度评估时，保留一定比例适应度最高的个体，在交叉变异完成后，将种群中适应度最低的那部分个体用精英替换。

注意：轮盘赌的实现代码决定个体的适应度应当是非负的，否则会出现错误。

function [bestChromosome,fitnessBest]=GA(numOfChromosome,numOfGene,iterationNum)
%% 函数功能：基于自适应遗传算法最值求解
%   输入：
%       numOfChromosome：染色体数量，即迭代的种群大小
%       numOfGene：基因的数量，即所用二进制编码的位数
%       iterationNum：迭代的总次数，达到迭代次数即终止迭代
%   输出：
%       bestChromosome：最优的染色体（即最优的输入）
%       fitnessBest：最优的适应度值（即最优的结果）

%% 随机生成初始种群，种群大小为numOfChromosome，染色体中基因数为numOfGene
% lastPopulation：上一代的种群（染色体）
% newPopulation：新一代的种群（染色体）
% randi([0,1])会产生0或1的整数
lastPopulation=randi([0,1],numOfChromosome,numOfGene);
newPopulation=zeros(numOfChromosome,numOfGene);

%% 进行遗传迭代，直至达到最大迭代次数iterationNum
for iteration=1:iterationNum
    %% 计算所有个体（染色体）的适应度，一共有numOfChromosome个适应度值
    fitnessAll=zeros(1,numOfChromosome);
    for i=1:numOfChromosome
        individual=lastPopulation(i,:);
        fitnessAll(i)=fitnessFunc(individual);
    end
    %% 从种群中挑选出精英并备份
    [~,descendOrder]=sort(fitnessAll,'descend');
    elitePercent=0.1;
    eliteSum=fix(numOfChromosome*elitePercent);
    eliteIndex=zeros(1,eliteSum);
    for ii=1:eliteSum
        eliteIndex(ii)=descendOrder(ii);
    end
    elite=lastPopulation(eliteIndex,:);
    %% 如果达到最大迭代次数，跳出（不能再进行选择遗传和变异了）
    if iteration==iterationNum
        break;
    end
    
    %% 使用轮盘赌法选择numOfChromosome条染色体，种群中个体总数不变
    fitnessSum=sum(fitnessAll);
    fitnessProportion=fitnessAll/fitnessSum;
    % 使用随机数进行numOfChromosome次选择，保持种群中个体数量不变
    for i=1:numOfChromosome
        probability=rand(1);
        proportionSum=0;
        chromosomeIndex=1;
        for j=1:numOfChromosome
            proportionSum=proportionSum+fitnessProportion(j);
            if proportionSum>=probability
                chromosomeIndex=j;
                break;
            end
        end
        newPopulation(i,:)=lastPopulation(chromosomeIndex,:);
    end

    %% 将染色体进行配对，执行单点交叉
    lastPopulation=newPopulation;
    % 生成从1到numOfChromosome的无序排列，每两个相邻数字进行配对
    coupleAllIndex=randperm(numOfChromosome);
    for i=1:floor(numOfChromosome/2)
        coupleOneIndex=coupleAllIndex(2*i-1:2*i);
        % 定义两条染色体交叉的概率，自己选择
        probability=0.6;
        % 如果生成的随机数在交叉概率内，执行交叉操作
        if rand(i)<probability
            % 随机生成交叉的基因点，将两条基因进行交叉
            crossPosition=randi([1,numOfGene],1);
            newPopulation(coupleOneIndex(1),crossPosition:end)=lastPopulation(coupleOneIndex(2),crossPosition:end);
            newPopulation(coupleOneIndex(2),crossPosition:end)=lastPopulation(coupleOneIndex(1),crossPosition:end);
        end
    end

    %% 对每条染色体执行基本位变异操作
    lastPopulation=newPopulation;
    for i=1:numOfChromosome
        % 定义染色体变异的概率，自己选择
        probability=0.2;
        % 如果生成的随机数在变异概率内，执行变异操作
        if rand(1)<probability
            % 选择变异的位置
            mutatePosition=randi([1,numOfGene],1);
            % 将对应基因位置的二进制数反转
            if(lastPopulation(i,mutatePosition)==0)
                newPopulation(i,mutatePosition)=1;
            else
                newPopulation(i,mutatePosition)=0;
            end
        end
    end 
    
    %% 将适应度低的个体替换为精英
    fitnessAll=zeros(1,numOfChromosome);
    for i=1:numOfChromosome
        individual=newPopulation(i,:);
        fitnessAll(i)=fitnessFunc(individual);
    end
    [~,ascendOrder]=sort(fitnessAll);
    weakIndex=zeros(1,eliteSum);
    for ii=1:eliteSum
        weakIndex(ii)=ascendOrder(ii);
    end
    newPopulation(weakIndex,:)=elite;
    %% 完成了一次迭代，更新种群
    lastPopulation=newPopulation;
end

%% 遗传迭代结束后，获得最优适应度值和对应的基因
fitnessBest=max(fitnessAll);
bestChromosome=newPopulation(find(fitnessAll==fitnessBest,1),:);

适应度评估函数

function fitness=fitnessFunc(chromosome)
%% 函数功能：计算染色体的表现型及其适应度
% 输入：
%       chromosome：染色体的基因序列
% 输出：
%       fitness：染色体（个体）的适应度值

%% 计算雪兔染色体对应表现型
len=length(chromosome);
numList=2.^(len-1:-1:0);
x=sum(chromosome.*numList);

%% 计算表现型对应的适应度
if x<1024
    fitness=x;
else
    if x>1024
        fitness=2048-x;
    else
        fitness=1024;
    end
end