前言
在很多问题上是没有标准解的，我们要找到最优解。
这就用到了遗传算法。
遗传算法是一种通过模拟自然进化过程来解决问题的优化算法。
它在许多领域和场景中都有广泛应用。以下是一些常见的使用遗传算法的场景：
- 优化问题：遗传算法可以应用于各种优化问题，如工程设计、物流优化、路径规划、参数调优等。 它可以帮助找到最优或接近最优解，解决复杂的多目标优化问题。
- 机器学习：遗传算法可以用于机器学习的特征选择和参数调优。 例如，使用遗传算法来选择最佳特征组合，或者通过遗传算法搜索最佳参数配置以提高机器学习算法的性能。
- 调度和排程问题：遗传算法可以应用于解决调度和排程问题，如作业车间调度、员工排班、交通信号优化等。 它可以找到最佳的任务分配和调度策略，从而提高效率和降低成本。
- 约束满足问题：遗传算法可以用于解决约束满足问题，如布尔满足问题（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个最优的。
这里加了个退出条件，当适应度一直不变达到一定数量的时候，就退出。
代码示例：
代码语言：javascript复制<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>
