GA

Примечание

При отправке результатов в виде json post-запросом на url в первом задании обьем вещей выл равен 11.9, но это число не подходило под формат целого числа.

Задание 1

Для реализации первого задания используем библиотеку genalg.
Так как набор предметов генерируется случайно, то нам нужно проверять подходит ли данный набор рюкзака под наши параметры веса и обьема. Фитнес функция считается как сумма ценностей каждого предмета, входящего в рюкзак. Eсли особь не подходит под параметры веса и обьема, то возвращаем 0.

def func_to_optimize(item):
    price = 0
    w = 0
    v = 0
    for i in range(0, cnt):
        if item[i] == 1:
            price += items[i][3]
            w += items[i][1]
            v += items[i][2]
    if w > weight_cap or v > voluem_cap:
        price = 0
    return price

Для расчета наилучшего расклада рюкзака задаем фитнес функцию, количество поколей, которые нужны для сходимости, и кол-во особей.

p = genalg.Population(
    popsize=2000,  # количество особей
    nchrom=30,  # количество предметов в рюкзаке 
    chromset=range(0, 2)  # 1-предмет входит в состав рюкзака, 0-нет
)
best = p.run(
    eval_fn=func_to_optimize,  
    fitness_goal=float("Inf"),  # максимизируем стоимость вещей
    generations=400  # количество поколений
)

Задание 2

0. Кодирование –выбор «генетического кода»

Item –битовая последовательность размера n (в данном случае 30)

1.Начальная популяция –кол-во особей всегда = 200:

Жадный выбор, начиная со случайного груза.

Сортируем грузы по их ценности и затем начиная со случайно выбранного груза начинаем по порядку набирать грузы до достижения заданных параметрами ограничений по весу и обьему. Получаем Item, который полностью соответствует требованиям. Таким образом получаем популяцию рюкзаков.

2.Отборособей для скрещивания:

Выбор каждой особи пропорционально приспособленности (рулетка)

Используем отрезок как интерпретацию рулетки, считаем сумму ценности для всех особей. Располагаем особи в порядке убывания весов. Генерируем число в интервале от 0 до суммы всех ценностей, смотрим в какой промежуток попало число, выбираем данную особь и удаляем ее из дальнейшей выборки.

3.Скрещивание (кроссинговер) между выбранными особями.

Каждая особь скрещивается 1 раз за 1 поколение, 1 пара дает 2 потомка:

Mноготочечный с 3мя точками

Генерируем 3 числа, которые будем считать за лини разбиения. Составляем 2 новые особи, которые получаются из двух родительских с помощью многоточечного( с 3мя точками) скрещивания
Например, при таком распределении точек у родительских особей

Получаем потомство такого вида:

4.Мутация:

Инвертирование всех битов у 1 особи

Случайно выбираем 1 особь из новой популяции и инвертируем у нее все биты.

5.Формирование новой популяции

«штраф» за «старость» -20% функции

Для старой популяции (популяция этого поколения) уменьшаем ценность особи на 20% , так как ценность особи храниться вместе с набором предмета, то мы можем снимать штрафы без пересчета

6.Оценка результата

Оцениваем 100 поколений