Решаем задачу о ранце. Муравьиный алгоритм или генетический лучше? Давайте разбираться.

 Муравьиный алгоритм — один из общепризнанных в математической среде лидеров по нахождению решения для задачи коммивояжёра (поиска оптимального пути). С другой стороны, существуют другие, более гибкие методы, один из которых — эволюционный. Какой же алгоритм окажется лучше, если столкнуть их в задаче менее свойственной для муравьиного алгоритма — задаче о ранце.

Задача о ранце или knapsack problem — одна из классических задач оптимизации, завязанная на необходимости найти оптимальный набор таких действий, которые позволят максимизировать одни параметры при соблюдении ограничения других. Сложно? Проще на примерах.

Приходя в супермаркет мы чаще всего решаем: «Чего бы такого купить, чтобы можно было целую неделю не кататься через половину города ради шопинга, но при этом не оставить там всей зарплаты?» Или, допустим, вы выбираете, как удачно вложить свои кровно нажитые. Заходите в мобильное приложение любого банка, и глаза разбегаются от предложений вложить деньги. А наши средства к глубокому сожалению не бесконечны. Вы возможно думаете, что ходите за покупками или решаете, куда вложить деньги? Нет, это не так. То есть, конечно, так – обдумываете свой выбор. Но в целом вы решаете одну и ту же задачу — knapsack problem.

Подытожим: у вас есть некоторый набор предметов, которые имеют минимум два условных параметра — вес и ценность. Ранец, в который вы помещаете предметы, имеет ограничение по весу. Необходимо выбрать предметы с максимальной ценностью, которые могут уместиться в рюкзаке.

Чтобы найти оптимальные решения для этой и прочих подобных задач существует достаточное количество разных подходов и алгоритмов. Наиболее простые, но от того не менее интересные — муравьиный и эволюционный алгоритмы.

Первый основан на поведении колонии муравьёв при добыче ими пищи. В паре слов, можно описать идею алгоритма так: каждый обособленный муравей случайным образом двигается от одного источника пищи к другому, оставляя за собой на протяжении всего пути след из феромонов, который влияет на выбор других муравьёв при выборе пути. Таким образом, чем больше феромонов, тем выше вероятность выбора той или иной дороги. Сразу же напрашивается задача поиска пути, в которой муравьиный алгоритм стабильно показывает хорошие результаты, опережая как раз таки эволюционный. Проблема заключается в том, что алгоритм подразумевает под собой нахождение последовательности предметов, хотя на самом деле нам нет разницы в каком порядке складывать предметы в ранец - главное, чтобы сумка выдержала. Поэтому вместо нахождения пути от одного предмета к другому будем смотреть на муравья, как на обычного клиента банка, такого «инвестора», который выбирает, во что ему вложить свои деньги.

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

Хватит с погружением в теорию — перейдём к коду!

Для обоих алгоритмов обратимся к ООП. В муравьином алгоритме будут классы Investment, Ant и AntAlgorithm. Investment — это обёртка для нашего предмета из ранца, в которой будет храниться стоимость инвестиции (или вложение, которое совершит муравей), доход от нашей инвестиции (вес предмета), количество феромона и id.

class Investment:
    def __init__(self, id, cost, profit):
        self._id = id
        self._cost = cost
        self._profit = profit
        self._pheromone = 1.0

Ant — это тот самый муравей, который помнит, сколько он может вложить (вместимость рюкзака), сколько денег он уже вложил, свой доход (суммарная ценность всех выбранных муравьём предметов) и непосредственно сам набор этих предметов (или портфель инвестиций).

мclass Ant:
    def __init__(self, max_cost):
        self._max_cost = max_cost
        self._cost = 0
        self._profit = 0
        self._portfolio = []

И непосредственно сам алгоритм мы реализуем в классе AntAlgorithm.

class AntAlgorithm:
    def __init__(self, count_ants, count_iteration, max_ant_cost, items, evaporation_coefficient):
        self._count_ants = count_ants
        self._count_iteration = count_iteration
        self._max_ant_cost = max_ant_cost
        self._items = items
        self._evaporation_coefficient = evaporation_coefficient

Алгоритму мы будем передавать количество муравьёв и итераций алгоритма, вместимость рюкзака (она же максимальная суммарная стоимость инвестиций муравья), список предметов (веса, ценности и первоначальный id каждого из них) и коэффициент испарения.

«Подождите, что за коэффициент испарения?» - спросите вы. Самое время рассказать об одной из главных проблем при создании методов оптимизации. Если муравей будет ходить длинным путём до еды, то он будет расходовать весь свой феромон на протяжении всего этого длинного пути. От этого его насыщенность будет ниже, чем на более коротком пути до «блюда», из-за чего следующие муравьи с большей вероятностью будут выбирать более короткий путь. В свою очередь феромон не остаётся на дороге постоянно и в течение времени испаряется. И испаряется он тем сильнее, чем продолжительнее путь. Так решается проблема сходимости. Благодаря испарению, алгоритм начинает сходиться к конкретному решению, на котором остаётся феромона в несколько раз больше, чем на других путях.

Но не забываем! Мы уже не муравьи, ищущие дорогу до пищи, мы муравьи-инвесторы, которые выбирают такие вложения, чтобы заработать побольше, а заплатить при этом поменьше! Поэтому выбирать наш алгоритм будет не просто предмет, стоимость которого ниже, но ещё и доход в котором выше, т.е. отношение ценности к весу больше.

Выбирать инвестиции муравей будет по формуле:

После того, как муравей выберет «вклады», он должен оставить феромон на тех, которые он выбрал по формуле:

Казалось бы, так вот и всё решение — просто выбрать предметы с самым высоким отношением дохода к стоимости, соблюдая ограничение рюкзака. Бинго! Но не всё так просто. Часто в ходе поиска лучшего решения задачи, алгоритмы попадают в локальные максимумы — такие решения, которые лучше соседних, но не являются оптимальным для нашего набора данных. Поэтому необходимо не попадать в такие локальные максимумы, либо выходить из них и искать другие решения. Для этого в муравьином алгоритме часто вводят так называемых «элитных муравьёв» — такие наборы, которые позволяют корректировать движение всех остальных муравьёв путём увеличения за свой счёт количества феромонов на определённых путях. Такие муравьи помогают и увеличить сходимость, и не попасть в наиболее очевидные локальные максимумы.

Теперь попробуем реализовать основную функцию в классе алгоритма. Назовём её WolfWallStreet

def WolfWallStreet (self):

В нём создаём список всех вкладов.

inventory = []
i = 0
while (i < len(self._items[0])):
    inventory.append(Investment(self._items[2][i], self._items[0][i], self._items[1][i]))
    i += 1

Инициализируем будущего «элитного муравья» и организуем цикл по количеству итераций алгоритма.

i = 0
best_ant = Ant(self._max_ant_cost)
while (self._count_iteration > i):

Введём переменную sum для той самой суммы

 из формулы и рассчитаем её. Делать это нам нужно каждую итерацию для перерасчёта вероятностей выбора предметов.

sum = 0
j = 0
while (j < len(inventory)):
    sum += (inventory[j].pheromone ** P) * ((inventory[j].profit / inventory[j].cost) ** Q)
    j += 1

И непосредственно рассчитаем вероятности.

j = 1
investment_probability = []
investment_probability.append((inventory[0].pheromone ** P) * ((inventory[0].profit / inventory[0].cost) ** Q) / sum)
while (j < len(inventory)):
    investment_probability.append(
        investment_probability[j - 1] + ((inventory[j].pheromone ** P) * (((inventory[j].profit / inventory[j].cost) ** Q) / sum)))
    j += 1

Теперь поработаем над тем, чтобы наш муравей выбрал свои предметы. Для этого в классе Ant «соберём его портфель».

def BuildPortfolio(self, investment_probability, inventory):
    min_cost_investment = inventory[0].cost # Вклад с минимальой стоимостью
    min_cost_iter = 0 # Итератор вклада с минимальой стоимостью
    investment_availability = [1] * len(inventory) # Список значений наличия вклада
    while ((self._max_cost - self._cost) >= min_cost _investment):
        rand = random.random()# Выбираем случайное число 
        k = 0
        while (k < (len(inventory))):
            if ((investment_probability[k] >= rand) & ((investment_availability[k] == 0) | ((self._max_cost - self._cost) < inventory[k].cost))):
                break # Если вклад мы уже выбирали для этого муравья
            if ((investment_probability[k] >= rand) & (investment_availability[k] == 1) & ((self._max_cost - self._cost) >= inventory[k].cost)): # Нашли блюдо
                investment_availability[k] = 0 # Обнуляем индикатор вклада
                self._portfolio.append(inventory[k]) # Добавляем в «портфель»
                self._cost += inventory[k].cost # Повышаем сумму стоимости
                self._profit += inventory[k].profit # И дохода
                if (k == min_cost _iter): # Если найденный вклад оказалось вкладом с наименьшей стоимостью — ищем следующий доступный вклад
                    investment_availability[min_cost_iter] = 0
                    min_cost_iter = next((j for j, x in enumerate(investment_availability) if x), None)
                    if (min_cost_iter != None):
                        min_cost_investment = inventory[min_cost_iter].cost
                    else:
                        break
                break
            k += 1
    return self

Теперь, когда наши муравьи научились собирать свои инвестиционные портфели, пора запускать колонию на заработки. Возвращаемся в класс AntAlgorithm и набираем популяцию муравьёв; параллельно выбираем из созданных муравьёв того самого элитного.

j = 0
ant_population = []
while (self._count_ants > j):
    ant_population.append(Ant(self._max_ant_cost).BuildPortfolio(investment_probability, inventory))
    if (best_ant.profit < ant_population[j].profit):
        best_ant = ant_population[j]
    j += 1

Муравьи выбрали вклады, элитный муравей выбран, осталось дать обратную связь — оставить феромон. Логика распределения феромона проста: чем больше вклад приносит дохода и чем меньше тратит при этом, тем большую часть феромона оставляем на нём. Также сравниваем количество еды с элитным муравьём, чтобы больше феромона оставалось на тех вкладах, которые были выбраны в лучшем на данный момент решении.

while (self._count_ants > j):
    sum_function = 0 # Переменная для подсчёта суммы отношений выгоды к затратам
    y = 0
    while (y < len(ant_population[j].portfolio)):
        sum_function += ant_population[j].portfolio[y].profit / ant_population[j].portfolio[y].cost
        y += 1
    y = 0
    pheromone_coefficient = ant_population[j].profit / best_ant.profit # Сравниваем выгоду портфеля муравья с выгодой инвестиций элитного
    while (y < len(ant_population[j].portfolio)):
        inventory[ant_population[j].portfolio[y].id].pheromone += pheromone_coefficient / sum_function * (inventory[
            ant_population[j].portfolio[y].id].profit / inventory[ant_population[j].portfolio[y].id].cost) # Добавляем вкладу феромон
        y += 1
    j += 1

Будем использовать элитных муравьёв для увеличения количества феромона на выбранных ими вкладах. Для этого также подсчитываем сумму отношений

j = 0
while (j < len(best_ant.portfolio)):
    sum_function += best_ant.portfolio[j].profit / best_ant.portfolio[j].cost
    j += 1

и добавим феромон.

j = 0
while (j < len(best_ant.portfolio)):
    inventory [best_ant.portfolio[j].id].pheromone += i * sum_function * \
        (inventory [best_ant.portfolio[j].id].profit / inventory[best_ant.portfolio[j].id].cost)
    j += 1

И последний шаг итерации — испарение феромона.

 увеличение происходило в ходе итерации, поэтому осталось только умножить на

j = 0
while (len(inventory) > j):
    inventory[j].pheromone = (1 - self._evaporation_coefficient) * inventory[j].pheromone
    j += 1

Заканчиваем итерацию и возвращаем результат работы алгоритма, которым будет последний полученный элитный муравей.

    i += 1
best_ant.ShowMeYourPortfolio ()
result = [best_ant.cost, best_ant.profit, best_ant. InvestmentsToItems()]
return result

Функции ShowMeYourPortfolio и InvestmentsToItems реализуем в классе Ant для красивого вывода и для преобразования объектов типа Investment обратно в листы.

def ShowMeYourPorttfolio(self):
    portfolio_id = '[ '
    i = 0
    while (len(self._portfolio) > i):
        portfolio_id = portfolio_id + str(self._portfolio[i].id) + ' '
        i += 1
    portfolio_id = portfolio_id + ']'
    print(f'weight = {self._cost } value = {self._profit} {portfolio_id}')
def InvestmentsToItems(self):
    i = 0
    items = []
    while (len(self._portfolio) > i):
        items.append(self._portfolio[i].id)
        i += 1
    return items

И наконец уже можно увидеть результаты наших трудов. В main зададим список для наших параметров веса, ценности и первоначального id. Список сразу отсортируем по возрастанию веса.

items = [[1, 3, 4, 4, 5, 5, 6, 7, 8, 10, 12, 17], # вес
         [6, 2, 4, 10, 5, 17, 13, 9, 7, 16, 25, 33], # ценность
         [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]] # id

и вызовем функцию.

AntAlgorithm(COUNTANTS, COUNTITERATIONFORANTS, MAXWEIGHTKNAPSACK, items, 
EVAPORATIONCOEFFICIENT).WolfWallStreet()

Советую все коэффициенты держать в виде констант.

MAXWEIGHTKNAPSACK = 30
COUNTANTS = 5000
COUNTITERATIONFORANTS = 30
EVAPORATIONCOEFFICIENT = 0.08 

На тестовых данных алгоритм без проблем находит лучший вариант.

weight = 28 value = 71 [ 0 3 5 6 10 ]

Перейдём к бойцу на другом конце ринга — генетическому алгоритму.

Для алгоритма также реализуем 3 класса: EvolutionAlgorithm, Genotype, Gene. Gene это подобие Investment, но без феромона.

class Gene:
    def __init__(self, id,  weight, value):
        self._id = id
        self._weight = weight
        self._value = value

Genotype — это набор этих генов, некоторая особь, которая хранит в себе помимо списка генов, максимальный возможный вес, текущий вес и стоимость.

class Genotype:
    def __init__(self, maxWeight):
        self._genes = []
        self._maxWeight = maxWeight
        self._weight = 0
        self._value = 0

Реализуем сразу и вывод.

def GenesToItems(self):
    i = 0
    items = []
    while (len(self._genes) > i):
        items.append(self._genes[i].id)
        i += 1
    return items

def ShowMeYourGenes(self):
    genesId = '[ '
    i = 0
    while (len(self._genes) > i):
        genesId = genesId + str(self._genes[i].id) + ' '
        i += 1
    genesId = genesId + ']'

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

def Born(self, genes):
    minWeightGenes = genes[0].weight # Gene с минимальным весом
    minWeightIter = 0
    geneAvailability = [1] * len(genes) # Список доступности Gene
    probability = 1/len(genes) # Вероятность выбора Gene
    while ((self._maxWeight - self._weight) >= minWeightGenes):
        i = int(random.random()/probability) # Выбираем случайный Gene
        if ((geneAvailability[i] == 1) & ((self._maxWeight - self._weight) >= genes[i].weight)): # Проверяем его наличие
            geneAvailability[i] = 0 # Обнуляем значение в листе, если ген нам подходит
            self._genes.append(genes[i]) # Добавляем в генотип ген
            self._weight += genes[i].weight # Увеличиваем значение веса
            self._value += genes[i].value # И стоимости
            if (i == minWeightIter): # Если найденный ген – минимальный, выбираем следующий минимальный
                geneAvailability[minWeightIter] = 0
                minWeightIter = next((j for j, x in enumerate(geneAvailability) if x), None)
                if(minWeightIter != None):
                    minWeightGenes = genes[minWeightIter].weight
                else:
                    break
    return self

Переходим к алгоритму. Класс EvolutionAlgorithm содержит в себе информацию о начальной популяции, количестве итераций, коэффициент селекции, коэффициент репродукции, коэффициент мутации, список предметов и максимальной вместимости рюкзака.

class EvolutionAlgorithm:
    def __init__(self, countFirstGeneration, countIteration, countSelection, countReproduction, countMutation, items, maxGenotypeWeight):
        self._countFirstGeneration = countFirstGeneration
        self._countIteration = countIteration
        self._countSelection = countSelection
        self._countReproduction = countReproduction
        self._countMutation = countMutation
        self._items = items
        self._maxGenotypeWeight = maxGenotypeWeight
        self._genes = []

Для начала создадим начальную популяцию.

def TheEvolutionBegins(self):
    self._genes = TransformationGenes(self._items)
    population = []
    while (len(population) < self._countFirstGeneration):
        population.append(Genotype(self._maxGenotypeWeight).Born(self._genes))

Селекция — процесс вымирания наименее приспособленных особей. Приспособленность той или иной особи мы выбираем по value. Чем выше value, тем лучше. Можно придумать достаточно большое количество типов реализации как селекции, так и размножения с мутацией, но в этот раз разберём наиболее простые из реализованных. В селекции остановимся на турнирной — будем случайным образом из популяции выбирать две особи и из них выбирать ту, у которой value выше.

Селекция — процесс вымирания наименее приспособленных особей. Приспособленность той или иной особи мы выбираем по value. Чем выше value, тем лучше. Можно придумать достаточно большое количество типов реализации как селекции, так и размножения с мутацией, но в этот раз разберём наиболее простые из реализованных. В селекции остановимся на турнирной — будем случайным образом из популяции выбирать две особи и из них выбирать ту, у которой value выше.

Каждый вид селекции, размножения и мутации реализуем отдельной функцией в классе EvolutionAlgorithm.

def TournamentSel(self, population, countAlive):
    newPopulation = [] # Пустой list для новой популяции
    genotypeAvailability = [1] * len(population) # Список доступности популяции
    probability = 1/len(population) # Вероятность выбора особи для отбора
    i = 0
    while (i < countAlive):
        first = int(random.random() / probability) # Индекс первого кандидата на выживание
        second = int(random.random() / probability) ) # Индекс второго кандидата на выживание
        if ((first != second)&(genotypeAvailability[first] == 1)&(genotypeAvailability[second] == 1)):
            if (population[first].value >= population[second].value):
                genotypeAvailability[first] = 0
                newPopulation.append(population[first])
            if (population[first].value < population[second].value):
                genotypeAvailability[second] = 0
                newPopulation.append(population[second])
            i += 1
    return newPopulation

После селекции идёт размножение или скрещивание.

parentAvailability = [1] * len(population) ) # Список доступности популяции
countChildren = int(self._countReproduction * len(population) / 2) # Количество новых особей, полученных в ходе репродукции
population = EvolutionAlgorithm.PanmixiaRep(self, population, parentAvailability, countChildren)

Берутся 2 особи и определённым образом образуют новую особь в популяции, в качестве генов для которой выступают только наборы «родителей». В зависимости от задачи можно каким-то конкретным способом как выбирать родителей, так и их гены, но мы выберем наиболее простой — панмиксии (выбор родителя равновероятен).

def PanmixiaRep(self, population, parentAvailability, countChildren):
    i = 0
    parentProbability = [] # Список вероятностей выбора особи для спаривания
    probability = 1 / len(population) # Вероятность
    for i in parentProbability:
        i = probability * (i + 1) # Распределение вероятностей 
    while (i < countChildren):
        firstParent = int(random.random()/probability) # Выбираем первого
        if ((parentAvailability[firstParent] == 1)):
            secondParent = int(random.random() / probability) # Выбираем второго родителей
            if((firstParent != secondParent)): # Оба родителя подходят 
                j = 0
                parentsGenes = [] # Набор генов для будущего «ребёнка»
                while (j < len(population[firstParent].genes)):
                    parentsGenes.append(population[firstParent].genes[j])
                    j += 1 # Добавляем гены первого родителя
                j = 0
                while (j < len(population[secondParent].genes)):
                    parentsGenes.append(population[secondParent].genes[j])
                    j += 1 # Добавляем гены второго родителя
                parentsGenes = list(set(parentsGenes)) # Убираем дубликаты генов
                parentsGenes = SortingGenes(parentsGenes) # Сортируем гены population.append(Genotype(self._maxGenotypeWeight).Born(parentsGenes)) # «Порождаем» новую особь
                i += 1
    return population

Функция для сортировки генов.

def SortingGenes(genes):
    i = 0
    j = 1
    while i < (len(genes)-1):
        mini = i
        while j < (len(genes)):
            if genes[j].weight < genes[mini].weight:
                mini = j
            j+=1
        if mini != i:
            a = genes[i]
            genes[i] = genes[mini]
            genes[mini] = a
        i+=1
        j = i+1
        #print(items)
    return genes

И осталось провести мутацию — создание новых особей каким-то определённым методом. Мутация очень важна для того, чтобы алгоритм очень быстро не сходился к какому-то локальному максимуму за счёт абсолютно новых особей.

countMutant = int(self._countMutation * len(population)) # Новые особи
population = EvolutionAlgorithm.RandomMut(self, population, countMutant)

def RandomMut(self, population, countMutant):
    i = 0
    while (i < countMutant):
        population.append(Genotype(self._maxGenotypeWeight).Born(self._genes))
        i += 1
    return population

И выводим результат. Я выбрал такие коэффициенты, что до конца работы алгоритм оставляет в популяции только одну особь, но в общем случае вывод реализуем так:

while (j < len(population)):
    Genotype.ShowMeYourGenes(population[j])
    j += 1
result = [population[0].weight, population[0].value, population[0].GenesToItems()]
return result

И перейдём к проверке.

MAXWEIGHTKNAPSACK = 30
COUNTFIRSTGENERATION = 100000
COUNTITERATIONFOREVOLUTION = 100
COUNTSELECTION = 0.52
COUNTREPRODUCTION = 0.9
COUNTMUTATION = 0.1

items_result.append(EvolutionAlgorithm(COUNTFIRSTGENERATION, COUNTITERATIONFOREVOLUTION, COUNTSELECTION, COUNTREPRODUCTION,
COUNTMUTATION, items, MAXWEIGHTKNAPSACK).TheEvolutionBegins())

На тестовых данных алгоритм также находит лучший результат! Но при большем наборе данных (50, 100, 500) результаты уже очевидно выглядят лучше у генетической системы, хотя в муравьином алгоритме на наборе в 50 предметов стабильно находится лучший вариант, когда в эволюционном нашёлся только 1 из 25 (у муравьиного 25/25).

С ростом начальных данных (увеличении размера рюкзака, количества предметов, итераций алгоритмов, коэффициентов из генетического) работа алгоритмов замедляется, особенно эволюционного. Так для 50000 предметов, работа обоих алгоритмов достигла 1,5 часов. Страшно представить сколько будет работать алгоритм в реалиях жизни, когда количество возможных предметов переваливает за миллион. Также не стоит забывать, что оба метода не гарантируют нахождение наилучшего решения, а только приближаются к нему.

В общем случае перевес остается на стороне эволюционного алгоритма.

Если спрашивать меня - автора сего проекта - какой же алгоритм лучше и почему, то я поддержу именно генетический. На мой взгляд, он более гибкий и без лишних усложнений даёт достаточно хороший результат за счёт своих инструментов. И все же обе основополагающие идеи алгоритмов будоражат мое сознание ещё со времен обучения в институте. Только задумайтесь: наша природа настолько изобретательна в многообразии своих механизмов устройства, что даже грубые и точные в своём мышлении математики и программисты готовы заимствовать что-то у такой, хаотичной на первый взгляд системы мироздания.

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

Ссылка на гитхаб.