自适应模拟退火

2024-10-09

自适应模拟退火（精选3篇）

自适应模拟退火篇1

摘要：提出一种基于自适应遗传模拟退火策略的Web日志关联规则挖掘算法。该算法在遗传模拟退火策略基础上,引入自适应的交叉概率和变异概率,使其具有较强的全局搜索能力,有效地避免了早熟的现象。实验结果证明,该算法能有效地解决Web日志关联规则挖掘问题。

关键词：关联规则,遗传算法,模拟退火算法,Web挖掘,自适应

1 关联规则挖掘模型

在关联规则系统中,规则本身是“如果条件怎么样、怎么样,那么结果或者情况就怎么样”的形式。可表示为“A⇒B”关联规则,它包括两个部分:左部A称为前件,右部称为后件。前件可以包括一个或多个条件,在某个给定的正确率中,要使后件为真,前件中的所有条件必须同时为真。后件一般只包括一种情况。如:购买计算机有购买财务软件趋向的关联规则、年龄在30至40岁之间并且年收入在4200元至5000元之间的客户购买高清晰度彩色电视机趋向的关联规则可分别表示为:

undefined

数据项集合A和B由一项或多项属性组成,分别为决策属性和任务属性。通过对问题的分析,可以发现,决策属性相互间是无序的。因此可以将决策属性一次性排定顺序组成属性串,且在挖掘过程中不变其顺序。为了便于问题的分析,作以下形式定义。

定义1( Web事务。)在事务文件中出现的所有页面集合表示为P={p1,p2,…,pn}。其中每个页面pi(i=1,2,…,n)通过其URL地址唯一表示。事务集合U表示为U={u1,u2,…,un},每个事务ui={i=1,2,…,m}均为页面集合P的子集。

定义2 (页面权值。)假定将用户访问页面的平均停留时间作为该页面的权值。整个事务的权值为

undefined

定义3 (向量空间。)事务集合中的每一个事务ui(i=1,2,…,m)可以转换为页面空间上的n维向量,u=

定义4 (支持度s(pi)。)页面pi∈p的支持度为

undefined

定义5 (可信度。)规则pi⇒pj的可信度为C(pi⇒pj)=s(pi∪pj)/s(pi)。

定义6 (支持度 s(pi∪pj)。)页面 pi∪pj支持度为S(pi∪pj)=∑u∈U&pi∈uw(pi,u)×w(pj,u)/|{u∈U|pi∈u∧pj∈u }|

定义7 (AGSAA算法。)AGSAA=(Ω,f,P0,N,T0,Φ,Γ,Ψ)。其中,Ω为个体的编码方法;f为适应度函数;P0为初始种群;N为群体规模;TO为初始温度;Φ为遗传选择;Γ为交叉算子;Ψ为退火变异。

2自适应遗传退火算法的设计

2.1染色体编码

本文采用二进制编码来表示关联规则。对所有的特征属性和类别属性取离散值,且对连续型的值先作离散化处理。已知取值范围,对每个属性的每一个取值用一个合适长度的二进制串来表示,每个二进制串代表一个基因。将所有属性值的二进制串连接在一起得到一个二进制串作为一个染色体。一个染色体就代表一个关联规则,染色体的基因对应于事务中的页面权值。

2.2适应度函数

适应度函数评估是选择操作的依据,它的设计对遗传算法的收敛速度及能否找到最优解至关重要。本文考虑到在遗传算法中适应函数通常是最大值的形式,设计的适应函数为fitness=1/F。且采用适应度拉伸方法:

i=1其中,fi为第i个个体的适应度;g为遗传代数;T为温度;T0为初始温度

2.3遗传选择

遗传选择是将父代的个体信息传递到子代,每代中的每一个个体按照适应度函数的大小决定它能够复制到下一代的概率。AGSAA算法采用“轮盘赌”式的选择策略,随机生成一个数r=random[0,1],若(p0+p1+…+pi-1),则第i个个体被选择到下一代。算法采用的选择概率为:

2.4自适应遗传交叉、变异

IAGA算法为了保证每一代的优良个体不被破坏,采用了精英保留策略。即如果下一代种群的最优个体适应度值小于当前种群最优个体适应度值,则将当前种群最优个体或者适应度值大于下一代最优个体适应度值的个体直接复制到下一代,随机替代或替代最差的下一代种群中的相应数量的个体。此策略保证了当前的最优个体不被交叉、变异。但当适应度值等于最大适应度值的时候,交叉概率和变异概率的值为零,此时易产生局部最优解,出现停滞现象。为了避免此现象的发生,AGSAA算法根据适应度值来动态调整交叉概率和变异概率。

其中,fmax为种群最大适应度,favg为每代种群的平均适应度值,fmin为种群最小适应度值,f′为要交叉的两个个体中较大的适应度值,f为要变异个体的适应度值。Pc1>Pc2>Pc3,Pm1>Pm2>Pm3取(0,1)区间的值,可在优化过程中调整。

2.5个体模拟退火过程

用适应度作为模拟退火遗传算法中的能量,对算法中的近邻子集采用动态调节的方式选取:M=λ×(fmaxfavg)。当适应度值增加时,接受该解作为下一个当前解,否则,以一定的概率p=exp(-△fitness/T)接受该解。即

其中,fi+1为子个体的适应度值,fi为父个体的适应度值,温度T由随着算法进程递减其值的控制参数担当。

2.6并行模式

AGSAA算法采用主从式的并行遗传算法模型,该模型在不改变遗传算法结构的基础上,将一个群体的选择、交叉和变异等全局操作由主处理器串行进行,而适应度的评价和计算由各个从处理器并行执行。

2.7结束条件

如果经过若干代计算后,仍然没有满足用户给定阈值的规则,则终止并输出结果。

3实验及分析

3.1实验环境

为验证本文所提出方法的有效性,采用天网2001年用户查询与点击日志。其中,用户查询日志记录了用户查询时提交的关键词、提交时间、用户ip、页号及是否在cache中命中等信息。天网点击日志记录了用户的点击时间、查询串、点击的URL、点击页面的编号、点击URL的序号等信息。系统数据共维护了100多万个有效页面,被点击的URL只有16万多。经过数据净化处理,从中识别出2019条事务和317个页面。实验过程中所使用到得参数初始化定义为:种群规模150、交叉概率0.8、变异概率0.15、初始温度1、最大迭代次数genmax=220、支持度阈值10%、置信度阈值80%。实验环境为Intelc2.0GHZ、2GB内存、Windows xp和MATLAB7.0。分别对SA、AGA和AGSAA算法进行对比试验。

3.2 AGSAA算法流程

AGSAA算法流程如图1所示:

3.3实验结果及分析

图2描述的是在同迭代次数下SA、AGA和AGSAA三种算法产生的关联规则数的比较。从图2可看出,AG-SAA算法能够有效地进行关联规则挖掘,具有较快的收敛速度。图3描述的是3种算法在同迭代次数下关联规则准确率的比较。图3表明AGSAA算法挖掘出的规则的准确率比SA和AGA算法要高。表1描述的是SA、AGA和AGSAA算法在同计算时间下关联规则提取量的比较。从表1可看出,在初始阶段,AGA算法挖掘的规则数要高于AGSAA算法,但是在中后期阶段,AGSAA算法的挖掘效果要优于SA和AGA算法。这主要是因为通过引入自适应的交叉概率和变异概率,有利于AGSAA算法跳出局部最优解,增强了较差个体的变异能力,克服了早熟的现象。

4结束语

针对Web日志关联规则挖掘,本文在模拟退火遗传算法基础上,引入自适应的交叉概率和变异概率,且采用并行处理技术保持和丰富种群的多样性。通过对Web日志数据进行关联规则的实验和分析得出,该算法具有较强全局搜索能力,有效避免了早熟现象。表明该算法能有效地应用于Web日志关联规则挖掘中。

参考文献

[1]忠植.知识发现[M].北京:清华大学出版社,2002.

[2]阮光栅.基于兴趣度策略的启发式web挖掘算法[J].计算机工程与应用,2009(5).

[3]朱颢东,钟勇.一种改进的模拟退火算法[J].计算机技术与发展,2009(6).

[4]GALE D.The game of Hex and the Brouwer fixed point theorem[J].American Mat-Hematical Monthly,1979(10).

[5]李凤营,赵连朋,王红雨.一种基于遗传算法的关联规则改进方法[J].计算机工程与应用,2008(10).

[6]武兆慧,张桂娟,刘希玉.基于模拟退火遗传算法的关联规则挖掘[J].计算机应用,2005(5).

[7]SRINIVAS M,PA TNAIL K L M.Adaptive probabilities of cross-over and mutation in genetic algorithms[J].IEEE Transaction onsystem,Man and Cybernetics,1994(4).

[8]任子武,伞治.自适应遗传算法的改进及在系统识别中应用研究[J].系统仿真学报,2006(1).

[9]许国艳,史清宇.遗传算法在关联规则挖掘中的应用[J].计算机工程,2002(7).

[10]刘若,孙杨军.基于多克隆选择的多维关联规则挖掘算法[J].复旦学报,2004(5).

[11]符保龙.基于规则提取量的web日志关联规则挖掘方法[J].计算机应用研究,2010(2).

自适应模拟退火篇2

关键词：自适应模拟退火,连续搅拌釜式反应器,动态优化

模拟退火算法 (SA) 是近些年来发展起来的一种基于固体退火过程模拟的随机全局优化方法。由于它具有高效、通用、灵活的特点, 因此被广泛应用于解决各种工程优化问题。

连续搅拌釜式反应器 (Continuous Stirred Tank Reactor, CSTR) 具有采用连续操作方式, 过程在恒速操作条件下可达定常态, 以及物料质点在釜内的停留时间各不相同等三大特征。

本文分析了CSTR的动态优化模型, 研究了一种改进的自适应模拟退火算法 (ASA) , 并将其应用于求解CSTR的动态优化问题。

1 改进的自适应模拟退火算法

优化问题通常可以归结为求某一函数在一定范围内的最小值问题。但是以往传统的优化算法都是运用某种局部的比较去决定寻优路径, 带来的后果就是如果初始值选取不当将很容易陷入局部极小值。SA作为一种随机搜索法, 不仅接受使函数值下降的点作为新解, 而且按照一定比率接受使函数值上升的点作为新解[1], 因为暂时使函数值上升的方向也有可能找到全局最小值, 这样就可以使函数轻松逃离局部极值。

由于SA为了避免函数落入局部极值, 通常采用Metropolis接受准则, 而每一温度下要使状态达到平衡又是一个很漫长的过程, 为了提高算法的效率主要从以下几点进行改进。

1.1 新变量产生函数

根据Corana 1987年提出的自适应邻域模拟退火算法 (ASA) [2]对变量进行扰动:

现取随机扰动γ为柯西分布:

由于柯西分布有一平坦的拖尾, 因而具有迅速跳出局部极值的能力。模型可以在高温时进行大范围搜索, 而在低温时仅在当前模型附近搜索。因此加入柯西分布可以使函数具有更快的收敛速度[3]。

mu为自适应步长, 由如下公式确定

${\begin{cases} m_{u^{'}} = m_{u} \times g_{u} (p_{u}) \\ g_{u} (p_{u}) = 1 + c \frac{p_{u} - p_{1}}{p_{2}}, i f p_{u} ＞ p_{1} \\ g_{u} (p_{u}) = (1 + c \frac{p_{2} - p_{u}}{p_{2}})^{- 1}, i f p_{u} ＜ p_{2} \\ g_{u} (p_{u}) = 1, o t h e r w i s e \\ p_{1} = 0.6, p_{2} = 0.4 \end{cases} (3)$

式 (3) 中:接收率 $p_{u} = \frac{n}{Ν}$ , n为第u方向同一邻域范围内接收解的个数, N为第u方向同一邻域范围内总的搜索次数。当pu> p1时说明在此邻域内接收的点太多, 应延u方向放大搜索区域, 当pu<p2时说明接收的点过少, 已接近最优值, 应延u方向缩小搜索范围。而p2<pu<p1时, 说明搜索的步长刚好合适, 保持原步长进行搜索。

1.2 接收概率采用Metropolis准则

$Ρ = \exp (- \frac{f (y_{u}^{i}) - f (x_{u}^{i})}{Τ_{Κ}})$ (4)

即当f (y $_{u}^{i}$ ) <f (x $_{u}^{i}$ ) 时按照概率1接受为新解, 并更新为当前最优解;反之则按公式 (4) 给出的概率接受为新解。开始时由于P较大, 算法接受恶化解的概率较大, 在接近全局最优值的过程中P逐渐减小, 最终算法将不接受恶化解并以概率1收敛于全局最优值。

1.3 降温方式

采用Ingber (1989) 提出的VFSA中的降温方式:

TK=T0exp (-CK1/N) (5)

式 (5) 中:T0为初始温度;K为温度迭代次数;C为给定常数;N为参数个数。一般将式 (5) 变形为式 (6) , 通常0.7≤α≤1。

TK=T0αK1/N (6)

2 CSTR动态优化模型

CSTR的优化要经过目标函数的确定, 自由度分析以确定决策变量, 可行域 (约束条件) 的确定及优化问题的求解等几个步骤[4]。

在初始状态和要求达到的终态已知的情况下控制冷剂流量u (t) , 使反应器能够以最短的时间从一个稳态过渡到另一个稳态。目标函数形式如下:

式 (7) 中下标为“des”的均代表期望达到的过渡终值。α1, α2, α3为各个状态 (浓度、温度) 和操作变量 (冷剂流量) 的权重系数。

为了有效近似 (7) 式, 我们使用Radau求积公式得 (13) 式。并且用正交配置法对微分方程进行离散。离散后微分方程约束变为一组代数方程, 其中第k个有限元离散如下:

质量平衡:

$\sum_{j = 1}^{Ν + 2} A_{i j} y_{1, j} - h_{k} f_{1} (y) = 0, i = 2, Ν + 2$ (8)

能量平衡:

$\sum_{j = 1}^{Ν + 2} A_{i j} y_{2, j} - h_{k} f_{2} (y) = 0, i = 2, Ν + 2$ (9)

连接点处的质量和能量平衡:

$\frac{1}{h_{k}} \sum_{j = 1}^{Ν + 2} A_{Ν + 2, j} y_{1, j} - \frac{1}{h_{k + 1}} \sum_{j = 1}^{Ν + 2} A_{1 j} y_{1, j} = 0, i = 2, Ν + 2 (10)$

$\frac{1}{h_{k}} \sum_{j = 1}^{Ν + 2} A_{Ν + 2, j} y_{2, j} - \frac{1}{h_{k + 1}} \sum_{j = 1}^{Ν + 2} A_{1 j} y_{2, j} = 0, i = 2, Ν + 2$ (11)

总过渡时间:

$\sum_{k = 1}^{Ν e} h_{k} \leq θ$ (12)

其中hk为第k段有限元长度, N为有限元内配置点个数, A为配置矩阵, Ne为有限元个数。

$\begin{array}{l} \min φ \approx \sum_{k = 1}^{Ν e} h_{k} \sum_{j = 1}^{Ν e} W_{j} [a_{1} (y_{1, i j} - y_{1, d e s})^{2} + \\ a_{2} (y_{2, i j} - y_{2, d e s})^{2} + a_{3} (u_{i j} - u_{d e s})^{2}] 。 \end{array}$

Nc为包括右边界在内的正交配置点数, 在此Nc=3, y1, ij、y2, ij和uij分别代表第ij个离散点处的无因次浓度、温度和冷剂流速。Wj为Radau求积公式中的求积系数。他们试验了不同的权重系数, 并且发现最优过渡依赖于权重系数的取值。在这里考虑到浓度是主要的输出变量, 因此所占权重较大。

由以上离散后, 变成了如下形式的连续多变量优化问题:

目标函数:

3 优化处理及仿真结果

CSTR过渡过程中参数设置如表1。

配置点选为[0.211 0.789], Radau求积权重W=[0.376 0.512 0.111]T。

CSTR优化问题中的目标函数是关于控制变量、状态变量的一个函数。在此只需要填加一个计算目标函数的子程序即可。经过计算, 最优过渡曲线如图1与图2所示, 最优控制曲线如图3所示。

图中可以看出, 在给定最优控制后, 连续搅拌釜中的温度以及浓度都以较快速度过渡到了指定稳定状态, 达到了比较理想的控制效果。

4 结论

本文基于改进的自适应模拟退火算法, 很好地解决了CSTR的动态优化问题。通过MATLAB/SIMULINK对CSTR的模拟和动态优化过程的仿真, 验证了算法对动态优化过程最优解的求取不仅缩短了计算时间, 而且取得了令人比较满意的优化结果。

参考文献

[1]康立山, 谢云, 尤矢勇, 等.非数值并行算法——模拟退火算法.北京:科学出版社, 1994

[2]Silva A B, Flores A T, Arrieta J J C.Dynamic trajectory optimization between unstable steady-states of a class of CSTRs.Netherlands:Computer Aided Chemical Engineer, 2002;10:547—552

[3]王知人, 章胤, 李新乔.一种改进的模拟退火算法.高等学校计算数学学报, 2006;28 (1) :15—19

[4]Hicks G A, Ray W H.Approximation methods for optimal control synthesis.canada.Can J Chem Eng, 1971;40:522—529

自适应模拟退火篇3

目前, 在PCM/FM遥测体系中模拟信号采集普遍采用8位量化, 全部模拟信号均归一化到0~5 V范围内, 随着需要采集的模拟信号的类型多样化, 势必增加信号调理电路的多样性, 不利于系统的简化和模块化。在量化位数一定的系统中, 被衰减处理的信号中实际量化误差等于N倍 (N是信号被衰减的倍数) 的最小量化误差, 因此合理的信号调理电路和A/D取值是保证量化精度的关键。本文提供的方式有效地解决了这个问题, 既简化了前端信号调理电路的复杂度, 又充分利用了A/D转换器的输入电压动态范围和量化位数优势, 实现了对多路模拟信号的自适应采集, 对其他信号采集系统也具有一定的借鉴意义。

1 系统设计[1,2,3]

该系统主要由信号调理电路、采集电路和时序控制等几部分组成。被测模拟信号经过信号调理电路后, 经多路选择器的快速切换, 按需求依次送入A/D转换器进行采样, 采样后的数据送入FPGA中处理, 系统框图如图1所示。

系统设计的主要指标:模拟信号通道数为46路;系统采样率大于300 Kb/s;量化位数为8位;频率响应范围为DC~1 kHz;通道采样率为100 Hz, 200 Hz, 400 Hz, 500 Hz, 800 Hz, 1 kHz, 2 kHz, 4 kHz可选;A/D转换器允许输入信号的最大幅度为±10 V。

2 系统各部分功能及实现

2.1 信号调理电路[4]

信号调理电路主要完成被测信号的阻抗匹配和电压变换, 设计时信号调理电路均采用差分输入电路形式。针对不同类型的信号, 通过调整电阻阻值即可实现信号的衰减、放大或者阻抗匹配, 有利于电路形式的模块化和标准化。信号调节电路如图2所示。

整个信号调理电路采用±12 V供电, 根据信号类型将全部模拟信号调理到合适的范围内, 以便充分利用A/D的输入动态范围来实现自适应采集。

2.2 采集电路[5,6]

采集电路主要包括多路选择器和A/D转换器等, 多路选择器采用ADG406, 通过级联可以形成46路模拟信号通道, 采用±12 V供电, 保证调理后的信号不失真通过, 12根地址线用来控制模拟信号的切换;A/D转换器采用AD7892-1, 其具有±10 V的输入电压动态范围和12位的量化能力, 信号输入范围设置为±10 V, 控制线用来控制A/D转换器的工作状态, 并将转换后的12位数据全部接入FPGA中进行处理。

2.3 时序控制[7,8]

时序控制通过FPGA程序来实现, 主要完成多路选择器的切换, A/D转换器的控制和自适应采集逻辑等功能。对于多路选择器的切换和A/D转换器的控制逻辑, 只要注意多路选择器的开关稳定时间和A/D转换器的采样时刻即可完成数据采集。自适应采集就是根据已知模拟信号的类型自动选择A/D的转换器输出码位来实现的。为了便于对后文的理解, 表1给出AD7892-1输入/输出对应码表和处理后的码表。

前面信号调理电路根据模拟信号的类型把信号分别调理到0~5 V, -5~-0 V, -5~+5 V, 0~+10 V, -10~-0 V, -10~+10 V等范围内, 结合表1的内容即可实现对模拟信号的自适应采集, 保证信号的采集精度。数据自动转换模块的FPGA程序示例如下:

通过测试验证, 该法是可行的。在不改变任何硬件电路的情况下, 通过FPGA程序可有效实现模拟信号的动态量化, 确保信号的量化精度。通过数据处理软件即可恢复原始信号, 如图3所示。

3 结语

设计的基于FPGA的多路模拟信号自适应采集系统, 在有限的量化位数限制下, 充分利用信号调理电路、A/D转换器的输入电压动态范围和12位的位宽, 在相同的量化位数下提高了大部分模拟信号的采样精度, 具有一定的参考价值。

参考文献

[1]郑俭锋.多路高速信号并行采样及实时存储解决方案[J].电子设计应用, 2007 (3) :98-101.

[2]许锦峰, 陈炳泉.双通道逻辑控制高速实时数据采集系统的设计[J].电子技术应用, 2007 (11) :77-79.

[3]赵红梅, 米启超.基于DSP和CPLD的信号采集与编码系统设计[J].矿山机械, 2007 (6) :43-45.

[4]吴居娟, 齐娟.基于可编程增益放大器的多路高速数据采集系统设计[J].煤矿现代化, 2007 (5) :54-55.

[5]张志刚.常用A/D、D/A器件手册[M].北京:电子工业出版社, 2008.

[6]吴巍, 李相平, 段鲁生, 等.一种基于A/D和DSP的高速数据采集技术[J].单片机与嵌入式系统应用, 2007 (3) :26-28.

[7]李洪伟, 袁斯华.基于QuartusⅡ的CPLD/FPGA设计[M].北京:电子工业出版社, 2006.