人工智能爬山法搜索(仅供参考).doc

人工智能爬山法搜索（仅供参考）

一、问题描述
设X∈Ω(Rn),f(X)是定义在Ω上的函数, 记f: Ω → R, 求Xmax={X∈Ω|任取Y∈Ω→f(Y)≤f(X)}.
·具体问题:求出f(x,y)=1/(x*x + y*y + 2)的最优解.
·要求:计算过程可视化.
二、问题分析
这个问题用"爬山法搜索"(最速下降法)的方法可以求得最大值.
该函数的图形是一三维图形,很难直观地从平面图上去分析,所以
现从函数的特性分析,首先引入梯度的概念:
梯度:函数f(x,y)在点P(x,y)的梯度定义为grad(f)=fx(x,y)i+fy(x,y)j,是f(x,y)在该点增长最快的方向.(fx(x,y)是f(x,y)在P点对X轴的偏导数,fy(x,y)是f(x,y)在P点对Y轴的偏导数.)
梯度的模:||grad(f)||=sqrt(fx(x,y)*fx(x,y)+fy(x,y)*fy(x,y)),(sqrt()表示开平方根函数).
由此,可以知道函数f(x,y)的最大值在沿着梯度方向寻找时,搜索的速度最快 .
三、算法描述(c语言伪代码)
x = x0; y = x1; e = 0.001;
fg = sqrt( fx(x,y) * fx(x,y) + fy(x,y) * fy(x,y) );
while(fg > e)
{
x = x + pace * fx(x,y);
y = y + pace * fy(x,y);
xx = fx(x,y);
yy = fy(x,y);
fg = sqrt( xx * xx + yy * yy );
}
四、具体实现
环境:Visual C++ 6.0
·控制部分
为了使搜索过程的每一步都可见,用时钟中断来实现.
定义变量
变量名 说明int tid 所开时钟的id号int speed 时钟中断的间隔
bool Tbegin 开始/结束标志
bool Tsuspend 暂停/继续标志
开始/结束:OnStart()用来初始化各变量,并开始搜索过程.
如果Tbegin为True,开时钟中断——SetTimer(tid,speed,NULL),并将开关标签改为"结束".
如果Tbegin为False,关时钟中断——KillTimer(tid),并将开关标签改为"开始".
暂停/继续:OnSuspend()用来暂停搜索过程.
如果Tsuspend为True,关闭当前时钟中断——KillTimer(tid),并将开关标签改为"继续".
如果Tsuspend为False,新开一个时钟中断,但不初始化各变量——SetTimer(++tid,speed,NULL),将标签改为"暂停".
·搜索部分
因为搜索过程是重复进行相同的步骤,可用OnTimer()函数实现这一操作.如果||grad(f)||大于精度e,就再求出新的x,y值;如果||grad(f)||小于精度e,则取当前点的x,y值,其函数值即为最大值.
·可视化部分
坐标转换
为了便于分析,设置以下取值范围:
X的取值范围为:[-4,4];Y的取值范围为:[-4,4]的方形区域,所以取
原点坐标: sx=100,sy=300
X轴终点坐标:hx=678,hy=300 长度:628
Y轴终点坐标:vx=50,vy=100 长度:200
X轴长度/Y轴长度 = 3.14
2.画曲线
屏幕上坐标点(sx+i,sy+j) 实际(x,y)值:
x = i * 3.14 / (hx-sx) i∈[0,hx-sx]
y = f(x) j=int((vy-sy)*y+0.5)
代码实现:
for(int i=0; i<=hx-sx; i++)
{
double x=i*3.14/(hx-sx);
double y=f(x);
int j=int((vy-sy)*y+0.5);
pDC->LineTo(i+sx,sy+j);
}
3.划区间
用由浅到深的红色来划分依次得出的区间[a,b],将画笔颜色设置为RGB(rc,gc,bc).
在OnStart()函数中初始化画笔颜色参数为rc=255,gc=240,bc=240;
在OnTimer()函数中每执行一次操作,画笔颜色加深一次——gc-=10,bc-=10.
用for循环画线来给区间涂色,坐标点的转换如上所述.
代码实现:
for(int i=st; i<=ed; i++)
{
y=int((vy-sy)*f(3.14/(hx-sx)*i));
pDC->MoveTo(sx+i,sy-2);//减2以防将坐标线覆盖
pDC->LineTo(sx+i,sy+y);
}