【越飞越高讲堂3】函数的极值及其应用(附源码及讲解)
<P> </P><P>这几天创建了一个求函数极值的程序。</P>
<P>函数求极值，特别是求极小值，在很多方面都有应用。</P>
<P>看了《数值算法》的书后，颇有心得。其中的算法主要是Brent方法和黄金搜索法。因而根据其算法，编写了 LISP程序。首先，我用对话框编写了一个通用的求解函数极小值的程序。（只是一维的）命令:min.</P>
<P></P>
<P>后来，把它应用到CAD上，举了三个例子：</P>
<P>第一个例子：求两条曲线之间的最小距离。命令CPC.</P>
<P></P>
<P>第二个例子：求一条曲线的boungbox,（即包围盒）,命令:BBC.这个例子，对于在UCS下也成立。特别是对于spline，比用getboundingbox的方法准确很多。</P>
<P></P>
<P> </P>
<P>第三个例子：就是求公切线。有兴趣的不妨参考如下帖子。 </P>
<P><FONT face=Verdana><A href="http://bbs.mjtd.com/forum.php?mod=viewthread&tid=82900">http://bbs.mjtd.com/forum.php?mod=viewthread&tid=82900</A></FONT></P>
<P> </P>
<P> 其中有一种方法就是采取这个求极值的方法的。</P>
<P><SPAN style="mso-list: Ignore"><SPAN style="mso-fareast-font-family: 'Times new=" lang=EN-US Roman?? New?><SPAN style="mso-list: Ignore"><SPAN style="mso-fareast-font-family: 'Times new=" lang=EN-US Roman?? New?><SPAN style="mso-list: Ignore"><SPAN style="mso-fareast-font-family: 'Times new=" lang=EN-US Roman?? New?><SPAN style="mso-list: Ignore"><SPAN style="FONT: 7pt =" mso-fareast-font-family: EN-US? 7pt?=" lang="><SPAN 7pt?=" ?Times ? Roman:><?xml:namespace prefix = o /><o:p> </p></o:p></span></span></span></span></span></span></span></span></span></span> <p> </p> <p><font color=" face="幼圆" size="6" #ff0000?>源码公布：</FONT></P>
<P></P></SPAN></SPAN></SPAN></SPAN></SPAN></SPAN></SPAN></SPAN></SPAN> 本帖最后由 作者 于 2010-9-12 19:18:39 编辑 <br /><br />
<p class="MsoNormal">呵呵，这么多天了，仅仅4个人下载哦。</p>
<p class="MsoNormal"><?xml:namespace prefix = o ns = "urn:schemas-microsoft-com:office:office" /><o:p> </o:p></p>
<p class="MsoNormal">我继续谈谈函数的极值的求法和一些应用，特别是CAD应用上的思路。</p>
<p class="MsoNormal"> </p>
<p class="MsoNormal"></p>
<p class="MsoNormal"> </p>
<p class="MsoNormal"><font size="3"></font>
<p class="MsoNormal"><font size="3"></font></p>
<p class="MsoNormal"><o:p><font size="3"></font></o:p></p><font size="3"> <br/>
<p>首先，不得不说函数的极值问题是一个比较难的问题，特别是全局的极值问题。</p>
<p>一种启发式方法为：从独立自变量的各种不同初值开始，求出所有的局部极值，然后从中选出最大的或者最小的。二是对局部极值以一有限步长的扰动，然后分析由此计算出来的就结果，是稍有改进还是一直保持不变。关于模拟退火法，呵呵，太高级了，在lisp中很难实现。</p><br/>
<p>我在这个程序中，首先参考了《数值算法》的C程序部分，编写了LISP。</p>
<p>在这本书中讲到了几个方法：</p>
<p>1、 一维黄金分割搜索。经过研究，极值的折半搜索并不是有效的，最佳划界区间a<b<c应满足内点b与其中一个外点(如a)的距离比例为0.38197，而与另一外点的距离比例为0.6180399。这个思想就是在每一步划界中给定一个三点组，下一试探点取在较长区间段的0.38197的分割点，如果开始划界的三点组的各段没有按照黄金比率分割，那么逐次选择黄金分割点的进程很快收敛到合适的、自行重复的比率。这个搜索方法是线性的，即随着附加函数的计算，有效数字逐步线性增长。</p>
<p>2、 关于Brent方法，是超线性的，在技术上被称之为逆抛物线内插。其原理是通过拟抛物线内插法，逐步接近目标函数的最小值。</p>
<p>3、 一阶导数的一维搜索法，那就是采用一阶导数，沿着函数的递减方向前进，并综合了Brent方法，黄金分割搜索法。</p>
<p>4、 其他的还有几个方法，谈到了多维函数的极值问题。我留待以后讲解。</p>
<p>5、 其中还讲到了如何划界的方法，以及一个实现划界的函数mnbrak（即在一个区间内找到区间中间的点，并且这个点的函数值在这三点中最小）</p><br/>
<p>另外我自己也根据思路编写了一个折半的搜索方法，这个对上面的几种求解无效的情况下，显得很有效果。</p><br/>
<p>可能你有点不耐烦，因为你最关心的是如何跟CAD的结合问题。</p>
<p>CAD的图元之间的函数关系，常常不是规则的，那么显而易见的。因而对它们的求极值，求导，是一件很困难，甚至不可能的事情，因此，我们要综合运用多种方法。</p><br/>
<p>下面我分例子讲解我的思路。</p><br/>
<p>1、 两条曲线之间的最小距离.</p>
<p>这个问题如果是用其他方法，完全是有函数的，譬如arx的<font color="#0000ff">getclosestpointto</font>函数，就是用来求解两个曲线之间的最小距离的。但LISP中<font color="#0000ff">vlax-curve</font> 函数中没有提供，只是提供了<font color="#0000ff">vlax-curve-getclosestpointto</font> ，但这个函数仅仅是某点到曲线的最小距离，而不是两条曲线之间的最小距离。但是，我们可以利用这个函数来计算两条曲线之间的最小距离。因此程序的流程如下：</p>
<p>A 目标函数的设计： </p>
<p>参数 x ---第一条曲线的曲线参数x</p>
<p>返回值：参数x对应的点 pt 到第二条曲线的最小距离。(为了使得程序有通用性，采用了列表的函数返回值，第一个数值是这点对应的最小距离，第二和第三个分别是这两点)</p><br/>
<p>B .对第一条曲线分成几个区间，每个区间采用mnbrak函数去试探点。</p>
<p> 然后采用Brent方法去求得目标函数的最小值。</p>
<p> C 上步中求的的最小值是局部解，所以我们必须要每个局部比较一下，这样才能选取全局部的最小。</p>
<p> D 得到解之后，画出来。</p><br/>
<p>2 画出曲线的包围盒</p>
<p>说实在话，我并不想用求极值的方法来求解这个问题。因为，<font color="#0000ff">vla-getboundingbox</font>已经可以做到，但是Autodesk公司却表现的不够完美， boundingBox，对于spline来说根本就不准确，还有一点的就是，boundingBox得到的总是WCS 下的,所以，如果追求完美的人或者有这方面的需要的，就不够了。</p>
<p>因此建议<font color="#0000ff">vla-getboundingbox</font>如果能满足你的需要，就不要采用这个程序了，毕竟用了迭代，速度上会有所下降。但完全可以满足一般要求。</p><br/>
<p>那么程序是怎样设计的呢？</p>
<p>A 目标函数的设计</p>
<p>参数 x ---曲线的参数x</p>
<p>返回值 参数x对应的点的坐标的分量(我在这里只是设计了x、y分量，如果你需要的话，可以把z分量也加上)的最大最小数值，（最大数值可以加一个符号就能求最小了）</p>
<p>B .对曲线分成几个区间，每个区间采用mnbrak函数去试探点。</p>
<p> 然后采用Brent方法去求得目标函数的最小值。</p>
<p>C 同例子1.</p>
<p>D 解出来后，依据x y分量的极值，画出boundingbox。</p><br/>
<p>3 画出两条曲线的公切线。</p>
<p>这个功能是在你不想用command中xline来求解时候，或者无需人工干预的情况下用到。</p>
<p>关于椭圆，圆的公切线，参见我下面的帖子，这里采用的技术更快，更准确：</p>
<p><a href="http://bbs.mjtd.com/forum.php?mod=viewthread&tid=82900&star=2">http://bbs.mjtd.com/forum.php?mod=viewthread&tid=82900&star=2</a></p>
<p>为了求出spline 或者复杂点的曲线的公切线，有必要采用另外的一种方式：</p><br/>
<p>A 目标函数的设计</p>
<p> 参数: x --第一条曲线的曲线参数x</p>
<p> 返回值： 说实在话，这个地方我为难了很久，一直没找到一个完美的返回值。不过我这里是这么设置的，第一条曲线参数x对应的点P1的切线与第二条曲线相交，如果没有交点则设置为返回值为1e308---无穷大，如果相交或者相切，就为第二条曲线上的交点P，交点处的切线矢量Q和P1之间的det数值除以P1 到P的距离。</p>
<p>B、基本同例1.但是因为函数是不连续的，所以Brent方法我不肯定是否都有效，故采用了我自己设计的搜索法</p>
<p>C、实际上只有满足特定解的才能算是公切线，故需要判断。</p>
<p>D、画出公切线。</p><br/>
<p>细节问题：譬如参数越界问题，坐标旋转问题，怎样取点和划分区间等等各位可以参考我的程序。</p>
<p>另外，由于是匆匆写来，我没进行错误检查和bug测试。希望你能提出好的建议。谢谢。</p>
<p>函数进行了更新，请重新下载附件。Vlx是编译的文件，运行速度更快。</p>
<p>在以后的跟帖中，我会继续谈谈我的体会和一些应用。</p>
<p>譬如特别是在排料中的一些应用，这些已经进入到二维或者更高维。那时候这些一维的方法有些就不能用了，</p><br/>
<p>源码已经附上。各位如需要转载请说明来源。谢谢。</p>
<p>放在一楼。</p></font><span style="mso-list: Ignore"><span style="mso-fareast-font-family: 'Times new=" lang="EN-US" Roman?? New?><span style="mso-list: Ignore"><span style="mso-fareast-font-family: 'Times new=" lang="EN-US" Roman?? New?><span style="mso-list: Ignore"><span style="mso-fareast-font-family: 'Times new=" lang="EN-US" Roman?? New?><span style="mso-list: Ignore"><span style="FONT: 7pt="7pt"=" lang=" EN-US? mso-fareast-font-family:><span style=" Roman?? New? 7pt?=" Roman?? ?Times New? 7pt?=" ?Times Ignore? mso-list:><span style="COLOR: black" lang="EN-US"><o:p>
<p> </p></o:p>
<p class="MsoNormal"><o:p></o:p></p>
<p></p></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span></span> 这就是二分法求极值吗 有没有源码 <p></p>
<p>源码有，现在发布为时过早。一是有些代码还没整理好，二是先让大家测试，试验效果如何，和一些bug的发现</p> 学习，谢谢！ 想学。。可是看不懂 很好 研究一下 源码没有附上呀，还是只有编译后的文件 看不懂这么高深的，所以老规矩做记号，以后慢慢看！ 本帖最后由 作者 于 2010-9-11 21:10:09 编辑 <br /><br />
<p>再来一个例子：</p><br/>
<p>4 画出物体的最小包围框</p>
<p>物体的最小包围框并不等于boundingbox，最小值指的可能是面积，也可能是周长或者其他的数值，所以无法由一个简单的boundingbox来获得。</p>
<p>因而在这里函数的求极值发挥了作用。</p><br/>
<p>A 目标函数的设计</p>
<p> 参数: x –旋转的角度x</p>
<p> 返回值： 在这个角度由boundingbox得到的矩形的面积，或者周长等。</p>
<p>B、把360度等分，在每个等分区间试探。</p>
<p>C、试探后得到的三个值返给Brent函数来求这个区间段的局部极小值。</p>
<p>D、对每个局部的极小值进行比较，得到一个全局的最小值。</p>
<p>E、后续处理就是依据最小值时候的点画出矩形，然后旋转回去，就得到了结果。</p>
<p>程序对spline 不准确，但对其他物体有效，包括填充，文字，等等。</p>
<p> </p>