MichaelLin 的部落格

[Term-Project]基因演算法

"基因演算法(Genetic Algorithm) 一、前言: 基因演算法是一種模仿大自然界中,物競天擇和基因交配的演算方式。它進來頗引人注意,因為一些傳統人工智慧方法無法有效解決的計算問題,它都可以很快速地找出答案來。基本上來說,基因演算法是一種特殊的搜尋技巧,適合處理多變數非線性的問題。 基因演算法採用三種基本的運作機制以模仿自然遺傳的過程,包括複製(Reproduction)、交配(Crossover)、突變(Mutation),能在合理的時間範圍內求得近似最佳解。 

   二、基因演算法簡述:基因演算法(Genetic Algorithm)其實是取法大自然的一種演算法,藉著對於演化現象的觀察,John H. Holland 認為可以透過把問題轉為基因型(Genotype),利用競爭-生存以及基因交換-突變,尋求出問題的正確解答。透過競爭-生存,擁有好基因的品種會有較高的機會生存到下一代,而與生存較無關的基因則會隨著時間逐漸被淘汰,。在理想的狀態下,競爭-生存會迫使不具優勢的品種逐漸消失。然而單單擁有一種好基因是不夠的;透過基因的交配,不同的個體可以把它們的好基因組合起來,變成更具優勢的下一代;而若是組合出來的後代不理想,也只會加速被淘汰。但交換基因也不能改變現有的基因狀態,還要再配合突變,才能夠產生革命性的改變,進而對族群進步有突破性的發展。因此,"生存-競爭""交配""突變"就是整個基因演算法,也可以說是演化的中心思想。 三、基因演算法的基本元素:第一個是基因;沒有基因來當作媒介,我們沒有辦法進行基因演算法,但是要怎麼表現基因呢?以電腦世界而言,最常見的就是 0 1 的組合形成的"Bit String",例如:0010 就是一個四個位元的 bit string。用四個位元就可以表現出十六種基因組合,而不同的基因組合又可以對照到不同的"表現型"上,例如第一個 bit 表示顏色、第二個 bit 表示長度,第三個 bit 表示色調等等。除了固定長度的基因之外,也可以採用不定長度的基因;例如,假如要用英文字測試是否能夠演化出一本莎士比亞全集,就可以採用不定長度的基因,讓莎士比亞全集由最早的英文單字逐漸長到厚厚數本書這麼大。利用適合的基因表達方式,才能夠讓問題更容易利用演化的方式找到解答。如果問題本身不適合用固定長度來表達,就可以考慮用不定長度的基因;相對的,如果問題本身不需要不定長度就可以解決,用不定長度基因型反而會造成程式更慢找到解答。第二個是適應函式(fitness function);適應函式是用來測試個體在現在的環境中的適應程度,一般而言,適應得越好得分越高,也就會給它更高的機會傳遞它的基因給下一代。舉例來說,如果要程式要找出基因中全都是 1 沒有 0 的個體,那麼適應函式就可以計算現在個體的基因中有幾個 1適應函式其實就是所謂的"環境";適應函式不但要考慮個體相對於整體的表現,還要考慮在不同時期給予個體不同的壓力。例如,程式不太可能在一開始就亂數產生出英文中合文法的句子,這時候就要比較寬容一點給分給鬆一點;等到後期程式已經抓到語法的訣竅,那麼有一個拼字錯誤,或許就會被扣不少分數。第三個是選擇函式(selection function);一般來說,選擇函式都會依照適應函式的分數來作為判斷依據,但選擇有很多方式,最簡單的就是前面一半就晉級,另外也有依照得分多寡加權計算機率的,甚至於保送到下一代的方式。選擇函式做的就是"天擇"的動作。不同的選擇函式各有優缺點,也有其道理所在,請容以後再詳述。第四個是交配方式(crossover);由選擇函式中選出的兩個個體的基因要如何重組?在固定的點切開一人一份,還是可以在任意點切開來組合?對不定長度的基因,是用模組/區塊的方式重組交配還是同樣在固定點切開?這都要依照目標的不同而調整。最後是突變方式(mutation);個體在什麼樣的狀況下會突變?突變的地方又是在哪裡?突變之後會變成什麼值?這些都是可以考慮的。 四、程式架構: 現今電腦中當然沒有所謂的生物基因物質,倒是有一大堆01所組成的記憶體。所以基因演算法就用一串01所組成的字串,來代表基因物質。通常此字串用來表示問題目前搜尋的結果,你必須依問題特性設計編碼的方法。基因演算法就在一堆字串中間進行人工的演化,用類似基因複製時所進行的程序(交叉配對、基因複製和基因突變),產生新的子代字串。然後從中挑選「優秀」的字串們,重複以上動作,直到產生符合成功條件的結果為止。 如底下步驟:1.   產生一堆字串,形成一個大族群。2.   評估每個字串的分數。檢查結束條件是否成立?3.   選擇優秀的字串。4.   進行字串間的交配演化動作(交叉配對、基因複製和基因突變),產生新的子代字串。跳回步驟2              五、結語:「基因演算法」的應用層面相當廣泛,例如:排程、資源配置、生產計劃……等等,皆須應用到基因演算法。先前曾在批踢踢上與人討論一個Case,希望能在大學四年內以打工的方式,來賺取實際寫作的經驗,但對方要求使用「基因演算法」,此演算法當時沒聽過也沒學過,因此只好選擇放棄。現在,我以這個當作我期末的Project,希望能將之前吃鱉的演算法,利用這個機會好好的研究,才不會下次機會來了,但仍沒有這個實力撰寫程式。 參考資料:1.    http://pesty.yichi.org/blog/2.    http://www.weikeg.com.tw/download/clisp2_files/p15.html3.    http://nmlab.mis.nchu.edu.tw/elearn/archives/ga-for-%20itemselect.ppt#269,5,基因演算法[@more@]"

[Pre Class] PageRank

"簡單的

假設一個由4個頁面組成的小團體:ABCD。如果所有頁面都鏈向A,那麼APR(PageRank)值將是BCD的和。

PR(A) = PR(B) + PR(C) + PR(D)

繼續假設B也有連結到C,並且D也有連結到包括A的3個頁面。一個頁面不能投票2次。所以B給每個頁面半票。以同樣的邏輯D投出的票只有三分之一算到了A的 PageRank 上。

換句話說,根據鏈處總數平分一個頁面的PR值。

最後,所有這些被換算為一個百分比再乘上一個係數q。由於下面的演算法,沒有頁面的PageRank會是0。所以,Google通過數學系統給了每個頁面一個最小值1 − q

所以一個頁面的 PageRank 是由其他頁面的PageRank計算得到。Google 不斷的重複計算每個頁面的 PageRank。如果您給每個頁面一個隨機 PageRank 值(非0),那麼經過不斷的重複計算,這些頁面的 PR 值會趨向於正常和穩定。這就是搜索引擎使用它的原因。

完整的

這個方程式引入了隨機瀏覽的概念,即有人上網無聊隨機打開一些頁面,點一些連結。一個頁面的PageRank值也影響了它被隨機瀏覽的機率。為了便於理解,這裡假設上網者不斷點網頁上的連結,最終到了一個沒有任何鏈出頁面的網頁,這時候上網者會隨機到另外的網頁開始瀏覽。

為了對那些有鏈出的頁面公平,q = 0.15(q的意義見上文)的演算法被用到了所有頁面上, 估算頁面可能被上網者放入書籤的機率。

所以,這個等式如下:

p1,p2,...,pN是被研究的頁面,M(pi)是鏈入pi頁面的數量,L(pj)pj鏈出頁面的數量,而N是所有頁面的數量。

PageRank值是一個特殊矩陣中的特徵向量。這個特徵向量為

R是等式的答案

如果pj不鏈向pi, 而且對每個j都成立時,等於 0

這項技術主要的弊端是,舊的頁面等級會比新頁面高,因為新頁面,即使是非常好的頁面,也不會有很多連結,除非他是一個站點的子站點。

這就是 PageRank 需要多項演算法結合的原因。PageRank 似乎傾向於維基百科頁面,在條目名稱的搜索結果中總在大多數或者其他所有頁面之前。原因主要是維基百科內相互的連結很多,並且有很多站點鏈入。

資料來源:維基百科(http://zh.wikipedia.org/w/index.php?title=PageRank&variant=zh-tw)

[@more@]"

Dynamic programming

"

In computer science, dynamic programming is a method of solving problems exhibiting the properties of overlapping subproblems and optimal substructure (described below) that takes much less time than naive methods.

The term was originally used in the 1940s by Richard Bellman to describe the process of solving problems where one needs to find the best decisions one after another. By 1953, he had refined this to the modern meaning. The field was founded as a systems analysis and engineering topic which is recognized by the IEEE. Bellman's contribution is remembered in the name of the Bellman equation, a key result.

The word "programming" in "dynamic programming" has no particular connection to computer programming at all. A program is, instead, the plan for action that is produced. For instance, a finalized schedule of events at an exhibition is sometimes called a program. Programming, in this sense, is finding an acceptable plan of action.

 資料來源:維基百科(http://en.wikipedia.org/wiki/Dynamic_programming)

[@more@]"

[Pre-class]RSA加密演算法

"

RSA加密演算法是一種非對稱加密演算法。在公鑰加密標準電子商業中RSA被廣泛使用。RSA是1977年羅納德·李維斯特(Ron Rivest)、阿迪·薩莫爾(Adi Shamir)和倫納德·阿德曼(Leonard Adleman)一起提出的。當時他們三人都在麻省理工學院工作。RSA就是他們三人姓氏開頭字母拼在一起組成的。

1973年,在英國政府通訊總部工作的數學家克利福德·柯克斯(Clifford Cocks)在一個內部文件中提出了一個相應的演算法,但他的發現被列入機密,一直到1997年未被發表。

RSA演算法的可靠性基於分解極大的整數是很困難的。假如有人找到一種很快的分解因子的演算法的話,那麼用RSA加密的信息的可靠性就肯定會極度下降。但找到這樣的演算法的可能性是非常小的。今天只有短的RSA鑰匙才可能被強力方式解破。到2004年為止,世界上還沒有任何可靠的攻擊RSA演算法的方式。只要其鑰匙的長度足夠長,用RSA加密的信息實際上是不能被解破的。

1983年麻省理工學院在美國為RSA演算法申請了專利。這個專利2000年9月21日失效。由於該演算法在申請專利前就已經被發表了,在世界上大多數其它地區這個專利權不被承認。

資料來源:維基百科(http://zh.wikipedia.org/w/index.php?title=RSA&variant=zh-tw)

[@more@]"

[Pre-class]RSA加密演算法

"

RSA加密演算法是一種非對稱加密演算法。在公鑰加密標準電子商業中RSA被廣泛使用。RSA是1977年羅納德·李維斯特(Ron Rivest)、阿迪·薩莫爾(Adi Shamir)和倫納德·阿德曼(Leonard Adleman)一起提出的。當時他們三人都在麻省理工學院工作。RSA就是他們三人姓氏開頭字母拼在一起組成的。

1973年,在英國政府通訊總部工作的數學家克利福德·柯克斯(Clifford Cocks)在一個內部文件中提出了一個相應的演算法,但他的發現被列入機密,一直到1997年未被發表。

RSA演算法的可靠性基於分解極大的整數是很困難的。假如有人找到一種很快的分解因子的演算法的話,那麼用RSA加密的信息的可靠性就肯定會極度下降。但找到這樣的演算法的可能性是非常小的。今天只有短的RSA鑰匙才可能被強力方式解破。到2004年為止,世界上還沒有任何可靠的攻擊RSA演算法的方式。只要其鑰匙的長度足夠長,用RSA加密的信息實際上是不能被解破的。

1983年麻省理工學院在美國為RSA演算法申請了專利。這個專利2000年9月21日失效。由於該演算法在申請專利前就已經被發表了,在世界上大多數其它地區這個專利權不被承認。

資料來源:維基百科(http://zh.wikipedia.org/w/index.php?title=RSA&variant=zh-tw)

[@more@]"

Backtracking

"

Backtracking algorithms try each possibility until they find the right one. It is a depth-first search of the set of possible solutions. During the search, if an alternative doesn't work, the search backtracks to the choice point, the place which presented different alternatives, and tries the next alternative. When the alternatives are exhausted, the search returns to the previous choice point and tries the next alternative there. If there are no more choice points, the search fails.

This is usually achieved in a recursive function where each instance takes one more variable and alternatively assigns all the available values to it, keeping the one that is consistent with subsequent recursive calls. Backtracking is similar to a depth-first search but uses even less space, keeping just one current solution state and updating it.

In order to speed up the search, when a value is selected, before making the recursive call, the algorithm either deletes that value from conflicting unassigned domains (forward checking) or checks all the constraints to see what other values this newly-assigned value excludes (constraint propagation). This is the most efficient technique for certain problems like 0/1 knapsack and n-queen problem. It gives better results than dynamic programming for these problems.

資料來源:http://en.wikipedia.org/wiki/Backtracking

[@more@]"

[Pre class]Greedy algorithm

"

貪心法Greedy algorithm ,直譯:貪心演算法) 是一種在每一步選擇中都採取在當前狀態下最好或最優(即最有利)的選擇,從而希望導致結果是最好或最優的演算法。比如在旅行推銷員問題中,如果旅行員每次都選擇最近的城市,那這就是一種貪心演算法。

貪心演算法在有最優子結構的問題中尤為有效。最優子結構的意思是局部最優解能決定全局最優解。簡單地說,問題能夠分解成子問題來解決,子問題的最優解能遞推到最終問題的最優解。

貪心演算法與動態規劃的不同在於它每對每個子問題的解決方案都做出選擇,不能回退。動態規劃則會保存以前的運算結果,並根據以前的結果對當前進行選擇,有回退功能。

貪心法可以解決一些最優性問題,如:求中的最小生成樹、求哈夫曼編碼……對於其他問題,貪心法一般不能得到我們所要求的答案。一旦一個問題可以通過貪心法來解決,那麼貪心法一般是解決這個問題的最好辦法。由於貪心法的高效性以及其所求得的答案比較接近最優結果,貪心法也可以用作輔助演算法或者直接解決一些要求結果不特別精確的問題。

 資料來源:維基百科(http://zh.wikipedia.org/w/index.php?title=%E9%A6%96%E9%A1%B5&variant=zh-tw)

[@more@]"

[Project Proposal] 基因演算法 494511627 林暐翔

"

之前在PTT上看到有人需要幫忙撰寫程式

我想說既然讀資工就要在就學期間接一些CASE

以增加自己的一些經驗及能力

只不過經過我與對方的對談之後

發現對方需要基因演算法的基礎(殘念‧‧‧我不會!)

因此希望藉由這次的研究

搞清楚我所不會的演算法以增加我的實力

參考資料:http://pesty.yichi.org/blog/category/%e5%9f%ba%e5%9b%a0%e6%bc%94%e7%ae%97%e6%b3%95/

[@more@]"

[Project Proposal] 基因演算法 494511627 林暐翔

"

之前在PTT上看到有人需要幫忙撰寫程式

我想說既然讀資工就要在就學期間接一些CASE

以增加自己的一些經驗及能力

只不過經過我與對方的對談之後

發現對方需要基因演算法的基礎(殘念‧‧‧我不會!)

因此希望藉由這次的研究

搞清楚我所不會的演算法以增加我的實力

參考資料:http://pesty.yichi.org/blog/category/%e5%9f%ba%e5%9b%a0%e6%bc%94%e7%ae%97%e6%b3%95/

[@more@]"

頁面