遗传算法及基于该算法的典型问题的求解实践博文对应的代码(Matlab)

%% 遗传算法解决旅行商问题 %% %关于本代码相关的问题背景说明、建模过程、以及核心代码块的解读，可参考csdn连接% %author: https://blog.csdn.net/xhblair?spm=1000.2115.3001.5343 % clear all; close all; clc; %------参数预设------% cityNum = 10; %城市数，每个城市可以编号为1：N citySize = 100; %限定这些城市在x/y轴上的最远距离(范围) axisTmp = randperm(citySize); %先这样随机设置吧 cityX = axisTmp(1:cityNum); cityY = axisTmp(citySize-9:end); %构建一个两两城市之间间距的矩阵 DistanceMatrix = zeros(cityNum,cityNum); for ii = 1:cityNum for jj = 1:cityNum DistanceMatrix(ii,jj) = sqrt( (cityX(ii) - cityX(jj))^2 + (cityY(ii) - cityY(jj))^2 ); end end %预设染色体： Chromosome_num = 10; Chromosome = zeros(Chromosome_num,cityNum); for ii = 1:Chromosome_num Chromosome(ii,:) = randperm(cityNum); %随机生成chromosome_num条不重复的路径 end %计算预设染色体的适应度： 这里适应度函数用距离和来评价。 [adaptability] = CalAdaptability(Chromosome,DistanceMatrix,cityNum); %计算每条染色体被选取的概率： [SelectionProbability] = CalSelectionProbability(adaptability,Chromosome_num); figure(1); %看看初始随机分配的染色体中距离最短的情况,需要把尾巴和头连接上！ [~,minDistanceID1] = max(SelectionProbability); minDistance1 = 1/(adaptability(minDistanceID1)); Xaxis_1 = cityX(Chromosome(minDistanceID1,:)); Xaxis_1 = [Xaxis_1 Xaxis_1(1)]; Yaxis_1 = cityY(Chromosome(minDistanceID1,:)); Yaxis_1 = [Yaxis_1 Yaxis_1(1)]; plot(Xaxis_1,Yaxis_1,'-o'); hold on; scatter(Xaxis_1(1),Yaxis_1(1),'r*'); scatter(Xaxis_1(end-1),Yaxis_1(end-1),'b*'); hold off; xlabel('横坐标');ylabel('纵坐标');title(['随机初始化染色体中距离最短的路线图','最短距离： ',num2str(minDistance1),'m']); legend('路线图','起始点','最后一个城市'); xlim([0 citySize+10]);ylim([0 citySize+10]); grid on; %------迭代/进化部分------% staynum = floor(Chromosome_num/5); %每次进化从上一级复制的染色体个数 iterations = 100; %迭代次数 muteRate = 0.02; %预设变异率 muteNum = ceil(Chromosome_num*muteRate); %得到单次进化的变异数量 figure(2); %观察每次迭代下各条染色体对应的适应度(所耗时长) adaptabilityOld = adaptability; %这里也要预先赋值一次 ChromosomeOld = Chromosome; SelectionProbabilityOld = SelectionProbability; for KK = 1:iterations ChromosomeNew = zeros(Chromosome_num,cityNum); %交叉+变异部分 这里的交叉选择顺序交叉：子代中不能产生重复基因！(城市) for jj = 1:Chromosome_num - staynum %选择父&母染色体 - 基于轮盘赌的方法选择 dadID = ChoseParaments(SelectionProbabilityOld); dadchromosome = ChromosomeOld(dadID,:); while 1 momID = ChoseParaments(SelectionProbabilityOld); if momID ~= dadID break; end end momchromosome = ChromosomeOld(momID,:); %交叉 - 顺序交叉 %随机选择其中一个结点(这里的结点对应的是任务点)，然后进行交叉生成一条新的染色体。但是这里的交叉需要保证新生成的染色体的基因不能前后重复. crosspoint = randi(cityNum); ChromosomeNew(jj,1:crosspoint) = dadchromosome(1:crosspoint); addnum = 1; for ii = 1:cityNum if isempty( find(ChromosomeNew(jj,:) == momchromosome(ii)) ) ChromosomeNew(jj,crosspoint+addnum) = momchromosome(ii); addnum = addnum + 1; if addnum > (cityNum - crosspoint) %如果已经填充满了 就及时break出去。 break; end end end end %变异 %这里变异的方法是随机选择两个基因进行交换。(同样，你需要保证不会有重复的)。 mutedID = zeros(1,muteNum); for pp = 1:muteNum cityIndex1 = randi(cityNum); while 1 cityIndex2 = randi(cityNum); %需要确保两个基因不是一个位置！ if cityIndex2 ~= cityIndex1 break; end end while 1 ChromosomeID = randi(Chromosome_num-staynum); if isempty(find(mutedID == ChromosomeID)) %需要保证你变异时是选择不同的染色体。 break; end end cityID1 = ChromosomeNew(ChromosomeID,cityIndex1); cityID2 = ChromosomeNew(ChromosomeID,cityIndex2); ChromosomeNew(ChromosomeID,cityIndex1) = cityID2; ChromosomeNew(ChromosomeID,cityIndex2) = cityID1; mutedID(pp) = ChromosomeID; end %完成复制(也可以放在后面)：选择几个适应度最高的直接复制到下一代，这几条不参与变异！ dataTmp = adaptabilityOld; minVal = min(dataTmp); for ii = 1:staynum [~,ID] = max(dataTmp); ChromosomeNew(ii+(Chromosome_num-staynum),:) = ChromosomeOld(ID,:); dataTmp(ID) = minVal; %为了防止最大适应度的染色体被重复找到 end %以上完成了一次染色体的更新，这里需要再重新计算新染色体的适应度以及概率% [adaptabilityNew] = CalAdaptability(ChromosomeNew,DistanceMatrix,cityNum); %计算每条染色体对应的选取概率 [SelectionProbabilityNew] = CalSelectionProbability(adaptabilityNew,Chromosome_num); %重新赋值： ChromosomeOld = ChromosomeNew; adaptabilityOld = adaptabilityNew; SelectionProbabilityOld = SelectionProbabilityNew; scatter(KK,1./adaptabilityOld,10,'or','filled');hold on; flag = 0+KK end title('不同迭代次数下各条染色体的总距离');xlabel('迭代次数');ylabel('完成任务的总距离');xlim([0 iterations+20]);ylim auto; grid on; hold off; %计算、画出得到最短距离及其路线图： [DistanceUse,ID] = min(1./adaptabilityOld); ChromosomeUse = ChromosomeOld(ID,:); figure(3); %看看完成迭代后距离最短的情况,需要把尾巴和头连接上！ [~,minDistanceID2] = max(SelectionProbabilityOld); minDistance2 = 1/(adaptabilityOld(minDistanceID2)); Xaxis_2 = cityX(ChromosomeOld(minDistanceID2,:)); Xaxis_2 = [Xaxis_2 Xaxis_2(1)]; Yaxis_2 = cityY(ChromosomeOld(minDistanceID2,:)); Yaxis_2 = [Yaxis_2 Yaxis_2(1)]; plot(Xaxis_2,Yaxis_2,'-o'); hold on; %为了和起始情况保持一致，这里选择起始中起点进行特别标识 scatter(Xaxis_1(1),Yaxis_1(1),'r*'); scatter(Xaxis_2(end-1),Yaxis_2(end-1),'b*'); hold off; xlabel('横坐标');ylabel('纵坐标');title(['随机初始化染色体中距离最短的路线图','最短距离： ',num2str(minDistance2),'m']); legend('路线图','起始点','最后一个城市'); xlim([0 citySize+10]);ylim([0 citySize+10]); grid on; breakpoint1 = 1; %% 计算每条染色体的适应度 %% function [adaptability] = CalAdaptability(Chromosome,DistanceMatrix,cityNum) Chromosome_num = size(Chromosome,1); adaptability = zeros(1,Chromosome_num); %每条染色体的适应度 for ii = 1:Chromosome_num %对于每条染色体 DistanceSum = 0; for jj = 1:cityNum-1 DistanceSum = DistanceMatrix(Chromosome(ii,jj),Chromosome(ii,jj+1)) + DistanceSum; %基于DistanceMatrix来获得前后两个城市之间的间隔。 end adaptability(ii) = DistanceSum + DistanceMatrix( Chromosome(ii,cityNum), Ch