启发式搜索算法python

启发式搜索算法是一种通过探索问题空间中的有希望的区域来寻找解决方案的算法。它通常用于解决那些传统的搜索算法难以解决的问题，例如NP难问题。常见的启发式搜索算法包括遗传算法、蚁群算法、爬山算法和禁忌搜索算法等。

以下是两种启发式搜索算法的Python实现：

1.遗传算法

import random

# 适应度函数
def fitness(individual):
    return sum(individual)

# 个体类
class Individual:
    def __init__(self, chromosome):
        self.chromosome = chromosome
        self.fitness = fitness(chromosome)

    # 交叉操作
    def crossover(self, other):
        pivot = random.randint(0, len(self.chromosome) - 1)
        child1 = self.chromosome[:pivot] + other.chromosome[pivot:]
        child2 = other.chromosome[:pivot] + self.chromosome[pivot:]
        return Individual(child1), Individual(child2)

    # 变异操作
    def mutate(self):
        index = random.randint(0, len(self.chromosome) - 1)
        self.chromosome[index] = 1 - self.chromosome[index]
        self.fitness = fitness(self.chromosome)

# 种群类
class Population:
    def __init__(self, size, chromosome_length):
        self.size = size
        self.individuals = []
        for i in range(size):
            chromosome = [random.randint(0, 1) for j in range(chromosome_length)]
            self.individuals.append(Individual(chromosome))

    # 选择操作
    def selection(self):
        return random.choices(self.individuals, weights=[i.fitness for i in self.individuals], k=2)

    # 进化操作
    def evolve(self):
        new_population = []
        for i in range(self.size):
            parent1, parent2 = self.selection()
            child1, child2 = parent1.crossover(parent2)
            child1.mutate()
            child2.mutate()
            new_population.extend([child1, child2])
        self.individuals = new_population

# 测试
population = Population(10, 5)
for i in range(10):
    print(f"Generation {i}: {[j.chromosome for j in population.individuals]}")
    population.evolve()
print(f"Generation {i+1}: {[j.chromosome for j in population.individuals]}")

2.爬山算法

import random

# 目标函数
def objective_function(x):
    return x ** 2

# 爬山算法
def hill_climbing(start, objective_function, step_size=0.01, max_iter=1000):
    current = start
    for i in range(max_iter):
        left = objective_function(current - step_size)
        right = objective_function(current + step_size)
        if left > objective_function(current) and left > right:
            current -= step_size
        elif right > objective_function(current) and right > left:
            current += step_size
        else:
            break
    return current

# 测试
start = random.uniform(-10, 10)
result = hill_climbing(start, objective_function)
print(f"Start: {start}, Result: {result}")