启发式算法 – Heuristic

zhangtianzhao · 发表于 2023-4-18 19:38

启发式算法（Heuristic Algorithm）是一种常用于求解复杂优化问题的计算方法，其主要思想是模拟人类或自然界中蕴含的智慧和经验来寻找问题最优解。与传统数学方法相比，启发式算法更加注重在近似解空间中进行搜索，从而能够快速找到较好的结果。
启发式算法有许多类型，其中一些常见的包括遗传算法、鱼群算法、蚁群算法、粒子群算法等等。这些算法都提供了不同的机制来解决不同的问题，并且通常具有良好的适应性和可扩展性。
启发式算法通常被应用在组合优化、约束优化、排队论、路径规划、生产调度等领域中，并被证明在某些情况下能够为问题提供更好的解决方案。然而，在具体应用时需要考虑各个参数和随机性对算法效果的影响，并根据实际问题和需求选择适当的启发式算法。
遗传算法（Genetic Algorithm，GA）

基于生物进化与遗传变异的思想，通过模拟基因的交叉和突变，并利用适应度函数筛选个体来搜索最优解。
该算法用于求解函数最小值，其中每个基因表示变量的取值，而染色体则代表具体的解向量。
import random

# 目标函数，这里以 f(x,y)=(x-10)^2+(y-20)^2 为例
def fitness(individual):
x = individual[0]
y = individual[1]
return (x - 10) ** 2 + (y - 20) ** 2

# 生成初始种群（个体数为pop_size，每个个体由两个基因构成）
def generate_initial_population(pop_size, gene_len):
population = []
for i in range(pop_size):
      individual = []
      for j in range(gene_len):
         individual.append(random.uniform(-50, 50)) # 基因取值范围为[-50,50]
      population.append(individual)
return population

# 交叉操作（选取概率较高的前两个个体进行交叉）
def crossover(parents, offspring_num):
offspring = []
for i in range(offspring_num):
      child = []
      for j in range(len(parents[0])):
         if random.random() < 0.5:
            child.append(parents[0][j])
         else:
            child.append(parents[1][j])
      offspring.append(child)
return offspring

# 变异操作（某个基因以一定概率发生随机改变）
def mutate(individual, mutation_prob):
for i in range(len(individual)):
      if random.random() < mutation_prob:
         individual += random.normalvariate(0, 1)
return individual

# 选择操作（针对种群中的每个个体进行选择，返回最优解）
def selection(population, offspring_num):
fitnesses = []
for individual in population:
      fitnesses.append(fitness(individual))
selected = sorted(zip(population, fitnesses), key=lambda x: x[1])[:offspring_num]
return [x[0] for x in selected]

# 遗传算法主函数
def genetic_algorithm(pop_size, gene_len, max_iter, crossover_prob, mutation_prob):
# 生成初始种群
population = generate_initial_population(pop_size, gene_len)

# 迭代寻找最优解
for i in range(max_iter):
      # 计算适应度并选择前两个个体进行交叉
      parents = selection(population, 2)
      offspring = crossover(parents, pop_size - 2)

      # 对新个体进行变异操作
      mutated_offspring = [mutate(x, mutation_prob) for x in offspring]

      # 用于与新个体进行竞争的父代是不变的，保护历史最优解
      new_population = selection(population, 2) + mutated_offspring

      # 输出历史最优解
      best_individual = min(population, key=fitness)
      print(&#34;Generation {}: Best Fitness {}&#34;.format(i+1, fitness(best_individual)))

      # 更新种群
      population = new_population

# 输出最优解和最优适应度
best_individual = min(population, key=fitness)
print(&#34;Best Solution: &#34;, best_individual)
print(&#34;Best Fitness: &#34;, fitness(best_individual))

# 示例运行
genetic_algorithm(pop_size=100, gene_len=2, max_iter=100, crossover_prob=0.8, mutation_prob=0.005)上述代码实现了一个简单的遗传算法，用于求解函数的最小值。
模拟退火算法（Simulated Annealing，SA）

通过对当前状态下的随机扰动与目标函数值之间的关系进行统计研究，以概率接受或者拒绝新的状态，从而降低系统能量并达到全局最优解。
该算法用于求解函数最小值，其中每个状态表示一个变量的取值，初始温度为T，降温速率为a，最大迭代次数为max_iter，初始解x0由用户自行给定。
import math
import random

# 目标函数，这里以 f(x)=(x-10)^2 为例
def fitness(x):
return (x - 10) ** 2

# 模拟退火函数
def simulated_annealing(x0, T, a, max_iter):
x = x0
for i in range(max_iter):
      # 生成新状态
      new_x = x + random.uniform(-1, 1)

      # 计算能量差
      delta_E = fitness(new_x) - fitness(x)

      # 根据概率接受或拒绝新状态
      if delta_E < 0 or math.exp(-delta_E / T) > random.uniform(0, 1):
         x = new_x

      # 按照指定速率降低温度
      T *= a

return x

# 示例运行
x0 = random.uniform(-50, 50) # 初始解随机选择
T = 100 # 初始温度
a = 0.95 # 降冷速率
max_iter = 1000 # 最大迭代次数

result = simulated_annealing(x0, T, a, max_iter)
print(&#34;Best Solution: &#34;, result)
print(&#34;Best Fitness: &#34;, fitness(result))上面的代码实现了一个简单的模拟退火算法，并用于求解函数的最小值。
粒子群优化算法（Particle Swarm Optimization，PSO）

基于鸟群的行为方式，通过设立多个粒子来进行搜索，在各个粒子之间通过信息交换实现全局最优解的搜索。
该算法用于求解函数最小值，其中每个粒子包含两个变量x1和x2表示粒子位置，以及两个速度变量v1和v2表示粒子移动速度。
import random

# 目标函数，这里以 f(x,y)=(x-10)^2+(y-20)^2 为例
def fitness(particle):
x = particle[0]
y = particle[1]
return (x - 10) ** 2 + (y - 20) ** 2

# 粒子群优化函数
def particle_swarm_optimization(pop_size, w, c1, c2, max_iter):
# 随机初始化每个粒子的位置和速度
particles = []
for i in range(pop_size):
      x = random.uniform(-50, 50)
      y = random.uniform(-50, 50)
      v1 = random.uniform(-1, 1)
      v2 = random.uniform(-1, 1)
      particles.append([(x, y), (v1, v2)])

# 初始化历史最佳位置和所有粒子的历史最佳位置
p_best = particles.copy()
for i in range(len(particles)):
      if fitness(particles[0]) < fitness(p_best[0]):
         p_best = particles.copy()

g_best = min(p_best, key=lambda x: fitness(x[0]))
g_best_pos = g_best[0]

# 迭代寻找最优解
for i in range(max_iter):
      for j in range(len(particles)):
         # 更新速度和位置
         v1 = w * particles[j][1][0] + c1 * random.uniform(0, 1) * (p_best[j][0][0]-particles[j][0][0]) + c2 * random.uniform(0, 1) * (g_best_pos[0]-particles[j][0][0])
         v2 = w * particles[j][1][1] + c1 * random.uniform(0, 1) * (p_best[j][0][1]-particles[j][0][1]) + c2 * random.uniform(0, 1) * (g_best_pos[1]-particles[j][0][1])
         newX = particles[j][0][0] + v1
         newY = particles[j][0][1] + v2

         if abs(newX) > 50:
            newX = random.uniform(-50, 50)
            particles[j][1][0] = 0
         if abs(newY) > 50:
            newY = random.uniform(-50, 50)
            particles[j][1][1] = 0

         particles[j][0] = (newX, newY)
         particles[j][1] = (v1, v2)

         # 更新历史最佳位置
         if fitness(particles[j][0]) < fitness(p_best[j][0]):
            p_best[j] = particles[j].copy()

      # 更新全局最佳位置
      g_best = min(p_best, key=lambda x: fitness(x[0]))
      g_best_pos = g_best[0]

      # 输出历史最优解
      print(&#34;Generation {}: Best Fitness {}&#34;.format(i+1, fitness(g_best_pos)))

# 输出最优解和最优适应度
print(&#34;Best Solution: &#34;, g_best_pos)
print(&#34;Best Fitness: &#34;, fitness(g_best_pos))

# 示例运行
particle_swarm_optimization(pop_size=50, w=0.6, c1=1.4, c2=1.4, max_iter=100)上述代码实现了一个简单的粒子群算法，用于求解函数的最小值。
蚁群算法（Ant Colony Optimization，ACO）

模拟蚂蚁在搜索食物过程中留下信息素，让其他蚂蚁跟从这些信息素寻找较为优美路径的过程。通过加强和挥发信息素实现优化。
该算法用于求解TSP（Traveling Salesman Problem，旅行商问题），即寻找一条经过所有城市且路径最短的路线。
import random
import numpy as np

# 读取数据文件，返回距离矩阵和城市数量
def read_data_file(file_path):
with open(file_path) as f:
      data = f.readlines()
coords = [list(map(float, x.strip().split(&#39; &#39;)[1:])) for x in data[6:-1]]
n = len(coords)
dist = np.zeros((n,n))
for i in range(n):
      for j in range(i+1,n):
         d = np.linalg.norm(np.subtract(coords,coords[j]))
         dist[j] = d
         dist[j] = d
return dist, n

# 蚂蚁类
class Ant:
def __init__(self, alpha, beta, pheromone, start_node):
      self.alpha = alpha # 信息素影响因子
      self.beta = beta # 启发函数值影响因子
      self.pheromone = pheromone # 信息素矩阵
      self.start_node = start_node
      self.n_city = pheromone.shape[0] # 城市数

# 根据当前选择的节点和剩余未选择节点的距离信息计算下一个节点
def select_next(self, curr_node, allowed_nodes):
      # 计算每个节点的概率值
      probs = []
      for node in allowed_nodes:
         phero_level = self.pheromone[curr_node][node]
         dist_level = 1.0 / self.dist_mat[curr_node][node]
         probs.append(pow(phero_level, self.alpha) * pow(dist_level, self.beta))
      # 根据概率随机选择下一个节点
      sum_probs = sum(probs)
      norm_probs = [x/sum_probs for x in probs]
      next_node = np.random.choice(allowed_nodes, p=norm_probs)
      return next_node

# 计算一只蚂蚁的路径长度
def tour(self):
      self.visited = set() # 已访问节点
      self.curr_node = self.start_node # 当前节点
      self.visited.add(self.curr_node)
      self.path_len = 0 # 路径长度
      while len(self.visited) < self.n_city:
         allowed_nodes = set(range(self.n_city)) - self.visited # 剩余未访问节点
         next_node = self.select_next(self.curr_node, allowed_nodes)
         self.visited.add(next_node)
         self.path_len += self.dist_mat[self.curr_node][next_node]
         self.curr_node = next_node
      self.path_len += self.dist_mat[self.curr_node][self.start_node] # 加上回到起点的距离
      return self.path_len

# 更新信息素矩阵
def update_pheromone(self):
      nodes = list(self.visited)
      for i in range(self.n_city):
         self.pheromone[nodes][nodes[(i+1)%self.n_city]] += 1.0 / self.path_len

# ACO算法
def aco(dist_mat, max_iter, ant_count=10, alpha=1, beta=2, rho=0.5):
# 初始化信息素矩阵，每个边上的初始信息素设置为1
pheromone = np.ones(dist_mat.shape)

# 开始迭代
for i in range(max_iter):
      ants = [Ant(alpha, beta, pheromone, random.randint(0,dist_mat.shape[0]-1)) for _ in range(ant_count)]
      paths = [ant.tour() for ant in ants]

      # 计算最优路径和长度
      best_ant_idx = np.argmin(paths)
      best_path = paths[best_ant_idx]
      best_tour = ants[best_ant_idx].visited

      # 更新信息素矩阵
      pheromone *= (1 - rho)
      for ant in ants:
         ant.update_pheromone()

      # 输出本次迭代结果
      print(&#34;Generation {}: Best Path Length {}&#34;.format(i+1, best_path))

return best_tour, best_path

# 运行示例
dist_mat, city_num = read_data_file(&#39;data.txt&#39;) # 读取数据文件

best_tour, best_path = aco(dist_mat, max_iter=100)
print(best_tour)
print(&#34;Length of the path found: &#34;, best_path)上述代码实现了一个简单的蚁群算法用于求解TSP问题。
人工鱼群算法（Artificial Fish Swarm Algorithm，AFSA）

将自然界鱼类群集在一个区域内进行食物寻求映射到寻优问题中。通过调整鱼类的位置和运动路径实现目标的达成。
该算法用于求解函数最小值，其中每个鱼表示一个变量的取值，初始种群大小为N。
import random
import math

# 目标函数，这里以 f(x,y)=(x-10)^2+(y-20)^2 为例
def fitness(fish):
x = fish[0]
y = fish[1]
return (x - 10) ** 2 + (y - 20) ** 2

# 人工鱼群算法函数
def artificial_fish_swarm(N, visual, step, delta, max_iter):
fishes = []
# 随机初始化N条鱼的位置和状态
for i in range(N):
      x = random.uniform(-50, 50)
      y = random.uniform(-50, 50)
      direction = random.uniform(0, 2*math.pi)
      speed = random.uniform(0, visual / 2)
      fishes.append([(x, y), direction, speed])

# 迭代寻找最优解
for iter in range(max_iter):
      # 活动阶段
      for i in range(N):
         # 移动鱼群中的鱼，选择前往其他成员离当前位置较近的地方
         move_to = None
         for j in range(N):
            if i == j:
                  continue
            if fitness(fishes[j][0]) < fitness(fishes[0]):
                  move_to = j
                  break
         if move_to is None:
            continue

         # 计算运动方向和速度
         curr_pos = fishes[0]
         target_pos = fishes[move_to][0]
         distance = math.sqrt((curr_pos[0]-target_pos[0])**2 + (curr_pos[1]-target_pos[1])**2)
         direction = math.atan2(target_pos[1]-curr_pos[1], target_pos[0]-curr_pos[0])
         speed = min(fishes[2] + delta, visual / 2)
         new_x = curr_pos[0] + speed * math.cos(direction)
         new_y = curr_pos[1] + speed * math.sin(direction)

         # 判断是否超出边界，如果超出则随机走一步
         if abs(new_x) > 50 or abs(new_y) > 50:
            new_x = random.uniform(-50, 50)
            new_y = random.uniform(-50, 50)
            direction = random.uniform(0, 2*math.pi)
            speed = random.uniform(0, visual / 2)

         fishes = [(new_x, new_y), direction, speed]

      # 探索阶段
      for i in range(N):
         # 捕食行为：在当前附近区域内随机移动
         new_direction = random.uniform(0, 2*math.pi)
         new_speed = random.uniform(0, step)
         new_x = fishes[0][0] + new_speed * math.cos(new_direction)
         new_y = fishes[0][1] + new_speed * math.sin(new_direction)

         # 随机行为：在整个搜索空间随机游动
         if random.uniform(0, 1) < 0.5 or abs(new_x) > 50 or abs(new_y) > 50:
            new_x = random.uniform(-50, 50)
            new_y = random.uniform(-50, 50)
            new_direction = random.uniform(0, 2*math.pi)
            new_speed = random.uniform(0, visual / 2)

         fishes = [(new_x, new_y), new_direction, new_speed]

      # 按照适应度大小排序，从中选择最优的N条鱼作为下一轮种群
      fishes.sort(key=lambda x: fitness(x[0]))
      fishes = fishes[:N]

      # 输出本次迭代结果
      print(&#34;Generation {}: Best Fitness {}&#34;.format(iter+1, fitness(fishes[0][0])))

return fishes[0][0]

# 示例运行
result = artificial_fish_swarm(N=50, visual=10, step=2, delta=1, max_iter=100)
print(&#34;Best Solution: &#34;, result)
print(&#34;Best Fitness: &#34;, fitness(result))上述代码实现了一个简单的人工鱼群算法，并用于求解函数的最小值。

		自动登录	找回密码
密码			立即注册