1 遗传算法（Genetic Algorithm）
1.1简介
GA是一种进化算法，基本原理效仿生物界“物竞天择，适者生存”的演化法则。
一些基本概念
种群population：问题潜在的解集
个体individual：每一个可能的解，通过基因编码一定数目的个体形成一个种群
适应度fitness：由此判断个体的优良，进而进行选择
选择selection、交叉crossover、变异mutation
编码：实现从表现型到基因型的映射
解码：反之得到问题最优解
首先将问题的解进行编码以适配GA，产生初代种群，在每一代中根据适应度大小选择个体，并借助遗传算子（genetic operator）进行交叉和变异，产生代表新解集的种群，末代种群的最优个体经过解码，作为问题近似最优解。
1.2三个基本操作
选择：从当前种群中选出优良个体，作为父代进行繁衍，使适应度强的个体为下一代贡献一个或多个后代的概率大。
交叉：通过交叉得到新一代个体，新个体组合父辈个体特征。个体随机成对，以交叉概率交换它们之间部分染色体。
变异：每一个个体以变异概率改变一个或多个基因座上基因值为其他的等位基因。与生物界相似，变异发生概率很低。
交叉和变异保证了个体和解空间的多样性。
1.3基本步骤
编码：将解空间的解数据表示成遗传空间的基因型串结构数据，串结构数据的不同组合便构成了不同的点。
初始种群的生成：随机产生N个初始串结构数据，每个串结构数据为一个个体，N个个体构成一个种群。GA以这N个串结构数据作为初始点开始进化。
适应度评估：适应度表示个体或解的优劣性。不同问题，适应度函数定义不同。
选择
交叉
变异
1.4 GA工具箱
MATLAB内嵌工具箱：gadst
Sheffield大学：gatbx
北卡罗来纳大学：gaot
三者都差不多，开源（gaot）的可以看到代码，更好理解
1.5重点函数解读（gaot）
initializega
初始化种群
pop = initializega（populationSize，variableBounds，evalFN，evalOps，options）
ga
遗传算法
[x，endPop，bPop，traceInfo] = ga（bounds，evalFN，evalOps，startPop，opts，termFN，termOps，selectFN，selectOps，xOverFNs，xOverOps，mutFNs，mutOps）
1.5.1一元函数优化
一元函数优化，默认为求最大值，如果要求最小值将适应度函数取倒数或者取负号
x = 0:0.01:9;
y = x + 10*sin(5*x)+7*cos(4*x);
%求上述函数的最大值%适应度函数
function [sol, fitnessVal] = fitness(sol, options)x = sol(1);fitnessVal = x + 10*sin(5*x)+7*cos(4*x);end
%% I. 清空环境变量
clear all
clc%% II. 绘制函数曲线
x = 0:0.01:9;
y = x + 10*sin(5*x)+7*cos(4*x);figure
plot(x, y)；
xlabel('自变量')；
ylabel('因变量')；
title('y = x + 10*sin(5*x) + 7*cos(4*x)')；%% III. 初始化种群
initPop = initializega(50,[0 9],'fitness');%% IV. 遗传算法优化
[x, endPop, bpop, trace] = ga([0 9],'fitness',[],initPop,[1e-6 1 1],'maxGenTerm',25,...'normGeomSelect',0.08,'arithXover',2,'nonUnifMutation',[2 25 3]);%% V. 输出最优解并绘制最优点
x
hold on
plot (endPop(:,1),endPop(:,2),'ro')%% VI. 绘制迭代进化曲线
figure(2)
plot(trace(:,1),trace(:,3),'b:')
hold on
plot(trace(:,1),trace(:,2),'r-')
xlabel('Generation'); ylabel('Fittness');
legend('Mean Fitness', 'Best Fitness')结果：
1.5.2 二元函数优化
function [sol, fitnessVal] = fitness2(sol,options)
x1 = sol(1);
x2 = sol(2);
fitnessVal = cos(x1)-sin(x1).*cos(x2)+sin(x2);
end%% 二元函数GA优化
close all;
clear all;
clc;
%% 二元函数
x1 = 1:0.01:8;
x2 = -3:0.01:7;
[X1,X2] = meshgrid(1:0.01:8,-3:0.01:7);
y = cos(X1)-sin(X1).*cos(X2)+sin(X2);
figure
mesh(X1,X2,y);
title('y=cos(x1)-sin(x1)cos(x2)+sin(x2)');
xlabel('x1');
ylabel('x2');
grid on
%% 初始化种群
pop = initializega(50,[1 8;-3 7],'fitness2');%% GA优化
[x, endPop, bPop, trace] = ga([1 8;-3 7],'fitness2',[],pop,[1e-6 1 1],...'maxGenTerm',30,'normGeomSelect',0.08,'arithXover',2,'nonUnifMutation',[2 25 3]);
%% 画图比较
x
hold on
plot3(x(1),x(2),x(3),'ro');
plot3(endPop(:,1),endPop(:,2),endPop(:,3),'b+');
figure
plot(trace(:,1),trace(:,2),'r-');%best
hold on
plot(trace(:,1),trace(:,3),'b--');%average
xlabel('Generation'); ylabel('Fittness');
legend('Best Fitness', 'Average Fitness')结果：
2 MATLAB GA工具箱使用
主要功能是求最小值，如果求最大值可以把目标函数乘以-1
function f = fitness(x)
f = (x(1)-2)^2+(x(2)-1)^2+(x(3)-7)^2+(x(4)-9)^2;
end%% 线性不等式约束
A = [-1 2 -1 1;-2 -1 2 -1];
b = [-1;-5];注意：不等式约束默认为小于等于零，所以上面的系数都加了负号。
%非线性约束，m为不等式，n为等式，多个式子时写成矩阵形式
function [m,n] = nonlinear(x)
m = -1*(x(1)^2/4-x(2)^2+x(3)-x(4)^2+1);
n = x(1)^2+x(2)-x(3)+x(4)-99;
end结果：
注意
整数约束如上所示，整数规划和非线性等式约束不能同时存在
