【路径规划】基于A*、遗传、蚁群优化和元胞自动机四种经典算法实现四种场景下六边形网格路径规划附Python代码
✅作者简介:热爱科研的Matlab仿真开发者,擅长毕业设计辅导、数学建模、数据处理、建模仿真、程序设计、完整代码获取、论文复现及科研仿真。
🍎 往期回顾关注个人主页:Matlab科研工作室
👇 关注我领取海量matlab电子书和数学建模资料
🍊个人信条:格物致知,完整Matlab代码获取及仿真咨询内容私信。
🔥 内容介绍
一、背景
(一)路径规划的广泛应用
路径规划在众多领域都有着不可或缺的地位。在机器人领域,无论是工业机器人在生产线上的操作路径规划,还是服务机器人在室内环境中的自主导航,都需要精确的路径规划以确保高效、安全地完成任务。在物流配送中,规划最优的配送路线可以降低成本、提高效率。此外,在地理信息系统(GIS)、自动驾驶、无人机飞行控制等领域,路径规划也起着关键作用。
(二)六边形网格的优势
相较于传统的正方形网格,六边形网格具有独特的优势。六边形网格的顶点到其相邻顶点的距离相等,这使得在网格内的移动具有更好的各向同性,能更均匀地覆盖空间。在处理一些需要考虑方向一致性或对空间利用率要求较高的场景时,六边形网格能提供更合理的空间划分。例如,在模拟自然环境中的扩散现象、资源分配,或者在机器人路径规划中,六边形网格可以更准确地反映实际场景中的空间关系,减少因网格形状带来的误差。
(三)多种算法结合的必要性
不同的路径规划算法各有优缺点。单一算法可能无法在所有场景下都表现出色。例如,某些算法在寻找全局最优解方面表现优异,但计算复杂度较高;而另一些算法虽然计算效率高,但可能陷入局部最优解。因此,结合多种经典算法,利用它们各自的优势,可以更好地应对不同场景下的六边形网格路径规划问题,提高路径规划的质量和效率。
二、原理
(一)A * 算法原理
- 节点与搜索空间
:A * 算法在六边形网格构成的搜索空间中,将每个网格单元视为一个节点。每个节点包含自身的位置信息、从起始节点到该节点的实际代价 g(n),以及从该节点到目标节点的估计代价 h(n)。
- 评估函数
:核心评估函数为 f(n)=g(n)+h(n)。其中,g(n) 是从起始节点沿着已探索路径到达当前节点 n 的实际代价,通常根据移动的距离或步数来计算。h(n) 是启发函数,用于估计从当前节点 n 到目标节点的代价。在六边形网格中,可以使用曼哈顿距离、欧几里得距离等作为启发函数的基础进行调整,以适应六边形网格的几何特性。例如,根据六边形网格中节点间的实际距离关系来定义更精确的启发函数。
- 搜索过程
:算法从起始节点开始,将其放入一个优先队列(按照 f(n) 值从小到大排序)。每次从优先队列中取出 f(n) 值最小的节点进行扩展,检查其相邻节点。如果相邻节点未被访问过或者通过当前路径到达该相邻节点的 g(n) 值更小,则更新该相邻节点的 g(n)、h(n) 和 f(n) 值,并将其加入优先队列。当目标节点被取出扩展时,通过回溯父节点的方式可以得到从起始节点到目标节点的最优路径。A * 算法保证在启发函数满足一定条件(如一致性)时,找到的路径是全局最优路径。
(二)遗传算法原理
- 编码与种群初始化
:在六边形网格路径规划中,将路径编码为染色体。一种常见的编码方式是将路径经过的网格节点顺序排列作为染色体的基因序列。随机生成一组初始染色体,构成初始种群,这些染色体代表了不同的路径尝试。
- 适应度函数
:定义适应度函数来评估每条染色体(路径)的优劣。适应度函数的设计通常基于路径的长度、是否避开障碍物等因素。例如,路径越短且不经过障碍物区域,其适应度值越高。在六边形网格场景下,需要根据六边形网格的特点精确计算路径长度以及判断与障碍物的关系。
- 遗传操作
:
- 选择
:根据适应度值从种群中选择染色体,适应度高的染色体有更大的概率被选中,进入下一代种群。这模拟了自然界中适者生存的原则,使得优良的路径特征能够保留和传递。
- 交叉
:对选中的染色体进行交叉操作,交换部分基因片段,产生新的染色体(路径)。例如,通过单点交叉或多点交叉的方式,在两条父代染色体上随机选择交叉点,交换交叉点后的基因片段,从而生成子代染色体,探索新的路径可能性。
- 变异
:以一定概率对染色体的基因进行变异,随机改变某个基因的值(即路径中的某个节点),增加种群的多样性,避免算法陷入局部最优解。在六边形网格中,变异操作需要确保生成的新节点仍然在合法的网格范围内。通过不断重复遗传操作,种群中的染色体逐渐向最优路径进化。
- 选择
(三)蚁群优化算法原理
- 蚂蚁与信息素
:模拟蚂蚁在六边形网格环境中寻找食物(目标节点)的行为。每只蚂蚁从起始节点出发,在网格中随机选择下一个节点移动。蚂蚁在移动过程中会在经过的路径上留下信息素,信息素浓度会随着时间逐渐挥发。

(四)元胞自动机原理
- 元胞与规则
:将六边形网格中的每个网格单元视为一个元胞。每个元胞具有一定的状态,例如空闲、障碍物、已访问等。元胞的状态根据其自身状态以及相邻元胞的状态,按照预先定义的规则进行更新。
- 路径生成规则
:定义元胞状态更新规则以生成路径。例如,从起始元胞开始,标记为已访问,然后根据相邻元胞的状态(是否空闲、是否为障碍物)以及与目标元胞的相对位置关系,决定下一个被访问的元胞。如果某个相邻元胞是空闲且未被访问过,且在朝着目标元胞的方向上,则该元胞可能被选中并更新为已访问状态。通过不断更新元胞状态,逐步形成从起始元胞到目标元胞的路径。在这个过程中,可以根据不同场景的需求,调整规则以适应障碍物分布、路径偏好等因素。例如,在存在复杂障碍物的场景中,规则可以优先选择避开障碍物且距离目标较近的元胞,从而生成可行的避障路径。
通过这四种经典算法在六边形网格上的应用,可以有效地解决不同场景下的路径规划问题,满足多样化的实际需求。
⛳️ 运行结果








🔗 参考文献
function [x,fval,exitFlag,output,population,scores] = ga(fun,nvars,Aineq,bineq,Aeq,beq,lb,ub,nonlcon,intcon,options)
%GA Constrained optimization using genetic algorithm.
% GA attempts to solve problems of the following forms:
% min F(X) subject to: A*X <= B, Aeq*X = Beq (linear constraints)
% X C(X) <= 0, Ceq(X) = 0 (nonlinear constraints)
% LB <= X <= UB
% X(i) integer, where i is in the index
% vector INTCON (integer constraints)
%
% Note: If INTCON is not empty, then no equality constraints are allowed.
% That is:-
% * Aeq and Beq must be empty
% * Ceq returned from NONLCON must be empty
%
% X = GA(FITNESSFCN,NVARS) finds a local unconstrained minimum X to the
% FITNESSFCN using GA. NVARS is the dimension (number of design
% variables) of the FITNESSFCN. FITNESSFCN accepts a vector X of size
% 1-by-NVARS, and returns a scalar evaluated at X.
%
% X = GA(FITNESSFCN,NVARS,A,b) finds a local minimum X to the function
% FITNESSFCN, subject to the linear inequalities A*X <= B. Linear
% constraints are not satisfied when the PopulationType option is set to
% 'bitString' or 'custom'. See the documentation for details.
%
% X = GA(FITNESSFCN,NVARS,A,b,Aeq,beq) finds a local minimum X to the
% function FITNESSFCN, subject to the linear equalities Aeq*X = beq as
% well as A*X <= B. (Set A=[] and B=[] if no inequalities exist.) Linear
% constraints are not satisfied when the PopulationType option is set to
% 'bitString' or 'custom'. See the documentation for details.
%
% X = GA(FITNESSFCN,NVARS,A,b,Aeq,beq,lb,ub) defines a set of lower and
% upper bounds on the design variables, X, so that a solution is found in
% the range lb <= X <= ub. Use empty matrices for lb and ub if no bounds
% exist. Set lb(i) = -Inf if X(i) is unbounded below; set ub(i) = Inf if
% X(i) is unbounded above. Linear constraints are not satisfied when the
% PopulationType option is set to 'bitString' or 'custom'. See the
% documentation for details.
%
% X = GA(FITNESSFCN,NVARS,A,b,Aeq,beq,lb,ub,NONLCON) subjects the
% minimization to the constraints defined in NONLCON. The function
% NONLCON accepts X and returns the vectors C and Ceq, representing the
% nonlinear inequalities and equalities respectively. GA minimizes
% FITNESSFCN such that C(X)<=0 and Ceq(X)=0. (Set lb=[] and/or ub=[] if
% no bounds exist.) Nonlinear constraints are not satisfied when the
% PopulationType option is set to 'bitString' or 'custom'. See the
% documentation for details.
%
% X = GA(FITNESSFCN,NVARS,A,b,Aeq,beq,lb,ub,NONLCON,options) minimizes
% with the default optimization parameters replaced by values in OPTIONS.
% OPTIONS can be created with the OPTIMOPTIONS function. See OPTIMOPTIONS
% for details. For a list of options accepted by GA refer to the
% documentation.
%
% X = GA(FITNESSFCN,NVARS,A,b,[],[],lb,ub,NONLCON,INTCON) requires that
% the variables listed in INTCON take integer values. Note that GA does
% not solve problems with integer and equality constraints. Pass empty
% matrices for the Aeq and beq inputs if INTCON is not empty.
%
% X = GA(FITNESSFCN,NVARS,A,b,[],[],lb,ub,NONLCON,INTCON,options)
% minimizes with integer constraints and the default optimization
% parameters replaced by values in OPTIONS. OPTIONS can be created with
% the OPTIMOPTIONS function. See OPTIMOPTIONS for details.
%
% X = GA(PROBLEM) finds the minimum for PROBLEM. PROBLEM is a structure
% that has the following fields:
% fitnessfcn: <Fitness function>
% nvars: <Number of design variables>
% Aineq: <A matrix for inequality constraints>
% bineq: <b vector for inequality constraints>
% Aeq: <Aeq matrix for equality constraints>
% beq: <beq vector for equality constraints>
% lb: <Lower bound on X>
% ub: <Upper bound on X>
% nonlcon: <Nonlinear constraint function>
% intcon: <Index vector for integer variables>
% options: <Options created with optimoptions('ga',...)>
% rngstate: <State of the random number generator>
%
% [X,FVAL] = GA(FITNESSFCN, ...) returns FVAL, the value of the fitness
% function FITNESSFCN at the solution X.
%
% [X,FVAL,EXITFLAG] = GA(FITNESSFCN, ...) returns EXITFLAG which
% describes the exit condition of GA. Possible values of EXITFLAG and the
% corresponding exit conditions are
%
% 1 Average change in value of the fitness function over
% options.MaxStallGenerations generations less than
% options.FunctionTolerance and constraint violation less than
% options.ConstraintTolerance.
% 3 The value of the fitness function did not change in
% options.MaxStallGenerations generations and constraint violation
% less than options.ConstraintTolerance.
% 4 Magnitude of step smaller than machine precision and constraint
% violation less than options.ConstraintTolerance. This exit
% condition applies only to nonlinear constraints.
% 5 Fitness limit reached and constraint violation less than
% options.ConstraintTolerance.
% 0 Maximum number of generations exceeded.
% -1 Optimization terminated by the output or plot function.
% -2 No feasible point found.
% -4 Stall time limit exceeded.
% -5 Time limit exceeded.
%
% [X,FVAL,EXITFLAG,OUTPUT] = GA(FITNESSFCN, ...) returns a
% structure OUTPUT with the following information:
% rngstate: <State of the random number generator before GA started>
% generations: <Total generations, excluding HybridFcn iterations>
% funccount: <Total function evaluations>
% maxconstraint: <Maximum constraint violation>, if any
% message: <GA termination message>
%
% [X,FVAL,EXITFLAG,OUTPUT,POPULATION] = GA(FITNESSFCN, ...) returns the
% final POPULATION at termination.
%
% [X,FVAL,EXITFLAG,OUTPUT,POPULATION,SCORES] = GA(FITNESSFCN, ...) returns
% the SCORES of the final POPULATION.
%
%
% Example:
% Unconstrained minimization of 'rastriginsfcn' fitness function of
% numberOfVariables = 2
% x = ga(@rastriginsfcn,2)
%
% Display plotting functions while GA minimizes
% options = optimoptions('ga','PlotFcn',...
% {@gaplotbestf,@gaplotbestindiv,@gaplotexpectation,@gaplotstopping});
% [x,fval,exitflag,output] = ga(@rastriginsfcn,2,[],[],[],[],[],[],[],options)
%
% An example with inequality constraints and lower bounds
% A = [1 1; -1 2; 2 1]; b = [2; 2; 3]; lb = zeros(2,1);
% % Use mutation function which can handle constraints
% options = optimoptions('ga','MutationFcn',@mutationadaptfeasible);
% [x,fval,exitflag] = ga(@lincontest6,2,A,b,[],[],lb,[],[],options);
%
% FITNESSFCN can also be an anonymous function:
% x = ga(@(x) 3*sin(x(1))+exp(x(2)),2)
%
% If FITNESSFCN or NONLCON are parameterized, you can use anonymous
% functions to capture the problem-dependent parameters. Suppose you want
% to minimize the fitness given in the function myfit, subject to the
% nonlinear constraint myconstr, where these two functions are
% parameterized by their second argument a1 and a2, respectively. Here
% myfit and myconstr are MATLAB file functions such as
%
% function f = myfit(x,a1)
% f = exp(x(1))*(4*x(1)^2 + 2*x(2)^2 + 4*x(1)*x(2) + 2*x(2) + a1);
%
% and
%
% function [c,ceq] = myconstr(x,a2)
% c = [1.5 + x(1)*x(2) - x(1) - x(2);
% -x(1)*x(2) - a2];
% % No nonlinear equality constraints:
% ceq = [];
%
% To optimize for specific values of a1 and a2, first assign the values
% to these two parameters. Then create two one-argument anonymous
% functions that capture the values of a1 and a2, and call myfit and
% myconstr with two arguments. Finally, pass these anonymous functions to
% GA:
%
% a1 = 1; a2 = 10; % define parameters first
% % Mutation function for constrained minimization
% options = optimoptions('ga','MutationFcn',@mutationadaptfeasible);
% x = ga(@(x)myfit(x,a1),2,[],[],[],[],[],[],@(x)myconstr(x,a2),options)
%
% Example: Solving a mixed-integer optimization problem
% An example of optimizing a function where a subset of the variables are
% required to be integers:
%
% % Define the objective and call GA. Here variables x(2) and x(3) will
% % be integer.
% fun = @(x) (x(1) - 0.2)^2 + (x(2) - 1.7)^2 + (x(3) -5.1)^2;
% x = ga(fun,3,[],[],[],[],[],[],[],[2 3])
%
% See also OPTIMOPTIONS, FITNESSFUNCTION, GAOUTPUTFCNTEMPLATE, PATTERNSEARCH, @.
% Copyright 2003-2021 The MathWorks, Inc.
% If the first arg is not a gaoptimset, then it's a fitness function followed by a genome
% length. Here we make a gaoptimset from the args.
defaultopt = struct('PopulationType', 'doubleVector', ...
'PopInitRange', [], ...
'PopulationSize', '50 when numberOfVariables <= 5, else 200', ...
'EliteCount', '0.05*PopulationSize', ...
'CrossoverFraction', 0.8, ...
'MigrationDirection','forward', ...
'MigrationInterval',20, ...
'MigrationFraction',0.2, ...
'Generations', '100*numberOfVariables', ...
'TimeLimit', inf, ...
'FitnessLimit', -inf, ...
'StallTest', 'averageChange', ...
'StallGenLimit', 50, ...
'StallTimeLimit', inf, ...
'TolFun', 1e-6, ...
'TolCon', 1e-3, ...
'InitialPopulation',[], ...
'InitialScores', [], ...
'NonlinConAlgorithm', 'auglag', ...
'InitialPenalty', 10, ...
'PenaltyFactor', 100, ...
'PlotInterval',1, ...
'CreationFcn',[], ...
'FitnessScalingFcn', @fitscalingrank, ...
'SelectionFcn', [], ...
'CrossoverFcn',[], ...
'MutationFcn',[], ...
'HybridFcn',[], ...
'Display', 'final', ...
'PlotFcns', [], ...
'OutputFcns', [], ...
'Vectorized','off', ...
'IntegerTolerance',1e-5, ...
'UseParallel', false ...
);
% Check number of input arguments
try
narginchk(1,11);
catch ME
error(message('globaloptim:ga:numberOfInputs', ME.message));
end
% If just 'defaults' passed in, return the default options in X
if nargin == 1 && nargout <= 1 && strcmpi(fun,'defaults')
x = defaultopt;
return
end
if nargin < 11, options = [];
if nargin < 10, intcon = [];
if nargin < 9, nonlcon = [];
if nargin < 8, ub = [];
if nargin < 7, lb = [];
if nargin <6, beq = [];
if nargin <5, Aeq = [];
if nargin < 4, bineq = [];
if nargin < 3, Aineq = [];
end
end
end
end
end
end
end
end
end
% Is third argument a structure
if nargin == 3 && (isstruct(Aineq) || isa(Aineq, 'optim.options.SolverOptions')) % Old syntax
options = Aineq; Aineq = [];
end
% Is tenth argument a structure? If so, integer constraints have not been
% specified
if nargin == 10 && (isstruct(intcon) || isa(intcon, 'optim.options.SolverOptions'))
options = intcon;
intcon = [];
end
% One input argument is for problem structure
if nargin == 1
if isa(fun,'struct')
[fun,nvars,Aineq,bineq,Aeq,beq,lb,ub,nonlcon,intcon,rngstate,options] = separateOptimStruct(fun);
% Reset the random number generators
resetDfltRng(rngstate);
else % Single input and non-structure.
error(message('globaloptim:ga:invalidStructInput'));
end
end
% Prepare the options for the solver
options = prepareOptionsForSolver(options, 'ga');
% Ensure that any *Fcn options are function handles or cell arrays of
% function handles. Ideally this would be done in the /private/validate.m
% function (called from gacommon). However, gaoptimset is called below
% before the call to gacommon and this does not accept string values for
% the *Fcn options. Hence the replacement is performed here.
if isfield(options, 'CreationFcn')
options.CreationFcn = replaceEnumStringWithFcnHdl('GaOptions', 'CreationFcn', options.CreationFcn);
end
if isfield(options, 'CrossoverFcn')
options.CrossoverFcn = replaceEnumStringWithFcnHdl('GaOptions', 'CrossoverFcn', options.CrossoverFcn);
end
if isfield(options, 'FitnessScalingFcn')
options.FitnessScalingFcn = replaceEnumStringWithFcnHdl('GaOptions', 'FitnessScalingFcn', options.FitnessScalingFcn);
end
if isfield(options, 'HybridFcn')
options.HybridFcn = replaceEnumStringWithFcnHdl('GaOptions', 'HybridFcn', options.HybridFcn);
end
if isfield(options, 'MutationFcn')
options.MutationFcn = replaceEnumStringWithFcnHdl('GaOptions', 'MutationFcn', options.MutationFcn);
end
if isfield(options, 'PlotFcns')
options.PlotFcns = replaceEnumStringWithFcnHdl('GaOptions', 'PlotFcn', options.PlotFcns);
end
if isfield(options, 'SelectionFcn')
options.SelectionFcn = replaceEnumStringWithFcnHdl('GaOptions', 'SelectionFcn', options.SelectionFcn);
end
% If fun is a cell array with additional arguments get the function handle
if iscell(fun)
FitnessFcn = fun{1};
else
FitnessFcn = fun;
end
% Only function handles or inlines are allowed for FitnessFcn
if isempty(FitnessFcn) || ~(isa(FitnessFcn,'inline') || isa(FitnessFcn,'function_handle'))
error(message('globaloptim:ga:needFunctionHandle'));
end
% We need to check the nvars here before we call any solver
valid = isnumeric(nvars) && isscalar(nvars)&& (nvars > 0) ...
&& (nvars == floor(nvars));
if ~valid
error(message('globaloptim:ga:notValidNvars'));
end
% Set default PopInitRange for non-MINLP problems
defaultopt.PopInitRange = [-10;10];
% Set the default ProblemdefOptions
defaultopt.ProblemdefOptions = struct('FunOnWorkers', true, 'FromSolve', false) ;
% Defaults for integer constrained problems
% Specific checks and modification of options for mixed integer GA
if ~isempty(intcon)
% Change the default options for PopulationSize and EliteCount here.
defaultopt.PopulationSize = max(min(10*nvars, 100), 40);
defaultopt.EliteCount = ceil(0.05*defaultopt.PopulationSize);
% Adjust PopInitRange for MINLPs
defaultopt.PopInitRange = [-1e4 + 1; 1e4 + 1];
end
user_options = options;
% Use default options if empty
if ~isempty(options) && ~isa(options,'struct')
error('globaloptim:ga:optionsNotAStruct', ...
getString(message('optimlib:commonMsgs:InvalidOptions')));
elseif isempty(options)
options = defaultopt;
end
% Take defaults for parameters that are not in options structure
options = gaoptimset(defaultopt,options); %#ok
% If a user doesn't specify PopInitRange, we want to set it to the
% bounds when we create the initial population. Need to store a flag
% that indicates whether the user has specified PopInitRange so we can
% do this in the creation function.
options.UserSpecPopInitRange = isa(user_options, 'struct') && ...
isfield(user_options, 'PopInitRange') && ~isempty(user_options.PopInitRange);
% Check for non-double inputs
msg = isoptimargdbl('GA', {'NVARS','A', 'b', 'Aeq','beq','lb','ub'}, ...
nvars, Aineq, bineq, Aeq, beq, lb, ub);
if ~isempty(msg)
error('globaloptim:ga:dataType',msg);
end
% Introduce field to describe the objective type
options.MultiObjective = false;
% Make sure the ProblemdefOptions are set
if isfield(user_options, 'ProblemdefOptions')
options.ProblemdefOptions = user_options.ProblemdefOptions;
else
options.ProblemdefOptions = defaultopt.ProblemdefOptions;
end
[x,fval,exitFlag,output,population,scores,FitnessFcn,nvars,Aineq,bineq,Aeq,beq,lb,ub, ...
NonconFcn,options,Iterate,type] = gacommon(nvars,fun,Aineq,bineq,Aeq,beq,lb,ub, ...
nonlcon,intcon,options,user_options);
if exitFlag < 0
return;
end
% Turn constraints into right size if they are empty.
if isempty(Aineq)
Aineq = zeros(0,nvars);
end
if isempty(bineq)
bineq = zeros(0,1);
end
if isempty(Aeq)
Aeq = zeros(0,nvars);
end
if isempty(beq)
beq = zeros(0,1);
end
if ~isempty(options.OutputFcns) || ~isempty(options.PlotFcns)
% For calling an OutputFcn, make an options object (to be updated
% later) that can be passed in
options.OutputPlotFcnOptions = optimoptions(@ga);
options.OutputPlotFcnOptions = copyForOutputAndPlotFcn(options.OutputPlotFcnOptions,options);
end
% Call appropriate single objective optimization solver
if ~isempty(intcon)
% Call gapenalty with 'bound' constraint type because linear
% and integer constraints are handled by operators explicitly.
[x,fval,exitFlag,output,population,scores] = gapenalty(FitnessFcn,nvars,...
Aineq,bineq,Aeq,beq,lb,ub,NonconFcn,options,output,Iterate,'boundconstraints');
else
switch (output.problemtype)
case 'unconstrained'
[x,fval,exitFlag,output,population,scores] = gaunc(FitnessFcn,nvars, ...
options,output,Iterate);
case {'boundconstraints', 'linearconstraints'}
[x,fval,exitFlag,output,population,scores] = galincon(FitnessFcn,nvars, ...
Aineq,bineq,Aeq,beq,lb,ub,options,output,Iterate);
case 'nonlinearconstr'
if strcmpi(options.NonlinConAlgorithm,'auglag')
[x,fval,exitFlag,output,population,scores] = gacon(FitnessFcn,nvars, ...
Aineq,bineq,Aeq,beq,lb,ub,NonconFcn,options,output,Iterate,type);
else
[x,fval,exitFlag,output,population,scores] = gapenalty(...
FitnessFcn,nvars,Aineq,bineq,Aeq,beq,lb,ub, ...
NonconFcn,options,output,Iterate,type);
end
end
end
🍅往期回顾扫扫下方二维码
更多推荐



所有评论(0)