遺傳演算法在Python中的應用

一、遺傳演算法簡介

遺傳演算法（Genetic Algorithm）是優化問題中的一種進化演算法。這種演算法源於生物學中進化理論的基本思想，通過模擬生物的進化過程來解決問題。遺傳演算法具有非常廣泛的適用範圍，在機器學習、數據挖掘、優化等領域都有廣泛的應用。

遺傳演算法的核心思想是通過模擬自然界中的進化過程，進行優化的求解過程。具體來說，遺傳演算法首先需要設定一個初始種群，然後通過選擇、交叉、變異等操作，對種群不斷進行迭代和進化，最終得到最優解。

二、遺傳演算法的基本流程

遺傳演算法的基本流程如下：

初始化：創建一個種群，其中每一個個體對應一個問題的解。
評估：對每個個體進行評估，得到該個體對應問題的解的適應度。
選擇：根據適應度對種群進行選擇，選擇前若干個個體作為下一步的父代。
交叉：對父代進行交叉，生成下一代個體。
變異：對下一代進行變異，引入新的基因。
替換：用新的個體替換原有的個體，生成新的種群。
終止：如果滿足停止條件，則演算法停止，返回最優解。

三、遺傳演算法的應用案例

案例1：函數最優化問題

以下面的函數為例，來演示如何使用遺傳演算法求解函數最優化問題。

def function(x):
    return x*x + 5*math.sin(x)

使用遺傳演算法求解函數最優化問題，需要設計好適應度函數。在這裡，用函數的取值來作為個體的適應度。具體的實現如下：

import random
import math

def function(x):
    return x*x + 5*math.sin(x)

# 適應度函數
def fitness_func(individual):
    return function(individual)

# 種群規模
POPULATION_SIZE = 100
# 交叉率
CROSSOVER_RATE = 0.8
# 變異率
MUTATION_RATE = 0.1
# 最大迭代次數
MAX_ITERATION = 100

# 種群類
class Population:
    def __init__(self, size):
        self.individuals = []
        for i in range(size):
            individual = random.uniform(-10, 10)
            self.individuals.append(individual)

    # 獲取種群中適應度最高的個體
    def get_best_individual(self):
        return max(self.individuals, key=fitness_func)

    # 獲取種群的平均適應度
    def get_average_fitness(self):
        total_fitness = sum([fitness_func(individual) for individual in self.individuals])
        return total_fitness / len(self.individuals)

    # 選擇
    def selection(self):
        fitness_list = [fitness_func(individual) for individual in self.individuals]
        fitness_sum = sum(fitness_list)
        fitness_prob = [fitness / fitness_sum for fitness in fitness_list]
        selected = random.choices(self.individuals, weights=fitness_prob, k=POPULATION_SIZE)
        return selected

    # 交叉
    def crossover(self, individuals):
        new_individuals = []
        for i, individual in enumerate(individuals):
            if random.random() < CROSSOVER_RATE and i != 0:
                parent1 = individual
                parent2 = individuals[i-1]
                m_rate = random.random()
                new_individual = m_rate * parent1 + (1 - m_rate) * parent2
                new_individuals.append(new_individual)
        return new_individuals

    # 變異
    def mutation(self, individuals):
        new_individuals = []
        for individual in individuals:
            if random.random() < MUTATION_RATE:
                new_individual = random.uniform(-10, 10)
            else:
                new_individual = individual
            new_individuals.append(new_individual)
        return new_individuals

    # 更新種群
    def update(self):
        selected = self.selection()
        crossed = self.crossover(selected)
        mutated = self.mutation(crossed)
        self.individuals = mutated

在這裡，我們設置種群大小為100，交叉率為0.8，變異率為0.1，最大迭代次數為100。定義一個Population類，實現選擇、交叉、變異等操作。最終得到該函數的最優解。

案例2：0-1背包問題

0-1背包問題是一個經典的組合優化問題，被廣泛應用於生產排程、資源分配等領域。以下是0-1背包問題的一個例子：

有一張表格，每行表示一件物品與其相應的權值和重量，背包的容量為C。假設每樣物品只有一個，即只有一件可用，如何選擇才能使得背包中的物品總權值最大？

使用遺傳演算法求解0-1背包問題，需要設計好適應度函數。在這裡，用背包中物品的權值之和來作為個體的適應度。具體的實現如下：

import random

# 物品類
class Item:
    def __init__(self, weight, value):
        self.weight = weight
        self.value = value

# 適應度函數
def fitness_func(individual, items, capacity):
    total_weight = sum([items[i].weight for i in range(len(individual)) if individual[i] == 1])
    if total_weight > capacity:
        return 0
    else:
        total_value = sum([items[i].value for i in range(len(individual)) if individual[i] == 1])
        return total_value

# 種群規模
POPULATION_SIZE = 100
# 交叉率
CROSSOVER_RATE = 0.8
# 變異率
MUTATION_RATE = 0.1
# 最大迭代次數
MAX_ITERATION = 100

# 種群類
class Population:
    def __init__(self, size, items, capacity):
        self.individuals = []
        self.items = items
        self.capacity = capacity
        for i in range(size):
            individual = [random.randint(0, 1) for _ in range(len(items))]
            self.individuals.append(individual)

    # 獲取種群中適應度最高的個體
    def get_best_individual(self):
        return max(self.individuals, key=lambda x: fitness_func(x, self.items, self.capacity))

    # 獲取種群的平均適應度
    def get_average_fitness(self):
        total_fitness = sum([fitness_func(individual, self.items, self.capacity) for individual in self.individuals])
        return total_fitness / len(self.individuals)

    # 選擇
    def selection(self):
        fitness_list = [fitness_func(individual, self.items, self.capacity) for individual in self.individuals]
        fitness_sum = sum(fitness_list)
        fitness_prob = [fitness / fitness_sum for fitness in fitness_list]
        selected = random.choices(self.individuals, weights=fitness_prob, k=POPULATION_SIZE)
        return selected

    # 交叉
    def crossover(self, individuals):
        new_individuals = []
        for i, individual in enumerate(individuals):
            if random.random() < CROSSOVER_RATE and i != 0:
                parent1 = individual
                parent2 = individuals[i-1]
                m_point = random.randint(1, len(self.items)-1)
                new_individual = parent1[:m_point] + parent2[m_point:]
                new_individuals.append(new_individual)
        return new_individuals

    # 變異
    def mutation(self, individuals):
        new_individuals = []
        for individual in individuals:
            if random.random() < MUTATION_RATE:
                m_point = random.randint(0, len(self.items)-1)
                individual[m_point] = 1 - individual[m_point]
            new_individuals.append(individual)
        return new_individuals

    # 更新種群
    def update(self):
        selected = self.selection()
        crossed = self.crossover(selected)
        mutated = self.mutation(crossed)
        self.individuals = mutated

在這裡，我們設置種群大小為100，交叉率為0.8，變異率為0.1，最大迭代次數為100。定義一個Population類，實現選擇、交叉、變異等操作。最終得到該問題的最優解。

原創文章，作者：小藍，如若轉載，請註明出處：https://www.506064.com/zh-tw/n/196876.html