wordpress.org账号,标题关键词优化报价,越秀公司网站建设,网页制作与网页设计简历遗传算法 1.什么是遗传算法
遗传算法#xff08;Genetic Algorithm#xff0c;简称GA#xff09;是一种基于生物进化论和遗传学原理的全局优化搜索算法。它通过模拟自然界中生物种群的遗传机制和进化过程来解决复杂问题#xff0c;如函数优化、组合优化、机器学习等。遗传…遗传算法 1.什么是遗传算法
遗传算法Genetic Algorithm简称GA是一种基于生物进化论和遗传学原理的全局优化搜索算法。它通过模拟自然界中生物种群的遗传机制和进化过程来解决复杂问题如函数优化、组合优化、机器学习等。遗传算法具有并行性、全局搜索能力和对问题描述的简单性在很多领域有着广泛应用。
2.遗传算法的基本原理
遗传算法的基本思想是将问题的解表示为“染色体”Chromosome每个染色体由一系列“基因”Gene组成这些基因可以是二进制编码、实数或离散值。算法通过选择、交叉也称为杂交、变异等遗传操作模仿自然选择和遗传变异的过程使种群中的个体逐渐适应环境即找到问题的最优解或近似最优解。
下面我试着用通俗一点的例子来解释什么是“遗传算法”
想象一下在一座起伏的山脉中住着一群人。这些人散居在山脉的不同高度上有的住在山顶有的住在半山腰还有的住在山谷里。突然有一天洪水来袭水位不断上升那些住在低处的人们开始面临危险。但住在高处的人因为地势较高所以能够幸免于难我们可以说这些人对这种“洪水”环境的适应能力更强。
为了确保人类的延续这些适应能力强的人开始繁衍后代。他们的目标是希望通过繁殖能够产生出生活在山脉最高点的后代这样就能完全避免洪水的威胁相当于找到了最完美的生存策略。在这个过程中父母双方的特征我们称之为“基因”会通过一种类似“混合”的方式传递给子女有时候子女身上还会出现一些意料之外的新特征这就是“基因变异”。
遗传算法就像是指导这群人在面对洪水时如何繁衍出能在最高山峰生存的后代的一种智慧。它通过模拟自然界中的选择、交配和变异过程帮助寻找出最适应环境的解决方案。在这个例子中“最高山峰”的横坐标就是我们要找的答案也就是那组能让人们在任何情况下都能生存下来的最优“DNA”。
即变成了求解该函数在区间[0 , 5]上的最大值点的问题。
简而言之遗传算法就像是一种搜索策略它通过模仿自然进化的过程逐步改进并找到解决问题的最佳方案。在这个过程中那些表现更好适应度更高的解决方案会被优先保留和进一步优化直到找到最优解。
3.遗传算法的名词解释
种群Population遗传算法中的一组可能解的集合。每个解都是一个染色体。
染色体Chromosome代表一个可能的解由多个基因组成。
基因Gene染色体上的基本单元通常是一个二进制位或数值表示解的一个部分。
适应度函数Fitness Function用于评估染色体的好坏即解的质量。适应度高的染色体有更大的机会被选中进行遗传操作。
选择Selection根据适应度函数从当前种群中选择优秀的个体进入下一代种群的过程。常用的选择方法有轮盘赌选择、锦标赛选择等。
交叉Crossover两个染色体交换部分基因生成新的染色体。这是遗传算法中实现全局搜索的主要方式。
变异Mutation以很小的概率改变染色体中的某个基因增加种群的多样性防止算法过早收敛。
收敛Convergence当种群中的个体适应度不再显著提高时认为算法已经找到最优解或近似最优解此时算法结束。
遗传算法通过迭代上述过程不断优化种群最终找到满足要求的解。
4.遗传算法程序实现过程
遗传算法实现的一般流程如下
1初始化种群 生成一个初始种群种群中的每一个个体染色体都代表了一个可能的解。 每个个体由一组基因构成基因的编码形式取决于问题的特性可以是二进制、实数或符号编码等。 2评估适应度 使用适应度函数Fitness Function来评估每个个体的适应度这反映了个体在解决特定问题上的性能。 适应度函数应该设计得能够量化个体解的质量以便于比较不同个体的优劣。 3选择Selection 根据个体的适应度值进行选择适应度较高的个体有更高的概率被选中参与后续的遗传操作。 常见的选择策略包括轮盘赌选择、锦标赛选择、排名选择等。 4遗传操作 交叉Crossover选定的个体之间进行基因信息的交换以产生新的后代个体。 变异Mutation以小概率随机改变后代个体的某些基因以增加种群的多样性。 这些操作通常遵循一定的概率规则例如交叉概率和变异概率。 5替换Replacement 新产生的后代个体可能会替代旧的种群成员这个过程可以通过多种策略进行如世代替换、稳态遗传算法等。 有时会使用精英策略Elitism确保种群中最好的个体被保留到下一代。 6终止条件检查 检查是否达到预定的终止条件这可能是固定的迭代次数、种群的平均适应度或最佳适应度达到某个阈值。 如果满足终止条件则算法停止否则继续回到步骤3。 7输出结果 算法结束后输出种群中适应度最高的个体作为最优解。
5.遗传算法代码实现
5.1python代码实现
种群类设计
import numpy as np
# 定义种群类
class Population:def __init__(self, pop_size, chromosome_size):# 初始化种群大小和染色体大小self.pop_size pop_sizeself.chromosome_size chromosome_size# 随机生成初始种群每个基因是0或1self.population np.round(np.random.rand(pop_size, chromosome_size)).astype(np.int)# 初始化适应度值为0self.fit_value np.zeros((pop_size, 1))# 选择染色体方法def select_chromosome(self):# 计算总适应度值total_fitness_value self.fit_value.sum()# 计算每个个体的选择概率p_fit_value self.fit_value / total_fitness_value# 计算累积概率p_fit_value np.cumsum(p_fit_value)# 生成随机点用于轮盘赌选择point np.sort(np.random.rand(self.pop_size, 1), 0)# 初始化选择和新的种群索引fit_in 0new_in 0new_population np.zeros_like(self.population)# 轮盘赌选择新种群while new_in self.pop_size:if point[new_in] p_fit_value[fit_in]:new_population[new_in, :] self.population[fit_in, :]new_in 1else:fit_in 1# 更新种群self.population new_population# 交叉染色体方法def cross_chromosome(self, cross_rate):# 获取种群大小和染色体大小x self.pop_sizey self.chromosome_sizenew_population np.zeros_like(self.population)# 对种群中的染色体进行交叉操作for i in range(0, x-1, 2):# 根据交叉率决定是否交叉if np.random.rand(1) cross_rate:# 生成交叉点insert_point int(np.round(np.random.rand(1) * y).item())# 交叉染色体new_population[i, :] np.concatenate([self.population[i, 0:insert_point], self.population[i1, insert_point:y]], 0)new_population[i1, :] np.concatenate([self.population[i1, 0:insert_point], self.population[i, insert_point:y]], 0)else:# 不交叉则直接复制new_population[i, :] self.population[i, :]new_population[i 1, :] self.population[i 1, :]# 更新种群self.population new_population# 寻找最佳个体方法def best(self):# 初始化最佳个体和适应度值best_individual self.population[0, :]best_fit self.fit_value[0]# 遍历种群寻找最佳个体for i in range(1, self.pop_size):if self.fit_value[i] best_fit:best_individual self.population[i, :]best_fit self.fit_value[i]return best_individual, best_fit# 突变染色体方法def mutation_chromosome(self, mutation_rate):# 获取种群大小x self.pop_size# 对种群中的染色体进行突变操作for i in range(x):if np.random.rand(1) mutation_rate:# 生成突变点m_point int(np.round(np.random.rand(1) * self.chromosome_size).item())# 突变操作if self.population[i, m_point] 1:self.population[i, m_point] 0else:self.population[i, m_point] 1# 二进制转十进制方法def binary2decimal(self, population):pop1 np.zeros_like(population)y self.chromosome_size# 转换二进制到十进制for i in range(y):pop1[:, i] 2 ** (y - i - 1) * population[:, i]pop np.sum(pop1, 1)pop2 pop * 10 / (1 y)return pop2# 计算目标函数值方法def cal_obj_value(self):# 将二进制表示转换为十进制表示x self.binary2decimal(self.population)# 计算并更新适应度值self.fit_value 10 * np.sin(5 * x) 7 * np.abs(x - 5) *测试*
from GA遗传算法.Population import Population
import numpy as npcross_rate 0.6
mutation_rate 0.001
pop_size 100
chromosome_size 10
population Population(100, 10)for i in range(100):population.cal_obj_value()population.select_chromosome()population.cross_chromosome(cross_rate)population.mutation_chromosome(mutation_rate)best_individual, best_fit population.best()best_individual np.expand_dims(best_individual, 0)x population.binary2decimal(best_individual)print(X, x, \t Y: , best_fit)5.3结果展示 在某些情况下遗传算法可能陷入局部最优。
早熟收敛Premature Convergence 原因种群中的个体过早地变得相似导致遗传多样性下降使得算法无法探索解空间的其他区域。 表现种群的适应度值在算法早期迅速上升但随后停滞不前。选择压力过大 原因选择操作过于偏向适应度高的个体可能导致适应度较低的个体被过早淘汰减少了种群的多样性。 表现算法快速收敛到某个局部最优解而忽略了可能存在更好解的区域。交叉和突变概率设置不当 原因交叉率和突变率太低无法有效地探索新的解空间交叉率和突变率太高可能导致算法变成随机搜索。 表现交叉和突变不足时算法容易在局部最优解附近徘徊过度交叉和突变则可能导致算法无法收敛。适应度函数设计不当 原因适应度函数未能准确反映解的质量或者存在多个局部最优解而适应度函数无法有效区分。 表现算法可能收敛到非目标解的局部最优解。解的表示方法 原因解的编码方式可能不适合特定问题导致算法难以找到全局最优解。 表现即使算法能够探索解空间但由于编码的限制仍可能无法表示全局最优解。种群大小 原因种群大小太小无法维持足够的遗传多样性种群大小太大计算成本过高。 表现种群太小容易陷入局部最优种群太大则可能导致算法效率低下。算法停止条件 原因算法停止条件设置过早可能导致算法未能充分探索解空间。 表现算法在达到停止条件时可能刚好处于局部最优解。 遗传算法的MATLAB代码 %ga_1
clc
clear
close all%% 画出函数图
figure(1);
hold on;lb 1; ub 2; %函数自变量范围【1.2】
ezplot(sin(10*pi*X)/X,[lb,ub]); %画出函数曲线
xlabel(自变量/x)
ylabel(自变量/y)%% 定义遗传算法参数
NIND 40; %种群大小
MAXGEN 20; %最大遗传代数
PRECI 20; %个体长度
GGAP 0.95; %代沟
px 0.7; %交叉概率
pm 0.01; %变异概率
trace zeros(2,MAXGEN); %寻优结果的初始值
FieldD [PRECI;lb;ub;1;0;1;1]; %区域描述器
Chrom crtbp(NIND,PRECI); %创建任意离散随机种群%% 优化
gen 0; %代计数器
X bs2rv(Chrom,FieldD); %初始种群二进制到十进制转换
ObjV sin(10*pi*X)./X; %计算目标函数值
while genMAXGENFitnV ranking(ObjV); %分配适应度值SelCh select(sus,Chrom,FitnV,GGAP); %选择SelCh recombin(xovsp,SelCh,px); %重组SelCh mut(SelCh,pm); %变异X bs2rv(SelCh,FieldD); %自带个体的十进制转换ObjVSel sin(10*pi*X)./X; %计算自带的目标函数值[Chrom,ObjV] reins(Chrom,SelCh,1,1,ObjV,ObjVSel); %重插入子代到父代得到新种群X bs2rv(Chrom,FieldD);gen gen1; % 代计数器增加%获取每代的最优解及其序号Y为最优解I为个体的序号[Y,I] min(ObjV);trace(1,gen) X(I); %记下每代的最优值trace(2,gen) Y; %记下每代的最优值
endplot(trace(1,:),trace(2,:),bo); %画出每代的最优点
grid on;
plot(X,ObjV,b*); %画出最后一代的种群hold off
hold off
%% 画进化图
figure(2);
plot(1:MAXGEN,trace(2,:));
grid on
xlabel(遗传代数)
ylabel(解的变化)
title(进化过程)
bestY trace(2,end);
bestX trace(1,end);
fprintf([最优解\nX ,num2str(bestX),\nY ,num2str(bestY),\n])
% ga_2
clc
clear all
close all%% 画出函数图
figure(1);
lbx -2;ubx 2;
lby -2;uby 2;
ezmesh(y*sin(2*pi*x)x*cos(2*pi*y),[lbx,ubx,lby,uby],50); %画出函数曲线
hold on;%% 定义遗传算法参数
NIND 40; %种群大小
MAXGEN 50; %最大遗传代数
PRECI 20; %个体长度
GGAP 0.95; %代沟
px 0.7; %交叉变异
pm 0.01; %变异概率
trace zeros(3,MAXGEN); %寻优结果的初始值
FieldD [PRECI PRECI;lbx lby;ubx uby;1 1;0 0;1 1;1 1]; %区域扫描器
Chrom crtbp(NIND,PRECI*2); %创建任意离散随即种群%% 优化
gen 0; %代计数器
XY bs2rv(Chrom,FieldD); %初代种群的十进制转换
X XY(:,1); Y XY(:,2);
ObjV Y.*sin(2*pi*X)X.*cos(2*pi*Y); %计算目标函数值
while genMAXGENFitnV ranking(-ObjV); %分配适应度值SelCh select(sus,Chrom,FitnV,GGAP); %选择SelCh recombin(xovsp,SelCh,px); %重组SelCh mut(SelCh,pm); %变异XY bs2rv(SelCh,FieldD); %子代个体的十进制转换X XY(:,1); Y XY(:,2);ObjVSel Y.*sin(2*pi*X)X.*cos(2*pi*Y); %计算子代的目标函数[Chrom,ObjV] reins(Chrom,SelCh,1,1,ObjV,ObjVSel); %重插入子代到父代得到新种群XY bs2rv(Chrom,FieldD);gen gen 1 ; %代计数器增加%获取每代的最优解及其序号Y为最优解I为个体的序号[Y,I] max(ObjV);trace(1:2,gen) XY(I,:); %记下每代的最优值trace(3,gen) Y; %记下每代的最优解
end
plot3(trace(1,:),trace(2,:),trace(3,:),bo); %画出每代的最优点
grid on;
plot3(XY(:,1),XY(:,2),ObjV,bo); %画出最后一代的种群
hold off%% 画进化图
figure(2);
plot(1:MAXGEN,trace(3,:));
grid on
xlabel(遗传代数)
ylabel(解的变化)
title(进化进程)
bestZ trace(3,end);
bestX trace(1,end);
bestY trace(2,end);
fprintf([最优解:\nX ,num2str(bestX),\nY ,num2str(bestY),\nz ,num2str(bestZ),\n])
% ga_tsp
clear;clc;
% 输入数据
vertexsimportdata(city.txt); %城市坐标
nlength(vertexs); %城市数目
distzeros(n); %城市距离矩阵
for i 1:nfor j 1:ndist(i,j)distance(vertexs(i,:),vertexs(j,:));end
end
% 遗传算法参数设置
NIND50; %种群大小
MAXGEN150; %迭代次数
Pm0.9; %交叉概率
Pc0.1; %变异概率
pSwap0.2; %选择交换结构的概率
pReversion0.5; %选择逆转结构的概率
pInsertion0.3; %选择插入结构的概率
Nn; %染色体长度城市数目
% 种群初始化
ChromInitPop(NIND,N);
% 优化
gen1; %计数器
bestChromChrom(1,:); %初始全局最优个体
bestLRouteLength(bestChrom,dist);%初始全局最优个体的总距离
BestChromzeros(MAXGEN,N); %记录每次迭代过程中全局最优个体
BestLzeros(MAXGEN,1); %记录每次迭代过程中全局最优个体的总距离
while genMAXGENSelChBinaryTourment_Select(Chrom,dist); %二元锦标赛选择 SelChRecombin(SelCh,Pm); %OX交叉SelChMutate(SelCh,Pc,pSwap,pReversion,pInsertion); %变异ChromSelCh; %将Chrom更新为SelChObjObjFunction(Chrom,dist); %计算当前代所有个体总距离[minObj,minIndex]min(Obj); %找出当前代中最优个体if minObjbestL %将当前代中最优个体与全局最优个体进行比较如果当前代最优个体更好则将全局最优个体进行替换bestChromChrom(minIndex,:); bestLminObj;endBestChrom(gen,:)bestChrom; %记录每一代全局最优个体及其总距离BestL(gen,:)bestL;disp([第 num2str(gen) 次迭代全局最优路线总距离 num2str(bestL)]); %显示外层循环每次迭代的信全局最优路线的总距离figure(1); %画出每次迭代的全局最优路线图PlotRoute(bestChrom,vertexs(:,1),vertexs(:,2))pause(0.01);gengen1; %计数器加1
end
figure; % 打印每次迭代的全局最优个体的总距离变化趋势图
plot(BestL,LineWidth,1);
title(优化过程)
xlabel(迭代次数);
ylabel(总距离);function dist distance(a,b)
%a 第一个城市坐标
%b 第二个城市坐标
%dist 两个城市之间距离x (a(1)-b(1))^2;y (a(2)-b(2))^2;dist (xy)^(1/2);
endfunction DistObjFunction(Chrom,dist)
%Chrom 种群
%dist 距离矩阵
%Dist 每个个体的目标函数值即每个个体的总距离NINDsize(Chrom,1); %种群大小Distzeros(NIND,1); %目标函数初始化为0for i1:NINDrouteChrom(i,:); %当前个体Dist(i,1)RouteLength(route,dist); %计算当前个体的总距离end
endfunction LRouteLength(route,dist)
%route 路线
%dist 距离矩阵
%L 该路线总距离nlength(route);route[route route(1)];L0;for k1:n iroute(k);jroute(k1); LLdist(i,j); end
endfunction ChromInitPop(NIND,N)
%种群初始化
%NIND 种群大小
%N 染色体长度
%Chrom 随机生成的初始种群Chromzeros(NIND,N); %种群初始化为NIND行N列的零矩阵for i1:NINDChrom(i,:)randperm(N); %每个个体为1~N的随机排列end
endfunction FitnVFitness(Obj)
%适应度函数总距离的倒数
%输入Obj 每个个体的总距离
%输出FitnV 每个个体的适应度值即总距离的倒数FitnV1./Obj;
endfunction SelchBinaryTourment_Select(Chrom,dist)
%Chrom 种群
%dist 距离矩阵
%Selch 二元锦标赛选择出的个体ObjObjFunction(Chrom,dist); %计算种群目标函数值即每个个体的总距离FitnVFitness(Obj); %计算每个个体的适应度值即总距离的倒数[NIND,N]size(Chrom); %NIND-种群个数、N-种群长度Selchzeros(NIND,N); %初始化二元锦标赛选择出的个体for i1:NINDRrandperm(NIND); %生成一个1~NIND的随机排列index1R(1); %第一个比较的个体序号index2R(2); %第二个比较的个体序号fit1FitnV(index1,:); %第一个比较的个体的适应度值适应度值越大说明个体质量越高fit2FitnV(index2,:); %第二个比较的个体的适应度值%如果个体1的适应度值 大于等于 个体2的适应度值则将个体1作为第i选择出的个体if fit1fit2Selch(i,:)Chrom(index1,:);else%如果个体1的适应度值 小于 个体2的适应度值则将个体2作为第i选择出的个体Selch(i,:)Chrom(index2,:);endend
endfunction SelChRecombin(SelCh,Pc)
% 交叉操作
%SelCh 被选择的个体
%Pc 交叉概率
% SelCh 交叉后的个体NSelsize(SelCh,1);for i1:2:NSel-mod(NSel,2)if Pcrand %交叉概率Pc[SelCh(i,:),SelCh(i1,:)]OX(SelCh(i,:),SelCh(i1,:));endend
end
function [a,b]OX(a,b)
%输入a和b为两个待交叉的个体
%输出a和b为交叉后得到的两个个体Llength(a);while 1r1randsrc(1,1,[1:L]);r2randsrc(1,1,[1:L]);if r1~r2smin([r1,r2]);emax([r1,r2]);a0[b(s:e),a];b0[a(s:e),b];for i1:length(a0)aindexfind(a0a0(i));bindexfind(b0b0(i));if length(aindex)1a0(aindex(2))[];endif length(bindex)1b0(bindex(2))[];endif ilength(a)breakendendaa0;bb0;breakendend
endfunction SelChMutate(SelCh,Pm,pSwap,pReversion,pInsertion)
% 变异操作
%SelCh 被选择的个体
%Pm 变异概率
%pSwap 选择交换结构的概率
%pReversion 选择逆转结构的概率
%pInsertion 选择插入结构的概率
%SelCh 变异后的个体NSelsize(SelCh,1);for i1:NSelif PmrandindexRoulette(pSwap,pReversion,pInsertion);route1SelCh(i,:);if index1 %交换结构route2Swap(route1);elseif index2 %逆转结构route2Reversion(route1);else %插入结构route2Insertion(route1);endSelCh(i,:)route2;endend
endfunction indexRoulette(pSwap,pReversion,pInsertion)
%pSwap 选择交换结构的概率
%pReversion 选择逆转结构的概率
%pInsertion 选择插入结构的概率
%index 最终选择的邻域结构p[pSwap pReversion pInsertion];rrand;ccumsum(p);indexfind(rc,1,first);
endfunction route2Swap(route1)
%交换操作
%route1 原路线1
%route2 经过交换结构变换后的路线2nlength(route1);seqrandperm(n);Iseq(1:2);i1I(1);i2I(2);route2route1;route2([i1 i2])route1([i2 i1]);
endfunction route2Reversion(route1)
%逆转变换
%route1 路线1
%route2 经过逆转结构变换后的路线2nlength(route1);seqrandperm(n);Iseq(1:2);i1min(I);i2max(I);route2route1;route2(i1:i2)route1(i2:-1:i1);
endfunction route2Insertion(route1)
%插入变换
%route1 路线1
%route2 经过插入结构变换后的路线2nlength(route1);seqrandperm(n);Iseq(1:2);i1I(1);i2I(2);if i1i2route2route1([1:i1-1 i11:i2 i1 i21:end]);elseroute2route1([1:i2 i1 i21:i1-1 i11:end]);end
endfunction PlotRoute(route,x,y)
%route 路线
%x,y x,y坐标route[route route(1)];plot(x(route),y(route),k-o,MarkerSize,10,MarkerFaceColor,w,LineWidth,1.5);xlabel(x);ylabel(y);
end
