A 50-line matlab implementation of a genetic algorithm
已有 1475 次阅读
|个人分类:|系统分类:|关键词:遗传算法
首先给出全部源代码:一个用matlab实现的50行的遗传算法程序 &1 引言遗传算法 (genetic algorithms) 是一种很有意思最优化方法，常用于解决一些传统方法力所不及的多变量最优化问题。这种方法很通用，即用同样的思想可以解决很多不同的问题。只要你能对问题所有可能的解定义一个反映其好坏程度的量，就有可能用遗传算法找到高质量的解。遗传算法的应用十分广泛，编程实现也很容易。本文介绍遗传算法的基本概念和算法流程，给出一个用matlab实现的50行的遗传算法程序，并用一个简单的例子展示它的应用。2 遗传算法的基本概念2.1 生物学中的相关概念 与遗传算法有关的生物学概念主要有： a)染色体（chromosome）。所有生物都由细胞组成，每一个细胞中都有一套相同的染色体。一条染色体由若干基因(gene) 组成，每个基因控制一种特定的蛋白质，从而决定生物的某种特征。所有染色体合称为基因组(genome)。基因组完全决定了一个生物个体。该个体在微观（基因）层次的表现称为基因型 (genotype)，在宏观（特征）层次的表现称为显型 (phenotype)。在简单的遗传算法中，将基因组中的若干条染色体看作一整条染色体。 b)个体复制。在复制的过程中，父母的染色体通过交叉（crossover）产生子女的染色体。染色体还可以以一定的小概率变异（mutate）。 2.2 遗传算法的基本概念 在一般的遗传算法应用中，我们研究的是这样的优化问题：对一个有 N 个参数 x_i (1 &= i &= N) 的实函数 f(x_i) (该函数可以有任何形式；我们不要求它有任何解析性质)，找到一组合适的参数使得该函数的值尽可能地大或者尽可能地小。该函数叫做适应度函数 (fitness function)，其值叫做适应度。 下面我们用这个最优化问题结合上面的生物学概念说明遗传算法中的基本概念：a)个体，问题的一个可能的解，即任何一组参数。这组参数也叫基因型，对应的函数值叫做显型。b)解空间，又叫搜索空间，即所有参数构成的 N 维空间。c)种群 (population)，即一定数量的个体的集合。该数量叫做种群规模 (population size)。 遗传算法的每一次循环中的种群称为一代 (generation)。每一代中最好的解叫做精英 (elite)。 3. 遗传算法的基本流程
首先，随机产生一个初始种群。遗传演化开始计算当前种群中所有个体的适应度根据适应度的大小选择一部分较好的个体，使其存活下来并繁殖子女（所谓“适者生存”）用遗传操作(genetic operators) 繁殖子女（子女数目等于死去的个体的数目），包括交叉：将两个候选者的染色体以某种方式交叉，产生两个新的个体的染色体变异：以某种方式随机改变一些个体的染色体的部分基因在每一代中，精英都会记录下来，且不参与变异若找到了足够好的解，则可提前终止演化遗传演化结束4. 一个50行的matlab函数下面直接给出一个实现简单的遗传算法的matlab函数。此函数虽短小，但却很通用。它适用于任何实数基因的情形。这里的实数是与整数（包括二进制数）对应的。在很多遗传算法的应用中，部分或者全部变量的值仅能取整数。我给出的函数不适用于这种离散变量的情形，但通过少量的修改可以变成适用于该情形的函数。若读者对这样的应用感兴趣，可以自行修改。我的程序中有大量的注释，可以帮助理解。有两点要注意：1）该函数假定我们的目标是求一个函数的最小值。若我们目标是求最大值，则可将函数f(x)换成-f(x)。2) 该函数假定每个变量的取值范围都是[0, 1]。也就是说，矩阵population的每个元素的值都在此区间。在编写适应度函数时要根据具体问题对变量进行变换。function [best_fitness, elite, generation] = my_ga(number_of_variables, fitness_function, ... & &population_size, parent_number, mutation_rate, maximal_generation, minimal_cost)% number_of_variables = 求解问题的参数个数 % fitness_function = 自定义适应度函数名 % population_size = 种群规模（每一代个体数目） % parent_number = 每一代中保持不变的数目（除了变异）% mutation_rate = 变异概率% maximal_generation = 最大演化代数% minimal_cost = 最小目标值（函数值越小，则适应度越高）cumulative_probabilities = cumsum((parent_number:-1:1) ... & & & & & & & & & & & & / sum(parent_number:-1:1)); %一个从0到1增长得越来越慢的函数best_fitness = ones(maximal_generation, 1); % 用于记录每一代的最佳适应度elite = zeros(maximal_generation, number_of_variables); % 用于记录每一代的最优解child_number = population_size - parent_ % 每一代子女的数目population = rand(population_size, number_of_variables); % 初始化种群for generation = 1 : maximal_generation % 演化循环开始 & &cost = feval(fitness_function, population); % 计算所有个体的适应度 & &[cost, index] = sort(cost); % 将适应度函数值从小到大排序 & &population = population(index(1:parent_number), :); % 先保留一部分较优的个体 & &best_fitness(generation) = cost(1); % 记录本代的最佳适应度 & &elite(generation, :) = population(1, :); % 记录本代的最优解（精英） & &if best_fitness(generation) & minimal_ end % 若最优解已足够好，则停止演化 & & & &for child = 1:2:child_number % 染色体交叉开始 & & & &mother = min(find(cumulative_probabilities & rand)); % 选择一个较优秀的母亲 & & & &father = min(find(cumulative_probabilities & rand)); % 选择一个较优秀的父亲 & & & &crossover_point = ceil(rand*number_of_variables); % 随机地确定一个染色体交叉点 & & & &mask1 = [ones(1, crossover_point), zeros(1, number_of_variables - crossover_point)]; & & & &mask2 = not(mask1); & & & &mother_1 = mask1 .* population(mother, :); % 母亲染色体的前部分 & & & &mother_2 = mask2 .* population(mother, :); % 母亲染色体的后部分 & & & &father_1 = mask1 .* population(father, :); % 父亲染色体的前部分 & & & &father_2 = mask2 .* population(father, :); % 父亲染色体的后部分 & & & &population(parent_number + child, :) = mother_1 + father_2; % 一个孩子 & & & &population(parent_number+child+1, :) = mother_2 + father_1; % 另一个孩子 & &end % 染色体交叉结束 & & & &% 染色体变异开始 & &mutation_population = population(2:population_size, :); % 精英不参与变异 & &number_of_elements = (population_size - 1) * number_of_ % 全部基因数目 & &number_of_mutations = ceil(number_of_elements * mutation_rate); % 将要变异的基因数目 & &mutation_points = ceil(number_of_elements * rand(1, number_of_mutations)); % 确定要变异的基因 & &mutation_population(mutation_points) = rand(1, number_of_mutations); % 对选中的基因进行变异操作 & &population(2:population_size, :) = mutation_ % 发生变异之后的种群 & &% 染色体变异结束 & &end % 演化循环结束5. 一个简单的例子考虑一个浅显的例子：计算函数 的最小值，其中每个变量的取值区间都是[-1, +1]。我们知道该问题的最优解：每个x_i都等于0。如果用遗传算法研究这个问题，我们可以写出如下适应度函数（注意matlab矢量化编程的技巧）：function y = my_fitness(population)population = 2 * population - 1; y = sum(population.^2, 2);写好了适应度函数，再写一个脚本调用遗传算法函数并画图即可完成任务。脚本内容如下：% 调用 my_ga 进行计算[best_fitness, elite, generation] = my_ga(10, 'my_fitness', 100, 50, 0.1, 1e-6);% 最佳适应度的演化情况figureloglog(1 : generation, best_fitness(1 : generation), 'linewidth',2)xlabel('Generation','fontsize',15);ylabel('Best Fitness','fontsize',15);set(gca,'fontsize',15,'ticklength',get(gca,'ticklength')*2);% 最优解的演化情况figuresemilogx(1 : generation, 2 * elite(1 : generation, :) - 1)xlabel('Generation','fontsize',15);ylabel('Best Solution','fontsize',15);set(gca,'fontsize',15,'ticklength',get(gca,'ticklength')*2);此脚本的计算只需一秒钟左右。计算结束后，会出现如下两幅图：此图展示最佳适应度（对于最小化问题，函数值越小，适应度越高）随演化代数增加而变化的情况。可以看出，函数值很快向最小值0趋近。当函数值低于设定的最小值10^(-6)时，演化提前终止。此图展示最优解变量随演化代数增加而变化的情况。可以看出，所有变量都趋近于0，与正确解一致。
转载本文请联系原作者获取授权，同时请注明本文来自樊哲勇科学网博客。链接地址：
上一篇：下一篇：
当前推荐数：0
评论 ( 个评论)
扫一扫，分享此博文
作者的精选博文
作者的其他最新博文
热门博文导读
Powered by
Copyright &1 用matlab编写的采用遗传算法进行图像分割的一个程序
238万源代码下载-
&文件名称: 1
& & & & &&]
&&所属分类:
&&开发工具: matlab
&&文件大小: 343 KB
&&上传时间:
&&下载次数: 47
&&提 供 者:
&详细说明：用matlab编写的采用遗传算法进行图像分割的一个程序-using Matlab prepared using genetic algorithms for image segmentation of a program
文件列表(点击判断是否您需要的文件，如果是垃圾请在下面评价投诉):
&&1\func_DWT.asv&&.\func_Main.asv&&.\func_Main2.asv&&.\func_Main2.m&&.\func_Main3.asv&&.\func_Main3.m&&.\func_Main4.m&&.\func_Mywavedec2.asv&&.\func_wavelet_packet.asv&&.\func_wavelet_packet.m&&.\my_syn1_result.mat&&.\new2.bmp&&.\new2_1.bmp&&.\new3.bmp&&.\new4.bmp&&.\new5.bmp&&.\sar.bmp&&1
&[]:纯粹是垃圾
&近期下载过的用户:
&相关搜索:
&输入关键字，在本站238万海量源码库中尽情搜索：
&[] - 本程序时应用MATLAB分割技术中的区域生长来实现图像分割
&[] - 利用遗传算法进行图像分割(matlab源码)[matlab]
&[] - 遗传算法图像分割，利用遗传算法进行图像分割
&[] - 基于改进遗传算法的图像分割，算法中引入了优生算子、改进的变异算子和新个体,避免了局部早熟,提高了收敛速度和全局收敛能力。
&[] - 遗传算法对于图像分割有着最重要的意义，可以对边界有着很好的检测
&[] - 一个遗传算法图像分割程序. 对于图片分割的效果相当理想.
&[] - matlab遗传算法工具箱，包括所有的m文件，还有例子，丰富，实用，扩展性强，欢迎大家下载。
&[] - This program is a Matlab code for finding optimal solution of tower crane location in construction project using GENETIC Algorithm
&[] - GENETIC algorithm
&[] - 经典遗传算法工具箱中的最大代数终止程序，与大家分享君，已阅读到文档的结尾了呢~~
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
基于遗传算法的研究与Matlab代码的实现
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口1775人阅读
图像处理（16）
matlab学习笔记（5）
利用最佳直方图熵法（KSW熵法）及传统遗传算法实现灰度图像二阈值分割
matlab代码如下：
1、main.m(主函数)：
I=imread('D:\MATLAB\work\2.21.jpg');
figure(1),imshow(I);
I=rgb2gray(I);
hist=imhist(I);
for i=0:255
total=total+hist(i+1);
hist1=hist/
population=20;
X00=round(rand(1,population)*255);
X01=round(rand(1,population)*255);
for i=1:population
X0(i,:)=[X00(i) X01(i)];
for i=1:population
if X0(i,1)&X0(i,2)
temp=X0(i,1);
adapt_value0(i)=ksw_2(X0(i,1),X0(i,2),0,255,hist1);
adapt_average0=mean(adapt_value0);
adapt_value1=adapt_value0;
adapt_average1=adapt_average0;
generation=100;
for k=1:generation
s1=select_2d(X1,adapt_value1);
s_code10=dec2bin(s1(:,1),8);
s_code11=dec2bin(s1(:,2),8);
[c10,c11]=cross_2d(s_code10,s_code11);
[v10,v11]=mutation_2d(c10,c11);
X20=(bin2dec(v10))';
X21=(bin2dec(v11))';
for i=1:population
X2(i,:)=[X20(i) X21(i)];
for i=1:population
adapt_value2(i)=ksw_2(X2(i,1),X2(i,2),0,255,hist1);
adapt_average2=mean(adapt_value2);
if abs(adapt_average2-adapt_average1)&=0.03
adapt_value1=adapt_value2;
adapt_average1=adapt_average2;
max_value=max(adapt_value2);
number=find(adapt_value2==max_value);
opt=X2(number(1),:);
search_time=etime(t1,t0);
I_temp1=I;
[height,width]=size(I_temp1)
for i=1:height
for j=1:width
if I_temp1(i,j)&opt(1);
I_temp1(i,j)=0;
else if I_temp1(i,j)&opt(2);
I_temp1(i,j)=255;
else I_temp1(i,j)=180;
I1= I_temp1;
disp('灰度图像阈值分割的效果如图所示：');
disp('源图为：Fifure No.1');
disp('最佳直方图熵法及传统遗传算法阈二值分割后的图像为：Fifure No.2');
figure(2);
imshow(I);
title('源图');
figure(3);
imshow(I1);
title('最佳直方图熵法及传统遗传算法阈二值分割后的图像');
disp('最佳直方图熵法及传统遗传算法二阈值为(s,t)：');
disp(opt(1));
disp(opt(2));
disp('最佳直方图熵法及传统遗传算法二阈值搜索所用时间（s）：');
disp(search_time);
function s1=select_2d(X1,adapt_value1)
population=20;
total_adapt_value1=0;
for i=1:population
total_adapt_value1=total_adapt_value1+adapt_value1(i);
adapt_value1_new=adapt_value1/total_adapt_value1;
r=rand(1,population);
for i=1:population
for j=1:population
temp=temp+adapt_value1_new(j);
if temp&=r(i)
s1(i,:)=X1(j,:);
function [c10,c11]=cross_2d(s_code10,s_code11)
population=20;
ww0=s_code10;
ww1=s_code11;
for i=1:(pc*population/2)
r0=abs(round(rand(1)*10)-3);
r1=abs(round(rand(1)*10)-3);
for j=(r0+1):8
temp0=ww0(2*i-1,j);
ww0(2*i-1,j)=ww0(2*i,j);
ww0(2*i,j)=temp0;
for j=(r1+1):8
temp1=ww1(2*i-1,j);
ww1(2*i-1,j)=ww1(2*i,j);
ww1(2*i,j)=temp1;
function [v10,v11]=mutation_2d(c10,c11)
population=20;
for i=1:population
r0=rand(1);
r1=rand(1);
temp0(i,j)=c10(i,j);
tt=not(str2num(c10(i,j)));
temp0(i,j)=num2str(tt);
temp1(i,j)=c11(i,j);
tt=not(str2num(c11(i,j)));
temp1(i,j)=num2str(tt);
v10=temp0;
v11=temp1;
function y=ksw_2(s,t,mingrayvalue,maxgrayvalue,hist1)
for i=mingrayvalue:s;
Ps=Ps+hist1(i+1);
for i=s:t;
Pt=Pt+hist1(i+1);
Pn=Pn+hist1(i+1);
for i=mingrayvalue:s
if hist1(i+1)==0
temp=hist1(i+1)*log(1/hist1(i+1));
if hist1(i+1)==0
temp=hist1(i+1)*log(1/hist1(i+1));
for i=t:maxgrayvalue
if hist1(i+1)==0
temp=hist1(i+1)*log(1/hist1(i+1));
if Ps==0 || Ps==1||Pt==0 || Pt==1||Pn==0 || Pn==1
temp1=log(Ps)+log(Pt)+log(Pn)+Hs/Ps+Ht/Pt+Hn/Pn;
if temp1 & 0
运行结果如下：
灰度图像：
双阈值分割图像：
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：80237次
积分：1904
积分：1904
排名：第18612名
原创：107篇
评论：22条
(3)(77)(32)(5)(2)}