4 基于智能算法的路径规划 —— 遗传算法

基础讲解

常用函数

mod：取余、取模
fix：向 0 取整
floor：向下取整

1. 种群初始化

• 起点和终点对应的x和y坐标

% 求起点和终点对应的x和y坐标
% 起点所在列（从左到右编号1.2.3...）
xs = mod(p_start, x) + 1; % x  = 20, 对应上面公式的Gsize
% 起点所在行（从上到下编号行1.2.3...）
ys = fix(p_start / x) + 1; % x = 20 ，fix 向0取整
% 终点所在列、行
xe = mod(p_end, x) + 1;
ye = fix(p_end / x) + 1;
1
2
3
4
5
6
7
8

• 判断不连续，并插入栅格

while i ~= single_path_num % ~= 不等于
    % 点i所在列（从左到右编号1.2.3...）
    x_now = mod(single_new_pop(1, i), x) + 1; 
    % 点i所在行（从上到下编号行1.2.3...）
    y_now = fix(single_new_pop(1, i) / x) + 1;
    % 点i+1所在列、行
    x_next = mod(single_new_pop(1, i + 1), x) + 1;
    y_next = fix(single_new_pop(1, i + 1) / x) + 1;
    
    % 初始化最大迭代次数
    max_iteration = 0;
    
    % 判断点i和i+1是否连续,若不连续插入值
    while max(abs(x_next - x_now), abs(y_next - y_now)) > 1
        x_insert = floor((x_next + x_now) / 2);
        y_insert = floor((y_next + y_now) / 2);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2. 选择

• d —— 表示路径长度，越短越好
• fit1 —— 取路径 d 的倒数，这样越短的路径其适应度越大
• fit2 —— 路径的顺滑性，如角6，0-6-7，角度越大越好，所以不用取倒数
• fit —— 适应度的值
• p —— 表示概率，为每个个体计算一个概率，使用轮盘赌方式，为每个概率分配所占面积。面积越大，被选择概率越大。好的个体保留下来的概率比较大，保证了多样性。

3. 交叉

• 交换交叉点前后的路径形成新的路径，丰富了个体

4. 变异

通过种群初始化的方式，在 1和 13 之间产生新的路径，1-7-13，产生更好的路径。

循环执行以上三步

路径会越优越短

算法讲解 MATLAB

用坐标(a,b)表示栅格序号(0-399)

 % 栅格序号
 num_insert = (x_insert - 1) + (y_insert - 1) * x; % x = 20
1
2