Решение задачи о ранце генетическом алгоритмом

Т.е. дотехпор, покавыполняетсяусловие:k < rateGenerationsLen or (trendEvolution(k) > rateGenerationsCosts and k < maxGenerations)Где trendEvolution – функция, определяющая долю роста популяции за rateGenerationsLen поколений.deftrendEvolution(k):i = (k-1) % rateGenerationsLen return (arrRateGenerations[i] - arrRateGenerations[(i+1) % rateGenerationsLen]) / arrRateGenerations[i]Массив arrRateGenerations – массив, в который заносятся лучшие результаты поколений на протяжении rateGenerationsLen поколений. Это делается в конце итерации обновления популяции следующим образом:arrRateGenerations[k % rateGenerationsLen] = bags[0].costПолный код представлен в приложении А. На рисунке 6 представлен график эволюции качества сумок за 100 поколений.Рисунок 6 – График изменения качества сумок со сменой поколений: - среднее значение ценности сумки в поколении;- лучшее значение ценности сумки в поколении.ЗаключениеВ проделанной работе реализован генетическим алгоритмом метод решения задачи заполнения ранца определенной вместимости таким набором предметов и представленного множества, чтобы его ценность была как можно больше.Данный метод является существенно равномернее сходящимся, чем метод полного перебора, поэтому, в случае, когда не требуется идеального решения, он позволяет находить за заданное время оптимальное решение.Задача о ранце решалась как задача о рюкзаке, в который можно положить не более одного экземпляра каждого предмета. Адаптация решения для задачи о неограниченном рюкзаке. Решение задачи о рюкзаке, у которого есть несколько параметров ограничения по предметам представляется принципиально аналогичным, но, возможно, допускающим добавление каких-либо оптимизаций и упрощений расчётов.В работу не вошел анализ изменения таких параметров алгоритма, как количество потомков, количество особей в отборе и вероятность мутации, на скорость сходимости алгоритма и преодолении им плохих начальных условий (набор особей первого поколения с предметами низкой ценности). Рассмотрение этих параметров достойно отдельной работы.Список использованных источниковБатищев, Д.И Применение генетических алгоритмов к решению задач дискретной оптимизации [Текст] / Д.И. Батищев. – Н.Новгород.:ННГУ, 2007. – 88 с.Визгунов, Н.П. Динамическое программирование в экономических задачах с применением системы MATLAB: учеб. – Н.Новгород.: ННГУ, 2006. – 48 с.Окулов, С. М - Программирование в алгоритмах: [Текст] / С.М. Окулов. – М.: БИНОМ. Лаборатория знаний, 2004. – 341 с.: ил.Окулов, С.М. Информатика в задачах [Текст] / С.М. Окулов, А.А, Пестов, О.А. Пестов. – Киров: Изд-во ВГПУ, 1998. — 343с.Кормен, Т. Алгоритмы: построение и анализ: [Текст] / Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. — Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с.Хаггари, Р. Дискретная математика для программистов: учеб.– М.: Техносфера, 2003. – 320с.Акулич, И.Л Динамическое программирование в примерах и задачах: Учеб.пособие для студентов эконом. спец. вузов [Текст] / И.Л. Акулич. – М.: Высш. шк., 1986. – 319 с., ил.ПриложениеАimport randomimport matplotlib.pyplot as plt#максимальныйвес, переносимыйсумкойmaxWeight = 50#количествослучайныхпредметовitemsCount = 1000#количествосумок в поколенииbagsCount = 50#количестводетей у каждойсумкиchildrenCount = 4#вероятностьмутацииmutationProb = 0.05#количествопоколений, покоторымоцениваетсяинтенсивностьулучшениярезультатаrateGenerationsLen = 10#доля, накоторуюзаоцениваемоеколичествопоколенийдолженулучшитьсялучшийпоказательценностиrateGenerationsCosts = 0.01#предельноеколичествопоколений, наслучай, еслиинтенсивностьростанебудетзатухатьmaxGenerations = 200class Item:def __init__(self, weight, cost, id):self.weight = weightself.cost = cost self.id = id#Генерациянаборавещейсослучайнымиценами и весами (от 0 до 1)bagAllItems = [0] * itemsCountfor i in range(itemsCount): weight = random.random() cost = random.random()bagAllItems[i] = Item(weight, cost, i)ПродолжениеприложенияАclass Bag:def __init__(self, items1, items2=[]):self.maxWeight = maxWeightself.items = []self.weight = 0self.cost = 0parentsItems = items1 + items2 while len(parentsItems) > 0:nextItem = int(random.random() * len(parentsItems)) if not self.itemInBag(parentsItems[nextItem]): if self.weight + parentsItems[nextItem].weight > self.maxWeight: breakself.addItem(parentsItems[nextItem])parentsItems.pop(nextItem)defaddItem(self, item):self.items.append(item)self.weight += item.weightself.cost += item.costdefdelItem(self, item): for i in range(len(self.items)): if self.items[i].id == item.id:self.weight -= self.items[i].weightself.cost -= self.items[i].costself.items.pop(i) return TruedefitemInBag(self, nowItem): for item in self.items: if nowItem.id == item.id: return True return Falsedef mutation(self, items): if len(items) > len(self.items):newItem = int(random.random() * len(items)) while self.itemInBag(items[newItem]):newItem = int(random.random() * len(items)) if not self.itemInBag(items[newItem]):self.addItem(items[newItem]) while self.weight > self.maxWeight:delItem = int(random.random() * len(self.items))self.weight -= self.items[delItem].weightself.cost -= self.items[delItem].costself.items.pop(delItem)ПродолжениеприложенияАdefaverageCost(bags): cost = 0 for bag in bags: cost += bag.cost return cost / len(bags)#оценкадолиросталучшейценностизаrateGenerationsLenпоколенийdeftrendEvolution(k):i = (k-1) % rateGenerationsLen return (arrRateGenerations[i] - arrRateGenerations[(i+1) % rateGenerationsLen]) / arrRateGenerations[i]#созданиеполядляграфикаfig = plt.figure(figsize=(15, 8))ax = fig.add_subplot(1, 1, 1)bags0 = [0] * bagsCountfor i in range(bagsCount): bags0[i] = Bag(bagAllItems)bags = bags0.copy()#Добавлениеточкинаграфиксосредним и максимальнымзначениемценности в первомпоколениисумокax.plot(0, averageCost(bags), c=(0.25, 0.25, 1.00), lw=2, label="Line", zorder=10)bags.sort(reverse=True, key=lambda x: x.cost)ax.plot(0, bags[0].cost, linewidth=5, marker='o', markerfacecolor='red', markeredgecolor='w', label='max')ОкончаниеприложенияА#созданиемассивахраненияисторииэволюциисумокarrRateGenerations = [0]*rateGenerationsLenk = 0#циклэволюцииwhile k < rateGenerationsLen or (trendEvolution(k) > rateGenerationsCosts and k < maxGenerations):newBags = [] for bag1 in bags: for childNum in range(int(childrenCount/2)): bag2 = bags[int(random.random()*len(bags))]newBags.append(Bag(bag1.items, bag2.items)) if mutationProb < random.random():newBags[-1].mutation(bagAllItems) bags += newBagsbags.sort(reverse=True, key=lambda x: x.cost) bags = bags[:bagsCount] print(k, '%.3f' % averageCost(bags), '%.3f' % bags[0].cost)ax.plot(k, averageCost(bags), linewidth=5, marker='o', markerfacecolor='black', markeredgecolor='w', label='average')ax.plot(k, bags[0].cost, linewidth=5, marker='o', markerfacecolor='red', markeredgecolor='w', label='max')arrRateGenerations[k % rateGenerationsLen] = bags[0].cost k += 1plt.show()print(Лучшийнайденныйрезультат:', bags[0].cost, bags[0].weight)