蚁群算法解决指数正弦问题

指数正弦组合优化问题Byhero鹏摘要：对指数正弦组合优化问题分别采用了牛顿法及蚁群算法两种方法进行解决。重点强调智能优化问题在解决一些数学问题上的重要性。本文阐述蚁群算法的思想，并利用基于网格划分策略的连续域蚁群算法解决所提出的指数正弦组合优化问题。分析了普通优化方法与智能优化方法之间的区别，并指出了它们之间存在的一些不足。关键词：优化，蚁群算法，牛顿法，指数正弦组合前言当今时代，科学迅猛发展，寻找解决问题的最优化方法则是科学发展的动力之一。在人类的发展的历程中，大自然是人类一切思想的源泉，自然界的许多自适应优化现象不断给人以启示，生物的各种行为就使寻多在人类看起来高度复杂的优化问题得到完美的解决。蚁群算法就是人类模仿蚂蚁觅食而产生的一种仿生优化方法。生物学家通过对蚂蚁的长期观察研究发现，每只蚂蚁的智能并不高，看起来没有集中的指挥，但它们却能协同工作，依靠群体的力量发挥出超出个体的智能。于是，人们就对蚂蚁的这种行为，进而形成了蚁群算法。蚁群算法最初是由意大利学者DorigoM于1991年提出的，如今，蚁群算法的研究已深入到多个应用领域，并由离散域范围内的研究逐步拓展到了连续域范围内的研究。针对指数正弦组合优化问题中的复杂函数，我们是想要求在连续域中求出其的最小值，并且竟可能的精确，由于蚁群算法最初是用来解决离散域组合优化问题，因此我们需要寻找一种稳定性良好的，能够解决连续域组合优化问题的算法。基于网格划分策略的连续域蚁群算法正是这样的一种算法，利用网格划分的思想，将变量区域打网格，在网格点上求目标函数的值，逐步比较目标函数的大小，从中选择较小者，以此较小者作为基点，缩小变量区间，重复搜索，直至满足所给精度为止。网格划分的思想，给了我们解决连续域问题的启示，就是不断地将连续区间划分成尽可能小的离散点，用以回归到离散域组合优化问题的蚁群算法。1.算法介绍本文运用牛顿法以及基于网格划分的连续域蚁群算法解决同一指数正弦组合优化问题miny=5@0・5xsin(30x)+的2xsin(20x)+6〈、xe[0,8]1.1牛顿法牛顿法的具体思想是，把非线性函数f(x)在x0出展开成泰勒级数，即有f(x)=f(X0)+(x-x0)fXx0)+(x-x0)2f\x0)/2!+,取其线性部分，作为非线性函数f(x)=0的近似方程，则有f(x)=f(x0)+(x-x0)f(x0)，解之x=x0-f(x0)，在把f，(x0)f(x)在x处进行泰勒展开，取其线性部分作为方程f(x)的近似解，如此进行下去，得牛顿迭代公式x〃+i=x〃-f(x〃)/f，(x〃)。不过需要注意的是，在每次迭代我们需要导数f'(x)主0。n本文是要解决指数正弦组合函数y=5e-0.5xsin(30x)+e0.2xsin(20x)+6的最小值问题，所以，利用牛顿法我们只有先函数y的所有极值点，也即利用牛顿迭代法求y'=-2.5e-0.5xsin30x+150e-0.5xcos30x+0.2e0.2xsin20x+20e0.2xcos20x=0在区间[0,8]内的所有解值X[N],并找出使函数值y(X[N])最小的X[k],也即解决了本组合优化问题。1.2蚁群算法本文针对指数正弦组合函数，采用基于网格划分策略的连续域蚁群算法，其具体思想为，对于给定的变量区间，在变量区域打网格，空间上的网格点对应于一个状态，蚂蚁在各个空间网格点之间移动，并根据各网格点处目标函数值的不同留下不同的信息量，以此影响下一批蚂蚁的移动方向，循环一段时间后，目标函数小的网格点出的信息量比较大，找出信息量较大的网格节点，并以此节点为基点缩小变量范围，在此点附近进行蚁群移动。不断重复这一过程，直到满足给定的跳出条件为止。下面给出本蚁群算法中要用到的一些状态的定义。第i个网格点处的信息量邙]；信息量更新方程:t[i]=(1-p)t[i]+Q/f，其中Q表示信息强度，P为信息挥发系数，用以表示信息素的挥发，f表示此时的目标函数值。(3)蚂蚁从第转移到第i个网格节点的转移概率p=t[i]/Ilt[i]i=1由此，基于网格划分策略的连续域蚁群算法的实现步骤如下：将变量X分成N等份，即有H=(xhigh-xlow)/N；若H<eps(eps为给定精度)，则算法停止，最优解为x=(xhigh+xlow)/2,否则，跳至第(3)步继续执行；循环次数Nc=0；给t[i]赋相同的值1，设置Q、p、NcMax的初始值；设置蚂蚁数为M，对每只蚂蚁按P=t[i]/»t[i]选择下一节点；蚂蚁移动后，按t[i]=(1-p)t[i]+Q/f修改信息量，并Nc=Nc+1；若Nc<NcMax，则跳转至第(4)步继续执行，否则，找出t[i]最大的元素，并记录此时网格节点的位置i，缩小变量的取值范围，令xhigh=xlow+(i+1)H,xlow=xlow+(i-1)H,跳转至第(1)步继续执行。2.程序流程框图2.1牛顿法程序流程图3.程序源代码3.1牛顿法源代码〃本程序尝试用牛顿迭代法寻求最优值#include<iostream>#include<math.h>#include<string>#include<iomanip>#include<windows.h>//为了使用窗口属性控制函数#defineN100usingnamespacestd;//全局变量声明doublex[N]={0};//用以存储所有解值//目标函数f(x)doubleFunction(doublex)(doubleY;Y=5*exp(-0.5*x)*sin(30*x)+exp(0.2*x)*sin(20*x)+6;returnY;}//目标函数的导函数f'(x)doubleDFunction(doublex)(doubley;y=-2.5*exp(-0.5*x)*sin(30*x)+150*exp(-0.5*x)*cos(30*x)+0.2*exp(0.2*x)*sin(20*x)+20*exp(0.2*x)*cos(20*x);returny;//目标函数f(x)的二次导函数f''(x)doubleDDFunction(doublex)(doubley;y=-4498.75*exp(-0.5*x)*sin(30*x)-150*exp(-0.5*x)*cos(30*x)-399.96*exp(0.2*x)*sin(20*x)+8*exp(0.2*x)*cos(20*x);returny;}//牛顿法解函数f(x)=0的近似值voidNewton()(cout<<"**尝试求解使方程y=5*exp(-0.5*x)*sin(30*x)+exp(0.2*x)*sin(20*x)+6有最小解的解值**"<<endl;doublex0,x1,eps,d;eps=10;staticintk=1;cout<<"请输入精度二=>”;cin>>eps;x0=0.0;〃循环寻找区间内的解值点while(x0<8)(doublexx;//将区间上限存入数组x[0]=0;x1=x0-DFunction(x0)/DDFunction(x0);d=fabs(x1-x0);xx=x0;//保存初始X0值〃利用牛顿迭代法解X0处的值while(d>eps)(x0=x1;x1=x0-DFunction(x0)/DDFunction(x0);d=fabs(x1-x0);}//将解值存入数值x[N]if(x1>0)(x[k]=x1;k++;}x0=xx+0.1;}〃将区间上限存入数组x[k+1]=8;}//主函数voidmain()(HANDLEhCon;hCon二GetStdHandle(STD_OUTPUT_HANDLE);〃控制台窗口信息CONSOLE_SCREEN_BUFFER_INFOInfo;〃获取控制台信息GetConsoleScreenBufferInfo(hCon,&Info);doubleMin=100;intK=0;〃调用函数NewtonNewton();〃找出区间端点及所有极值点处的最小值for(intk=0;k<N;k++)(if(Function(x[k])<Min)(Min=Function(x[k]);K=k;}}〃控制输出台信息SetConsoleTextAttribute(hCon,13);cout<<"目标函数最优解值x为：〃<<x[K]<<endl;cout<<"则最优目标值为:"<<Function(x[K])<<endl;〃恢复窗口原来属性SetConsoleTextAttribute(hCon,Info.wAttributes);}2.2蚁群算法源代码/*本程序利用蚁群算法的思想，解决无约束非线性最优化问题*/#include<iostream>#include<iomanip>#include<string>#include<time.h>#include<math.h>#include<windows.h>#defineN30//划分等份#defineM18//蚂蚁数量usingnamespacestd;//全局变量声明doubleQ;//信息强度doubleeps,rou;//rou为信息素挥发系数intNc,NcMax;//循环次数doubletao[N];//tao表示信息量，P表示状态转移概率doubleJJ[M][N];//JJ为禁忌表，用来记录蚂蚁当前走过的节点doublexlow,xhigh;//存储变量的上下限intRoute[M][N];//记录蚂蚁所走过的节点doubleX;〃函数声明voidInitData();//初始化数据doubleFunction(doublex);//非线性方程voidAntSolution();//蚁群算法实现//主函数voidmain()(cout<<"尝试求解使方程y=5*exp(-0.5*x)*sin(30*x)+exp(0.2*x)*sin(20*x)+6有最小解的解值x\n"<<endl;stringanswer;do(AntSolution();cout<<"还要进行测试吗yes/no?==>";getline(cin,answer);}while(answer=="yes");}//初始化数据voidInitData()(cout<<"请设置信息强度Q,循环次数NcMax,精度eps及信息素挥发系数rou的初始值，输入顺序为Q,NcMax,eps,rou==>”;cin>>Q>>NcMax>>eps>>rou;cin.ignore();}//非线性方程doubleFunction(doublex)(doubleY;Y=5*exp(-0.5*x)*sin(30*x)+exp(0.2*x)*sin(20*x)+6;returnY;}//蚁群算法实现voidAntSolution()(〃估计各变量取值范围cout<<"**输入变量的取值范围**\n"<<endl;doublelow,high;cout<<"变量的上下限二=>”;cin>>low>>high;xlow=low;xhigh=high;HANDLEhCon;//句柄hCon二GetStdHandle(STD_OUTPUT_HANDLE);〃控制台窗口信息CONSOLE_SCREEN_BUFFER_INFOInfo;〃获取控制台信息GetConsoleScreenBufferInfo(hCon,&Info);//将变量N等份doubleH;H=(xhigh-xlow)/N;InitData();//cout<<H<<endl;//cout<<eps;while(fabs(H)>eps)(//初始化信息量for(inti=0;i<N;i++)tao[i]=1;〃初始化蚂蚁的位置for(intk=0;k<M;k++)(for(i=0;i<N;i++)Route[k][i]=-1;srand(time(NULL));//获得随机时间种子}for(k=0;k<M;k++)(Route[k][0]=k%N;JJ[k][Route[k][0]]=1;//每只蚂蚁随机分布在各个节点}//对每只蚂蚁按状态转移概率选择下一结点do(ints=1;doubleP;doubleprand=0.05;//随机概率while(s<N)(for(intk=0;k<M;k++)(intp1rand=rand()%3000;prand二double(p1rand)/3001;//利用时间种子获取随机概率//cout<<prand<<endl;P=0;doublesum=0;〃计算所有节点上的信息量总和for(inti=0;i<N;i++)(sum+=tao[i];}//cout<<sum<<endl;〃计算概率，以确定蚂蚁将走的下一结点for(i=0;i<N;i++)(if(JJ[k][i]==0)//蚂蚁走过的节点不重复计算P+=tao[i]/sum;if(P>prand)(//cout<<P<<〃**〃<<i<<endl;break;}}JJ[k][i]=1;//对已走过的节点做标记Route[k][s]=i;//记录蚂蚁第s步走过的节点//cout<<i<<endl;}s++;}〃寻找最优寻优路线doubleMin1=10;intK;//用以确定哪只蚂蚁所走路线最优，并记录该蚂蚁所走路线用以更新信息素for(intk=0;k<M;k++)(doublesum1;for(inti=0;i<N;i++)(sum1+=Function(xlow+Route[k][s]*H);}if(sum1<Min1)(Min1=sum1;K=k;}}//更新信息素量for(inti=0;i<N;i++)tao[i]=(1-rou)*tao[i];for(i=0;i<N;i++)(tao[Route[K][i]]+=Q/Function(low+H*Route[K][i]);}Nc++;}while(Nc<NcMax);〃找出信息量最大的节点intI=0;doubleMax=0;for(i=0;i<N;i++)(if(tao[i]>Max)(Max=tao[i];I=i;//cout<<I<<endl;}}〃缩小变量区间范围xhigh=xlow+(I+1)*H;xlow=xlow+(I-1)*H;H=(xhigh-xlow)/N;//cout<<xhigh<<""<<xlow<<""<<H<<endl;}〃当区间范围足够小时进行输出X=(xhigh+xlow)/2;//控制输出信息的颜色SetConsoleTextAttribute(hCon,10);cout<<"最优解值x是==>"<<X<<endl;cout<<Function(X)<<endl;〃恢复原来窗口属性SetConsoleTextAttribute(hCon,Info.wAttributes);}4.运行界面程序的运行界面如图4.1及4.2所示，其中4.1是牛顿法的结果，4.2是蚁群算法的结果。g-D:\C4-^习\Debug\牛顿法解最优值问题-eke**尝试求解使方程y=5*exp<-0.5*x>*sin<30*x>+exp<0.2*x>*sin<20*x）有最小解的解值**柄输入精度==冲-00001目卷函蔓佐解值x为汩-572542妙是优目标25731Pressanykeytocontinue—搜狗拼音半二gu:xireoug七邛而昇右Kmw-txjzi-exe尝试求解使方程SF=5*exp<-0.5*x>*5in<30*x>+exp<0.2*x>*sin<20*x>+6有最小解的解值x**输入变量的取值范围**变量的上下限==冲8请设置信息强度。，循环次数NcMax,精度eps及信息素挥发系数fdu的初始值，输入顺序为Max,eps,pou==>10100Q.000010.1慑优解值x是==>。-1447511.91487Pressanykeytocontinue—搜狗拼音半;图4.2

5.计算结果由4中运行界面得知，经牛顿法得出的函数j=5-0.5Xsin(30x)+e0.2、sin(20x)+6的最小值是y(0.72542)=1.25731,而采用蚁群算法思想解出的结果为y(0.144751)=1.91487。经由matlab绘出目标函数的曲线图如图5.1所示。图5.1如上图所示，容易看出目标函数的最小值小于2。且经计算，目标函数的最小精确值为1.44085。与我们所得结果相比较，牛顿算法及蚁群算法得出的结果非常接近目标精确值，因此，两算法是有效的。6结束语本文完成了用牛顿法与蚁群算法解决指数正弦组合优化问题，由图5