GA算法简介

遗传算法的理解一定要抛弃掉生物学和进化论的思想，抓着这种论调会使得算法的流程和实现云遮雾绕；

遗传算法的理解：

初始种群：

所谓初始种群就是满足任务的解的不等式条件，形式上相似的有拉格朗日乘数法求约束条件下的极值问题；
简单来说就是你的函数的未知数虽然是随机生成的 0,1整数，但是这些个0-1组合起来的解并不是每个都能符合
任务需求；

此部分设计了一个小的优化点，采用了矩阵运算将 0，1构成的二进制编码(这里是将[0,1,0,1]这类0-1整型数组通过和二进制基数数组做矩阵运算得到转换后的十进制数)，利用这个十进制数减少用于越界检查的集合的内存大小，并且通过短路或，实现随机生成的二进制编码在越界集合内就重新生成，通过循环生成可以满足约束条件的解，直到达到种群数量

适应度函数

这里讲一下适应度函数和适应度，其实就是经常讲的损失、代价函数，因为多数优化算法都是最大化适应度函数作为优化目标，需要最小化适应度函数的时候可以通过 取倒数 fitness = 1/fitness 或者取负值 fitness = -1* fitness 来转化为最大化目标形式，适应度函数也就是你要求最大或者最小的那个值的计算过程，可以通过对这个计算过程进行合理的重构，来优化计算效率，比如因式分解，减少计算的步骤，这里可以提一提，文献中经常看见对适应度函数的变形和优化

遗传迭代：

这里的迭代就是通过多次更新解的编码，来搜索比较好的个体，迭代过程中会保存全局最优个体的适应度值和解

  1.   score = self._get_score(solo) # 这里计算每个个体的适应度值
  2.   bestIndex = np.argmin(score)  # 得到转换前的最小适应度个体，这个时候的适应度就是成本函数
  3.   self.iter_score.append(score[bestIndex][0]) # 使用一个全局列表容器记录每一轮迭代的最佳值
  4.   next_pop = []  # [solo[bestIndex]]
  5.   if score[bestIndex] < self.Gbest_score: # 如果出现新的最佳适应度，就新建一个容器来存放这个值对应的解
  6.       self.Gbest_solo = [solo[bestIndex].tolist()]
  7.       self.Gbest_score = score[bestIndex]
  9.   elif score[bestIndex] == self.Gbest_score: # 如果最佳适应度的解不止一个就继续添加到列表容器当中
  10.       self.Gbest_solo.append(solo[bestIndex].tolist())

选择过程：

选择过程是遗传算法比较难懂的点，可以将轮盘赌看作是一个switch case 结构；首先对群落中所有个体做归一化得到这个个体在本轮中相对的优越程度，也就是GA算法简介 - 图1 操作，然后通过累计和处理 GA算法简介 - 图2 ,这样就将适应度分割成一个个区间，只有没能落到前面的区间才会继续往后找，这个搜索的过程：如果原有个体 item的 解 solo的 fitness 处理后的适应度值大，则落入该个体代表的区间的概率大，也就是rand()<pop.fitness[i] 这里是看似是每个个体值和一个随机数来比较，其实在选择过程中其详细代码如下：

  1.   for i in range(self.pop):
  2.       r = np.random.rand()
  3.       for j in range(cumProb.shape[0]):
  4.           if r < cumProb[j]:
  5.               next_pop.append(solo[j])
  6.               break

按照Java的写法应该是：

  1. for(int i=0;i<pop.size;i++){
  2.   int r = Math.random();
  3.   for(int j=0;j<cumProb.size();j++ ){
  4.     if(r<cumProb.get(j)){
  5.       next_pop.add(solo.get(j));
  6.       break;
  7.     }
  8.   }
  9. }

也就是需要生成和群落里面元素数量相等的随机数，每个随机数从最群落里面向后遍历，直到遇到第一个大于这个随机数的元素的适应度累计概率的值，也就是说当 r < cumProb[j]的条件满足的时候，其实是 cumProb[j-1]<r < cumProb[j] 也就是 r落在了 j 这个个体表示的概率区间里面 因为 这个区间的大小是 GA算法简介 - 图3 也就是原本的归一化比例，现在将原本的遍历过程，看成是查找随机值落在哪一个样本上。

经过轮盘赌随机选择之后的样本会被用作后续的交叉和变异过程的材料

选择操作对群落( 可以视作是一个定长的容器)里面的元素是必定经历的环节，但是下面的交叉操作和变异操作对元素来说是以一定概率来执行的。

交叉操作：

在算法构建初期存在一个形参设置：pc 也就是 cross probability 交叉概率，当生成的随机值小于 交叉概率 pc的时候就会执行交叉操作，也就是 PC越接近于1 交叉操作越频繁，现在介绍交叉操作的细节：

现在有两个数组如下图所示，要交换 选择阶段留下的群落中两个相邻 item的 随机位置前后的连续元素的值

算法实现如下：

  1.  while(i < self.pop-1):
  2.             position = np.random.randint(0, rangeIndex)
  3.             temp11 = next_pop[i][:position]
  4.             temp12 = next_pop[i][position:]
  5.             temp21 = next_pop[i+1][:position]
  6.             temp22 = next_pop[i+1][position:]
  7.             next_pop[i] = np.concatenate((temp11, temp22))
  8.             # 这个操作是把两个数组分段拼接起来
  9.             next_pop[i+1] = np.concatenate((temp21, temp12))

本阶段和下一个变异阶段存在一个约束检查的操作，要求生成的个体要满足 GA算法简介 - 图4 也就是保证能够买够足够数量的商品，不满足约束的个体会重新执行变异或者交叉操作直到满足约束

变异操作

这部分是遗传算法的最后一个主要模块：仍旧遵循：通过随机值来判断交叉后得到的新群落中的每一个元素是否要执行变异操作，变异后检查是否符合约束条件，不符合就重新生成

变异的思想和实现都是十分简单的：

  1. for i in range(len(next_pop)):
  2.             ret = np.random.rand()
  3.             if ret < self.pm:  # 命中变异概率
  4.                 position = np.random.randint(0, self.dims_select)
  5.                 next_pop[i][position] = 1 - next_pop[i][position]
  6.                 # 取反变异
  7.                 while(self.check_out(next_pop[i])):
  8.                     position = np.random.randint(0, self.dims_select)
  9.                     next_pop[i][position] = 1 - next_pop[i][position]

核心的步骤是：

  • 对列表容器内的个体元素遍历执行以下操作

  • 产生一个随机数，当前的 pm mutation probability 也就是变异概率 是不是小于这个随机数，小于执行下一步，大于直接放回列表容器

  • 产生一个在编码长度以内的随机位置索引

  • 对这个随机位置进行取反 也就是 GA算法简介 - 图5 这个操作的实现代码是 1- next_pop[i][rand_position] 当随机位置上的元素是0的时候： GA算法简介 - 图6; 当随机位置上的元素是1的时候：GA算法简介 - 图7; 这样实现了对随机位置的取反

  • 检查约束条件是否满足，不满足就对当前元素反复执行变异，直到满足约束条件

PS： 约束条件

约束条件的检查是通过：

np.matmul(temp, self.constraint) < self.Min_need 这个布尔表达是来判断的，这个表达式为 true 时，说明当前的个体的解不能满足基本约束条件，会反复重新生成，在交叉阶段会反复执行交叉操作，在变异阶段会反复执行变异操作；

最后的主函数： main()

  1.   # 产生初始解
  2.   solo = self.init_solo()
  3.   # 初始化种群
  4.   for i in range(self.Max_iter):
  5.       pop = self.selecter(solo)
  6.       pop = self._cross(pop)
  7.       pop = self.maturain(pop)
  8.       solo = np.array(pop)
  9.   for i in self.Gbest_solo:
  10.       print(i, end=":  :")
  11.       print(self.Gbest_score)

流程上是：

  • 产生初始解

  • 执行遗传迭代

    • 选择优势个体的解
    • 按照交叉概率，对选择的解进行交叉生成合乎条件的新的群落
    • 按照变异概率，对交叉的解进行变异生成合乎条件的新的群落
    • 是否满足终止条件：达到最大迭代次数
  • 输出存在全局列表当中的每一轮产生的全局最佳适应度和对应的解