上一次我們使用遺傳算法求解了一個(gè)較為復(fù)雜的多元非線性函數(shù)的極值問(wèn)題，也基本了解了遺傳算法的實(shí)現(xiàn)基本步驟。這一次，我再以經(jīng)典的TSP問(wèn)題為例，更加深入地說(shuō)明遺傳算法中選擇、交叉、變異等核心步驟的實(shí)現(xiàn)。而且這一次解決的是離散型問(wèn)題，上一次解決的是連續(xù)型問(wèn)題，剛好形成對(duì)照。
首先介紹一下TSP問(wèn)題。TSP(traveling salesman problem,旅行商問(wèn)題)是典型的NP完全問(wèn)題，即其最壞情況下的時(shí)間復(fù)雜度隨著問(wèn)題規(guī)模的增大按指數(shù)方式增長(zhǎng)，到目前為止還沒(méi)有找到一個(gè)多項(xiàng)式時(shí)間的有效算法。TSP問(wèn)題可以描述為：已知n個(gè)城市之間的相互距離，某一旅行商從某一個(gè)城市出發(fā)，訪問(wèn)每個(gè)城市一次且僅一次，最后回到出發(fā)的城市，如何安排才能使其所走的路線最短。換言之，就是尋找一條遍歷n個(gè)城市的路徑，或者說(shuō)搜索自然子集X={1,2,...,n}(X的元素表示對(duì)n個(gè)城市的編號(hào))的一個(gè)排列P(X)={V1,V2,....,Vn},使得Td=∑d(Vi,Vi+1)+d(Vn,V1)取最小值，其中,d(Vi,Vi+1)表示城市Vi到Vi+1的距離。TSP問(wèn)題不僅僅是旅行商問(wèn)題，其他許多NP完全問(wèn)題也可以歸結(jié)為T(mén)SP問(wèn)題，如郵路問(wèn)題，裝配線上的螺母問(wèn)題和產(chǎn)品的生產(chǎn)安排問(wèn)題等等，也使得TSP問(wèn)題的求解具有更加廣泛的實(shí)際意義。
再來(lái)說(shuō)針對(duì)TSP問(wèn)題使用遺傳算法的步驟。
?。?）編碼問(wèn)題：由于這是一個(gè)離散型的問(wèn)題，我們采用整數(shù)編碼的方式，用1~n來(lái)表示n個(gè)城市，1~n的任意一個(gè)排列就構(gòu)成了問(wèn)題的一個(gè)解。可以知道，對(duì)于n個(gè)城市的TSP問(wèn)題，一共有n!種不同的路線。
(2)種群初始化：對(duì)于N個(gè)個(gè)體的種群，隨機(jī)給出N個(gè)問(wèn)題的解（相當(dāng)于是染色體）作為初始種群。這里具體采用的方法是：1,2，...,n作為第一個(gè)個(gè)體，然后2,3，..n分別與1交換位置得到n-1個(gè)解，從2開(kāi)始，3,4,...,n分別與2交換位置得到n-2個(gè)解，依次類推。（如果這樣還不夠初始種群的數(shù)量，可以再考慮n,n-1,...,1這個(gè)序列，然后再按照相同的方法生成，等等）
(3)適應(yīng)度函數(shù)：設(shè)一個(gè)解遍歷初始行走的總距離為D，則適應(yīng)度f(wàn)itness=1/D.即總距離越高，適應(yīng)度越低，總距離越低（解越好），適應(yīng)度越高。
(4) 選擇操作：個(gè)體被選中的概率與適應(yīng)度成正比，適應(yīng)度越高，個(gè)體被選中的概率越大。這里仍然采用輪盤(pán)賭法。
