昨天我們聊到了快速簡單且能達到一定成效的爬山法。
但也聊到了爬山法的缺點在於如果初始位置沒有座落在好的點,則無法找到全域的最佳解 (Global Maximum),那麼今天我們就先來聊聊另一個能夠避開這個缺點的演算法。
模擬退火法 跟爬山法一樣通常是用來尋找最佳解的演算法,其來源是模擬冶金學中退火的原理。
在冶金時,退火是將材料加熱後再讓它經由特定的速率使其慢慢冷卻的過程,這樣的機制可以幫助金屬減少其中的缺陷。因此在冶金中,升溫打鐵並退火冷卻的過程會不斷重複著,直到達到滿意的晶體為止。
而這種機制運用到演算法來看的話,可以想像他是一個類似爬山法的概念,如果它往好的方向移動了,那麼沒話說,接受這個結果並繼續前進 (打鐵升溫);
但如果發現結果是往比較差的方向移動 (表示目前可能已經卡在局部最佳解),這個時候模擬退火就會以一定的機率接受這個結果 (退火),具體的接受機率取決於參數的設定 (初始溫度、退火速率、運行的次數等等)。
我們以昨天同一張圖來做說明:
假設我們從最右方出發,目標是找到最大的解,那麼一開始沒有懸念的一路往左邊上方移動,當地一次來到平坦的局部最佳解時 ("flat" local maximum),如果是爬山法此時直接放棄球賽結束
然而我們從不輕言放棄的辣個男人 三井壽 模擬退火法 靠著降溫退火的機制,到了這個台地時,有一定的機率去接受自己往左邊的下坡處移動,而當退火退到了另一個低谷後,前方又是一片光明,又可以開心的往上爬了,反正人生嘛,有起才有落,有落才有起
就這樣經過幾次爬到高點 (打鐵升溫) 再往低處移動 (退火降溫) 後,最終模擬退火法能夠比爬山法有更高的機率去找到 全域最佳解。
今天要介紹的另一個演算法跟昨天的 螞蟻演算法 一樣都是模擬自然界生物習性所發展出來的演算法,而蜂群演算法模擬的是蜜蜂群 極高效率的採花蜜行為 。
大自然裡蜜蜂採蜜時,首先會先由偵查蜂出去尋找,一旦找到了已經開花的蜜源,就會將花蜜吸滿、帶回巢穴裡分給巢穴裡的蜜蜂夥伴讓它門熟悉花蜜的甜味與香味,同時,它會用翅膀擺動身體開始跳舞,用舞蹈來告訴同伴我找到的花蜜在哪個方向、距離多遠等等...
而這時候得到訊息的其他外勤蜂就會依照得到的資訊飛往花蜜的所在區域並大量的將花蜜採回巢穴裡。
那麼對應到蜂群演算法裡,首先我們將蜂群分為偵查蜂、引領蜂以及跟隨蜂三種,花蜜即為我們可以找到的解,每一個花蜜代表一個可能的解,而目標是找到最佳的花蜜 (最佳解, 具體如何定義依照問題而不同)。
而在中間每一次的搜尋過程中,引領蜂以及跟隨蜂的作用為先後開採花蜜,也就是尋找最佳解,而偵查蜂的目標則是觀察找到的解是否陷入局部最佳解 (如同前面爬山法所介紹的相對高點),若是發現到已經陷入了局部最佳解的情況,則重新隨機去搜尋新的花蜜源 (其他解)。
我們把流程簡化一點來看:
經過這幾天的幾個演算法介紹,不知道大家是否慢慢的對於一些專有名詞慢慢覺得熟悉了,並且感覺好像這些演算法都會有類似的設計,例如
那麼明天我們來聊聊比較不一樣的AI演算法來幫這系列的最後一篇劃上句號,之後我們就開始來聊聊AI是如何應用在作曲上以及目前有哪些公司已經做出具有相當水準的應用。 或是放棄去過個開心的週末