2018/11/22 Developing a Visualization Tool for Spider Web-Building Algorithms 模擬蜘蛛結網之演算法設計及視覺化工具開發 指導教授：尹邦嚴 陳怡孜 陳瑩哲 沈扇綸 郭怡君 老師 各位來賓大家好，我們是國立暨南國際大學資訊管理學系，今天很榮幸能夠來這裡跟大家一起分享.

Presentation on theme: "2018/11/22 Developing a Visualization Tool for Spider Web-Building Algorithms 模擬蜘蛛結網之演算法設計及視覺化工具開發 指導教授：尹邦嚴 陳怡孜 陳瑩哲 沈扇綸 郭怡君 老師 各位來賓大家好，我們是國立暨南國際大學資訊管理學系，今天很榮幸能夠來這裡跟大家一起分享."— Presentation transcript:

1 2018/11/22 Developing a Visualization Tool for Spider Web-Building Algorithms 模擬蜘蛛結網之演算法設計及視覺化工具開發 指導教授：尹邦嚴 陳怡孜 陳瑩哲 沈扇綸 郭怡君 老師 各位來賓大家好，我們是國立暨南國際大學資訊管理學系，今天很榮幸能夠來這裡跟大家一起分享 這一年由尹邦嚴老師帶領我們所研究的模擬蜘蛛結網之演算法設計及視覺化工具開發，以下這些是我們的研究伙伴，我是陳怡孜， 2018/11/22 OPlab, IM, NTU

2 Outline Introduction Literature review
2018/11/22 Outline Introduction Abstract Motivation Literature review Artificial Intelligence Related spider papers Spider web-building algorithm design Visualization tool prototype of the model Internal factors External factors Conclusion and future work 今天我們會分五個部分來介紹我們的研究內容，首先我們會先由摘要跟動機的部分來分享，當初選定這個研究的原因，再來是一些和本研究相關的文獻簡介，第三部份我們會介紹本研究所設計的蜘蛛結網演算法，皆下來則是利用視覺化的工具開發第三部份設計的model，最後則是結論跟未來的相關研究 2018/11/22 OPlab, IM, NTU

3 I. Introduction 1/2 Abstract
Sequential behavior of spider web-building model Internal factors of the spider web-building model External factors of the spider web-building model Implementation of visualization tool 2018/11/22 OPlab, IM, NTU

4 I. Introduction 2/2 Motivation Figure 1. The motivation of the model
2018/11/22 I. Introduction 2/2 Motivation 目前在歐洲有一各學派叫做complex system 稱做複雜氏系統 ，這些學者將一些生物觀察學家有推論出來的生物習慣規則利用電腦程式的方式來模擬，這樣的模擬方式有幾個好處 第一：不同的地區的學者可以利用視覺化的程式了瞭解生物的行為表現，這種方式當然比傳統的拍照錄影的方式更好，拍照攝影耗時間更耗費錢，很多生物學家是很窮的 第二 有些生物研究是需要觀察生殖繁延世代交替的行為，要等生物一代一代繁殖是很花時間的，利用電腦模擬預測的話，可以使研究更有效率 在人工智慧的部份，在傳統的人工智慧都是以簡單的邏輯來表示，但是這種表示方法已經遇到瓶頸了，因為智慧不可能單單只用if else來表示，所以很多學者利用大自然的智慧來結決人工智慧的瓶頸 在應用的部份，現在已經有一些演算法，如ACO螞蟻演算法 (Dorigo, 1992) 被用來求推銷員求解的問題 因此我們在研讀了一些關於蜘蛛生物學的資料發現，生物學家對蜘蛛結網的觀察都已經詳細的敘述，因此我們決定蜘蛛結網規則建立model並且設計成演算法，讓蜘蛛結網演算法也能用來解決現實生活中的問題 Figure 1. The motivation of the model 2018/11/22 OPlab, IM, NTU

5 Outline Introduction Literature review
2018/11/22 Outline Introduction Abstract Motivation Literature review Artificial Intelligence Related spider papers Spider web-building algorithm design Visualization tool prototype of the model Internal factors External factors Conclusion and future work 在簡介完我們的研究之後，現在介紹一下在人工智慧中與生物相關的演算法 以及 生物學中與蜘蛛相關的研究 2018/11/22 OPlab, IM, NTU

6 Artificial Intelligence
2018/11/22 II. Literature review　1/3 Artificial Intelligence Swarm intelligence Geese migratine –fly in a “V” formation Bees and wag-tail dance Ant colony optimization (ACO) Solve discrete optimization problems (Dorigo, 1992) Particle swarm optimization (PSO) A optimization for representing sociocognition of human and artificial agents tool (Kennedy and Eberhart,1995) 當然在人工智慧的領域相當廣泛，所以當初我們研究就直接鎖定在群體智慧上面，在自然界中我們本來就熟知很多動物都是群體生活，群體移動的， 1.譬如說雁群的換季遷移，就是以V字型的方式飛行，只要在V字型裡面有雁子死亡受傷，就會修正整個隊伍，或是有人受傷或是脫隊的話就會產生另一各雁， 2.像是蜜蜂的話，奧國養蜂學家費瑞希(Karl von Frisch 1886~1982)，提出蜜蜂搖擺舞，這個搖擺舞在1973年也得到諾貝爾獎，就是蜜蜂每分鐘在空中用尾部畫出八個類似八的圖形，這個搖擺舞的作用就是要告訴其他蜜蜂，所發現花蜜來源的距離和方位的編碼信息 3.那像是螞蟻的費落蒙學說應該就是大家比較常聽說的，就是螞蟻在移動的時候留費落蒙，所以越常走的地方會越多這種化學物質，因此藉由這種物質螞蟻會漸漸移往最短路俓，那dorigo已經在92年把螞蟻演算法用在解決TSP旅行推銷員求解的問題上面，我覺的這是一各很棒的典範，就是群體 智慧演算法，一隻小小螞蟻，她的本能反應就能拿來解決我們本來視為NP-complete的問題，所以當初我在讀這些paper的時候真的是有被感動到.. 4. 第四個這個PSO 粒子族群最佳化，其實說穿了就是小鳥演算法的運用，也有人說是魚的演算法，因為他們的行為都很類似，都使整個團體朝同一方向、目標而去 ，所以這個很明顯也是一各最佳化的演算法 2018/11/22 OPlab, IM, NTU

7 II. Literature review 2/3 Related spider papers
Influence of the genes on the web (Kirnk, 1996) Wind, Temperature, and Humidity (Vollrath, 1997) Prey size (Vollrath, 1998) The pattern of the capture spiral(李蔡彥and林翰儂, 2004) 2018/11/22 OPlab, IM, NTU

8 II. Literature review 3/3 Related spider artificial intelligence
The pattern of the capture spiral (李蔡彥and林翰儂, 2004) Figure.2 Capture spiral pattern Figure.3 Different capture spiral pattern 2018/11/22 OPlab, IM, NTU

9 Outline Introduction Literature review
2018/11/22 Outline Introduction Abstract Motivation Literature review Artificial Intelligence Related spider papers Spider web-building algorithm design Visualization tool prototype of the model Internal factors External factors Conclusion and future work 在第三部份 我們會介紹本研究所設計的蜘蛛結網演算法 2018/11/22 OPlab, IM, NTU

10 III. Spider web-building algorithm model design 1/8
2018/11/22 III. Spider web-building algorithm model design 1/8 根據一些生物文獻所知，我們先設計出蜘蛛結網的演算法，然後整理歸納出目前文獻中所有跟蜘蛛結網有關的因素，如圖所示分為內在及外在因素，並且在根據生物學實驗結果來修正model，接下來我們會詳細介紹整個model Figure.4 The factor-analysis tree of web-building. 2018/11/22 OPlab, IM, NTU

11 III. Spider web-building algorithm model design 2/8
2018/11/22 III. Spider web-building algorithm model design 2/8 Figure.5 The rule-analysis tree of web-building. Auxiliary spiral (AS) Capture spiral (CS) 1.在圖二中，可以看出蜘蛛結網的步驟，首先先來介紹一下蜘蛛網的各部位名稱， 2.蜘蛛在結網可以分兩大步驟，蜘蛛會先將radii固定在周圍的環境上，然後在產生蜘蛛網外匡，接下來會產生第一種沒有黏性的絲線稱作AS，在順時針向外隻出，這種絲線 是當作鷹架來輔助產生CS，，然後沿著AS反方線產生CS，最後在蜘蛛網還有空白的地方作CS reverse ，這是一種巧妙的行為，因為這種遇到外匡就反方向之回去的方式，可以讓整個蜘蛛網結的更完整 Figure.6 The real spider web. Influence of the genes on the web (Kirnk, 1996) 2018/11/22 OPlab, IM, NTU

12 III. Spider web-building algorithm model design 3/8
Radii Gene 1：Control the number of radii (　 ) and base angle (　). Gene 2：Control the difference of the angle (　) from the north to the first radii. Gene 3：Control the difference of the angle (　) between the other radii. Figure.7 The relation between radii and gene 2018/11/22 OPlab, IM, NTU

13 III. Spider web-building algorithm model design 4/8
Frame The distance (HF) between hub and frame is the length of the radii (RL) subtract the length which is control by Gene 4 (　). HF = RL - Because of the effects of the gravity, the distance between hub and downward frame is longer than the others distance. RL HF Figure.8 The relation between frame and gene 2018/11/22 OPlab, IM, NTU

14 III. Spider web-building algorithm model design 5/8
2018/11/22 III. Spider web-building algorithm model design 5/8 AS The effects of the interactions between Gene 5 (　) and Gene 6 (　　) control the intersection points of the AS and radii, resulting in a clockwise spiral (AS). Figure.9 The relation between AS and gene 2018/11/22 OPlab, IM, NTU

15 III. Spider web-building algorithm model design 6/8
CS Along the AS, a spider creates an anticlockwise spiral (CS). The intersection points of the CS and radii are effected by Gene 7 (　　 ). Figure.10 The relation between CS and gene 2018/11/22 OPlab, IM, NTU

16 III. Spider web-building algorithm model design 7/8
CS reverse Using reverse to fill the remaining space of web, which is uncovered with CS. Figure.11 The relation between radii and gene 2018/11/22 OPlab, IM, NTU

17 III. Spider web-building algorithm model design 8/8
2018/11/22 III. Spider web-building algorithm model design 8/8 Experiments 圖四就是我們利用視覺畫的方式來呈獻我們設計的model，由左至右，由上至下，任何人即使是非生物學家都可以看出蜘蛛結網的詳細過程， Figure.12 Sequential behavior of spider web-building. 2018/11/22 OPlab, IM, NTU

18 Outline Introduction Literature review
2018/11/22 Outline Introduction Abstract Motivation Literature review Artificial Intelligence Related spider papers Spider web-building algorithm design Visualization tool prototype of the model Internal factors External factors Conclusion and future work 皆下來我們利用在分別考慮內外在因素， 修正原先蜘蛛結網的演算法，再以真實的生物實驗來檢驗正確性 2018/11/22 OPlab, IM, NTU

19 IV. Visualization tool prototype of the model 1/23
2018/11/22 IV. Visualization tool prototype of the model 1/23 Internal factors Explanation of the rules Experiments Model simulation Verification External factors 2018/11/22 OPlab, IM, NTU

20 IV. Spider web-building algorithm model design 2/12
2018/11/22 IV. Spider web-building algorithm model design 2/12 Internal factors 在內在因素部分，主要是由於蜘蛛本身個體差異的影響，kirink在96年的paper將他分為四個因素 基因 體重 體型大小跟腺體儲存量 Figure.6 The internal factor-analysis tree of web-building 2018/11/22 OPlab, IM, NTU

21 IV. Visualization tool prototype of the model 3/23
2018/11/22 IV. Visualization tool prototype of the model 3/23 Internal factors Body size (χ) Larger spiders would build larger webs Weight (ψ) Heavier spiders with the same size of their body would build larger webs Gland silk (ω) Larger gland silk with the same size of their body build larger webs χ, ψ, ω interaction 由於時間的關係，在內在因素中我們以蜘蛛的體型為例子，對於其他因素有興趣的，歡迎等一下私底下討論，實際上就算是同卵雙胞胎，也可能因為後天的條件而造成身體大小不同，因此較大的蜘蛛會有較大的蜘蛛網，現在我們看一下我們實際上模擬的結果 2018/11/22 OPlab, IM, NTU

22 IV. Visualization tool prototype of the model 3/23
Body size (χ) experiments Model simulation Verification Figure.13(b) Maximize χ, minimize ψ, ω Figure.13(a) minimize χ, ψ, ω 2018/11/22 OPlab, IM, NTU

23 IV. Visualization tool prototype of the model 4/23
Weight (ψ) experiments Model simulation Verification Figure.14(a) minimize χ, ψ, ω Figure.14(b) Maximize ψ, minimize χ, ω 2018/11/22 OPlab, IM, NTU

24 IV. Visualization tool prototype of the model 5/23
Gland silk (ω) experiments Model simulation Verification Figure.15(a) minimize χ, ψ, ω Figure.15(b) Maximize ω, minimize χ, ψ 2018/11/22 OPlab, IM, NTU

25 IV . Visualization tool prototype of the model 6/23
χ, ψ, ω interaction experiments experiments Model simulation Verification Figure.16(a) minimize χ, ψ, ω Figure.16(b) Maximize ω, χ, ψ 2018/11/22 OPlab, IM, NTU

26 IV. Visualization tool prototype of the model 1/23
2018/11/22 IV. Visualization tool prototype of the model 1/23 Internal factors Explanation of the rules Experiments Model simulation Verification External factors 再介紹完內在因素後，繼續接著討論外在因素的model 2018/11/22 OPlab, IM, NTU

27 IV. Visualization tool prototype of the model 7/23
2018/11/22 IV. Visualization tool prototype of the model 7/23 External factors Climate Surrounding environments Prey size 外在因素對蜘蛛網的影響主要是在蜘蛛網的網間距離上，所謂網間距離，簡單的說就是蜘蛛絲一條一條的縫隙之間的距離，根據生物觀察的結果影響的可以分為 氣候 周圍環境 獵物大小 ， Figure.17 The external factor analysis tree of web-building 2018/11/22 OPlab, IM, NTU

28 IV. Visualization tool prototype of the model 8/23
2018/11/22 IV. Visualization tool prototype of the model 8/23 Climate Wind Affect mesh Affect the length and the number of radius Temperature Affect the frequency of CS reverse Humidity Affect the viscosity of CS 在氣候中我們以風力為例，以一般常理推斷，我們可以想像出蜘蛛網如果受風力吹拂 的時候，要是蜘蛛網的空隙大一點，風在吹的時候，風就會從細縫穿過，蜘蛛網也比較不容易受損，因此 蜘蛛網就有這個特性，當風力越大的時候，蜘蛛網的網間距離會上升。 2018/11/22 OPlab, IM, NTU

29 IV. Visualization tool prototype of the model 9/23
2018/11/22 IV. Visualization tool prototype of the model 9/23 Wind( ) experiments Model simulation Adjusting the control value of Gene to create new mesh. Figure.18 Wind influence in mesh 那我們這個model的設計主要是以兩個概念為基礎， 第一：根據文獻所知，由基因演算法、螞蟻演算法 、小鳥演算法 及許多生物演算法中，歸納得知生物體受外界刺激時，生物體反應是一種指數型的曲線，舉例來說，人類對溫度的感覺，在28-29時，是不會察覺溫度有所改變，可是要是溫度是38-39，可能就會突然覺得熱的受不了，這種反應就是指數型曲線； 第二：設計出來的model要符合Vollrath在實驗室環境控制下所得的真實數據 圖12就可以看出蜘蛛網網間距離在風力4-5改變的時候有明顯的改變 皆下來我們看一下實驗結果跟真實數據相比的情形 2018/11/22 OPlab, IM, NTU

30 IV. Visualization tool prototype of the model 10/23
2018/11/22 IV. Visualization tool prototype of the model 10/23 Verification-wind 在這裡的實驗，我們是學VOLRRAH一樣，當所有條件一樣的情況下，只有改變風力時所造成的影響， 跟真實生物實驗的數據相比較，是同樣的反應 Figure.19(a) Wind effect mesh Figure.19(b) Wind effect mesh 　：0m/s ：25℃ ：45% 　 ：1m/s ：25 ℃ 　 ：45% Bias:16.33% Bias:17.33% 2018/11/22 OPlab, IM, NTU

31 IV. Visualization tool prototype of the model 11/23
Temperature( ) experiments Model simulation Adjusting the control value of Gene to create new mesh. Figure.20 Temperature influence in mesh 2018/11/22 OPlab, IM, NTU

32 IV. Visualization tool prototype of the model 12/23
Verification-temperature Figure.21(a) Temperature effect mesh Figure.21(b) Temperature effect mesh 　：24 ℃ ：0m/s ：55% 　 ：12 ℃ ：0m/s 　 ：55% Bias:0.60% Bias:1.67% 2018/11/22 OPlab, IM, NTU

33 IV. Visualization tool prototype of the model 13/23
Humidity( ) experiments Model simulation Adjusting the control value of Gene to create new mesh. Figure.22 Humidity influence in mesh 2018/11/22 OPlab, IM, NTU

34 IV. Visualization tool prototype of the model 14/23
Verification-humidity Figure.23(a) Humidity effect mesh Figure.23(b) Humidity effect mesh ：20% ：0m/s ：24 ℃ 　 ：70% ：0m/s ：24 ℃ Bias:0.16% Bias:0.87% 2018/11/22 OPlab, IM, NTU

35 IV. Visualization tool prototype of the model 15/23
2018/11/22 IV. Visualization tool prototype of the model 15/23 Surrounding environments To affect the area of the web The goal of web-building is to maximize 在周圍環境中，蜘蛛每次結網都會考慮如何能夠利用負周圍環境的方式，讓自己的蜘蛛網面積最大，以捕獲最多的獵物，那看一樣我們實驗的模擬情形會比較清楚環境對蜘蛛的影響 2018/11/22 OPlab, IM, NTU

36 IV. Visualization tool prototype of the model 16/23
2018/11/22 IV. Visualization tool prototype of the model 16/23 Surrounding environments experiments Model simulation Verification 比較一下左右兩圖，可以輕易看出，在左邊這個圖蜘蛛景物相對距離較近的時候，蜘蛛網會比較小 Figure.24(a) Available space relatively small Figure.24(a) Available space relatively big 2018/11/22 OPlab, IM, NTU

37 IV. Visualization tool prototype of the model 17/23
2018/11/22 IV. Visualization tool prototype of the model 17/23 Prey size Affect mesh Applying the past experiences for catching difference sizes of prey to adjust the mesh of the next web-building 這邊是獵物大小對蜘蛛網的影響，因為蜘蛛結網就是要抓獵物，所以蜘蛛網的距離一定會隨著獵物大小而有所改變 2018/11/22 OPlab, IM, NTU

38 IV. Visualization tool prototype of the model 18/23
2018/11/22 IV. Visualization tool prototype of the model 18/23 Prey size experiments Model simulation The major concept is that using animals learning to simulate the real world Verification 而我們在設計這個model的時候，考慮到所有生物都有學習本能，當蜘蛛發現今天的網間距離太大而抓不到列霧的時候，他在明天的網間距離會比較小，而學習的特性最重要的精髓就是有遺忘的情況，前天跟昨天的經驗相比，當然是昨天的經驗影響會比較大，而我們所設計的model具有剛剛強調的這幾個特性，那現在看一下實驗模擬的情形 2018/11/22 OPlab, IM, NTU

39 IV. Visualization tool prototype of the model 19/23
Verification Figure.25(a) The first day Figure.25(b) The second day 2018/11/22 OPlab, IM, NTU

40 IV. Visualization tool prototype of the model 20/23
Verification Figure.25(c) The third day Figure.25(d) The fourth day 2018/11/22 OPlab, IM, NTU

41 IV. Visualization tool prototype of the model 21/23
2018/11/22 IV. Visualization tool prototype of the model 21/23 Summary 最後我們整合一下以上幾個公式，而每個因素有不同強度的影響，這個model就是代表外在因素蜘蛛結網的影響 2018/11/22 OPlab, IM, NTU

42 Outline Introduction Literature review
2018/11/22 Outline Introduction Abstract Motivation Literature review Artificial Intelligence Related spider papers Spider web-building algorithm design Visualization tool prototype of the model Internal factors External factors Conclusion and future work 在簡介完我們的研究之後，現在介紹一下在人工智慧中與生物相關的演算法 以及 生物學中與蜘蛛相關的研究 2018/11/22 OPlab, IM, NTU

43 V. Conclusion and future work 1/2
2018/11/22 V. Conclusion and future work 1/2 Success in simulation the sequential behavior of spider web-building The proposed model was verified by comparing with numerical experiment of biologists Unobserved behavior of spiders could be successfully predicted 1.本研究現在已經可以以視覺畫的方式模擬蜘蛛結網的情形， 2.而且每個model都跟經過真實的生物實驗驗證 3.並且可以預測一些未知的情況，因為目前的實驗都單純考慮一各因素，那利用我們的model可以預測多因素下的情況，要是預測的結果真 實際結果有誤差，我們還可以利用改變各因素權重的方式，來調整model 2018/11/22 OPlab, IM, NTU

44 V. Conclusion and future work 2/2
2018/11/22 V. Conclusion and future work 2/2 Long term learning Simulating the behavior of spider to repair the web Designing social spider web-building model Applying spider web-building algorithms to optimization problems 最後，在設計完這個演算法之後，其實從一些生物學研究上發現，蜘蛛網是很容易受損，所以面對受損 蜘蛛會有補網的情形，不僅如此，不同蜘蛛間也是會有一些社會行為，因次我們也希望未來可以朝這個方向研究， 最後在設計完完整的演算法之後，我們也希望這個演算法能夠向螞蟻演算法一樣運用在生活中解決生活問題。 2018/11/22 OPlab, IM, NTU

45 Acknowledgements We thank our adviser PhD Peng-Yeng Yin.
We thank NSC to provide our budget. Project name:模擬蜘蛛結網之演算法設計及視覺化工具開發 Project number: C E Adviser :尹邦嚴 Name:陳怡孜 2018/11/22 OPlab, IM, NTU

46 Q＆A ? 2018/11/22 OPlab, IM, NTU

47 Thank you !! 2018/11/22 OPlab, IM, NTU