Algorithm 版 (精华区)

发信人: ssos (存在与虚无), 信区: Algorithm
标  题: 生物信息学笔记（四）
发信站: 哈工大紫丁香 (2001年06月08日18:51:36 星期五), 站内信件

§4 模拟退火算法
一 局部搜索算法
局部搜索算法从一个初始解i∈S开始,运用一个产生器,持续地在解i(称为当前解)
的邻域Si中搜索比i更优的解.若找到比i更优的解,就用这个解取代i,成为当前解,再
对当前解继续算法;否则算法终止,当前解就是算法的最终解.
最终解一般是某个局部最优解,无法保证最终解的质量.
重启策略
设一次局部搜索找到最优解的概率为p0,则重启k次找到最优解的概率
p=1-(1-p0)^k,k=T/t0,T为给定时间,t0为一次运行时间.
对TSP问题,取3-邻域结构最好.
二 模拟退火算法
按照一定概率接受恶化解.设p(i,j)为由i接受j的概率,
如果f(j)<=f(i),则p(i,j)=1;否则p(i,j)=exp((f(i)-f(j))/t). (Metropolis准则)
t为控制参数(温度).t由一个较大的值逐步减少到0,在每一步,进行Lk次
变换.
模拟算法在一定条件下可以跳出局部最优的陷阱,找到最优解.
三 Gibbs分布 (略)
四 Markov链 (略)
五 冷却进度表的选取
1 初值T0
2 T的衰减函数
3 终止准则
4 Markov链长度Lk
§5 DDP
问题:任给A={ai|1≤i≤n},B={bj|1≤j≤m}和C={ck|1≤k≤l}.其中ai,bj,ck∈Z+,且Σ
ai=Σbj
=Σck.设σ,μ分别是1,2,...,n和1,2,...,m的排列.
          i                                  j
记S={ Σ a σ(t) | 1≤i≤n} ∪{ Σ b μ(t) | 1≤j≤m}
         t=1                             t=1
     ={s k | 0≤k≤q }
其中s0=0,si<sj (i<j).
C(σ,μ)={sk - s k-1| 1≤k≤q }
求排列σ,μ使得C(σ,μ)=C.
一 DDP是NP-hard的
C=A,B={L/2,L/2},L=Σai是偶数.即划分问题.
二 用模拟退火求解
A,B,C的元素从小到大排列.
可行解:(σ,μ)
目标函数:将C(σ,μ)的元素从小到大排列.
               l
f(σ,μ) = Σ ( Ci(σ,μ) - ci) ^ 2 / ci , 如果q=l;
              i=1
f(σ,μ) = ∞, 如果q≠l.
邻域: N(σ,μ) = N k(σ) ×S m ∪S n ×N k(μ) .

--

   
<<社会契约论>>是一本好书,应当多读几遍
风味的肘子味道不错,我还想再吃它      

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.230.220]