当前位置：文档之家› 人工智能大作业解读

人工智能大作业解读

实现遗传算法的0-1背包问题求解

摘要 (2)

一．问题描述 (2)

二．遗传算法特点介绍 (2)

三．使用基本遗传算法解决0- 1背包问题 (3)

四．基本遗传算法解决0- 1背包问题存在的不足 (4)

五．改进的遗传算法解决0- 1背包问题 (6)

六．心得体会 (9)

七．参考文献 (10)

八．程序代码 (10)

摘要：研究了遗传算法解决0-1背包问题中的几个问题：

1）对于过程中不满足重量限制条件的个体的处理,通过代换上代最优解保持种群的进化性

2）对于交换率和变异率的理解和处理方法,采用逐个体和逐位判断的处理方法

3）对于早熟性问题,引入相似度衡量值并通过重新生成个体替换最差个体方式保持种群多样性。4）一种最优解只向更好进化方法的尝试。

通过实际计算比较表明,本文改进遗传算法在背包问题求解中具有很好的收敛性、稳定性和计算效率。通过实例计算，表明本文改进遗传算法优于简单遗传算法和普通改进的遗传算法。

关键词：遗传算法；背包问题；优化

一、问题描述

0-1背包问题属于组合优化问题的一个例子，求解0-1背包问题的过程可以被视作在很多可行解当中求解一个最优解。01背包问题的一般描述如下：

给定n个物品和一个背包，物品i的重量为Wi，其价值为Vi，背包的容量为C。选择合适的物品装入背包，使得背包中装入的物品的总价值最大。注意的一点是，背包内的物品的重量之和不能大于背包的容量C。在选择装入背包的物品时，对每种物品i只有两种选择：装入背包或者不装入背包，即只能将物品i装入背包一次。称此类问题为0/1背包问题。

其数学模型为：

0-1背包问题传统的解决方法有动态规划法、分支界限法、回溯法等等。传统的方法不能有效地解决0-1背包问题。遗传算法（Genetic Algorithms）则是一种适合于在大量的可行解中搜索最优（或次优）解的有效算法。

二、遗传算法特点介绍:

遗传算法(Genetic Algorithm, GA)是1962年Holland教授首次提出了GA算法的思想是近年来随着信息数据量激增，发展起来的一种崭新的全局优化算法，它借用了生物遗传学的观点，通过自然选择、遗传、变异等作用机制，实现各个个体的适应性的提高。

基本遗传算法求解步骤：

Step 1 参数设置：在论域空间U上定义一个适应度函数f(x)，给定种群规模N，交叉率P c 和变异率P m，代数T；

Step 2 初始种群：随机产生U中的N个染色体s1, s2, …, s N，组成初始种群S={s1, s2, …, s N}，置代数计数器t=1；

Step 3计算适应度：S中每个染色体的适应度f() ；

Step 4 判断：若终止条件满足，则取S中适应度最大的染色体作为所求结果，算法结束。Step 5 选择-复制：按选择概率P(x i)所决定的选中机会，每次从S中随机选定1个染色体并将其复制，共做N次，然后将复制所得的N个染色体组成群体S1；

Step 6 交叉：按交叉率P c所决定的参加交叉的染色体数c，从S1中随机确定c个染色体，配对进行交叉操作，并用产生的新染色体代替原染色体，得群体S2；

Step 7 变异：按变异率P m所决定的变异次数m，从S2中随机确定m个染色体，分别进行变异操作，并用产生的新染色体代替原染色体，得群体S3；

Step 8 更新：将群体S3作为新一代种群，即用S3代替S，t=t+1，转步3；

遗传算法是一种仿生算法, 即模拟生命演化的算法，它从一个代表问题初始解的初始种群出发, 不断重复执行选择, 杂交和变异的过程, 使种群进化越来越接近某一目标既最优解，如果视种群为超空间的一组点, 选择、杂交和变异的过程即是在超空间中进行点集之间的某种变换, 通过信息交换使种群不断变化，遗传算法通过模拟达尔文“优胜劣汰, 适者生存”的原理激励好的结构, 同时寻找更好的结构, 作为一种随机的优化与搜索方法, 遗传算法有着其鲜明的特点。

—遗传算法一般是直接在解空间搜索, 而不像图搜索那样一般是在问题空间搜索, 最后才找到解(如果搜索成功的话)。

—遗传算法的搜索随机地始于搜索空间的一个点集, 而不像图搜索那样固定地始于搜索空间的初始节点或终止节点, 所以遗传算法是一种随机搜索算法。

—遗传算法总是在寻找优解(最优解或次优解), 而不像图搜索那样并非总是要求优解, 而一般是设法尽快找到解(当然包括优解), 所以遗传算法又是一种优化搜索算法。

—遗传算法的搜索过程是从空间的一个点集(种群)到另一个点集(种群)的搜索,而不像图搜索那样一般是从空间的一个点到另一个点地搜索。因而它实际是一种并行搜索, 适合大规模并行计算, 而且这种种群到种群的搜索有能力跳出局部最优解。

—遗传算法的适应性强, 除需知适应度函数外, 几乎不需要其他的先验知识。

—遗传算法长于全局搜索, 它不受搜索空间的限制性假设的约束,不要求连续性, 能以很大的概率从离散的、多极值的、含有噪声的高维问题中找到全局最优解。

三、使用基本遗传算法解决0- 1背包问题：

1: 打开数据文件

2: 设置程序运行主界面

3: 调用初始化种群模块

3- 1: 按照一定的种群规模和染色体长度以基因为单位用随机产生的0- 1对个体赋值3- 2: 调用计算适应度函数

4: 以最大进化代数为循环终止条件开始进行循环

4- 1: 调用产生新一代个体的函数

4- 1- 1: 调用选择函数

4- 1- 2: 调用交叉函数

4- 1- 3: 调用变异函数

4- 1- 4: 调用计算适应度函数

5: 调用计算新一代种群统计数据函数

6: 调用输出新一代统计数据函数

7: 返回到第四步, 直至循环结束

四、基本遗传算法解决0- 1背包问题存在的不足：

1.对于过程中不满足重量限制条件的个体的处理

在用基本遗传算法解决0- 1背包问题的时候，在初始化或者交叉变异后可能会产生不满足重量约束条件的伪解，而对于这些伪解，基本遗传算法没有给出一个很好的处理方法，而只是又随机生成了一个满足约束条件的解作为新的个体从而替换掉原来的个体。根据遗传算

法的根本思想“优胜劣汰，适者生存”的原则，可以将不满足条件的个体用已有的最优个体来进行替换，这样，既使得种群中所有的个体均满足重量的约束条件，又保留了较优解，符合遗传算法的思想。

具体做法为：

在程序中加入一个变量保存每代的最优解，当前代在进行选择、复制、交叉、变异后如果有不满足约束条件的个体，则在种群更新时采用这个最优值作为替代。

具体做法为：在每代遗传后通过函数FindBestandWorstIndividual()找到当前最优值并保存bestindividual中，在计算适应度函数CalculateFitnessValue()中加入：

if(w>KW) X[i]=bestindividual; //如果不是解，找最好的一个解代之

其中w为当前个体的总重量，KW为背包最大承重量，X[i]表示种群中第i个个体，bestindividual 为保存的个体最优解。

2.对于交换率和变异率的理解和处理方法

根据遗传算法的基本步骤的交叉和变异操作

Step 6 交叉：按交叉率P c所决定的参加交叉的染色体数c，从S1中随机确定c个染色体，配对进行交叉操作，并用产生的新染色体代替原染色体，得群体S2；

Step 7 变异：按变异率P m所决定的变异次数m，从S2中随机确定m个染色体，分别进行变异操作，并用产生的新染色体代替原染色体，得群体S3；

可以有两种处理方法：

其一，采用先确定数目在随机选取的方法，步骤如下：

对于交叉操作：

1,根据交叉率确定应该交叉的个体数目n

2,在种群中进行n次循环

2-1随机选中种群中的一个个体a

2-2随机选中种群中异于a的一个个

体b

2-3随机确定交叉位数

2-4进行交叉对于变异操作：

1,根据变异率确定应该变异的染色体数目n

2,在种群中进行n次循环

2-1随机选中种群中的一个个体的染

色体a

2-2随机选中染色体a 的某位基因

2-3对进行0-1互换变异

其二，采用对每个操作单元分别进行特定概率下处理的方法，步骤如下：

对于交叉操作：

1,在种群中进行S次循环,其中S代表种群中个体的数量

2,对于每一个个体X[i]（X为种群数组）做如下操作

2-1生成随机数p[0,1],判断p 与的大小关系

2-2如果p说明X[i]需要交换

2-2-1 随机在种群中找到异于X[i]的另一个体进行交换

2-3如果p说明X[i]不需要交换对于变异操作：

1,在种群中进行S次循环,其中S代表种群中个体的数量

2,对每一个个体X[i]做N次循环，其中N为染色体位数

2-1对染色体的每一位

3-1生成随机数q[0,1],判断q 与

的大小关系

3-2如果q 说明需要进行0-1互换变异2-3如果q 说明不需要变

分析这两种处理方法可知：方法一没有很好地体现随机机会均等的思想，因为在步骤1中确

定的需要操作的数目n后，总体上是保证了交叉或者变异的数目，但不是对于每一个个体而言的，因而会出现有的个体被选择交叉或者变异多次而有的没有机会交叉或者变异的情况，而如果采用方法二，就体现了机会的均等性，即要求对每一个单元操作目标进行概率的验证，以确定是否变异或者交叉。在程序中具体的实现方法体现在交叉和变异函数中：

void CrossoverOperator(void)//交叉操作

for(i=0; i

do{p=rand()%S;//两个[0，S]的随机数

q=rand()%S;

}while(p==q);

int w=1+rand()%N;//[1,N]交换的位数

double p=(rand()%1001)/1000.0; if(p<=Pc) for(j=0;j

for (i=0; i

for (j=0; j

q=(rand()%1001)/1000.0;//产生q[0,1]

if (q

if(X[i].chromsome[j]==1)X[i].chromsome[j]=0;

else X[i].chromsome[j]=1;

1.对于算法早熟性的分析及解决方法

遗传算法中种群中的个体由初始化时的具有多样性，可能会由于在进化过程中一些超常个体限制其它个体的进化——这个个体的适应度大大优于种群内的其它值，由于适者生存原则这个个体被不断复制从而充满了整个种群，使得种群的多样应大大降低，进化停滞，从而出现算法收敛于局部最优解的现象，称为早熟现象。

早熟现象的可能解法：

1）通过提高变异率来增加种群的多样性，以期更优解的出现，这也是最简单基本遗传算法中不添加相关操作的情况下唯一的一种方法，然而这种方法有明显的弊端：在提高变异率获得多样性种群的同时，个体变异的机会增加，使得较优解发生变异，从而遗传算法丧失了其优于其它算法的优越性，所以这种方法不是很好地解决方法。

2）引入多样性衡量和处理

基本思路：在出现进化停滞现象时要引入新的个体来增强种群的多样性。

做法：1,判断是否达到早熟现象

对于种群中S个个体，判断等位基因的相等程度，即引入一个参数值same,如果same达到一定的理论值大小就可以认为达到了早熟现象。

2,早熟现象的处理，即引入新的个体。

处理过程中应该不违反适者生存的原则，所以应该保留较好的个体，所以首先选中适应度最小的个体执行删除操作，然后随机生成一个新的符合重量限制且打破早熟现象的新个体。

具体实现见函数：void checkalike(void)

//相似度校验

for( i=0;i

for(j=0;j

bool temp=X[i].chromsome[j];

for(int k=1;k

if(temp!=X[k].chromsome[j])

break;

if(j==N)same++;

if(same>N*0.5)//大于50%作为判定为早熟//确定最小

int minindex=0;

for(intn=0;n

if(X[n].fitness

for (j=0; j

bool m=(rand()%10<5)?0:1;

X[minindex].chromsome[j]=m;

X[minindex].weight+=m*weight[j];

//个体的总重量

X[minindex].fitness+=m*value[j];

//个体的总价值

2.一种最优解只向更好进化方法的尝试

基本思路为：每一组的最优解是一个独特的个体，我们求解的问题最终的最优解或者近似解都产生于这个特殊的个体，最优解只向更好进化方法中规定：每代中选出一个最优解并做好相应的记录或者标记，最优解参与交叉和变异，只是在交叉或者变异时对最优解进行前后适应度的比较，如果发现交叉或者变异后适应度大于操作前适应度，则保存操作后的结果，如果发现交叉或者变异后适应度小于操作前适应度，则禁止最优解的操作，而不禁止与最优解进行交叉的个体的变化。这样，每一代中的最优解的特性可以通过交叉传递给同代中的其它个体，而保证种群一定会向更好的方向进化。

做法在交叉后和变异后调用以下函数判断：

int comp(individual bestindividual,individual temp)//比较函数

{

int fit=0,w=0;//第一种不变:操作后不满足重量函数，第二种:操作后适应度小于操作前

for(int i=0;i

if(w>KW)return -1;

return (bestindividual.fitness>fit?-1:1);//如果小于原来值或者不满足重量函数，则返回-1

}

五、改进的遗传算法解决0- 1背包问题：

1、参数设置：

#define S 500 //种群的规模

#define Pc 0.8 //交叉概率

#define Pm 0.01 //突变概率

#define KW 878 //背包最大载重

#define N 20 //物体总数

#define T 1000 //最大换代数

2个体的表示和染色体编码

用变量i代表物件, i = 1, 2, ,n 定义变量xi，其含义为：xi= 1表示：第i个物件被选入背包, xi = 0表示第i个物件没有被选入背包。考虑n 个物件的选择与否, 就可以得到一个长度为n的0, 1序列。由此可见遗传算法应用于上述背包问题时,采用简单二进制编码较为适宜1 每一组编码即为某一个个体的基因表示, 称其为染色体, 染色体长度取决于待分配的物件的个数n.在编码形式的表示方法中,形如二进制编码10010101 表示为一个待分配的物件的个数为8（编码长度）的一个背包问题的一个解, 则该个体对应于选择了物件1, 4, 6, 8，即第1, 4, 6, 8个物品被放入了背包。用数据格式表示为：

struct individual //个体结构体

{

bool chromsome[N]; //染色体编码

double fitness; //适应度//即本问题中的个体所得价值

double weight; //总重量

};

2产生初始种群

n个待分配的物件随机产生S个长度为n的二进制串, 即种群中个体的染色体编码的每一位按等概率在0与1中选择S 指的是种群规模, 即种群中的个体数目.

void GenerateInitialPopulation(void); //初始种群

3适应度函数

背包内物件的总重量为a1x1 + a2x2 + ,anxn, 物件的总价值为c1x1 + c2x2 + , + cn xn

0-1背包问题中采用每个个体的总价值作为适应度，在满足背包容量的条件下，价值越大，适应度越高。所以适应度求解方法为：

f i = c1x1 + c2x2 + , + cnxn ( 当t a1x1 + a2x 2 + , + anxn < = c ，xj = 0, 1)

考虑到会有不不满足容量条件的个体则：

f i = 0 (当a1x1 + a2x2 + , + anxn > c ，xj = 0, 1)

上述适应度函数基于一个考虑违背约束条件的惩罚处理，根据上述具体问题适应度函数值不可能为零, 所以当随机产生的某个个体违背约束条件时, 通过把其适应度函数值罚为0而达到淘汰该个体的目的。 4选择-复制操作

参照适应度函数值和约束条件用赌轮选择法进行模拟，具体为: ( 1)根据适应度函数值和约束条件, 罚掉部分个体（前述不满足容量条件的个体） (2)对于满足约束条件的个体, 根据适应度函数值计算个体被选中的概率,称为选择概率：公式为: P

p()称为染色体x i (i =1, 2, …, n )的选择概率

(3)根据轮盘赌累计公式为：

称为染色体x i (i =1, 2, …, n )的积累概率

( 4) 对已得到的累计概率作如下处理，完成选择操作： 1）在［0, 1］区间内产生一个均匀分布的伪随机数r 。 2）若r≤q1,则染色体x1被选中。 3）若qk-1

对于每一个个体，根据交叉率P c 做如下操作： ( 1)随机产生一个交叉点的位置 ( 2)随机选取当前代中的两个个体作为父个体 ( 3)根据交叉点的位置, 做单点交叉 6变异操作: 根据变异率P m

( 1)随机产生变异点的位置 ( 2)在变异点位置作0- 1翻转 8、算法终止

程序中定义了一个最优值，stop=

一般情况下这个最优值达不到，一旦程序在执行过

程中达到此最优值，也就没有必要在执行下去，因为这必定是最好的解，所以保存最优值和最优解，结束。

如果程序的最优值达不到理想情况下的stop ，那么根据最大换代次数来结束程序，在结束后的种群中找到一个最好的解作为本问题的最优解，程序结束。

4算例

1. 小规模问题的算例：

算例1-1：设定物品价值value={50,30,60,80,20}重量weight{35,40,40,20,15}背包的最大承重量为100

遗传算法中参数：群体大小S=5，交叉率Pc=0.8,变异率Pm=0.05,最大换代次数T=20, 通过多次试验比较本文改进后遗传算法和其他得到结果如下表所示：

∑==i

j j i x P q 1)

(

本文改进的遗传算法：

实验总次数：30

达到全局最优解次数：27

未达到全局最优解：3

由实验结果可知在小规模算例中，本文改进的遗传算法优于前两者。

2．较大规模问题求解算例：

遗传算法中参数：

群体大小S=5，交叉率Pc=0.8,变异率Pm=0.05,最大换代次数T=800，相似度取5%

实例1：

价值value：{ 92,4,43,83,84,68,92,82,6,44,32,18,56,83,25,96,70,48,14,58}

重量weight：{ {44,46,90,72,91,40,75,35,8,54,78,40,77,15,61,17,75,29,75,63}}

背包的最大承重量：878

实例2：

价值value：

{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};

重量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,25,30,45,30,60,50 ,20,65, 20,25,30,10,20,25,15,10,10,10,4,4,2,1};

背包最大承重量：1000

本文改进遗传算法实验结果：

实例1：

实例2：

由此得出结论：遗传算法优于前两种。

六.心得体会：

遗传算法是一种模拟生物进化在解中求解最优值的方法，实现起来方便，适于处理大宗数据，然而基于简单基本遗传算法在求解不同问题时应该具体问题具体分析，找的结合所解问题的优化方法，例如本文分析的遗传算法解决0-1背包问题，虽然简单基本遗传算法可以求出一个比较好的解出来，但是分析可知，结果并不令人满意，在对问题进行细致的分析、查阅相关资料和深入思考后，我提出了自己认为比较好的改进方法并通过实践结合具体的算例把改进后的遗传算法和与原来的简单遗传算法和参考文献中的一种改进方法进行了比较，结果显示本文改进的遗传算法无论在小规模数据处理还是较大规模数据处理方面均优于前两者，这一点很令人高兴。通过本次实践，我也深刻体会到对于算法分析和改进的重要性，往往一个算法经过认真地分析和合理的改进后会获得性能上的提高时间复杂度或者空间复杂度的降低，而且能够获得更好的解。

七.参考文献：

《用基本遗传算法解决0- 1背包问题》

八.程序实现：

已通过vc6.0编译后运行

#include

/*小规模***********************************************************************

#define S 5 //种群的规模

#define N 5 //物体总数

#define Pc 0.8 //交叉概率

#define Pm 0.05 //突变概率

#define KW 100 //背包最大载重

#define T 20 //最大换代数

#define ALIKE 0.05 //判定相似度

int stop=0; //初始化函数中初始化为所有价值之和

int t=0; //目前的代数

int weight[]={35,40,40,20,15}; //物体重量

int value[]={50,30,60,80,20}; //物体价值

/*实例1***********************************************************************

#define S 5 //种群的规模

#define N 20 //物体总数

#define Pc 0.8 //交叉概率

#define Pm 0.05 //突变概率

#define KW 878 //背包最大载重

#define T 800 //最大换代数

#define ALIKE 0.05 //判定相似度

int stop=0; //初始化函数中初始化为所有价值之和

int t=0; //目前的代数

int weight[]={44,46,90,72,91,40,75,35,8,54,78,40,77,15,61,17,75,29,75,63}; //物体重量

int value[]={92,4,43,83,84,68,92,82,6,44,32,18,56,83,25,96,70,48,14,58}; //物体价值

/*实例2***********************************************************************

#define S 5 //种群的规模

#define Pc 0.8 //交叉概率

#define Pm 0.05 //突变概率

#define KW 1000 //背包最大载重1000

#define N 50 //物体总数

#define T 800 //最大换代数

#define ALIKE 0.05 //判定相似度

int stop=0; //初始化函数中初始化为所有价值之和

int t=0; //目前的代数

int vaue[]={

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

int 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,25,30,45,30,60,50,20,65 ,20,25,30,10,20,25,15,10,10,10,4,4,2,1};

/*实例3***********************************************************************/

#define S 5 //种群的规模

#define Pc 0.8 //交叉概率

#define Pm 0.05 //突变概率

#define KW 6718 //背包最大载重1000

#define N 100 //物体总数

#define T 800 //最大换代数

#define ALIKE 0.05 //判定相似度

int stop=0; //初始化函数中初始化为所有价值之和

int t=0; //目前的代数

int vaue[]={

597,596,593,586,581,568,567,560,549,548,547,529,529,527,520,491,482,478,475,475,466,462,459,458,454,45 1,449,443,442,421,410,409,395,394,390,377,375,366,361,347,334,322,315,313,311,309,296,295,294,289,285, 279,277,276,272,248,246,245,238,237,232,231,230,225,192,184,183,176,171,169,165,165,154,153,150,149,14 7,143,140,138,134,132,127,124,123,114,111,104,89,74,63,62,58,55,48,27,22,12,6,250};

Int weight[]={

54,183,106,82,30,58,71,166,117,190,90,191,205,128,110,89,63,6,140,86,30,91,156,31,70,199,142,98,178,16,1 40,31,24,197,101,73,16,73,2,159,71,102,144,151,27,131,209,164,177,177,129,146,17,53,64,146,43,170,180,17 1,130,183,5,113,207,57,13,163,20,63,12,24,9,42,6,109,170,108,46,69,43,175,81,5,34,146,148,114,160,174,156 ,82,47,126,102,83,58,34,21,14};

/************************************************************************/

struct individual //个体结构体

{

bool chromsome[N]; //染色体编码

double fitness; //适应度//即本问题中的个体所得价值

double weight; //总重量

};

int best=0;

int same=0;

individual X[S],Y[S],bestindividual;//

/************************************************************************/

int comp(individual bestindividual,individual temp); //比较函数

void checkalike(void); //检查相似度函数

void GenerateInitialPopulation(void); //初始种群

void CalculateFitnessValue(void); //适应度

void SelectionOperator(void); //选择

void CrossoverOperator(void); //交叉

void MutationOperator(void); //变异

void FindBestandWorstIndividual(void); //寻找最优解

void srand(unsigned int seed); //随机生成

/************************************************************************/

int comp(individual bestindividual,individual temp)//比较函数

{

int fit=0,w=0;//第一种不变:操作后不满足重量函数，第二种:操作后适应度小于操作前

for(int i=0;i

if(w>KW)return -1;

return (bestindividual.fitness>fit?-1:1);//如果小于原来值或者不满足重量函数，则返回-1

}

/************************************************************************/

void Checkalike(void)

{

int i=0,j=0;

for( i=0;i

{

for(j=0;j

{

bool temp=X[i].chromsome[j];

for(int k=1;k

{

if(temp!=X[k].chromsome[j])

break;

}

if(j==N)same++;

}

if(same>N*ALIKE)//大于ALIKE作为判定为早熟

{

int minindex=0;

for(int n=0;n

if(X[n].fitness

for (j=0; j

{

bool m=(rand()%10<5)?0:1;

X[minindex].chromsome[j]=m;

X[minindex].weight+=m*weight[j];//个体的总重量

X[minindex].fitness+=m*value[j]; //个体的总价值

}

/************************************************************************/ void GenerateInitialPopulation(void)//初始种群,保证每个值都在符合条件的解

{

int i=0,j=0; bool k;

for(i=0;i

for (i=0; i

{

int w=0,v=0;

for (j=0; j

{

k=(rand()%10<5)?0:1;

X[i].chromsome[j]=k;

w+=k*weight[j];//个体的总重量

v+=k*value[j]; //个体的总价值

}

if(w>KW) i--; //如果不是解，重新生成

else

{

X[i].fitness=v;

X[i].weight=w;

if(v==stop){bestindividual=X[i];return;}//这种情况一般不会发生

}

/************************************************************************/

void CalculateFitnessValue()

{

int i=0,j=0;

for (i=0; i

{

int w=0,v=0;

for (j=0; j

{

w+=X[i].chromsome[j]*weight[j];//个体的总重量

v+=X[i].chromsome[j]*value[j]; //个体的总价值

}

X[i].fitness=v;

X[i].weight=w;

if(v==stop){bestindividual=X[i];return;}//符合条件情况下最优解这种情况一般不会发生if(w>KW) X[i]=bestindividual; //如果不是解，找最好的一个解代之}

}

/************************************************************************/

void SelectionOperator(void)

{

int i, index;

double p, sum=0.0;

double cfitness[S];//选择、累积概率

individual newX[S];

for (i=0;i

for (i=1;i

for (i=0;i

{

p=(rand()%1001)/1000.0;//产生一个[0,1]之间的随机数

index=0;

while(p>cfitness[index])//轮盘赌进行选择

{

index++;

}

newX[i]=X[index];

}

for (i=0; i

}

/************************************************************************/

void CrossoverOperator(void)//交叉操作

{

int i=0, j=0,k=0;individual temp;

for(i=0; i

{

int p=0,q=0;

{

p=rand()%S;//产生两个[0，S]的随机数

q=rand()%S;

}while(p==q);

int w=1+rand()%N;//[1,N]表示交换的位数

double r=(rand()%1001)/1000.0;//[0,1]

if(r<=Pc)

{

for(j=0;j

{

temp.chromsome[j]=X[p].chromsome[j];//将要交换的位先放入临时空间

X[p].chromsome[j]=X[q].chromsome[j];

X[q].chromsome[j]=temp.chromsome[j];

}

if(p==best)

if(-1==comp(bestindividual,X[p]))//如果变异后适应度变小

X[p]=bestindividual;

if(q==best)

if(-1==comp(bestindividual,X[q]))//如果变异后适应度变小

X[q]=bestindividual;

}

/************************************************************************/ void MutationOperator(void)

{

int i=0, j=0,k=0,q=0;

double p=0;

for (i=0; i

{

for (j=0; j

{

p=(rand()%1001)/1000.0;

if (p

{

if(X[i].chromsome[j]==1)X[i].chromsome[j]=0;

else X[i].chromsome[j]=1;

}

if(i==best)

if(-1==comp(bestindividual,X[i]))//如果变异后适应度变小

X[i]=bestindividual;

}

/************************************************************************/ void FindBestandWorstIndividual(void)

{

int i;

bestindividual=X[0];

for (i=1;i

{

if (X[i].fitness>bestindividual.fitness)

{

bestindividual=X[i];

best=i;

}

/*主函数*****************************************************************/ void main(void)

{

srand((unsigned)time(0));

t=0;

GenerateInitialPopulation(); //初始群体包括产生个体和计算个体的初始值

while (t<=T)

{

FindBestandWorstIndividual(); //保存当前最优解

SelectionOperator(); //选择

CrossoverOperator(); //交叉

MutationOperator(); //变异

Checkalike(); //检查相似度

CalculateFitnessValue(); //计算新种群适应度

t++;

}

FindBestandWorstIndividual(); //找到最优解

cout<

for(int k=0;k

cout<

}

/*结束***********************************************************************/

读书的好处

1、行万里路，读万卷书。

2、书山有路勤为径，学海无涯苦作舟。

3、读书破万卷，下笔如有神。

4、我所学到的任何有价值的知识都是由自学中得来的。——达尔文

5、少壮不努力，老大徒悲伤。

6、黑发不知勤学早，白首方悔读书迟。——颜真卿

7、宝剑锋从磨砺出，梅花香自苦寒来。

8、读书要三到：心到、眼到、口到

9、玉不琢、不成器，人不学、不知义。

10、一日无书，百事荒废。——陈寿

11、书是人类进步的阶梯。

12、一日不读口生，一日不写手生。

13、我扑在书上，就像饥饿的人扑在面包上。——高尔基

14、书到用时方恨少、事非经过不知难。——陆游

15、读一本好书，就如同和一个高尚的人在交谈——歌德

16、读一切好书，就是和许多高尚的人谈话。——笛卡儿

17、学习永远不晚。——高尔基

18、少而好学，如日出之阳；壮而好学，如日中之光；志而好学，如炳烛之光。——刘向

19、学而不思则惘，思而不学则殆。——孔子

20、读书给人以快乐、给人以光彩、给人以才干。——培根

人工智能大作业

第一章 1、3 什么就是人工智能？它的研究目标就是什么？人工智能(Artificial Intelligence),英文缩写为AI。它就是研究、开发用于模拟、延伸与扩展人的智能的理论、方法、技术及应用系统的一门新的技术科学。研究目标:人工智能就是计算机科学的一个分支,它企图了解智能的实质,并生产出一种新的能以人类智能相似的方式做出反应的智能机器,该领域的研究包括机器人、语言识别、图像识别、自然语言处理与专家系统等。 1、7 人工智能有哪几个主要学派？各自的特点就是什么？主要学派:符号主义,联结主义与行为主义。 1.符号主义:认为人类智能的基本单元就是符号,认识过程就就是符号表示下的符号计算, 从而思维就就是符号计算; 2.联结主义:认为人类智能的基本单元就是神经元,认识过程就是由神经元构成的网络的信息传递,这种传递就是并行分布进行的。 3.行为主义:认为,人工智能起源于控制论,提出智能取决于感知与行动,取决于对外界复杂环境的适应,它不需要只就是,不需要表示,不需要推理。 1、8 人工智能有哪些主要研究与应用领域？其中有哪些就是新的研究热点？ 1、研究领域:问题求解,逻辑推理与定理证明,自然语言理解,自动程序设计,专家系统,机器学习,神经网络,机器人学,数据挖掘与知识发现,人工生命,系统与语言工具。 2、研究热点:专家系统,机器学习,神经网络,分布式人工智能与Agent,数据挖掘与知识发现。第二章 2、8 用谓词逻辑知识表示方法表示如下知识: (1)有人喜欢梅花,有人喜欢菊花,有人既喜欢梅花又喜欢菊花。三步走:定义谓词,定义个体域,谓词表示定义谓词 P(x):x就是人

西电人工智能大作业

人工智能大作业学生：021151** 021151** 时间：2013年12月4号

一．启发式搜索解决八数码问题 1.实验目的问题描述：现有一个3*3的棋盘，其中有0-8一共9个数字，0表示空格，其他的数字可以和0交换位置（只能上下左右移动）。给定一个初始状态和一个目标状态，找出从初始状态到目标状态的最短路径的问题就称为八数码问题。例如：实验问题为

到目标状态：从初始状态：要求编程解决这个问题，给出解决这个问题的搜索树以及从初始节点到目标节点的最短路径。 2.实验设备及软件环境利用计算机编程软件Visual C++ 6.0，用C语言编程解决该问题。 3.实验方法 (1).算法描述： ①.把初始节点S放到OPEN表中，计算() f S，并把其值与节点S联系起来。 ②.如果OPEN表是个空表，则失败退出，无解。 ③.从OPEN表中选择一个f值最小的节点。结果有几个节点合格，当其中有一个为目标节点时，则选择此目标节点，否则就选择其中任一节点作为节点i。 ④.把节点i从OPEN表中移出，并把它放入CLOSED的扩展节点表中。 ⑤.如果i是目标节点，则成功退出，求得一个解。 ⑥.扩展节点i，生成其全部后继节点。对于i的每一个后继节点j： a.计算() f j。 b.如果j既不在OPEN表中，也不在CLOSED表中，则用估价函数f

把它添加入OPEN表。从j加一指向其父辈节点i的指针，以便一旦找到目标节点时记住一个解答路径。 c.如果j已在OPEN表或CLOSED表上，则比较刚刚对j计算过的f 值和前面计算过的该节点在表中的f值。如果新的f值较小，则 I.以此新值取代旧值。 II.从j指向i，而不是指向它的父辈节点。 III.如果节点j在CLOSED表中，则把它移回OPEN表。 ⑦转向②，即GO TO ②。 (2).流程图描述： (3).程序源代码： #include #include

人工智能作业一答案

作业一 1.考虑一个实时的在线电话翻译系统，该系统实现英语与日语之间的实时在线翻译，讨论该系统的性能度量，环境，执行器，感知器，并对该环境的属性进行分析。【Answer】性能度量：翻译的正确率环境：电话线路传感器：麦克风执行器：音响完全可观察的，单agent，确定的(无噪音条件下)，片段的，静态的，离散的。2.考虑一个医疗诊断系统的agent，讨论该agent最合适的种类(简单agent,基于模型的agent, 基于目标的agent和基于效用的agent)并解释你的结论。【Answer】 utility-based agent。能够治愈病人的方法有很多种，系统必须衡量最优的方法来推荐给病人 3.先建立一个完整的搜索树，起点是S,终点是G,如下图,节点旁的数字表示到达目标状态的距离，然后用以下方法表示如何进行搜索。 (a).深度优先； (b).宽度优先； (c).爬山法； (d).最佳优先；图一【Answer】: 建立树：深度: 宽度：爬山法：优先搜索： 4.图二是一棵部分展开的搜索树，其中树的边记录了对应的单步代价，叶子节点标注了到达目标结点的启发式函数的代价值，假定当前状态位于结点A。 (a)用下列的搜索方法来计算下一步需要展开的叶子节点。注意必须要有完整的计算过程，同时必须对扩展该叶子节点之前的节点顺序进行记录： 1.贪婪最佳优先搜索 2.一致代价搜索 3.A*树搜索 (b)讨论以上三种算法的完备性和最优性。【Answer】: 贪婪最佳优先：如果h(B)>5,首先访问叶子结点C,如果h(B)<=5,首先访问B,再访问C 一致代价搜索：B,D,E,F,G,H,C A*树搜索：如果h(B)>15,首先访问D 如果h(B)<=15,首先访问B,在E,G,D,H,F,C 图二 5.给定一个启发式函数满足h(G)=0,其中G是目标状态，证明如果h是一致的，那么它是

人工智能大作业

内蒙古科技大学2012/2013 学年第一学期《人工智能》大作业课程号：67111317 考试方式：大作业任课教师：陈淋艳使用专业、年级班级：学号：姓名：

试用谓词演算语句集合表示下面这段话；并用归结反演的方法回答下列问题：设TONY，|MIKE和JOHN属于ALPINE俱乐部， ALPINE俱乐部的成员不是滑雪运动员就是登山运动员。登山运动员不喜欢下雨，而且任何不喜欢雪的人都不是滑雪运动员。MIKE讨厌TONY所喜欢的一切东西，而喜欢TONY所讨厌的一切东西。TONY喜欢雨和雪。试问有没有ALPINE俱乐部的成员，他是一个登山运动员但不是滑雪运动员。五、(20分)在主观Bayes推理中，LS和LN的意义是什么？设系统中有如下规则： R1：IF E1THEN （50 0，0.01）H1 R2 IF E2THEN （1，100）H1 R3：IF E3THEN （1000，1）H2 R4：IF H1THEN （20，1）H2 并且已知P(H1)=0.1，P(H2)=0.1，P(H3)=0.1，初始

人工智能大作业实验

人工智能大作业实验-标准化文件发布号：（9456-EUATWK-MWUB-WUNN-INNUL-DDQTY-KII

湖南中医药大学本科课程实验教学大纲《人工智能》计算机科学与技术专业执笔人：丁长松审定人：*** 学院负责人：*** 湖南中医药大学教务处二○一四年三月

一、课程性质和教学目的《人工智能》是计算机专业本科生的一门专业必修课，适应于计算机科学与技术专业、医药信息工程专业。本课程是关于人工智能领域的引导性课程，通过本课程的学习，是使学生了解和掌握人工智能的基本概念、原理和方法，培养学生在计算机领域中应用人工智能技术提高分析和解决较复杂问题的能力，启发学生对人工智能的兴趣，培养知识创新和技术创新能力。《人工智能》主要研究智能信息处理技术、开发具有智能特性的各类应用系统的核心技术。本课程主要介绍人工智能的基本理论、方法和技术，主要包括常用的知识表示、逻辑推理和问题求解方法、人工智能发展学派以及主要理论。先修课程：高等数学、数据结构、数据库原理、算法设计与分析、数理逻辑二、课程目标人工智能实验应在一种为高效率开发专家系统而设计的高级程序系统或高级程序设计语言环境中进行。在目前开来，专家系统开发工具和环境可分为5种主要类型：程序设计语言、知识工程语言、辅助型工具、支持工具及开发环境。在这里主要是要求学生能用相关术语描述、表示一些问题；用程序设计语言如：C、C++、JAVA编程来实现一些基本的算法、推理、搜索等过程。三、实验内容与要求实验一：谓词表示【实验内容】设农夫、狼、山羊、白菜都在河的左岸，现在要把它们运送到河的右岸去，农夫有条船，过河时，除农夫外船上至多能载狼、山羊、白菜中的一种。狼要吃山羊，山羊要吃白菜，除非农夫在那里。试设计出一个确保全部都能过河的方案。

人工智能试题

内蒙古科技大学2013/2014 学年第一学期《人工智能》大作业课程号：67111317、76807376 考试方式：大作业使用专业、年级：计算机2011-1，2，3，4 任课教师：陈淋艳班级：学号：姓名：

一、（15分）智能、智力、能力的含义是什么？什么是人工智能？人类研究人工智能的最终目标是什么？二、（15分）传教士与野人问题：有三个传教士和三个野人来到河边，河边只有一条一次最多可供两个人过河的小船，传教士如何用这条小船过河才能使河两边的野人数目决不会超过传教士的数目？指定状态描述的格式，开始状态和目标状态；画出状态空间图。（只要画出河两边野人数目不会超过传教士数目的状态即可）。三、(10分)用谓词公式表示下列语句：因为老百姓授法律管制，所以晁盖劫了生辰纲，触犯了宋王朝的法律，受到官府追究；而达官贵人和恶少不受法律管制，所以高衙内强抢民女，虽然也违法，却可以横行无忌。四、(20分)什么是演绎推理？他的推理规则是什么？试用谓词演算语句集合表示下面这段话；并用归结反演的方法回答下列问题：设TONY，|MIKE和JOHN属于ALPINE俱乐部，ALPINE俱乐部的成员不是滑雪运动员就是登山运动员。登山运动员不喜欢下雨，而且任何不喜欢雪的人都不是滑雪运动员。MIKE讨厌TONY所喜欢的一切东西，而喜欢TONY所讨厌的一切东西。 TONY喜欢雨和雪。试问有没有ALPINE俱乐部的成员，他是一个登山运动员但不是滑雪运动员。五、(20分)在主观Bayes推理中，LS和LN的意义是什么？

设系统中有如下规则： R1：IF E1THEN （50 0，0.01）H1 R2 IF E2THEN （1，100）H1 R3：IF E3THEN （1000，1）H2 R4：IF H1THEN （20，1）H2 并且已知P(H1)=0.1，P(H2)=0.1，P(H3)=0.1，初始证据的概率为P(E1|S1)=0.5 ，P(E2|S2)=0 ，P(E3|S3)=0.8，用主观Bayes方法求H2的后验概率P(H2|S1& S2& S3)。六、（20分）结课报告题目：选以下题目之一或自选题目写一篇5000 字左右的报告，要有关键字，图要有图号，最后要有参考资料。 1、总结知识表达技术。（选取三种知识表达放法加以介绍，并进行比较） 2、查找两篇或三篇已发表的与人工智能理论相关的论文，从文章所论述的问题，阐述的理论，其社会效益，与原有的方法相比，他的优缺点等。 3、介绍一已有的专家系统。 4、写一篇文章介绍人工神经网络。（应用领域，人工神经元模型，学习方法）不符合以下要求的作业不收本试题一律使用A4纸完成，一至五题要求手写。

人工智能课程大作业

作业题目摘要：机器博弈是人工智能的一个重要研究分支，本文通过设计一个五子棋智能博奕程序，采用传统的博弈树算法，利用剪枝和极大极小树搜索最佳位置，从而实现人机智能博弈。并对现有算法存在的问题进行探究改进，最后给出展示，结果表明效果比较理想。关键词：人工智能；五子棋；博弈本组成员：本人分工：α-β剪枝实现 1 引言人工智能[1]是一门综合新型的新兴边缘科学，与生物工程、空间技术并列为三大尖端技术，而机器博弈却是其一个重要的研究分支。它研究如何利用计算机去实现那些过去只能靠人的智力去完成的工作，博弈为人工智能提供了一个很好的应用场所。博弈过程可以采用与或树进行知识表达，这种表达形式称为博弈树。α—β剪枝技术是博弈树搜索中最常采用的策略。 2 算法原理与系统设计根据五子棋游戏规则，此次五子棋游戏我们采用基于极大极小值分析法的α—β剪枝算法来实现计算机走棋。α—β剪枝技术是博弈树搜索中最常采用的策略，α—β剪枝搜索由极大极小值分析法演变而来[2]。极大极小分析法其基本思想或算法是： (1) 设博弈的双方中一方为MAX，另一方为MIN。然后为其中的一方(例如MAX)寻找一个最优行动方案。 (2) 为了找到当前的最优行动方案，需要对各个可能的方案所产生的后果进行比较,具体地说，就是要考虑每一方案实施后对方可能采取的所有行动，并计算可能的得分。 (3) 为计算得分，需要根据问题的特性信息定义一个估价函数，用来估算当前博弈树端节点的得分。此时估算出来的得分称为静态估值。 (4) 当端节点的估值计算出来后，再推算出父节点的得分，推算的方法是：对“或”节点，选其子节点中一个最大的得分作为父节点的得分，这是为了使自己在可供选择的方案中选一个对自己最有利的方案；对“与”节点，选其子节点中一个最小的得分作为父节点的得分，这是为了立足于最坏的情况。这样计算出的父节点的得分称为倒推值。 (5) 如果一个行动方案能获得较大的倒推值，则它就是当前最好的行动方案。上述的极小极大分析法，实际是先生成一棵博弈树，然后再计算其倒推值，至使极小极大分析法效率较低。于是在极小极大分析法的基础上提出了α-β剪枝技术。α-β剪枝技术的基本思想或算法是，边生成博弈树边计算评估各节点的倒推值，并且根据评估出的倒推值范围，及时停止扩展那些已无必要再扩展的子节点，即相当于剪去了博弈树上的一些分枝，从而节约了机器开销，提高了搜索效率。具体的剪枝方法如下： (1) 对于一个与节点MIN，若能估计出其倒推值的上确界β，并且这个β值不大于MIN的父节

人工智能导论1-4章作业

《人工智能导论》作业（1-4章） 1．人工智能有哪几个主要的学派？各学派的基本理论框架和主要研究方向有何不同？2．用谓词逻辑方法表述下面问题积木世界的问题。（定义谓词、描述状态、定义操作、给出操作序列） 3．请给出下列描述的语义网络表示： 1)11月5日，NBA常规赛火箭主场对阵小牛，火箭107-76大胜小牛。 2)张老师从9月至12月给自动化专业学生教授《自动控制原理》。李老师从10至12月给计算机专业学生教授《操作系统原理》。 3)树和草都是植物；树和草都有根和叶；水草是草，生活在水中；果树是树，会结果；苹果树是果树，结苹果。 4．请用相应谓词公式描述下列语句： 1)有的人喜欢足球、有的人喜欢篮球；有的人既喜欢足球又喜欢篮球。 2)喜欢编程的同学都喜欢计算机。 3)不是每个自控系的学生都喜欢编程。 4)有一个裁缝，他给所有不自己做衣服的人做衣服。 5)如果星期六不下雨，汤姆就会去爬山。 5．什么是谓词公式的解释？对于公式?x ?y (P(x)→Q(f(x),y)) D={1，2，3} 分别给出使公式为真和假的一种解释。 6．什么是合一？求出下面公式的最一般合一: P(f(y), y, x) P(x, f(a),z)。 7．把下面谓词公式化为子句集 ?x ?y (P(x,y)∨Q(x,y))→R(x,y)) ?x (P(x) →?y(P(y)∧R(x,y))

?x (P(x)∧?y(P(y) →R(x,y))) 8．证明下面各题中，G是否是F的逻辑结论？ F1: ?x (P(x) →?y(Q(y)→L(x,y))) F2: ?x (P(x)∧?y(R(y) →L(x,y))) G: ?x (R(x) →~Q(x)) F1: ?z (~B(z)→?y(D(z,y)∧C(y))) F2: ?x (E(x)∧A(x)∧?y (D(x,y) →E(y))) F3: ?y(E(y) →~B(y)) G: ?z (E(z) ∧C(z)) 9．已知：John, Mike, Sam是高山俱乐部成员。高山俱乐部成员都是滑雪运动员或登山运动员（也可以都是）。登山运动员不喜欢雨。滑雪运动员都喜欢雪。凡是Mike喜欢的，John就不喜欢。凡是Mike 不喜欢的，John就喜欢。 Mike喜欢雨和雪。问：高山俱乐部是否有一个成员，他是登山运动员，但不是滑雪运动员？如果有，他是谁？10．为什么说归结式是其亲本子句的逻辑结论？ 11．何为完备的归结策略？有哪些归结策略是完备的？ 12．何谓搜索？有哪些常用的搜索方法？盲目搜索与启发式搜索的根本区别是什么？13．用状态空间法表示问题时，什么是问题的解？什么是最优解？在图搜索算法中，OPEN 表和CLOSED表的作用是什么？f(x)有何不同含义？ 14．宽度优先搜索和深度优先搜索有何不同？在何种情况下，宽度优先搜索优于深度优先搜索，何种情况反之？ 15．什么是启发式搜索，g(x)与h(x)各有什么作用？A*算法的限制条件是什么？

人工智能期末试题及答案完整版

人工智能期末试题及答案完整版 Prepared on 21 November 2021

xx学校 2012—2013学年度第二学期期末试卷考试课程：《人工智能》考核类型：考试A卷考试形式：开卷出卷教师：考试专业：考试班级：一单项选择题（每小题2分，共10分） 1.首次提出“人工智能”是在（D ）年 2. 人工智能应用研究的两个最重要最广泛领域为：B A.专家系统、自动规划 B. 专家系统、机器学习 C. 机器学习、智能控制 D. 机器学习、自然语言理解 3. 下列不是知识表示法的是 A 。 A：计算机表示法B：“与/或”图表示法 C：状态空间表示法D：产生式规则表示法 4. 下列关于不确定性知识描述错误的是 C 。 A：不确定性知识是不可以精确表示的 B：专家知识通常属于不确定性知识 C：不确定性知识是经过处理过的知识 D：不确定性知识的事实与结论的关系不是简单的“是”或“不是”。 5. 下图是一个迷宫，S0是入口，S g是出口，把入口作为初始节点，出口作为目标节点，通道作为分支，画出从入口S0出发，寻找出口Sg的状态树。根据深度优先搜索方法搜索的路径是 C 。 A：s0-s4-s5-s6-s9-sg B：s0-s4-s1-s2-s3-s6-s9-sg C：s0-s4-s1-s2-s3-s5-s6-s8-s9-sg D：s0-s4-s7-s5-s6-s9-sg 二填空题（每空2分，共20分） 1.目前人工智能的主要学派有三家：符号主义、进化主义和连接主义。 2. 问题的状态空间包含三种说明的集合，初始状态集合S、操作符集合F以及目标状态集合G 。 3、启发式搜索中，利用一些线索来帮助足迹选择搜索方向，这些线索称为启发式(Heuristic)信息。

人工智能大作业

人工智能基础大作业 —－－－八数码难题学院：数学与计算机科学学院班级：计科14—1 姓名:王佳乐学号：１2 2０1６、12、20 一、实验名称八数码难题得启发式搜索二、实验目得八数码问题:在3×3得方格棋盘上,摆放着1到８这八个数码,有1个方格就是空得，其初始状态如图1所示,要求对空格执行空格左移、空格右移、空格上移与空格下移这四个操作使得棋盘从初始状态到目标状态. 要求：1、熟悉人工智能系统中得问题求解过程; 2、熟悉状态空间得启发式搜索算法得应用； 3、熟悉对八数码问题得建模、求解及编程语言得应用。三、实验设备及软件环境 1.实验编程工具：VC＋+ 6、0 2.实验环境：Wｉndoｗs7 64位四、实验方法：启发式搜索 1、算法描述 1.将Ｓ放入open表,计算估价函数f(ｓ)

2.判断oｐeｎ表就是否为空，若为空则搜索失败,否则，将opeｎ表中得第一个元素加入cｌｏse表并对其进行扩展（每次扩展后加入ｏpen表中得元素按照代价得大小从小到大排序，找到代价最小得节点进行扩展）注:代价得计算公式ｆ(n)=d（ｎ）+ｗ（n)、其中f（n)为总代价，d(n）为节点得度,w（ｎ)用来计算节点中错放棋子得个数. 判断i就是否为目标节点,就是则成功，否则拓展i，计算后续节点f（j），利用f（j)对oｐeｎ表重新排序 2、算法流程图： 3、程序源代码：＃ｉncluｄｅ＜stdｉｏ、ｈ> # iｎclude＜strｉng、h> # include # iｎclude〈stｄliｂ、ｈ＞ tyｐeｄef ｓtruct nodｅ｛ ?int i,cost,ｄeｇree，eｘp，fａthｅr； ?ｉnt a［3]［３]; ?ｓtｒｕct nｏde ＊bef，＊late；

人工智能大作业

第一章 1.3 什么是人工智能？它的研究目标是什么？人工智能（Artificial Intelligence），英文缩写为AI。它是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门新的技术科学。研究目标：人工智能是计算机科学的一个分支，它企图了解智能的实质，并生产出一种新的能以人类智能相似的方式做出反应的智能机器，该领域的研究包括机器人、语言识别、图像识别、自然语言处理和专家系统等。 1.7 人工智能有哪几个主要学派？各自的特点是什么？主要学派：符号主义，联结主义和行为主义。 1.符号主义：认为人类智能的基本单元是符号，认识过程就是符号表示下的符号计算，从而思维就是符号计算； 2.联结主义：认为人类智能的基本单元是神经元，认识过程是由神经元构成的网络的信息传递，这种传递是并行分布进行的。 3.行为主义：认为，人工智能起源于控制论，提出智能取决于感知和行动，取决于对外界复杂环境的适应，它不需要只是，不需要表示，不需要推理。 1.8 人工智能有哪些主要研究和应用领域？其中有哪些是新的研究热点？ 1.研究领域：问题求解，逻辑推理与定理证明，自然语言理解，自动程序设计，专家系统，机器学习，神经网络，机器人学，数据挖掘与知识发现，人工生命，系统与语言工具。 2.研究热点：专家系统，机器学习，神经网络，分布式人工智能与Agent，数据挖掘与知识发现。第二章 2.8 用谓词逻辑知识表示方法表示如下知识： (1)有人喜欢梅花，有人喜欢菊花，有人既喜欢梅花又喜欢菊花。三步走：定义谓词，定义个体域，谓词表示定义谓词 P(x)：x是人 L(x,y)：x喜欢y y的个体域：{梅花，菊花}。将知识用谓词表示为： (?x)(P(x)→L(x, 梅花)∨L(x, 菊花)∨L(x, 梅花)∧L(x, 菊花)) (2) 不是每个计算机系的学生都喜欢在计算机上编程序。定义谓词 S(x)：x是计算机系学生

人工智能作业

1、用谓词逻辑知识表示方法表示如下知识： (1) 有人喜欢梅花，有人喜欢菊花，有人既喜欢梅花又喜欢菊花。解：定义谓词 P(x)：x 是人。 L(x,y)：x 喜欢y 其中，y 的个体域是{梅花，菊花}。将知识用谓词表示为： (Ex )(P(x)→L(x, 梅花)∨L(x, 菊花)∨L(x, 梅花)∧L(x, 菊花) (2) 不是每个计算机系的学生都喜欢在计算机上编程序。解：定义谓词 S(x)：x 是计算机系学生 L(x, pragramming)：x 喜欢编程序 U(x,computer)：x 使用计算机将知识用谓词表示为： ? (Ex) (S(x)→L(x, pragramming)∧U(x,computer)) 2. 请用语义网络表示如下知识：高老师从3月到7月给计算机系的学生讲“计算机网络”课。 3. 什么是产生式系统？它由哪几个主要部分组成？答：产生式系统是指以产生式知识表示方法和产生式推理方法所实现的系统。J 具体而言，就是一组产生式一起相互配合，协同作用，一个产生式生成的结论可以供另一个产生式作为已知事实使用，以解决问题，这样的系统称为产生式系统。它是由规则库、综合数据库和推理机三个部分组成。 4. 判断以下子句集是否为不可满足 {P(x)∨Q(x )∨R(x), ﹁P(y)∨R(y), ﹁ Q(a), ﹁R(b)} 老师讲课事件 7月 8月高老师讲课计算机网络计算机学生 ISA Subject Start End Object Action Caurse

5. 证明G是F的逻辑结论 F: (?x)(?y)(P(f(x))∧(Q(f(y))) G: P(f(a))∧P(y)∧Q(y) 解：(1) 先将F和?G化成子句集：S={P(a,b), ?P(x,b)} 再对S进行归结： {a/x} 所以，G是F的逻辑结论P(a,b) -P(x,b) NIL P(x) v Q(x) v R(x) ?Q(a) ?R(b) P(x) v R(x) P(x) NIL ?P(y) ?P(y) v R(y) a/x b/y a/x , b/y

人工智能大作业

人工智能大作业人工智能课程考查论文学号姓名系别年级专业人工智能大作业 (1)什么是人工智能, 人工智能(Artificial Intelligence) ，英文缩写为AI。它是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门新的技术科学。人工智能是计算机科学的一个分支，它企图了解智能的实质，并生产出一种新的能以人类智能相似的方式做出反应的智能机器，该领域的研究包括机器人、语言识别、图像识别、自然语言处理和专家系统等。人工智能的定义可以分为两部分，即“人工”和“智能”。“人工”比较好理解，争议性也不大。有时我们会要考虑什么是人力所能及制造的，或者人自身的智能程度有没有高到可以创造人工智能的地步，等等。但总的来说，“人工系统”就是通常意义下的人工系统。人工智能是计算机学科的一个分支，二十世纪七十年代以来被称为世界三大尖端技术之一(空间技术、能源技术、人工智能)。也被认为是二十一世纪(基因工程、纳米科学、人工智能)三大尖端技术之一。这是因为近三十年来它获得了迅速

的发展，在很多学科领域都获得了广泛应用，并取得了丰硕的成果，人工智能已逐步成为一个独立的分支，无论在理论和实践上都已自成一个系统。人工智能(Artificial Intelligence，AI)是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门新的技术科学。人工智能从诞生以来，理论和技术日益成熟，应用领域也不断扩大，但没有一个统一的定义。 (2)简述人工智能的研究内容与研究目标、人工智能的研究途径和方法、人工智能的研究领域。 A. 人工智能的研究内容: 1、搜索与求解: 为了达到某一目标而多次地进行某种操作、运算、推理或计算的过程。事实上，搜索是人在求解问题时而不知现成解法的情况下所采用的一种普遍方法。许多问题(包括智力问题和实际工程问题)的求解都可以描述为或归结为对某种图或空间的搜索问题。搜索技术就成为人工智能最基本的研究内容 2、学习与发现: 学习与发现是指机器的知识学习和规律发现。事实上，经验积累能力、规律发现能力和知识学习能力都是智能的表现 3、知识与推理: 知识就是力量，知识就是智能，发现客观规律，运用知识解决问题都是有智能的表现，而且是最为基本的一种表现。发现规律和运用知识本身还需要知识，因此知识是智能的基础和源泉。研究面向机器的知识表示形式和基于各种表示的机器推理技术:知识表示要求便于计算机的接受、存储、处理和运用，机器的推理方式与知识的表示又息息相关 4、发明与创造:

人工智能作业三(答案)

作业三 1. 下列两个一阶逻辑的语句有什么问题？如果错误，请给出正确的表示: (a) ) ( ) (x Tall x xBoy∧ ? (要表达的意思: 所有的男孩都是高的) (b) ) ( ) (x Tall x xBoy? ? (要表达的意思：一些男孩是高的) [Answer]: ) ( ) (x Tall x xBoy? ? ) ( ) (x Tall x xBoy∧ ? 2.已知如下的两个命题“任何一个选了人工智能(AI)课程的人都是聪明的”，“任何一门课只要教授人工智能相关知识它就是人工智能(AI)课程”，其相应的一阶逻辑表达式如下： ? x (? y AI course(y) ∧ Takes(x,y)) ? Smart(x) ? x (? y AI topic(y) ∧ Teaches(x,y)) ? AI course(x) 现在已知事实：John选了课程CS3243，CS3243课教授的推理知识属于人工智能相关知识，请将该事实表达成一阶逻辑句子，并且将该语句转换成CNF的形式，然后用归结算来证明“john是聪明的”。 [Answer]: CNF形式： ) 3243 , ( ) , 3243 ( ) ( _CS John Takes Inference CS Teaches Inference topic AI∧ ∧

3.考虑从一副标准的52张纸牌（不含大小王）中分发每手5张牌的扑克牌域。假设发牌人是公平的。 (a)在联合概率分布中共有多少个原子事件（即，共有多少种5张手牌的组合）？每个原子事件的概率是多少？ (b)拿到大同花顺（即同花的A、K、Q、J、10）的概率是多少？四同张（4张相同的牌，分别为4种花色）的概率是多少？ [Answer]: (a) C552,1/C552 (b) 4/C552, C113C148/C552 4.文本分类是基于文本内容将给定的一个文档分类成固定的几个类中的一类。朴素贝叶斯模型经常用于这个问题。在朴素贝叶斯模型中，查询（query）变量是这个文档的类别，而结果（effect）变量时语言中每个单词的存在与否；假设文档中单词的出现是独立的，单词的出现由文档类别决定。 1）给定一组已经被分类的文档，准确解释如何构造这样的模型。 2）准确解释如何分类新文档。 3）题目中的条件独立性假设合理吗？请讨论。 [Answer]: 1) P(category|document)= P(document|category)P(category)/P(document) 2)P(document|category),P(category)根据已有条件可以统计计算出，因此，给定一个新的测试文档，只需将P(document|category)P(category)最大的category赋给该文档即可。 3）不合理，单词之间不具有独立性。 5.“三一”重工想某工程投标，计划采取两种策略：一种是投高标，中标概率为0.2，不中标概率为0.8；另一种是投低标，中标与不中标的概率均为0.5。投标

人工智能作业答案(中国矿大)

1把以下合适公式化简为合取范式的子句集：（1）? (?x)(?y)(?z){P(x) ? (?x)[Q(x, y) ? R(z)]} （2）( ?x)( ?y){{P(x) ∧ [Q(x) ∨ R(y)]} ? (?y)[P(f(y)) ? Q(g(x))]} (3) (?x)( ?y){P(x) ∧ [Q(x)∨ R(y)]}? (?y){[P(f(y))? Q(g(y))]? (?x)R(x)} (1) ??(?x)( ?y)( ?z){P(x) ? (?x)[Q(x,y) ? R(z)]} ??(?x)( ?y)( ?z){ ?P(x) ∨ ( ?x)[?Q(x,y) ∨ R(z)]} ? (?x)( ?y)( ?z){ P(x) ∧ (? x)[Q(x,y) ∧?R(z)]} ? P(A) ∧ [Q(f(y,z), y) ∧?R(z)] ? {P(A), Q(f(y,z),y), ∧?R(w)} （2)? (?x)(?y){{P(x) ∧ [Q(x) ∨ R(y)]} ? (?y)[P(f(y)) ? Q(g(x))]} ? (?x)(?y){?{P(x) ∧ [Q(x) ∨ R(y)]} ∨(?y)[?P(f(y)) ∨ Q(g(x))]} ? (?x)(?y){?P(x) ∨ [?Q(x) ∧?R(y)] ∨ (?w)[?P(f(w)) ∨ Q(g(x))]} ? (?x){?P(x) ∨ [?Q(x) ∧?R(h(x))] ∨ (?w)[?P(f(w)) ∨ Q(g(x))]} ? [?P(x) ∨?Q(x) ∨?P(f(w)) ∨ Q(g(x))] ∧ [?P(x) ∨?R(h(x)) ∨?P(f(w)) ∨ Q(g(x))] ? {?P(x1) ∨?Q(x1) ∨?P(f(w1) ∨ Q(g(x1)),

东南大学软件学院研究生人工智能期末大作业

研究生课程考试成绩单（试卷封面）任课教师签名：日期：注：1. 以论文或大作业为考核方式的课程必须填此表，综合考试可不填。 “简要评语”栏缺填无效。 2.任课教师填写后与试卷一起送院系研究生秘书处。 3. 学位课总评成绩以百分制计分。

一、基本技术介绍 1、智能Agent （1）概念：Agent能够通过传感器感知环境，通过执行器的动作作用于环境。在Agent的概念框架下，AI的任务就是设计和建造理性的Agent，所以人们更为关心的是理性Agent。理性Agent对每一个可能的感知序列，根据已知的感知序列提供的证据和Agent具有的先验知识，理性Agent应该选择能使其性能度量最大化的行动。（2）特点：从感知序列到行动的理想映射，在很多情形下有可能设计一个好的、紧凑的Agent 来实现映射。一个真正的智能Agent在有足够时间去学习调整的条件下，应当在各种类型环境下做出成功的行动（自主性）。（3）结构：从传感器中将感知送到程序，运行程序，并将程序的行动选择送到作用体，这样就完成了一次Agent的工作过程。Agent、结构和程序三者间关系为：Agent=结构+程序。（4）环境：Agent施加行动于环境中，环境反过来又为Agent提供感知。不同的环境要求用不同的Agent程序与之对应。（5）AI与agent：在智能 agent的概念框架下，AI的任务就是设计和建造理性的、适合不同任务和环境特征的各种agent，由此将AI领域的各部分内容加以组织使它们有机联系在一起 2、基于知识的Agent （1）概念：智能获得不是靠反射机制而是对知识的内部表示进行操作的推理过程，在AI的世界里，这种智能方法体现在基于知识的Agent上。用逻辑作为支持基于知识的Agent的一类通用表示。基于知识的Agent的核心部件是知识库，知识库是一个语句集合。这些语句用知识表示语言表达。（2）基于知识的Agent的程序概述：基于知识的Agent用感知信息作为输入，返回一个行动。Agent维护一个知识库KB，该知识库在初始化时就包括了一些背景知识。每次调用Agent程序，做三件事。首先，Agent告诉（TELL）知识库它感知到的内容。然后询问（ASK）知识库应该执行什么行动。在恢复该查询的过程中，可能要对关于世界的当前状态、可能行动序列的执行结果进行大量推理。最后，Agent程序用TELL告诉知识库它所选择的行动，并执行该行动。 3、学习Agent （1）概念：Agent任何部件的性能都可通过从数据中进行学习，进而改进执行未来任务时的性能。改进及其改进所用的技术依赖于四个主要因素：要改进哪一个部件、Agent具备什么样的预备知识、数据和部件使用什么样的表示法、对学习可用的反馈是什么。（2）学习的反馈：在无监督学习中，在不提供显示反馈的情况下，Agent学习输入中的模式，最常见的无监督学习任务是聚类。在强化学习中，Agent在强化序列（奖赏和惩罚组合的序列）中学习。在监督学习中，Agent观察某些“输入—输出”对，学习从输入到输出的映射函数。 4、一阶逻辑（1）概念：一阶逻辑是一种形式推理的逻辑系统，是一种抽象推理的符号工具。功能就是将自然事物给符号化以为体系的确立奠定语言基础。（2）命题逻辑与一阶逻辑：一阶逻辑表示语言，它比命题逻辑表达能力更强。在命题逻辑中，研究的基本单位是简单命题，对简单命题不再进行分解，并且不考虑命题之间的内在联

人工智能作业一

作业一 1.对于下列活动，分别给出任务环境的PEAS描述，并按照 2. 3.2节列出的性质进行分析: (a) (b) (c) 2.先建立一个完整的搜索树，起点是S,终点是G,如下图,节点旁的数字表示到达目标状态的距离，然后用以下方法表示如何进行搜索。

图一首先，我们画出图一对应的完整的搜索树(按节点字母从小到大顺序依次画出)： (a).深度优先: 我们知道深度优先搜索是无信息搜索，按照编程的习惯，下图中深度优先搜索的顺序是按照节点的A-G的排序进行的 (b).广度优先: 我们知道一般的广度优先搜索也是无信息搜索，按照编程的习惯，下图中广度优先搜索的顺序同样是是按照节点的A-G的排序进行的

(c).爬山法: 对于爬山法我们需要了解的是，它是简单的循环过程，不断向最优方向移动。该算法不需要维护搜索树，当前的节点的数据结构只需要记录当前状态和目标函数值。此外，爬山法不会考虑与当前状态不相邻的状态。从S出发，与S邻近最佳的状态为B，依次往下，一旦找到目标状态则算法终止，这也就是为什么爬山法容易陷入局部最优。 (d).最佳优先: 最佳优先算法的结点是基于评价函数f(n)去扩展的，评估价值最低的结点首先选择进行扩展。最佳优先算法和一致代价搜索算法实现类似，不同的是最佳优先是根据f值而不是根据g值对优先级队列排队。

3.图二是一棵部分展开的搜索树，其中树的边记录了对应的单步代价，叶子节点标注了到达目标结点的启发式函数的代价值，假定当前状态位于结点A。图二 (a)用下列的搜索方法来计算下一步需要展开的叶子节点。注意必须要有完整的计算过程，同时必须对扩展该叶子节点之前的节点顺序进行记录： 1.贪婪最佳优先搜索：首先，贪婪最佳优先算法是试图扩展离目标最近的节点，它只用到启发信息，也就是f(n)=h(n)。如图，h(B)是未知的，但是根据三角不等式，我们可以知道7<=h(B)<=13。因此，先扩展C结点。 2.一致代价搜索一致性代价搜索扩展的是路径消耗最小的结点。所以一致代价搜索接下来扩展结点的顺序为BDEFGHC 3.A*树搜索 A*搜索对结点的评估结合了g(n)，即到达此结点已经花费的代价，和h(n)，从该结点到目标结点所花的代价:f(n)=g(n)+h(n)。由于都是从A结点开始扩展，所以对于下一步可扩展的结点的f(D)=18，f(C)=21,10<=f(B)<=16。因此，当先扩展B结点，否则先扩展D结点。 (b) 讨论以上三种算法的完备性和最优性。贪婪最佳优先搜索试图扩展离目标最近的结点，理由是这样可以很快找到解。贪婪最佳优先搜索于深度优先搜索类似，即使是有限状态空间，他也是不完备的，容易陷入死胡同或者导致死循环；一致代价搜索按结点的最优路径顺序扩展结点，这是对任何单步代价函数都是最优的算法，它不再扩展深度最浅的结点。一致代价搜索与宽度优先搜索类似，是完备的； A*搜索是完备的，此外，A*算法对于任何给定的一致的启发函数都是效率最优的。 4.给定一个启发式函数满足h(G)=0,其中G是目标状态，证明如果h是一致的，那么它是可采纳的。一致性（单调性）的定义：如果对于每个结点n和通过任意行动a生成的n的每个后继结点n’，从结点n到

人工智能大作业解读

实现遗传算法的0-1背包问题求解目录摘要 (2) 一．问题描述 (2) 二．遗传算法特点介绍 (2) 三．使用基本遗传算法解决0- 1背包问题 (3) 四．基本遗传算法解决0- 1背包问题存在的不足 (4) 五．改进的遗传算法解决0- 1背包问题 (6) 六．心得体会 (9) 七．参考文献 (10) 八．程序代码 (10)

摘要：研究了遗传算法解决0-1背包问题中的几个问题： 1）对于过程中不满足重量限制条件的个体的处理,通过代换上代最优解保持种群的进化性 2）对于交换率和变异率的理解和处理方法,采用逐个体和逐位判断的处理方法 3）对于早熟性问题,引入相似度衡量值并通过重新生成个体替换最差个体方式保持种群多样性。4）一种最优解只向更好进化方法的尝试。通过实际计算比较表明,本文改进遗传算法在背包问题求解中具有很好的收敛性、稳定性和计算效率。通过实例计算，表明本文改进遗传算法优于简单遗传算法和普通改进的遗传算法。关键词：遗传算法；背包问题；优化一、问题描述 0-1背包问题属于组合优化问题的一个例子，求解0-1背包问题的过程可以被视作在很多可行解当中求解一个最优解。01背包问题的一般描述如下：给定n个物品和一个背包，物品i的重量为Wi，其价值为Vi，背包的容量为C。选择合适的物品装入背包，使得背包中装入的物品的总价值最大。注意的一点是，背包内的物品的重量之和不能大于背包的容量C。在选择装入背包的物品时，对每种物品i只有两种选择：装入背包或者不装入背包，即只能将物品i装入背包一次。称此类问题为0/1背包问题。其数学模型为： 0-1背包问题传统的解决方法有动态规划法、分支界限法、回溯法等等。传统的方法不能有效地解决0-1背包问题。遗传算法（Genetic Algorithms）则是一种适合于在大量的可行解中搜索最优（或次优）解的有效算法。二、遗传算法特点介绍: 遗传算法(Genetic Algorithm, GA)是1962年Holland教授首次提出了GA算法的思想是近年来随着信息数据量激增，发展起来的一种崭新的全局优化算法，它借用了生物遗传学的观点，通过自然选择、遗传、变异等作用机制，实现各个个体的适应性的提高。基本遗传算法求解步骤： Step 1 参数设置：在论域空间U上定义一个适应度函数f(x)，给定种群规模N，交叉率P c 和变异率P m，代数T； Step 2 初始种群：随机产生U中的N个染色体s1, s2, …, s N，组成初始种群S={s1, s2, …, s N}，置代数计数器t=1； Step 3计算适应度：S中每个染色体的适应度f() ； Step 4 判断：若终止条件满足，则取S中适应度最大的染色体作为所求结果，算法结束。Step 5 选择-复制：按选择概率P(x i)所决定的选中机会，每次从S中随机选定1个染色体并将其复制，共做N次，然后将复制所得的N个染色体组成群体S1； Step 6 交叉：按交叉率P c所决定的参加交叉的染色体数c，从S1中随机确定c个染色体，配对进行交叉操作，并用产生的新染色体代替原染色体，得群体S2；

文档之家

人工智能大作业解读

人工智能大作业

西电人工智能大作业

人工智能作业一答案

人工智能大作业

人工智能大作业实验

人工智能试题

人工智能课程大作业

人工智能导论1-4章作业

人工智能期末试题及答案完整版

人工智能大作业

人工智能大作业

人工智能作业

人工智能大作业

人工智能作业三(答案)

最新人工智能期末试题及答案完整版(最新)

人工智能作业答案(中国矿大)

东南大学软件学院研究生人工智能期末大作业

人工智能作业一

人工智能大作业解读