遗传算法背包问题

1. 如何通俗易懂地解释遗传算法

遗传算法，核心是达尔文优胜劣汰适者生存的进化理论的思想。

我们都知道一个种群，通过长时间的繁衍，种群的基因会向着更适应环境的趋势进化，牛B个体的基因被保留，后代越来越多，适应能力低个体的基因被淘汰，后代越来越少。经过几代的繁衍进化，留下来的少数个体，就是相对能力最强的个体了。

那么在解决一些问题的时候，我们能不能学习这样的思想，比如先随机创造很多很多的解，然后找一个靠谱的评价体系，去筛选比较好的解，再用这些好的解像生小宝宝一样生一堆可能更好的解，然后再筛再生，反复弄个几代，得到的说不定就是近似最优解哟

说干就干，有一个经典组合问题叫“背包问题”，我们拿这种思路来试试

“背包问题（Knapsack Problem）是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。”

这个问题的衍生简化问题“0-1背包问题” 增加了限制条件：每件物品只有一件，可以选择放或者不放，更适合我们来举例

这样的问题如果数量少，当然最好选择穷举法

比如一共3件商品，用0表示不取，1表示取，那么就一共有

000 001 010

011 100 101

110 111

这样方案，然后让计算机去累加和，与重量上限比较，留下来的解里取最大即可。

2. 如何用遗传算法求解多重背包问题

遗传算法将目标函数转换为适应度函数，评估，复制，交叉，变异种群中的个体，并从中选出适应性最强的个体，算法的最优解就是这个个体。具体流程是：1.初始种群的产生。2.适应度函数的构造。3.选择和繁殖。4.终止条件。

3. 遗传算法的一个问题

先在0到5中任选n个数,在将着n 个数转换成二进制,然后存进一个数组A.定义一个函数f(x)(就是求x的四次方).定义循环次数为20次(可以自选).
1).计算A中每个数的函数制.(按十进制)
2).如果次数超过20,则取数组中最大的就是结果,算法结束.
3).以一定概率选 A中k个最大的复制后加入数组,在删除一些最小的,形成
数组A'
4).以一定概率选A'中若干二进制数进行交叉(既两两某些位互换),形成新
数组A''
5).以一定概率选A''中若干二进制数进行变异(即某些数的一些位发生反转),
形成新数组A'''
6).将A'''做为A,转步骤2.

4. 遗传算法可以解决什么问题

遗传算法的应用比较广泛，可用于解决数值优化、组合优化、机器学习、智能控制、人工生命、图像处理、模式识别等领域的问题。比较具体多是：函数最值问题、旅行商问题、背包问题、车辆路径问题、生产排程问题、选址问题等。

5. 怎么使用遗传算法解决背包问题

楼主，能给点悬赏分吗？给的话，我帮你找找程序。

6. 遗传算法具体应用

1、函数优化

函数优化是遗传算法的经典应用领域，也是遗传算法进行性能评价的常用算例，许多人构造出了各种各样复杂形式的测试函数：连续函数和离散函数、凸函数和凹函数、低维函数和高维函数、单峰函数和多峰函数等。

2、组合优化

随着问题规模的增大，组合优化问题的搜索空间也急剧增大，有时在目前的计算上用枚举法很难求出最优解。对这类复杂的问题，人们已经意识到应把主要精力放在寻求满意解上，而遗传算法是寻求这种满意解的最佳工具之一。

此外，GA也在生产调度问题、自动控制、机器人学、图象处理、人工生命、遗传编码和机器学习等方面获得了广泛的运用。

3、车间调度

车间调度问题是一个典型的NP-Hard问题，遗传算法作为一种经典的智能算法广泛用于车间调度中，很多学者都致力于用遗传算法解决车间调度问题，现今也取得了十分丰硕的成果。

从最初的传统车间调度（JSP）问题到柔性作业车间调度问题（FJSP），遗传算法都有优异的表现，在很多算例中都得到了最优或近优解。

(6)遗传算法背包问题扩展阅读：

遗传算法的缺点

1、编码不规范及编码存在表示的不准确性。

2、单一的遗传算法编码不能全面地将优化问题的约束表示出来。考虑约束的一个方法就是对不可行解采用阈值，这样，计算的时间必然增加。

3、遗传算法通常的效率比其他传统的优化方法低。

4、遗传算法容易过早收敛。

5、遗传算法对算法的精度、可行度、计算复杂性等方面，还没有有效的定量分析方法。

7. 什么是遗传算法

遗传算法是模拟自然界中按“优胜劣汰”法则进行进化过程而设计的算法。Bagley和Rosengerg于1967年在他们的博士论文中首先提出了遗传算法的概念。1975年Holland出版的专着奠定了遗传算法的理论基础。如今遗传算法不但给出了清晰的算法描述，而且也建立了一些定量分析的结果，在众多领域得到了广泛的应用，如用于控制(煤气管道的控制)、规划(生产任务规划)、设计(通信网络设计)、组合优化(TSP问题、背包问题)以及图像处理和信号处理等。

8. 遗传算法求解背包问题的程序

1楼的不是遗传算法吧！
刚好做过这个遗传算法解背包问题的论文，给你回答啦~~独家哦，分数要给偶~~

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;

//一个种群中最大和最小适应度的个体
int minpop,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=0;j<lchrom;j++)
{
fscanf(fp,"%d",&profit[j]);
}
//读入物体重量信息
for (j=0;j<lchrom;j++)
{
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=0;j<lchrom;j++)
{
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=0;j<lchrom;j++)
{
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=1;i<popsize;i++)
{
//计算种群的总适应度
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=0;j<lchrom;j++)
{
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=0;i<popsize;i++)
{
while (!ispop)
{
for(j=0;j<lchrom;j++)
{
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=0;j<=cross_pos;j++)
{ //保留复制；
//包括在概率选择不成功时，父体完全保留
newpop[i].chrom[j]=parent1[j];
}
for(j=cross_pos+1;j<=(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=0;j<lchrom;j++)
{
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=0;k<lchrom;k++)
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();
}

9. 求助基于遗传算法的多选择背包问题matlab程序

目标函数是使得资源均衡，满足工序的合适开始时间即基因值
，困难是基因值不体现在目标函数的显式表达式中，而是在约束条件中，不知道怎么处理？
如果有哪位虫友感兴趣并愿意提供帮助，将不胜感激！