前言

在很多问题上是没有标准解的，我们要找到最优解。

这就用到了遗传算法。

遗传算法是一种通过模拟自然进化过程来解决问题的优化算法。

它在许多领域和场景中都有广泛应用。以下是一些常见的使用遗传算法的场景：

优化问题：遗传算法可以应用于各种优化问题，如工程设计、物流优化、路径规划、参数调优等。

它可以帮助找到最优或接近最优解，解决复杂的多目标优化问题。
机器学习：遗传算法可以用于机器学习的特征选择和参数调优。

例如，使用遗传算法来选择最佳特征组合，或者通过遗传算法搜索最佳参数配置以提高机器学习算法的性能。
调度和排程问题：遗传算法可以应用于解决调度和排程问题，如作业车间调度、员工排班、交通信号优化等。

它可以找到最佳的任务分配和调度策略，从而提高效率和降低成本。
约束满足问题：遗传算法可以用于解决约束满足问题，如布尔满足问题（SAT）、旅行商问题（TSP）等。

它可以搜索解空间，寻找满足所有约束条件的最优解或近似最优解。
数据挖掘和模式识别：遗传算法可以应用于数据挖掘和模式识别任务，如聚类、分类、回归等。

它可以通过优化模型参数或搜索特征组合，提高模型的性能和泛化能力。

概要

基因 ( Gene ) ：一个遗传因子。

染色体 ( Chromosome ) ：包含一组的基因。

遗传与变异：新个体会遗传父母双方各一部分的基因，同时有一定的概率发生基因变异。

简单说来就是：

繁殖过程，会发生基因交叉( Crossover ) ，基因突变 ( Mutation ) ，适应度( Fitness )低的个体会被逐步淘汰，而适应度高的个体会越来越多。那么经过N代的自然选择后，保存下来的个体都是适应度很高的，其中很可能包含史上产生的适应度最高的那个个体。

我们首先要生成N个祖先染色体，N大于1。

从中选择X个染色体，进行繁殖下一代，繁殖过程有两种：交叉和变异。

交叉：选择的染色体和另一个替换基因。
变异：选择的染色体自己发生变异。

从中选择最优的N个染色体继续繁殖，达到设置的繁殖代数后，获取适应度最高的个体。

需要注意的是

繁殖次数内不一定找到最优的解，繁殖的次数越多找到最优解的可能越高。

示例

假如我们的原始数组是[1, 9, 2, 6, 7, 5]，我们想要数组和目标数组更类似[1, 9, 2, 6, 7, 5]。

所以数组的适应度可以用数组的每一项想减的绝对值相加，值越小适应度越高。

首先产生祖先数组

最后一列是计算的适应度。

这里生成了10个祖先染色体。

每次繁殖的时候，新的染色体添加到祖先数组后，按适应度排序，再保留前10个最优的。

这里加了个退出条件，当适应度一直不变达到一定数量的时候，就退出。

代码示例：

<template>
  <div>
    <div class="title"><input type="button" value="开始演变" @click="heredity">
      <div class="mleft">当前数量：{{ currNum }}</div>
    </div>
    <div class="title">目标数组</div>
    <div class="a_item">
      <div class="a_item_left">
        <div v-for="(num,i2) in targetArr" :key="i2" class="num_item">
          {{ num }}
        </div>
      </div>
    </div>
    <div class="title">祖先数组</div>
    <div>
      <div v-for="(item,index) in ancestorsArr" :key="index" class="a_item">
        <div class="a_item_left">
          <div v-for="(num,i2) in item.arr" :key="i2" class="num_item">
            {{ num }}
          </div>
        </div>
        <div class="fitness_div">{{ item.fitnessValue }}</div>
      </div>
    </div>

  </div>
</template>

<script>
export default {
  name: "GeneticAlgorithm",
  data() {
    return {
      originArr: [1, 9, 2, 6, 7, 5],
      targetArr: [1, 4, 7, 2, 5, 8],
      ancestorsArr: [],//祖先数组
      maxNum: 1000,//繁殖总次数
      mutateRate: 0.3,//变异概率
      currNum: 0,//当前繁殖次数
    }
  },
  mounted() {
    //先初始化祖先数组
    this.initAncestorsArr();
    //祖先数组计算适应度并排序
    this.computeFitness();
  },
  methods: {
    initAncestorsArr() {
      let ancestorsArr = [];
      //生成祖先数组
      for (let i = 0; i < 10; i++) {
        let sortArr = [...this.originArr].sort(() => Math.random() - 0.5);
        ancestorsArr.push({
          arr: sortArr,
          fitnessValue: 0
        });
      }
      this.ancestorsArr = ancestorsArr;
    },
    //计算适应度 并排序
    computeFitness() {
      let ancestorsArr = this.ancestorsArr;
      let targetArr = this.targetArr;
      for (let i = 0; i < ancestorsArr.length; i++) {
        let item = ancestorsArr[i];
        //使用对应项的绝对值求和来计算适应度
        let arr = item.arr;
        let count = 0;
        for (let j = 0; j < arr.length; j++) {
          count += Math.abs(arr[j] - targetArr[j]);
        }
        item.fitnessValue = count;
      }
      ancestorsArr.sort((item1, item2) => {
        return item1.fitnessValue - item2.fitnessValue;
      })
    },
    getRandomNumber(min, max) {
      // 生成从min到max范围内的随机数
      return Math.floor(Math.random() * (max - min + 1)) + min;
    },
    removeItemsFromArray(originalArray, itemsToRemove) {
      for (let item of itemsToRemove) {
        let index = originalArray.indexOf(item);
        if (index !== -1) {
          originalArray.splice(index, 1);
        }
      }
      return originalArray;
    },
    delayRun(millSec) {
      return new Promise((resolve) => {
        setTimeout(resolve, millSec);
      })
    },
    async heredity() {
      let maxNum = this.maxNum;
      this.currNum = 0;
      let mutateRate = this.mutateRate;
      let minFitnessValue = this.ancestorsArr[0].fitnessValue;
      let minFitnessValueCount = 0;
      while (this.currNum < maxNum) {
        this.currNum += 1;
        if (Math.random() < mutateRate) {
          console.info("变异");
          this.mutate();
        } else {
          console.info("交叉");
          this.evolution();
        }
        if (minFitnessValue === this.ancestorsArr[0].fitnessValue) {
          minFitnessValueCount += 1;
          if (minFitnessValueCount >= 300) {
            break;
          }
        } else {
          minFitnessValue = this.ancestorsArr[0].fitnessValue;
          minFitnessValueCount = 0;
        }
        await this.delayRun(50);
      }
    },
    //交叉
    evolution() {
      //加入目前最优项为A，随机找到一个非目前最有的项B，随机一段最优项A的片段A1,删除B中A1的值，把A1片段插入到B中A1在A的索引位置
      let ancestorsArr = this.ancestorsArr;
      let index = this.getRandomNumber(1, ancestorsArr.length - 1);
      let optimalItem = ancestorsArr[0];
      let optimalItemArr = optimalItem.arr;
      let currItem = JSON.parse(JSON.stringify(ancestorsArr[index]));
      let currItemArr = currItem.arr;
      //这里子片段选3个值
      let optimalItemArrIndex = this.getRandomNumber(0, optimalItemArr.length - 4);
      let optimalItemArrSlice = optimalItemArr.slice(optimalItemArrIndex, optimalItemArrIndex + 3);
      this.removeItemsFromArray(currItemArr, optimalItemArrSlice);
      currItemArr.splice(optimalItemArrIndex, 0, ...optimalItemArrSlice);
      ancestorsArr.push(currItem);
      //祖先数组计算适应度并排序
      this.computeFitness();
      this.ancestorsArr = this.ancestorsArr.slice(0, 10);
    },
    //变异
    mutate() {
      //随机找到一个非目前最有的项B，找其中一个片段，把片段打乱顺序后重新插入原来的位置
      let ancestorsArr = this.ancestorsArr;
      let index = this.getRandomNumber(1, ancestorsArr.length - 1);
      let currItem = JSON.parse(JSON.stringify(ancestorsArr[index]));
      let currItemArr = currItem.arr;
      currItemArr.sort(() => Math.random() - 0.5);
      ancestorsArr.push(currItem);
      //祖先数组计算适应度并排序
      this.computeFitness();
      this.ancestorsArr = this.ancestorsArr.slice(0, 10);
    }
  }
}
</script>

<style scoped>

.title {
  display: flex;
  justify-content: flex-start;
  font-weight: bold;
  margin-top: 10px;
  margin-bottom: 10px;
}

.a_item {
  display: flex;
  align-items: center;
}

.a_item_left {
  display: flex;
}

.num_item {
  border: 1px solid #ddd;
  padding: 4px;
  border-radius: 4px;
  margin: 4px;
  width: 20px;
}

.fitness_div {
  color: red;
  border: 1px solid red;
  padding: 4px;
  border-radius: 4px;
  margin: 4px;
}

.mleft {
  margin-left: 10px;
}
</style>

我是码客，我是全栈工程师，我为自己代言。

最优解-遗传算法

前言

概要

示例