XIX Международный конкурс научно-исследовательских и творческих работ учащихся

Старт в науке

Генетический алгоритм для решения диофантовых уравнений

• Авторы
• Руководители
• Файлы работы
• Наградные документы

Первушин В.И. 1

---

1МБОУ "Средняя общеобразовательная школа №125 с углублённым изучением математики", г. Снежинск Челябинской области

Первушина Н.А. 1

---

1МБОУ «Средняя общеобразовательная школа № 125 с углубленным изучением математики», г. Снежинск Челябинской области

Работа в формате PDF

1.2 MB

Автор работы награжден дипломом победителя I степени

Диплом школьникаСвидетельство руководителя

ВВЕДЕНИЕ

Приёмы решения уравнений в целых числах (диофантовых уравнений) представляют собой большой раздел алгебры и порой являются очень сложными и неочевидными. Изучить все известные приёмы решения уравнений может и можно, но вероятность появления нового вида уравнения в целых числах, для которого не существует типового приёма решения, очень большая. В 1970 г. русский математике Ю. В. Матиясевич доказал, что общего способа решения у таких уравнений не существует.

Из Internet-источников я узнал, что есть интересный метод математического моделирования, который можно применять для решения уравнений, нахождения экстремумов функций и др. задач – генетический алгоритм (ГА). Автором ГА считается Джордж Холланд, который предложил его модель в начале 70-х г.г. прошлого столетия. ГА имеет типовую структуру, которую можно изменять для обеспечения решения конкретной задачи. Поэтому задача разработки такого алгоритма для решения диофантовых уравнений актуальна.

Гипотеза исследования: генетический алгоритм приводит к решению любого диофантова уравнения, если решение есть.

Цельпроекта: исследование диофантовых уравнений и разработка генетического алгоритма для решения уравнения в рамках практической задачи.

Задачи исследования:

1)  изучить разновидности диофантовых уравнений и подходы к их решению;

2) изучить структуру генетического алгоритма, познакомиться с генетическими операторами;

3) выбрать практическую задачу с решением уравнений в целых числах и разработать для неё генетический алгоритм;

4) выбрать среду программирования;

5) разработать схему и написать программу работы генетического алгоритма;

6) провести тестирование работы программы, сделать выводы, подтвердить или опровергнуть гипотезу исследования.

Объект исследования – диофантовы уравнения. Предмет исследования: генетический алгоритм и его практическая реализация. Методы исследования:изучение литературы и Интернет-ресурсов, извлечение знаний, систематизация информации и анализ.

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

Практическая значимость настоящей работы в том, что разработан генетический алгоритм и создана программа для ПЭВМ для решения транспортной задачи, которую можно доработать и применять для решения других задач в целых числах. Срок работы над проектом – 9 месяцев.

Продукт проекта: программа для ПЭВМ для решения системы диофантовых уравнений на примере транспортной задачи.

ГЛАВА 1 Теоретическое обоснование исследования

Диофантовы уравнения и подходы к их решению

1.1.1 Диофант Александрийский и его уравнения

Диофант – последний из величайших греческих математиков. Его вклад в математику настолько велик, что его иногда называют «отцом алгебры». Краткая справка по данным из [6] приведена в Приложении А.

Однако наиболее известными являются «диофантовы уравнения» – уравнения с произвольным количеством неизвестных, решения которых необходимо искать только в целых числах (в некоторых случаях в рациональных) [7]. Примеры таких уравнений (1.1) и (1.2).

(1.1)

(1.2)

Решения некоторых уравнений часто имеют свои названия. Например, уравнению (1.2) удовлетворяют «пифагоровы тройки», т.к. решения данного уравнения – это стороны прямоугольного треугольника.

Одна из 20 великих математических задач XX века посвящена проблеме диофантовых уравнений.

1.1.2 Разновидности диофантовых уравнений и подходы к их решению

До нас дошли всего 7 книг Диофанта, каждая из которых содержит описание задач, пояснения и их решения. Это уравнения и системы уравнений с 2, 3, 4, 5 и 6-ю неизвестными степени . В более поздних трудах появляются уравнения третьей и более высоких степеней.

Некоторые уравнения с 2-мя и 3-мя неизвестными появились в задачах астрономии при определении периодического повторения небесных явлений. Для уравнения

, где – целые числа, (1.3)

впервые было представлено решение в 625 г. индийским мудрецом Брахмагуптой. Баше де Мезирьяк для решения уравнения (1.3) в 1624 г. применил принцип, сводящийся к последовательному вычислению неполных частных и рассмотрению подходящих дробей. После в 17 и 18 в.в. различные правила решения уравнений типа (1.3) давали Роль, Эйлер, Саундерсон, Лагранж и др. математики [5].

К диофантовым относится и уравнение Пелля (неопределённое уравнение Ферма)

, (1.4)

где – целое положительное число, не являющееся полным квадратом.

Первые упоминания об уравнениях (1.4) найдены в работах у древних греков и индийцев. В общем виде задачу сформулировал французский математик Пьер Ферма, поэтому уравнение (1.4) во Франции называют уравнением Ферма.

В 1630 г. П. Ферма сформулировал гипотезу, которую называют великой теоремой Ферма: «Уравнение для натурального не имеет решений в натуральных числах». Ферма не доказал эту теорему. Позднее в его бумагах было найдено доказательство для . 300 лет математики пытались доказать теорему Ферма. В 1770 г. Эйлер доказал для , в 1825 г. Лежандр и Дирихле для . В общем случае доказать эту теорему не получалось. В 1995 г. Э. Уайлс доказал эту теорему.

Основные методы решения диофантовых уравнений приведены в Приложении Б на конкретных примерах. Уравнений и подходов к их решению множество.

На протяжении многих веков математики пытались отыскать общий способ решения диофантовых уравнений. В 1970 г. русский математик Ю. В. Матиясевич доказал, что такого общего способа быть не может [5].

Генетический алгоритм

1.2.1 Основные понятия генетических алгоритмов

Генетические алгоритмы возникли в результате наблюдения и копирования естественных процессов, происходящих в мире живых организмов: эволюции и естественного отбора популяции живых существ [10]. Идею ГА высказал Дж. Холланд в конце 60-х – начале 70-х г.г.

В ГА применяется ряд терминов из генетики:

Популяция – конечное множество особей.

Особь – хромосомы с закодированными в них множествами параметров задачи.

Хромосома – упорядоченная последовательность генов.

Ген – атомарный элемент генотипа, в частности, хромосомы.

Генотип – набор хромосом данной особи.

Фенотип – набор значений, соответствующих данному генотипу.

Функция пригодности (приспособленности) – мера приспособленности данной особи в популяции (далее по тексту ФП).

Новое поколение – вновь создаваемая популяция особей.

Типовой процесс получения оптимального решения с помощью ГА представлен на рисунке 1.

Оптимальным считается решение, которое по тем или иным качествам лучше других. Генетические операторы – кроссинговер и мутация.

Кроссинговер – оператор «скрещивания» (перемешивания) хромосом.

Мутация – случайная замена одного или нескольких генов в хромосоме.

Рисунок 1 – Схема работы ГА

1.2.2 Пример решения Диофантова уравнения генетическим алгоритмом

Подробный пример решения Диофантова уравнения приведён в [1]. Я решил подобрать своё уравнение и на его примере разобраться, как будет работать ГА. Рассмотрим уравнение из [12], которое было предложено для решения на олимпиаде «Покори Воробьёвы горы!» в 2014 году: решить уравнение

, (1.5)

где – целые числа.

Если решить уравнение (1.5) обычным способом, то можно сгруппировать слагаемые и от суммы перейти к произведению:

Уравнение (1.5) становится эквивалентно уравнению:

(1.6)

Если разложить число 165 на множители, то получим и решение уравнения (1.5) с учётом (1.6) будет следующее:

a = 10, b = 4,c = 2. (1.7)

Чтобы решить уравнение (1.5) с помощью ГА, используем знания о его решении (1.7) и ограничим поиск решения с помощью условия:

(1.8)

1 шаг. Выберем 5 случайных решений (хромосом) в рамках условия (1.8) с помощью генератора случайных чисел [7].

Таблица 1 – Первое поколение хромосом

2 шаг. Подставим каждое решение из табл. 1 в уравнение (1.5) и вычислим расстояние от найденного решения до нужного – 164 и определим коэффициент выживаемости.

Таблица 2 – Коэффициенты выживаемости первого поколения хромосом

Если найдётся значение ФП Δ равное нулю, т.е. решение найдено. ГА заканчивает работу. Соответствующая хромосома и есть решение.

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

3 шаг. Вычисление вероятности оказаться родителем.

Таблица 3 – Проценты выживаемости

\

4 шаг. Выбор родителей для новой популяции.

Для выбора пяти пар родителей, каждая из которых будет иметь 1 потомка, т.е. появится всего 5 новых решений, выполним следующее. Полученные в таблице 3 проценты выживаемости умножим на 10. Представим, что у нас 1000-сторонняя игральная кость: 112 сторон – хромосома 1, 141 сторона – хромосома 2, 27 сторон – хромосома 3, 270 сторон – хромосома 4, 450 сторон – хромосома 5. Для выбора первой пары хромосом «кидаем» игральную кость 2 раза. Имитацию броска можно сделать также с помощью генератора случайных чисел [3] в диапазоне от 1 до 1000: от 1 до 112 – хромосома 1,от 113 до 253 – хромосома 2, от 254 до 280 – хромосома 3, от 281 до 550 – хромосома 4, от 551 до 1000 – хромосома 5.

Аналогично выбираем остальные пары родителей. Результат выбора приведен в табл. 4.

Таблица 4 – Результат выбора родителей

5 шаг. Создание нового поколения

Хромосомы родителей «смешаем» с помощью кроссинговера. Результат приведён в табл. 5.

Таблица 5 – Кроссинговер хромосом родителей

6 шаг. Повторяем шаг 2 для хромосом-потомков из табл. 5.

Таблица 6 – Коэффициенты выживаемости второго поколения хромосом

Значение ФП Δ равно нулю для хромосомы (2, 10, 4), т.е. решение уравнения (1.5) найдено. ГА заканчивает работу.

Практическая задача с решением в целых числах

Транспортная задача (ТЗ) относится к перечню классических задач, решаемых в практике деятельности людей. Эта задача методами классической математики не решается [11]. Для её решения разработаны специальные методы: метод опорного плана и метод потенциалов. Поскольку перевозки – это целые числа (вагоны, ящики, кг и др.), то можно попробовать её решить с помощью ГА.

Имеется m пунктов отправления (ПО): А₁, А₂, …, А_m, в которых сосредоточены запасы однородного груза в размерах а₁, а₂, …, а_m соответственно. Имеется n пунктов назначения (ПН): В₁, В₂, …, В_n, которые подали заявки на b₁, b₂, …, b_n единиц груза соответственно.

Полагается, что сумма запасов равна сумме заявок:

(1.9)

Если же условие (1.9) не выполняется, то для решения вводят фиктивный ПО или ПН с разницей в запасах или заявках соотвественно.

Известна стоимость перевозки единицы груза c_ij из i-го ПО в j-ый ПН. стоимости каждой возможной перевозки сводятся в матрицу стоимостей:

(1.10)

Требуется составить такой план перевозок, при котором все заявки были бы выполнены, а общая стоимость всех перевозок должна быть минимальной. Так как критерий эффективности в данной задачи – стоимость, то такая задача носит название – транспортная задача по критерию стоимости.

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

1) Суммарное количество груза, направляемое из каждого ПО во все ПН, должно быть равно запасу груза в данном ПО. Это даёт т условий-равенств:

(1.11)

2) Суммарное количество груза, доставляемое в каждый ПН изо всех ПО, должно быть равно заявке, поданной данным ПО. Это даст п условий-равенств:

(1.12)

3) Суммарная стоимость всех перевозок должна быть минимальной:

(1.13)

Уравнения (1.11) и (1.12) в целых числах, т.е. Диофантовы.

Условия ТЗ (1.9) – (1.12) удобно представлять в виде транспортной таблицы В.1 Приложения В.

ГЛАВА 2 Практические результаты исследования

2.1 Разработка программы реализации ГА

2.1.1 Выбор языка программирования

Для разработки ГА я решил воспользоваться языком программирования Python («Питон»), который мы изучаем на уроках информатики в школе. Python – высокоуровневый язык программирования, отличающийся эффективностью, простотой и универсальностью использования [13]. Язык Python создан похожим по своему синтаксису на естественные языки (прежде всего английский). Блоки кода в нем отделяются друг от друга пробельными отступами. Это делает код, написанный на Python, более читаемым и понятным для программистов.

2.1.2 Разработка схемы программы

Для составления схемы решения ТЗ с помощью ГА ограничимся n = 2 и m = 3, т.е. двумя ПО и тремя ПН соответственно. Элементов решения (перевозок x_ij) будет 6. Запасы ПО: а₁, а₂. Заявки ПН: b₁, b₂, b₃. Условие баланса (1.9) выполняется:

Матрица стоимостей имеет вид:

.

На основе данного условия ТЗ мною была разработана схема программы на основе ГОСТ [4].

Cхема программы представлена в Приложении Г.

2.1.3 Разработка программы

Для создания программы на Python по рекомендации консультанта мне потребовалось изучить некоторые его конструкции, которые удобно будет применить для создания генетического алгоритма.

«Класс» — это логическая группа функций и данных [9]. Классы Python определяются ключевыми словами «class». Внутри классов можно определить функции или методы, которые являются частью класса. Все в классе имеет отступ, как и код в функции, цикле, операторе if и т. д. Конструктор Python – это функция класса, которая создаёт объект с переопределёнными значениями. Он начинается с двойного подчёркивания. Это метод __init__(…). Пример создания класса User приведён на рисунке 2.

Рисунок 2 – Пример создания класса в Python.

Аргумент «self» относится к самому объекту. Отсюда и использование слова «self». «Self» будет ссылаться на конкретный экземпляр этого объекта, с которым работает.

@classmethod – это обычный метод класса, имеющий доступ ко всем атрибутам класса, через который он был вызван. Следовательно, classmethod – это метод, который привязан к классу, а не к экземпляру класса [8].

В программе мне потребовалось @classmethod использовать для создания методов класса, и cls должен быть первым аргументом каждого метода класса. Пример использования @classmethod приведён на рисунке 3.

Рисунок 3 – Пример использования @classmethod в Python.

Для реализации ГА на языке Python оказалось удобно использовать функцию map(lambda «аргументы»: «условие», «перечисляемые элементы»). Например:

map(lambda x : x*2, [1, 2, 3, 4]) #Вернет [2, 4, 6, 8].

В задаче проекта «перечисляемые элементы» – это хромосомы из элементов решения (значений перевозок).

Функция chain() модуля itertools используется для обработки нескольких последовательностей как единой целой без программного объединения этих последовательностей. Эта функция нужна для соединения перевозок из строк таблицы в одну цепочку. Например:

>>>fromitertoolsimportchain

>>>it1=range(1,6)

>>>it2=range(10,16)

>>>rez=chain(it1,it2)

>>> list(rez)

# [1, 2, 3, 4, 5, 10, 11, 12, 13, 14, 15]

Модуль operator предоставляет функцию для каждого встроенного оператора Python [2]. Для программирования ГА удобно оказалось использовать operator.mul (умножение).

Программу на языке Python для реализации ГА непростая, но с помощью применения описанных функций и классов мне удалось написать её с помощью примеров применения из Internet и при помощи констультанта.

Текст программы представлен в Приложении Д.

2.2 Проверка работоспособности программы на тестовых примерах

Для примера покажем работоспособность программы при решении ТЗ небольшой размерности.

1) Проверка работоспособности программы на тестовом примере №1: с 2-мя ПО и 3-мя ПН.

Запасы ПО: а₁ = 35, а₂ = 10. Заявки ПН: b₁ = 25, b₂ = 5, b₃ = 15. Условие баланса выполняется:

.

Пусть матрица стоимостей имеет вид:

.

Условие задачи приведено в транспортной таблице В.2 Приложения В.

Разработанный ГА должен подобрать лучшую хромосому ( , , , , , ) – план перевозок, чтобы стоимость перевозок (1.13) была минимальна. Количество шагов до оптимального решения зададим 100.

Результат работы программы приведён в Приложении Е.

Данный результат оказался необычным, т.к. ГА найдено 100 подходящих хромосом, т.е. 100 планов перевозок с одинаковой стоимостью L = 85. В качестве решения выдаётся последняя их подходящих хромосом

Лучшеерешение: Chromosome(gen=[22, 2, 11, 3, 3, 4] fitness=0 L=85.

План перевозок такой: = 22, = 2, = 11, = 3, = 3, = 4.

Я обратил внимание, что среди найденных решений имеются, например, такие:

48: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85.

Перевозки в два направления равны нулю: = = 0. Такой план перевозок лучше предыдущего с точки зрения оптимизации числа направлений перевозки.

В текст программы я добавил ещё одно условие при выборе лучшего решения:

sum(map(lambda x: x == 0, h.gen)) > sum(map(lambda x: x == 0, best.gen)).

Если переменная из списка равна 0, то мы её отмечаем логической 1, а потом складываем число единиц. Чем оно больше, тем хромосома лучше.

Результат работы программы с уточнением условия приведён в приложении 5.

…

02: best: Chromosome(gen=[18, 5, 12, 7, 0, 3] fitness=0 L=85
03: best: Chromosome(gen=[18, 5, 12, 7, 0, 3] fitness=0 L=85
04: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
…

Уже на первом шаге найдено лучшее решение с одной нулевой перевозкой, а на 4-м шаге с двумя нулевыми перевозками и лучше решение ГА найти не удалось. Оно есть оптимальное.

2) Проверка работоспособности программы сначала я проверил на тестовом примере №2: с 3-мя ПО и 3-мя ПН.

Запасы ПО: а₁ = 35, а₂ = 10, а₃ = 10. Заявки ПН: b₁ = 25, b₂ = 15, b₃ = 15. Условие баланса выполняется:

.

Пусть матрица стоимостей имеет вид:

.

Условие задачи приведено в транспортной таблице В.3 Приложения В.

Результат работы программы приведён в Приложении Е.

Это пример оказался интереснее с точки зрения поиска лучшего решения:

…

02: best: Chromosome(gen=[13, 7, 15, 9, 1, 0, 3, 7, 0] fitness=0 L=152
…
14: best: Chromosome(gen=[16, 4, 15, 1, 9, 0, 8, 2, 0] fitness=0 L=147

…
32: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145

Оптимальное решение имеет минимальную стоимость перевозок и максимальное количество нулевых перевозок.

Лучшеерешение: Chromosome(gen=[7, 13, 15, 8, 2, 0, 10, 0, 0] fitness=0 L=145

Приведённые примеры ТЗ показывают работоспособность ГА в поиске решения.

Тестирование программы было также проведено для ТЗ большей размерности (до 5 ПО и 5 ПН). Если раньше лучшее решение удавалось найти за 100 шагов, и увеличение количества шагов решения до 1000 не приводило к лучшему результату, то для этой задачи потребовалось увеличить поиск до 1000 шагов, чтобы найти решение.

Работоспособность программы подтверждена.

ЗАКЛЮЧЕНИЕ

В ходе выполнения исследовательского проекта удалось познакомиться с диофантовыми уравнениями (в целых числах), а также с генетическими алгоритмами: разобраться с их основными элементами и описанием. Методов решения диофантовых уравнений множество и каждый из методов не является универсальным, а позволяет решить только определённый тип уравнений. Я в этом убедился, изучая способы решения. При изучении генетического алгоритма мне стало понятно, что именно он позволит решить любое диофантово уравнение, если, конечно, у него есть решение. Если решения нет, то ГА будет пытаться его найти бесконечно.

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

Изучив генетический алгоритм и условие транспортной задачи, я составил схему для написания программы на ПЭВМ. В качестве языка программирования я выбрал Pythton, который изучаю в школе. За дополнительными знаниями я обратился к консультанту и сети Internet.

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

Все поставленные задачи выполнены, цель исследования достигнута.

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

Полученный продукт проекта – программу для ПЭВМ, можно использовать для решения ТЗ, а также адаптировать её под другой вид задач.

СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ И ЛИТЕРАТУРЫ

1 Введение в ГА и Генетическое Программирование. [Электронный ресурс]. – Режим доступа: http://algolist.ru/ai/ga/intro.php

2 Введение в модуль operator в Python. [Электронный ресурс]. – Режим доступа: https://docs-python.ru/standart-library/modul-operator-python/vvedenie-modul-operator/

3 Генератор случайных чисел. [Электронный ресурс]. – Режим доступа: http://castlots.org/generator-sluchajnyh-chisel/

4 ГОСТ 19.701-90 (ИСО 5807-85) Единая система программной документации. Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения. Дата введения 01.01.92. [Электронный ресурс]. – Режим доступа: https://base.garant.ru/5369717/

5 Гринько Е. П., Головач А. Г. Методы решения диофантовых уравнений при подготовке школьников к олимпиадам. Учебно-методическое пособие. [Электронный ресурс]. – Режим доступа: https://lib.brsu.by/sites/default/files/books/ГринькоГоловачМетоды решения диофантовых уравнений при подготовке школьников к олимпиадам.pdf

6 Диофант. [Электронный ресурс]. – Режим доступа: http://www.univer.omsk.su/omsk/Edu/Math/ddiofant.htm

7 Диофантовы пятерки, ускользающие от математиков почти 2000 лет. [Электронный ресурс]. – Режим доступа: https://dzen.ru/media/mathematic/diofantovy-piaterki-uskolzaiuscie-ot-matematikov-pochti-2000-let-60a79dd170bb2023e79ffb4a

8 Объяснение @classmethod и @staticmethod в Python. [Электронный ресурс]. – Режим доступа: https://webdevblog.ru/obyasnenie-classmethod-i-staticmethod-v-python/

9 ООП в Python: класс, объект, наследование и конструктор с примерами. [Электронный ресурс]. – Режим доступа: https://webformyself.com/oop-v-python-klass-obekt/

10 Рутковская Д., Пилиньский М., Рутковский Л. Нейронные сети, генетические алгоритмы и нечёткие системы: Пер. с польск. И. Д. Рудинского. – М.: Горячая линия – Телеком, 2004. – 452 с.: ил.

11 Транспортная задача линейного программирования. [Электронный ресурс]. – Режим доступа: https://habr.com/ru/post/573224/

12 Яковлев И.В. Материалы по математике. Уравнения в целых числах. [Электронный ресурс]. – Режим доступа: https://mathus.ru/math/ez.pdf.

13 Python. [Электронный ресурс]. – Режим доступа: https://blog.skillfactory.ru/glossary/python/

Приложение А

Диофант Александрийский

Диофант (вероятно, III в.) – древнегреческий математик из Александрии. О его жизни нет почти никаких сведений. Сохранилась часть математического трактата Диофанта «Арифметика» (6 кн. из 13) и отрывки книги о многоугольных (фигурных) числах. В «Арифметике», помимо изложения начал алгебры, приведено много задач, сводящихся к неопределенным уравнениям различных степеней, и указаны методы нахождения решений таких уравнений в рациональных положительных числах; здесь же впервые появляется терминология многомерной геометрии. Изложение Диофанта чисто аналитическое. Для обозначения неизвестного и его степеней, обратных чисел, равенства и вычитания Диофант употреблял сокращенную запись слов. При умножении сумм и разностей двух чисел применял правила знаков. Имел представление об отрицательных числах, например, знал, что квадрат отрицательного числа равен положительному числу. Сочинения Диофанта были отправной точкой для теоретико-числовых исследований П. Ферма, Л. Эйлера , К. Гаусса и других математиков. Именем Диофанта названы два больших раздела теории чисел – теория диофантовых уравнений и теория диофантовых приближений.

Приложение Б

Типы диофантовых уравнений

Приложение В

Транспортные таблицы

Таблица В.1 – Транспортная таблица

ПН ПО	В1	В2	…	Вn	Запасы
А1			…		а1
А2			…		а2
…	…	…	…	…	…
Аm			…		аm
Заявки	b1	b2	…	bn

Таблица В.2 – Транспортная таблица для тестового примера №1

ПН ПО	В1	В2	Вn	Запасы
А1	1	4	2	35
А2	2	5	3	10
Заявки	25	5	15	45

Таблица В.3 – Транспортная таблица для тестового примера №2

ПН ПО	В1	В2	Вn	Запасы
А1	1	4	2	35
А2	2	5	3	10
А2	3	7	9	10
Заявки	25	15	15	55

Приложение Г

Схема программы реализации ГА для решения транспортной задачи

Начало

Задние условий ТЗ:

кол-во запасов, заявок и стоимости перевозок, N – кол-во шагов до решения

a₁, a₂, b₁, b₂, b₃,

C, N

Начальные данные переменных и массивов

L₀= 10⁶ – начальное значение целевой функции (стоимости перевозок),

n = 0.

Вычисляется подходящесть каждой из 4-х хромосом условиям (1.11) – 1, 2 и (1.12) – 3, 4, 5. Отличия по модулю – Z_ij. Сумма отличий по всем условиям – Δ_i

while 1

n < N

Случайным образом генерируются 4 хромосомы

H₁, H₂, H₃, H₄ из 6-ти генов по числу неизвестных:

(x₁₁, x₁₂, x₁₃, x₂₁, x₂₂, x₂₃)

while 2

k ≤ 4

Генерация хромосом при:

x_ij ≤ min{a_i, b_j}

while 2

да

Δ_i= 0

нет

А

В

D

А

В

D

Определяется степень пригодности каждой из 4-х хромосом, чтобы стать родителем.

Вычисление процента выживаемости

Имитация рулетки

Мать:

(d₁, d₂, d₃, d₄, d₅, d₆)

Отец:

(t₁, t₂, t₃, t₄, t₅, t₆)

Выбор для потомства 2-х наиболее пригодных хромосом

Кроссинговер

1: (d₁| t₂, t₃, t₄, t₅, t₆)

2: (d₁, d₂| t₃, t₄, t₅, t₆)

3: (d₁, d₂, d₃| t₄, t₅, t₆)

4: (d₁, d₂, d₃, d₄| t₅, t₆)

5: (d₁, d₂, d₃, d₄, d₅| t₆)

6: (t₁| d₂, d₃, d₄, d₅, d₆)

7: (t₁, t₂| d₃, d₄, d₅, d₆)

8: (t₁, t₂, t₃| d₄, d₅, d₆)

9: (t₁, t₂, t₃, t₄| d₅, d₆)

10: (t₁, t₂, t₃, t₄, t₅| d₆)

Генерация 10-ти хромосом- потомков от «матери» и «отца»

Вычисляется подходящесть каждой из 10-ти хромосом условиям (1.11) – 1, 2 и (1.12) – 3, 4, 5. Отличия по модулю – Z_ij. Сумма отличий по всем условиям – Δ_i

А

В

С

D

А

В

С

D

да

Δ_i= 0

нет

Имитация рулетки

Мать:

(d₁, d₂, d₃, d₄, d₅, d₆)

Отец:

(t₁, t₂, t₃, t₄, t₅, t₆)

Выбор для мутации 2-х наиболее пригодных хромосом

Мутация

Мать:

(f₁, f₂, F, f₄, f₅, f₆)

Отец:

(h₁, h₂, h₃, h₄, h₅, H)

Случайная замена в каждой из хромосом одного гена на значение из соответствующего гену интервала x_ij ≤ min{a_i, b_j}

Вычисление процента выживаемости

Определяется степень пригодности каждой из 2-х хромосом после мутации

Δ_i= 0

да

нет

D

В

В

D

Решение в соответствии с ограничениями (1.11) и (1.12) найдено:

(x₁₁, x₁₂, x₁₃, x₂₁, x₂₂, x₂₃)

Вычисляется стоимость перевозок (1.13):

Проверяется условие уменьшения стоимости перевозок

L ≤ L₀

нет

да

L₀ = L

n = n + 1

Запоминается выбранная хромосома с минимальной стоимостью перевозок

H_лучш= H

while 1

Конец

Приложение Д

Текст программы реализации ГА для решения транспортной задачи

import data

import random

from typing import Iterable, List

from heapq import nlargest

from itertools import chain

import operator

class Chromosome:

rows = len(data.C)

cols = len(data.C[0])

def __init__(self, gen: List[int]):

self.gen = gen

@classmethod

def random(cls):

h = list()

for i in range(cls.rows):

for j in range(cls.cols):

h.append(random.randint(0, min(data.A[i], data.B[j])))

return cls(h)

def mutate(self):

idx=random.randint(0, len(self.gen) - 1)

tmp = Chromosome.random()

self.gen[idx] = tmp.gen[idx]

def fitness(self):

z = list()

for a_i, x_i in zip(data.A, zip(*[iter(self.gen)]*self.cols)):

z.append(abs(a_i - sum(x_i)))

for j in range(self.cols):

x_j = sum(self.gen[j::self.cols])

z.append(abs(data.B[j] - x_j))

return sum(z)

def price(self):

return sum(map(operator.mul, self.gen, chain(*data.C)))

def __repr__(self):

return "%s(gen=%s fitness=%r L=%r" %(self.__class__.__name__,

self.gen,

self.fitness(),

self.price() if self.fitness() == 0 else None)

def __lt__(self, other):

return self.fitness() < other.fitness()

def __eq__(self, other):

return self.gen == other.gen

def roulette(chromosomes: Iterable):

x = zip(ranking(chromosomes),chromosomes)

return list(h for rank, h in nlargest(2,x))

def ranking(chromosomes: Iterable[Chromosome]):

fitness = tuple(map(lambda h: 1.0/h.fitness() if h.fitness() else 1.0 , chromosomes))

s = sum(fitness)

return tuple(100.0*(x/s) for x in fitness)

def crossing_over(a: Chromosome, b: Chromosome):

for i in range(1, len(a.gen)):

yield Chromosome(a.gen[0:i] + b.gen[i:])

yield Chromosome(b.gen[0:i] + a.gen[i:])

def update_best(chromosomes: Iterable[Chromosome]):

global best

updated = False

for h in suggestions(chromosomes):

if not best or best.price() > h.price() or (best.price() == h.price()) and sum(map(lambda x: x == 0, h.gen)) > sum(map(lambda x: x == 0, best.gen)):

best = h

updated = True

return updated

def suggestions(chromosomes: Iterable[Chromosome]):

return tuple(filter(lambda h: h.fitness() == 0, chromosomes))

def generation(parents: Iterable[Chromosome]):

childrens = list(crossing_over(*parents))

if update_best(childrens):

return None

a, b = roulette(childrens)

a.mutate()

b.mutate()

if update_best([a, b]):

return None

else:

return a, b

best = None

def main():

N=100

global best

for n in range(1, N+1):

print("%02d: best: %s" % (n, best))

chromosomes = list(Chromosome.random() for _ in range(4))

if not update_best(chromosomes):

chromosomes = roulette(chromosomes)

i = 1

while chromosomes:

if i > 1000:

break

i += 1

chromosomes = generation(chromosomes)

print("Лучшеерешение:", best)

if __name__ == '__main__':

main()

Текст программы data.py со входными данными

для решения транспортной задачи

1 Тестовый пример задачи с 2-мя ПО и 3-мя ПН

A=[35, 10]

B=[25, 5, 15]

C=[

[1, 4, 2],

[2, 5, 3]

]

2 Тестовый пример задачи с 3-мя ПО и 3-мя ПН

A=[35, 10, 10]

B=[25, 15, 15]

C=[

[1, 4, 2],

[2, 5, 3],

[3, 7, 9]

]

Приложение Е

Результат работы программы для тестового примера №1

01: best: None
02: best: Chromosome(gen=[23, 4, 8, 2, 1, 7] fitness=0 L=85
03: best: Chromosome(gen=[23, 3, 9, 2, 2, 6] fitness=0 L=85
04: best: Chromosome(gen=[22, 5, 8, 3, 0, 7] fitness=0 L=85
05: best: Chromosome(gen=[17, 4, 14, 8, 1, 1] fitness=0 L=85
06: best: Chromosome(gen=[18, 4, 13, 7, 1, 2] fitness=0 L=85
07: best: Chromosome(gen=[17, 4, 14, 8, 1, 1] fitness=0 L=85
08: best: Chromosome(gen=[20, 3, 12, 5, 2, 3] fitness=0 L=85
09: best: Chromosome(gen=[24, 1, 10, 1, 4, 5] fitness=0 L=85
10: best: Chromosome(gen=[18, 4, 13, 7, 1, 2] fitness=0 L=85
11: best: Chromosome(gen=[23, 3, 9, 2, 2, 6] fitness=0 L=85
12: best: Chromosome(gen=[23, 3, 9, 2, 2, 6] fitness=0 L=85
13: best: Chromosome(gen=[20, 1, 14, 5, 4, 1] fitness=0 L=85
14: best: Chromosome(gen=[19, 1, 15, 6, 4, 0] fitness=0 L=85
15: best: Chromosome(gen=[21, 3, 11, 4, 2, 4] fitness=0 L=85
16: best: Chromosome(gen=[19, 3, 13, 6, 2, 2] fitness=0 L=85
17: best: Chromosome(gen=[18, 3, 14, 7, 2, 1] fitness=0 L=85
18: best: Chromosome(gen=[19, 4, 12, 6, 1, 3] fitness=0 L=85
19: best: Chromosome(gen=[16, 5, 14, 9, 0, 1] fitness=0 L=85
20: best: Chromosome(gen=[19, 5, 11, 6, 0, 4] fitness=0 L=85
21: best: Chromosome(gen=[17, 5, 13, 8, 0, 2] fitness=0 L=85
22: best: Chromosome(gen=[23, 3, 9, 2, 2, 6] fitness=0 L=85
23: best: Chromosome(gen=[20, 5, 10, 5, 0, 5] fitness=0 L=85
24: best: Chromosome(gen=[18, 5, 12, 7, 0, 3] fitness=0 L=85
25: best: Chromosome(gen=[21, 3, 11, 4, 2, 4] fitness=0 L=85
26: best: Chromosome(gen=[16, 4, 15, 9, 1, 0] fitness=0 L=85
27: best: Chromosome(gen=[20, 3, 12, 5, 2, 3] fitness=0 L=85
28: best: Chromosome(gen=[21, 1, 13, 4, 4, 2] fitness=0 L=85
29: best: Chromosome(gen=[21, 4, 10, 4, 1, 5] fitness=0 L=85
30: best: Chromosome(gen=[23, 2, 10, 2, 3, 5] fitness=0 L=85
31: best: Chromosome(gen=[20, 3, 12, 5, 2, 3] fitness=0 L=85
32: best: Chromosome(gen=[18, 4, 13, 7, 1, 2] fitness=0 L=85
33: best: Chromosome(gen=[22, 3, 10, 3, 2, 5] fitness=0 L=85
34: best: Chromosome(gen=[17, 5, 13, 8, 0, 2] fitness=0 L=85
35: best: Chromosome(gen=[18, 3, 14, 7, 2, 1] fitness=0 L=85
36: best: Chromosome(gen=[19, 3, 13, 6, 2, 2] fitness=0 L=85
37: best: Chromosome(gen=[23, 2, 10, 2, 3, 5] fitness=0 L=85
38: best: Chromosome(gen=[20, 3, 12, 5, 2, 3] fitness=0 L=85
39: best: Chromosome(gen=[22, 2, 11, 3, 3, 4] fitness=0 L=85
40: best: Chromosome(gen=[23, 2, 10, 2, 3, 5] fitness=0 L=85
41: best: Chromosome(gen=[18, 5, 12, 7, 0, 3] fitness=0 L=85
42: best: Chromosome(gen=[18, 5, 12, 7, 0, 3] fitness=0 L=85
43: best: Chromosome(gen=[22, 1, 12, 3, 4, 3] fitness=0 L=85
44: best: Chromosome(gen=[25, 1, 9, 0, 4, 6] fitness=0 L=85
45: best: Chromosome(gen=[20, 0, 15, 5, 5, 0] fitness=0 L=85
46: best: Chromosome(gen=[19, 2, 14, 6, 3, 1] fitness=0 L=85
47: best: Chromosome(gen=[22, 1, 12, 3, 4, 3] fitness=0 L=85
48: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
49: best: Chromosome(gen=[18, 4, 13, 7, 1, 2] fitness=0 L=85
50: best: Chromosome(gen=[19, 1, 15, 6, 4, 0] fitness=0 L=85
51: best: Chromosome(gen=[18, 5, 12, 7, 0, 3] fitness=0 L=85
52: best: Chromosome(gen=[22, 0, 13, 3, 5, 2] fitness=0 L=85
53: best: Chromosome(gen=[22, 3, 10, 3, 2, 5] fitness=0 L=85
54: best: Chromosome(gen=[24, 2, 9, 1, 3, 6] fitness=0 L=85
55: best: Chromosome(gen=[18, 5, 12, 7, 0, 3] fitness=0 L=85
56: best: Chromosome(gen=[20, 5, 10, 5, 0, 5] fitness=0 L=85
57: best: Chromosome(gen=[24, 3, 8, 1, 2, 7] fitness=0 L=85
58: best: Chromosome(gen=[22, 4, 9, 3, 1, 6] fitness=0 L=85
59: best: Chromosome(gen=[23, 2, 10, 2, 3, 5] fitness=0 L=85
60: best: Chromosome(gen=[17, 3, 15, 8, 2, 0] fitness=0 L=85
61: best: Chromosome(gen=[21, 1, 13, 4, 4, 2] fitness=0 L=85
62: best: Chromosome(gen=[20, 5, 10, 5, 0, 5] fitness=0 L=85
63: best: Chromosome(gen=[18, 5, 12, 7, 0, 3] fitness=0 L=85
64: best: Chromosome(gen=[18, 3, 14, 7, 2, 1] fitness=0 L=85
65: best: Chromosome(gen=[16, 4, 15, 9, 1, 0] fitness=0 L=85
66: best: Chromosome(gen=[24, 1, 10, 1, 4, 5] fitness=0 L=85
67: best: Chromosome(gen=[16, 5, 14, 9, 0, 1] fitness=0 L=85
68: best: Chromosome(gen=[19, 1, 15, 6, 4, 0] fitness=0 L=85
69: best: Chromosome(gen=[23, 1, 11, 2, 4, 4] fitness=0 L=85
70: best: Chromosome(gen=[20, 2, 13, 5, 3, 2] fitness=0 L=85
71: best: Chromosome(gen=[25, 3, 7, 0, 2, 8] fitness=0 L=85
72: best: Chromosome(gen=[22, 2, 11, 3, 3, 4] fitness=0 L=85
73: best: Chromosome(gen=[22, 2, 11, 3, 3, 4] fitness=0 L=85
74: best: Chromosome(gen=[23, 5, 7, 2, 0, 8] fitness=0 L=85
75: best: Chromosome(gen=[17, 4, 14, 8, 1, 1] fitness=0 L=85
76: best: Chromosome(gen=[17, 4, 14, 8, 1, 1] fitness=0 L=85
77: best: Chromosome(gen=[23, 3, 9, 2, 2, 6] fitness=0 L=85
78: best: Chromosome(gen=[19, 2, 14, 6, 3, 1] fitness=0 L=85
79: best: Chromosome(gen=[17, 4, 14, 8, 1, 1] fitness=0 L=85
80: best: Chromosome(gen=[19, 3, 13, 6, 2, 2] fitness=0 L=85
81: best: Chromosome(gen=[22, 4, 9, 3, 1, 6] fitness=0 L=85
82: best: Chromosome(gen=[16, 5, 14, 9, 0, 1] fitness=0 L=85
83: best: Chromosome(gen=[21, 2, 12, 4, 3, 3] fitness=0 L=85
84: best: Chromosome(gen=[25, 4, 6, 0, 1, 9] fitness=0 L=85
85: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
86: best: Chromosome(gen=[24, 5, 6, 1, 0, 9] fitness=0 L=85
87: best: Chromosome(gen=[19, 3, 13, 6, 2, 2] fitness=0 L=85
88: best: Chromosome(gen=[21, 2, 12, 4, 3, 3] fitness=0 L=85
89: best: Chromosome(gen=[20, 1, 14, 5, 4, 1] fitness=0 L=85
90: best: Chromosome(gen=[22, 1, 12, 3, 4, 3] fitness=0 L=85
91: best: Chromosome(gen=[21, 1, 13, 4, 4, 2] fitness=0 L=85
92: best: Chromosome(gen=[20, 5, 10, 5, 0, 5] fitness=0 L=85
93: best: Chromosome(gen=[18, 5, 12, 7, 0, 3] fitness=0 L=85
94: best: Chromosome(gen=[16, 4, 15, 9, 1, 0] fitness=0 L=85
95: best: Chromosome(gen=[19, 4, 12, 6, 1, 3] fitness=0 L=85
96: best: Chromosome(gen=[22, 3, 10, 3, 2, 5] fitness=0 L=85
97: best: Chromosome(gen=[22, 5, 8, 3, 0, 7] fitness=0 L=85
98: best: Chromosome(gen=[23, 3, 9, 2, 2, 6] fitness=0 L=85
99: best: Chromosome(gen=[21, 4, 10, 4, 1, 5] fitness=0 L=85
100: best: Chromosome(gen=[21, 3, 11, 4, 2, 4] fitness=0 L=85
Лучшеерешение: Chromosome(gen=[22, 2, 11, 3, 3, 4] fitness=0 L=85

Результат работы программы для тестового примера №1

суточнениемусловия

01: best: None
02: best: Chromosome(gen=[18, 5, 12, 7, 0, 3] fitness=0 L=85
03: best: Chromosome(gen=[18, 5, 12, 7, 0, 3] fitness=0 L=85
04: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
05: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
06: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
07: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
08: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
09: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
10: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
11: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
12: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
13: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
14: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
15: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
16: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
17: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
18: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
19: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
20: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
21: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
22: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
23: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
24: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
25: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
26: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
27: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
28: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
29: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
30: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
31: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
32: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
33: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
34: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
35: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
36: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
37: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
38: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
39: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
40: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
41: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
42: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
43: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
44: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
45: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
46: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
47: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
48: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
49: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
50: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
51: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
52: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
53: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
54: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
55: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
56: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
57: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
58: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
59: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
60: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
61: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
62: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
63: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
64: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
65: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
66: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
67: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
68: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
69: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
70: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
71: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
72: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
73: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
74: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
75: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
76: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
77: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
78: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
79: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
80: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
81: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
82: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
83: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
84: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
85: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
86: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
87: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
88: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
89: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
90: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
91: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
92: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
93: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
94: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
95: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
96: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
97: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
98: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
99: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
100: best: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85
Лучшеерешение: Chromosome(gen=[25, 0, 10, 0, 5, 5] fitness=0 L=85

Результат работы программы для тестового примера №2

01: best: None
02: best: Chromosome(gen=[13, 7, 15, 9, 1, 0, 3, 7, 0] fitness=0 L=152
03: best: Chromosome(gen=[13, 7, 15, 9, 1, 0, 3, 7, 0] fitness=0 L=152
04: best: Chromosome(gen=[13, 7, 15, 9, 1, 0, 3, 7, 0] fitness=0 L=152
05: best: Chromosome(gen=[13, 7, 15, 9, 1, 0, 3, 7, 0] fitness=0 L=152
06: best: Chromosome(gen=[13, 7, 15, 9, 1, 0, 3, 7, 0] fitness=0 L=152
07: best: Chromosome(gen=[13, 7, 15, 9, 1, 0, 3, 7, 0] fitness=0 L=152
08: best: Chromosome(gen=[13, 7, 15, 9, 1, 0, 3, 7, 0] fitness=0 L=152
09: best: Chromosome(gen=[13, 7, 15, 9, 1, 0, 3, 7, 0] fitness=0 L=152
10: best: Chromosome(gen=[13, 7, 15, 9, 1, 0, 3, 7, 0] fitness=0 L=152
11: best: Chromosome(gen=[13, 7, 15, 9, 1, 0, 3, 7, 0] fitness=0 L=152
12: best: Chromosome(gen=[13, 7, 15, 9, 1, 0, 3, 7, 0] fitness=0 L=152
13: best: Chromosome(gen=[13, 7, 15, 9, 1, 0, 3, 7, 0] fitness=0 L=152
14: best: Chromosome(gen=[16, 4, 15, 1, 9, 0, 8, 2, 0] fitness=0 L=147
15: best: Chromosome(gen=[16, 4, 15, 1, 9, 0, 8, 2, 0] fitness=0 L=147
16: best: Chromosome(gen=[16, 4, 15, 1, 9, 0, 8, 2, 0] fitness=0 L=147
17: best: Chromosome(gen=[16, 4, 15, 1, 9, 0, 8, 2, 0] fitness=0 L=147
18: best: Chromosome(gen=[16, 4, 15, 1, 9, 0, 8, 2, 0] fitness=0 L=147
19: best: Chromosome(gen=[16, 4, 15, 1, 9, 0, 8, 2, 0] fitness=0 L=147
20: best: Chromosome(gen=[16, 4, 15, 1, 9, 0, 8, 2, 0] fitness=0 L=147
21: best: Chromosome(gen=[16, 4, 15, 1, 9, 0, 8, 2, 0] fitness=0 L=147
22: best: Chromosome(gen=[16, 4, 15, 1, 9, 0, 8, 2, 0] fitness=0 L=147
23: best: Chromosome(gen=[16, 4, 15, 1, 9, 0, 8, 2, 0] fitness=0 L=147
24: best: Chromosome(gen=[16, 4, 15, 1, 9, 0, 8, 2, 0] fitness=0 L=147
25: best: Chromosome(gen=[16, 4, 15, 1, 9, 0, 8, 2, 0] fitness=0 L=147
26: best: Chromosome(gen=[16, 4, 15, 1, 9, 0, 8, 2, 0] fitness=0 L=147
27: best: Chromosome(gen=[16, 4, 15, 1, 9, 0, 8, 2, 0] fitness=0 L=147
28: best: Chromosome(gen=[16, 4, 15, 1, 9, 0, 8, 2, 0] fitness=0 L=147
29: best: Chromosome(gen=[16, 4, 15, 1, 9, 0, 8, 2, 0] fitness=0 L=147
30: best: Chromosome(gen=[16, 4, 15, 1, 9, 0, 8, 2, 0] fitness=0 L=147
31: best: Chromosome(gen=[16, 4, 15, 1, 9, 0, 8, 2, 0] fitness=0 L=147
32: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
33: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
34: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
35: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
36: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
37: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
38: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
39: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
40: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
41: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
42: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
43: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
44: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
45: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
46: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
47: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
48: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
49: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
50: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
51: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
52: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
53: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
54: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
55: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
56: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
57: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
58: best:Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
59: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
60: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
61: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
62: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
63: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
64: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
65: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
66: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
67: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
68: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
69: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
70: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
71: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
72: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
73: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
74: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
75: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
76: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
77: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
78: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
79: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
80: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
81: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
82: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
83: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
84: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
85: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
86: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
87: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
88: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
89: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
90: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
91: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
92: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
93: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
94: best: Chromosome(gen=[14, 8, 13, 1, 7, 2, 10, 0, 0] fitness=0 L=145
95: best: Chromosome(gen=[7, 13, 15, 8, 2, 0, 10, 0, 0] fitness=0 L=145
96: best: Chromosome(gen=[7, 13, 15, 8, 2, 0, 10, 0, 0] fitness=0 L=145
97: best: Chromosome(gen=[7, 13, 15, 8, 2, 0, 10, 0, 0] fitness=0 L=145
98: best: Chromosome(gen=[7, 13, 15, 8, 2, 0, 10, 0, 0] fitness=0 L=145
99: best: Chromosome(gen=[7, 13, 15, 8, 2, 0, 10, 0, 0] fitness=0 L=145
100: best: Chromosome(gen=[7, 13, 15, 8, 2, 0, 10, 0, 0] fitness=0 L=145
Лучшеерешение: Chromosome(gen=[7, 13, 15, 8, 2, 0, 10, 0, 0] fitness=0 L=145