(六)_計算智慧_N4830B

發佈日期: 作者:

20140920
網路硬碟1號: 課程代號碼 GNCI

2015新增 GNEC

教材:
Ant_Colony_Optimization_Marco_Dorigo_and_Thomas_Stützle
(六)_計算智慧_N4830B

1_artificial_intelligence-20140920

artificial intelligence = AI 人工智能

strategy 戰略層——–>智慧化–> unstructured(非結構化)–> EIS / BI
planning 規劃層———–>智慧化–> unstructured(非結構化)–> 排課 / 排程 / 人力
transaction 交易層(作業層)—>電腦化 / 自動化 –> structured(結構化)–> 倉管 / 採購

 

2_artificial_intelligence-20140920

Wisdom智慧
Intelligence情報
Knowledge知識
Information信息
Data數據

3_artificial_intelligence-20140920 4_artificial_intelligence-20140920

Symbolic Reasoning 符號推理
if  XX  then  YY
語意分析  專家系統

Computational Intelligence 計算智能
Evolutionary Computing 演化計算 (先求有~再求好)
Artificial Neural Networks 人工神經網絡 (類神經)
Fuzzy System 模糊系統

—->
Degree 度
unmanned 無人駕駛

5_artificial_intelligence-20140920 6_artificial_intelligence-20140920

********************************************

20140927

AI: artificial intelligence

1.
Symbolic Reasoning 符號推理
EX: Expert systems. 專家系統
Semantic Networks. 語意網路
–> Inference Engine 推理引擎
–> Rule Base 規則庫
Forward chaining 由因推果
Backward chaining 由果推因

X紅燈 ~~~Y煞車~~~Z油門
深層推理VS淺層推理

Blackboard Case-based. 黑板理論

專家系統是單一系統 = 一個專家
黑板理論是跨群組決策 = 一群專家會診

“醉漢走路” = 股價均線(沒有政府干預) = 隨機走路

2.計算智慧(分三支)
a. Evolutionary Computing. (演化計算) (進化計算)
b. Artificial Neural Networks. (類神經網路) (人工神經網路)
c. Fuzzy System. (模糊系統) (degree.)->條件不同下~同一個命令~產生結果不同!
EX:開車加速
在高速公路上..
當時速50時~聽到建議加速~車主會加到90 (在限速100的條件下)–>增加40
當時速80時~聽到建議加速~車主會加到90 (在限速100的條件下)–>增加10

EX:熱水器 / 空調 / 煮飯..

模糊:
好像~非常
If ___ then ___

類神經:
好像又好像不像
圖案很像 EX: 4 與 9 (手寫會很像)

最佳化–>修改一點會引起連鎖反應–>其他也都要動到
分群分類
預測

工具是中性的～只有合不合適問題
EX為什麼過去的人沒有做訓練烏龜去賽跑!?

20140927_N4830B

20140927_N4830B_2

 

 

C I.
(Solution Tools)		 Problems. Application domains
1 Evolutionary Computing.
–>解決最佳化問題		 Optimization
最佳化
(本學期上課)		 transportation
交通
2 Artificial Neural Networks.
人工神經網絡
–>
適合用在分群~預測		 Clustering
分群
Classification
分類		 production
生產
3 Fuzzy System.
–>右邊三個都可用		 Forecasting
預測
(下學期上課)		 investment
投資
4 (作業研究)
Operations Research
–>解決最佳化問題
5 (統計)Statistics
–>解決分群分類問題

optimal solutions 上帝心中的最佳解 (絕對好)

Best solutions 相對起來最好的解答

quantitative 劑量

constrained 受限–>資源受到限制(有看的見與看不見的)
材料~預算~勞動力多少~都是一種限制~
資源的配置地點要放在那?可以降低反應時間?!
EX:醫院~消防隊(依人口多少去配置)

emergency equipment and personnel 應急設備和人員
EX:軍力覆蓋的到~就不用擔心~
EX:大樓消防設施要能撐到消防隊來~

財務規劃~動物飼料調合..
減肥計畫(卡落里越低越好~但又不能太餓)
生產排程(那個單先上~會影響完工時間)
配送計劃(EX:貨櫃上下順序如何才會比較順比較省時省錢)

mix of products 產品組合 (選什產品來生產~對產能價值會最大)
EX水果盒

線性規劃~可用圖型解法~
可先人工算~後再給電腦算~

model模式:把一個Domain本行的問題~經過數學模式化後~再用左邊的工具來解題~

建模都很困難~需要一點數學天份~
對本行很有經驗~這樣去建模才能知其本行特性~
所以數學家去建立~不見得好~因為不懂本行特性~
解題反而簡單~

目標函式 Objective: 決策者可以決定的東西~
決策變數 Decision Variables
限制式Constraints: (大於~等於~小於) 資源稀有~ 小於等於現有資源
參數Parameters

極大化VS極小化:
極大化: profits..
極小化: cost..

Subject to (手寫要注意)

Backlog本期缺貨~下期再捕 (但是已先收單)

nonnegativity constraints 非負約束 / 非負限制

要先訂義model~然後目標函數~
怎樣的”組合”可以讓目標變最大?!要找出最佳變數組合~能讓目標函式值最大
“組合”在值上又分成兩種:
infeasible solution 不可行的解決方案
feasible solution 可行的解決方案 (合理可行解)

遇到不合理解~要回頭去檢查~因為若是基因演算法的話~可能會不小心就跳到~所以要檢查

建模的過程 Model Formulation 模型公式
verification 驗證解法對不對?!
validation 驗證這過程有沒有意義?!

大學:老師給方向~題目~解答~
碩士:老師給方向~題目~
博士:老師給方向~ (類似產品經理)

事先不知答案的才叫研究~

Real world problems –> Modeling –>Mathe. models –> Solving –> Solutions
–> verification –> Answers –> validation –>Real world problems

Model_Formulation

 

*************************************

20141004

Objective fact 客觀事實
D.V
Constraints. 限制
parameters.(參數)~從ERP去撈出來~

Example 2. (P287) Problem statement:

A firm that assembles computers and computer equipment is about to start production of two new types of microcomputer.
在組裝電腦和電腦設備公司即將開始生產兩種新型微機。

Each type will require assembly time, inspection time, and storage space.
每種類型都需要裝配時間，檢驗時間，以及存儲空間。

The amounts of each of these resources that can be devoted to the production of the microcomputers is limited.
這些資源可以投入生產的微型計算機的數量是有限的。

The manager of firm would like to determine the quantity of each microcomputer to produce in order to maximize the profit generated by sales of these microcomputers.
公司經理想確定每個微型計算機的量產，以最大化銷售這些微型計算機產生的利潤。

…….

找出目標函數(求其大~求其小)
決策變數(選擇:投入或產出)
(Each type will require assembly time, inspection time, and storage space.)
（每種類型都需要裝配時間，檢驗時間，以及存儲空間。）

限制式..
(The amounts of each of these resources that can be devoted to the production of the microcomputers is limited.)
（這些資源可以專門生產微型計算機的數量是有限的。）

The manager of firm would like to determine..
(這要去決定…) (公司的經理想確定..)

生產資料:

per unit Type 1 Type 2
Profit $60 $50
Assembly time 4 hours 10 hours
Inspection time 2 hours 1 hours
Storage space 3 cubic feet 3 cubic feet

資源: 

Resource Amount available
Assembly time 100 hours
Inspection time 22 hours
Storage time 39 hours

然後開始建模…

20141004_Example_2_P287

把符號變成一條線:
可行解區域越小~越好找到解~

Assembly time 是一條線~
Inspection 也是一條線~
Storage 又是另一條線~
三條線交叉可得~(取靠近原點位置的區域)
得到一個五角型區域~在裡面找一個最佳的解(點)
這時目標函式還沒用到~
所以令Z=0 或 Z=60 或 Z=90 去做測試..
(在一個區域中求極大值~從原點開始往上切~最後一個離開的點就是最佳解)

20141004_2_Example_2_P287

20141004_Example_2_P287_2

將右邊式子帶入左邊~這樣式子剛好相等~
管理的意函是: 資源剛好用完最好~

畫個星星代表最佳解~

B.C. = Binding constraint 束縛限制式 (構成最佳解的限制式)
上面式子需要再增加資源才能有新的產出

Non. B. C. = 非束縛限制式 (這個不用再加資源~因為效益不大)

Redundant Constraint (多餘限制式)=在可行解區域外面的(沒有用的)

頂角點

Slack and Surplus 鬆弛和剩餘
解代入限制式後~還有剩下的資源~這叫Slack寬鬆
Slack(unused resources)(還沒用完的資源)
Surplus多餘的 (多生產的東西先放倉庫~有人要就可以買上給~未必是壞事)

兩個決策變數可用圖型解法~慢慢去切出來解~
但後來發現解都會出現在五角型的其中一個點上~
所以另壹個解法叫做”菱角點檢查法“(用逆時針方法去找)~一個個代入去得到值~
代入每個後發現往下走的值後~再退一步回去最高的那個就是解了~
就是逐一檢查~應該要一直增加才叫進步~
當再跳下一個點沒有改善卻反而退步~這樣則上一個點就是最佳解!!

這樣做習題有這兩個方法可以做~

萬一是三個決策變數的話~就變成是一個立方體~
這樣多邊型面積就會變類似鑽石表面~
三個決策變數以上就要改用”單型法”

Using LINDO
Lindo簡介
(它被廣泛運用來幫助使用者更快速、簡單且有效的建立與解決線性、非線性、整數最優化的工具。Lindo 主要用於求解線性規劃和 二次規劃問題；Lingo 除了具有 Lindo 的全部功能外，亦使用於求解非線性規劃問題與線性/非線性方程組等，包含了最優化模型的解釋、建立與編輯問題的完整介面及最快速的內建式解法。應用的領域包含生產線規劃、運籌管理、財務金融、投資分配、資本預算等。)

HW1LP題目.doc ~可先做2~3題建模~ 1~2題最佳解~
其他下星期教(敏感度分析)~才能解下去..

MBA(Master of Business Administration)會比較專注在建模與後段為什麼?
其他部份轉成數學模式後~解題部份會丟給專注的RD去做~

Linear Programming HW (HW1LP題目.doc)

2. Solve these problems using graphical linear programming and then answer the questions that follow. Use simultaneous equations to determine the optimal values of the decision variables.
2，使用圖形化的線性規劃解決這些問題，然後回答後面的問題。利用聯立方程來確定決策變量的最優值。

20141004_HW1LP_2

 

D: X1=3 , X2=4  and  X1=4 , X2=2
E: X1=3 , X2=2  and  X1=6 , X2=1
F: X1=2 , X2=5  and  X1=8 , X2=2

20141004_HW1LP_3

 

(1) What are the optimal values(最優值) of the decision variables(決策變量) and Z?
（1）什麼是決策變量和Z的最優值？

(2) Do any constrains have (nonzero) slack?
If yes, which one(s) and how much slack does each have?
（2）是否有任何限制條件有（非零）鬆弛？
如果是的話，哪個（些），有多少鬆弛並各有？

(3) Do any constrains have(nonzero)surplus?
If yes, which one(s) and how much surplus does each have?
（3）是否有任何限制條件有（非零）盈餘？
如果是的話，哪個（些），有多少盈餘也各有？

(4) Are any constrains redundant?  If yes, which one(s)? Explain briefly.
（4）任何約束冗餘？如果是的話，哪個（些）？簡要解釋。

 

 

 

 

 

**************************************************

20141011

兩條限制式型成的點~就是optimal solution

小於等於的右邊通常都是資源~(圖片1)

Simplex:
A linear programming algorithm that can solve problems having more than two decision variable. Space limitations preclude describing it here.
(這樣不用每一個點都去找)

Sensitivity Analysis (民敢性分析)~ 要試過才知道`~數學式也可以做(參數改變就可)
Slack and Surplus 鬆弛和剩餘–>都是限制式
1.用參數做分析
2.參數有那些:
目標函數的改變(利潤改變)EX三星出錯~這樣HTC可漲價
右邊的數字
限制式前面(若制程改善~生產時間變少~也可加大)
—>對原來的生產(9,4)有沒有影響
生產要備料~要從很早就開始~原物料價格改變~利潤就改變~
銷售端折扣也會影響~制程改善也會影響~(上面因素都會影響)

用平行線移動法~最後離開就是最佳解~
參數改變~造成線的斜率改變~這樣最後離開的點就會改變~
斜率的改變~在一定的角度內~最佳點不會改變~這叫”最佳範圍 ”
(However, not every change in the value of an obj. fct. coefficient will lead to a changed solution, there is a range of values for which the optimal values of the decision variables will not change.)
EX:要橫向連繫~APS(先進排程系統)~接單與生產要合的來(產銷要協調)

Range of optimality
變數最好是一個變~另一個不動~但解是一樣~
參數改變~但最佳解不變~這樣Z值就改變~

參數有三類~若前面系數改變這樣較複雜~

束縛限制~代表不需要再加資源下去~
經濟學:邊際應用~邊際效應~

Shadow Price 影子價格 (應該是從經濟學來的名稱)
定義:一個量~目標函式值Z~
每增加一單位~Z會增加多少~
(Amount by which the value of the objective function would change with a one-unit change in the RHS value of a constraint. )

每一個限制式都有一個相對應的影子價格
(Each constraint has a corresponding shadow price)
優先增加Shadow Price影子價格高的資源

圖3

Sensitivity-20141011

Nonbinding constraints have either slack (<=) or surplus (>=).
There is no profit associated with slack.

For nonbinding constraints shadow price = 0 (ie no impact on the value of obj. fct.
But have impact on the value of slack and surplus).

圖4
Sensitivity-20141011-B

Range of optimality (可行範圍)
Range of feasibility
圖5
Sensitivity-20141011-C

Sensitivity Analysis(4/4)
excel 圖
Sensitivity-20141011-D

No upper limit (怎增加都沒用)
evolution_of_execution_time_for_various_complexity_functions

Sensitivity Analysis(4/4) Using LINDO
LINDO每一個都是正數
(教育版只能有200個決策變數)

工廠排程~都上萬個變數~
SAP內有APS

Lingo / option 要改設定~~/
可呈現出敏感度分析 Range Report

run Lindo時DV前係數用1/3會導致錯誤答案~要改成0.33333才行

~~~~~~~~~~~~~~~~~~~~

功能~分裠分類~預測~

基因演算法: Genetic Algorithms ~~ GA簡介.ppt
已經有數學的方法後~為什麼還要有GA?
因為在某些問題運算上需要大量的時間~無法在短時間完成~
EX:工廠訂單的Sequencing排序問題(那個先~那個後)
上機台的順序不同~這樣完工時間就不同
當問題Problem Size越大~則CPU Time 越大時~就需要用到GA方法去解~
就算沒能找到最佳解~至少還有可用解~

圖:

圖:Table 1

Polynomial time ( cpu time) = 多項式
Non poly~~~(NP-hard)
數學解法可以找到上帝最佳解~
GA可以在很大範圍內的合理時間內找到還不錯的解~
EX未婚同學
換言之~~問題是NP-hard就適合用基因去解問題~
Optimal
Near-Optimal 近似最佳解

交易層~策略層~

HW第三題~把輸出結果貼上去就可以~

下次上課就從GA開始上

************************************************

20141018

上次作業~有些數據要先經過換算~
內容有些英文說明是沒有用的~不要被騙了~

~~~~~~~~~~~~~

NP-hard problems. –>Non-polynominal.

Seguencing排序

n!–>(2.5)n次方

GAs基因演算
EP演化式規化:切割到另一個區域找
(把一個大問題分成左右兩塊~再各跑GA~再分割~再跑GA~選比較好的那邊去繼續跑下去)
(樹的分岔~遇到不好的解~就再回朔)
ESs(evolution strategies)

Applications of Gas (派車問題~工廠布置問題~廠址選址問題~如何選讓物流最低~

Simple GA
by Holland (1975): “Adaptation in Natural and Artificial Systems,”
Univ. of Michigan–>很強的可鍍金實驗室

Adaptation調適性:

GAs are stochastic search (GA用天女散花方式去傻出去找~)~再慢慢往最佳解靠近~
經過幾次以後會找到最佳解~(圖 1)
在合理的時間之內去找到最佳解(上帝知道)~跑程式過程不會知道~
optimal sol.
near-optimal sol.

GAs=Population-based.(是一種母體為基的搜尋方法)
一開始給一組解~這解市隨機的~

解釋專有名詞:

Population:母體(由很多解所形成)
Chromosome:染色體= a solution (等於一個完整的解)
Gene:基因 = solution string中的一個bit
Generation:世代
(在世代中做一些事[natural selection 天擇 and natural genetics 自然遺傳]~
先求有再求好~去往最佳解靠近)
Fitness:適應值=obj. fct value. –> 目標函式值
Offspring:子代(new solution)
Crossover:交配(遺傳方法之一)
Mutation:突變(遺傳方法之一)

圖2

np-hard-problems

GA-population-based

最佳解一定在數學合理趨育內~

Evolution:先求有~再求好(是整個演化過程的一個基本精神)

世代為零的時候:初始解
進到第一個世代~父代:
(N+n) = (父代+子代) 去做天擇

上帝造人後~做了一個人叫父代~父代遺傳產生一個世代(小孩)~
父代與世代(小孩)做天擇~後再產生下一個父代~

Crossover
全域 global search –>早期做的事(較不容易陷入區域最佳解)
區域 local search –> 晚期做的事

中文先看懂~再來看英文~

Let P(t) be parents, C(t) be offspring in the current generation, t
Begin
t = 0;
initialize P(t);
evaluate P(t);
While (not termination condition) do
recombine P(t) to yield C(t);
evaluate C(t);
select P(t+1) from P(t) and C(t);
t = t + 1;
End
End
(See Fig. 1.1)

~~

螞蟻演算法用在離散

底下兩個圖有修正過~是正確的圖!
20141018-solution-space-_N4830B20141018- crossover-_N4830B

 

***************************************************

20141101

Professor: 創造知識
Teacher: 提供知識

Begin
t = 0;
initialize P(t); 初始化
evaluate P(t);
While (not termination condition) do 累積機率分怖(CDF)
recombine P(t) to yield C(t);
evaluate C(t);
select P(t+1) from P(t) and C(t);
t = t + 1;
End
End

第一個世代~才初始化~這樣不知對不對~要多跑幾次才準~
基本慨念還是要用上圖~Fig. 1 The general structure of genetic algorithms~

怎用程式來執行轉輪盤~
eval(V1)=f(-2.687969,5.361653)=19.805119
eval(V2)=f(0.474101,4.170144)=17.370896
eval(V3)=f(10.419457,4.661461)=9.590546最差
eval(V4)=f(6.159951,4.109598)=29.406122最好
eval(V5)=f(-2.301286,4.477282)=15.68091
eval(V6)=f(11.788084,4.477282)=11.900541
eval(V7)=f(9.342067,5.121702)=17.958717
eval(V8)=f(-0.330256,4.694977)=19.763190
eval(V9)=f(11.671267,4.873501)=26.401669
eval(V10)=f(11.446273,4.171908)=10.252480

解越好~越容易活下去~物競天擇~
EX假設解有4個~適應值越大~佔的面積就越大~
對第一個解來說=第一個解佔的面積去除以全部的解(當分母)
上面是第一個想法~圖1

20141101_genetic_solutions

第二個想法:
累積機率分怖(CDF)
一直累加~最後會等於一
圖2
20141101_genetic_CDF

圖3
20141101_genetic_RN_CDF
直軸是0~1的地方是射飛標~
橫軸是看射中那一塊~(有放的CDF區域)
射飛標後取隨機亂數的值…

適應

20141101-GA-selection

每交一個女朋友就要做評估~合理性檢查~

nGenerate a random number r from the range [0, 1]

nIf r ≤ q1, then select the first chromosome v1;otherwise, select the Kth chromosome vk(2≤k≤pop_size) such that qk-1≤r≤ qk

俄羅斯輪盤轉成現實條件來看~所以不會射中正中紅心~一定在0~1之間~
萬一解的數目超過四十~五十以上~這樣跟隨便丟都一樣解果(隨機亂數)
(pizza切太多太細)~

演化計算希望在最短時間內找到最佳解~慢慢往最好的解聚攏~
原來解都不一樣~演化後會慢慢靠攏~
若用泡泡排序法(希特樂)這樣就不會靠龍~
EX有十個解~會慢慢往最佳解聚攏~

區域最佳解有可能會聚在某個山頭~但卻忘了後面還有一個更高的山頭~
這時候就須要有突變的狀況產生~才有可能找到後面的解~

太早收殮可能只會找到區域最佳解~

20141101_crossover_mutation_rate

~~~
交配突變~
單點交配~Crossover
Crossover rate交配率~太高很難收殮~太低則很容易陷入區域最佳解~
Mutation rate突變率(偏區域搜尋~但要看是演化早期還是晚期~但晚期會越來越聚攏)~
上面兩個都要考慮到解的多元化(若多元化不夠就很容易陷入區域最佳解)
所以解的收斂與解的多元這兩個要平衡~若太多則CPU要跑太久~

The probability of crossover is set as pc=0.25
Procedure: Crossover
begin
k←0;
while(k≤10)do
rk←random number from [0,1];
if(rk<0.25)then
select vk as one parent crossover;
end
k←k+1;
end
end

**********************************************************

20141108

By Grefenstette and Baker (1989)
Let P(t) be parents, C(t) be offspring in the current generation, t
Begin
t = 0;
initialize P(t);
evaluate P(t);
While (not termination condition) do
recombine P(t) to yield C(t);
evaluate C(t);
select P(t+1) from P(t) and C(t);
t = t + 1;
End
End
(See Fig. 1.1)

~~~~~~~~~~~~~

Pc controls the expected # of chromosomes to undergo the crossover operations

Pc交配率:
global search (若Pc值比較高是全域找~這樣CPU time 就會增加)
local search
上面兩個要平衡

Larger Pc allows to explore more the solution space, decrease the chances of settling for a false optimum, but increase computation time
到大區域去找~可降低陷入區域最佳解的困境~但會增加計算時間
(任何事都有利有弊~但要看何時用)

Mutation rate, Pm, is the percentage of the total number of genes in the population
Pm controls the rate at which new genes are introduced into the population for tria

If Pm is too low => 太低會怎樣? 背後原因是蛇?~可能會有基因沒發現
many genes are never tried out
If Pm is too high => 太高會怎樣? 背後原因是蛇?~隨機腦動會增加
random perturbation increases
the offspring will start losing their resemblance to the parents
the algorithm will lose ability to learn from the history of the search
演算法會喪失能力

GAs work with a coding of solution set, not the solutions (用解的編馬來演化)
GAs search from a population of solutions, not a single solution (單點來搜尋)
GAs use payoff information (fitness function), not derivatives or other auxiliary knowledge
(透過適應值的導引~若適應不好就會在天擇那關淘汰)
(若無法量測的小確幸則沒法解~工具有很多種~但問題要找對適合工具)
GAs use probabilistic transition rules, not deterministic rules
GAs 好處是不用寫數學~跑程式就好~

EX台電有備載容量~因為供給與能量剛剛好是最好~但要有備載~要有管理層去做操作~
萬一突然跑出很多單~這樣會產不出來~
所以要有業務去緩衝~最後若是非技術性手段~EX加錢就可以先出單~或外包出去~
產與供的平衡

量化的目標函數值~一代代改進~若要用數學~但必須要看的懂數學~
懂本行~然後把想法轉成數學~再轉成程式~然後用電腦去跑~

Solving(大部份是解決這一塊)
Model_Formulation

目前學生大多是做右半邊~

GAs use payoff information (fitness function), not derivatives or other auxiliary knowledge
GAs use probabilistic transition rules, not deterministic rules
隨機性也會帶來一些風險~

Exploitation and Exploration(1/2)
探索與開發
圖1
global_local_search

solution_string

Search methods
Exploiting the best solution(改善現有解)
Exploring the search space(尋找新的解)

Population-based search(要透過親朋好友去幫忙找)

Meta-heuristics (對GA來說~無論是什麼問題都可以解!很像DB中的管理資料庫的DATA)
每個事業的上層還有個總管理處~
巨集啟發式演算法(經驗法則)EX計程車時間點不同要去不同地方載客

phenotype 顯性 -> real sol.
genotype 隱性 -> codel sol.

一星期有七天~但若要用2的3次方去電腦表示~則會有星期八出現(illegal sol 非法解)
但已知星期三不行~則為infeasible sol.不可行解~不合理解~圖2

20141018-solution-space-_N4830B

Feasibility_and_legality
Feasibility_and_legality

拋棄法:產生星期8就一定捨棄~
修補法:再重修~
逞罰法(本來是求極大~若Z值被拉下來~這樣天擇時會比較沒有競爭力)

如果說連限制式都不好~則沒有辦法去玩天擇~
若是求極小的問題就去後面加一個很大的值~

Lingo美國~Cplex法國(但被IBM買走)
教育版只有200個決策變數

~~~~~~~~~~~~~

GA/TSP Problems 離散最佳化
Traveling Salesman Problem

The traveling salesman problem is one of the most widely studied combinatorial optimization problems.

A salesman seeks the shortest tour through n cities.

EX:有個五邊型: 全部互聯=C5取2=總共10條連線
A_salesman_seeks_the_shortest_tour_through_n_cities

最近鄰居法=貪婪法(這方法通常用來產生初始值)~但最後有可能遇到大白鯊~
Evolution_of_execution_times

Permutation Representation

Sequencing 排序

Partial-Mapped Crossover (PMX) 部份對應法 (要注意位置與內容)
有的位置直接貼下去~有的內容要置換~
Partial-Mapped_Crossover_PMX

Order Crossover (OX)
兩個父代產生一個子代
Order_Crossover_OX

Position-Based Crossover
Position-Based_Crossover

generations

~~~~~~~~~~~~~~~

HD1 分享代號 N4830 有畫圖說明簡報檔~
陳柏翰
kb24and@gmail.com

下星期考試用筆試(考簡報內容的基本問題)~主要是考GA觀念
單點搜尋與多點搜尋的差別在那兒?
~然後要報告程式做到那兒?(簡報Demo)

**********************************************

20141115

遺傳演算法採用隨機多點同時搜尋的方式(複製(reproduction)、交配(crossover)、突變(mutation)) ，而非傳統的單點依序搜尋方式，因此可以避免侷限在區域的最佳解 ..而得到問題的最佳解上。

20141115-so-far-best

交配率九宮格:
20141115-parameter-setting

Redundant constraints ? / Binding constraints ?

in Model formulation ~ Verification and validation are different?

in Linear Programming ~ What is “shadow price” ?

What is “NP-hard”? ~ NP?

Mathematical Programming ? /  Genetic algorithms ?

Mathematical Programming and Evolutionary algorithms are Advantages and disadvantages ?

what is Genetic algorithms three key function ?

Crossover and Mutation who are role in Evolution ?

Evolutionary algorithms

GA TSP Cycle Crossover (CX)

*****************************************

20141129

20141129-induction-deduction

Induction歸納(內化) <—> deduction 推導
Induction歸納(內化)也是不斷唸Paper的效果
deduction 推導

完全沒震盪的話~就代表跳不出區域最佳解~
若只有和坤~則就只有區域最佳解~

計量決策
1. 最佳化 OR. GA.
2. Clustering分群 + classification 分類~SVM
3. Forecasting 預測 (US MBA 要上一個學期) 經理人要對數字敏感

Clustering分群會先上Cluster Analysis 集群分析.
多變量分析~
Particle swarm optimization粒子演算法(如何能做快速分群)
綠色代表傳統數學

Clustering分群: 無中生有~目的要產生Classification scheme 分類架構
classification 分類: 有中生有~有=(樣版~模型)
先分群後分類!(商業上也是如此)換言之因才施教~先分群吃到虧後分類!
當沒有標準的時候就要去分出來~這過程叫分群~
分類是已經有標準~這時候要分類~就可以去歸類~

Clustering分群:被歸納在unsupervised learning 非監督式學習(學習策略)
classification 分類: supervised learning classification 分類:

SCI paper 不適合用在在職班身上~

Cluster Analysis
1. Applied Multivariate Statistical Analysis, Johnson & Wichern, PH, 1998
2. 多變量分析，陳順宇，華泰書局

Clustering分群Outlines:底下又分兩類
1. K組數事先知道
2. K組數事先不知道
階層式分群法
非階層式分群法

高維度資料投引到2維面上去看出差異~這是用很久的方法

Similarity measures :
Grouping a complex data set requires a measure of similarity.
Important considerations include the nature of the variables (discrete, continuous, binary), scales of measurement (nominal, ordinal, interval, ratio), and subject matter knowledge.
要先看資料間的相似度~計算可能不一樣~當初測量也可能不一樣~

Distances (1/4) 歐基理得變數
無論分群或分類大概都會需要底下這幾個東西:
資料收集~整理~分析~呈現

資料收集 整理 分析 呈現
FeatureSelection特徵選取避免全部特徵都抓下來~這樣會稀釋問題 Coding編碼 SimilarityCoefficient相似度 S.C. matrixDistance matrix
Feature Extraction特徵萃取(事先不知~要自己去找出) Clustering分群方法 ExplanationImplementation解釋意涵(如何呈現)
多變量分析中有PCA

 

20141129Distances

距離越大~代表相異度越大

20141129-distances

20141129-distances-2

 

 

 

 

20141129-variables

 

下圖是contingence table 關聯表

20141129_contingence_table

分群結果會受到上面一連串的影響~

The example of similarity coefficient(1/6)

20141129-example-similarity-coefficient

符合我們分群分類目的~怎設計~

20141129-example-similarity-coefficient-2

相似度

 

20141129-example-similarity-coefficient-3

關聯表

20141129-example-similarity-coefficient-4-individual

*********************************************************

20141206

在RUN的時候~每一次都要先清乾淨~再去RUN~

隨機性中又有導引性~
讓比較大的機率留到下一代~

先天女散花~然後縮到一個小圓圈~
在合理的時間內找到還不錯的解~

收斂性的證明~是現在趨勢~用big O~去算~
還沒跑程式前先用big O去算~划不划算~
但這是資工在用的~

同一個程式跑20次~找出最好~最差~
證明積效是在某個範圍中~
標準差~還有跑20次的CPUtime~

蒙特利梭教學:
i here
i do
i see
i understand
…..
實驗要做獨立實驗(上一次結果不會影響下一次結果)

演化早期振盪~中期漸縮小~後期驅向平穩~
20141206_Evolution_Convergence

Clustering methods

Hierarchical clustering methods:
— Agglomerative:
Single linkage, Complete linkage, Average linkage, Ward’s method
— Divisive: MST
Nonhierarchical clustering methods:
— K-means method

20141206_Clustering_methods

*************************************************************

20150110

螞蟻有兩種~
解離散最佳化~以及分群用~
Sequencing(這功能最好用)
若不是排序問題~就不建議用螞蟻去做

PSO / GA –>
1.已有完整解~先求有再求好~透過世代迴圈逐步改善
2.for contimuous opt. (GA除外)

ANT螞蟻是: (有記憶與漸間的資訊分享)
1.建構解(逐漸把解建構出來)
2.for discrete opt. (所以螞蟻不能解離散問題)

City –> next City
1. select next city.
2. lay pheromone.