【Matlab代码】基于遗传算法和蚂蚁优化算法的路径优化问题

目录

1 概述

2 Matlab代码

3 运行结果

---

1 概述

在1959年，Dantzing 和 Ramser在经过实验和思考后，首次提出配送车辆路径优化问题。在物流运输中配送是重要的环节，准确选择配送车辆路径能有效缩短运输时间、降低运输成本、满足顾客需求等目的。关于寻找最优配送线路问题已经成为研究的热点之一2。最初蚁群算法是研究旅行商的问题⒆，现在已经广泛应用到许多寻找最优解的问题中。例如:郑娟毅等利用蚁群算法寻找配送车辆路径最优的问题，张银玲等利用蚁群算法寻找移动机器人的最优路径，鲁丰玲、白俊强等通过蚁群算法寻找无人机最优路径P~，蚁群算法被应用到解决旅游最优路线的问题中9-10]Wang Yong等""利用蚁群算法解决VNF布局网络问题，张肖琳等在绿色环保角度，对油耗、污染物排放等因素进行约束构建路径优化模型，利用蚁群算法找出最优路径。可以看出蚁群算法虽然可以解决许多实际问题，但还存在不足，于是提出最大最小蚂蚁系统吧以及混合蚂蚁系统等方法，都在一定程度上提高了运算效率。虽然大多数文献已经对路径优化进行了充分研究.
本文基于遗传算法和蚂蚁优化算法的路径优化问题

2 Matlab代码

function [ genxx,genyy ] = addallgen( genx,geny,xs,ys,xt,yt)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% addallgen()：将起始点和目标点存入种群
% genx geny为种群 xs ys,xt,yt分别为起始点和目标点
% genxx genyy 返回包含起始点和目标点的坐标
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
[sizex,sizey] = size(genx);     %获取种群维度
genxx = zeros(sizex,sizey+2);   %初始化种群x方向
genxx(:,1) = ones(sizex,1)*xs;  %分别将目标点 起始点加入
genxx(:,end) = ones(sizex,1)*xt;%个体加入
genxx(:,2:end-1)=genx;
genyy = zeros(sizex,sizey+2);   %y方向上同操作
genyy(:,1) = ones(sizex,1)*ys;
genyy(:,end) = ones(sizex,1)*yt;
genyy(:,2:end-1)=geny;
end

function [ newgenx,newgeny ] = jiaocha( genx,geny,pa,fitvalue,xobs,yobs,robs,xs,ys,xt,yt)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% jiaocha（）：交叉操作
% genx geny为种群
% pa 交叉概率
% newgenx newgeny返回新种群
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% 关注公众号：荔枝科研社
%% 回复关键字：基于遗传算法和蚂蚁优化算法的路径规划问题
%% 下载全部代码
    [maxfitvalue,maxvalueindex] = max(fitvalue);
    [gensizex,gensizey] = size(genx);         %获取种群的维度 genx 种群个数
    newgenx = zeros(gensizex,gensizey);       %初始化新种群
    newgeny = zeros(gensizex,gensizey);       %初始化新种群
    newgenx(1,:) = genx(maxvalueindex,:);     %保留最优个体
    newgeny(1,:) = geny(maxvalueindex,:);
    genx(maxvalueindex,:) = genx(1,:);        %替换最优个体
    geny(maxvalueindex,:) = geny(1,:);
    genx(1,:) = newgenx(1,:);
    geny(1,:) = newgenx(1,:);
    for i = 2:2:gensizex-1
        pat = rand(1);             %产生随机数
        if pat<=pa                 %产生交叉
            a = rand(1);           %交叉比率
            xx1 = a*genx(i,:)+(1-a)*genx(i+1,:);
            xx2 = a*genx(i+1,:)+(1-a)*genx(i,:);
            yy1 = a*geny(i,:)+(1-a)*geny(i+1,:);
            yy2 = a*geny(i+1,:)+(1-a)*geny(i,:);
            while(1)   %交叉后与障碍物碰撞 则重新交叉
                if (iscollison([xs xx1 xt],[ys yy1 yt],xobs,yobs,robs)~=0)
                    if (iscollison([xs xx2 xt],[ys yy2 yt],xobs,yobs,robs)~=0)
                        break;
                    end
                end
                a = rand(1);           %交叉比率
                xx1 = a*genx(i,:)+(1-a)*genx(i+1,:);
                xx2 = a*genx(i+1,:)+(1-a)*genx(i,:);
                yy1 = a*geny(i,:)+(1-a)*geny(i+1,:);
                yy2 = a*geny(i+1,:)+(1-a)*geny(i,:);
            end
            newgenx(i,:) = xx1;       %保留交叉后的结果
            newgenx(i+1,:) = xx2;
            newgeny(i,:) = yy1;
            newgeny(i+1,:) = yy2;
        else                          %不交叉
            newgenx(i,:) = genx(i,:); %直接保留个体
            newgenx(i+1,:) = genx(i+1,:);
            newgeny(i,:) = geny(i,:);
            newgeny(i+1,:) = geny(i+1,:);
        end
    end
end
3 运行结果

 

 在物流运输中配送是重要的环节，准确选择配送车辆路径能有效缩短运输时间、降低运输成本、满足顾客需求等目的。关于寻找最优配送线路问题已经成为研究的热点之一2。最初蚁群算法是研究旅行商的问题⒆，现在已经广泛应用到许多寻找最优解的问题中。例如:郑娟毅等利用蚁群算法寻找配送车辆路径最优的问题，张银玲等利用蚁群算法寻找移动机器人的最优路径，鲁丰玲、白俊强等通过蚁群算法寻找无人机最优路径P~，蚁群算法被应用到解决旅游最优路线的问题中9-10]Wang Yong等""利用蚁群算法解决VNF布局网络问题，张肖琳等在绿色环保角度，对油耗、污染物排放等因素进行约束构建路径优化模型，利用蚁群算法找出最优路径。可以看出蚁群算法虽然可以解决许多实际问题，但还存在不足，于是提出最大最小蚂蚁系统吧以及混合蚂蚁系统等方法，都在一定程度上提高了运算效率。虽然大多数文献已经对路径优化进行了充分研究.

首次提出配送车辆路径优化问题。在物流运输中配送是重要的环节，准确选择配送车辆路径能有效缩短运输时间、降低运输成本、满足顾客需求等目的。关于寻找最优配送线路问题已经成为研究的热点之一2。最初蚁群算法是研究旅行商的问题⒆，现在已经广泛应用到许多寻找最优解的问题中。例如:郑娟毅等利用蚁群算法寻找配送车辆路径最优的问题，张银玲等利用蚁群算法寻找移动机器人的最优路径，鲁丰玲、白俊强等通过蚁群算法寻找无人机最优路径P~，蚁群算法被应用到解决旅游最优路线的问题中9-10]Wang Yong等""利用蚁群算法解决VNF布局网络问题，张肖琳等在绿色环保角度，对油耗、污染物排放等因素进行约束构建路径优化模型，利用蚁群算法找出最优路径。可以看出蚁群算法虽然可以解决许多实际问题，但还存在不足，于是提出最大最小蚂蚁系统吧以及混合蚂蚁系统等方法，都在一定程度上提高了运算效率。虽然大多数文献已经对路径优化进行了充分研究.
本文基于遗传算法和蚂蚁优化算法的路径优化问题