关于遗传算法：
读完知乎上一篇关于遗传算法的介绍，感觉确实挺有意思的，于是决定写一个程序应用一下试试。
首先重新回忆一下高中生物知识：
判断一个图和最优解的接近程度（选择函数）：对于该图，不断向该图中所含水滴数最多的格子内添水，直到该图水滴
数为0时停止，记录该办法所添加的水滴数。
第一代：随机向图中几个格加点儿水。
杂交：从上一代中随机取出两组，用随机函数将他们分成新的两组。得到的新的两组，如果有一步是要向一个空格子内
添加水滴，那么这一步绝对没好处，所以在这时我选择违背自然规律删掉这一步，从而得到一个更好的子代。
选择：用选择函数，让离最优解越远的选择方法出现的概率越少。
变异：自认为很重要，因为它可以引入新的可能性。因为之前所有的操作都只会减少操作步数，不会使操作步数增加，
所以我决定随机添加操作步数模拟变异。所以对于每一组，都有百分之x的可能性在该组后面再添加一步操作。
代码：
//十滴水，启发式算法
/*-------------------------------------------------------------------------------------------------------- 读完知乎上一篇关于遗传算法的介绍，感觉确实挺有意思的，于是决定写一个程序应用一下试试。 首先重新回忆一下高中生物知识： 判断一个图和最优解的接近程度（选择函数）：对于该图，不断向该图中所含水滴数最多的格子内添水，直到该图水滴 数为0时停止，记录该办法所添加的水滴数。 第一代：随机向图中几个格加点儿水。 杂交：从上一代中随机取出两组，用随机函数将他们分成新的两组。得到的新的两组，如果有一步是要向一个空格子内 添加水滴，那么这一步绝对没好处，所以在这时我选择违背自然规律删掉这一步，从而得到一个更好的子代。 选择：用选择函数，让离最优解越远的选择方法出现的概率越少。 变异：自认为很重要，因为它可以引入新的可能性。因为之前所有的操作都只会减少操作步数，不会使操作步数增加， 所以我决定随机添加操作步数模拟变异。所以对于每一组，都有百分之x的可能性在该组后面再添加一步操作。 --------------------------------------------------------------------------------------------------------*/
#include<bits/stdc++.h>
/*#include<iostream> #include<math.h> #include<stdio.h> #include<vector> #include<stdlib.h> #include<time.h> #include<string.h> #include<algorithm>*/
using namespace std;
const int GENERATION=100;//培育代数
const int UNIT_NUM=1000;//每代培育个数
int step_unit_num[36*4]={0};//step_unit_num[i]=x表示适应函数值为 i 的个体个数为 x
int my_map[6][6];//储存原地图
struct ADD_STEP//在某一点增加水滴（模拟基因）
{
int x;int y;
};
struct UNIT//由若干个有序基因组成的个体（模拟生物）
{
vector<ADD_STEP>gene;
//int fit;//描述生物的适应程度
};
UNIT unit[UNIT_NUM];
UNIT unit_2[UNIT_NUM];
UNIT best;
ADD_STEP my_way[36];
bool Unit_cmp(UNIT x , UNIT y)
{
return x.gene.size()<y.gene.size();
}
bool Map_empty( int (*m)[6] )
{
for(int i=0;i<6;i++)
{
for(int j=0;j<6;j++)
{
if(m[i][j]!=0)return 0;
}
}
return 1;
}
void Init()//用一种我觉得比较好的顺序来加水。设置搜索路径基本思路：从中间到两边。
{
my_way[0].x=3;my_way[0].y=3; my_way[1].x=3;my_way[1].y=4; my_way[2].x=4;my_way[2].y=3;
my_way[3].x=4;my_way[3].y=4; my_way[4].x=2;my_way[4].y=3; my_way[5].x=5;my_way[5].y=4;
my_way[6].x=3;my_way[6].y=5; my_way[7].x=4;my_way[7].y=2; my_way[8].x=5;my_way[8].y=3;
my_way[9].x=4;my_way[9].y=5; my_way[10].x=3;my_way[10].y=2; my_way[11].x=2;my_way[11].y=4;
my_way[12].x=2;my_way[12].y=5; my_way[13].x=5;my_way[13].y=5; my_way[14].x=5;my_way[14].y=2;
my_way[15].x=2;my_way[15].y=2; my_way[16].x=1;my_way[16].y=3; my_way[17].x=6;my_way[17].y=4;
my_way[18].x=4;my_way[18].y=1; my_way[19].x=3;my_way[19].y=6; my_way[20].x=4;my_way[20].y=6;
my_way[21].x=3;my_way[21].y=1; my_way[22].x=6;my_way[22].y=3; my_way[23].x=1;my_way[23].y=4;
my_way[24].x=1;my_way[24].y=5; my_way[25].x=6;my_way[25].y=2; my_way[26].x=1;my_way[26].y=2;
my_way[27].x=5;my_way[27].y=6; my_way[28].x=6;my_way[28].y=5; my_way[29].x=2;my_way[29].y=6;
my_way[30].x=2;my_way[30].y=1; my_way[31].x=5;my_way[31].y=1; my_way[32].x=6;my_way[32].y=1;
my_way[33].x=6;my_way[33].y=6; my_way[34].x=1;my_way[34].y=6; my_way[35].x=1;my_way[35].y=1;
}
void Boom(int (*m)[6] , int x , int y)//坐标（x，y）爆炸！
{
m[x][y]=0;
int lx=x,ly=y;
while(1)
{
lx--;
if(lx<0)break;
if(m[lx][ly]!=0)
{
m[lx][ly]++;
if(m[lx][ly]>4)
{
Boom(m,lx,ly);
}
break;
}
}
lx=x;
while(1)
{
lx++;
if(lx>=6)break;
if(m[lx][ly]!=0)
{
m[lx][ly]++;
if(m[lx][ly]>4)
{
Boom(m,lx,ly);
}
break;
}
}
lx=x;
while(1)
{
ly--;
if(ly<0)break;
if(m[lx][ly]!=0)
{
m[lx][ly]++;
if(m[lx][ly]>4)
{
Boom(m,lx,ly);
}
break;
}
}
ly=y;
while(1)
{
ly++;
if(ly>=6)break;
if(m[lx][ly]!=0)
{
m[lx][ly]++;
if(m[lx][ly]>4)
{
Boom(m,lx,ly);
}
break;
}
}
}
void Add_map(int (*m)[6], int x , int y)//对一个图的（x，y）位置添加一滴水之后得到的新图
{
m[x][y]++;
if(m[x][y]>4)Boom(m,x,y);
}
ADD_STEP Find_way( int (*m)[6] )
{
for(int i=4;i>0;i--)
{
for(int j=0;j<36;j++)
{
if(m[my_way[j].x][my_way[j].y]==i)return my_way[j];
}
}
}
void Fit_step(int (*m)[6] , UNIT & this_unit)//找出地图的适应程度，并且补全余剩走法
{
int test_map[6][6];
for(int i=0;i<6;i++)
{
for(int j=0;j<6;j++)
{
test_map[i][j]=m[i][j];
}
}
for(int i=0;i<this_unit.gene.size();i++)
{
if(Map_empty(test_map))
{
while(this_unit.gene.size()!=i)
{
this_unit.gene.pop_back();
}
break;
}
Add_map( test_map , this_unit.gene[i].x , this_unit.gene[i].y );
}
while(!Map_empty(test_map))
{
this_unit.gene.push_back( Find_way(test_map) );
//this_unit.fit++;
Add_map( test_map , this_unit.gene[this_unit.gene.size()-1].x , this_unit.gene[this_unit.gene.size()-1].y );
}
//cout<<this_unit.gene.size()<<" ";
}
/*------------------------------------------------------------------------------------------------------ 初代种群每个生物基因组成为：首先随机产生3个有序位置，然后使用补全走法。 注意这里可能会出现bug，因为如果随机产生的两个正好可以消去所有的水滴，那么生成随机数的循环将无法跳出。 -------------------------------------------------------------------------------------------------------*/
void Produce_first()//产生初代种群
{
memset(step_unit_num,0,sizeof(step_unit_num));
srand( (unsigned)time( NULL ) );
for(int i=0;i<UNIT_NUM;i++)
{
/*int test_map[6][6]; for(int j=0;j<6;j++) { for(int k=0;k<6;k++) { test_map[j][k]=my_map[j][k]; } }*/
for(int j=0;j<3;j++)//假设初代每个个体基因数为3
{
ADD_STEP k;
k.x=rand()%6;k.y=rand()%6;
//cout<<k.x<<k.y<<endl;
unit[i].gene.push_back(k);
}
Fit_step( my_map , unit[i] );
//if(unit[i].gene.size()<3)cout<<unit[i].gene.size()<<" ";
step_unit_num[unit[i].gene.size()]++;
if(best.gene.size()>unit[i].gene.size())
{
best=unit[i];
}
}
sort(unit,unit+UNIT_NUM,Unit_cmp);
}
/*------------------------------------------------------------------------------------------------------*/
/*-------------------------------------------------------------------------------------------------------- 选择函数：保证了每一个适应值为 x 的生物存活的几率为适应值为 x+1 的生物的存活几率的 2 倍。 ----------------------------------------------------------------------------------------------------------*/
int choose()
{
int S=UNIT_NUM;
int K=0;
for(int i=0;i<GENERATION;i++)
{
for(int j=1;j<=36*4;j++)
{
int x=rand()%(S+step_unit_num[j]);
if(x<step_unit_num[j]*2)
{
return x/2+K;
}
K+=step_unit_num[j];
S-=step_unit_num[j];
}
}
}
/*-------------------------------------------------------------------------------------------------------- 交配： --------------------------------------------------------------------------------------------------------*/
void Born()//让编号为 x 的生物和编号为 y 的生物交配，产生两个新个体。
{
int x,y;
for(int i=0;i<UNIT_NUM;i+=2)//假定种群数量为偶数
{
x=choose();
y=choose();
//cout<<x<<" "<<y<<endl;
/*---------------------------------------生成第一个生物--------------------------------------------------*/
for(int j=0;j<(unit[x].gene.size()+1)/2;j++)//这里如果是奇数，那么将会多取一个
{
unit_2[i].gene.push_back(unit[x].gene[j]);
}
for(int j=0;j<(unit[y].gene.size()+1)/2;j++)//这里如果是奇数，那么将会多取一个
{
unit_2[i].gene.push_back(unit[y].gene[j+unit[y].gene.size()/2]);
}
/*--------------------------------------------------------------------------------------------------------*/
/*---------------------------------------生成第二个生物--------------------------------------------------*/
for(int j=0;j<(unit[y].gene.size()+1)/2;j++)//这里如果是奇数，那么将会多取一个
{
unit_2[i+1].gene.push_back(unit[y].gene[j]);
}
for(int j=0;j<(unit[x].gene.size()+1)/2;j++)//这里如果是奇数，那么将会多取一个
{
unit_2[i+1].gene.push_back(unit[x].gene[j+unit[x].gene.size()/2]);
}
/*--------------------------------------------------------------------------------------------------------*/
/*------------------------------------------基因突变------------------------------------------------------*/
if(rand()%1000==1)
{
ADD_STEP l;
l.x=rand()%6;
l.y=rand()%6;
unit_2[i+rand()%2].gene.push_back(l);
}
/*--------------------------------------------------------------------------------------------------------*/
Fit_step(my_map,unit_2[i]);
Fit_step(my_map,unit_2[i+1]);
}
memset(step_unit_num,0,sizeof(step_unit_num));
for(int i=0;i<UNIT_NUM;i++)
{
unit[i]=unit_2[i];
step_unit_num[unit[i].gene.size()]++;
if(best.gene.size()>unit[i].gene.size())
{
best=unit[i];
cout<<best.gene.size()<<endl;
}
}
sort(unit,unit+UNIT_NUM,Unit_cmp);
}
void Input()
{
for(int i=0;i<6;i++)
{
for(int j=0;j<6;j++)
{
cin>>my_map[i][j];
}
}
}
void Output()
{
for(int i=0;i<best.gene.size();i++)
{
cout<<best.gene[i].x+1<<" "<<best.gene[i].y+1<<endl;
}
}
int main()
{
Init();
Input();
Fit_step(my_map,best);
cout<<best.gene.size()<<endl;
Produce_first();
for(int i=0;i<GENERATION;i++)
{
Born();
cout<<i<<" "<<best.gene.size()<<endl;
}
cout<<best.gene.size()<<endl;
Output();
}
京公网安备 11010502036488号