Java教程

遗传算法解决车辆调度问题

本文主要是介绍遗传算法解决车辆调度问题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

前言:

我们现在假设n个工厂每天早上同时发出需求,即想要哪个工厂的多少货。然后进行统一分配,这样做能好做一些,后期我们再实现有单独的工厂发出订单,然后单独调度解决。目前代码只考虑总体所有工厂的调度。

一、我们有三个输入参数:

1、首先是各个工厂(即节点)间的 距离(此例题中是8个节点)
在这里插入图片描述
2.然后是各个工厂想要的货量(我们之前想的是每个工厂对哪个工厂需求多少,但此题是针对物流中心的需求量,即不针对哪个特定的工厂要货)
在这里插入图片描述
3.第三个参数是物流中心到各个工厂节点的距离

在这里插入图片描述

二、主程序

其中每代他设置了80个样本,即80*8的二维矩阵
一共跑200代
每代这80个样本都要先交叉 变异一下
(感觉这地方有点暴力的意思)

1.首先种群初始化了80×8的矩阵
2.然后while200层循环,每层循环体里先进行交叉变异函数,具体函数在第三大模块
3.经过交叉后还是80*8 但是变异后变成132×8了 即132个样本了
4.然后通过size函数,并且变量设为1,即取得这个二维矩阵的行数 即132
5.然后对着132行进行for循环,每个样本都要进行解码和最短路程的计算,计算结果放到了Total_Dis,即这个矩阵是132×1
6.然后关键的更新种群,他把这个Total_Dis排了个升序(即找最短路程最少的80个),然后依照索引取出对应好的80个样本,然后放到下一代里,继续重复同样的操作
7.最后经过200代,持续淘汰,选出最后一代里80个子代中Total_Dis里最低的那个样本,即最后求出的结果(是一个所有车该先去哪个工厂送货,再去哪个)(然后根据这个结果逐一分配车辆就可以了-这个思路简单)(所以程序关键在于求出一个整体结果)

关于解码函数在下方,也需要转换为java程序

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

主程序

%算法参数
population_num=80;%种群规模
Max_gen=200;%迭代次数
Pc=0.9;%交叉概率
Pm=0.09;%变异概率
%%
%问题参数
%车辆数量Car_num=2
%客户数量Customer_num=8
%车辆容量capacity_max=8
%行驶距离distance_max=50
Car_num=2;
Customer_num=8;
capacity_max=8;
distance_max=50;
load Demand %客户的需求
load Distance %客户间的距离
load X %物流中心到客户间的距离
%%
%种群初始化
population=zeros(population_num,Customer_num);
for i=1:population_num
     population(i,:)=randperm(Customer_num);
end
%%
y=1;%循环计数器
 while y<Max_gen
     %交叉
     [new_pop_intercross]=Mating_pool(population_num,population,Pc);
     %变异
     [new_pop_mutation]=Mutation(new_pop_intercross,Pm);
     %计算目标函数
     mutation_num=size(new_pop_mutation,1);
     Total_Dis=[];
     for k=1:mutation_num
     [Result]=decode(new_pop_mutation(k,:),distance_max,capacity_max);
     [Total_Dis(k,1)]=parameter(Result,Customer_num,Car_num);
     end
     %更新种群
     new_pop_new=zeros(population_num,Customer_num);
     [Total_Dissort, index] = sort(Total_Dis);
     
     for k=1:population_num
         new_pop_new(k,:)=new_pop_mutation(index(k),:);
     end
     population=new_pop_new;
     %迭代次数加一
     y=y+1;
 end
 Dis_min1=min(Total_Dis);
for k=1:mutation_num
    if Total_Dis(k,1)==Dis_min1
       position1= k;
       break
    end
end
X_Best=new_pop_mutation(position1,:)
Y_Obj=Total_Dis(position1,1)
t=toc;

三、交叉变异函数

交叉函数

function [new_pop_intercross]=Mating_pool(population_num,population,Pc)
%%
%输入:population,population_num,Pc
%输出:1.new_popopulation_intercross
%     2.c3,配对池:随机将种群population两两配对
%     3.pool
%%
pl=randperm(population_num);
num=population_num/2;
c3=zeros(2,num);
pool=[];
new_pop_intercross=population;
for kj=1:num
    c3(1,kj)=pl(2*kj-1);
    c3(2,kj)=pl(2*kj);
end%生成“配对池c3”

%%判断“配对池c3”每一对个体的随机数是否小于交叉概率Pc
rd=rand(1,num);
for kj=1:num
    if rd(kj)<Pc
       pool=[pool,c3(:,kj)];
    end
end
%%判断配对池每一对个体的随机数是否小于交叉概率Pc,若小于,保存到“产子池pool”

pool_num=size(pool,2);
for kj=1:pool_num
    c1=population(pool(1,kj),:);
    c2=population(pool(2,kj),:);
    [new_c1,new_c2]=cross(c1,c2);
    new_pop_intercross(pool(1,kj),:)=new_c1;
    new_pop_intercross(pool(2,kj),:)=new_c2;
end
end

    

变异函数

function [Mut_Pop]=Mutation(Cross_Pop,Pm)
Mut_Pop=Cross_Pop;
Cross_Pop_num=size(Cross_Pop,1);
for j=1:Cross_Pop_num
    A=Cross_Pop(j,:);
    A_1=A;
    n=size(A,2);
    r=rand(1,n);
    Pe=find(r<Pm);%可以引入变异概率
    sum_Pe=size(Pe,2);
    for i=1:sum_Pe
        c=A(Pe(i));
        A_1(Pe(i))=A_1(find(r==max(r)));
        A_1(find(r==max(r)))=c;
        Mut_Pop=[Mut_Pop;A_1];
    end
end

四、解码函数

decode.m

function [Result]=decode(T,distance_max,capacity_max)
%distance_max=50;
%capacity_max=8;
load Demand
load Distance
load X
WS=1;WT=1;
a1=0;b1=0;
for i=1:size(T,2)
    if WT==1
       a1=2*X(T(i));
       b1=Demand(T(i));
    elseif WT==2
        a1=X(T(i-1))+X(T(i))+Distance(T(i),T(i-1));
        b1=Demand(T(i-1))+Demand(T(i));
    else
        a1=0;b1=0;
        for j=i-WT+1:i-1
            a1=a1+Distance(T(j+1),T(j));
            b1=b1+Demand(T(j));
        end
        b1=b1+Demand(T(i));
        a1=a1+X(T(i-WT+1))+X(T(i));
    end
    if (a1>distance_max)|(b1>capacity_max)
        a1=2*X(T(i));
        b1=Demand(T(1));
        WS=WS+1;
        Result(i,:)=[T(i),WS,a1,b1];
        WT=2;
    else
        Result(i,:)=[T(i),WS,a1,b1];
        WT=WT+1;
    end
   
end


parameter.m

function [Total_Dis]=parameter(Result,Customer_num,Car_num)
%% 解码
if Result(Customer_num,2)<=Car_num
Current_Workstation=1;
Total_Dis=0;
for i=1:Customer_num
    if Result(i,2)==Current_Workstation;
        continue
    else
        Total_Dis=Total_Dis+Result(i-1,3);
        Current_Workstation=Current_Workstation+1;
    end  
end
Total_Dis=Total_Dis+Result(Customer_num,3);
else
    Total_Dis=10000;%引入罚函数
end
这篇关于遗传算法解决车辆调度问题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!