遺傳算法

遺傳算法是根據(jù)生物學(xué)的種群進(jìn)化規(guī)律推導(dǎo)出來的隨機(jī)化搜索算法
物競天擇 適者生存
在種群的進(jìn)化過程當(dāng)中，基因型決定表現(xiàn)型，而表現(xiàn)型則取決于當(dāng)前生物能不在很好的在這個(gè)環(huán)境中生活下去，表現(xiàn)型不好的被淘汰(死亡)，表現(xiàn)型好的則生存下來，產(chǎn)生后代，將決定適應(yīng)該環(huán)境的良好的基因遺傳下去。在生物遺傳演化當(dāng)中，有遺傳變異，變異是產(chǎn)生新物種的前提，同理，在算法當(dāng)中，遺傳變異產(chǎn)生新的表現(xiàn)型，而環(huán)境選擇表現(xiàn)型，所以在經(jīng)過無數(shù)次代數(shù)以后，物種的表現(xiàn)型趨于穩(wěn)定，基因型相似，在算法中的表現(xiàn)就是，最后你所找到的最優(yōu)序列或者說種群的數(shù)字編碼趨向于一個(gè)數(shù)（收斂）

圖片解釋：

遺傳算法的圖解

用遺傳算法解決商旅旅行的問題

商旅問題（Travel-Salesman Problem，TSP）：
設(shè)有n個(gè)可以相互直達(dá)的城市，某推銷商準(zhǔn)備從A城處罰，周游一圈以后，回到A城，要求為推銷商規(guī)劃一條最短的旅行線路。使用遺傳算法

輸入：

一個(gè)n*n半角矩陣A_i=j=0，定義兩城市之間距離

A：兩城市之間距離矩陣

以0到n-1表示A0到An-1 n個(gè)城市
現(xiàn)在應(yīng)該是編碼選擇：兩種，二進(jìn)制和數(shù)值類型
此方法選擇以數(shù)組保持先后到城市順序【0，2，1】表示從A出發(fā)然后到A->A0->A2->A1->A
設(shè)置初始種群，就是生成Max個(gè)城市序列：
然后評價(jià)種群中的個(gè)體適應(yīng)度，在本算法當(dāng)中就是距離最短
選擇兩個(gè)最長的將其淘汰掉
選擇距離最短的兩個(gè)序列進(jìn)行交叉和變異，交叉和變異都是有一定的概率
然會將新產(chǎn)生的兩個(gè)個(gè)體加入原來種群，交叉變異之前的依然保留
然后構(gòu)建一個(gè)新的種群，進(jìn)行適應(yīng)度選擇評估，選擇計(jì)算交叉變異
不斷循環(huán)這個(gè)過程，直到找到解空間穩(wěn)定

代碼：

import random
import numpy as np
class geneticTravel():
    def __init__(self):
        self.distance_matix=self.inputDis();#初始化地圖
        self.maxNum=3#表示要走的城市個(gè)數(shù)是maxnum=,則總共有4個(gè)城市
        self.populationNum=int(self.maxNum*(self.maxNum-1)/2)*2#種群數(shù)量
        self.population=self.infoPopulation()#初始化種群
        self.crossPro=0.7#只定義了交叉，暫時(shí)不考慮變異
    #定義快排
    def QuickSort(self,myList,myOtherList, start, end):
        # 判斷l(xiāng)ow是否小于high,如果為false,直接返回
        if start < end:
            i, j = start, end
            base = myList[i]
            base1= myOtherList[i]
            while i < j:
                # 如果列表后邊的數(shù),比基準(zhǔn)數(shù)大或相等,則前移一位直到有比基準(zhǔn)數(shù)小的數(shù)出現(xiàn)
                while (i < j) and (myList[j] >= base):
                    j = j - 1
                # 如找到,則把第j個(gè)元素賦值給第個(gè)元素i,此時(shí)表中i,j個(gè)元素相等
                myList[i] = myList[j]
                myOtherList[i] = myOtherList[j]
                # 同樣的方式比較前半?yún)^(qū)
                while (i < j) and (myList[i] <= base):
                    i = i + 1
                myList[j] = myList[i]
                myOtherList[j] = myOtherList[i]
            # 做完第一輪比較之后,列表被分成了兩個(gè)半?yún)^(qū),并且i=j,需要將這個(gè)數(shù)設(shè)置回base
            myList[i] = base
            myOtherList[i]= base1
            # 遞歸前后半?yún)^(qū)
            self.QuickSort(myList,myOtherList, start, i - 1)
            self.QuickSort(myList,myOtherList, j + 1, end)
        return myList
    #定義距離矩陣,這個(gè)要從txt文件當(dāng)中讀取
    def inputDis(self):
        A = [[1,0,0], [1, 2,0], [1, 2, 3]]
        return A
    #初始化種群數(shù)，一共是maxNum！個(gè)城市，現(xiàn)在產(chǎn)生int（maxNum*(maxNUm-1)/2）*2個(gè)個(gè)體
    def infoPopulation(self):
        #隨機(jī)產(chǎn)生populationNum個(gè)個(gè)人,每個(gè)都是0-maxNum的隨機(jī)序列
        temp=[]
        for i in range(self.populationNum):
            temp.append(list(np.random.permutation(range(self.maxNum))))
        return temp

    def max_list(self,lt):
        temp = 0
        max_str=lt[0]
        temp-0
        for i in lt:
            if lt.count(i) > temp:
                max_str = i
                temp = lt.count(i)/len(lt)
        return max_str,temp

    #判斷種群是否穩(wěn)定
    def judge(self):#還未寫
        max_str,pro=self.max_list(self.population)
        print(pro)
        if pro>0.3:
            return max_str,True
        else:
            return max_str,False

    def coutDistance(self,disList):
        dis=self.distance_matix[disList[0]][0]
        for i in range(len(disList)-1):
            max1=max(disList[i],disList[i+1])
            min1 = min(disList[i],disList[i+1])
            dis+=self.distance_matix[max1][min1]
        dis+=self.distance_matix[disList[len(disList)-1]][0]
        return 0

    #評價(jià)種群當(dāng)中的個(gè)體適應(yīng)度,并排序
    def individualFitness(self):
        #遍歷每一個(gè)解決方案，進(jìn)行排序
        dis=[]
        for i in range(self.populationNum):
            dis.append(self.coutDistance(self.population[i]))
        #現(xiàn)在要做的是根據(jù)距離排序
        self.QuickSort(dis,self.population,0,len(dis)-1)
        #這個(gè)地方應(yīng)該是交叉變異，現(xiàn)在只考慮交叉
    def crossoveVariation(self,list1,list2):
        #交叉的主要隨機(jī)產(chǎn)生連個(gè)不相同的數(shù)字maxNum/2,a,b,將a,換成a+b，將a+b換成a
        a=random.randint(0,(int(self.maxNum/2)))
        b = random.randint(0, int(self.maxNum/2))
        for i in range(self.maxNum):
            if list1[i]==a:
                list1[i]=a+b
            if list1[i]==a+b:
                list1[i]=a
            if list2[i]==a:
                list2[i]=a+b
            if list2[i]==a+b:
                list2[i]=a
            return list1,list2
    def solve(self):
        #當(dāng)種群穩(wěn)定是結(jié)束
        judge=False
        while not judge:
            answer,judge=self.judge()
            #如果種群不穩(wěn)定，進(jìn)行遺傳演變
            self.individualFitness()
            #選擇最前面兩個(gè)進(jìn)行交叉變異，將最后產(chǎn)生的結(jié)果把最后兩個(gè)換掉
            new1,new2=self.crossoveVariation(self.population[0],self.population[1])
            self.population[self.populationNum-1]=new1
            self.population[self.populationNum - 1] = new2
        print(answer)
···
主函數(shù)
if __name__ == '__main__':
    A=geneticTravel()
    print("1111:"+str(A.population))
    A.solve()
    print(1111)
結(jié)果：
E:\Anaconda\python.exe F:/CODE/PYTHON/510466/geneticTravel.py
1111:[[0, 2, 1], [0, 1, 2], [0, 2, 1], [0, 1, 2], [0, 2, 1], [0, 2, 1]]
0.6666666666666666
[0, 2, 1]
1111

Process finished with exit code 0