上一次我們使用遺傳算法求解了一個較為復(fù)雜的多元非線性函數(shù)的極值問題，也基本了解了遺傳算法的實(shí)現(xiàn)基本步驟。這一次，我再以經(jīng)典的TSP問題為例，更加深入地說明遺傳算法中選擇、交叉、變異等核心步驟的實(shí)現(xiàn)。而且這一次解決的是離散型問題，上一次解決的是連續(xù)型問題，剛好形成對照。
首先介紹一下TSP問題。TSP(traveling salesman problem,旅行商問題)是典型的NP完全問題，即其最壞情況下的時間復(fù)雜度隨著問題規(guī)模的增大按指數(shù)方式增長，到目前為止還沒有找到一個多項(xiàng)式時間的有效算法。TSP問題可以描述為：已知n個城市之間的相互距離，某一旅行商從某一個城市出發(fā)，訪問每個城市一次且僅一次，最后回到出發(fā)的城市，如何安排才能使其所走的路線最短。換言之，就是尋找一條遍歷n個城市的路徑，或者說搜索自然子集X={1,2,...,n}(X的元素表示對n個城市的編號)的一個排列P(X)={V1,V2,....,Vn},使得Td=∑d(Vi,Vi+1)+d(Vn,V1)取最小值，其中,d(Vi,Vi+1)表示城市Vi到Vi+1的距離。TSP問題不僅僅是旅行商問題，其他許多NP完全問題也可以歸結(jié)為TSP問題，如郵路問題，裝配線上的螺母問題和產(chǎn)品的生產(chǎn)安排問題等等，也使得TSP問題的求解具有更加廣泛的實(shí)際意義。
再來說針對TSP問題使用遺傳算法的步驟。
（1）編碼問題：由于這是一個離散型的問題，我們采用整數(shù)編碼的方式，用1~n來表示n個城市，1~n的任意一個排列就構(gòu)成了問題的一個解?？梢灾溃瑢τ趎個城市的TSP問題，一共有n!種不同的路線。
(2)種群初始化：對于N個個體的種群，隨機(jī)給出N個問題的解（相當(dāng)于是染色體）作為初始種群。這里具體采用的方法是：1,2，...,n作為第一個個體，然后2,3，..n分別與1交換位置得到n-1個解，從2開始，3,4,...,n分別與2交換位置得到n-2個解，依次類推。（如果這樣還不夠初始種群的數(shù)量，可以再考慮n,n-1,...,1這個序列，然后再按照相同的方法生成，等等）
(3)適應(yīng)度函數(shù)：設(shè)一個解遍歷初始行走的總距離為D，則適應(yīng)度fitness=1/D.即總距離越高，適應(yīng)度越低，總距離越低（解越好），適應(yīng)度越高。
(4) 選擇操作：個體被選中的概率與適應(yīng)度成正比，適應(yīng)度越高，個體被選中的概率越大。這里仍然采用輪盤賭法。
延伸閱讀
- ssh框架 2016-09-30
- 阿里移動安全 [無線安全]玩轉(zhuǎn)無線電——不安全的藍(lán)牙鎖 2017-07-26
- 消息隊(duì)列NetMQ 原理分析4-Socket、Session、Option和Pipe 2024-03-26
- Selective Search for Object Recognition 論文筆記【圖片目標(biāo)分割】 2017-07-26
- 詞向量-LRWE模型-更好地識別反義詞同義詞 2017-07-26
- 從棧不平衡問題 理解 calling convention 2017-07-26
- php imagemagick 處理 圖片剪切、壓縮、合并、插入文本、背景色透明 2017-07-26
- Swift實(shí)現(xiàn)JSON轉(zhuǎn)Model - HandyJSON使用講解 2017-07-26
- 阿里移動安全 Android端惡意鎖屏勒索應(yīng)用分析 2017-07-26
- 集合結(jié)合數(shù)據(jù)結(jié)構(gòu)來看看(二) 2017-07-26
學(xué)習(xí)是年輕人改變自己的最好方式