《运用演化式机率提高IGA演化绩效》由会员分享，可在线阅读，更多相关《运用演化式机率提高IGA演化绩效（29页珍藏版）》请在金锄头文库上搜索。
1、運用演化式機率提高IGA演化績效:字型設計之研究卓聖威真理大學資訊管理學系許瑋玲真理大學資訊管理學系摘要 IGA是一種普遍被應用在創意設計的方法。本研究將利用IGA去做創意字型的設計，作為研究的基本架構。IGA的創意評估來自於使用者的評分，也就是使用者去決定適應值。傳統的IGA會遭遇一些問題，(1)傳統IGA收斂緩慢，將會讓使用者產生疲勞。(2)傳統IGA無法涵蓋所有的解答空間，所以傳統的IGA找出的解答往往只是讓使用者滿意的解答，而不是最佳解。本研究將針對IGA的適應值去做預測機制的研究，利用預測機制加速IGA的收斂，改善傳統IGA遭遇的問題。 類神經網路(NN)是一種常用於預測機制的方式，
2、利用模擬人類神經網路去不斷的學習訓練，將所建立的訓練機制用於預測上面。本研究則採用演化式機率(ALP)作為預測機制，ALP則是利用預測機率以及漸進式學習模型的概念，將N個問題與解答配對作為學習的條件，當出現第N+1個問題，漸進式學習模型便會根據先前學習的結果，產生答案N+1的機率分佈。 本研究將探討ALP-IGA與傳統IGA的比較，會把ALP-IGA與傳統IGA去做比較，去證實加入ALP預測機制的IGA可以有效解決傳統IGA收斂緩慢的問題。關鍵字: 互動式遺傳演算法(IGA)，演化式機率(ALP)，類神經網路(NN)壹、研究動機與研究問題 互動式遺傳演算法(IGA)在過去的研究中已被大量用於許
3、多目標函數待搜尋的複雜多準則決策問題上，IGA利用了遺傳演算法搜尋解答的能力，以及使用人的主觀評估去定義出多準則問題的目標函數。 因此IGA較適合應用於目標函數未被明確定義或是屬於主觀評估問題價值的決策上，而IGA在過去的幾十年中，實例應用則被廣泛的應用於藝術設計及商品設計的問題上。 首先我們必須瞭解IGA為何會被廣泛的應用於藝術設計或是商品設計。IGA是藉由與人互動的方式扮演所謂目標函數，人們藉由自己主觀意識去評定自己所謂的喜愛而定出心目中的標準。令一方面IGA透由GA全域找尋解答的能力，搭配人們所給定的目標函數去找尋出答案。 人的主觀意識往往來自於每個人對事情的認知不同，所以對於設計的創意
4、來源也有所不同。IGA藉由與人們之間的互動搭配GA全域搜尋的能力，解決創意設計需求的問題。在文獻探討的過程中，我們將會發現IGA的重點不外乎是在1.如何藉由人去評估目標函數2.提升目標函數的準確度3.藉由GA演化出解答。 本研究將從知識學習的角度，去提升目標函數的準確度，探討利用演化式機率(ALP)為基礎的學習目標函數的IGA是否能較傳統的IGA更為有效。 IGA雖然已經被運用於許多領域，但其方法上仍存在一些問題。本研究認為傳統IGA存在兩個主要的問題4,5,6,7：一、傳統IGA收斂緩慢的問題 傳統IGA由於需要人的參與評估每一代的個體，人會因為演化代數過多或是需要的評分個數太多而產生負擔過
5、重、疲勞等問題。一旦人們覺得負擔過重，就可能會對評分胡亂做答，甚至產生不作答的情形。這樣的話由人所決定的目標函數就會發生誤差，而無法找到人們真正的偏好。為了減低人們的疲勞，就必須在極少的族群以及極短代數的條件下找出最佳解。 而傳統IGA很難在很短的代數之內減少評分的個數找出最佳解，要找出最佳解往往又得去增加演化的代數，但卻又會造成疲勞的問題。所以爲了提高IGA的實用性，我們有必要針對傳統IGA進行方法的改善，以提高傳統IGA演化績效，加速IGA的收斂。二、傳統IGA的解答空間不一定涵蓋人們的目標 所以人們透過IGA系統進行設計時，不管怎樣去進行演化，都很難去找出完全滿意的答案。 傳統的IGA對
6、於評分個體仍是亂數決定而來，這樣的做法不一定所抽取的為所想要的。亂數的抽取是無序的，而為了使其從無序轉換為有序的，必須突破一個臨界點；也就是說為了偏離隨機，必須加入預測的模式，做為突破的臨界點，使其具有偏離隨機的性質。12 為了解決傳統IGA的問題，本研究導入了預測的機制，對於IGA的Fitness值加速收斂速度。經由預測的機制搭配IGA去從事字體設計的工作。 類神經網路是一個廣泛被應用的預測機制，而本研究根據Solomonoff21,22,23的研究，將導入另一種的預測機制-演化式機率(Algorithmic Probability，ALP)，藉由預測機制去做漸進式的學習，以發展出一套漸進式
7、機器學習模型搭配IGA去從事字體設計工作。 預測可以加速IGA的收斂，提升IGA目標函數的準確度。類神經與ALP都可用來做學習的預測。 類神經網路根據學習法則，透由訓練以調整連結練加權值的方式完成學習目標的收斂，利用所學習而成的學習目標與實際值所造成的誤差去倒傳遞再一次學習，直到學習達到可接受的合理誤差，完成學習的過程。在藉由所學習的學習目標去做合理的預測。 而Solomonoff21,22,23所提出的演算式機率(ALP)則是利用分別學習的觀念，去分析每一個學習機制學習到事件發生時所發生的機率，透過各個學習機制的機率分布去調整各個學習機制的比重，再藉由先驗機率去調整預測函數，完成所謂的預測機
8、制。 纇神經雖然是個廣泛應用於預測的方式，可是將類神經應用於IGA做為適應值的預測機制時，會遇到一些問題2：(一) 類神經只能做單一目的，無法拓展應用。(二) 類神經預測訓練不具有彈性。(三) 類神經需要大量的訓練資料，較無助於加速IGA的收斂。 纇神經與ALP都可以去做預測，但是類神經是一個黑盒子，雖然可以藉由訓練去找出規則做預測，可是類神經無法得知這規則是從什麼原因而來的。類神經就是利用一個黑箱，把數據丟進去訓練它，訓練完就成為一個可以用的工具，至於這個黑箱的如何變化卻無法知道。類神經無法得知權重，即水準效用值內所隱含的意義。當A資料進去訓練與B資料進去訓練出一套結果，可是當C資料去訓練時
9、，並分套用A或B的訓練成果，就可以達到C結果的預測。類神經無法得知水準與水準之間的關係為何，因為類神經是黑箱作業的預測模式。 因此類神經必須分別訓練，想達成A的預測則需做A的訓練，想做B的預測也需做B的訓練。類神經的訓練雖然可以使誤差值極小，易於受於控制。可是每次預測都得各自訓練，這樣的做法使得類神經缺乏彈性。 ALP則不受此限制，ALP即使預測A的水準與B的水準，也可同時得知水準與水準彼此的相關程度。ALP的權重可以調整與水準具相關系，而類神經的權重只是為了訓練因應而生的，與水準無法產生直接的關聯。其權重的目的 只是為了訓練調整，讓答案對而已，使誤差值變小。ALP的權重可以與水準效用值做相關
10、的對應。ALP可藉由水準與權重之間的關係去發現關鍵的因素，類神經只能做單一目的，因為類神經與訓練的資料相關，不同關係的訓練資料都需個別訓練。因此類神經無法拓展彼此的應用，而ALP可以把分數去拆給各個成分效用值，找出彼此的關聯性。 本研究根據Solomonoff21,22,23的研究，導入演化式機率(Algorithmic Probability，ALP)以發展出一套漸進式機器學習模型，搭配IGA去從事字體設計的工作。 所謂的漸進式機器學習，是指IGA的系統透由人們所決定的目標函數去學習，藉由先前學習的結果，產生答案的機率分佈，透過ALP的方法去分析目標函數預測人們的偏好，透過此反覆的學習過程找
11、出符合解答的預測目標函數。 這樣的作法有幾個好處: 透由ALP所設計的機器學習法搭配上IGA比傳統IGA較具彈性。因為ALP可以去預測人們的偏好。藉著ALP-IGA提高目標函數的準度。(一) 透由ALP所設計的機器學習模型可以加速IGA收斂，解決傳統IGA收斂緩慢的問題。(二) ALP-IGA具有預測學習的效能，具備了偏離隨機的性質。 古典機率是利用原先的事前機率結合額外的資訊(條件機率)，去導出事後的機率達到預測的目的，即所謂的貝氏定理(Bayes Theorem)。可是古典機率的預測需要大量的訓練資料達到預測的準度。由Solomonoff研究的ALP理論就可以補強古典機率分佈之不足。ALP
12、理論可以跳出古典機率大量資料的限制，即使在少量的訓練資料，也能學習到正確的預測目標函數。然而預測雖然具有偏離隨機的性質，可是偏離隨機並不是一下子就完成的，是一點一點累積而成的。所以ALP的預測還需要藉由IGA去做累積知識的工作。 故本研究將發展出一個以ALP所設計的機器學習模型搭配IGA的字體設計系統框架。在這個框架裡，我們會把人們所決定的目標函數，交由ALP機器去做漸進學習，預測出偏好的目標函數，透由IGA的方法去實做。最後，我們會將ALP-IGA與傳統IGA去做效益的比較評估。貳、文獻探討一、遺傳演算法(GA) 遺傳演算法(genetic algorithm，GA)是根據達爾文的進化論為基
13、礎，模擬自然界演化的程序，就是達爾文說的物競天擇，適者生存的自然演化機制為理論基礎所發展出來的演算法。GA最早由Holland(1975)18所提出，藉由遺傳演算法的流程可以為目標明確的問題找出適切的解答。二、互動式遺傳演算法(IGA) 由於GA需要一個目標函數來計算個體的適應值，所以GA適合用在目標函數確定的問題之上。然而，有些問題的目標函數卻不一定明確，其評估在於人的主觀衡量，這些問題的目標函數是隱含在每個人的心理，我們很難定義出一組適當的目標函數來衡量它，因此GA在解決這類問題時就出現了困難。 交談式遺傳演算法(Interactive Genetic Algorithm，IGA)就是為了
14、要解決上述的問題而發展出來的。IGA的主要概念，就是以人來扮演GA中適應值的角色，其適應值是由IGA的使用者根據其對問題的主觀評估來給定，而其餘的演化過程則與傳統GA相同。 IGA可以透過與使用者互動的過程，進行邊看邊選的決策過程，對於解決決策者尋找目標，決策者的偏好隨著決策分析進行而改變的多準則決策問題有著優異的能力。 Caldwell and Johnston(1991)15首次將IGA應用於嫌犯臉譜指認，這是IGA最早的研究。目擊者依照他對嫌犯的外表印象，對每一代的臉譜作出評分，而GA系統則依照此適應值來演化產生下一代臉譜，直到產生滿意的嫌犯臉譜為止。證實IGA可以幫助我們再目標無法完整
15、定義或描述的問題，有效的找出心目中的最佳解。 Aoki and Takagi(1997)以3D電腦繪圖的光線設計來驗證IGA在3D電腦繪圖領域的設計能力，文中顯示出IGA系統可以有效的幫助非專業設計者來進行設計，尤其是對於經驗或是能力不高的使用者而言。 Banzhaf(1977)14實際應用了互動演化的系統在工程設計的領域，而且將IGA應用在消費市場客製化的系統之中，此系統可以讓消費者設計屬於自己獨一無二的產品設計，公司也可以利用此一系統追蹤顧客的活動找出最佳的產品設計。 由此可知，近幾十年，IGA已經被廣泛的應用於圖形藝術以及工業設計之中。三、演算式機率(ALP) 歸納式推論(inductive inference)是Solomonoff於1964提出的人工智慧問題解決模型。Solomonoff認為所有的推論問題都可轉換為二元字串(binary string)的外插(extrapolation)問題。換句話說，給定一個長度為的二元字串x，任由其隨機指定輸入，但需由之前所輸出的前位元的x字串中，去預測x字串之後緊接著輸出會出現”1”的機率。則所謂的推論問題便是用統計上的貝式定理(Bayes theorem)推估而出的。可以用下列式子表示之： (1) 其中x1,x0分別代表字串x後出現1或0的組合字元，PM(x)是給予任意輸入字串s，PM(x1)市字串s
