注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

highspeedlogic

FPGA/MATLAB/Simulink

 
 
 

日志

 
 

基于matlab的遗传优化算法实现最短路径搜索  

2017-10-16 03:32:22|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

clc;
clear;
close all;
tic
%这个代码是m文件,是GUI界面的底层代码,可以通过这个程序产看各个变量的数值变化
iter = 8;%遗传次数
number_point = 45;
% 数据的初始化
% %  产生的数据格式共7列
% %  1:编号;2,3:坐标位置;4:货物需求;5,6:时间限制,7:每个点的时间
% %  产生一个中心的位置,总时间跨度,其索引编号为0
% data(1,:) = [0,round(200*rand(1,1)),round(200*rand(1,1)),0,0,1500,0];
% %  产生N个货物点的相关参数
% for i =2:number_point+1
%     T_start = round(1000*rand(1,1));
%     T_end   = round(500*rand(1,1));
%     data(i,:) = [i,round(200*rand(1,1)),round(200*rand(1,1)),round(100*rand(1,1)),T_start,T_start+T_end,90];
% end
%为了便于观察,保存第一次产生的数据,以后每次load这样保证每次调用的数据是相同的
load data.mat

%几个主要参数的初始化
NUM      = number_point;                 %收货点的数目
K        = 40;                            %汽车的数目
capacity = 200;                          %每辆汽车的容量
NC       = 5;
xy       = data(2:NUM+1,2:3);   % 坐标
ETLT     = data(2:NUM+1,5:6);   % 时间限制
demand   = data(2:NUM+1,4);     % 货量大小
Tcontine = data(2,7);         % 停留时间

figure;
plot(data(1,2),data(1,3),'ms','LineWidth',2,'MarkerEdgeColor','k','MarkerFaceColor','r');hold on;
plot(xy(:,1),xy(:,2),'ms','LineWidth',2,'MarkerEdgeColor','k','MarkerFaceColor','g');hold off
axis([0,150,0,150]);
title('各个货物点的位置');
legend('中心点','各个分发点');

%计算每个收货点与中心的位置
distance_center=zeros(1,NUM);
for i=1:NUM
    distance_center(i)=sqrt((data(i+1,2)-data(1,2))^2+(data(i+1,3)-data(1,3))^2);
end
 
%计算每个收货点与中心的位置
data_time = {};
PT        = zeros(1,NUM);
distance  = ones(NUM)*Inf;
for i=1:NUM-1
     for j=i+1:NUM
         distance_point = sqrt((xy(i,1)-xy(j,1))^2+(xy(i,2)-xy(j,2))^2)+Tcontine;%时间积累过程   
         %在限制的时间内统计
         if( ETLT(i,2) + distance_point > ETLT(j,1) && ETLT(i,1) + distance_point < ETLT(j,2) )
             PT(i)               = PT(i)+1;
             data_time{i}(PT(i)) = j;
             distance(i,j)       = distance_point;      
         end
         if( ETLT(j,2) + distance_point > ETLT(i,1) && ETLT(j,1) + distance_point < ETLT(i,2) )
             PT(j)               = PT(j)+1;
             data_time{j}(PT(j)) = i;
             distance(j,i)       = distance_point;
         end 
     end
end

chrom   = {};
numVehi = zeros(1,NC*2);
fit     = ones(1,NC*2);
for i = 1:NC*2
     while(1)
         [chrom{i},numCus] = func_randomSelect(NUM,K,demand,distance_center,PT,data_time,distance,capacity);
         if(numCus==NUM)
             break;
         end
     end
end

chromChild = {};
ddd        = {};
fitAll     = zeros(iter,2*NC);
lastMin    = inf;
lastIndex  = 0;


for j=1:iter
 index     = randperm(2*NC);
 for i=1:NC
     chromChild{i}=func_crossOver(chrom{index(2*i-1)},chrom{index(2*i)},distance,NUM,K,capacity,demand);
 end
 for i=1:NC
     chrom{i}=chromChild{i};
     while(1)
         [chrom{i+NC},numCus]=func_randomSelect(NUM,K,demand,distance_center,PT,data_time,distance,capacity);
         if(numCus==NUM)
             break;
         end
     end
     fit(i)=func_fitness(chrom{i},distance-Tcontine,distance_center);
     fit(i+NC)=func_fitness(chrom{i+NC},distance-Tcontine,distance_center);
 end
 [minChrom,minIndex]=min(fit);
 if(minChrom==lastMin)
     break;
 end
 lastMin=minChrom;
 lastIndex=minIndex

 lend=length(chrom{lastIndex});
 ddd{j}=[];
 for k=1:lend
     ddd{j}=[ddd{j},0,chrom{lastIndex}{k}];
 end
 fitAll(j,:)=fit;
end


resultChrom=chrom{lastIndex};

for i=1:length(resultChrom)
    for j = 1:length(resultChrom{i})+2
    resultChrom2{i}(1)                          = 0;
    resultChrom2{i}(2:length(resultChrom{i})+1) = resultChrom{i};
    resultChrom2{i}(length(resultChrom{i})+2)   = 0;
    end
end

figure;
plot(data(1,2),data(1,3),'ms','LineWidth',2,'MarkerEdgeColor','k','MarkerFaceColor','r');hold on;
plot(xy(:,1),xy(:,2),'ms','LineWidth',2,'MarkerEdgeColor','k','MarkerFaceColor','g');hold on
axis([0,150,0,150]);
legend('中心点','各个分发点'); 
for i=1:length(resultChrom2)
    for j = 1:length(resultChrom2{i})-1
    line([data(resultChrom2{i}(j)+1,2),data(resultChrom2{i}(j+1)+1,2)],[data(resultChrom2{i}(j)+1,3),data(resultChrom2{i}(j+1)+1,3)]);
    end
end
toc
%注意
%resultChrom2为最佳的路经,从workspace中查看
%toc为算法的运行时间
%resultChrom2为最佳的路经

  评论这张
 
阅读(36372)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017