用matlab解决车辆路径规划问题，主要是遗传算法

遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它最初由美国Michigan大学J.Holland教授于1975年首先提出来的，并出版了颇有影响的专著《Adaptation in Natural and Artificial Systems》，GA这个名称才逐渐为人所知，J.Holland教授所提出的GA通常为简单遗传算法（SGA）。遗传算法（Genetic Algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。它是由美国的J.Holland教授1975年首先提出，其主要特点是直接对结构对象进行 *** 作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术。 对于一个求函数最大值的优化问题(求函数最小值也类同)，一般可以描述为下列数学规划模型:遗传算法族磨 式中为决策变量，为目标函数式，式2-2、2-3为约束条件，U是基本空间，R是U的子集。满足约束条件的解X称为可行解，集合R表示所有满足约束条件的解所组成的集合，称为可行解集合。 遗传算法的基本运算过程如下: a)初始化:设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个兆晌斗体作为初始群体P(0)。 b)个体评价:计算群体P(t)中各个个体的适应度。 c)选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择 *** 作是建立在群体中个体的适应度评估基础上的。 d)交叉运算；将交叉算子作用于群体。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的 *** 作。遗传算法中起核心作用的就是交叉算子。 e)变异运算:将变异算谨慎子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。 群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t 1)。 f)终止条件判断:若tT,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。

function [path,lmin]=ga(data,d)  %data为点集,d为距离矩阵，即赋铅慧权图

tic

%======================

sj0=data%开环最短路线

%=================================

% sj0=[datadata(1,:)] %闭环最短路线

%=========================

x=sj0(:,1)y=sj0(:,2)

N=length(x)

%=========================

% 槐族答d(N,:)=d(1,:)%闭环最短路线

% d(:,N)=d(:,1)%距离矩阵d    

%======================

L=N   %sj0的长度

w=800dai=1000

%通过改良圈算法选取优良穗唤父代A

for k=1:w

c=randperm(L-2)

c1=[1,c+1,L]

flag=1

while flag>0

flag=0

for m=1:L-3

for n=m+2:L-1

if d(c1(m),c1(n))+d(c1(m+1),c1(n+1))<d(c1(m),c1(m+1))+d(c1(n),c1(n+1))

flag=1

c1(m+1:n)=c1(n:-1:m+1)

end

end

end

end

J(k,c1)=1:L

end

J=J/L

J(:,1)=0J(:,L)=1

rand('state',sum(clock))

%遗传算法实现过程

A=J

for k=1:dai %产生0～1 间随机数列进行编码

B=A

c=randperm(w)

%交配产生子代B

for i=1:2:w

F=2+floor(100*rand(1))

temp=B(c(i),F:L)

B(c(i),F:L)=B(c(i+1),F:L)

B(c(i+1),F:L)=temp

end 

%变异产生子代C

by=find(rand(1,w)<0.1)

if length(by)==0

by=floor(w*rand(1))+1

end

C=A(by,:)

L3=length(by)

for j=1:L3

bw=floor(1+fix(rand(1,3)*N))      %产生1-N的3个随机数

bw=sort(bw)

C(j,:)=C(j,[1:bw(1)-1,bw(2)+1:bw(3),bw(1):bw(2),bw(3)+1:L])

end

G=[ABC]

TL=size(G,1)

%在父代和子代中选择优良品种作为新的父代

[dd,IX]=sort(G,2)

temp=[]

temp(1:TL)=0

for j=1:TL

for i=1:L-1

temp(j)=temp(j)+d(IX(j,i),IX(j,i+1))

end

end

[DZ,IZ]=sort(temp)

A=G(IZ(1:w),:)

end

path=IX(IZ(1),:)

% for i=1:length(path)

% path(i)=path(i)-1

% end

% path=path(2:end-1)

lmin=0l=0

for j=1:(length(path)-1)

    t1=path(j)t2=path(j+1)

    l=d(t1,t2)

    lmin=lmin+l

end

xx=sj0(path,1)yy=sj0(path,2)

plot(xx,yy,'r-o')

axis equal

toc

代码亲自前几天还用来着，绝对可用

% Optimizing a function using Simple Genetic Algorithm with elitist preserved

%Max f(x1,x2)=10-x1*x1-x2*x2+x1*x2-2.0480<=x1,x2<=2.0480

clcclear all

format long%Set the data format(设定数据显示格式)

%parameters Initialization (初始化参数)

T=100% Generation( 仿真代数)

N=80% Population size ( 群体规模)

pm=0.05pc=0.8%Crossover and mutation probability(交叉变异概率)

umax=2.048umin=-2.048%Parameter range(参数取值范围)

L=10%Single parameter string length, the total coding length is 2L(单个参数字串长度，总编码长度2L)

bval=round(rand(N,2*L))%Population Initialization(初始种群槐首禅)

bestv=-inf%Optimal fitness Initialization(最优适应度初值)

%Iteration stsar(迭代开始)

for ii=1:T

%Decoding, and the fitness calculation(解码，计算适应度)

for i=1:N

y1=0y2=0

for j=1:1:L

y1=y1+bval(i,L-j+1)*2^(j-1)

end

x1=(umax-umin)*y1/(2^L-1)+umin

for j=1:1:L

y2=y2+bval(i,2*L-j+1)*2^(j-1)

end

x2=(umax-umin)*y2/(2^L-1)+umin

obj(i)=10-x1*x1-x2*x2+x1*x2%The objective function(目标函数)

xx(i,:)=[x1,x2]

end

func=obj%Objective function into the fitness function(目标函数转换为适应度函数铅尘)

p=func./sum(func)

q=cumsum(p)%Cumulative(累加)

[fmax,indmax]=max(func)%seeking the best in this generation(求当代最佳个体)

if fmax>=bestv

bestv=fmax%So far, the best fitness value(到目前为止最优适应度值)

bvalxx=bval(indmax,:)%So far the best bit string(到目前为止最佳位串)

optxx=xx(indmax,:)%So far the optimal parameters(到目前为止最优参数)

end

Bfit1(ii)=bestv% So far the optimal parameters(存储每代的最优适应度)

%%%%Genetic operation starts(遗传 *** 作开始)

%Roulette wheel selection(轮盘赌选择)

for i=1:(N-1)

r=rand

tmp=find(r<=q)

newbval(i,:)=bval(tmp(1),:)

end

newbval(N,:)=bvalxx%Optimal retention(最优保留)

bval=newbval

%Single-point crossover(单点交叉)

for i=1:2:(N-1)

cc=rand

if cc<pc

point=ceil(rand*(2*L-1))%To obtain one integer from 1 to 2L-1(取得一个1到2L-1的整数)

ch=bval(i,:)

bval(i,point+1:2*L)=bval(i+1,point+1:2*L)

bval(i+1,point+1:2*L)=ch(1,point+1:2*L)

end

end

bval(N,:)=bvalxx%Optimal retention(最芹陆优保留)

%Locus mutation(位点变异)

mm=rand(N,2*L)<pm%N lines(N行)

mm(N,:)=zeros(1,2*L)%Variation of the last line not change set to 0(最后一行不变异，强制赋0)

bval(mm)=1-bval(mm)

end

%Output(输出)

plot(Bfit1)% Draw the best fitness evolution curves(绘制最优适应度进化曲线)

bestv %Output the optimal fitness value(输出最优适应度值)

这个遗传的我没试过

下面这个是蚁群的结果

function [R_best,L_best,L_ave,Shortest_Route,Shortest_Length]=ACATSP(C,NC_max,m,Alpha,Beta,Rho,Q)

%%=========================================================================

%% ACATSP.m

%%-------------------------------------------------------------------------

%% 主要符号说明

%% C n个城市的坐标，n×2的矩阵

%% NC_max 最大迭代次数

%% m 蚂蚁个数

%% Alpha 表征信息素重要程度的参数

%% Beta 表征启发式因子重要程度的参数

%% Rho 信息素蒸发系数

%% Q 信息素增加强度系数

%% R_best 各代最佳路线

%% L_best 各代最佳路线的长度

%%=========================================================================

%%第一步：变量初始化

C=[1304,23123639,13154177,22443712,13993488,15353326,1556]

NC_max=200

m=31

Alpha=1

Beta=5

Rho=0.1

Q=100

n=size(C,1)%n表示问题的规模（城市个数）

D=zeros(n,n)%D表示完全图的赋权邻接矩阵

for i=1:n

for j=1:n

if i~=j

D(i,j)=((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2)^0.5

else

D(i,j)=eps

end

D(j,i)=D(i,j)

end

end

Eta=1./D%Eta为启发因子，这里设为距离的倒数

Tau=ones(n,n)%Tau为信息素矩阵

Tabu=zeros(m,n)%存储并记录路径的生成

NC=1%迭代计数器

R_best=zeros(NC_max,n)%各代最佳路线

L_best=inf.*ones(NC_max,1)%各代最佳路线的长度

L_ave=zeros(NC_max,1)%各代路线的平均长度

while NC<=NC_max%停止条件之一：达到最大迭代次数

%%第二步：将m只蚂蚁放到n个城市上

Randpos=[]

for i=1:(ceil(m/n))

Randpos=[Randpos,randperm(n)]

end

Tabu(:,1)=(Randpos(1,1:m))'

%%第三步：m只蚂蚁按概率函数选择下一座城市，完成各自的周游

for j=2:n

for i=1:m

visited=Tabu(i,1:(j-1))%已访问的城市

J=zeros(1,(n-j+1))%待访问的城市

P=J%待访问城市的选择概率分布

Jc=1

for k=1:n

if length(find(visited==k))==0

J(Jc)=k

Jc=Jc+1

end

end

%下面计算待选城市的概率分布

for k=1:length(J)

P(k)=(Tau(visited(end),J(k))^Alpha)*(Eta(visited(end),J(k))^Beta)

end

P=P/(sum(P))

%按概率原则选取下一个城市

Pcum=cumsum(P)

Select=find(Pcum>=rand)

to_visit=J(Select(1))

Tabu(i,j)=to_visit

end

end

if NC>=2

Tabu(1,:)=R_best(NC-1,:)

end

%%第四步：记录本次迭代最佳路线

L=zeros(m,1)

for i=1:m

R=Tabu(i,:)

for j=1:(n-1)

L(i)=L(i)+D(R(j),R(j+1))

end

L(i)=L(i)+D(R(1),R(n))

end

L_best(NC)=min(L)

pos=find(L==L_best(NC))

R_best(NC,:)=Tabu(pos(1),:)

L_ave(NC)=mean(L)

NC=NC+1

%%第五步：更新信息素

Delta_Tau=zeros(n,n)

for i=1:m

for j=1:(n-1)

Delta_Tau(Tabu(i,j),Tabu(i,j+1))=Delta_Tau(Tabu(i,j),Tabu(i,j+1))+Q/L(i)

end

Delta_Tau(Tabu(i,n),Tabu(i,1))=Delta_Tau(Tabu(i,n),Tabu(i,1))+Q/L(i)

end

Tau=(1-Rho).*Tau+Delta_Tau

%%第六步：禁忌表清零

Tabu=zeros(m,n)

end

%%第七步：输出结果

Pos=find(L_best==min(L_best))

Shortest_Route=R_best(Pos(1),:)

Shortest_Length=L_best(Pos(1))

subplot(1,2,1)

DrawRoute(C,Shortest_Route)

subplot(1,2,2)

plot(L_best)

hold on

plot(L_ave)

function DrawRoute(C,R)

%%=========================================================================

%% DrawRoute.m

%% 画路线图的子函数

%%-------------------------------------------------------------------------

%% C Coordinate 节点坐标，由一个N×2的矩阵存储

%% R Route 路线

%%=========================================================================

N=length(R)

scatter(C(:,1),C(:,2))

hold on

plot([C(R(1),1),C(R(N),1)],[C(R(1),2),C(R(N),2)])

hold on

for ii=2:N

plot([C(R(ii-1),1),C(R(ii),1)],[C(R(ii-1),2),C(R(ii),2)])

hold on

end

---