路径规划 | 图解遗传(GA)算法(附ROS C++仿真)

0 专栏介绍

🔥附C++/Python/Matlab全套代码🔥课程设计、毕业设计、创新竞赛必备！详细介绍全局规划(图搜索、采样法、智能算法等)；局部规划(DWA、APF等)；曲线优化(贝塞尔曲线、B样条曲线等)。

🚀详情：图解自动驾驶中的运动规划(Motion Planning)，附几十种规划算法

1 从进化论说起

从仿生学的角度来看，遗传算法(Genetic Algorithm, GA)是模拟自然界中生物进化过程的一种计算方法。它借鉴了达尔文的进化论中的许多概念，并将这些概念应用到解决优化问题上，例如

• 基因编码: 在遗传算法中，问题的解被编码成为一串基因序列，类似于生物体的染色体。这种编码方式可以直接映射到生物体的基因结构，每个基因对应于解空间中的一个特定参数或变量。
• 种群与个体: 遗传算法通过维护一个包含多个个体（解）的种群来模拟自然种群的概念。每个个体都代表了解决问题的一个可能方案，类似于自然界中的个体生物。
• 适应度评估: 遗传算法中的适应度评估类似于生物体在自然选择过程中的适应度。每个个体根据其解决方案在问题空间中的表现被赋予一个适应度分数，用于评价其优劣。
• 选择与交叉: 通过选择和交叉操作，遗传算法模拟了生物繁殖过程中的自然选择和基因交换。适应度较高的个体更有可能被选择为父代，并且它们的基因会通过交叉操作进行组合，产生新的后代个体。
• 变异: 变异操作在遗传算法中引入了个体基因的随机变化，类似于自然界中的基因突变。这种变异可以增加种群的多样性，从而有助于避免陷入局部最优解。

从这些角度来看，遗传算法可以被视为一种模仿生物进化过程的计算方法，它通过模拟生物体的繁殖、变异和适应度评估等过程，来寻找问题空间中的最优解。这种仿生学的视角不仅帮助我们理解遗传算法的原理，也为我们提供了一种全新的优化问题求解思路。

2 遗传算法基本概念

遗传算法的基本概念如下：

• $M$：种群数量；
• $\mathbf{x}$：染色体，其对应可行域中的一个可行解，染色体分量 称为基因片段，基因片段是发生交叉、变异的基本单位；
• $fit\left(\cdot \right)$：个体适应度函数，使目标函数越小的染色体对应的适应度越高；
• 选择算子：通过适应度从当前种群中筛选较优的染色体集合，并将其特性遗传到下一代种群，实现“优胜劣汰”的进化机制，筛选算法有轮盘赌筛选、精英筛选、排序筛选等，本文采用分层筛选法；
• 交叉算子：以一定的概率将两个匹配染色体中的部分基因片段互换，产生两个新的染色体，实现“同源染色体交叉互换”的进化特征，提高算法搜索能力，交叉算法有：均匀交叉、单点交叉、多点交叉等，本文采用多点交叉；
• 变异算子：以一定的概率将染色体的部分基因进行突变，产生新染色体，实现“基因突变”的进化特征，增强种群遗传因子多样性，缓解算法进入局部最优的概率，变异算法有：高斯变异、基本位变异、均匀变异等，本文采用基本位变异。

3 遗传算法流程

遗传算法基本原理如下所示

4 遗传算法ROS实现

核心代码如下所示

bool GA::plan(const Node& start, const Node& goal, std::vector<Node>& path, std::vector<Node>& expand)
{
  // variable initialization
  double init_fitness;
  Genets best_genet;
  PositionSequence init_positions;
  std::vector<Genets> genets_swarm;
  std::vector<Genets> genets_parent;
  std::vector<Genets> genets_children;

  // Generate initial position of genets swarm
  initializePositions(init_positions, start, goal, init_mode_);

  // genets initialization
  for (int i = 0; i < n_genets_; ++i)
  {
    std::vector<std::pair<int, int>> init_position;

    if ((i < n_inherited_) && (inherited_genets_.size() == n_inherited_))
      init_position = inherited_genets_[i].best_pos;
    else
      init_position = init_positions[i];

    // Calculate fitness
    init_fitness = calFitnessValue(init_position);

    if ((i == 0) || (init_fitness > best_genet.fitness))
    {
      best_genet.fitness = init_fitness;
      best_genet.position = init_position;
    }
    // Create and add genets objects to containers
    genets_swarm.emplace_back(init_position, init_fitness);
  }

  // random data
  std::random_device rd;
  std::mt19937 gen(rd());

  // Iterative optimization
  for (size_t iter = 0; iter < max_iter_; iter++)
  {
    selection(genets_swarm, genets_parent);

    genets_children = genets_parent;
    std::rotate(genets_children.begin(), genets_children.begin() + 1, genets_children.end());

    std::vector<std::thread> genets_list = std::vector<std::thread>(genets_parent.size());
    for (size_t i = 0; i < genets_parent.size(); ++i)
      genets_list[i] = std::thread(&GA::optimizeGenets, this, std::cref(genets_parent[i]), std::ref(genets_children[i]),
                                   std::ref(best_genet), i, std::ref(gen), std::ref(expand));
    for (size_t i = 0; i < genets_parent.size(); ++i)
      genets_list[i].join();

    // Copy the elements from genets_parent and genets_children to genets_swarm
    std::copy(genets_children.begin(), genets_children.end(), genets_swarm.begin());
    std::copy(genets_parent.begin(), genets_parent.end(), genets_swarm.begin() + genets_children.size());
  }

  // Generating Paths from Optimal Genets
  ...
  
  return !path.empty();
}

完整工程代码请联系下方博主名片获取

🔥 更多精彩专栏：

• 《ROS从入门到精通》
• 《Pytorch深度学习实战》
• 《机器学习强基计划》
• 《运动规划实战精讲》
• …