anfa 的部落格

[Pre-Class] DTD

"

什麼是文件類型定義(DTD)?
http://taiwan.cnet.com/builder/programming/story/0,2000027293,20008001-6,00.htm

文件類型定義(Document Type Definition, DTD)是一組標籤的語法規範。在 DTD 裡面說明了文件中有哪些標籤可用,它們的使用順序,哪些標籤可以被包含在哪些標籤裡面,哪些標籤可以有哪些屬性等等這一類的資訊與規則。DTD 原本是用來與 SGML 搭配使用的,它可以是 XML 文件本身的一部分,不過通常都是單獨成為另一份,或者甚至是一系列的文件。

W3C 建議網頁使用的 DTD 清單
http://www.w3.org/QA/2002/04/valid-dtd-list.html

瀏覽器對各種 DTD 的處理方式清單
http://gutfeldt.ch/matthias/articles/doctypeswitch/table.html

不同瀏覽器公司所提供的 DTD 支援說明
http://msdn.microsoft.com/library/default.asp?url=/workshop/author/dhtml/reference/objects/doctype.asp
http://msdn2.microsoft.com/en-us/library/bb250395.aspx#cssenhancements_topic2
http://www.opera.com/docs/specs/doctype/
http://www.mozilla.org/docs/web-developer/quirks/doctypes.html

延伸: 容錯與 quirk 模式
http://wiki.moztw.org/index.php/Error_tolerance_and_quirk_mode_(zhTW)

J2EE 的 DTD 清單
http://java.sun.com/dtd/

滿簡單的 DTD 基本使用教程
http://www.zvon.org/xxl/DTDTutorial/General/book.html

"

KML 簡介

"

Term project成員

資工三甲 493511149 張吟瑋

資工三甲 493511242 粘家盛

資工三甲 493511632 岑志豪

Term project主題

KML

KML 全稱為 Keyhole Markup Language, 是一種 XML-based 的 地理位置信息 描述語言, 採用 XML Schema 作檢查.

以前為 Keyhole, Inc 所有. 而後來 Keyhole 於 2004 被 Google 收購, 並把軟體名稱改為 Google Earth.

KML 最新版本為 2.1 

作為 地理位置信息 描述語言, KML 提供以下的 Ojbect 供我們使用:

透過這些 Object,  我們可以在 Google Earth 上放入 地標, 文字, 圖片, 多邊形, 模型等東西.

而除了純文字形式的 KML 檔外, 我們還可以使用經過 ZIP 壓縮的 KMZ 檔來減低佔用空間.

其中 KMZ 檔中有2個固定的檔案名稱:

doc.xml - Google Earth 最先讀取的 KML 檔

textures.txt - 把 COLLADA 3D Object 所需要的圖像位置 影射 到 KMZ 檔內

而 KML, KMZ 檔使用的 MIME Type 為:

application/vnd.google-earth.kml+xml
application/vnd.google-earth.kmz

由 Google Earth 4.0 開始提供直接引用外部 .dae 物件內加入模型. 免除了在 KML 內加入大量 Polygons 才可生成模型的麻煩, 也提高了 KML 的可讀性.

"

Term Project - 基因演算法(2)

"

資工三甲 岑志豪 493511632

題目:基因演算法

[@more@]

解釋
在解釋為什麼 GA 能夠為什麼能達到最佳化之前,我們先說明一些模式(schema)。在基因序列中,我們可以用 * 來表示「任何值」或「不重要值」,假若我們有一組基因序列為 1011*001*0,則符合這種表達式的基因序列有:
1011000100                    1011100100
1011000110                    1011100110
而基因序列 101 也可以用以下的表達式表示:101                                  *01
10*                                  *0*
1*1                                  **1
1**                                  *** 

而染色體長度為 2 時,我們可以用下面的schema 來表示:

00                            10                            *1

01                            *0                            1*

0*                            11                            **

注意的是,若一個schema裡包含 n *,則他所能表達的染色體數量有 2n個。而一個 r bits 的染色體可以用 2rschema來表示。而染色體長度為 m時,能夠用 3mschema來表示。

一個 schema的定義長度是定義為一個schema中第一個被定義的 bit 與最後一個被定義的bit 之距離。下面的schema我們都把他的定義長度看為4

**10111*

1*0*1**

11111

1***1

*******10**1********

一個 schema order 是定義為已被定義的 bit 數目總和(或者是說並不是 * bit)。下面的 schema 我們都把他的 order 判定為 4

**10*11*

1*0*1**1

1111

1**1**1**1

1*****10*1****

 我們把 定義長度記為 dL(S)schema 長度記為 L(S)order記為 O(S) 接下來我們再看看執行步驟中有哪些會影響到 schema (i) 繁殖(reproduction)

我們先假定一個群體中有如下十個染色體:

C1 = 01000100101010010001010100101010

C2 = 10100010100100001001010111010101

C3 = 01010101011110101010100101010101

C4 = 11010101010101001101111010100101

C5 = 11010010101010010010100100001010

C6 = 00101001010100101010010101111010

C7 = 00101010100101010010101001010011

C8 = 11111010010101010100101001010101

C9 = 01010101010111101010001010101011

C10 =11010100100101010011110010100001

而我們有如下的 schema

S0 = 11010***************************

而符合以上 schema 的基因有 C4 C5 C10,我們可以記為下式,其中 i 代表世代數。

m(S0, i) = 3

schema 的適應性定義為符合該schema 之染色體適應性平均值。假若我們已知 C4 C5 C10之適應性分別如下:

f(C4, i) = 10

f(C5, i) = 22

f(C10, i) = 40

schema S0 之適應性將會為:

f(S0, i) = (10 + 22 + 40) / 3 = 24

則我們能夠得出下式:

這裡 a(i) 是指在第i世代時染色體適應性之平均值。

而因為 c 可以用 schema S 來表演,因此我們可以把式子改為:

                        (1)

c1 cn 代表在群體中符合 schema S 之染色體適應性。

而按照我們對 f(S, i) 之定義,我們可以有如下的式子:

                             (2)

然後我們透過方程式 (1) (2),能夠得出如下式子:

這樣子的方程式說明了,對比適應性平均值來說,schema 的適應性越高於他,則他出現在下一代的機會就越高。

(ii) 交配、突變

交配和變異都會有可能使得 schema 的存在不再。假若我們選出的交錯點落在定義長度裡的話,則在交配過程中 schema 就會被破壞。如果在交配所產生的新染色體和其母體同樣符合一個 schema的話,則我們稱該 schema 有存活式交配。而 schema 之存活機率我們可以透過下式表示:

其中 Ps(S) 是指該schema之存活機率,dL(S) 指該schema之定義長度,而L(S)則指該 schema 之長度。這裡可以看出,當 schema 之長度越短,其存活之可能性則越大。實際上這表示使用較小基因來表現的特徵較容易由父母傳到下一代。

在上述的方程式裡,我們是假設每對父母都會進行交配。但事實上,常常出現一些染色體進行無性繁殖(克隆)的情況。因此,如果我們以 Pc 來表示其交配之機率的話,上式則可以修改為:

這樣表示,交配機率越低,schema存活之可能性越高。

之前提到,如果交配點落在定義長度裡的話 schema 則會被破壞,但事實上其實必然。以如下的染色體為例:

10111101

01001110

第二個染色體符合 schema **0011**的要求,如果我們以第4位及第5位之間作交錯點交配,則會產生如此的後代:

10111110

01001101

在這一代裡,第二個染色體仍然符合 schema **0011** 的要求。如此,我們可以再把上式修改為:

而在突變裡,我們以 Pm 來表示 染色體發生突變的機率。要只突變的位置不落在定義長度裡,則該schema 就可以存活下來。另外我們以 O(S) 來表示 schema order,則該 schema 之生存機率為:

這表示如果 order 越小,schema 之生存機率越高。

到這裡我們可以把上面提及的式子所合併:

這麼可怕的方程式稱為 schema theorem,由 Holland 所發明。全式的意思是「長度較短、order較低、適應性比平均的高之schema通常會以指數上升出現在下一代中」。

 使用領域

銷售員問題 (Traveling Salesman Problem)

飛行員排班問題 (Airman Scheduling Problems)

排程問題 (Timetabling problems)

戰術調整策略 (Tactical Asset Allocation)

最佳化資料壓縮系統 (Optimization of data compression systems)

分散式系統檔案分配 (File allocation for a distributed system)

 尾聲

其實很多電腦上應用到的演算法,其原理都是在自然規律、人常生活中領悟出來。然而要把他們在電腦上實淺出來,可能並不是一件容易的事。上面所寫的希望能令大家對 GA 有所了解,但途中有解釋不對的地方請別見怪。


參考資料

Genetic Algorithm

http://en.wikipedia.org/wiki/Genetic_algorithms

 

遺傳演算法

http://zh.wikipedia.org/wiki/%E9%81%97%E4%BC%A0%E7%AE%97%E6%B3%95

 

Term Project - 基因演算法(1)

"

資工三甲 岑志豪 493511632

題目:基因演算法

[@more@]

基因演算法
概念

以進化論的角度來說,隨著時間的改變,生物在不同的世代有可能會出現一些差異。這些差異,可能是為了適應環境的改變所引起,也有可能是受到外來的刺激所引致,也可以是在繁殖下一代的過程中出現。這樣子的差異,對生物來說可能是好的,也可能是壞的,「物競天擇、適者生存」,對生物有利的改變令他們存活下來,而對生物有害的改變則令他們逐漸被淘汰。而管理著生物特徵的源頭就是生物體內的基因,生物在繁殖下一代的時候也會把自己的基因加在裡頭。一旦基因發生改變,所生成的下一代就會和前一代不一樣。

假若,我們有能力去控制基因改變,把對我們有利的基因保留下來,對我們有害的基因除去,那就能產生更好的下一代了。

基因演算法正是以這種生物現象為概念所發展出來的一種演算法。

 歷史
在還沒有這個名詞之前,早於1954 Nils Aall Barricelli 已開始使用電腦來進行進化的模擬實驗。他當時是對一個動自機在玩卡牌遊戲過程中的進化作實驗。於1957年,澳洲 定量遺傳學者 Alex Fraser發表了一系列關於 控制在多重地方的生物人工選擇裡可度量到的特徵 實驗。由此開始,在60年代初期,由生物學家所進行的電腦模擬進化實驗變得更為普及。而在 Fraser, Burnell Crosby 所寫的書也裡描述了多種方法。很多前期的論文都被 Fogel 重印了。

雖然 Barricelli 也有用進化模擬實驗作為普通的最佳化方法,但基因演算法變得廣為認知的最佳化方法,仍拜 John Holland 的功勞所賜(70年代初期),其中以他在975年所出的 Adaptation in Natural and Artificial Systems一書最為特出。有此想法是起源於他和他的同僚在密西根大學時對於 宮格自動機(cellular automata) 的研究。然而當時對於 GA 的研究仍然處於非常理論化的階段。直到80年代中期,在伊利諾伊大學召開了第一屆世界遺傳演算法大會。隨著電腦計算能力的發展和實際應用需求的增多,遺傳演算法逐漸進入實際應用階段。1989年,紐約時報作者約翰·馬科夫寫了一篇文章描述第一個商業用途的遺傳演算法--進化者(Evolver)。之後,越來越多種類的遺傳演算法出現並被用於許多領域中,財富雜誌500強企業中大多數都用它進行時間表安排、數據分析、未來趨勢預測、預算、以及解決很多其他組合優化問題。

 過程

過程大概如下:

1.      產生一群隨機的染色體 (此為第一代)

2.      評估每一個染色體之適應性。

3.      選擇出適應性較高之染色體作交配及變異,

生成新的染色體群(下一代)

4.      再進行染色體之適應性。

5.      如達到終止條件得出答案,演算法結束,

否則將再選擇染色體。

通常舊一代種群與新一代種群之間的大小是不會改變的。但有一些情況下種群大小的改變會對我們有幫忙。

每一個染色體大小需要相同才能進行交配。在少數情況下可改變的染色體的大小。

普遍來說,是由每代中選出最恰當的染色體去與其他作交配,而每一對染色體可生成2個後代。然後合成的後代染色體群取代上一代。

另外也可指定某合適的雙親生成相對更多的後代,除此之外還可以指定某一代裡面某部分的染色體存活到下一代。在下面所提及的內容裡面,我們將假設每對雙親生成二個後代並被其取代。

接下來我們說一下在這個過程中要注意的要點。

 要點
(1) 適應性 (Fitness)

基因對環境的適應程度,會影響其存活的可能性。我們以人類主觀來決定其適應性。此外每一代都是由其雙親中突變出來的後代。

在多數的傳統基因演算裡,我們需要一種機制去量度一個能夠被檢測出來的基因的適應性。例如,我們使用GA來以數值大小來排序一組數字,一個合適的衡量適應性方法可能是以執行演算法的過程中計算已落在正確位置的數字數目來檢查。一個更複雜的方法衡量方法是計算每個位置中錯誤數字距離其正確位置有多遠。

Karl Sims 按照生物的能力去安排他們一些簡單的工作(如行走、躍、游泳來飼養,使其進化。Sims 用其表現及一系列的規則來檢查他的生物在他們的環境裡,各主要部份如何互相影響。在這個情況下的適應性評量是基於實體由基因資訊碰到特定要素所呈現的顯型 的延伸。我們可以通過建立適應函數(fitness function)來計算個體在現有環境中的適應程度。一般情況下,適應程度越好,數值將會越高,表示他有較高的機會將其基因傳遞給下一代。我們也可以按情況需要改為適應函數來選出更好的下一代。其函數會配合目標函數(objective function)使用。 
(2) 交配 (Crossover)
此過程需要兩個染色體來進行,我們先隨機選擇一個交配點,然後隨該點把每個染色體分為兩段,再作交錯交換重新組合。下面我們用一個簡單的例子說明,假設我們現在有如下的兩個染色體:
110100110001001
010101000111101
接著我們以第6和第7個基因之間為交配點把染色體分為兩部份:
110100 | 110001001
010101 | 000111101
然後把分段的部份進行交錯重組:
110100 | 110001001                      =>            110100000111101
010101 | 000111101                      =>            010101110001001
這種方式是基於人類繁殖時 DNA 序列相互重組行為。 單點交配是最常使用的方法,但有些時候我們會以兩個或以上的點作為交錯位置。在兩點交錯時,我們會把位於兩點之間的基因序列相互交換,如下面所示:
10 | 0110 | 001                                 =>            10 | 1100 | 001
01 | 1100 | 100                                 =>            01 | 0110 | 110 
還有另一種的交配是均勻交配(uniform crossover),就是沒有按照特定的點作交換,可以說是完全隨機性。 
(3) 突變 (Mutation)
如果光是使用交配這種方式,有可能陷入一定的循環,無法達到更好的目標。因此我們需要引入突變這種機制來減低這樣的可能性。突變是使單一的基因改變,這種行為的發生機率比較低,比如1%0.1%
010101110001001           =>          010101110101001 
(4) 終止要素 (Termination Criteria)通常我們有兩種方法來令執行中的基因演算法終止。一種是限制其產生下一代的次數,另一種是當我們找到一特定的解或在特定數值中找出一個最高的適應等級時。例如如果我們使用 GA 來解決一個數學函數時,我們只要能解出一個正確答應,就可以把 GA 停止了。在道金斯生物型態世界中,並不存在著這樣的終止條件。在執行中強迫他在一個特定的世代中停止是不可行的,也沒一個目的測量適應性包含在裡面,系統檢查不到要在什麼地步才停下來。但兩者有一個重要的區別。在通常情況下,基因演算法是用來解決有一定目標解答的問題,當其找到解答時就可以停下來。另一方面,其是用在一些更為抽像的目的,如產生一些有趣的圖片。在這種情況下,我們必需透過人為判斷來決定他何時才終止。 
(5) 最佳化 (Optimization)

以下我們用 GA 來求出數學函數式最大值來說明。

假設我們試圖求出這函數之最大值:

                f(x) = sin(x)

x 之取值範圍為 1 ~ 15, 其中 x 為弧度制。

每一個染色體以 4 bits 來表示 x 之有效值。

我們使用四個染色體的群體。第一步先隨機產生群體,我們所使用的第一代如下:

c1 = 1001

c2 = 0011

c3 = 1010

c4 = 0101

 要計算每一個染色體的適應性,我們先選定當 f(x) = 1 時適應性為 100,當 f(x) = -1 適應性為 0,當f(x) = 0 時適應性為 50。然後我們定義 f(x)為下:f’(x) = 50( f(x)) + 1 )        = 50( sin(x) + 1 )

染色體之適應度是指染色體適應性佔群體適應性總和的百分比。

下表為計算各值後的數據:

第一代

染色體

基因

數值

f(x)

適應性 f(x)

適應度

c1

1001

9

0.41

70.61

46.29%

螞蟻演算法

"

看到這篇文, 覺得和我之前 post 的粒子群優化 及 將要交的 基因演算法 有點關係.

在演算法中, 有一個領域叫 最佳化演算法, 下面幾個演算法都屬於該領域:

蟻群最佳化 (ACO, Ant colony optimization)

粒子群最佳化 (PSO, Particle swarm optimization) 

隨機擴散搜索 (SDS, Stochastic diffusion search)

基因演算法 (GA, Genetic Algorithms)

維基百科裡也有例出一些比較常見的.


因為12點前 Blog 又爆了所以現在才貼, 別見怪 >_<"

粒子群優化 簡介

"

粒子群優化, 英文 PSO (Particle Swarm Optimization), 是進化計算技術的一種,

源自於對鳥群捕食的行為研究.

[@more@]

這個和我 Term Project 打算報告的 基因演算法 有點類似, 只是他並沒有 交叉 與 變異的過種.

其原理是基於群體的, 根據對環境的適應度將群體中的個體移動到好的區域.

和他類似的群智能算法有蟻群演算法.

其算法的概念就好像鳥群找食物一樣, 食物只有某一區域, 但是他們不知道在哪,

然而他們知道自己離食物還有多遠, 那麼最有效找到食物的方法就是找出離鳥群最近的食物的區域.

 遺傳算法和 PSO 的比較

大多數演化計算技術都是用同樣的過程
1. 種群隨機初始化
2. 對種群內的每一個個體計算適應值(fitness value).適應值與最優解的距離直接有關
3. 種群根據適應值進行複製
4. 如果終止條件滿足的話,就停止,否則轉步驟2

如此看來, PSO 和 GA 有很多相同之處, 但之前也提及過, PSO 並沒有 交叉 和 變異 的過程, 而是根據自己的速度和記憶.

而 PSO 的信息分享機制也不像GA那樣分享出去, 只是單向的由 1Best 發出信息如其他粒子. 全部粒子都以最優的為標準.

參考資料

Wikipedia 記載

http://www.swarmagents.com/complex/models/algorithm.htm

"

Second Life?

"

看到別人第一天玩 Second Life 的心情, 看起來滿有趣的, 並非單純是一個網路遊戲.

可以建3D物件, 可以寫 Scripting, 有點像寫程式 :P

可惜現在忙都透不過氣來, 都沒空玩遊戲...

我可不想我修的課程有 Second Time

有機會的話再試看看. (寒假 ?)

"

WebAPI

"

看到這裡提到一些 WebAPI 的重要性,

其實網上有提供 WebAPI 的服務不少, 問題是我們怎樣去應用在我們的需要上.

有些功能, 我們是不需要的, 但是我們需要的他又不一定有提供.

當然也要看自己的創意到哪裡, 把幾個 Web 服務 MushUp 起來, 另創一番新景象.

"

2006 的 Web 發展回顧

"看到這篇文章, 說一下感想.

「本地化」在網路空間中絕對是至關重要的。比如說,有些本地化的品牌服務表現的更加優於 Yahoo 和 Google 所提供的相同服務。...

這方面確實如此, 以 Blog, 相簿 服務來說, 無名佔了台灣絕大部份的市場, 而 UrMap 的地圖服務就本土使用來說遠比其他國外的好.

P2P 流量的不斷增長

2006 年, BT發展急劇, 也成為了最常用的 P2P 軟體.

網路語音通訊領域正在逐漸地升溫。Skype 現在已經迎來了一大幫新的競爭者,他們都在想著瓜分現存的傳統電話通訊市場。  

Skype 這個 P2P 的 VoIP 也不斷發展, 再加上長途電話費遠比本台電訊公司的價錢便宜, 其一定的吸引力.

線上影片(Online video) 在今年真是非常火紅!現在有一大幫志在趕超 YouTube 網站的崇拜者們。...

我想其中一個功勞要拜 3G手機所賜吧?

RSS 技術依然在一步步地接近主流用戶群體。雖然2006年還不能說是 RSS 技術普及大眾的「破冰之年」,但是... 我們很可能將看到 RSS 技術在2007年的時候呈現出爆炸性增長趨勢。

其實透過 RSS 已經改變了我不成瀏覽資訊的形式, 藉著 Bloglines, 我能隨時看到有提供 RSS 服務的網站更新情況. 把"我去找他"的角色轉變為"他來找我".

"

頁面