改进萤火虫算法之三：混沌萤火虫算法（Chaos Firefly Algorithm，CFA）
混沌萤火虫算法（Chaos Firefly Algorithm，CFA）是一种基于混沌理论和生物萤火虫行为的新型优化算法。
一、基本原理
混沌萤火虫算法结合了混沌优化技术和萤火虫算法的优势。混沌是一种非线性动力学系统的性质，具有灵敏度和不可预测性，以及很高的随机性和复杂度。混沌序列的引入使得算法具有更高的搜索多样性，有助于避免算法陷入局部最优解，能够更好地找到全局最优解。萤火虫算法则受自然界萤火虫的发光行为启发而来，借鉴了萤火虫相互吸引和闪烁的行为，用以模拟物种在自然界中寻找食物和交流信息的过程。
二、算法步骤
混沌萤火虫算法的主要步骤包括：
（1）初始化参数：包括萤火虫个体数、萤火虫飞行范围、光强度、混沌初始参数等。萤火虫个体可以用一个向量来表示，向量的每个分量对应了问题的每个决策变量。萤火虫的位置随机初始化，并设置发光亮度。
（2）计算适应度值：根据问题的目标函数对每个萤火虫位置进行评估，以确定其在当前位置的适应度。适应度值代表了解决方案的优劣程度，亮度值越高代表解决方案越优秀。
（3）生成光信号：根据萤火虫之间的距离和亮度大小，生成光信号。萤火虫之间的互相吸引程度取决于其发光亮度值的强度和距离。
（4）更新萤火虫位置：根据光信号的吸引度和移动步长来更新位置。这个位置更新是在当前解的基础上进行调整，从而实现搜索过程。同时，根据萤火虫的亮度调整光强度，以指导其他萤火虫的移动。
（5）全局最优更新：根据所有萤火虫的亮度值，更新全局最优解。
（6）收敛判断：判断算法是否达到停止条件，若满足条件则输出全局最优解。
三、算法的数学表达
1. 基本假设与参数
（1）萤火虫个体：用向量表示，每个分量对应一个决策变量。
（2）位置初始化：在搜索空间内随机初始化萤火虫的位置。
（3）光强度：与萤火虫的目标函数值相关，作为萤火虫的亮度或吸引力。
（4）混沌参数：用于生成混沌序列，影响搜索的多样性和遍历性。
2. 数学表达
（1）位置向量：设萤火虫
的位置向量为
。
（2）目标函数：
表示萤火虫
的目标函数值，用于评估其亮度或吸引力。
（3）混沌序列：使用混沌映射函数生成混沌序列，如Logistic映射或Tent映射。混沌序列用于在搜索过程中提供新的解或调整搜索方向。
3. 关键公式
（1）混沌映射函数（以Logistic映射为例）：
其中，
为混沌系统的控制参数，通常取值在(0,4]之间；
为当前混沌状态；
为下一状态的混沌值。
（2）萤火虫之间的吸引力：
其中，
表示萤火虫
对萤火虫
的吸引力；
为最大吸引力；
是光强吸收系数，
是萤火虫
和萤火虫
之间的距离。
（3）位置更新公式：
其中，
表示萤火虫
更新后的位置；
表示萤火虫
更新前的位置；
为步长因子，控制移动步长；
为吸引力；
和
分别为萤火虫
和
的位置；混沌调整项是基于混沌序列生成的调整量，用于增加搜索的多样性。
（4）混沌调整项：
混沌调整项可以基于混沌序列生成，如使用混沌映射函数产生的混沌值对位置进行微调。具体实现方式可能因问题而异，但通常涉及混沌序列与当前位置的某种组合或运算。
****四、****混沌序列生成规则
CFA中的混沌序列生成规则是算法的关键部分之一，它利用混沌系统的随机性和遍历性来提高搜索的多样性和全局搜索能力。
1.混沌理论简介
混沌理论是20世纪70年代由美国数学家洛伦兹首次提出的一种新的动力学系统理论。混沌系统具有高度不确定性和灵敏度依赖初始条件的特性，其非线性性质使得其呈现出复杂且难以预测的行为。在混沌系统中，即使微小的初始扰动也会导致系统走向完全不同的轨迹。
2.混沌序列生成原理
混沌序列是混沌现象在非线性动态系统中出现的确定性的类似随机的过程的产物之一。这种过程既非周期又不收敛，并且对初始值极其敏感。基于混沌现象的的特性，混沌序列具有以下特性：初始条件的微小的变化即可导致大范围内不同的结果，这使得信息的保密性大大增强。
在CFA中，混沌序列通常通过混沌映射函数生成。常见的混沌映射函数包括Logistic映射、Chebyshev映射及Tent映射等。这些映射函数能够产生具有混沌特性的序列，用于在搜索过程中提供新的解或调整搜索方向。
3.混沌序列生成规则
（1）选择混沌映射函数：根据问题的具体需求和混沌映射函数的特性，选择合适的混沌映射函数。例如，Logistic映射函数因其简单且易于实现而常被选用。
（2）设置初始值和控制参数：为混沌映射函数设置初始值和控制参数。初始值通常是一个在特定范围内的随机数，而控制参数则根据混沌映射函数的特性进行设定。
（3）迭代生成混沌序列：根据混沌映射函数的迭代公式，从初始值开始迭代生成混沌序列。每次迭代都会根据当前状态和映射函数的规则产生下一个状态的值。
（4）量化处理：为了将生成的混沌序列应用于CFA中，可能需要对混沌序列进行量化处理。例如，可以将混沌序列的连续值量化为离散值，或者根据需要将混沌序列的值映射到特定的范围内。
4. 混沌序列在CFA中的应用
在CFA中，混沌序列主要用于以下几个方面：
（1）初始化种群：利用混沌序列的随机性和遍历性初始化萤火虫的位置，以获得质量较高且分布较均匀的初始解。
（2）调整搜索方向：在搜索过程中，根据混沌序列的值调整萤火虫的搜索方向或步长，以增加搜索的多样性和避免陷入局部最优解。
（3）优化解的选择：在迭代过程中，利用混沌序列对部分适应值低的个体进行混沌优化，以提高种群的多样性并寻找更优的解。
五****、算法流程****
（1）初始化，算法参数和萤火虫位置。
（2）计算亮度，根据目标函数计算萤火虫的亮度。
（3）生成混沌序列，根据混沌映射函数生成混沌序列。
（4）计算吸引力与距离，计算萤火虫之间的吸引力和位置更新量（距离）。
（5）更新萤火虫的位置，并考虑混沌调整项的影响。
（6）评估更新后萤火虫的亮度，并更新全局最优解。
（7）判断是否满足停止条件，如达到最大迭代次数或满足精度要求。
（8）若不满足停止条件，则返回步骤3继续迭代；否则，输出全局最优解。
图1 混沌萤火虫算法流程图
六****、算法特点****
（1）全局搜索能力强：由于混沌序列的引入，算法具有更高的搜索多样性，能够更有效地在全局范围内搜索最优解。
（2）收敛速度快：通过模拟萤火虫之间的光信号传递机制，实现了群体智能的优化过程，从而加快了收敛速度。
（3）鲁棒性和稳定性好：算法在解决各种优化问题时展现了出色的性能，并且具有较好的鲁棒性和稳定性。
七****、应用领域****
混沌萤火虫算法已经成功应用于多个领域，包括工程优化、神经网络训练、数据挖掘、无线传感器网络、多目标优化、图像处理等方面。例如，在无线传感器网络中，通过优化传感器节点的部署和通信协议，可以提高网络能耗效率和数据传输速率；在图像处理领域，通过优化滤波器参数和阈值等，可以提高图像处理的准确性。
八****、改进与发展****
尽管混沌萤火虫算法具有许多优点，但也存在一些不足之处，如对参数的敏感性较高、调参较为困难，以及可能陷入局部最优解等。为了克服这些问题，研究者们正在不断改进算法，如引入自适应参数控制策略、多种混沌映射函数等方法，从而进一步提升算法的性能。
九、python示例
以下是一个使用Python实现的CFA的完整示例。这个示例将解决一个简单的优化问题：最小化函数Rastrigin函数 。Rastrigin函数是一个非凸函数，具有许多局部最小值，常用于测试全局优化算法。该函数在三维空间中点 (0,0) 处有一个全局最小值，通过搜索找到最小值所在的位置。
1.目标函数：
Rastrigin函数是一个常用的非线性多峰测试函数，它在优化算法中用来评估算法的性能。这个函数在二维空间中定义如下：
其中，
和
是两个独立变量，函数的全局最小值点为(0,0)，最小值为0。
展示在二维/三维空间中绘制这个函数的图像：
图2 Rastrigin函数的二维效果图
图3 Rastrigin函数的三维效果图
2.参数设置
首先，我们为了优化目标函数，先设置关键参数的初始范围，初始设置如下：
参数设置
num_fireflies = 30
dim = 2
max_iter = 100
beta0 = 1
gamma = 1
alpha = 0.2
chaos_factor = 0.1
search_space = [-5.12, 5.12]
整个程序过程：首先，我们需要定义一些基本的函数，包括混沌映射函数（例如Logistic映射）、目标函数、萤火虫之间的吸引力计算、位置更新等。然后，我们将这些函数整合到一个主循环中，以执行CFA的迭代过程。最后，我们将绘制迭代过程中最优解的变化情况。
CFA算法的Python代码如下：
import numpy as np
import matplotlib.pyplot as plt
# 定义Logistic混沌映射函数
def logistic_map(x, r=3.99):
return r * x * (1 - x)
# 定义目标函数（例如，Rastrigin函数）
def rastrigin(x):
return 10 * len(x) + sum([(xi ** 2 - 10 * np.cos(2 * np.pi * xi)) for xi in x])
# 初始化萤火虫位置
def initialize_fireflies(num_fireflies, dim, search_space):
return np.random.uniform(search_space[0], search_space[1], (num_fireflies, dim))
# 计算萤火虫之间的吸引力
def calculate_attraction(fireflies, beta0, gamma):
num_fireflies, dim = fireflies.shape
attraction = np.zeros((num_fireflies, num_fireflies, dim))
for i in range(num_fireflies):
for j in range(num_fireflies):
if i != j:
rij = np.linalg.norm(fireflies[i] - fireflies[j])
beta = beta0 * np.exp(-gamma * rij ** 2)
attraction[i, j] = beta * (fireflies[j] - fireflies[i]) / rij
return attraction
# 更新萤火虫位置
def update_fireflies(fireflies, attraction, alpha, chaos_factor):
num_fireflies, dim = fireflies.shape
new_fireflies = fireflies.copy()
for i in range(num_fireflies):
total_attraction = np.sum(attraction[i], axis=0)
if np.linalg.norm(total_attraction) > 0:
direction = total_attraction / np.linalg.norm(total_attraction)
else:
direction = np.random.uniform(-1, 1, dim)
new_position = fireflies[i] + alpha * direction + chaos_factor * (np.random.uniform(-1, 1, dim) - 0.5)
new_fireflies[i] = np.clip(new_position, -5.12, 5.12) # 假设搜索空间为[-5.12, 5.12]
return new_fireflies
# 主CFA函数
def chaos_firefly_algorithm(num_fireflies, dim, max_iter, beta0, gamma, alpha, chaos_factor, search_space):
fireflies = initialize_fireflies(num_fireflies, dim, search_space)
best_solution = fireflies[np.argmin([rastrigin(x) for x in fireflies])]
best_value = rastrigin(best_solution)
values = [best_value]
for t in range(max_iter):
attraction = calculate_attraction(fireflies, beta0, gamma)
fireflies = update_fireflies(fireflies, attraction, alpha, chaos_factor * logistic_map(t / max_iter))
current_best = fireflies[np.argmin([rastrigin(x) for x in fireflies])]
current_value = rastrigin(current_best)
if current_value < best_value:
best_solution = current_best
best_value = current_value
values.append(best_value)
return best_solution, best_value, values
# 参数设置
num_fireflies = 30
dim = 2
max_iter = 100
beta0 = 1
gamma = 1
alpha = 0.2
chaos_factor = 0.1
search_space = [-5.12, 5.12]
# CFA
best_solution, best_value, values = chaos_firefly_algorithm(num_fireflies, dim, max_iter, beta0, gamma, alpha, chaos_factor, search_space)
# 绘制效果图
plt.plot(values)
plt.xlabel('Iteration')
plt.ylabel('Best Value')
plt.title('Chaos Firefly Algorithm Optimization Process')
plt.grid(True)
plt.show()
print(f"Best Solution: {best_solution}")
print(f"Best Value: {best_value}")
可视化此时算法优化过程如下：
图4 可视化算法优化过程
注意事项：
（1）混沌映射函数：在这个例子中，我们使用了Logistic映射函数来生成混沌因子，但它可以替换为其他混沌映射函数。
（2）目标函数：这里使用了Rastrigin函数作为目标函数，但你可以根据具体问题替换为其他函数。
（3）参数调整：CFA的参数（如beta0, gamma, alpha, chaos_factor）需要根据具体问题进行调整，以获得最佳性能。
（4）搜索空间：在这个例子中，搜索空间被设置为[-5.12, 5.12]，但你可以根据具体问题调整它。
（5）效果图：代码绘制了迭代过程中最优解的变化情况，以帮助你了解算法的性能。
3.与经典萤火虫算法FA的比较结果
混沌萤火虫算法通过引入混沌映射来增强搜索能力，而经典萤火虫算法则没有这种机制。通过对比两者的优化结果，可以观察到混沌萤火虫算法在全局搜索能力上的提升。
与FA算法对比的Python代码如下：
import numpy as np
import matplotlib.pyplot as plt
def rastrigin(x):
return 10 * len(x) + np.sum(x**2 - 10 * np.cos(2 * np.pi * x))
def chaos_map(x):
return 4 * x * (1 - x)
def initialize_fireflies(n, dim, lb, ub):
return lb + (ub - lb) * np.random.rand(n, dim)
def attractiveness(beta0, r):
return beta0 / (1 + r**2)
def move_fireflies(fireflies, fitness, beta0, alpha, gamma, lb, ub):
n, dim = fireflies.shape
for i in range(n):
for j in range(n):
if fitness[i] > fitness[j]:
r = np.linalg.norm(fireflies[i] - fireflies[j])
beta = attractiveness(beta0, r)
fireflies[i] += beta * (fireflies[j] - fireflies[i]) + alpha * (np.random.rand(dim) - 0.5)
fireflies[i] = np.clip(fireflies[i], lb, ub)
return fireflies
def chaos_firefly_algorithm(n, dim, lb, ub, max_gen, beta0, alpha, gamma):
fireflies = initialize_fireflies(n, dim, lb, ub)
fitness = np.array([rastrigin(firefly) for firefly in fireflies])
best_firefly = fireflies[np.argmin(fitness)]
best_fitness = np.min(fitness)
for gen in range(max_gen):
fireflies = move_fireflies(fireflies, fitness, beta0, alpha, gamma, lb, ub)
fitness = np.array([rastrigin(firefly) for firefly in fireflies])
current_best = np.min(fitness)
if current_best < best_fitness:
best_fitness = current_best
best_firefly = fireflies[np.argmin(fitness)]
# Apply chaos map to enhance exploration
for i in range(n):
for j in range(dim):
fireflies[i, j] = chaos_map(fireflies[i, j])
fireflies = np.clip(fireflies, lb, ub)
return best_firefly, best_fitness
# Parameters
n = 20
dim = 2
lb = -5.12
ub = 5.12
max_gen = 100
beta0 = 1
alpha = 0.2
gamma = 1
best_firefly_cfa, best_fitness_cfa = chaos_firefly_algorithm(n, dim, lb, ub, max_gen, beta0, alpha, gamma)
print(f"CFA Best Solution: {best_firefly_cfa}, Best Fitness: {best_fitness_cfa}")
def firefly_algorithm(n, dim, lb, ub, max_gen, beta0, alpha, gamma):
fireflies = initialize_fireflies(n, dim, lb, ub)
fitness = np.array([rastrigin(firefly) for firefly in fireflies])
best_firefly = fireflies[np.argmin(fitness)]
best_fitness = np.min(fitness)
for gen in range(max_gen):
fireflies = move_fireflies(fireflies, fitness, beta0, alpha, gamma, lb, ub)
fitness = np.array([rastrigin(firefly) for firefly in fireflies])
current_best = np.min(fitness)
if current_best < best_fitness:
best_fitness = current_best
best_firefly = fireflies[np.argmin(fitness)]
return best_firefly, best_fitness
best_firefly_fa, best_fitness_fa = firefly_algorithm(n, dim, lb, ub, max_gen, beta0, alpha, gamma)
print(f"FA Best Solution: {best_firefly_fa}, Best Fitness: {best_fitness_fa}")
# Plotting the results
plt.figure(figsize=(12, 6))
# Generate the grid for contour plot
x = np.linspace(lb, ub, 400)
y = np.linspace(lb, ub, 400)
X, Y = np.meshgrid(x, y)
# Calculate Z values for each point in the grid
Z = np.zeros_like(X)
for i in range(X.shape[0]):
for j in range(X.shape[1]):
Z[i, j] = rastrigin(np.array([X[i, j], Y[i, j]]))
plt.subplot(1, 2, 1)
plt.contourf(X, Y, Z, 50, cmap='viridis')
plt.colorbar()
plt.scatter(best_firefly_cfa[0], best_firefly_cfa[1], color='red', label='CFA Best Solution')
plt.title('Chaos Firefly Algorithm')
plt.xlabel('x')
plt.ylabel('y')
plt.legend()
plt.subplot(1, 2, 2)
plt.contourf(X, Y, Z, 50, cmap='viridis')
plt.colorbar()
plt.scatter(best_firefly_fa[0], best_firefly_fa[1], color='red', label='FA Best Solution')
plt.title('Firefly Algorithm')
plt.xlabel('x')
plt.ylabel('y')
plt.legend()
plt.tight_layout()
plt.show()
CFA与FA算法对比找到的最优解位置如下：
图5 经典萤火虫算法FA对比找到的最优解
综上所述，混沌萤火虫算法是一种高效的优化算法，通过模拟萤火虫之间的光信号传递机制和混沌系统的特性，实现了群体智能的优化过程。在未来，混沌萤火虫算法将继续发展和完善，为解决各种复杂的优化问题提供更好的解决方案。