otchet (1108529)
Текст из файла
Московский государственный университет имени М. В. ЛомоносоваФакультет вычислительной математики и кибернетикиОтчёт по второму заданиюВариант 17. Задача сельского почтальонаАсирян Александр КамоевичГруппа 428Москва, 2015Оглавление1 Постановка задачи22 Генерация тестов2.1 Граф-цикл . . . .2.2 Граф-звезда . . .2.3 Полный граф . .2.4 Случайный граф33344............................................................................................................3 Генетический алгоритм64 Визуализация85 Результаты10Заключение11Приложение. Код программы12Литература321Глава 1Постановка задачиНа вход программе подаётся описание взвешенного неориентированногографа G = (V, E) в виде списка описаний рёбер.
Каждое описание ребраe ∈ E имеет вид (N ODE1 N ODE2 W EIGHT ), где N ODE1, N ODE2 –атомы, W EIGHT – целое положительное число. Затем на вход программеподаётся целое положительное число K и список рёбер L. Существует ли вграфе гамильтонов G цикл, то есть путь, начинающийся и заканчивающийсяв одной и той же вершине и проходящий через каждую вершину из графа Gтолько один раз, стоимости не более чем K, включающий в себя все рёбра изсписка L (и, возможно, другие)? Стоимость пути – это суммарная стоимостьрёбер, составляющих путь. Если искомый цикл не существует, напечатайте#f. Если искомый цикл существует, напечатайте #t, далее стоимость цикла, азатем найденный цикл в виде списка.
Первым и последним элементом спискадолжен быть один и тот же атом. Если существует несколько возможныхрешений, найдите решение с минимальной стоимостью.Решение задачи разделено на три этапа:1. На первом этапе разрабатываются тесты, на которых будет проверятьсяпрограмма.2. На втором этапе разрабатывается версия программы, которая находитрешение, но не выполняет визуализацию.3. На третьем этапе разрабатывается полная версия программы, выполняющая и решение задачи, визуализацию хода решения, визуализациюнайденного ответа.2Глава 2Генерация тестовНа данном этапе рассматривались только несколько видов графов, каждый из которых обладает своими свойствами.
Вес для ребер генерировалсяслучайно на отрезке [0, 9]. Количество сгенерированных контрольных реберравнялось max(b|V | / 2c + 1, 1).2.1Граф-циклГраф-циклпредставляетсобойпоследовательностьвида((v1 v2 weight1,2 ) (v2 v3 weight2,3 ) ... (vN −1 vN weightN −1,N ) (vN v1 weightN,1 )).В качестве контрольного веса бралась величина, равная |V | ×M AX_W EIGHT / 2 + (random (|V | × M AX_W EIGHT )), гдеM AX_W EIGHT – число, на единицу превышающее максимальный весребра, то есть 10. В качестве списка контрольных ребер был взят пустойсписок. Это объясняется тем, что граф-цикл сам по себе является гамильтоновым циклом, и добавление проверочных ребер, которые генерируетсяслучайным образом, с большой вероятностью приведут к отрицательномуответу.
Ответ находится очень легко – цикл из любой вершины и сумма всехвесов. Единственным критерием существования ответа является сверка сконтрольным весом.2.2Граф-звездаГраф-циклпредставляетсобойпоследовательностьвида((v1 v2 weight1,2 ) (v1 v3 weight1,3 ) ... (v1 vN weight1,N )). Контрольныйвес был принят за (random (|V | × M AX_W EIGHT )).
Контрольные ребрагенерировались. Вес и ребра никак не влияют на ответ, т.к. он заведомоотрицательный из-за структуры данного вида графов.32.3Полный графПолный граф – это граф вида ((v1 v2 weight1,2 ) ... (v1 vN weight1,N )(v2 vN weight2,N ) ... (vN −1 vN weightN −1,N )). Контрольный вес такой же, как ив случае графа-цикла. Контрольные ребра генерировались. Ответ находитсяпереборным алгоритмом. В полном графе заведомо есть гамильтонов цикл,влияние на ответ оказывают лишь контрольные вес и ребра.2.4Случайный графСлучайный граф – это генерация различных ребер. Изначально их количество равняется (|V | − 1) × |V | / 2, т.е. количеству ребер в полном графе.Но т.к. ребра генерируются случайно, и в список не добавляются ребра содинаковыми вершинами и те, которые уже есть в списке, то итоговый графбудет не полным с очень большой вероятностью.
Все входные параметрытакие же, как и в случае полного графа. Ответ также находится переборнымалгоритмом.Всего было сгенерировано 150 различных тестовых наборов:• 25 графов-циклов с количеством вершин от 3 до 27• 15 графов-звезд с количеством вершин от 4 до 18• 50 полных графов: по 5 на каждый граф с количеством вершин от 1 до10• 60 случайных графов: по 5 на каждый граф с количеством вершин от1 до 12Программа генерации тестов была написана на языке Scheme. Так жебыли написаны два скрипта на языке Python для автоматизирования генерации тестов и проверки работы генетического алгоритма.
Первый скриптсоздает файл, в котором отражается время генерации тестовых наборов длякаждого вида графа. Второй скрипт в свою очередь создает файл в видеhtml-страницы с информацией о прохождении тестов (рис. 2.1): результат,количество пройденных и непройденных тестов, процент пройденных тестов,общее время работы, среднее количество итераций генетического алгоритма,количество итераций для каждого теста.4Рис. 2.1: html-страница с результатами работы алгоритма5Глава 3Генетический алгоритмАлгоритм в большинстве своем основывается на исследовании, произведенном в статье [1]. Каждая особь представляет из себя некий гамильтоновцикл. Например для графа с 6-ю вершинами особью может быть последовательность L = {v1 v4 v5 v6 v3 v2}, то есть геном является вершина графа.Начальная популяция представляет собой некоторое число сгенерированныхслучайным образом особей.Далее происходит скрещивание популяции. Для каждой особи из популяции выбирается случайным образом еще одна особь.
Потом они скрещиваютсяв 2 этапа:1. Из второго родителя берется срез длиной, равной половине его длины,начиная с любой позиции, где этот срез возможен. Данный срез присваивается потомку в те же позиции, что и у родителя.2. Оставшиеся гены заполняются из генов первого родителя: родитель просматривается справа налево, и в случае отсутствия гена у потомка, гендобавляется потомку слева направо.Например, есть особь L1 = {v1 v2 v3 v4 v5 v6}. Допустим, в пару ей былавыбрана особь L2 = {v4 v1 v3 v5 v2 v6}. Делается срез длины 3, начиная со2-й позиции и помещается в потомка: L1,2 = {∗ v1 v3 v5 ∗ ∗}. Теперь берутсягены первого родителя: ген v6 есть в родителе и отсутствует в потомке, значитнадо добавить – L1,2 = {v6 v1 v3 v5 ∗ ∗}.
Таким образом на выходе получимL1,2 = {v6 v1 v3 v5 v2 v4}.В результате скрещивания популяция увеличивается в 2 раза (2 родителя– 1 потомок). Но дальше происходит селекция: на следующий этап алгоритмапроходит только определенная доля лучших (по значению фитнес-функции)особей из родительской и дочерней популяций. Причем сумма процентов дляобоих видов особей равняется 100. Так как обе популяции равны, то общаяпопуляция сократится в два раза и сравняется по количеству с начальной.6Худшая половина отобранных особей подвергается мутации с некоторойдолей вероятности. Мутация представляет собой перестановку двух случайных генов местами. Например имеется особь L3 = {v6 v2 v1 v5 v4 v3} и вкачестве мутации первый ген меняется местом с четвертым, получается особьLM3 = {v5 v2 v1 v6 v4 v3}.
Размер популяции не меняется.В качестве целевой функции считается вес пути, причем если ребро отсутствует в графе или контрольное ребро отсутствует в пути, к значению функции добавляется штраф (заменяется на вес ребра в первом случае), равныйдлине пути, умноженной на увеличенный на единицу максимальный вес ребра.
Штраф добавляется за каждое отсутствие, он однозначно отделит особи,которые не могут быть путями в графе, от потенциальных ответов. В конце,если значение функции превышает штраф, то ей прибавляется контрольныйвес плюс один, чтобы особь не могла быть выбрана в качестве ответа. Например, дан граф G = {(v1 v2 4) (v1 v3 5)} , максимальный вес ребра –9, контрольных ребер нет, контрольный вес – 50, вес особи L = {v2 v3 v1}равняется WL = 3 × 10 + 5 + 4 + 50 + 1 = 90.В качестве критериев остановки работы алгоритма является максимальное количество итераций и отличие среднего веса новой популяции от старойменьше, чем на некотрое δ.В программе были использованы следующие параметры:• Максимальный вес ребра – 9• Размер популяции – 30• Вероятность мутации особи – 40%• Доля родителей в селекции – 60%• Максимальное количество итераций – 10000• Отличие весов популяций δ = 0.000017Глава 4ВизуализацияНа данном этапе были использованы библиотеки The Racket GraphicalInterface Toolkit, Plot, The Racket Drawing Toolkit.
Пользователю предлагается выбрать вид графа, количество вершин в нем и все параметры для работыгенетического алгоритма. Кроме того можно: убрать показ весов ребер, т.к.при их большом количестве трудно понять какой вес к какому ребру относится; задать генерацию контрольных ребер для работы алгоритма; установитьскорость показа результатов (рис. 4.1). Все входные данные проверяются накорректность.При нажатии на кнопку "Запустить алгоритм" генерируется граф, длянего решается задача о поиске гамильтонова цикла минимального веса, меньше контрольного веса, включающего контрольные ребра.
Алгоритм показывается по итерациям, выводя информацию о лучшей и худшей особях, атакже среднем весом популяции (рис. 4.2). Также показывается статистика об изменении среднего веса популяции на каждой итерации (рис. 4.3).Рис. 4.1: Пример начальногосостояния окна8Рис. 4.2: Пример работы интерфейса. Зеленым выделена лучшая особь наданной итерацииРис. 4.3: Статистика9Глава 5РезультатыРезультаты алгоритма на описанных выше входных параметрах оказалисьследующими:• Средний процент прохождения тестов ≈ 96%• Среднее количество итераций алгоритма ≈ 700, а случаи выхода изалгоритма по максимальному количеству итераций единичны• Среднее время работы алгоритма ≈ 9 минут на всех тестах, дольшевсего алгоритм работает на графах-циклах (≈ 30 секунд при количестве вершин ≥ 20 ). Но тем не менее общее время гораздо меньше, чемрешение задачи переборным алгоритмом (≈ 9 минут только на полныхграфах)Данная реализация генетического алгоритма не находила верный ответв основном для графов-циклов (были единичные случаи для полных и случайных графов, когда алгоритм находил решение, но оно не было лучшим,то есть в графе существовал гамильтонов цикл с меньшим весом).
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
