源代碼傳送門

文章目錄

Genetic Algorithm
- 導言
- GA算法流程
- - 初始化種群
  - 個體适應度計算
  - 選擇
  - 交叉
  - 變異
- 效果
- 總結
- - 遺傳算法的優化思路
  - GA與SA的比較

Genetic Algorithm

遺傳算法(Genetic Algorithm, GA)是Holland在20世紀60年代末提出的，是受遺傳學中自然選擇和遺傳機制啟發發展起來的一種搜尋算法。它的基本思想是使用模拟生物和人類進化的方法求解複雜的優化問題，因而也稱為模拟進化優化算法。模拟進化優化算法在計算原理上是自适應的，結構上是并行的，而且模仿了人的智能處理特征，因而成為人工智能的一個重要研究領域。

導言

在TSPLIB中選一個大于100個城市數的TSP問題，使用遺傳算法求解TSP問題
實驗環境 Win 10 + Python 3

GA算法流程

使用GA算法解決TSP問題Genetic Algorithm

Code

# 初始化種群
population = initPopulation(cities, numOfCity)

# 演化
curGen = 0 
while curGen < MAXGENS:
    random.shuffle(population)
    # 選擇
    population = select(population, numOfCity)
    # 交叉
    population = crosscover(population, numOfCity)
    # 變異
    population = mutate(population, numOfCity)
    # 引入局部搜尋，加強進化
    population = localSearch(population, numOfCity)

初始化種群

關于種群初始化，其實預設是比較容易的，即随機生成種群即可。但是實驗起來發現随機生成初始種群，其收斂效果很差并且效率很低。是以在初始化種群的時候加入部分貪心生成的個體，加快種群成熟速度，也保證了種群中個體的多樣性。對于貪心個體的生成，直接使用貪心算法生成，每個結點都選擇下一個未被加入路徑的最近結點，但是經過測試，發現加入貪心個體的數目不宜過多，否則将導緻過于早熟。

# Initial population
def initPopulation(cities, numOfCity):
    population = []

    individual = [i for i in range(numOfCity)]
    for _ in range(int(POPSIZE * 2 / 10)):
        random.shuffle(individual)
        population.append(individual[:])    

    for _ in range(int(POPSIZE - len(population))):
        start = random.randint(0, numOfCity-1)
        gIndividual = []
        gIndividual.append(start)
        j = 1
        while j < numOfCity:
            mixDis = float_info.max 
            i, bestId = 0, 0
            while i < numOfCity:
                if (i not in gIndividual) and i != gIndividual[-1] and distance[gIndividual[-1]][i] < mixDis:
                    bestId = i
                    mixDis = distance[gIndividual[-1]][i]
                i += 1
            j = j + 1
            gIndividual.append(bestId)
        population.append(gIndividual[:]) 
    
    random.shuffle(population)
    return population

個體适應度計算

關于适應度評估，其适應度等于該路徑的的倒數，即

1 / totalDistance

# calculate indibidual fitness
def evaluate(individual):
    fitness = 0.0
    for i in range(len(individual) - 1):
        fitness += distance[individual[i]][individual[i+1]]
    # back to starting point
    fitness += distance[individual[len(individual)-1]][individual[0]]
    return fitness

選擇

使用比較通用的輪盤賭，同時選擇其他的選擇政策的效果也是不錯的

# selection operation
def select(population, numOfCity):
    newPopulation = []
    best = float_info.max
    bestId = 0
    fitness = []
    sumOfFitness = 0.0

    # evalute
    for i in range(POPSIZE):
        fit = evaluate(population[i])
        fitness.append(1 / fit)
        sumOfFitness += 1 / fit
        if (best > fit) :
            best = fit
            bestId = i

    # choosing the best individual to directly inherit to the next generation
    newPopulation.append(population[bestId])

    # cumulative probability
    cumPro = []
    for i in range(POPSIZE):
        if i == 0:
            cumPro.append(fitness[i] / sumOfFitness)
        else:
            cumPro.append(fitness[i] / sumOfFitness + cumPro[i-1])       
    
    # roulette selection of offspring
    for i in range(POPSIZE-1):
        pro = random.random()
        for j in range(POPSIZE):
            if cumPro[j] >= pro:
                newPopulation.append(population[j])
                break
    return newPopulation

交叉

關于交叉操作，取随機的兩條染色體i,j，有一定的機率進行交叉。這部分使用次序交叉法(Order Crossover)

# order crossover
subPopulation = []
for i in range(POPSIZE):
    if random.random() <= PXOVER:
        chromosomeFir = random.randint(0, POPSIZE - 1)
        chromosomeSec = random.randint(0, POPSIZE - 1)
        while chromosomeFir == chromosomeSec:
            chromosomeSec = random.randint(0, POPSIZE - 1)
        start = random.randint(0, numOfCity - 2)
        end = random.randint(start + 1, numOfCity - 1)
        newIndividual_i = []
        newIndividual_j = []
        k = 0
        for j in range(numOfCity):
            if j >= start and j < end:
                newIndividual_i.append(population[chromosomeFir][j])
                j = end
            else:
                while k < numOfCity:
                    if population[chromosomeSec][k] not in population[chromosomeFir][start:end]:
                        newIndividual_i.append(population[chromosomeSec][k])
                        k += 1
                        break
                    k += 1
        k = 0      
        for j in range(numOfCity):
            if population[chromosomeSec][j] in population[chromosomeFir][start:end]:
                newIndividual_j.append(population[chromosomeSec][j])
            else:
                if k == start:
                    k = end
                newIndividual_j.append(population[chromosomeFir][k])
                k += 1
        subPopulation.append(newIndividual_i[:])
        subPopulation.append(newIndividual_j[:])

但是對于結果生成的子代，并非都直接将其替換父代加入，而是再将生成的子代與父代進行一定的競争，如果不進行篩選的話，算法的收斂速度太慢

# competition
subPopulation.sort(key = lambda x: evaluate(x))
for i in range(len(subPopulation)):
    for j in range(POPSIZE):
        if evaluate(subPopulation[i]) < evaluate(population[j]):
            population[j] = subPopulation[i]
            break

變異

關于變異，使用兩種變異操作。種群中每個個體的每個結點看作一個基因，第一種變異操作為将兩個基因之間的基因片段反轉，第二種變異操作則隻是将兩個基因的位置對換

# mutation operation
def mutate(population, numOfCity):
    for i in range(len(population)):
        if random.random() <= PMUTATION:
            geneFir = random.randint(1,numOfCity-2)
            geneSec = random.randint(geneFir+1, numOfCity-1)
            population[i][geneFir:geneSec] = population[i][geneSec-1:geneFir-1:-1]
        if random.random() <= PMUTATION:
            geneFir = random.randint(0,numOfCity-1)
            geneSec = random.randint(0, numOfCity-1)
            while geneFir == geneSec:
                geneSec = random.randint(0, numOfCity-1)
            population[i][geneFir], population[i][geneSec] = population[i][geneSec], population[i][geneFir]
    return population

效果

測試 TSP - ch130
Optimal solutions for symmetric TSPs - ch130: 6110
設定
- 種群大小 50
- 遺傳代數 1000
- 交叉機率 0.9
- 變異機率 0.2
運作結果

使用GA算法解決TSP問題Genetic Algorithm
算法本次測試結果為 6637(8.63%) ，參考最佳結果為 6110 。大多數情況下，算法與最優參考解的平均內插補點為 9% ，最優的結果為 6627.0 ，誤差為 8.5% 。

總結

遺傳算法的優化思路

控制參數的選取方面。對于種群規模的設定上，一般情況為 20~200 ，對于問題規模比較大的情況，其含有比較多的模式，我們需要提供足夠的模式采樣容量，這樣也可以防止在成熟期前就收斂。交叉機率的選擇上，一般取 0.6~1.0 ，交叉率越高，群體中新結構的引入越快，已獲得的優良的基因結果的丢失速度也相應升高，而交叉機率太低則可能導緻搜尋效率阻塞。變異機率一般取 0.005~0.2 。
在初始化種群的時候可以加入部分貪心算法生成的個體，這樣可以使得種群的收斂比較好。但是貪心生成的個體的比列不宜過高，否則可能導緻提前收斂，陷入局部最優，此時得到的最優解近似貪心生成的最優個體的解。
合理有效的交叉操作。一個合理有效的交叉操作對于遺傳算法的效率有着比較大的影響。初始本來使用單點交叉、兩點交叉以及多點交叉，但是效果都相當的差，現在使用的是順序交叉，效果可以達到與問題最優解內插補點10%以内，但是效率仍然不是很理想。
引入局部搜尋，增強進化的方向。

GA與SA的比較

所設計的

遺傳算法（GA）

與

模拟退火算法（SA）

相比，

GA

的效率比

SA

低，個人認為主要是目前所設計的交叉操作仍然不夠理想，使得其在後期導緻搜尋阻滞，未能夠得到一個更優解。但是

GA

的改進空間比

SA

應該是更大的，在解決問題上，

GA

提供了更多的可選模式，可以多個模式進行一系列操作進行改進，

SA

則是在目前模式上進行操作，

GA

更容易跳出局部最優。

使用GA算法解決TSP問題Genetic Algorithm

文章目錄

Genetic Algorithm

導言

GA算法流程

初始化種群

個體适應度計算

選擇

交叉

變異

效果

總結

遺傳算法的優化思路

GA與SA的比較

繼續閱讀

K-近鄰算法以及圖像分類應用

小i機器人受邀赴韓交流，CFO首爾亞洲金融論壇演講

吳恩達deeplearning

吳恩達logistic回歸實作

【人工智能行業大師訪談1】吳恩達采訪 Geoffery Hinton

吳恩達機器學習筆記（3）

吳恩達j機器學習之過拟合

吳恩達機器學習(一) 介紹

深度學習模型分析人類複雜疾病的準确性

疾病研究：重症肌無力

人工智能如何有效地運用于自然語言處理

新聞 | Mapbox 牽手阿裡，飛豬旅行上線六大城市地圖功能

[HTML5]自定義屬性 data-* 和 jQuery.data 詳解

2021-2025年中國運動療法（KT）帶行業市場供需與戰略研究報告

2021年危險化學品經營機關安全管理人員考試題庫及危險化學品經營機關安全管理人員考試技巧

無人機--飛控科普