описание (1108524)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Вспомогательные функции:

1. (push lst elem), (all-vertex graph), (cmd-parser) – такие же, как и в tests.rkt.

2. (pick-random lst) – выбор случайного элемента из списка.

3. (slice lst start count) – рекурсивный срез из списка count элементов, начиная с позиции start.

• (get-n-items lst num) – рекурсивный выбор первых num элементов из списка

(define pop-size 30)

(define mutate-prob 0.6)

(define par-percent 0.6)

(define max-iter 10000)

(define exit-percent 0.00001)

(define daughter-percent (- 1 par-percent))

Генерация первой популяции

(gen-first-pop n graph) – генерирует n особей для графа. Проверяет можно ли сгенерировать именно столько особей. В качестве особи берется случайный путь, т.е. список длины N, где N – количество всех вершин в графе.

• (helper vertices n result) - вспомогательная итеративная функция, генерирующая n особей из вершин vertices

  • (gen-random-list vertices result) – итеративная функция, генерирующая случайный путь

Фитнес-функция

(path-weight path) – считает весь пути. В самом простом случае считается действительно только вес пути. Но если в особи содержатся ребра, отсутствующие в графе, то к весу прибавляется penalty, равный длине пути, умноженной на увеличенный на единицу максимальный вес ребра. Такой штраф однозначно отделит особи, которые не могут быть путями в графе, от потенциальных ответов.

• (define penalty (* (length path) 10)) – штраф

• (find-weight edge) – определяет есть ли ребро в графе. Возвратит вес, если оно есть

• (helper path result) - вспомогательная итеративная функция для поиска веса всего пути

(fitness-function individ) – считает вес для одной особи. Отличается от path-weight только тем, что проверяет наличие контрольных ребер (control-edges) в пути. Так же добавляет штраф, если их нет. В итоге, если вес особи больше штрафа, то ей прибавляется контрольный вес (control-weight) плюс один, чтобы особь не могла быть выбрана в качестве ответа.

• (define penalty (* (length individ) 10)) - штраф

• (check-edges path) – проверяет наличие контрольных ребер в пути

(fitness-pop population) - находит вес каждой особи в популяции и сортирует их в порядке убывания. На выходе список пар (особь . вес).

Скрещивание

(cross-pop population) – скрещивает две особи. Для каждой особи выбирается пара из оставшихся и на выходе получается один потомок, таким образом, имеем N потомков и N родителей – всего 2 * N особей.

• (cross par1 par2) – скрещивает две особи следующим образом: из особи par2 длиной M делается срез длиной (quotient M 2), начиная с любой позиции. Оставшиеся гены заполняются из генов первого родителя: родитель просматривается справа налево, и в случае отсутствия гена у потомка, ген добавляется потомку слева направо

  • (fill lst1 lst2 to from tmp) – добавляет список lst2 в список lst1 неповторяющимися элементами. to, from – количество элементов, которые нужно добавить в начало и в конец соответственно. tmp – временное хранение элементов, добавляющихся в начало

• (helper pop result) - вспомогательная итеративная функция для скрещивания популяции

Селекция

(selection par-pop daughter-pop) – выбор par-percent особей из родительской популяции (N особей) и daughter-percent особей из потомков (N особей). В итоге получается снова N особей.

Мутация

(mutate-pop population) – применение мутации для популяции.

• (mutate individ) – мутация одной особи, происходит с помощью переставления двух генов местами

  • (swap ind1 ind2 lst) – переставляет два элемента списка местами, ind2 >= ind1

  • (gen-other-index index) – генерация индекса отличного от index, нужно для того, чтобы мутация действительно имела эффект

• (helper population result) – вспомогательная итеративная функция для мутации популяции (не вход подается только худшая половина популяции). Каждая особь мутирует с вероятностью 1 – mutate-prob

(population-weight population) – считает средний вес популяции.

(evolution population iter total-sum) – итеративная функция итерации алгоритма. Критерием останова является максимальное количество итераций max-iter и отличие среднего веса новой популяции от старой меньше, чем на exit-percent.

(new-pop (mutate-pop (selection population (cross-pop population))) – новая популяция, как и описывалось выше.

(genetic-algorithm graph

control-weight

control-edges

pop-size

mutate-prob

par-percent

max-iter

exit-percent) – генетический алгоритм, входные параметры описаны выше. Вызывает первую итерация с сгенерированной первой популяцией размером pop-size.

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

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

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов лабораторной работы