算法是通法

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

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();
}

Ⅱ 何谓算法算法有什么性质

算法（algorithm），在数学（算学）和计算机科学之中，为任何一系列良定义的具体计算步骤，常用于计算、数据处理和自动推理。作为一个有效方法，算法被用于计算函数，它包含了一系列定义清晰的指令，并可于有限的时间及空间内清楚的表述出来。

特点：

1、输入：一个算法必须有零个或以上输入量。

2、输出：一个算法应有一个或以上输出量，输出量是算法计算的结果。

3、明确性：算法的描述必须无歧义，以保证算法的实际执行结果是精确地符合要求或期望，通常要求实际运行结果是确定的。

4、有限性：依据图灵的定义，一个算法是能够被任何图灵完备系统模拟的一串运算，而图灵机只有有限个状态、有限个输入符号和有限个转移函数（指令）。而一些定义更规定算法必须在有限个步骤内完成任务。

5、有效性：又称可行性。能够实现，算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。

(2)算法是通法扩展阅读：

常用设计模式

完全遍历法和不完全遍历法：在问题的解是有限离散解空间，且可以验证正确性和最优性时，最简单的算法就是把解空间的所有元素完全遍历一遍，逐个检测元素是否是我们要的解。

这是最直接的算法，实现往往最简单。但是当解空间特别庞大时，这种算法很可能导致工程上无法承受的计算量。这时候可以利用不完全遍历方法——例如各种搜索法和规划法——来减少计算量。

1、分治法：把一个问题分割成互相独立的多个部分分别求解的思路。这种求解思路带来的好处之一是便于进行并行计算。

2、动态规划法：当问题的整体最优解就是由局部最优解组成的时候，经常采用的一种方法。

3、贪心算法：常见的近似求解思路。当问题的整体最优解不是（或无法证明是）由局部最优解组成，且对解的最优性没有要求的时候，可以采用的一种方法。

4、简并法：把一个问题通过逻辑或数学推理，简化成与之等价或者近似的、相对简单的模型，进而求解的方法。

Ⅲ 算法有什么用

问题一：提问！算法到底有什么用啊！ 学了数据结构了以后，就算偶们不说你也会知道算法的重要。。。。
咱举个非常简单的例子，编一个比较n个数的大小并排列，但是用一般法、冒泡法、折半法.....各种不一样的算法效率是不一样的。

详情还是请仔细翻阅《数据结构》并把指针之类重要的内容全部搞清楚.....

做学问切勿心急，欲速而不达~~~~

问题二：在计算机中算法有什么作用？ 一个程序的核心在于算法。比如说打开一个软件和运行一个软件的速度在计算机硬件性能相同情况下，软件的算法畅到了几近决定性作用，所有的计算机软件和硬件的编程都是需要算法的，就算一个hello world程序虽然我们编时候没有用到算法但是在编译他和运行再屏幕显示的时候就是算法了。算法是计算机乃至自然界的核心，如果知道人脑的算法，就可以制造出人工智能的软件。

问题三：编程算法有什么用？ 研究学习别人的算法，能够让你散搏站在巨人的肩膀上思考问题。其实我们身边无时不刻都在接触算法，一方面提高自身思考的能力，一方面可以提升代码质量。
好的算法不是晦涩难懂的，而是能够让人拍手称奇的。

希望我的回答能对你有些许帮助，谨祝你成功！

问题四：学算法分析到底有什么用？ 其实你都说明白了，研究更高效的算法就是为了节省时间。你学过数值分析么？你知道如过没有高效的算法,就按照矩阵的定义,来求20X20的矩阵,目前的电脑要算到地老天荒的。
API是哪来储？你写的那个能被sun采纳么？如果都不研究排序算法,那么写出来的代码岂不跟你无异？

云，听说过吧？现在处理的数字,运算量已经超过了你的想象。一网络为例，每一天都处理的数据都是海量的，你要查个东西,没几秒就出来了，那不研究算法,能行么。？

尤其是现在，数据越来越大，越来越多，算法就显得尤为重要了。

研究算法，其实是锻炼自己的思维。一个问题有不同的解决方式。当你碰到一个新的事物，你有可能写得出算法,单不一定能写得出代码。./question/422543292?oldq=1比如这个，我就是像想到算法的乎掘团。

而且,敲代码技术含量本身就不高，孰能生巧的过程。

问题五：研究计算机算法对于编程有什么作用？ 让我来告诉你，算法通俗意义上来讲――就是解决一个问题的方法。据此而论，编写程序解决的任何一个问题都可以岁橘叫做算法。狭义上来讲研究算法就是在使用相同的计算资源的并解决同一个问题的情况下怎么样可以更加的节约资源，也就是说使计算速度更快。
拿一个例子来讲就是排序，我们现在了解到的算法有：冒泡，快速，插入，堆排序等等很多，在不同的输入数据规模的情况下采用不同的算法，因为可以节约计算资源。

问题六：学算法有什么用 其实你都说明白了，研究更高效的算法就是为了节省时间。你学过数值分析么？你知道如过没有高效的算法,就按照矩阵的定义,来求20X20的矩阵,目前的电脑要算到地老天荒的。
API是哪来的？你写的那个能被sun采纳么？如果都不研究排序算法,那么写出来的代码岂不跟你无异？

云，听说过吧？现在处理的数字,运算量已经超过了你的想象。一网络为例，每一天都处理的数据都是海量的，你要查个东西,没几秒就出来了，那不研究算法,能行么。？

尤其是现在，数据越来越大，越来越多，算法就显得尤为重要了。

研究算法，其实是锻炼自己的思维。一个问题有不同的解决方式。当你碰到一个新的事物，你有可能写得出算法,单不一定能写得出代码。./question/422543292?oldq=1比如这个，我就是像想到算法的。

而且,敲代码技术含量本身就不高，孰能生巧的过程。

问题七：算法与编程有什么关系? 算法是通过编程来体现的

问题八：竖式计算有什么作用 竖式的沿革没有典籍记载 我国古代数学以计算为主,取得了十分辉煌的成就.其中十进位值制记数法、筹算和珠算在数学发展中所起的作用和显示出来的优越性,在世界数学史上也是值得称道的. 十进位值制记数法曾经被马克思（1818―1883）称为“最妙的发明之一”①. 从有文字记载开始,我国的记数法就遵循十进制.殷代的甲骨文和西周的钟鼎文都是用一、二、三、四、五、六、七、八、九、十、百、千、万等字的合文来记十万以内的自然数的.例如二千六百五十六写作■■■■（甲骨文）,六百五十九写作■■■■■（钟鼎文）.这种记数法含有明显的位值制意义,实际上,只要把“千”、“百”、“十”和“又”的字样取消,便和位值制记数法基本一样了. 春秋战国时期是我国从奴隶制转变到封建制的时期,生产的迅速发展和科学技术的进步提出了大量比较复杂的数字计算问题.为了适应这种需要,劳动人民创造了一种十分重要的计算方法――筹算.我们认为筹算是完成于春秋战国时期,理由是：第一,春秋战国时期,农业、商业和天文历法方面有了飞跃的发展,在这些领域中,出现了大量比以前复杂得多的计算问题.由于井田制的废除,各种形状的私田相继出现,并相应实行按亩收税的制度,这就需要计算复杂形状的土地面积和产量；商业贸易的增加和货币的广泛使用,提出了大量比例换算的问题；适应当时农业需要的厉法,要计算多位数的乘法和除法.为了解决这些复杂的计算问题,才创造出计算工具算筹和计算方法筹算.第二,现有的文献和文物也证明筹算出现在春秋战国时期.例如“算”和“筹”二字出现在春秋战国时期的着作（如《仪礼》、《孙子》、《老子》、《法经》、《管子》、《荀子》等）中,甲骨文和钟鼎文中到现在仍没有见到这两个字.一二三以外的筹算数字最早出现在战国时期的货币（刀、布）上.《老子》提到：“善计者不用筹策”,可见这时筹算已经比较普遍了.因此我们说筹算是完成于春秋战国时期.这并不否认在春秋战国时期以前就有简单的算筹记数和简单的四则运算. 关于算筹形状和大小,最早见于《汉书・律历志》.

问题九：什么叫算法？什么叫计算机算法？ 算法是一系列解决问题的清晰指令，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。算法常常含有重复的步骤和一些比较或逻辑判断。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
算法的时间复杂度是指算法需要消耗的时间资源。一般来说，计算机算法是问题规模n 的函数f(n)，算法执行的时间的增长率与f(n) 的增长率正相关，称作渐进时间复杂度（Asymptotic Time plexity）。时间复杂度用“O（数量级）”来表示，称为“阶”。常见的时间复杂度有： O（1）常数阶；O（log2n）对数阶；O（n）线性阶；O（n2）平方阶。

算法的空间复杂度是指算法需要消耗的空间资源。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。

[font class=Apple-style-span style=font-weight: bold; id=bks_etfhxykd]算法 Algorithm [/font]

算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。

一个算法应该具有以下五个重要的特征：

1、有穷性： 一个算法必须保证执行有限步之后结束；

2、确切性： 算法的每一步骤必须有确切的定义；

3、输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件；

4、输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；

5、可行性： 算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。

算法的设计要求

问题十：什么是网络算法？ 说的简单点，就是指网络公司对于网站排名的一种计算公式。
从事SEO工作的人，想认识学习SEO，可以加群，群号前面137中间303后面464。特别是新手站长，没有人指导的话，很容易走歪，自学SEO是比较难的，需要专业系统的学习。

2016网络搜索算法大盘点

6月：打击欺骗下载和无告知的捆绑下载。

7月：冰桶3.0，打击移动页强制用户下载或调起APP的行为。

8月：天网，打击网站窃取用户信息，在网页嵌恶意代码，用于盗取网民的QQ号、手机号等隐私行为。

9月：冰桶4.0，网络搜索针对移动搜索结果页广告过多、影响用户体验的页面，进行策略调整，冰桶算法4.0特打击此类站点。

11月：蓝天，蓝天算法主要打击新闻源站点售卖软文、目录行为。