---
title: 用GA來解最短路徑問題
tags: Python, AI, GA, Algorithm
description: 期末報告
---

# 用GA來解最短路徑問題

---

## 介紹

大家好，我們是第N組，今天要跟大家介紹使用基因演算法來解決最短路徑問題。

在這之前，要跟大家提一下，我們的最短路徑問題除了最短路徑之外還有其他我們自己設定的條件，請看接下來的簡報。

---


---

跟大家解釋一下，這是一個我們自己設計的最短路徑問題
在最短路徑的基礎下，我們在產生的每個點上加入了一些條件，使問題更加複雜。
比如說
1. 地形：我們設計了山/平地兩種地形，若符合條件將會加強 DNA 的強度。
2. 雨天：根據實際的狀況設計的這個，若下雨的話可能會造成距離增加（繞路），但DNA強度將增強。
3. 優先權：或許有一些地點必須要優先到，針對高優先權的地點加入了對 DNA 強度增強的算法。
解釋完這些之後，大家可能要問我們的 DNA 是如何編碼，請看以下簡報。
---

---

其實就是最簡單的方式，我們採用了走過的城市做編碼。在這部分，我們有遇到一個小問題：交配時，會重複出現已經走過的城市。
比如說:

parent = [1,4,2,3] 
pop = [4,1,2,3]
new_dna = 
[parent[0],pop[1],parent[2], pop[3]] = [1,1,2,3]  (1重複兩次。)

解決這個問題待會會有介紹，其實就是簡單的檢查該元素是否已經存在於新的DNA當中。


跟大家介紹，我們解決問題的方式（其實你們可以自己看註解。），主要是由 keep_city 先 hold 住隨機取出的 parent DNA, 再把 pop 內不在 keep_city 內的元素放到 swap_city 內，在最後一行將兩者連接後輸出，便是我們交配後的DNA，我相信大家可能看不太懂這怎麼運作，可能要問那天寫這些ㄉ我才知道我到底在寫啥ㄌㄏㄏ。

接下來要跟大家介紹有關 DNA 強度，也就是 fitness的事情啦。


一開始算法很簡單，就是把全部的點連起來之後算距離，再透過一些特別的方式擴大差異（距離＊pop_size...等等，避免距離相近，導致 fitness 過於相近）。
後來我們覺得這樣好像太簡單，根據實際的狀況加入了雨天。
雨天的部分為隨機產生，也就是DNA被產生的時候不一定是雨天。
這一頁大家可以參考看看， fitness + 6.6% 其實是測試用數字，現在應該是 + 6.45%，根據多次的測試結果，偶爾可以看見最佳基因是以無下雨的時候最佳（但其實大部分的時候都是有下啦）接下來跟大家介紹優先權的部分。
這個優先權相對就簡單很多，我們產生城市的時候幫每個城市都加上一個優先權編號（0~3），將經過的優先權加起來，最後的 fitness 按比例的增強。注意，每做一輪行動，全部城市的優先權將-1, 我的意思是最大的優先權積分只有可能是(3+2+1)。
這個是 Code 的部分，大家可以參考看看。
（若時間夠） -> 稍微介紹
（若不夠） -> 那我們直接看下一張簡報。

最後是我們最後一個 fitness 增強條件，這個一樣滿簡單的。地形有兩種，就是山與平地，我們在地圖上的點顏色不同來做出區分。我們前面提到的『走得順路』，在這邊指的是地形事件。我們分為
- 平移
- 上山
- 下山

若採取平移，當段距離不變
若採取上山，當段距離將稍微變長
若採取下山，當段距離將稍微變短
大概是像這樣的Code。
我們廢話了那麼久，應該是要 demo 給大家看看結果是如何。我們加入了許多條件，所以產出來的圖或許不會很好看，但無論如何我們還是來 demo 一下ㄅ。

**demo**

最後我們檢討一下我們遇到的問題，有關第一點其實算是暫時解決，在很多的時候我們還是能看到起點被選在邊邊，但偶爾可以解決這樣的事情。

有關無法自訂起點：這其實是當初設計的疏忽。我在寫這支程式的時候沒有想過這點，當時想到這件事想要補進來的時候已經來不及ㄌQQ所以就先就這樣 demo

我們今天的報告跟 demo 就到這，感謝大家聆聽。