大家好，我是毛毛。
今天是Day 10，要來看看處理SFC配置問題有人用過的方法。
今天看的是Integer Linear Programming（ILP）和Heuristic Algorithm~ ヽ(✿ﾟ▽ﾟ)ノ

Integer Linear Programming

Integer Linear Programming（ILP），是最優化問題中的一個領域。現實生活中有很多的問題都是可以用線性規劃來處理，而線性規劃是在不違反限制式的情況下，找最大值或最小值的一個函式。

Integer Linear Programming又可分為：

• Pure Integer Linear Programming
  • 所有決策變數都要求得是整數的整數規劃
• Mixed Integer Linear Programming
  • 部分的決策變數要求得是整數的整數規劃
• Zero-one Integer Linear Programming
  • 所有決策變數都要求得是0或1的整數規劃
• Mixed Zero-one Integer Linear Programming
  • 部分的決策變數要求得是0或1的整數規劃

Integer Linear Programming的優點是可以用來找到問題的最佳解，但是缺點就是當要解決的問題解空間很大時，找到最佳解所花費的時間就會很高，因此才會需要其他的方法，目的是希望能夠在相對短的時間內，找到一個近似最佳解。

Heuristic Algorithm

Heuristic algorithm，中文稱啟發式演算法，是一個基於直觀或經驗構造的演算法，在可接受的花費（指計算時間和空間）下給出待解決組合優化問題每一個例項的一個可行解，該可行解與最優解的偏離程度一般不能被預計。

啟發式演算法中，很多的演算法都是透過觀察大自然中的現象而發展出來的：

• 觀察動物而發展出來的演算法，像是：
  • Particle Swarm Optimization（PSO），粒子群最佳化演算法
  • Ant Colony Optimization（ACO），蟻群演算法
  • Artificial Bee Colony（ABC），人工蜂群演算法
• 觀察植物而發展出來的演算法，像是：
  • Invasive Weed Optimization（IWO），入侵雜草演算法
  • Plant Growth Simulation Algorithm（PGSA），模擬植物生長演算法
• 觀察人類而發展出來的演算法，像是：
  • Harmony Search，和聲搜尋演算法

Genetic Algorithm

而其中一個最經典的就是基因演算法Genetic Algorithm（GA），這個演算法沒有歸在上面，是因為這個演算法是借鑒了進化生物學中的現象來的，所以覺得歸在動物或歸在植物都不太對。

在達爾文的進化論中提到「物競天擇，適者生存」，而這個概念就用在基因演算法中，利用基因的「選擇、複製」、「交配」和「突變」的步驟，來找到近似最佳解，透過突變還能讓最後的解避免是區域最佳解。

結論

透過Integer Linear Programming可以找到一個問題的最佳解，但是如果這個問題的解空間很大，那就很難在短時間內解出來。因此才會有人使用Heuristic Algorithm，希望能夠找到一個近似最佳解，而且所花的時間又可以接受。

今天就到這囉~
大家明天見