第1页 / 共12页
第2页 / 共12页
第3页 / 共12页
第4页 / 共12页
第5页 / 共12页
第6页 / 共12页
第7页 / 共12页
第8页 / 共12页
遗传算法解决01背包问题分析及代码.docx
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
int generation=200;
const int GR=200;
const
const int gene_num=50;
const
const int CAPACITY=300;
int mate[population_num+1];//存储选择个体的临时数组
double pc=0.9;//144-0.999//52-0.990//144-0.8-0.1//
double pm=0.1;//变异概率//0.1
int c=0;//计数变量
int population_num=2000;//种群数
int goods_num=50;//城市数
typedef struct Goods
{
double weight;
double value;
int gene;
} Goods;
Goods goods[goods_num+1],input_goods[goods_num+1];
typedef struct Population//定义种群（一个解）
{
Goods goods[goods_num+1];//一个解包含 city_num 个城市的信息
double fitness;//适应度
double accumulation_pi;//累积概率
double population_weight;
} Population;
Population population[population_num*3+1];
Population new_population[population_num+1];
Population old_population[population_num+1];
Population t;
queue best;
void Reset()//重置累计概率
{
}
for(int i=1; i<=population_num; i++)
population[i].accumulation_pi=0.0;
void Swap(int &a,int &b)//使用 C++自带函数可能出错
{
int temp;
temp=a;
a=b;
b=temp;
}
void init_population()
{
for(int i=1; i<=population_num; i++)
{
for(int j=1; j<=gene_num; j++)
{
population[i].goods[j].gene=rand()%2;
}
}
for(int i=1;i<=population_num;i++)
{
for(int j=1; j<=gene_num; j++)
{
population[i].goods[j].weight=input_goods[j].weight;
population[i].goods[j].value=input_goods[j].value;
}
}
for(int i=1; i<=population_num; i++)
{
population[i].fitness=0.0;//适应度
//population[i].fitness_pi=0.0;//适应率
population[i].accumulation_pi=0.0;//累积概率
population[i].population_weight=0.0;
}
}
double calculateFitness(Population &a)//种群适应度
{
a.fitness=0;
for(int i=1;i<=gene_num;i++)
{
if(a.goods[i].gene==1)
{
a.fitness+=a.goods[i].value;
}
}
return a.fitness;
}
double calculateWeight(Population &a)//种群适应度
{
a.population_weight=0;
for(int i=1;i<=gene_num;i++)
{
if(a.goods[i].gene==1)
{
a.population_weight+=a.goods[i].weight;
}
}
return a.population_weight;
}
void check_capcity(Population &a,int n)
{
while(a.population_weight>CAPACITY)
{
int idModify = rand()%gene_num;
if(a.goods[idModify].gene==1)
{
a.goods[idModify].gene= 0;
a.population_weight-= a.goods[idModify].weight;
a.fitness-= a.goods[idModify].value;
}
}
}
bool cmp(Population &a,Population &b)//比较原则，不能加"="号，否则可能出现分母为 0 的
错误，且计算时间延长
{
return a.fitness>b.fitness;
}
void sort_population(int n)//对种群根据适应率进行排序
{
sort(population+1,population+population_num*n+1,cmp);
}
void accumulation_rate()//种群累积概率
{
for(int i=1; i<=population_num; i++) //初始化
{
population[i].accumulation_pi=0.0;
}
for(int i=1; i<=population_num; i++)
{
for(int j=1; j<=i; j++)
{
population[i].accumulation_pi+=population[j].fitness;
}
}
//
printf(" 最 后 一 个 个 体 的 累 积 概 率 ：
accumulation_pi :%lf\n",population[population_num].accumulation_pi);
}
int roulette()//轮盘赌——根据累计概率，随机选择一个种群
{
int i;
double sum=0.0;
for(int j=1;j<=population_num;j++)
sum+=population[j].fitness;
r=rand()%t;
int t=(int)sum;
int
for(i=1; i<=population_num; i++)
{
if((population[i].accumulation_pi-r)>=0)
break;
}
return i;
}
void Copy(Population &a,Population &b)//把种群 a 复制给种群 b
{
// b.fitness_pi=a.fitness_pi;
b.fitness=a.fitness;
// b.distance=a.distance;
b.accumulation_pi=a.accumulation_pi;
b.population_weight=a.population_weight;
for(int i=1; i<=goods_num; i++)
{
b.goods[i].weight=a.goods[i].weight;
b.goods[i].value=a.goods[i].value;
b.goods[i].gene=a.goods[i].gene;
}
}
void crossover(Population &a,Population &b)//种群 a 和 b 进行交叉遗传
{
int k1=1+rand()%(gene_num/2);
int k2=k1+rand()%(gene_num/2);
for(int i=k1; i<=k2; i++) //交换中间段
{
Swap(a.goods[i].gene,b.goods[i].gene);
}
int t1[gene_num+1],t2[gene_num+1];//记录出现次数的两个临时数组
memset(t1,0,sizeof(t1));
memset(t2,0,sizeof(t2));
for(int i=1; i<=gene_num; i++)
{
t1[a.goods[i].gene]++;
t2[b.goods[i].gene]++;
}
for(int i=1; i<=gene_num; i++)
{
if(ik2)
{
if(t1[a.goods[i].gene]>1)//某个序号出现的次数大于 1
{
for(int j=1; j<=gene_num; j++)
{
if(jk2)
{
if(t2[b.goods[j].gene]>1)
{
Swap(a.goods[i].gene,b.goods[j].gene);
break;//////缺少会导致一直交换，出现一个种群中出现只有
}
}
}
一个个体的情况
}
}
}
}
void crossover_all()//所有种群之间进行交叉遗传
{
int t=(int)(population_num*pc);
// for(int i=t; i>=1; i--)
for(int i=1;i<=t;i++)
{
// (population[i],population[population_num/2+i]);
crossover(population[i],new_population[i]);////////////////////
}
}
void mutation_new()
{
for(int i=1; i<=population_num; i++)
{
double r=0.0;
//r=rand()/(double)RAND_MAX;
r=(double)(rand()%100/101.0);
if(r-pm<=0)//随机数大于变异概率——可以进行变异操作*/
{
for(int j=1; j<=7; j++) //交换等位基因
{
int k1=1+rand()%(gene_num/2);//记得加括号
int k2=k1+rand()%(gene_num/2);
Swap(new_population[i].goods[k1].gene,new_population[i].goods[k2].gene);
}
}
}
}
void inverse_mutation(Population &a)//倒位变异算子
{
double r=0.0;
//r=rand()/(double)RAND_MAX;
r=(double)(rand()%100/101.0);
if(r-pm<=0)//随机数大于变异概率
{
int k1=1+rand()%gene_num;
int k2=1+rand()%gene_num;
if(k1>k2)
Swap(k1,k2);
if(k2-k1<1)
return;
for(int i=k1+1; i<=(k2-k1)/2; i++) //要进行这么多次翻转
{
Swap(a.goods[i].gene,a.goods[k2-1-(i-(k1+1))].gene);
}
int t=a.goods[k2].gene;
for(int i=k2-1; i>=k1+1; i--)
{
a.goods[i+1].gene=a.goods[i].gene;
}
a.goods[k1+1].gene=t;
}
}
void inovation(Population &a)
{
Copy(a,t);//
int k1=1+rand()%gene_num;
int k2=1+rand()%gene_num;
if(k1>k2)
Swap(k1,k2);
if(k2-k1<1)
return;
for(int i=k1+1; i<=(k2-k1)/2; i++) //要进行这么多次翻转
{
Swap(t.goods[i].gene,t.goods[k2-1-(i-(k1+1))].gene);
}
calculateFitness(t);
if(a.fitness7) {c2++;c1=1;}
//population[i].fitness_pi=flag[c2];
}
{
}
if(population[i].fitness_pi!=population[i-1].fitness_pi)//适应度相同//适应度不同
c2++;
// population[i].fitness_pi=flag[c2];
population[i].fitness_pi=flag[c2];
}
adaptation_rate2();
sort_population2();
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
