差分进化算法

一、简介

差分进化（DE）是一种算法，通过创建一些随机个体，将它们与预定义的评估指标进行比较，并保留最好的个体，然后通过混合剩余个体的特征来创建新的个体，并重复这个过程来解决全局优化问题。在接下来的编码中，向大家仔细地解释这个过程。

二、代码

# 创建一个对象。
from typing import List, Dict, Tuple, Union

class Individual:
    def __init__(
            self,
            parameters: Dict[str, float],
            score: Union[float, None] = None
    ) -> None:
        super().__init__()
        self.parameter_values = parameters
        self.score = score
   # 该对象保存单个个体的参数和分数。具有参数的个体x=2, y=3     
parameter_value = {"x":2, "y":3}
score = 13
# 评分
def scoring(ind: Individual) -> float:
    return ind.parameter_values["x"] ** 2 + ind.parameter_values["y"] ** 2
# 创造一个群体并进化它们。
class Population:
    # 最大化方向常量
    MAXIMIZE = 1
    # 最小化方向常量
    MINIMIZE = -1

    def __init__(
            self,
            pop_size,  # 种群大小
            direction: int,  # 优化方向（1 表示最大化，-1 表示最小化）
            bounds: Dict[str, Tuple[float, float]],  # 参数的边界范围字典
            parameters: List[str]  # 参数名称列表
    ) -> None:
        """
        初始化 Population 类的实例

        参数：
        pop_size (int)：种群的大小
        direction (int)：优化的方向，1 表示最大化，-1 表示最小化
        bounds (Dict[str, Tuple[float, float]])：包含每个参数的边界范围的字典
        parameters (List[str])：参数的名称列表
        """
        self.pop_size = pop_size
        self.direction = direction
        self.bounds = bounds
        self.parameters = parameters
        self.individuals: List[Individual] = []  # 存储个体的列表

    def _create_individual(self) -> Individual:
        """
        内部方法，用于创建一个个体

        返回：
        Individual：创建的个体
        """
        dict_parameters = {}  # 用于存储个体的参数值
        for parameter in self.parameters:
            # 在参数的边界范围内生成随机值
            param_value = random.uniform(self.bounds[parameter][0], self.bounds[parameter][1])
            dict_parameters[parameter] = param_value
        individual = Individual(parameters=dict_parameters)  # 创建个体对象
        individual.score = scoring(individual)  # 计算个体的得分
        return individual

    def initiate(self):
        """
        初始化种群，创建指定数量的个体并添加到 individuals 列表中
        """
        for i in range(self.pop_size):
            individual = self._create_individual()
            self.individuals.append(individual)

    def get_best_individual(self) -> Individual:
        """
        获取种群中得分最优的个体

        返回：
        Individual：得分最优的个体
        """
        self.best_individual = max(self.individuals, key=lambda x: x.score * self.direction)
        return self.best_individual

    def get_worst_individual(self) -> Individual:
        """
        获取种群中得分最差的个体

        返回：
        Individual：得分最差的个体
        """
        self.best_individual = min(self.individuals, key=lambda x: x.score * self.direction)
        return self.best_individual

    def get_mean_score(self) -> float:
        """
        计算种群中个体得分的平均值

        返回：
        float：个体得分的平均值
        """
        self.mean_score = sum([ind.score for ind in self.individuals]) / len(self.individuals)
        return self.mean_score

    def get_std_score(self) -> float:
        """
        计算种群中个体得分的标准差

        返回：
        float：个体得分的标准差
        """
        self.std_score = sum([(ind.score - self.mean_score) ** 2 for ind in self.individuals]) / len(self.individuals)
        return self.std_score
        class Optimization:
    def __init__(self, f: float, cp: float, population: Population):
        """
        初始化 Optimization 类的实例

        参数：
        f (float)：某个相关的浮点数参数
        cp (float)：某个相关的浮点数参数
        population (Population)：种群对象
        """
        self.f = f
        self.cp = cp
        self.population = population

    @staticmethod
    def _mutant_choose(population: Population) -> Tuple[Individual, Individual, Individual]:
        """
        静态方法，从种群中选择 3 个随机个体

        参数：
        population (Population)：要选择个体的种群

        返回：
        Tuple[Individual, Individual, Individual]：随机选择的 3 个个体
        """
        # 从种群的个体列表中随机抽取 3 个个体
        individuals = population.individuals
        random_individuals = random.sample(individuals, 3)
        return tuple(random_individuals)

    @staticmethod
    def _handle_boundaries(parameter_value: float, bounds: Tuple[float, float]) -> float:
        """
        静态方法，处理参数值超出边界的情况

        参数：
        parameter_value (float)：要检查的参数值
        bounds (Tuple[float, float])：参数的边界范围

        返回：
        float：处理后的参数值
        """
        # 如果参数值大于上界，将其设为上界
        if parameter_value > bounds[1]:
            parameter_value = bounds[1]
        # 如果参数值小于下界，将其设为下界
        elif parameter_value < bounds[0]:
            parameter_value = bounds[0]
        return parameter_value

    @staticmethod
    def _calculate_parameter(
            semi_parents: Tuple[Individual, Individual, Individual],
            parameter_name: str,
            bounds: Tuple[float, float],
            f: float
    ) -> float:
        """
        静态方法，根据半亲代计算试验个体的参数

        参数：
        semi_parents (Tuple[Individual, Individual, Individual])：三个半亲代个体
        parameter_name (str)：参数的名称
        bounds (Tuple[float, float])：参数的边界范围
        f (float)：某个相关的浮点数参数

        返回：
        float：计算得到的试验个体的参数值
        """
        # 根据半亲代计算试验个体的参数
        trial_parameter = semi_parents[0].parameter_values[parameter_name] + \
                          f * (semi_parents[1].parameter_values[parameter_name] -
                               semi_parents[2].parameter_values[parameter_name])
        # 处理参数值超出边界的情况
        trial_parameter = Optimization._handle_boundaries(trial_parameter, bounds)
        return trial_parameter

    def _mutation(self, population: Population) -> Individual:
        """
        执行变异操作，创建试验个体

        参数：
        population (Population)：要操作的种群

        返回：
        Individual：创建的试验个体
        """
        # 选择半亲代
        semi_parents = Optimization._mutant_choose(population)
        trial_parameters = {}
        # 对于每个参数名称
        for parameter in population.parameters:
            # 计算试验个体的参数
            trial_parameter = self._calculate_parameter(
                semi_parents, parameter,
                population.bounds[parameter],
                self.f
            )
            trial_parameters[parameter] = trial_parameter
        # 创建试验个体
        trial_individual = Individual(parameters=trial_parameters)
        return trial_individual

def _crossover(self, parent: Individual, trial: Individual, parameters):
    """
    执行交叉操作，生成子代个体

    参数：
    parent (Individual)：父代个体
    trial (Individual)：试验个体
    parameters (List[str])：参数列表

    返回：
    Individual：生成的子代个体
    """
    child_parameters = {}
    # 对于每个参数
    for parameter in parameters:
        # 生成随机概率
        prob = random.random()
        # 根据概率决定子代参数取值来自父代还是试验个体
        if prob < self.cp:
            child_parameters[parameter] = parent.parameter_values[parameter]
        else:
            child_parameters[parameter] = trial.parameter_values[parameter]
    # 创建子代个体
    child = Individual(parameters=child_parameters)
    return child

@staticmethod
def _selection(child: Individual, parent: Individual, direction: int) -> bool:
    """
    执行选择操作，比较子代和父代个体的得分，并根据方向决定是否选择子代

    参数：
    child (Individual)：子代个体
    parent (Individual)：父代个体
    direction (int)：优化方向（1 表示最大化，-1 表示最小化）

    返回：
    bool：如果子代更优（或得分相等且倾向于选择子代），则返回 True，否则返回 False
    """
    child.score = scoring(child)
    # 在得分相等的情况下倾向于选择子代
    if direction == Population.MAXIMIZE:
        return child.score >= parent.score
    else:
        return child.score <= parent.score


def main(self, generations: int):
    """
    主函数，执行多代的优化过程

    参数：
    generations (int)：要执行的代数
    """
    population = self.population

    for gen in range(generations):
        new_individuals = []

        for i in range(population.pop_size):
            # 变异操作
            trial_individual = self._mutation(population)

            # 交叉操作
            parent = population.individuals[i]
            child = self._crossover(parent, trial_individual, population.parameters)

            # 选择操作
            if self._selection(child, parent, self.population.direction):
                new_individuals.append(child)
            else:
                new_individuals.append(parent)

        # 用新的个体更新种群
        population.individuals = new_individuals

        # 在每一代结束时更新统计信息或执行其他必要任务
        best_individual = population.get_best_individual()
        worst_individual = population.get_worst_individual()
        mean_score = population.get_mean_score()
        std_score = population.get_std_score()

        # 打印或存储关于这一代的相关信息
        print(
            f"Generation {gen + 1}: Best Score - {best_individual.score}, Worst Score - {worst_individual.score}, Mean Score - {mean_score}, Std Score - {std_score}")

    # 完成所有代后，可以返回或执行任何最终操作
    final_best_individual = population.get_best_individual()
    print(
        f"Optimization complete. Best individual: {final_best_individual.parameter_values}, Score: {final_best_individual.score}")



population = Population(
    pop_size=50,
    direction=Population.MINIMIZE,
    bounds={"x": (-100, 100), "y": (-100, 100)},
    parameters=["x", "y"]
)
population.initiate()

optimization = Optimization(
    f=0.5,
    cp=0.7,
    population=population
)

optimization.main(20)

三、局限性

尽管差分进化算法用途广泛，但它也并非没有缺点。这些限制中最明显的是许多元启发式算法所面临的局部最优问题。DE算法或任何遗传算法都不能保证它们找到的最佳参数就是最佳解。想象一下一个深谷，我们的人口想要穿过它，人们想要降低地面，所以他们都可能会进入山谷并被困在那里，而其他地方有一个更深的山谷。更改参数以使其更加多样化，并围绕解决方案空间采取更大的步骤可以有所帮助，但会带来性能成本。