刚好做过这个遗传算法解背包问题的论文，给你回答啦~~独家哦，分数要给偶~~
1、程序开发环境
开发环境：Visual C++6.0 (把Fortran程序改为VC)
*** 作系统：Windows 2003 Professional
2、程序性能对比
运行时间与加速比（如表1所示）
进程数p（个） 1 2 4
运行时间t（秒） 129s 78s 38s
加速比s 1.65 3.38
表1、运行时间与加速比
3、程序运行结果：
实例数据：
假设物体的重量Weight、物体的收益Profit和背包的容量Contain 分别为：
Weight={ 80，82，85，70，72，70，66，50，55，25 ，
50，55，40，48，50， 32，22，60，30，32 ，
40，38，35，32，25， 28，30，22，50，30 ，
45，30，60，50，20 ，65，20，25，30，10 ，
20，25，15，10，10 ，10，4， 4， 2， 1 }
Profit={ 220，208，198，192，180，180，165，162，160，158，
155，130，125，122，120 ， 118，115，110，105，101，
100，100，98， 96， 95， 90， 88， 82， 80， 77 ，
75， 73， 72， 70， 69， 66， 65， 63， 60， 58，
56， 50， 30， 20， 15， 10， 8， 5， 3， 1}
Contain=1000，
如何选择哪些物品装入该背包可使得在背包的容量约束限制之内所装物品的总价值最大?
传统的算法（动态规划、递归回溯法和贪心算法所得结果：
总价值为3077 , 总重量为999。
2001年张铃，张钹教授在计算机学报上发表的《佳点集遗传算法》所得结果
总价值为3103, 总重量为1000。梁首
我们算法所得结果： 总价值为3103, 总重量为1000。
我们所求得最优解的个体分配情况为：
11010 10111 10110 11011 01111 11101 00001 01001 10000
01000
算法 最大迭代次数 总价值为 总重量为
传统的算法 400 3077 999
佳点集算法 70 3103 1000
遗传算法75 3103 1000
// knapsack.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <AfxWin.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <conio.h>
#include <stdio.h>
// 重要常量参数
#define popsize 200 //种群的规模
#define pc 0.618/橡兄数/杂交概率
#define pm 0.03//变异概率
#define lchrom 50 //染色体长度
#define maxgen 1000 //最大进化代数尘侍
struct population
{
unsigned int chrom[lchrom] //染色体
double weight //背包重量
double fitness //适应度
unsigned int parent1,parent2,cross //双亲、交叉点
}
//新生代种群、父代种群
struct population oldpop[popsize],newpop[popsize]
//背包问题中物体重量、收益、背包容量
int weight[lchrom],profit[lchrom],contain
//种群的总适应度、最小、最大、平均适应度
double sumfitness,minfitness,maxfitness,avgfitness
//计算适应度时使用的 惩罚函数系数
double alpha
//一个种群中最大和最小适应度的个体
intminpop,maxpop
/* 读入背包信息,并且计算惩罚函数系数 */
void read_infor()
{
FILE *fp
int j
//获取背包问题信息文件
if ((fp=fopen("knapsack.txt","r"))==NULL)
{
//读取文件失败
AfxMessageBox("The file is not found",MB_OK,NULL)
return
}
//读入物体收益信息
for (j=0j<lchromj++)
{
fscanf(fp,"%d",&profit[j])
}
//读入物体重量信息
for (j=0j<lchromj++)
{
fscanf(fp,"%d",&weight[j])
}
//读入背包容量
fscanf(fp,"%d",&contain)
fclose(fp)
}
//根据计算的个体重量,判断此个体是否该留在群体中
double cal_weight(unsigned int *chr)
{
int j
double pop_weight//背包重量
pop_weight=0
for (j=0j<lchromj++)
{
pop_weight=pop_weight+(*chr)*weight[j]
chr++
}
return pop_weight
}
/* 种群中个体适应度计算*/
double cal_fit(unsigned int *chr)
{
int j
double pop_profit//适应度
pop_profit=0
// pop_weight=0
for (j=0j<lchromj++)
{
pop_profit=pop_profit+(*chr)*profit[j]
// pop_weight=pop_weight+(*chr)*weight[j]
chr++
}
return pop_profit
}
/* 群体适应度的最大最小值以及其他信息 */
void statistics(struct population *pop)
{
int i
double tmp_fit
sumfitness=pop[0].fitness
minfitness=pop[0].fitness
minpop=0
maxfitness=pop[0].fitness
maxpop=0
for (i=1i<popsizei++)
{
//计算种群的总适应度
sumfitness=sumfitness+pop[i].fitness
tmp_fit=pop[i].fitness
//选择种群中最大适应度的个体
if ((tmp_fit>maxfitness)&&((int)(tmp_fit*10)%10==0))
{
maxfitness=pop[i].fitness
maxpop=i
}
//选择种群中最小适应度的个体
if (tmp_fit<minfitness)
{
minfitness=pop[i].fitness
minpop=i
}
//计算平均适应度
avgfitness=sumfitness/(float)popsize
}
// printf("\nthe max pop = %d",maxpop)
// printf("\nthe min pop = %d",minpop)
// printf("\nthe sumfitness = %f\n",sumfitness)
}
//报告种群信息
void report(struct population *pop,int gen)
{
int j
int pop_weight=0
printf("the generation is %d.\n",gen)//输出种群的代数
//输出种群中最大适应度个体的染色体信息
printf("The population's chrom is: \n")
for (j=0j<lchromj++)
{
if (j%5==0)
{ printf(" ")}
printf("%1d",pop[maxpop].chrom[j])
}
//输出群体中最大适应度
printf("\nThe population's max fitness is %d.",(int)pop[maxpop].fitness)
printf("\nThe knapsack weight is %d.\n\n",(int)pop[maxpop].weight)
}
/* 生成初始种群 */
void initpop()
{
int i,j,ispop
double tmpWeight
//变量用于判断是否为满足条件的个体
ispop=false
//生成popsize个种群个体
for(i=0i<popsizei++)
{
while (!ispop)
{
for(j=0j<lchromj++)
{
oldpop[i].chrom[j]=rand()%2 //随机生成个体的染色体
oldpop[i].parent1=0 //双亲
oldpop[i].parent2=0
oldpop[i].cross=0 //交叉点
}
//选择重量小于背包容量的个体,即满足条件
tmpWeight=cal_weight(oldpop[i].chrom)
if (tmpWeight<=contain)
{
oldpop[i].fitness=cal_fit(oldpop[i].chrom)
oldpop[i].weight=tmpWeight
oldpop[i].parent1=0
oldpop[i].parent2=0
oldpop[i].cross=0
ispop=true
}
}
//此个体可以加入到种群中
ispop=false
}
}
/* 遗传 *** 作 */
//概率选择试验
int execise(double probability)
{
double pp
//如果生成随机数大于相应的概率则返回真，否则试验不成功
pp=(double)(rand()%20001/20000.0)
if (pp<=probability) return 1
return 0
}
// 选择进行交叉 *** 作的个体
int selection(int pop)
{
double wheel_pos,rand_Number,partsum
int parent
//赌轮法选择
rand_Number=(rand()%2001)/2000.0
wheel_pos=rand_Number*sumfitness //赌轮大小
partsum=0
parent=0
do{
partsum=partsum+oldpop[parent].fitness
parent=parent+1
} while (partsum<wheel_pos &&parent<popsize)
return parent-1
}
/* 交叉 *** 作 */
int crossover(unsigned int *parent1,unsigned int *parent2,int i)
{
int j,cross_pos
if (execise(pc))
{
//生成交叉位置0,1,...(lchrom-2)
cross_pos=rand()%(lchrom-1)
}
else cross_pos=lchrom-1
for (j=0j<=cross_posj++)
{ //保留复制；
//包括在概率选择不成功时，父体完全保留
newpop[i].chrom[j]=parent1[j]
}
for(j=cross_pos+1j<=(lchrom-1)j++)
{
//从交叉点开始交叉
newpop[i].chrom[j]=parent2[j]
}
//记录交叉位置
newpop[i].cross=cross_pos
return 1
}
/* 变异 *** 作 */
int mutation(unsigned int alleles)
{
if (execise(pm))
{
if (alleles)
alleles=0
else alleles=1
}
//返回变异值，或者返回原值
return alleles
}
/* 群体更新 */
void generation()
{
unsigned int i,j,mate1,mate2
double tmpWeight
int ispop//记录是否是符合条件的个体
i=0
while (i<popsize)
{
ispop=false
while (!ispop)
{
//选择
mate1=selection(i)
mate2=selection(i+1)
//交叉
crossover(oldpop[mate1].chrom,oldpop[mate2].chrom,i)
//变异
for (j=0j<lchromj++)
{
newpop[i].chrom[j]=mutation(newpop[i].chrom[j])
}
//选择重量小于背包容量的个体,即满足条件
tmpWeight=cal_weight(newpop[i].chrom)
if (tmpWeight<=contain)
{
newpop[i].fitness=cal_fit(newpop[i].chrom)
newpop[i].weight=tmpWeight
newpop[i].parent1=mate1
newpop[i].parent2=mate2
ispop=true
}
}
//此个体可以加入到种群中
i=i+1
}
}
void main(int argc, char* argv[])
{
int gen,oldmaxpop,k
double oldmax
read_infor()//读入背包信息
gen=0
srand( (unsigned)time( NULL ) )//置随机种子
initpop()
memcpy(&newpop,&oldpop,popsize*sizeof(struct population))
statistics(newpop)//统计新生种群的信息
report(newpop,gen)
while(gen<maxgen)
{
gen=gen+1
if (gen%100==0)
{
srand( (unsigned)time( NULL ) )//置随机种子
}
oldmax=maxfitness
oldmaxpop=maxpop
generation()
statistics(newpop)//统计新生代种群信息
//如果新生代种群中个体的最大适应度小于老一代种群
//个体的最大适应度，则保存老一代种群个体的最大适应度
//否则报告新生代的最大适应度
if (maxfitness<oldmax)
{
for(k=0k<lchromk++)
newpop[minpop].chrom[k]=oldpop[oldmaxpop].chrom[k]
newpop[minpop].fitness=oldpop[oldmaxpop].fitness
newpop[minpop].parent1=oldpop[oldmaxpop].parent1
newpop[minpop].parent2=oldpop[oldmaxpop].parent2
newpop[minpop].cross=oldpop[oldmaxpop].cross
statistics(newpop)
}
else if (maxfitness>oldmax)
{
report(newpop,gen)
}
//保存新生代种群的信息到老一代种群信息空间
memcpy(&oldpop,&newpop,popsize*sizeof(struct population))
}
printf("It is over.")
getch()
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）