Расстановка кораблей генетическим алгоритмом

[Семен_13]

Помогите расставить коробли в игре морской бой без пакета deap

 
from deap import base, algorithms
from deap import creator
from deap import tools

import algelitism
from graph_show import show_graph, show_ships

import random
import matplotlib.pyplot as plt
import numpy as np

POLE_SIZE = 7
SHIPS = 10
LENGTH_CHROM = 3*SHIPS    # длина хромосомы, подлежащей оптимизации

# константы генетического алгоритма
POPULATION_SIZE = 200   # количество индивидуумов в популяции
P_CROSSOVER = 0.9       # вероятность скрещивания
P_MUTATION = 0.2        # вероятность мутации индивидуума
MAX_GENERATIONS = 50    # максимальное количество поколений
HALL_OF_FAME_SIZE = 1

hof = tools.HallOfFame(HALL_OF_FAME_SIZE)

RANDOM_SEED = 42
random.seed(RANDOM_SEED)

creator.create("FitnessMin", base.Fitness, weights=(-1.0,))
creator.create("Individual", list, fitness=creator.FitnessMin)

def randomShip(total):
    ships = []
    for n in range(total):
        ships.extend([random.randint(1, POLE_SIZE), random.randint(1, POLE_SIZE), random.randint(0, 1)])

    return creator.Individual(ships)


toolbox = base.Toolbox()
toolbox.register("randomShip", randomShip, SHIPS)
toolbox.register("populationCreator", tools.initRepeat, list, toolbox.randomShip)

population = toolbox.populationCreator(n=POPULATION_SIZE)

def shipsFitness(individual):
    type_ship = [4, 3, 3, 2, 2, 2, 1, 1, 1, 1]

    inf = 1000
    P0 = np.zeros((POLE_SIZE, POLE_SIZE))
    P = np.ones((POLE_SIZE+6, POLE_SIZE+6))*inf
    P[1:POLE_SIZE+1, 1:POLE_SIZE+1] = P0

    th = 0.2
    h = np.ones((3, 6)) * th
    ship_one = np.ones((1, 4))
    v = np.ones((6, 3)) * th

    for *ship, t in zip(*[iter(individual)] * 3, type_ship):
        if ship[-1] == 0:
            sh = np.copy(h[:, :t+2])
            sh[1, 1:t+1] = ship_one[0, :t]
            P[ship[0] - 1:ship[0] + 2, ship[1]-1:ship[1] + t+1] += sh
        else:
            sh = np.copy(v[:t+2, :])
            sh[1:t+1, 1] = ship_one[0, :t]
            P[ship[0]-1:ship[0] + t+1, ship[1] - 1:ship[1] + 2] += sh


    s = np.sum(P[np.bitwise_and(P > 1, P < inf)])
    s += np.sum(P[P > inf+th*4])

    return s,         # кортеж

def mutShips(individual, indpb):
    for i in range(len(individual)):
        if random.random() < indpb:
            individual[i] = random.randint(0, 1) if (i+1) % 3 == 0 else random.randint(1, POLE_SIZE)

    return individual,


toolbox.register("evaluate", shipsFitness)
toolbox.register("select", tools.selTournament, tournsize=3)
toolbox.register("mate", tools.cxTwoPoint)
toolbox.register("mutate", mutShips, indpb=1.0/LENGTH_CHROM)

stats = tools.Statistics(lambda ind: ind.fitness.values)
stats.register("min", np.min)
stats.register("avg", np.mean)


def show(ax):
    ax.clear()
    show_ships(ax, hof.items[0], POLE_SIZE)

    plt.draw()
    plt.gcf().canvas.flush_events()


plt.ion()
fig, ax = plt.subplots()
fig.set_size_inches(6, 6)

ax.set_xlim(-2, POLE_SIZE+3)
ax.set_ylim(-2, POLE_SIZE+3)

population, logbook = algelitism.eaSimpleElitism(population, toolbox,
                                        cxpb=P_CROSSOVER,
                                        mutpb=P_MUTATION,
                                        ngen=MAX_GENERATIONS,
                                        halloffame=hof,
                                        stats=stats,
                                        callback=(show, (ax, )),
                                        verbose=True)

maxFitnessValues, meanFitnessValues = logbook.select("min", "avg")

best = hof.items[0]
print(best)

plt.ioff()
plt.show()

# plt.plot(maxFitnessValues, color='red')
# plt.plot(meanFitnessValues, color='green')
# plt.xlabel('Поколение')
# plt.ylabel('Макс/средняя приспособленность')
# plt.title('Зависимость максимальной и средней приспособленности от поколения')
# plt.show()
#

//////////////////////////////////////////////////////////////algelitism//////////////////////////////////////////////

from deap import tools
from deap.algorithms import varAnd


def eaSimpleElitism(population, toolbox, cxpb, mutpb, ngen, stats=None,
             halloffame=None, verbose=__debug__, callback=None):
    """Перелеланный алгоритм eaSimple с элементом элитизма
    """

    logbook = tools.Logbook()
    logbook.header = ['gen', 'nevals'] + (stats.fields if stats else [])

    # Evaluate the individuals with an invalid fitness
    invalid_ind = [ind for ind in population if not ind.fitness.valid]
    fitnesses = toolbox.map(toolbox.evaluate, invalid_ind)
    for ind, fit in zip(invalid_ind, fitnesses):
        ind.fitness.values = fit

    if halloffame is not None:
        halloffame.update(population)

    hof_size = len(halloffame.items) if halloffame.items else 0

    record = stats.compile(population) if stats else {}
    logbook.record(gen=0, nevals=len(invalid_ind), **record)
    if verbose:
        print(logbook.stream)

    # Begin the generational process
    for gen in range(1, ngen + 1):
        # Select the next generation individuals
        offspring = toolbox.select(population, len(population) - hof_size)

        # Vary the pool of individuals
        offspring = varAnd(offspring, toolbox, cxpb, mutpb)

        # Evaluate the individuals with an invalid fitness
        invalid_ind = [ind for ind in offspring if not ind.fitness.valid]
        fitnesses = toolbox.map(toolbox.evaluate, invalid_ind)
        for ind, fit in zip(invalid_ind, fitnesses):
            ind.fitness.values = fit

        offspring.extend(halloffame.items)

        # Update the hall of fame with the generated individuals
        if halloffame is not None:
            halloffame.update(offspring)

        # Replace the current population by the offspring
        population[:] = offspring

        # Append the current generation statistics to the logbook
        record = stats.compile(population) if stats else {}
        logbook.record(gen=gen, nevals=len(invalid_ind), **record)
        if verbose:
            print(logbook.stream)

        if callback:
            callback[0](*callback[1])

    return population, logbook

[macomics]

Заводишь массив по размеру поля с флагами и в этом массиве закрашиваешь флаги занятых клеток или клеток вокруг корабля. Далее random выбираешь позицию и в этом массиве проверяешь ее. Если все занимаемые кораблем клетки не закрашены, тогда устанавливаешь корабль и обновляешь флаги в этом массиве.