fbpx
维基百科

模拟退火

十二月 27, 2023

模擬退火（英語：Simulated annealing，缩写作SA）是一種通用概率演算法，常用來在一定時間內尋找在一個很大搜尋空間中的近似最優解。模擬退火在1983年为S. Kirkpatrick, C. D. Gelatt和M. P. Vecchi所發明，V. Černý也在1985年獨立發明此演算法。

模拟退火算法可用于求解组合问题。此处将模拟退火算法应用于求解旅行商问题，求出连接125个点的最小路线长度
使用模拟退火算法求解120个点的三维旅行商问题

簡介 编辑

模拟退火來自冶金學的專有名詞退火。退火是將材料加熱後再經特定速率冷卻，目的是增大晶粒的體積，並且減少晶格中的缺陷。材料中的原子原來會停留在使內能有局部最小值的位置，加熱使能量變大，原子會離開原來位置，而隨機在其他位置中移動。退火冷卻時速度較慢，使得原子有較多可能可以找到內能比原先更低的位置。

模擬退火的原理也和金屬退火的原理近似：我們將熱力學的理論套用到統計學上，將搜尋空間內每一點想像成空氣內的分子；分子的能量，就是它本身的動能；而搜尋空間內的每一點，也像空氣分子一樣帶有“能量”，以表示該點對命題的合適程度。演算法先以搜尋空間內一個任意點作起始：每一步先選擇一個“鄰居”，然後再計算從現有位置到達“鄰居”的概率。

可以证明，模拟退火算法所得解依概率收敛到全局最优解。

演算步驟 编辑

初始化 编辑

由一个产生函数从当前解产生一个位于解空间的新解，并定义一个足够大的数值作为初始温度。

迭代过程 编辑

迭代过程是模拟退火算法的核心步骤，分为新解的产生和接受新解两部分：

  1. 由一个产生函数从当前解产生一个位于解空间的新解；为便于后续的计算和接受，减少算法耗时，通常选择由当前新解经过简单地变换即可产生新解的方法，如对构成新解的全部或部分元素进行置换、互换等，注意到产生新解的变换方法决定了当前新解的邻域结构，因而对冷却进度表的选取有一定的影响。
  2. 计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生，所以目标函数差的计算最好按增量计算。事实表明，对大多数应用而言，这是计算目标函数差的最快方法。
  3. 判断新解是否被接受，判断的依据是一个接受准则，最常用的接受准则是Metropolis准则：若Δt′<0则接受S′作为新的当前解S，否则以概率exp（-Δt′/T）接受S′作为新的当前解S。
  4. 当新解被确定接受时，用新解代替当前解，这只需将当前解中对应于产生新解时的变换部分予以实现，同时修正目标函数值即可。此时，当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时，则在原当前解的基础上继续下一轮试验。

模拟退火算法与初始值无关，算法求得的解与初始解状态S（是算法迭代的起点）无关；模拟退火算法具有渐近收敛性，已在理论上被证明是一种以概率1收敛于全局最优解的全局优化算法；模拟退火算法具有并行性。

停止准则 编辑

迭代过程的一般停止准则：温度T降低至某阈值时，或连续若干次迭代均未接受新解时，停止迭代，接受当前寻找的最优解为最终解。

退火方案 编辑

在某个温度状态T下，当一定数量的迭代操作完成后，降低温度T，在新的温度状态下执行下一个批次的迭代操作。

虛擬碼（偽代碼） 编辑

尋找能量   最低的狀態   

s := s0; e := E(s) // 設定目前狀態為s0，其能量E (s0) k := 0 // 評估次數k while k < kmax and e > emin // 若還有時間（評估次數k還不到kmax）且結果還不夠好（能量e不夠低）則：  sn := neighbour(s) // 隨機選取一鄰近狀態sn  en := E(sn) // sn的能量為E (sn)  if random() < P(e, en, temp(k/kmax)) // 決定是否移至鄰近狀態sn  s := sn; e := en // 移至鄰近狀態sn  k := k + 1 // 評估完成，次數k加一 return s // 回傳狀態s

延伸閲讀 编辑

  • A. Das and B. K. Chakrabarti (Eds.), Quantum Annealing and Related Optimization Methods, Lecture Note in Physics, Vol. 679, Springer, Heidelberg (2005)
  • Weinberger, E. Correlated and uncorrelated fitness landscapes and how to tell the difference. Biological Cybernetics. 1990, 63 (5): 325–336. S2CID 851736. doi:10.1007/BF00202749. 
  • Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP. Section 10.12. Simulated Annealing Methods. Numerical Recipes: The Art of Scientific Computing 3rd. New York: Cambridge University Press. 2007 [2021-09-02]. ISBN 978-0-521-88068-8. （原始内容于2011-08-11）. 
  • Strobl, M.A.R.; Barker, D. On simulated annealing phase transitions in phylogeny reconstruction. Molecular Phylogenetics and Evolution. 2016, 101: 46–55. PMC 4912009  . PMID 27150349. doi:10.1016/j.ympev.2016.05.001. 
  • V.Vassilev, A.Prahova: "The Use of Simulated Annealing in the Control of Flexible Manufacturing Systems", International Journal INFORMATION THEORIES & APPLICATIONS, VOLUME 6/1999 （页面存档备份，存于互联网档案馆）

参閲 编辑

外部链接 编辑

  • ：SIMPSA（SA和单纯的组合），洗牌复杂的演化（SCA）和粒子群优化（PSO）。
  • Simulated Annealing （页面存档备份，存于互联网档案馆） A Javascript app that allows you to experiment with simulated annealing. Source code included.
  • "General Simulated Annealing Algorithm" （页面存档备份，存于互联网档案馆） An open-source MATLAB program for general simulated annealing exercises.
  • Self-Guided Lesson on Simulated Annealing A Wikiversity project.
  • Google in superposition of using, not using quantum computer （页面存档备份，存于互联网档案馆） Ars Technica discusses the possibility that the D-Wave computer being used by Google may, in fact, be an efficient simulated annealing co-processor.
  • [1] （页面存档备份，存于互联网档案馆） A Simulated Annealing-Based Multiobjective Optimization Algorithm: AMOSA.

十二月 27, 2023
模拟退火, 本條目存在以下問題, 請協助改善本條目或在討論頁針對議題發表看法, 此條目可参照英語維基百科相應條目来扩充, 2020年9月25日, 若您熟悉来源语言和主题, 请协助参考外语维基百科扩充条目, 请勿直接提交机械翻译, 也不要翻译不可靠, 低品质内容, 依版权协议, 译文需在编辑摘要注明来源, 或于讨论页顶部标记, href, template, translated, page, html, title, template, translated, page, translated, page, 标签,. 本條目存在以下問題 請協助改善本條目或在討論頁針對議題發表看法 此條目可参照英語維基百科相應條目来扩充 2020年9月25日 若您熟悉来源语言和主题 请协助参考外语维基百科扩充条目 请勿直接提交机械翻译 也不要翻译不可靠 低品质内容 依版权协议 译文需在编辑摘要注明来源 或于讨论页顶部标记 a href Template Translated page html title Template Translated page Translated page a 标签 此條目没有列出任何参考或来源 2020年9月25日 維基百科所有的內容都應該可供查證 请协助補充可靠来源以改善这篇条目 无法查证的內容可能會因為異議提出而被移除 模擬退火 英語 Simulated annealing 缩写作SA 是一種通用概率演算法 常用來在一定時間內尋找在一個很大搜尋空間中的近似最優解 模擬退火在1983年为S Kirkpatrick C D Gelatt和M P Vecchi所發明 V Cerny也在1985年獨立發明此演算法 模拟退火算法可用于求解组合问题 此处将模拟退火算法应用于求解旅行商问题 求出连接125个点的最小路线长度使用模拟退火算法求解120个点的三维旅行商问题 目录 1 簡介 2 演算步驟 2 1 初始化 2 2 迭代过程 2 3 停止准则 2 4 退火方案 3 虛擬碼 偽代碼 4 延伸閲讀 5 参閲 6 外部链接簡介 编辑模拟退火來自冶金學的專有名詞退火 退火是將材料加熱後再經特定速率冷卻 目的是增大晶粒的體積 並且減少晶格中的缺陷 材料中的原子原來會停留在使內能有局部最小值的位置 加熱使能量變大 原子會離開原來位置 而隨機在其他位置中移動 退火冷卻時速度較慢 使得原子有較多可能可以找到內能比原先更低的位置 模擬退火的原理也和金屬退火的原理近似 我們將熱力學的理論套用到統計學上 將搜尋空間內每一點想像成空氣內的分子 分子的能量 就是它本身的動能 而搜尋空間內的每一點 也像空氣分子一樣帶有 能量 以表示該點對命題的合適程度 演算法先以搜尋空間內一個任意點作起始 每一步先選擇一個 鄰居 然後再計算從現有位置到達 鄰居 的概率 可以证明 模拟退火算法所得解依概率收敛到全局最优解 演算步驟 编辑初始化 编辑 由一个产生函数从当前解产生一个位于解空间的新解 并定义一个足够大的数值作为初始温度 迭代过程 编辑 迭代过程是模拟退火算法的核心步骤 分为新解的产生和接受新解两部分 由一个产生函数从当前解产生一个位于解空间的新解 为便于后续的计算和接受 减少算法耗时 通常选择由当前新解经过简单地变换即可产生新解的方法 如对构成新解的全部或部分元素进行置换 互换等 注意到产生新解的变换方法决定了当前新解的邻域结构 因而对冷却进度表的选取有一定的影响 计算与新解所对应的目标函数差 因为目标函数差仅由变换部分产生 所以目标函数差的计算最好按增量计算 事实表明 对大多数应用而言 这是计算目标函数差的最快方法 判断新解是否被接受 判断的依据是一个接受准则 最常用的接受准则是Metropolis准则 若Dt lt 0则接受S 作为新的当前解S 否则以概率exp Dt T 接受S 作为新的当前解S 当新解被确定接受时 用新解代替当前解 这只需将当前解中对应于产生新解时的变换部分予以实现 同时修正目标函数值即可 此时 当前解实现了一次迭代 可在此基础上开始下一轮试验 而当新解被判定为舍弃时 则在原当前解的基础上继续下一轮试验 模拟退火算法与初始值无关 算法求得的解与初始解状态S 是算法迭代的起点 无关 模拟退火算法具有渐近收敛性 已在理论上被证明是一种以概率1收敛于全局最优解的全局优化算法 模拟退火算法具有并行性 停止准则 编辑 迭代过程的一般停止准则 温度T降低至某阈值时 或连续若干次迭代均未接受新解时 停止迭代 接受当前寻找的最优解为最终解 退火方案 编辑 在某个温度状态T下 当一定数量的迭代操作完成后 降低温度T 在新的温度状态下执行下一个批次的迭代操作 虛擬碼 偽代碼 编辑尋找能量 E s displaystyle E s nbsp 最低的狀態 s displaystyle s nbsp s s0 e E s 設定目前狀態為s0 其能量E s0 k 0 評估次數k while k lt kmax and e gt emin 若還有時間 評估次數k還不到kmax 且結果還不夠好 能量e不夠低 則 sn neighbour s 隨機選取一鄰近狀態sn en E sn sn的能量為E sn if random lt P e en temp k kmax 決定是否移至鄰近狀態sn s sn e en 移至鄰近狀態sn k k 1 評估完成 次數k加一 return s 回傳狀態s延伸閲讀 编辑A Das and B K Chakrabarti Eds Quantum Annealing and Related Optimization Methods Lecture Note in Physics Vol 679 Springer Heidelberg 2005 Weinberger E Correlated and uncorrelated fitness landscapes and how to tell the difference Biological Cybernetics 1990 63 5 325 336 S2CID 851736 doi 10 1007 BF00202749 Press WH Teukolsky SA Vetterling WT Flannery BP Section 10 12 Simulated Annealing Methods Numerical Recipes The Art of Scientific Computing 3rd New York Cambridge University Press 2007 2021 09 02 ISBN 978 0 521 88068 8 原始内容存档于2011 08 11 Strobl M A R Barker D On simulated annealing phase transitions in phylogeny reconstruction Molecular Phylogenetics and Evolution 2016 101 46 55 PMC 4912009 nbsp PMID 27150349 doi 10 1016 j ympev 2016 05 001 V Vassilev A Prahova The Use of Simulated Annealing in the Control of Flexible Manufacturing Systems International Journal INFORMATION THEORIES amp APPLICATIONS VOLUME 6 1999 页面存档备份 存于互联网档案馆 参閲 编辑演算法 旅行推銷員問題 蚁群算法 遗传算法外部链接 编辑基于MATLAB实现的全局优化算法 SIMPSA SA和单纯的组合 洗牌复杂的演化 SCA 和粒子群优化 PSO Simulated Annealing 页面存档备份 存于互联网档案馆 A Javascript app that allows you to experiment with simulated annealing Source code included General Simulated Annealing Algorithm 页面存档备份 存于互联网档案馆 An open source MATLAB program for general simulated annealing exercises Self Guided Lesson on Simulated Annealing A Wikiversity project Google in superposition of using not using quantum computer 页面存档备份 存于互联网档案馆 Ars Technica discusses the possibility that the D Wave computer being used by Google may in fact be an efficient simulated annealing co processor 1 页面存档备份 存于互联网档案馆 A Simulated Annealing Based Multiobjective Optimization Algorithm AMOSA 取自 https zh wikipedia org w index php title 模拟退火 amp oldid 73743769, 维基百科，wiki，书籍，书籍，图书馆，

文章

，阅读，下载，免费，免费下载，mp3，视频，mp4，3gp， jpg，jpeg，gif，png，图片，音乐，歌曲，电影，书籍，游戏，游戏。