在python中用遗传算法求解传教士和野人渡河问题并且图形化表示

传教士和野人渡河问题是一个经典的人工智能问题，可以使用遗传算法进行求解。下面是一个简单的实现例子：

首先定义遗传算法的参数和目标函数：

import random

POPULATION_SIZE = 50
MUTATION_RATE = 0.1
GENERATIONS = 100
MAX_MOVES = 100

def fitness(chromosome):
    # chromosome is a list of moves
    # each move is a tuple (m, c, b)
    # m is the number of missionaries on the left bank
    # c is the number of cannibals on the left bank
    # b is the position of the boat (0 for left, 1 for right)
    # the goal is to get all missionaries and cannibals to the right bank
    # without ever having more cannibals than missionaries on either bank
    moves = [(3, 3, 0)] + chromosome + [(0, 0, 1)]
    left_bank = (3, 3)
    right_bank = (0, 0)
    for i in range(len(moves) - 1):
        m1, c1, b1 = moves[i]
        m2, c2, b2 = moves[i + 1]
        if b1 == 0:
            left_bank = (left_bank[0] - m1, left_bank[1] - c1)
        else:
            right_bank = (right_bank[0] - m1, right_bank[1] - c1)
        if b2 == 0:
            left_bank = (left_bank[0] + m2, left_bank[1] + c2)
        else:
            right_bank = (right_bank[0] + m2, right_bank[1] + c2)
        if left_bank[0] < 0 or left_bank[1] < 0 or right_bank[0] < 0 or right_bank[1] < 0:
            # illegal move, return low fitness
            return 0
        if left_bank[0] > 0 and left_bank[0] < left_bank[1]:
            # more cannibals than missionaries on left bank, return low fitness
            return 0
        if right_bank[0] > 0 and right_bank[0] < right_bank[1]:
            # more cannibals than missionaries on right bank, return low fitness
            return 0
    # all moves are legal and goal is reached, return high fitness
    return 1

然后定义遗传算法的主要函数：

def crossover(parent1, parent2):
    # single-point crossover
    point = random.randint(1, len(parent1) - 2)
    child1 = parent1[:point] + parent2[point:]
    child2 = parent2[:point] + parent1[point:]
    return child1, child2

def mutate(chromosome):
    # random mutation of a single move
    i = random.randint(1, len(chromosome) - 2)
    m, c, b = chromosome[i]
    if random.random() < 0.5:
        m += random.randint(-1, 1)
    else:
        c += random.randint(-1, 1)
    b = 1 - b
    return chromosome[:i] + [(m, c, b)] + chromosome[i+1:]

def select(population):
    # tournament selection
    tournament = random.sample(population, 3)
    tournament.sort(key=lambda x: fitness(x), reverse=True)
    return tournament[0]

def evolve():
    # initialize population
    population = [[(0, 0, 0)] + [(1, 1, 0)] * (MAX_MOVES // 2) + [(0, 0, 1)] for _ in range(POPULATION_SIZE)]
    for generation in range(GENERATIONS):
        # evaluate fitness of population
        fitnesses = [fitness(chromosome) for chromosome in population]
        best_fitness = max(fitnesses)
        best_chromosome = population[fitnesses.index(best_fitness)]
        print("Generation", generation, "Best fitness", best_fitness)
        # select parents for crossover
        parents = [select(population) for _ in range(POPULATION_SIZE)]
        # create new population through crossover and mutation
        new_population = []
        for i in range(POPULATION_SIZE // 2):
            parent1 = parents[i]
            parent2 = parents[i + POPULATION_SIZE // 2]
            child1, child2 = crossover(parent1, parent2)
            if random.random() < MUTATION_RATE:
                child1 = mutate(child1)
            if random.random() < MUTATION_RATE:
                child2 = mutate(child2)
            new_population.append(child1)
            new_population.append(child2)
        population = new_population
    # return best solution
    return best_chromosome

最后可以将结果可视化，例如：

import matplotlib.pyplot as plt

solution = evolve()
moves = [(3, 3, 0)] + solution + [(0, 0, 1)]
left_bank = [(3, 3)]
right_bank = [(0, 0)]
boat = [0]
for i in range(len(moves) - 1):
    m1, c1, b1 = moves[i]
    m2, c2, b2 = moves[i + 1]
    if b1 == 0:
        left_bank.append((left_bank[-1][0] - m1, left_bank[-1][1] - c1))
    else:
        right_bank.append((right_bank[-1][0] - m1, right_bank[-1][1] - c1))
    if b2 == 0:
        left_bank.append((left_bank[-1][0] + m2, left_bank[-1][1] + c2))
    else:
        right_bank.append((right_bank[-1][0] + m2, right_bank[-1][1] + c2))
    boat.append(b2)
plt.plot([i for i in range(len(left_bank))], [b[0] for b in left_bank], label="Missionaries")
plt.plot([i for i in range(len(left_bank))], [b[1] for b in left_bank], label="Cannibals")
plt.plot([i for i in range(len(right_bank))], [b[0] for b in right_bank], label="Missionaries")
plt.plot([i for i in range(len(right_bank))], [b[1] for b in right_bank], label="Cannibals")
for i in range(len(boat)):
    if boat[i] == 0:
        plt.plot([i, i+1], [0.5, 0.5], color="black")
plt.legend()
plt.show()

这个例子只是一个简单的实现，还有很多改进的空间，例如添加更复杂的变异操作，使用更高级的选择算法等等。