遗传演算法之

1、遺傳演算法之遺傳演算法之Interactive Evolutionary Algorithms(IEA)資管系 王柳鋐2Introduction(1/7) Interactive GA/EA = GA/EA + Interaction with human Why Interaction? 以Conventional GA/EA解問題 決定編碼(gene representation)的方式 提供 fitness functions 以便進行 selection/reproduction 提供genetic operators exploration of the search space e

2、xploitation of genetic material 三事俱備, GA/EA得以進行 例: TSP, 工程控制問題, scheduling, 決策, data mining But, 如果無法提供上述三者之一? 無適當編碼, 無好用之operators - bad solution quality 無適當fitness function - right answers for wrong problem3Introduction(2/7) Why cant we provide an appropriate fitness function? 問題優劣的評估牽涉到 直覺(intuit

3、ion), 偏好(preference), 主觀意識(subjectivity), 感覺(sensation), 感官知覺(perception), 認知(cognition), 心理運作(psychological processing)很難定義一個數學函式來代表fitness function 好不好吃? 好不好聽? 好不好看? 像不像? 好不好用? 好不好玩 ? What can we do ? 由人來評估 由人取代selection function4Introduction(3/7) Interactive GA/EA的執行流程Initialize population;while(

4、The terminating condition is not satisfied) Present individuals to the user;/ phenotype or genotype The user gives the scores(evaluation) ; Reproduce individuals based on the users evaluation(selection); Apply genetic operators to the survived individuals after selection;1. 必須具體呈現各個individuals 因此,us

5、er interface好壞有決定性影響2. 該呈現individuals的表現型(phenotype) 或基因型(genotype)則不一定,以讓使用 者能有最佳評分的環境為原則5Introduction(4/7) Interactive GA/EA搜尋解答的概念真正的解答空間IGA/EA操作的解答空間使用者心中的解答IGA/EA呈現的解答使用者根據主觀意識考量facter 1,2,m,所給的分數d(指與心中解答的距離)評分解答空間的轉換空間轉換後,使用者給的距離d,轉化為GA的fitness value : dGA操作6Introduction(5/7) IGA/EA面臨的技術難題 IGA

6、/EA雖然透過讓human加入評估的方式,解決fitness function難以決定的難題,卻也引來另一些技術問題 human fatigue (疲勞) problem population size太大, user評估困難 跨多個畫面,造成前後標準不一因此, population size通常都很小 然而, population size小 收斂困難, 因此必須執行許多代 fatigue problem ! 技術有待解決 population要小(畫面大小,人類記憶) 不能執行太多代,(Takagi建議1020代) 但要能找到滿意解(near-optima,非local optima)7I

7、ntroduction(6/7) 解決human fatigue problem的方向 Prediction 適當的individuals展示順序,有助於減輕user評估時的負擔 預測user的喜好,根據喜好順序展示individuals 預測方法 Neural Network Euclidian distance 增加user的權利 human fatigue problem 部分原因來自單調 增加user評估individuals可做的動作 例 : 評估時允許user直接修改GP tree 當user權利擴充之後 another kind of IGA/EA : HBGA Human Ba

8、sed Genetic Algorithms8Introduction(7/7) Applications of IGA/EA 藝術方面 artificial life(art, animal & plant) car design dress design rhythm production(音樂) 工程方面 recovering filter for distorted speech facial recognition for criminal identification data mining MRI image enhancement9Human Based Genetic

9、 Algorithms(1/4) 以Conventional GA/EA解問題 決定編碼(gene representation)的方式 提供 fitness functions 以便進行 selection/reproduction 提供genetic operators(re-combination operators) exploration of the search space exploitation of genetic material IGA/EA : 由人充當selection operator How about the human as a recombination

10、operator? 由人充當和crossover / mutation 一樣角色的operator Creating new individuals10Human Based Genetic Algorithms(2/4) Human Based Genetic Algorithms(HBGA) 人可以擔任selection operator的角色(評估) 也可以擔任recombination operator的角色(創造) HBGA is also a multi-agent system11Human Based Genetic Algorithms(3/4) HBGA流程Initiali

11、ze population in the Central Agent;while(The terminating condition is not satisfied) Present individuals to the user agents; Some user agents give the scores(evaluation) and the others can create new individuals(recombination); Central agent is responsible for coordinating the results between user agents(orgnization);12Human Bas