题目1：z=2-exp[-(x2+y2)], x,y[-5,+5]，求函数最小值
（1）用遗传算法来做：
第一步：确定决策变量及其约束条件
s.t. -5<=x<=5
第二步：建立优化模型
y.^2)))+exp(-(x.^2--(2)(max =x f
第三步：确定编码方法，用长度为50位的二进制编码串来表示决策变量x
第四步：确定解码方法
y x ?---=1
2)5(550 第五步：确定个体评价方法
个体的适应度取为每次迭代的最小值的绝对值加上目标函数值，即 )(|)}(min{|)(x f x f x F +=
第六步：确定参数
本题种群规模n=30,迭代次数ger=200,交叉概率pc=0.65,变异概率pm=0.05
代码：
clear all;
close all;
clc;
tic;
ger=200;
pc=0.65;
pm=0.05;
% 生成初始种群
v=init_population(n,50);
[N,L]=size(v);
disp(sprintf('Number of generations:%d',ger)); disp(sprintf('Population size:%d',N));
disp(sprintf('Crossover probability:%.3f',pc)); disp(sprintf('Mutation probability:%.3f',pm));
% 待优化问题
xmin=-5;
xmax=5;
ymin=-5;
ymax=5;
f='-(2-exp(-(x.^2+y.^2)))';
[x,y]=meshgrid(xmin:0.1:xmax,ymin:0.1:ymax); vxp=x;
vzp=eval(f);
figure(1);
mesh(vxp,vyp,-vzp);
hold on;
grid on;
% 计算适应度，并画出初始种群图形x=decode(v(:,1:25),xmin,xmax);
y=decode(v(:,26:50),ymin,ymax);
fit=eval(f);
plot3(x,y,-fit,'k*');
title('(a)染色体的初始位置');
xlabel('x');
ylabel('y');
zlabel('f(x,y)');
% 迭代前的初始化
vmfit=[];
vx=[];
it=1; % 迭代计数器
% 开始进化
while it<=ger
% Reproduction(Bi-classist Selection)
vtemp=roulette(v,fit);
% Crossover
v=crossover(vtemp,pc);
% Mutation
M=rand(N,L)<=pm;
%M(1,:)=zeros(1,L);
v=v-2.*(v.*M)+M;
% Results
x=decode(v(:,1:25),xmin,xmax);
y=decode(v(:,26:50),ymin,ymax);
fit=eval(f);
[sol,indb]=max(fit); % 每次迭代中最优目标函数值v(1,:)=v(indb,:);
fit_mean=mean(fit); % 每次迭代中目标函数值的平均值vx=[vx sol];
vmfit=[vmfit fit_mean];
it=it+1;
end
%%%% 最后结果
disp(sprintf('\n')); %空一行
% 显示最优解及最优值
disp(sprintf('Maximum
found[x,f(x)]:[%.4f,%.4f,%.4f]',x(indb),y(indb),-sol));
% 图形显示最优结果
figure(2);
mesh(vxp,vyp,-vzp);
hold on;
grid on;
plot3(x,y,-fit,'r*');
title('染色体的最终位置');
xlabel('x');
ylabel('y');
zlabel('f(x,y)');
% 图形显示最优及平均函数值变化趋势
figure(3);
plot(-vx);
%title('最优,平均函数值变化趋势');
xlabel('Generations');
ylabel('f(x)');
hold on;
plot(-vmfit,'r');
hold off;
runtime=toc
运行结果：Maximum found[x,f(x)]:[0.0033,0.0017,1.0000] （2）用蚁群算法来做
代码:
% Ant main program
clear all;
close all;
clc;
tic;
Ant=100;
Ger=50;
xmin=-5;
xmax=5;
ymin=-5;
ymax=5;
tcl=0.05;
f='-(2-exp(-(x.^2+y.^2)))'; % 待优化的目标函数[x,y]=meshgrid(xmin:tcl:xmax,ymin:tcl:ymax); vxp=x;
vyp=y;
vzp=eval(f);
figure(1);
mesh(vxp,vyp,-vzp);
hold on;
% 初始化蚂蚁位置
for i=1:Ant
X(i,1)=(xmin+(xmax-xmin)*rand(1));
X(i,2)=(ymin+(ymax-ymin)*rand(1));
% T0----信息素,函数值越大,信息素浓度越大
T0(i)=exp(-(X(i,1).^2+X(i,2).^2))-2;
end
plot3(X(:,1),X(:,2),-T0,'k*');
hold on;
grid on;
title('蚂蚁的初始分布位置');
xlabel('x');
ylabel('y');
zlabel('f(x,y)');
% 开始寻优
for i_ger=1:Ger
P0=0.2; % P0----全局转移选择因子P=0.8; % P ----信息素蒸发系数
lamda=1/i_ger; % 转移步长参数
[T_Best(i_ger),BestIndex]=max(T0);
for j_g=1:Ant % 求取全局转移概率
r=T0(BestIndex)-T0(j_g);
Prob(i_ger,j_g)=r/T0(BestIndex);
end
for j_g_tr=1:Ant
if Prob(i_ger,j_g_tr) temp1=X(j_g_tr,1)+(2*rand(1)-1)*lamda; temp2=X(j_g_tr,2)+(2*rand(1)-1)*lamda; else temp1=X(j_g_tr,1)+(xmax-xmin)*(rand(1)-0.5); temp2=X(j_g_tr,2)+(ymax-ymin)*(rand(1)-0.5); end if temp1 temp1=xmin; end if temp1>xmax temp1=xmax; end if temp2 temp2=ymin; end if temp2>ymax temp2=ymax; end if -(2-exp(-(temp1.^2+temp2.^2)))>-(2-exp(-(X(j_g_tr,1).^2+X(j_g_tr,2).^2))) X(j_g_tr,1)=temp1; X(j_g_tr,2)=temp2; end end %信息素更新 for t_t=1:Ant T0(t_t)=(1-P)*T0(t_t)-(2-exp(-(X(t_t,1).^2+X(t_t,2).^2))); end [c_iter,i_iter]=max(T0); maxpoint_iter=[X(i_iter,1),X(i_iter,2)]; max_local(i_ger)=-(2-exp(-(X(i_iter,1).^2+X(i_iter,2).^2))); %将每代全局最优解存到max_global矩阵中 if i_ger>=2 if max_local(i_ger)>max_global(i_ger-1) max_global(i_ger)=max_local(i_ger); else max_global(i_ger)=max_global(i_ger-1); end else max_global(i_ger)=max_local(i_ger); end end % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % figure(2); mesh(vxp,vyp,-vzp); hold on; x=X(:,1); y=X(:,2); plot3(x,y,-eval(f),'b*'); hold on; grid on; title('蚂蚁的最终分布位置'); xlabel('x'); ylabel('y'); zlabel('f(x,y)'); figure(3); plot(1:Ger,-max_global,'b-') hold on; title('最优函数值变化趋势'); xlabel('iteration'); ylabel('f(x)'); grid on; [c_max,i_max]=max(T0); maxpoint=[X(i_max,1),X(i_max,2)] maxvalue=-(2-exp(-(X(i_max,1).^2+X(i_max,2).^2))) runtime=toc 结果：maxvalue =1.0000 题目2：利用蚁群算法求下面加权有向图中从A到G的最短路： 解： 第一步：初始化N只蚂蚁，也就是N条道路 第二步：初始化运行参数，开始迭代 第三步：在迭代步数范围之内，计算转移概率，如果小于全局转移概 率就进行小范围的搜索，否则就进行大范围的搜索 第四步：更新信息素，记录状态，准备进行下一次迭代 第五步：转第三步 第六步：输出结果 代码： function shortroad_ant_main % Ant main program clear all;close all;clc;%清屏 tic;%计时开始 Ant=50;Ger=100;%运行参数初始化 power=[0 5 3 100 100 100 100 100 100 100 100 100 100 100 100 100; 100 0 100 1 3 6 100 100 100 100 100 100 100 100 100 100; 100 100 0 100 8 7 6 100 100 100 100 100 100 100 100 100; 100 100 100 0 100 100 100 6 8 100 100 100 100 100 100 100; 100 100 100 100 0 100 100 3 5 100 100 100 100 100 100 100; 100 100 100 100 100 0 100 100 3 3 100 100 100 100 100 100; 100 100 100 100 100 100 0 100 8 4 100 100 100 100 100 100; 100 100 100 100 100 100 100 0 100 100 2 2 100 100 100 100; 100 100 100 100 100 100 100 100 0 100 100 1 2 100 100 100; 100 100 100 100 100 100 100 100 100 0 100 3 3 100 100 100; 100 100 100 100 100 100 100 100 100 100 0 100 100 3 5 100; 100 100 100 100 100 100 100 100 100 100 100 0 100 5 2 100; 100 100 100 100 100 100 100 100 100 100 100 100 0 6 6 100; 100 100 100 100 100 100 100 100 100 100 100 100 100 0 100 4; 100 100 100 100 100 100 100 100 100 100 100 100 100 100 0 3; 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 0]; [PM PN]=size(power); % 初始化蚂蚁位置 v=init_population(Ant,PN); v(:,1)=1;v(:,PN)=1;%始点和终点纳入路径 %把距离当信息素浓度 fit=short_road_fun(v,power); %距离越小越好，所以要和信息素浓度相对应。 T0 = max(fit)-fit; % 画出图形 figure(1);grid on;hold on; plot(fit,'k*'); title('(a)蚂蚁的初始位置'); xlabel('x');ylabel('f(x)'); % 初始化 vmfit=[];vx=[]; P0=0.2; % P0----全局转移选择因子 P=0.8; % P ----信息素蒸发系数 %C=[]; % 开始寻优 for i_ger=1:Ger lamda=1/i_ger; % 转移步长参数 [T_Best(i_ger),BestIndex]=max(T0);%最大信息素浓度 for j_g=1:Ant % 求取全局转移概率 r=T0(BestIndex)-T0(j_g);%与最佳的蚂蚁的距离 Prob(i_ger,j_g)=r/T0(BestIndex);%应该以多大的速率向它靠拢 end for j_g_tr=1:Ant if Prob(i_ger,j_g_tr) %局部转移----小动作转移 M=rand(1,PN) temp=v(j_g_tr,:)-2.*(v(j_g_tr,:).*M)+M; else %全局转移----大步伐转移 M=rand(1,PN) temp=v(j_g_tr,:)-2.*(v(j_g_tr,:).*M)+M; end %始点和终点重新加入。即不能在移动过程中发生改变。 temp(:,1)=1;temp(:,end)=1; if short_road_fun(temp,power) %记录 v(j_g_tr,:)=temp; end end %信息素更新，准备下一次迭代 fit=short_road_fun(v,power); T0 = (1-P)*T0+(max(fit)-fit);%信息素蒸发 [sol,indb]=min(fit); v(1,:)=v(indb,:);%记录本次迭代的状态 media=mean(fit); vx=[vx sol]; vmfit=[vmfit media]; end % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % %%%% 最后结果 disp(sprintf('\n')); %空一行 % 显示最优解及最优值 disp(sprintf('Shortroad is %s',num2str(find(v(indb,:)))));%num2str数据转换成字符。 disp(sprintf('Mininum is %d',sol)); v(indb,:) % 图形显示最优结果 figure(2);grid on;hold on; plot(fit,'r*'); title('蚂蚁的最终位置'); xlabel('x'); ylabel('f(x)'); % 图形显示最优及平均函数值变化趋势figure(3); plot(vx); title('最优,平均函数值变化趋势'); xlabel('Generations');ylabel('f(x)'); hold on;plot(vmfit,'r');hold off; runtime=toc%时间结束 end %% function fit=short_road_fun(v,power) [vm vn]=size(v); fit=zeros(vm,1);%记录每一条路径的距离for i=1:vm I=find(v(i,:)==1);%寻找在路径上的点 [Im,In]=size(I); for j=1:In-1 fit(i)=fit(i)+power(I(j),I(j+1));%求路径的距离end end end %% %Function init_population function v=init_population(n1,s1) v=round(rand(n1,s1));%初始化所有的蚂蚁 end 运行结果： Shortroad is 1 2 5 8 12 15 16 Mininum is 18 基于新的混合遗传算法的订单生产工序顺序相关的流水车 间调度问题研究 A novel hybrid genetic algorithm to solve the make-to-order sequence-dependent flow-shop scheduling problem Mohammad Mirabi ?S. M. T. Fatemi Ghomi ?F. Jolai 2013年5月29号收到该文献,2014年3月18号录取,2014年4月9日出版.作者（2014）.这篇文章在开放存取的https://www.doczj.com/doc/a314463706.html, 网站发表 摘要流水车间调度问题（FSP）用于处理m台机器n个工序的流水作业。尽管FSP是典 型的NP-hard问题，依然没有有效的算法以找到这个问题的最优解。为了减少库存，延迟和安装成本,在工作时间一定,序列相关的每台机器上解决流水车间调度排序问题，在这提出了一种有三个遗传算子的新型混合遗传算法（HGA）。该算法应用一种改进的方法来生成初始种群，并使用一种应用迭代交换过程改进初始解的改进启发式算法。我们认为订单式生产方式，工序间隔时间是基于最大安装成本的禁忌搜索算法的解。此外，与最近开发的启发式算法通过计算实验结果比较表明，该算法在解\的精度和效率方面表现出非常强的竞争力。 关键词:混合遗传算法流水作业调度序列相关 引言 流车间调度问题（FSP）作为在制造业研究的主要问题已经近七十年。在一个有M台机器的流水作业车间中有m个工位,每个工序又有一台或几台机器。此外，有n个工件在m个工位上依次加工。在经典的流水作业问题里，每个工位都有一台机器，这一领域的研究吸引了最多的人次。FSP的两个主要子问题是序列独立时间设置（SIST）和顺序相关时间设置（SDST）。SDST流水作业问题更具有现实意义，但是吸引的注意力却少得多，特别是2000年以前（Allahverdi等，2008） 在流水车间调度问题的目标是找到一个序列的机器加工的作业，以便一个给定的标准进行了优化。这里有n个工件在每台机器上操作的可能的顺序，以及（N！）*M个的可能处理顺序。流水作业调度的研究通常只参加置换序列，其中操作的处理顺序是所有机器。在这里，我们也采用这种限制。 最小化所有最大完工时间作业（成为完工期并通过的Cmax表示）是公知的，也是在文献M. Mirabi (&) Group of Industrial Engineering, Ayatollah Haeri University of Meybod, P.O. Box 89619-55133, Meybod, Iran e-mail: M.Mirabi@https://www.doczj.com/doc/a314463706.html, S. M. T. Fatemi Ghomi Department of Industrial Engineering, Amirkabir University of Technology, P.O. Box 15916-34311, Tehran, Iran e-mail: Fatemi@aut.ac.ir F. Jolai Department of Industrial Engineering, College of Engineering, University of Tehran, P.O. Box 14395-515, Tehran, Iran 动态蚁群遗传混合算法的研究及应用 （河北工程学院，河北邯郸056038） 摘要：蚁群算法是一种源于大自然生物世界的仿生类算法，该算法采用分布式并行计算和正反馈机制。易于与其他方法结合，具有很强的鲁棒性和适应性，但存在搜素时间长、易陷入局部最优解的缺点。为了克服这一缺点, 文中给出一种新的蚁群算法——动态蚂蚁遗传混合算法。在基本蚁群算法中引入变异机制, 采用最佳融合点评估策略来交叉地调用两种算法。动态地控制遗传算法与蚂蚁算法的调用时机，并设计了相应的信息素更新方法，有效减少了算法的冗余迭代次数，提高了搜索速度,同时引入迭代调整阈值控制算法后期的遗传操作和蚂蚁规模，加快了种群进化速度，从而更快地找到最优解。该法具有较快的收敛速度，节省计算时间，实验结果表明该方法是行之有效的。 关键词：蚁群算法; TSP问题; 遗传算法; 动态蚂蚁遗传混合算法 1 引言 蚁群算法 (Ant Colony Algorithms，ACO）又称蚂蚁算法。是一种用来在图中寻找优化路径的机率型技术。蚂蚁在寻找食物时，总是能找到较短的路径。受到蚁群系统信息共享机制的启发，意大利学者Macro Dorigo于1992年在他的博士论文中首次系统提出了蚁群算法，并成功地将该算法应用到求解旅行商问题（TSP)和二次分配问题（QAP)中。取得了一系列较好的实验结果。解决一些实际问题也有很好的效果。但蚁群算法同其它生物进化算法一样存在过早收敛易陷入局部极小值等问题。结合其它优化算法形成混合蚁群算法是克服这些缺点的有效手段。遗传算法(genetic algorithm，GA)以决策变量的编码作为运算对象，在优化过程中借鉴生物学中染色体和基因的概念，模拟自然界中生物和遗传进化等机理，通过个体适应度来进行概率选择操作，通过交叉变异产生新的个体，从而遗传算法具有较强的全局性。 为克服蚁群算法搜索速度慢、易陷入局部最优等缺点。本文提出了一种新的动态蚁群遗传混合算法(Dynamic Ant Algorithm -Genetic Algorithm，DAAGA)。该算法采用最佳融合点评估策略来交叉地调用两种算法，其框架是用蚂蚁算法的解作为遗传操作的种子，每当种 全局优化报告 ——遗传算法和蚁群算法的比较 某：X玄玄 学号：3112054023 班级：硕2041 1遗传算法 1.1遗传算法的发展历史 遗传算法是一种模拟自然选择和遗传机制的寻优方法。20世纪60年代初期，Holland教授开始认识到生物的自然遗传现象与人工自适应系统行为的相似性。他认为不仅要研究自适应系统自身，也要研究与之相关的环境。因此，他提出在研究和设计人工自适应系统时，可以借鉴生物自然遗传的基本原理，模仿生物自然遗传的基本方法。1967年，他的学生Bagley在博士论文中首次提出了“遗传算法”一词。到70年代初，Holland教授提出了“模式定理”，一般认为是遗传算法的基本定理，从而奠定了遗传算法的基本理论。1975年，Holland出版了著名的《自然系统和人工系统的自适应性》，这是第一本系统论述遗传算法的专著。因此，也有人把1975年作为遗传算法的诞生年。 1985年，在美国召开了第一届两年一次的遗传算法国际会议，并且成立了国际遗传算法协会。1989年，Holland的学生Goldberg出版了《搜索、优化和机器学习中的遗传算法》，总结了遗传算法研究的主要成果，对遗传算法作了全面而系统的论述。一般认为，这个时期的遗传算法从古典时期发展了现代阶段，这本书则奠定了现代遗传算法的基础。 遗传算法是建立在达尔文的生物进化论和孟德尔的遗传学说基 础上的算法。在进化论中，每一个物种在不断发展的过程中都是越来越适应环境，物种每个个体的基本特征被后代所继承，但后代又不完全同于父代，这些新的变化，若适应环境，则被保留下来；否则，就将被淘汰。在遗传学中认为，遗传是作为一种指令遗传码封装在每个细胞中，并以基因的形式包含在染色体中，每个基因有特殊的位置并控制某个特殊的性质。每个基因产生的个体对环境有一定的适应性。基因杂交和基因突变可能产生对环境适应性强的后代，通过优胜劣汰的自然选择，适应值高的基因结构就保存下来。遗传算法就是模仿了生物的遗传、进化原理，并引用了随机统计原理而形成的。在求解过程中，遗传算法从一个初始变量群体开始，一代一代地寻找问题的最优解，直到满足收敛判据或预先假定的迭代次数为止。 遗传算法的应用研究比理论研究更为丰富，已渗透到许多学科，并且几乎在所有的科学和工程问题中都具有应用前景。一些典型的应用领域如下： （1）复杂的非线性最优化问题。对具体多个局部极值的非线性最优化问题，传统的优化方法一般难于找到全局最优解；而遗传算法可以克服这一缺点，找到全局最优解。 （2）复杂的组合优化或整数规划问题。大多数组合优化或整数规划问题属于NP难问题，很难找到有效的求解方法；而遗传算法即特别适合解决这一类问题，能够在可以接受的计算时间内求得满意的近似最优解，如著名的旅行商问题、装箱问题等都可以用遗传算法得到满意的解。 机器学习大作业Revised on November 25, 2020 题目：机器学习 授课老师：韩红 基于BP 神经网络的非线性函数拟合 摘要：BP(Back Propagation)神经网络是 1986年由 Rumelhart和 McCelland 提出的，它是一种误差按反向传播的多层前馈网络，是目前应用最广泛的神经网络模型之一。 BP神经网络具有非常强的非线性映射能力，能以任意精度逼近任意连续函数，因此在人工智能的许多领域都得到了广泛的应用。 通常，BP算法是通过一些学习规则来调整神经元之间的连接权值，在学习过程中，学习规则以及网络的拓扑结构不变。然而一个神经网络的信息处理功能不仅取决于神经元之间的连接强度，而且与网络的拓扑结构（神经元的连接方式）、神经元的输入输出特性和神经元的阈值有关，因而神经网络模型要加强自身的适应和学习能力，应该知道如何合理地自组织网络的拓扑结构，知道改变神经元的激活特性以及在必要时调整网络的学习参数等。 1 BP神经网络概述 BP神经网络是一种多层前馈神经网络,该网络的主要特点是信号前向传递,误差反向传播。在前向传递中,输入信号从输入层经隐含层逐层处理, 直至输出层。每一层的神经元状态只影响下一层神经元状态。如果输出层得不到期望输出, 则转入反向传播,根据预测误差调整网络权值和阈值,从而使B P神经网络预测输出不断逼近期望输出。BP神经网络的拓扑结构如图 图1中, X1, X2, …, X n是BP神经网络的输入值, Y1, Y2, …, Y m是BP神经网络的预测值,ωij和ωjk为BP神经网络权值。从图2可以看出, BP神经网络可以看成一个非线性函数, 网络输入值和预测值分别为该函数的自变量和因变量。当输入节 作业 土规1101班刘迈克2011306200521 求下面加权有向图中从A到G的最短路径。 A B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 E3 F1 F2 G 5 3 1 3 6 8 7 6 6 5 8 3 3 3 8 4 2 2 2 1 3 3 3 5 5 2 6 6 4 3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 5 3 1 3 6 8 7 6 6 5 8 3 3 3 8 4 2 2 2 1 3 3 3 5 5 2 6 6 4 3 解： 基本思路： 第一步：确定决策变量及其约束条件。 第二步：建立优化模型。 第三步：确定编码方法。 第四步：确定解码方法。 第五步：确定个体评价方法。 第六步：设计遗传算子。 选择运算使用比例选择算子； 交叉运算使用单点交叉算子； 变异运算使用基本位变异算子。 第七步：确定遗传算法的运行参数。 程序： % n ---- 种群规模 % ger ---- 迭代次数 % pc ---- 交叉概率 % pm ---- 变异概率 % v ---- 初始种群（规模为n） % f ---- 目标函数值 % fit ---- 适应度向量 % vx ---- 最优适应度值向量 % vmfit ---- 平均适应度值向量 clear all; close all; clc; tic; % 生成初始种群 %power=[0 5 3 100 100 100 100 100; % 100 0 100 1 3 6 100 100; % 100 100 0 100 8 7 6 100; % 100 100 100 0 100 100 100 8; % 100 100 100 100 0 100 100 5; % 100 100 100 100 100 0 100 3; % 100 100 100 100 100 100 0 3; % 100 100 100 100 100 100 100 0]; power=[0 5 3 100 100 100 100 100 100 100 100 100 100 100 100 100; 100 0 100 1 3 6 100 100 100 100 100 100 100 100 100 100; 100 100 0 100 8 7 6 100 100 100 100 100 100 100 100 100; 一、粒子群算法 粒子群算法，也称粒子群优化算法（Particle Swarm Optimization），缩写为PSO，是近年来发展起来的一种新的进化算法(（Evolu2tionary Algorithm - EA）。PSO 算法属于进化算法的一种，和遗传算法相似，它也是从随机解出发，通过迭代寻找最优解，它也是通过适应度来评价解的品质，但它比遗传算法规则更为简单，它没有遗传算法的交叉(Crossover) 和变异(Mutation) 操作，它通过追随当前搜索到的最优值来寻找全局最优。这种算法以其实现容易、精度高、收敛快等优点引起了学术界的重视，并且在解决实际问题中展示了其优越性。 优化问题是工业设计中经常遇到的问题,许多问题最后都可以归结为优化问题.为了解决各种各样的优化问题,人们提出了许多优化算法,比较著名的有爬山法、遗传算法等.优化问题有两个主要问题:一是要求寻找全局最小点,二是要求有较高的收敛速度.爬山法精度较高,但是易于陷入局部极小.遗传算法属于进化算法(EvolutionaryAlgorithms)的一种,它通过模仿自然界的选择与遗传的机理来寻找最优解.遗传算法有三个基本算子:选择、交叉和变异.但是遗传算法的编程实现比较复杂,首先需要对问题进行编码,找到最优解之后还需要对问题进行解码,另外三个算子的实现也有许多参数,如交叉率和变异率,并且这些参数的选择严重影响解的品质,而目前这些参数的选择大部分是依靠经验.1995年Eberhart博士和kennedy博士提出了一种新的算法;粒子群优化(ParticalSwarmOptimization-PSO)算法.这种算法以其实现容易、精度高、收敛快等优点引起了学术界的重视,并且在解决实际问题中展示了其优越性. 粒子群优化(ParticalSwarmOptimization-PSO)算法是近年来发展起来的一种新的进化算法(Evolu2tionaryAlgorithm-EA).PSO算法属于进化算法的一种,和遗传算法相似,它也是从随机解出发,通过迭代寻找最优解,它也是通过适应度来评价 网络教育学院 《数据挖掘》课程大作业 题目：题目一：Knn算法原理以及python实现 姓名： XXX 报名编号： XXX 学习中心：奥鹏XXX 层次：专升本 专业：计算机科学与技术 第一大题：讲述自己在完成大作业过程中遇到的困难，解决问题的思路，以及相关感想，或者对这个项目的认识，或者对Python与数据挖掘的认识等等，300-500字。 答： 数据挖掘是指从大量的数据中通过一些算法寻找隐藏于其中重要实用信息的过程。这些算法包括神经网络法、决策树法、遗传算法、粗糙集法、模糊集法、关联规则法等。在商务管理，股市分析，公司重要信息决策，以及科学研究方面都有十分重要的意义。数据挖掘是一种决策支持过程，它主要基于人工智能、机器学习、模式识别、统计学、数据库、可视化技术，从大量数据中寻找其肉眼难以发现的规律，和大数据联系密切。如今，数据挖掘已经应用在很多行业里，对人们的生产生活以及未来大数据时代起到了重要影响。 第二大题：完成下面一项大作业题目。 2019秋《数据挖掘》课程大作业 注意：从以下5个题目中任选其一作答。 题目一：Knn算法原理以及python实现 要求：文档用使用word撰写即可。 主要内容必须包括： （1）算法介绍。 （2）算法流程。 （3）python实现算法以及预测。 （4）整个word文件名为 [姓名奥鹏卡号学习中心]（如 戴卫东101410013979浙江台州奥鹏学习中心[1]VIP ） 答： KNN算法介绍 KNN是一种监督学习算法，通过计算新数据与训练数据特征值之间的距离，然后选取K(K>=1)个距离最近的邻居进行分类判(投票法)或者回归。若K=1，新数据被简单分配给其近邻的类。 KNN算法实现过程 (1)选择一种距离计算方式, 通过数据所有的特征计算新数据与 机器学习大作业 题目机器学习大报告 学院电子工程学院 专业 学生姓名 学号 目录 第一章机器学习的基本理论及算法 (3) 1.1机器学习的基本理论 (3) 1.1.1 机器学习的概念 (3) 1.1.2 机器学习的发展历程 (3) 1.1.3 机器学习的模型 (4) 1.2机器学习主要算法 (5) 1.2.1 决策树算法 (5) 1.2.2 人工神经网络 (6) 1.2.3贝叶斯学习算法 (7) 1.2.4 遗传算法 (8) 1.2.5 支持向量机 (9) 第二章支持向量机（SVM）原理 (11) 2.1 SVM的产生与发展 (11) 2.2 统计学习理论基础 (12) 2.3 SVM原理 (12) 2.3.1．最优分类面和广义最优分类面 (13) 2.3.2 SVM的非线性映射 (16) 2.3.3．核函数 (17) 第三章支持向量机的应用研究现状 (19) 3.1 应用概述 (19) 3.2支持向量机的应用 (19) 3.2.1 人脸检测、验证和识别 (19) 3.2.2说话人/语音识别 (20) 3.2.3 文字／手写体识别 (20) 3.2.4 图像处理 (20) 3.2.5 其他应用研究 (21) 第四章基于SVM的实例及仿真结果 (23) 4.1 16棋盘格数据分类 (23) 4.2 UCI中iris数据分类 (25) 第一章机器学习的基本理论及算法 1.1机器学习的基本理论 1.1.1 机器学习的概念 机器学习是人工智能的一个分支，是现代计算机技术研究一个重点也是热点问题。顾名思义，机器学习就是计算机模仿人类获取知识的模式，通过建立相应的模型，对外界输入通过记忆"归纳"推理等等方式，获得有效的信息和经验总结，进而不断的自我完善，提高系统的功能。目前，机器学习的定义尚不统一，不同专业背景的学者出于不同的立场，对于机器学习的看法是不同的。下面主要介绍两位机器学习专业研究者赋予机器学习的定义。兰利（https://www.doczj.com/doc/a314463706.html,ngley）认为：“机器学习是一门人工智能的科学，该领域的主要研究对象是人工智能，特别是如何在经验学习中改善具体算法的性能”。米切尔（T.M.Mitchell）在其著作《机器学习》中谈到“机器学习”关注的问题是“计算机程序如何随着经验积累自动提高自身的性能”，也就是主要指的是归纳学习，另外“分析学习和增强学习也是学习的一个不可或缺组成部分”。两位学者的观点类似，都把机器学习看成是计算机或人工智能的一个分支学科，都强调的是归纳学习算法。 机器学习在人工智能领域中是一个相对比较活跃的研究领域,其研究目的就是要促进机器像人样可以源源不断获取外界的知识,建立相关学习的理论,构建学习系统,并将这些发明应用于各个领域。 1.1.2 机器学习的发展历程 机器学习(machine learning)是继专家系统之后人工智能应用的又一重要研究领域，也是人工智能和神经计算的核心研究课题之一。作为人工智能研究的一个新崛起的分支，机器学习的发展历程大至可分为如下几个时期： （1）热烈时期：20 世纪50 年代的神经模拟和决策理论技术,学习系统在运行时很少具有结构或知识。主要是建造神经网络和自组织学习系统, 学习表现为阈值逻辑单元传送信号的反馈调整。 （2）冷静时期：20 世纪60 年代早期开始研究面向概念的学习, 即符号学习。 比较专家系统、模糊方法、遗传算法、神经网络、蚁群算法的特点及其适合解决的实际问题 一、专家系统(Expert System) 1，什么是专家系统？ 在日常生活中大家所认知的“专家”一般都拥有某一特定领域的大量专业知识，以及丰富的实际经验。在解决问题时，专家们通常拥有一套独特的思维方式，能较圆满地解决一类困难问题，或向用户提出一些建设性的建议等。 专家系统一般定义为一个具有智能特点的计算机程序。 它的智能化主要表现为能够在特定的领域内模仿人类专家思维来求解复杂问题。因此，专家系统必须包含领域专家的大量知识，拥有类似人类专家思维的推理能力，并能用这些知识来解决实际问题。 专家系统的基本结构如图1所示，其中箭头方向为数据流动的方向。 图1 专家系统的基本组成 专家系统通常由知识库和推理机两个主要组成要素。 知识库存放着作为专家经验的判断性知识,例如表达建议、 推断、 命令、 策略的产生式规则等, 用于某种结论的推理、 问题的求解,以及对于推理、 求解知识的各种控制知识。 知识库中还包括另一类叙述性知识, 也称作数据,用于说明问题的状态,有关的事实和概念,当前的条件以及常识等。 专家系统的问题求解过程是通过知识库中的知识来模拟专家的思维方式的，因此，知识库是专家系统质量是否优越的关键所在，即知识库中知识的质量和数量决定着专家系统的质量水平。一般来说，专家系统中的知识库与专家系统程序是相互独立的，用户可以通过改变、完善知识库中的知识内容来提高专家系统的性能。 推理机实际上是一个运用知识库中提供的两类知识,基于木某种通用的问题求解模型,进行自动推理、 求解问题的计算机软件系统。 它包括一个解释程序, 用于决定如何使用判断性知识推导新的知识, 还包括一个调度程序, 用于决定判断性知识的使用次序。 推理机的具体构造取决于问题领域的特点,及专家系统中知识表示和组织的方法。 推理机针对当前问题的条件或已知信息，反复匹配知识库中的规则，获得新的结论，以得到问题求解结果。在这里，推理方式可以有正向和反向推理两种。正向推理是从前件匹配到结论，反向推理则先假设一个结论成立，看它的条件有没有得到满足。由此可见，推理机就如同专家解决问题的思维方式，知识库就是通过推理机来实现其价值的。 人机界面是系统与用户进行交流时的界面。通过该界面，用户输入基本信息、回答系统提出的相关问题，并输出推理结果及相关的解释等。 综合数据库专门用于存储推理过程中所需的原始数据、中间结果和最终结论，往往是作为暂时的存储区。解释器能够根据用户的提问，对结论、求解过程做出说明，因而使专家系统更具有人情味。 知识获取是专家系统知识库是否优越的关键，也是专家系统设计的“瓶颈”问题，通过知识获取，可以扩充和修改知识库中的内容，也可以实现自动学习功能。 2，专家系统的特点 在功能上, 专家系统是一种知识信息处理系统, 而不是数值信息计算系统。在结构上, 专家系统的两个主要组成部分 – 知识库和推理机是独立构造、分离组织, 但又相互作用的。在性能上, 专家系统具有启发性, 它能够运用专家的经验知识对不确定的或不精确的问题进行启发式推理, 运用排除多余步骤或减少不必要计算的思维捷径和策略；专家系统具有透明性, 它能够向用户显示为得出某一结论而形成的推理链, 运用有关推理的知识(元知识)检查导出结论的精度、一致性和合理性, 甚至提出一些证据来解释或证明它的推理；专家系统具有灵活性, 它能够通过知识库的扩充和更新提高求解专门问题的水平或适应环境对象的某些变化,通过与系统用户的交互使自身的性能得到评价和监护。 3，专家系统适合解决的实际问题 专家系统是人工智能的一个应用，但由于其重要性及相关应用系统之迅速发展，它已是信息系统的一种特定类型。专家系统一词系由以知识为基础的专家系统(knowledge-based expert system)而来，此种系统应用计算机中储存的人类知识，解决一般需要用到专家才能处理的问题，它能模仿人类专家解决特定问题时的推理过程，因而可供非专家们用来增进问题解决的能力，同时专家们也可把它视为具备专业知识的助理。由于在人类社会中，专家资源确实相当稀少，有了专家系统，则可使此珍贵的专家知识获得普遍的应用。 专家系统技术广泛应用在工程、科学、医药、军事、商业等方面，而且成果相当丰硕，甚至在某些应用领域，还超过人类专家的智能与判断。其功能应用领 第一章 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、利用遗传算法求出下面函数的极小值：z=2-exp[-(x2+y2)], x,y∈[-5,+5] 解： 第一步确定决策变量及其约束条件：x,y∈[-5,+5] 第二步建立优化模型：min z（x,y）=2-exp[-(x2+y2)] 第三步确定编码方法。用长度为50位的二进制编码串来表示决策变量x,y。第四步确定解码方法。解码时将50位长的二进制编码前25位转换为对应的十进制整数代码，记为x，后25位转换后记为y。 第五步确定个体评价方法。 第六步设计遗传算子。选择运算用比例选择算子，交叉运算使用单点交叉算子，变异运算使用基本位变异算子。 第七步确定遗传算法的运行参数。 实现代码： % n ---- 种群规模 % ger ---- 迭代次数 % pc ---- 交叉概率 % pm ---- 变异概率 % v ---- 初始种群（规模为n） % f ---- 目标函数值 % fit ---- 适应度向量 % vx ---- 最优适应度值向量 % vmfit ---- 平均适应度值向量 clear all; close all; clc; tic; n=30; ger=200; pc=0.65; pm=0.05; % 生成初始种群 v=init_population(n,50); [N,L]=size(v); disp(sprintf('Number of generations:%d',ger)); disp(sprintf('Population size:%d',N)); disp(sprintf('Crossover probability:%.3f',pc)); disp(sprintf('Mutation probability:%.3f',pm)); 全局优化报告——遗传算法和蚁群算法的比较 姓名：玄玄 学号：3112054023 班级：硕2041 1遗传算法 1.1遗传算法的发展历史 遗传算法是一种模拟自然选择和遗传机制的寻优方法。20世纪60年代初期，Holland教授开始认识到生物的自然遗传现象与人工自适应系统行为的相似性。他认为不仅要研究自适应系统自身，也要研究与之相关的环境。因此，他提出在研究和设计人工自适应系统时，可以借鉴生物自然遗传的基本原理，模仿生物自然遗传的基本方法。1967年，他的学生Bagley在博士论文中首次提出了“遗传算法”一词。到70年代初，Holland教授提出了“模式定理”，一般认为是遗传算法的基本定理，从而奠定了遗传算法的基本理论。1975年，Holland出版了著名的《自然系统和人工系统的自适应性》，这是第一本系统论述遗传算法的专著。因此，也有人把1975年作为遗传算法的诞生年。 1985年，在美国召开了第一届两年一次的遗传算法国际会议，并且成立了国际遗传算法协会。1989年，Holland的学生Goldberg 出版了《搜索、优化和机器学习中的遗传算法》，总结了遗传算法研究的主要成果，对遗传算法作了全面而系统的论述。一般认为，这个 时期的遗传算法从古典时期发展了现代阶段，这本书则奠定了现代遗传算法的基础。 遗传算法是建立在达尔文的生物进化论和孟德尔的遗传学说基础上的算法。在进化论中，每一个物种在不断发展的过程中都是越来越适应环境，物种每个个体的基本特征被后代所继承，但后代又不完全同于父代，这些新的变化，若适应环境，则被保留下来；否则，就将被淘汰。在遗传学中认为，遗传是作为一种指令遗传码封装在每个细胞中，并以基因的形式包含在染色体中，每个基因有特殊的位置并控制某个特殊的性质。每个基因产生的个体对环境有一定的适应性。基因杂交和基因突变可能产生对环境适应性强的后代，通过优胜劣汰的自然选择，适应值高的基因结构就保存下来。遗传算法就是模仿了生物的遗传、进化原理，并引用了随机统计原理而形成的。在求解过程中，遗传算法从一个初始变量群体开始，一代一代地寻找问题的最优解，直到满足收敛判据或预先假定的迭代次数为止。 遗传算法的应用研究比理论研究更为丰富，已渗透到许多学科，并且几乎在所有的科学和工程问题中都具有应用前景。一些典型的应用领域如下： （1）复杂的非线性最优化问题。对具体多个局部极值的非线性最优化问题，传统的优化方法一般难于找到全局最优解；而遗传算法可以克服这一缺点，找到全局最优解。 （2）复杂的组合优化或整数规划问题。大多数组合优化或整数规划问题属于NP难问题，很难找到有效的求解方法；而遗传算法即特别 《人工智能》课程学习体会兼论遗传算法在最优化问题的应用与发展 一、《人工智能》课程学习体会 1．课程学习历程 这学期，在《人工智能》课程学习中，我们以中国大学MOOC网上浙江工业大学王万良教授主讲的《人工智能导论》课程为主。课上老师给我们讲解了一些课程中的难点，课下老师发放了很多的人工智能课外阅读资料，供我们参考学习。 在学习的过程中，我们先对智能有了初步了解，之后再谈人工智能的概念。要想实现人工智能，就需要把我们人的思维形式化，于是学习了谓词逻辑知识表示，之后是产生式，然后是概率论和数理统计的一些内容。掌握了这些之后，我们就可以根据知识去解决问题了。可是怎么去解决，如何去推出结果，又是一个问题，于是我们学习了一些推理方法，如模糊推理等。按照智能的定义，那么现在已经基本实现智能了。即实现了智能=知识+智力，虽然不是真正意义上的智能。虽然现在可以去处理一些问题了，但是很明显的，它的效率非常的低，甚至于有些问题找到答案花费的时间特别长，是我们无法接受的。于是我们学习了如A*算法、遗传算法、粒子群优化算法、蚁群算法等一些加快处理问题的算法。最后，我们学习了神经网络、专家系统、机器学习和智能体系等内容。对于这些学习的知识，基本上还处于一个了解的水平，要想实际应用还需要更深入的学习。 课下，我们也看了一些和人工智能的书籍，诸如《浪潮之巅》，向我们讲述了科技公司像IBM，微软，英特尔等公司的兴衰；《智能革命》向我们讲述了AI 与我们的生活密切相关，并且越来越离不开智能。通过阅读这些课外读物，也使得我们对人工智能有了更深的理解与思考。 2．课程学习体会与感悟 学习完主要课程之后，给我的第一感觉就是：“哎！怎么还没有学呢！课程就结束了”。有这样的感觉主要还是受到疫情的影响，在家不能像在学校一样学的那么精细。很多的知识几乎是走一个概念便草草离场了，同时，人工智能这门课程本身涉及的知识面也比较广，如讲到神经网络的时候提到了生物学中的神经元、突触等这些结构，想一下子掌握这些内容是不可能的。 另一个方面则是，人工智能的应用领域非常之多，诸如机器学习，专家系统等，每一部分都是可以单独拿出来作为深入学习的方向的。因此，现在的学习，只是对人工智能有了一个初步的了解，想要入门还需要学习更多的内容，还需要投入更多的时间。 二、遗传算法在最优化问题的应用与发展 1.遗传算法简述 遗传算法在调节控制系统参数中的应用 【摘要】自动化控制系统多采用PID 控制器来调节系统稳定性和动态性，PID 的 Kp,Ki,Kd 参数需要合理选择方能达到目标。遗传算法是一种模拟生物进化寻求最优解的有效算法，本文通过利用GAbx 工具箱实现对控制电机的PID 进行参数优化，利用matlab 的仿真功能可以观察控制效果。 1. 直流伺服电机模型 1.1物理模型 图1 直流伺服电机的物理模型 αu ---电枢输入电压（V ） a R ---电枢电阻（Ω） S L ---电枢电感（H ） q u ---感应电动势（V ） g T ---电机电磁转矩（N m ?） J---转动惯量（2m kg ?） B---粘性阻尼系数（s m N ??） g i ---流过电枢的电流（A ） θ---电机输出的转角（rad ） 1.2传递函数 利用基尔霍夫定律和牛顿第二定律得出电机基本方程并进行拉布拉斯变换 ) ()()()()()()()()()()(2s s K s U K s I s T s Bs s Js s T s I s L R s I s U s U e q t a g g a a a a q a θθθ?=?=?+?=?+?=- 式中：t K 为电机的转动常数（m N ?）A ；e K 为感应电动势常数（s V ?）rad 图2 直流伺服电机模型方框图 消去中间变量得系统的开环传递函数： s K K B Js R s L K s U s s G C t a d t a ]))([() () ()(+++= = θ 系统参数如下：s m uN B m mg J ??=?=51.3,23.32 A m N K K uH L R e t a a )(03.0,75.2,4?===Ω= 2. PID 校正 图3 PID 校正 s K s K K s G d i p c ++ =)( Kp,Ki,Kd 为比例，积分，微分系数 令Kp=15、Ki=0.8 、Kd=0.6 M 文件：J=3.23E-6; B=3.51E-6; Ra=4; La=2.75E-6; Kt=0.03; num= Kt; den=[(J*La) ((J*Ra)+(La*B)) ((B*Ra)+Kt*Kt) 0]; t=0:0.001:0.2; step(num,den,t); Kp=15; Ki=0.8; Kd=0.6; numcf=[Kd Kp Ki]; dencf=[1 0]; numf=conv(numcf,num); denf=conv(dencf,den); [numc,denc]=cloop(numf,denf); t=0:0.001:0.04; step(numc,denc,t); matlab 进行仿真，我们可以看出不恰当的PID 参数并不能使系统达到控制系统的要求， WORD格式 人工智能实验报告 学号： 姓名： 实验名称：遗传算法 实验日期：2016.1.5 【实验名称】遗传算法 【实验目的】 掌握遗传算法的基本原理，熟悉遗传算法的运行机制，学会用遗传算法来求解问题。【实验原理】 遗传算法（GeneticAlgorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。 遗传算法是从代表问题可能潜在的解集的一个种群开始的，而一个种群则由经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体。在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度大小选择个体，并借助于自然遗传学的遗传算子进行组合交叉和变异，产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码，可以作为问题近似最优解。 遗传算法程度流程图为： 【 实】 ：已知f(x)=x*sin(x)+1，x[0,2],求f(x)的最大值和最小值。 数据结构： structpoptype { doublegene[length];//染色体 doublerealnumber;//对应的实数x doublefitness;//适应度 doublerfitness;//相对适应度 doublecfitness;//累计适应度 }; structpoptypepopulation[popsize+1];//最后一位存放max/min structpoptypenewpopulation[popsize+1];// 染色体编码： x [ 因此 ，染色体由2 3位字节的二进制矢X 与二进）2之 间的映射如下： 22 i bb......bb2x '; 222102i i010 xx' 2 23 21 适应度函数： 由于要求f (x )的最值,所以适应 度函数即可为f (x )。但为了确保每个个体都有被选中的可能性，因此需要将所有适应为大于0的值。因此，设计 求最大值的适应度函数如下： eval max f(x)5xsinx6; 将最小化为求-f(x)的最大值，同理，设计最小值的适应度函数如下： evalfxxx min()5sin4; 种群大小： 本50，再进行种群初始化。 实验参数： 主要有迭代数，交叉概率，变异概率这三个参数。一般交叉概率在0.6-0.9范围内， 变异概率在0.01-0.1范主要代码如下： voidinitialize()//种群初始化 { srand(time(NULL)); 简单对比遗传算法与蚁群算法求解旅行商问题 简单对比遗传算法与蚁群算法求解旅行商问题 1、旅行商 1.1 旅行商问题简介 旅行商问题（Traveling Saleman Problem）又称作旅行推销员问题、货郎担问题等，简称为TSP问题，是最基本的路线问题，该问题是在寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径成本。最早的旅行商问题的数学规划是由Dantzig（1959）等人提出，规则虽然简单，但在地点数目增多后求解却极为复杂。 TSP问题最简单的求解方法是枚举法。它的解是多维的、多局部极值的、趋于无穷大的复杂解的空间，搜索空间是n个点的所有排列的集合，大小为（n-1）！。有研究者形象地把解空间比喻为一个无穷大的丘陵地带，各山峰或山谷的高度即是问题的极值。求解TSP，则是在此不能穷尽的丘陵地带中攀登以达到山顶或谷底的过程。 1.2 求解TSP方法简介 旅行推销员的问题属于NP-Complete的问题，所以旅行商问题大多集中在启发式解法。Bodin（1983）等人将旅行推销员问题的启发式解法分成三种： 1.2.1 途程建构法（Tour Construction Procedures） 从距离矩阵中产生一个近似最佳解的途径，有以下几种解法： （1）最近邻点法（Nearest Neighbor Procedure）：一开始以寻找离场站最近的需求点为起始路线的第一个顾客，此后寻找离最后加入路线的顾客最近的需求点，直到最后。 （2）节省法（Clark and Wright Saving）：以服务每一个节点为起始解，根据三角不等式两边之和大于第三边之性质，其起始状况为每服务一个顾客后便回场站，而后计算路线间合并节省量，将节省量以降序排序而依次合并路线，直到最后。 （3）插入法（Insertion procedures）：如最近插入法、最省插入法、随意插入法、最远插入法、最大角度插入法等。 1.2.2 途程改善法（Tour Improvement Procedure） 先给定一个可行途程，然后进行改善，一直到不能改善为止。有以下几种解法： （1）K-Opt(2/3 Opt)：把尚未加入路径的K条节线暂时取代目前路径中K条节线，并计算其成本（或距离），如果成本降低（距离减少），则取代之，直到无法改善为止，K通常为2或3。 （2）Or-Opt：在相同路径上相邻的需求点，将之和本身或其它路径交换且仍保持路径方向性，并计算其成本（或距离），如果成本降低（距离减少），则取代之，直到无法改善为止。 1.2.3 合成启发法（Composite Procedure） 先由途程建构法产生起始途程，然后再使用途程改善法去寻求最佳解，又称为两段解法（two phase method）。有以下几种解法： （1）起始解求解+2-Opt：以途程建构法建立一个起始的解，再用2-Opt的方式改善途程，直到不能改善为止。 人工智能：Artificial Intelligence，简称AI，主要研究如何使用人工的方法和技术，使用各种自动化机器或智能化机器模仿、延伸和扩展人的智能，实现某些机器的智能行为。 传统划分①符号主义学派②联结主义学派③行为主义学派现代1.符号智能流派2.计算智能流派3.群体智能流派 人工智能的基本技术：1知识表示技术2知识推理、计算和搜索技术3系统实现技术。 符号智能的表示是知识的表示，运算是基于知识表示的推理或符号操作，采用搜索方法进行问题求解，一般在问题空间上进行，计算智能的表示是对象表示，运算时给予对象的表示的操作或计算，采用搜索方法进行问题求解，一般是在解空间上进行。 人工智能的研究领域：定理证明、专家系统、模式识别、机器学习、计算智能、自然语言处理、组合调度问题。应用领域：难题求解、自动定理证明、自动翻译、智能管理、智能通信、智能仿真等。 人工智能的主要研究途径与方法：1功能模拟。符号推演2结构模拟。神经计算3行为模拟。控制进化 人工智能的研究目标及其意义：1目标：远期目标是要制造智能机器，即探索智能的基本机理，最终制造出和人有相似或相近智力和行为能力的综合智能系统；近期目标是实现机器智能，即研究如何使用现有的计算机具备更高的智能，在一定领域或在一定程度上去完成需要人的复杂脑力劳动才能完成的工作。2意义：普遍的计算机智能低下，无法满足社会需求；研究AI是当前信息化社会的迫切需求；智能化是自动化发展的必然趋势；研究AI，对人类自身的智能的奥秘也提供有益的帮助。 人工智能的基本内容：1从人工智能的定义出发包括（感知与交流的模拟，记忆，联想，计算，思维的模拟，输出效率或行为模拟2从知识工程的角度出发包括（知识的获取，知识的处理以及知识的运用） 人工智能诞生1956年夏，达特莫斯大学的研究会，麦卡锡提议正式采用了“AI”术语。发展：推理期，知识期，学习期ＡＩ的现状与发展趋势：１多种途径齐头并进，多种方法协作互补２新思想、新技术不断涌现，新领域新方向不断开拓3理论研究更加深入，应用研究愈加广泛4研究队伍日益壮大，社会影响越来越大。以上展现了AI繁荣景象和光明前景，虽有困难，问题和挑战，但前进和发展毕竟是大势所趋。 盲目搜索：无向导的搜索，也称穷举搜素。在搜索中，没有任何背景知识作指导，不考虑任何与解有关的信息，随机地或按预先规定的顺序（如广度优先和深度优先）机械地生成树的节点，并判断是否为解，直到找到解或证明问题无解为止。特点：搜索效率太低，所以在实际中往往是不可行的。启发函数：通过函数计算来评价每种选择的价值大小，用以指导搜索过程。 启发式搜索：利用问题本身的“启发性信息”不断地改变或调整搜索的方向，使搜索朝着问题本身最希望的方向进行，加速问题的求解并找到最优解。特点：重排OPEN表，选择最有希望的节点加以扩展。 盲目和启发搜索的的不同：对于较大或无限状态空间问题，盲目搜索效率太低，所以在实际当中往往是不可行的。启发式搜索广泛地应用于实际问题求解中，如博弈、机器学习、数据挖掘、智能检索等。 启发式搜索—全局择优算法：也叫做最好优先搜索，在启发性知识导航下的广度优先搜索，在OPEN表中保留所有已生成而为考察的节点，对其中的每个节点x计算启发函数h（x）,从全部节点中选出最优节点进行扩展，而不管这个结点出现的搜索树的什么地方。 局部择优：是启发性知识导航下的深度优先搜索，在OPEN 表中保留所有已生成为为考察的节点，对其中新生成的每个子节点x计算启发函数h(x),从全部子节点中选出最优节点进行扩展，其选择下一个要考察的结点的范围是刚刚生成的全部子节点。 在图搜索算法中，OPEN表，CLOSED表的作用各是什么OPEN表：专门登记已经生成但还没有考察的节点，即待考察节点。算法执行时总是从OPEN表的首部取出节点。CLOSED表：用来记录考察过的节点以及节点之间的关系，如每个节点指向父节点的编号（返回指针）。 广度优先搜索的特点：广度优先中OPEN表是一个队列，又称为宽度优先。广度优先策略是完备的，即如果问题的解存在，则它一定可以找到解，并且找到的解还是最优解。广度优先搜索策略与问题无关，具有通用性。缺点搜索效率低 深度优先搜索的特点：OPEN表为一个堆栈。深度优先又称纵向搜索。一般不能保证找到最优解。当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制，即有界深度优先搜索。最坏情况时，搜索空间等同于穷举。 广度优先搜索及深度优先搜索都是盲目搜索，其共同点是：1搜索从初始节点开始，先自上而下地进行搜索，寻找终止节点及端节点，然后再自下而上地进行可解性标记，一旦初始节点被标记为可解节点或不可解节点，搜索就不再继续进行；2搜索都是按确定路线进行的，当要选择一个节点进行扩展时，只是根据节点在与或树中所处的位置，而没有考虑要付出的代价，因而求得的解树不一定是代价最小的解树，即不一定是最优解树。 与或图表示的是问题空间，状态空间图是一个表述问题全部可能状态及相互关系的有向图。 图搜索模式的是人脑分析问题，解决问题的过程，它是基于领域知识的问题求解过程。搜索方式为树式搜索和线性搜索。遗传算法是一种什么样的算法？适合于解决哪一类的问题？遗传算法时人们从生物界按自然选择和有性繁殖、遗传变异的自然进化现象中得到启发，而设计出来的一种随机优化搜索算法。遗传算法适合解决先验知识缺乏，希望寻找最优解，搜索空间不连续的这一类问题，如机器学习、规划、聚类、控制、调度等领域的问题。适合解决先验知识缺乏，希望寻找最优解，搜索空间不连续的这一类问题，如机器学习、规划、聚类、控制、调度等领域的问题。 化子句集的过程：1消去蕴含词和等值词2使否定词仅作用于原子公式3适当改名使量词间不含同名指导变元4消去存在量词5消去全称量词6化公式为合取范式7适当改名使子句间无同名变元8消去合取词以子句为元素组成一个集合S。谓词逻辑归结过程：写出谓词关系公式→用反演法写出谓词表达式→ SKOLEM标准形→子句集S →对S中可归结的子遗传算法
动态蚁群遗传混合算法1
遗传算法和蚁群算法的比较
机器学习大作业
(整理)遗传算法作业
AI人工智能的几种常用算法概念
大工19秋《数据挖掘》大作业题目及要求答案
机器学习大作业
比较专家系统、模糊方法、遗传算法、神经网络、蚁群算法的特点及其适合解决的实际问题
人工智能大作业
遗传算法作业
遗传算法和蚁群算法的比较
人工智能导论学习体会及遗传算法应用
MATLAB遗传算法PID大作业.
人工智能遗传算法实验报告
简单对比遗传算法与蚁群算法求解旅行商问题
人工智能期末考试重点
相关主题
文本预览