生物学中的进化论的核心为“物竞天择，适者生存”，暗含了的规则是生物能否生存是不定的，但是适应环境的生物更容易生存。生物的多样性能够保持来源于繁殖和变异。
没错，你没有点错，这的确是一篇有关人工智能入门的博客。开篇先提到一些生物学的观点是因为，人工智能中遗传算法的灵感来源于生物学，它是一种仿生的概念。
一.遗传算法
那么，什么是遗传算法呢？我们来举个栗子吧。
在爬虫动物园里有着各种各样的蚂蚁，我想选出一种蚂蚁来代表动物园去参加全城动物园的蚂蚁战斗比赛。那我该怎么选呢？这里有一个聪明人提出了一个方法：首先，我们从各个蚂蚁的种群中选择出一部分来（选择初代种群），让他们相互打架，然后把胜者留下来互相繁殖（交叉产生子代，选择了比较好的基因进行遗传）。把小蚂蚁养大，然后再让它们打架，胜者繁殖（不断生成子代）。通过多次的繁殖和选择，动物园有极大的可能选出的蚂蚁是所有蚂蚁中打架最厉害的。
好吧，这个例子不是特别的好。我理解的遗传算法，就是一个多点的不定向搜索。它通过多次的实验，来找到符合适应度函数的个体。
二.基本步骤
基本的步骤如下：
1.编码：将我们可以用来搜索的部分编码，常用二进制串
2.产生初代：
3.计算每个个体的适应度及适应度占总体的比例（这里我使用了轮盘赌方案）：
4.以交叉概率选择父代母代进行交叉
5.以变异概率进行变异
6.生成满足种群容量的子代
7.进化多代
三.代码及说明
Java代码：
import java.math.BigDecimal;
import java.util.Random;
public class Genetic {
int geneSize = 20;
int populationSize = 50;
int iterationNum =100;
double crossoverPro =0.8;
double mutationPro = 0.05;
int [][] individual = new int[populationSize][geneSize];
double [] realValue =new double[populationSize];
double [] fitness =new double [50];
double [] fitnessPro =new double [populationSize];
double currentOpt =0;
int currentX =0;
Random random =new Random();
double [] max =new double[iterationNum];
public void init(){
for(int i =0;i<populationSize;i++){
for(int j =0;j<geneSize;j++){
if(random.nextBoolean())
individual[i][j] =1;
else
individual[i][j] =0;
}
}
}
private void CalRealValue(){
for(int i =0;i<populationSize;i++){
realValue[i] =0;
double decimal = 0;
for(int j =0;j<3;j++){
realValue[i] = realValue[i]*2+individual[i][j];
}
for(int j =geneSize-1;j>=3;j--){
decimal = decimal/2+individual[i][j];
}
realValue[i] += decimal/2;
}
}
private void CalFitnessAndFitnessPro(){
double sum =0;
currentOpt =0;
currentX =0;
for(int i =0;i<populationSize;i++){
fitness[i] = realValue[i]+10*Math.sin(5*realValue[i])+7*Math.cos(4*realValue[i])+17;
if(currentOpt<fitness[i]){
currentOpt =fitness[i];
currentX =i;
}
sum+=fitness[i];
}
double section =0;
for(int i =0;i<populationSize;i++){
section +=fitness[i];
fitnessPro[i] = section/sum;
}
}
private void Reproduction(){
int [][] temp =new int [populationSize][geneSize];
//交叉
for(int i =0;i<populationSize-1;i=i+2){
int [] father =new int [geneSize];
double pro = random.nextDouble();
for(int j=0;j<populationSize;j++){
if(fitnessPro[j]>=pro){
for(int k =0;k<geneSize;k++)
father[k] = individual[j][k];
break;
}
}
pro =random.nextDouble();
int [] mother =new int [geneSize];
for(int j=0;j<populationSize;j++){
if(fitnessPro[j]>=pro){
for(int k =0;k<geneSize;k++)
mother[k] = individual[j][k];
break;
}
}
double pm =random.nextDouble();
if(pm<crossoverPro){
int changePosition =random.nextInt(geneSize);
for(int j=0;j<geneSize;j++){
if(j<changePosition){
temp[i][j] =father[j];
temp[i+1][j] = mother[j];
}
else {
temp[i][j] = mother[j];
temp[i+1][j] = father[j];
}
}
}else{
for(int j=0;j<geneSize;j++){
temp[i][j] =father[j];
temp[i+1][j] = mother[j];
}
}
}
for(int i =0;i<geneSize;i++){
individual[populationSize-1][i] = individual[currentX][i];
}
//变异
for(int i =0;i<populationSize-1;i++){
for(int j =0;j<geneSize;j++){
if(random.nextDouble()<mutationPro)
individual[i][j] = 1- temp[i][j];
else
individual[i][j] = temp[i][j];
}
}
}
public Genetic(){
init();
for(int i =0;i<iterationNum;i++){
CalRealValue();
CalFitnessAndFitnessPro();
BigDecimal optTemp =new BigDecimal(currentOpt-17);
BigDecimal valueTemp =new BigDecimal(realValue[currentX]);
optTemp =optTemp.setScale(5, BigDecimal.ROUND_HALF_UP);
valueTemp =valueTemp.setScale(5, BigDecimal.ROUND_HALF_UP);
System.out.println("第"+i+"代，最大值为："+optTemp+" 对应X是："+valueTemp);
max[i] = currentOpt-17;
Reproduction();
}
}
public double[] getMax(){
return max;
}
public static void main(String[] args) {
Genetic genetic =new Genetic();
}
}这里我使用了二进制编码，单点交叉，轮盘赌加精英选择（没代向下完整保留最优个体）。我目标是计算f(x) = x+ 10sin5x + 7cos4x 在[0,9]区间上的极大值，之所以在适应度函数里加入还加了17是因为f(x)在某些位置的时候是取到负数（最小-17），而参与轮盘赌计算的函数必须是正数，所以我加了17.
四.小尝试
二进制编码在0.001这样的数的时候是不精确的，于是我想能不能用十进制来解决这个问题呢？下面我尝试做了十进制编码（精确度是0.00001）
Java代码：
import java.math.BigDecimal;
import java.util.Random;
public class DecimalGenetic {
int geneSize = 6;
int populationSize = 50;
int iterationNum =100;
double crossoverPro =0.8;
double mutationPro = 0.01;
int [][] individual = new int[populationSize][geneSize];
double [] realValue =new double[populationSize];
double [] fitness =new double [50];
double [] fitnessPro =new double [populationSize];
double currentOpt =0;
int currentX =0;
Random random =new Random();
double []max =new double[iterationNum];
public void init(){
for(int i =0;i<populationSize;i++){
for(int j =0;j<geneSize;j++){
if(j == 0)
individual[i][j] =random.nextInt(9);
else
individual[i][j] =random.nextInt(10);
}
}
}
private void CalRealValue(){
for(int i =0;i<populationSize;i++){
realValue[i] =0;
realValue[i]+=individual[i][0];
double decimal = 0;
for(int j =geneSize-1;j>0;j--){
decimal = decimal/10+individual[i][j];
}
realValue[i] += decimal/10;
// System.out.println(realValue[i]+" "+i);
}
}
private void CalFitnessAndFitnessPro(){
double sum =0;
currentOpt =0;
currentX =0;
for(int i =0;i<populationSize;i++){
fitness[i] = realValue[i]+10*Math.sin(5*realValue[i])+7*Math.cos(4*realValue[i])+17;
if(currentOpt<fitness[i]){
currentOpt =fitness[i];
currentX =i;
}
sum+=fitness[i];
}
double section =0;
for(int i =0;i<populationSize;i++){
section +=fitness[i];
fitnessPro[i] = section/sum;
}
}
private void Reproduction(){
int [][] temp =new int [populationSize][geneSize];
//产生交叉
for(int i =0;i<populationSize-1;i=i+2){
int [] father =new int [geneSize];
double pro = random.nextDouble();
for(int j=0;j<populationSize;j++){
if(fitnessPro[j]>=pro){
for(int k =0;k<geneSize;k++)
father[k] = individual[j][k];
break;
}
}
pro =random.nextDouble();
int [] mother =new int [geneSize];
for(int j=0;j<populationSize;j++){
if(fitnessPro[j]>=pro){
for(int k =0;k<geneSize;k++)
mother[k] = individual[j][k];
break;
}
}
double pm = random.nextDouble();
if(pm<crossoverPro){
int changePosition =random.nextInt(geneSize);
for(int j=0;j<geneSize;j++){
if(j<changePosition){
temp[i][j] =father[j];
temp[i+1][j] =mother[j];
}
else {
temp[i][j] = mother[j];
temp[i+1][j] = father[j];
}
}
}
else{
for(int j=0;j<geneSize;j++){
temp[i][j] =father[j];
temp[i+1][j] =mother[j];
}
}
}
for(int i =0;i<geneSize;i++){
individual[populationSize-1][i] = individual[currentX][i];
}
//变异
for(int i =0;i<populationSize-1;i++){
for(int j =0;j<geneSize;j++){
if(random.nextDouble()<mutationPro)
individual[i][j] = random.nextInt(10);
else
individual[i][j] = temp[i][j];
}
}
}
public DecimalGenetic(){
init();
for(int i =0;i<iterationNum;i++){
CalRealValue();
CalFitnessAndFitnessPro();
BigDecimal optTemp =new BigDecimal(currentOpt-17);
optTemp =optTemp.setScale(5, BigDecimal.ROUND_HALF_UP);
System.out.println("第"+i+"代，最大值为："+optTemp+" 对应X是："+realValue[currentX]);
max[i] = currentOpt-17;
Reproduction();
}
}
public double[] getMax(){
return max;
}
public static void main(String[] args) {
DecimalGenetic decimalGenetic =new DecimalGenetic();
}
}
实现和二进制大部分一致，但是在变异部分我用了取随机数这个方法。
五.思考：
关于编码，我在做完之后有一些思考，想和大家分享.我们编码一个数据，用0-1串表示，每一位是没有差别的，但是转换为数字的时候，每一位的权值是不同的。对于真正的自然界，每个性状对于生物的存活几率的影响也是不同的。比如果蝇的翅膀大小和眼色对于它的生存几率的影响是不同的，那反应成我们这里的编码就是位置不同，权重不同.这里算是遗传算法的奇妙之处吧.
下面推荐一个讲述比较完整的博客：https://segmentfault.com/a/1190000004155021