一、简介
差分进化（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算法或任何遗传算法都不能保证它们找到的最佳参数就是最佳解。想象一下一个深谷，我们的人口想要穿过它，人们想要降低地面，所以他们都可能会进入山谷并被困在那里，而其他地方有一个更深的山谷。更改参数以使其更加多样化，并围绕解决方案空间采取更大的步骤可以有所帮助，但会带来性能成本。
