遗传算法
以上，就是利用遗传算法，经过10,000次演化得到的由100个三角形组成的MATLAB图标。
参考
遗传算法原理
软件实现
其中idea来自科学松鼠会，通过直观的方式理解遗传算法。源代码来源于网络，个人进行注释与并行处理。另外由于GPU问题，没有进行GPU加速。
“遗传算法是计算数学中用于解决最佳化的搜索算法，是进化算法的一种。进化算法最初是借鉴了进化生物学中的一些现象而发展起来的，这些现象包括遗传、突变、自然选择以及杂交等。”
所以，以下程序包括，遗传、突变、选择，交叉。遗传算法属于启发式算法，故在此就不进行证明等理论性工作。
程序解释
遗传算法脚本，其中在数据读取与参数设定里面，确定了种群数目等参数，参数确定后，将其与原始图片传入GA_Triangle_Draw函数内部，进行下一步的处理。接下来让我们共同理解遗传算法内部的运算与逻辑。
%% 数据读取与参数设定
[filename, pathname] = uigetfile({'*.jpg;*.tif;*.png;*.gif',...
'选择图片文件'});
% 读取文件
pic_origin = imread(fullfile(pathname,filename));
figure;
imshow(pic_origin);
% 读取并显示选择图片
individual_amount = 100;
% 种群数目
outstanding_gene_amount = 10;
% 卓越基因数目，本算法对卓越基因格外照顾
target_accuracy = 0.999;
% 目标准确率
generation_number = 100000;
% 最大代数，达到最大代数后即时没有达到目标准确率也停止
triangle_num = 3;
% 三角形个数
Pc = 0.7; % 交叉概率
Pcn = 0.3; % 交叉位置数目
Pm = 0.001; % 基因突变概率
%% 遗传算法主体
pic_out = GA_Triangle_Draw(pic_origin ,individual_amount ,outstanding_gene_amount ,target_accuracy ,generation_number ,Pc ,Pcn ,Pm,triangle_num);
%% 目标图像保存与显示
figure;
imshow(pic_out);
new_filename = regexp(filename,'(\w+)[.]','tokens');
new_filename = [new_filename{1}{1},'_Triangle.jpg'];
imwrite(pic_out,new_filename);
在如下的GA_Triangle_Draw函数中：
第一步，我们创建了有关图片的随机种群。
第二步，通过并行运算计算不同种群之间的适应度，这极大地节约了运算的时间开支。
第三步，然后保留最好的基因，并根据轮盘赌法，决定种群生存下来的个体基因。由于优化并非单调，难免存在局部最优不等于全局最优的结果，所以通过随机淘汰（适应度决定淘汰概率）来避免结果收敛于局部最优。
第四步，通过基因的交叉互换，随机交换存活下来的个体，从而提高种群的整体质量。
第五步，基因突变。如果只有第三第四步，基因难免重复，从而落入死循环中，通过小概率的基因突变，为种群基因库增添新的基因。虽然突变具有多害少利性，但通过突变可以增加种群的丰富度。
function pic_out = GA_Triangle_Draw(pic_origin ,individual_amount ,outstanding_gene_amount ,target_accuracy ,generation_number ,Pc ,Pcn ,Pm,triangle_num)
%% 数据预处理
[W,L,~] = size(pic_origin);
pic_resize = double(imresize(pic_origin,[256,256]));
total_amount = individual_amount + outstanding_gene_amount;
%% 创建种群
population = char(randi([48,49],72*triangle_num,total_amount));
% ACSII码48、49对应的值为0、1，以此表示二进制基因
%且染色体长度为7200
% optimal_fitness：最优适应度
% optimal_gene：最优适应度对应的基因
fitness_array = zeros(1,total_amount);
%% 遗传算法
figure('Name','optimal_gene');
for generation_counter = 1:generation_number
parfor i=1:total_amount
% 并行计算适应度
gene = population(:,i);
fitness_array(i) = Calculate_Fitness(pic_resize,gene,triangle_num);
end
[optimal_fitness, idx] = max(fitness_array);
optimal_gene = population(:,idx);
% 筛选出最优适应度与对应的基因
if optimal_fitness>=target_accuracy
break;
end
%% 选择给定数量的最优子代，直接遗传到下一代
[~,idx] = sort(fitness_array);
outstanding_gene = population(:, idx(end-outstanding_gene_amount+1:end));
%% 轮盘赌法选择基因
new_population = roulette_selection(population,fitness_array,outstanding_gene,individual_amount, total_amount,triangle_num);
% population： 种群
% fitness_array： 适应度数组
% outstanding_gene： 最优的基因
% individual_amount： 种群数量
% total_amount： 种群数量加最优基因的数量
% triangle_num: 三角形个数
%% 交叉基因
new_population = crossover(new_population,outstanding_gene,Pc,Pcn,total_amount,outstanding_gene_amount,triangle_num);
% new_population： 新的种群
% outstanding_gene： 最优的基因
% Pc： 交叉概率
% Pcn： 交叉位置数目
% total_amount： 种群数量加最优基因的数量
% outstanding_gene_amount： 最优基因的数量
% triangle_num: 三角形个数
%% 基因突变
population = mutation(new_population,outstanding_gene,Pm,total_amount,outstanding_gene_amount,triangle_num);
% new_population：： 新的种群
% outstanding_gene： 最优的基因
% Pm： 基因突变概率
% total_amount： 种群数量加最优基因的数量
% outstanding_gene_amount： 最优基因的数量
% triangle_num: 三角形个数
%% 数据输出
disp(['generation_',num2str(generation_counter),': ',num2str(optimal_fitness)]);
pic_out = Draw_Picture(optimal_gene,triangle_num);
pic_out = imresize(pic_out,[W,L]);
imshow(uint8(pic_out));
end
pic_out = Draw_Picture(optimal_gene,triangle_num);
pic_out = imresize(pic_out,[W,L]);
end
轮盘赌法选择基因，具体的思想是累加确定一个cdf，然后通过随机数归类，进行生还个体的选择。其实还可以通过rand之间的比较来确定，这里就不着重说明。
function new_population = roulette_selection(population, fitness_array, outstanding_gene, individual_amount, total_amount,triangle_num)
% 轮盘赌法选择基因
fitness_array_norm = fitness_array / sum(sum(fitness_array));
% 适应度归一化
fitness_array_cum = [0, cumsum(fitness_array_norm)];
roulette_number = rand(1,individual_amount);
survive_index = discretize(roulette_number ,fitness_array_cum);
% 将数据分组到类别中；累加过程中适应度越大，区间数据越多
new_population = zeros(72*triangle_num,total_amount);
new_population(:,1:individual_amount) = population(:,survive_index);
new_population(:,individual_amount+1:total_amount) = outstanding_gene;
new_population = new_population(:,randperm(total_amount));
% 随机置换，打乱new_population中的基因顺序
end
交叉基因。主要思想是通过随机生成的成对的1与-1，在原有index上进行运算，从而保证在基因交换的同时而数据不发生丢失。
function new_population = crossover(new_population,outstanding_gene,Pc,Pcn,total_amount,outstanding_gene_amount,triangle_num)
% 交叉基因
crossover_index = rand(1,total_amount/2)<Pc;
% 交叉概率
crossover_gene_index = repelem((rand(9*triangle_num,total_amount/2)<Pcn), 8, 1);
% 交叉位置数目
crossover_gene_index(:,~crossover_index) = 0;
% 非交叉基因部位的索引为0
gene_index_diff = zeros(72*triangle_num,total_amount);
gene_index_diff(:,1:2:total_amount) = crossover_gene_index;
gene_index_diff(:,2:2:total_amount) = -crossover_gene_index;
%
[X,Y] = meshgrid(1:total_amount,1:72*triangle_num);
new_gene_index = sub2ind([72*triangle_num,total_amount],Y,X+gene_index_diff);
% 将下标转换为线性索引
new_population = new_population(new_gene_index);
tmpIdx = total_amount-outstanding_gene_amount+1:total_amount;
new_population(:,tmpIdx) = outstanding_gene;
end
基因变异。通过随机数的比较，来确定变异的index。
function new_population = mutation(new_population,outstanding_gene,Pm,total_amount,outstanding_gene_amount,triangle_num)
% 基因突变
mutation_index = rand(72*triangle_num,total_amount)<Pm;
new_population = char(uint8(xor(new_population>48,mutation_index))+48);
% 将数值转化为二进制基因表示
tmpIdx = total_amount-outstanding_gene_amount+1:total_amount;
new_population(:,tmpIdx) = outstanding_gene;
end
最后缺少的就是绘图的函数，与计算适应度函数中的部分代码，如insertShape等极其相似，因此不做过多的解释，详情可以使用MATLAB自带的documentation。
function pic_out = Draw_Picture(gene,triangle_num)
% 绘图
% 类似方法也在Calculate_Fitness里面使用
triangle_point = gene(1:48*triangle_num);
triangle_color = gene(48*triangle_num+1:72*triangle_num);
triangle_point = reshape(triangle_point,6*triangle_num,8);
triangle_color = reshape(triangle_color,3*triangle_num,8);
triangle_point = bin2dec(triangle_point) + 1;
triangle_color = bin2dec(triangle_color);
triangle_point = reshape(triangle_point,triangle_num,6);
triangle_color = reshape(triangle_color,triangle_num,3);
pic_out = insertShape(ones(256,256,3)*255,'FilledPolygon',triangle_point,'Color',triangle_color,'Opacity',0.7);
pic_out = uint8(pic_out);
end
计算适应度则是将生成图像与原图每个元素进行比较，差别越少则适应度越高。
function Fitness = Calculate_Fitness(pic ,gene,triangle_num)
max_diff = 255^3*3;
% 由于图像为256*256，且为三通道，数据极差为255
% 故在数据归一化时使用max_diff
[W,L,~] = size(pic);
triangle_point = gene(1:48*triangle_num);
% 三角形的顶点由1::4800决定
triangle_color = gene(48*triangle_num+1:72*triangle_num);
% 三角形的颜色由4801:7200决定
triangle_point = reshape(triangle_point,6*triangle_num,8);
triangle_color = reshape(triangle_color,3*triangle_num,8);
triangle_point = bin2dec(triangle_point) + 1;
triangle_color = bin2dec(triangle_color);
% 将用文本表示的二进制数字转换为十进制数字
triangle_point = reshape(triangle_point,triangle_num,6);
% 每行六个数据分别表示三个点的横纵坐标
triangle_color = reshape(triangle_color,triangle_num,3);
% 每行三个数据分别颜色的RGB
pic_gene = insertShape(ones(W,L,3)*255,'FilledPolygon',triangle_point,'Color',triangle_color,'Opacity',0.7);
% Insert shapes in image or video
Fitness = abs(pic - pic_gene);
Fitness = 1 - sum(Fitness(:))/max_diff;
% 计算适应度
end
文字：Iydon