数据挖掘在优化算法(近似)中的应用

引言:

1.在数据挖掘后再优化

一个城市有N(已知)个镇,任意两个镇的距离dist(i,j)都已知,现需分配K个邮递员在K个镇上:每个镇由离它最近的邮递员负责送信,这样分配这K个邮递员使得每个镇到所管辖邮递员的那个镇的距离之和最小!

起初想用一般的方法建模求解实现,但“每个镇由离它最近的邮递员负责送信”处理起来比较困难,如果N比较大计算复杂度高。

现在有个想法就是像聚类那样,先把N个镇用聚类的方法分成K个类(可以基于距离分类),然后再在每个类上选出邮递员所在镇。这样计算复杂程度大大降低,接近最优解…..

难点:如何分类

总之,把聚类与优化联系起来。

可行应用方向:物流中心选址等

 

2.对优化过程中的数据进行数据挖掘。

随着优化问题的日益复杂,规模越来越大,经典的算法已难以解决。学者们引入了遗传算法,基于网格算法,随机模拟等,近代算法,这类的算法特点就是数据量大,在这样就可以引入数据挖掘的思想对这些数据进行处理,从这些数据中寻找反映了原问题的关联关系。

基于网格算法为例:

1.      对问题可行域S基于网格计算目标函数在网格点的函数值。

2.      基于各点的函数值,对网格点进行聚类(可分K类),类(i)中点的函数值小于类(i+1)中点的函数值。

一般的搜索方法,都是基于一个初始点,一个可行方向。在经典的优化算法中,可行方向是由目标函数的导数确定(这种方法不能有较的解决全局最优问题)。可根据聚类的思想定义新的可行方向:

a.       如果类(i)是近似球型的,可定义d=类(i+1)的几何中心点 —类(i)的几何中心点。

b.      如果类(i)是近似带型的,可定义d=类(i)指向类(i+1)的垂直方向。

其他:如果某类是环形的可推出环内有局部最优点。

3.延导出的方向进一步搜索,可得到更好的近似全局最优解。

主要可得到一种新的方法定义搜索方向。

Tagged on:

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>