Полный текст:
ОГЛАВЛЕНИЕ
Введение. 3
Постановка
задачи. 4
Генетические
алгоритмы.. 5
Генетические
операторы.. 8
Создание
начальной популяции. 9
Размножение. 9
Мутация. 10
Отбор
(селекция) 11
Скрещивание. 15
Разработка
программы.. 17
Тестирование. 24
Выводы.. 25
Литература. 26
Приложение. 27
Введение
Генетические элементы
(ГА) работают с совокупностью особей - популяцией, каждая из которых
представляет возможное решение данной проблемы. Каждая особь оценивается мерой
ее приспособленности согласно тому, насколько хорошо соответствующее ей решение
задачи. В природе это эквивалентно оценке того, насколько эффективен организм
при конкуренции за ресурсы. Наиболее приспособленные особи получают возможность
воспроизводить потомство с помощью перекрестного скрещивания с другими особями
популяции. Это приводит к появлению новых особей, которые сочетают в себе
некоторые характеристики, наследуемые ими от родителей. Наименее
приспособленные особи с меньшей вероятностью смогут воспроизвести потомков, так
что те свойства, которыми они обладали, будут постепенно исчезать из популяции
в процессе эволюции. Иногда происходят мутации, или спонтанные изменения в
генах.
Таким образом, из
поколения в поколение хорошие характеристики распространяются по всей
популяции. Скрещивание наиболее приспособленных особей приводит к тому, что
исследуются наиболее перспективные участки пространства поиска. В конечном
итоге популяция будет сходиться к оптимальному решению задачи. Преимущество ГА
состоит в том, что он находит приблизительные оптимальные решения за
относительно короткое время.
В процессе выполнения
данного проекта создана программа для поиска минимума функции двух вещественных
переменных в заданной области с помощью генетического алгоритма.
Постановка
задачи
Необходимо
найти минимум функции в заданной
области.
При
выполнении данного проекта необходимо учитывать, что решение задачи является
подверженным влиянию случайных величин. Поэтому каждый запуск программы
необходимо повторять, по крайней мере, 20-30 раз. После этого из набора полученных решений надо
отобрать лучшее. Разумеется, это надо сделать, поместив содержание главной
программы в соответствующий цикл, в котором будет одновременно выбираться
наилучшее решение. Одновременно надо вычислить и среднее значение минимума за
эти 20-30 прогонов.
.
.
.
Рассмотреть
одноточечное скрещивание и инверсионную мутацию.
Каждая
переменная кодируется 20 битами.
Провести
расчеты для 40 и 80 поколений.
Сравнить
получающиеся решения при размерах популяции 8, 12, 20 особей.
Генетические
алгоритмы
Пусть у нас есть
некоторый определенный тип или класс объектов (т.е. множество объектов,
удовлетворяющих некоторому набору условий). И пусть нам необходимо найти в этом
классе некоторый объект, удовлетворяющий другому некоторому условию. Такой
процесс можно обобщенно назвать поиском или решением. Класс, среди объектов
которого производится поиск, назовем областью поиска или пространством поиска.
Искомый объект можно назвать целью или целевым объектом поиска, а условие,
которому он должен удовлетворять - целевым условием. Для определения
условия обычно задается некоторая функция на пространстве поиска. Достижение
функцией определенного значения и является целевым условием. Такая функция
называется целевой функцией. Таким образом, поиск заключается в просмотре по
определенным правилам пространства поиска всех объектов, пока не будет
обнаружен целевой. Функции выбора нового кандидата для проверки называются
операторами поиска.
Для компьютерных
алгоритмов решения (поиска), использующих вычислительные модели механизмов эволюции
в качестве ключевых структурных элементов, используется обобщенное название -
эволюционные алгоритмы.
В генетическом алгоритме
(ГА) каждый индивид кодируется сходным с ДНК методом - в виде
строки из символов одного типа. Длина строки (ДНК) постоянна. Популяция из
индивидов подвергается процессу эволюции с интенсивным использованием
скрещивания и мутаций.
Назовем представление
каждого индивида геномом. Для каждого вида и каждого представления для данного
целевого условия задается целевая функция. Значение целевой функции назовем
целевым значением. Вектор, состоящий из целевых значений всех индивидов в
популяции, назовем вектором целевых значений. Тогда если вычислен вектор
целевых значений, то можно определить приспособленность (fitness) индивида в
популяции, для чего задается специальная функция приспособленности от данного
целевого значения и от вектора целевых значений. Аналогично вектору целевых
значений введем вектор приспособленности. Часто целевое значение называют
приспособленностью, а значение приспособленности, в смысле вероятность участия
в размножении, неявно вычисляется во время отбора. Процесс эволюции
останавливается, когда популяция отвечает определенному критерию - критерию
завершения.
Принципиальная схема
работы ГА состоит из следующих основных фаз:
Создание начальной популяции. Задание
генома каждому из индивидов. Расчет вектора целевых значений. Шаг эволюции -
построение нового поколения. Проверка критерия завершения, если не
выполнено - переход на 2.
Шаг эволюции можно
разделить на следующие этапы:
Вычисление вектора приспособленности.
Отбор кандидатов на скрещивание
(Отбор - Selection) .Скрещивание, т.е. порождение каждой
парой отобранных кандидатов новых индивидов, путем геномов. Мутация геномов. Вычисление вектора целевых значений и
построение новой популяции (нового поколения).
Среди компонентов,
образующих генетический алгоритм, в большинстве случаев только два
непосредственно определяются конкретной задачей - это кодировка задачи (отображение пространства
поиска на пространство битовых строк) и целевая функция. Рассмотрим задачу
параметрической оптимизации, заключающуюся в определении набора переменных,
минимизирующих некоторую величину (цель). В более традиционных терминах, задача
состоит в поиске минимума некоторой функции F(X1, X2, …, XM).
На первом этапе обычно
делается предположение, что переменные, представляющие параметры, могут быть
представлены битовыми строками. Это означает, что переменные предварительно
дискретизируются некоторым образом и что область дискретных значений
соответствует некоторой степени 2. Например, с 10 битами на параметр мы
получаем область из 210 = 1024 дискретных значений. Если параметры
непрерывны, то проблема дискретизации не заслуживает особого внимания.
Разумеется, предполагается, что дискретизация обеспечивает достаточное
разрешение, чтобы сделать возможным регулирование получения результата с
желаемым уровнем точности. Предполагается также, что дискретизация в некотором
смысле представляет основную функцию.
Битовую строку длины N
можно рассматривать как целое двоичное число I, которому соответствует
некоторое вещественное значение r из заданного диапазона . Это соответствие устанавливается формулой
.
За исключением проблемы
кодирования, целевая функция обычно дается как часть постановки задачи. С другой
стороны, разработка целевой функции иногда может непосредственно входить в
разработку алгоритма оптимизации или поиска решения. В других случаях значение
целевой функции может зависеть от реализации и давать только приближенный или
частный результат.
Генетические
операторы
В соответствии с
техническим заданием решение задачи производится генетическим алгоритмом.
Генетический алгоритм —
это эвристический алгоритм поиска, используемый для решения задач оптимизации и
моделирования путём случайного подбора, комбинирования и вариации искомых
параметров с использованием механизмов, напоминающих биологическую эволюцию.
Является разновидностью эволюционных вычислений. Отличительной особенностью
генетического алгоритма является акцент на использование оператора
«скрещивания», который производит операцию рекомбинации решений-кандидатов,
роль которой аналогична роли скрещивания в живой природе.
Задача формализуется
таким образом, чтобы её решение могло быть закодировано в виде вектора
(«хромосомы»). Случайным образом создаётся некоторое количество начальных
векторов («начальное поколение»). Они оцениваются с использованием «функции
приспособленности», в результате чего каждому вектору присваивается
определённое значение («приспособленность»), которое определяет вероятность
выживания организма, представленного данным вектором, а также может влиять на
вероятность применения к нему «генетических операторов».
Из полученного множества
решений («поколения») с учётом значения «приспособленности» выбираются решения
(обычно лучшие особи имеют большую вероятность быть выбранными), к которым
применяются «генетические операторы» (в большинстве случаев «скрещивание» —
crossover и «мутация» — mutation), результатом чего является получение новых
решений. Для них также вычисляется значение приспособленности, и затем
производится отбор («селекция») лучших решений в следующее поколение.
Этот набор действий
повторяется итеративно, так моделируется «эволюционный процесс», продолжающийся
несколько жизненных циклов (поколений), пока не будет выполнен критерий
остановки алгоритма. Таким критерием может быть:
нахождение глобального, либо
субоптимального решения;исчерпание числа поколений,
отпущенных на эволюцию;исчерпание времени, отпущенного на
эволюцию.
Генетические алгоритмы
служат, главным образом, для поиска решений в очень больших, сложных
пространствах поиска.
Создание начальной популяции
Перед первым шагом нужно
случайным образом создать начальную популяцию; даже если она окажется совершенно
неконкурентоспособной, генетический алгоритм все равно достаточно быстро
переведет ее в жизнеспособную популяцию. Таким образом, на первом шаге можно
особенно не стараться сделать слишком уж приспособленных особей, достаточно,
чтобы они соответствовали формату особей популяции, и на них можно было
подсчитать функцию приспособленности (Fitness). Итогом первого шага является
популяция H, состоящая из N особей.
Размножение
Размножение в
генетических алгоритмах обычно половое - чтобы произвести потомка, нужны
несколько родителей; обычно, конечно, нужны два. Размножение в разных
алгоритмах определяется по-разному - оно зависит от представления данных.
Главное требование к размножению - чтобы потомок или потомки имели возможность
унаследовать черты обоих родителей, «смешав» их каким-либо достаточно разумным
способом. Вообще говоря, для того чтобы провести операцию размножения, нужно
выбрать (1-s)p/2 пар гипотез из H и провести с ними размножение, получив по два
потомка от каждой пары (если размножение определено так, чтобы давать одного
потомка, нужно выбрать (1-s)p пар), и добавить этих потомков в H'. В результате
H' будет состоять из N особей. Почему особи для размножения обычно выбираются
из всей популяции H, а не из выживших на первом шаге элементов H0 (хотя
последний вариант тоже имеет право на существование)? Дело в том, что главный
бич многих генетических алгоритмов - недостаток разнообразия (diversity) в
особях. Достаточно быстро выделяется один-единственный генотип, который
представляет собой локальный максимум, а затем все элементы популяции
проигрывают ему отбор, и вся популяция «забивается» копиями этой особи. Есть
разные способы борьбы с таким нежелательным эффектом; один из них - выбор для
размножения не самых приспособленных, но вообще всех особей.
Мутация
К мутациям относится все
то же самое, что и к размножению: есть некоторая доля мутантов m, являющаяся
параметром генетического алгоритма, и на шаге мутаций нужно выбрать mN особей,
а затем изменить их в соответствии с заранее определенными операциями мутации.
Каждый бит каждой особи в
популяции мутирует (точнее, пытается мутировать) с некоторой низкой вероятностью
pm. Обычно мутация
применяется с вероятностью меньше чем 1 %.
Мутации бывают разных видов:
инверсионная, двухточечная. Инверсионная мутация интерпретируется как
“зеркальное отражение“ бита (инверсия его значения, т.е. изменение его с 1 на 0
или с 0 на 1).
Кроме описанной инверсионной
мутации можно применить оператор двухточечной мутации. В этом случае если
мутация происходит, то случайным образом выбираются два гена, которые
обмениваются своими значениями.
Однако в результате мутации
хромосома может не измениться если вероятность мутации низкая. И хромосома
останется прежней. Это приводит к замедлению поиска цели.
Высокая вероятность мутации
также плохо сказывается на поиске, так как хромосома может “проскочить” нужную
цель.
Поэтому вероятность
устанавливается в некоторое определенное значение.
Отбор (селекция)
На этапе отбора нужно из
всей популяции выбрать определенную ее долю, которая останется «в живых» на
этом этапе эволюции. Есть разные способы проводить отбор. Вероятность выживания
особи h должна зависеть от значения функции приспособленности Fitness(h). Сама
доля выживших s обычно является параметром генетического алгоритма, и ее просто
задают заранее. По итогам отбора из N особей популяции H должны остаться sN
особей, которые войдут в итоговую популяцию H'. Остальные особи погибают.
Целью селекции является
осуществление выборки индивидуумов в текущей популяции (т.е. из некоторого набора)
пропорционально их пригодности. Обычно используют четыре различных механизма
селекции - “колесо рулетки”, остаточная
стохастическая выборка, стохастическая равномерная выборка и турнирная
селекция. Первые три алгоритма являются вариантами пропорциональной селекции, а
последний - непропорциональной.
Основанный на принципе
колеса рулетки метод селекции считается для генетических алгоритмов основным
методом отбора особей для родительской популяции с целью последующего их
преобразования генетическими операторами, такими как скрещивание и мутация.
Несмотря на случайный характер процедуры селекции, родительские особи
выбираются пропорционально значениям их функций приспособленности: каждой
хромосоме сопоставлен сектор колеса рулетки, величина которого устанавливается
пропорциональной значению функции приспособленности данной хромосомы, поэтому,
чем больше значение функции приспособленности, тем больше сектор на колесе
рулетки. Отсюда вытекает, что чем больше сектор на колесе рулетки, тем выше
шанс, что будет выбрана именно эта хромосома. Слабая сторона этого метода
заключается в том, что особи с очень малым значением функции приспособленности
слишком быстро исключаются из популяции, что может привести к преждевременной
сходимости генетического алгоритма. В связи с вышесказанным, созданы и
используются альтернативные алгоритмы селекции.
При турнирной селекции все
особи популяции разбиваются на подгруппы с последующим выбором в каждой из них
особи с наилучшей приспособленностью. Различаются два способа такого выбора:
детерминированный выбор и случайный выбор. Детерминированный выбор
осуществляется с вероятностью, равной 1, а случайный выбор – с вероятностью,
меньшей 1. Подгруппы могут иметь произвольный размер, но чаще всего популяция
разделяется на подгруппы по 2-3 особи в каждой.
Турнирный метод пригоден для
решения задач как максимизации, так и минимизации функции. Помимо того, он
может быть легко распространен на задачи, связанные с многокритериальной
оптимизацией, т.е. на случай одновременной оптимизации нескольких функций. В
турнирном методе допускается изменение размера подгрупп, на которые
подразделяется популяция. Исследования подтверждают, что турнирный метод
действует эффективнее, чем метод рулетки.
При ранговой селекции особи
популяции ранжируются по значениям их функции приспособленности. Это можно
представить себе как отсортированный список особей, упорядоченных по
направлению от наиболее приспособленных к наименее приспособленным (или
наоборот), в котором каждой особи приписывается число, определяющее ее место в
списке и называемое рангом. Количество копий каждой особи, введенных в
родительскую популяцию, рассчитывается по априорно заданной функции в
зависимости от ранга особи. Достоинство рангового метода заключается в
возможности его применения как для максимизации, так и для минимизации функции.
Существуют различные
варианты алгоритмов селекции. Представленные выше методы (рулетки, турнирный и
ранговый) применяются чаще всего, но существуют так называемые особые процедуры
селекции: элитарная стратегия и генетический алгоритм с частичной заменой
популяции.
Элитарная стратегия
заключается в защите наилучших хромосом на последующих итерациях. В
классическом генетическом алгоритме самые приспособленные особи не всегда
переходят в следующее поколение. Это означает, что новая популяция не всегда
содержит хромосому с наибольшим значением функции приспособленности из
предыдущей популяции. Элитарная стратегия применяется для предотвращения потери
такой особи. Эта особь гарантированно включается в новую популяцию.
Генетический алгоритм с
частичной заменой популяции, иначе называемый генетическим алгоритмом с
зафиксированным состоянием, характеризуется тем, что часть популяции переходит
в следующее поколение без каких-либо изменений. Это означает, что входящие в
эту часть хромосомы не подвергаются операциям скрещивания и мутации. Часто в
конкретных реализациях алгоритма данного типа на каждой итерации заменяются
только одна или две особи вместо скрещивания и мутации в масштабе всей
популяции.
В данной работе используется
так называемая турнирная селекцию, не требующая предварительного ранжирования
функции пригодности. При этом последовательно берутся два соседних элемента
текущей популяции (первый и второй, третий и четвертый и т.д.) и лучший из них
(т.е. элемент, обладающий меньшим значением целевой функции или функции
пригодности) помещается в промежуточную популяцию P'. После первого прохода
(пока сформирована только половина промежуточной популяции) исходная популяция
случайным образом перемешивается и описанный процесс повторяется еще один раз.
Здесь лучшие или худшие индивидуумы рассматриваются в смысле их упорядочивания
согласно соответствующим значениям целевой функции.
Селекция
играем важную роль, так как ГА работают с совокупностью "особей" -
популяцией, каждая из которых представляет возможное решение данной проблемы.
Каждая особь оценивается мерой ее "приспособленности" согласно тому,
насколько "хорошо" соответствующее ей решение задачи. В природе это
эквивалентно оценке того, насколько эффективен организм при конкуренции за
ресурсы. Наиболее приспособленные особи получают возможность
"воспроизводить" потомство с помощью "перекрестного
скрещивания" с другими особями популяции. Это приводит к появлению новых
особей, которые сочетают в себе некоторые характеристики, наследуемые ими от
родителей. Наименее приспособленные особи с меньшей вероятностью смогут
воспроизвести потомков, так что те свойства, которыми они обладали, будут
постепенно исчезать из популяции в процессе эволюции.
Таким
образом, из поколения в поколение хорошие характеристики распространяются по
всей популяции. Скрещивание наиболее приспособленных особей приводит к тому,
что исследуются наиболее перспективные участки пространства поиска. В конечном
итоге популяция будет сходиться к оптимальному решению задачи.
Следовательно,
требуется проводить селекцию для отбора наиболее приспособленных особей с целью
ускорить поиск оптимального решения.
Наименее приспособленные особи с меньшей
вероятностью смогут воспроизвести потомков, так что те свойства, которыми они
обладали, будут постепенно исчезать из популяции в процессе эволюции. Таким
образом, из поколения в поколение хорошие характеристики распространяются по
всей популяции. Таким образом, для решения задачи необходимо выбирать особи с
лучшим значением целевой функции (наиболее минимальным значением).
Скрещивание
Наиболее
простым является одноточечное скрещивание - каждая
выбранная таким образом пара строк скрещивается следующим образом: случайным
образом выбирается положение точки сечения (целое число k в промежутке от 1 и l-1,
где l - длина
строки). Затем, путем обмена всеми элементами между позициями k+1 и l включительно, рождаются две новых строки. Например, пусть первая
особь - а вторая
соответственно и пусть случайно выбранная
точка сечения будет после третьего гена (бита). Тогда в результате скрещивания
получим две особи-потомки - и . После этого потомки замещают родительские особи в
промежуточной популяции . Схематично этот вариант показан на рисунке.
Одноточечное скрещивание
легко обобщается на n-точечное с n точками сечения. Предельным случаем является
равномерное скрещивание, при котором каждый ген первого из родителей случайным
образом передается любому из потомков, при этом другой потомок, соответственно,
получает ген от другого родителя.
Двухточечное скрещивание
иллюстрирует следующий пример:
Здесь чёрными линиями
выделены точки разреза исходной хромосомы, а в данном случае битовой строки.
В двухточечном кроссинговере
(и многоточечном кроссинговере вообще) хромосомы расцениваются как циклы,
которые формируются соединением концов линейной хромосомы вместе. Для замены
сегмента одного цикла сегментом другого цикла требуется выбор двух точек
разреза. В этом представлении, одноточечный кроссинговер может быть рассмотрен
как кроссинговер с двумя точками, но с одной точкой разреза, зафиксированной в
начале строки.
Разработка программы
Программа
реализована в одном модуле: genetic.pas, текст которой приведен в приложении.
Программа
состоит из нескольких процедур.
Процедура
InitPop создает начальную популяцию случайным образом с помощью вспомогательной
функции Flip, которая генерирует случайное число из вариантов 0 и 1. Процедура выполняется
при запуске программы и вычисляет функцию пригодности. Процедуры Select, Mutation и Crossover реализуют 3 генетических оператора.
Процедура
Select реализует
оператор турнирного отбора.
Функция
Select1 осуществляет
отбор наилучших особей для популяции.
В
функции происходит перемешивание популяции и выбор особей, которые перейдут в
следующее поколение (имеющие наилучшее значение целевой функции). Выбираются
две рядом стоящих особи и в следующее поколение переходит особь с наилучшим
значением целевой функции. Отбор происходит PopSize раз (количество особей в популяции).
Функция
Mutation реализует процесс
инверсионной мутации. Мутация происходит с некоторой вероятностью. Алгоритм
мутации имеет вид:
В процедуре используются
следующие переменные и константы:
alleleval
– ген для мутации;
PMutation
– вероятность мутации;
NMutation – счетчик мутаций;
Код функции:
function Mutation(alleleval: Allele; var NMutation: integer):
Allele;
begin
Mutation :=
alleleval;
{Если мутация должна произойти}
if Flip(PMutation) then
{ Мутация с вероятностью PMutation }
begin
Inc(NMutation); {Наращиваем счетчик мутаций}
{Ген мутирует}
Mutation := not alleleval; { Совершаем мутацию }
end;
end;
Инверсионная мутация
является самой простой мутацией. В ее случае выбирается произвольным образом
ген и инвертируется его значение. Однако мутация происходит только с
вероятностью PMutation т.к. в природе мутации наступают не часто.
Вероятность мутации в программе установлена согласно методическому пособию в
1%.
Процедура
Crossover реализует оператор одноточечного скрещивания. Скрещивание происходит
с некоторой вероятностью pcross.
Каждая выбранная таким
образом пара строк скрещивается следующим образом: если скрещивание должно
произойти, то наращивается счетчик скрещиваний и потомки наследуют гены путем
обмена между всеми элементами.
Случайным
образом выбирается положение точки сечения (целое число в промежутке от 1 и flchrom-1, где flchrom - длина
строки). Затем, путем обмена всеми элементами до и после точки счения рождаются
две новых строки. В процессе скрещивания происходит мутация.
После этого потомки замещают
родительские особи в промежуточной популяции. Если же скрещивание не
происходит, то потомками становятся сами родители.
Данная процедура использует
следующие переменные:
parent1, parent2 – хромосомы
родителей;
child1,child2 – хромосомы потомков;
flchrom
– длина хромосомы (количество генов);
ncross, nmutation – счетчики
количества скрещиваний и мутаций;
jcross – точка сечения.
Код процедуры:
procedure Crossover(var Parent1, Parent2, Child1,
Child2: Chromosome; flchrom: integer; var NCross, NMutation: integer);
var i, jcross: integer;
begin
if
Flip(PCross) then
{ Выполняется скрещивание с вероятностью PCross }
begin
{Определение
точки сечения в диапазоне между 1 и flchrom-1}
jcross := 1 + Random(flchrom);
Inc(NCross); { Наращивание счетчика скрещиваний }
{ Первая часть обмена, 1 в 1 и 2 в 2 }
{ Обмениваем часть до точки сечения }
for
i := 1 to jcross do
begin
{ Заодно и
мутируем с вероятностью pmutation }
{
Первый потомок }
Child1[i]
:= Mutation(Parent1[i], NMutation);
{ Второй
потомок }
Child2[i]
:= Mutation(Parent2[i], NMutation);
end;
{ Вторая часть обмена, 1 в 2 и 2 в 1 }
{ Обмениваем часть после точки сечения }
for
i := jcross + 1 to flchrom do
begin
{ Заодно и мутируем с вероятностью pmutation }
{
Первый потомок }
Child1[i]
:= Mutation(Parent2[i], NMutation);
{ Второй
потомок }
Child2[i]
:= Mutation(Parent1[i], NMutation);
end;
end;
end;
Процедура
Generation
используется для генерации нового поколения при помощи операторов отбора,
скрещивания и мутации.
Для
декодирования строки битов в вещественное число используется процедура Decode.
На
первом этапе обычно делается предположение, что переменные, представляющие
параметры, могут быть представлены битовыми строками. Это означает,
что переменные предварительно дискретизируются некоторым образом и что область
дискретных значений соответствует некоторой степени 2. Например, с 20 битами на
параметр мы получаем область из 220 = 1048576 дискретных значений.
Если параметры непрерывны, то проблема дискретизации не заслуживает особого
внимания. Разумеется, предполагается, что дискретизация обеспечивает
достаточное разрешение, чтобы сделать возможным регулирование получения результата
с желаемым уровнем точности. Предполагается также, что дискретизация в
некотором смысле представляет основную функцию. Битовую строку длины N можно
рассматривать как целое двоичное число I, которому соответствует некоторое
вещественное значение r из заданного диапазона . Это соответствие устанавливается формулой
.
В нашем случае n=20.
Для получения статистических данных:
минимального, максимального и среднего значений целевой функции (в программе
задана в виде функции ObjFunc) используется процедура Statistics. С помощью
данной процедуры находятся статистические данные. В основной программе она
используется следующим образом: по всей популяции считается функция
пригодности, находится максимальное и минимальное значение целевой функции а
также ее среднее.
procedure Statistics(var Max, Avg, Min: double; Pop: Population);
var j :integer;
SumFitness: double;
begin
SumFitness := Pop[1].Fitness;
Min := Pop[1].Fitness;
Max := Pop[1].Fitness;
for j := 2 to PopSize do
with Pop[j] do
begin
{ Накопление суммы значений
функции пригодности }
SumFitness := SumFitness +
Fitness;
if Fitness>Max then Max
:= Fitness; {Новое значение Max}
if Fitness<Min then Min
:= Fitness; {Новое значение Min}
end;
Avg := SumFitness /
PopSize; {
Расчет среднего }
end;
Каркасом
для построения решения задачи являлась программа реализованная в методическом
пособии. Она была изучена, обобщена и модифицирована под текущую задачу.
По
сравнению с предложенной программой внесены следующие изменения:
Изменено пространство поиска и одномерного случая на
двумерный.Изменены процедуры скрещивания и мутации в
соответствии с вариантом.Программа выполняет по 30 прогонов с целью улучшения
достоверности результата.Изменены целевая функция и границы поиска минимума.
Больше
изменений нет.
Тестирование
В
процессе тестирования программы были получены следующие результаты:.
Число поколений
Размер популяции
Среднее значение минимума
Лучшее значение минимума
40
8
1.423E+0000
8.707E+0000
12
2.118E-0001
3.141E-0005
20
9.421E-0003
8.944E-0005
80
8
7.874E-0001
1.046E-0001
12
1.904E-0001
3.847E-0003
20
3.381E-0003
2.814E-0003
Выводы
В
результате тестирования программы можно сделать вывод, что на точность
результата влияют следующие факторы: количество поколений и количество особей.
Так,
чем больше особей участвует в генетическом отборе (больший размер популяции)),
тем более точный получается результат; чем большее количество поколений живут
особи, тем точнее получается результат.
После
сопоставления двух факторов влияния: размера популяций и числа поколений можно
сделать из полученных результатов можно сделать вывод, что наибольшее влияние
на точность результата оказывает число поколений, так как чем больше поколение,
тем лучшее значение имеет функция пригодности.
Литература
Змитрович
А. И. Интеллектуальные информационные системы. — Мн.:ТетраСистемс, 1997. — 368
с.Батищев Д.
А. Генетические алгоритмы решения экстремальных задач. — Воронеж:Изд.-во ВГТУ,
1995.Емельянов
В. В., Курейчик В. В., Курейчик В. М. Теория и практика эволюционного
моделирования. — М.:ФизМатЛит, 2003. — 432 с.
Приложение
program Genetic;
uses Crt;
const
N = 30; { Количество прогонов }
MaxPop =
100; { Максимальное число поколений }
LenChrome = 20; { Число битов на один кодируемый параметр }
dim = 2; { Размерность пространства поиска }
P1 =
40; { Количество поколений }
P2 = 80;
S1 = 8;
{ Размер популяции }
S2 = 12;
S3 = 20;
PMutation = 0.01; {
Вероятность скрещивания }
PCross =
0.9; { Вероятность мутации }
type
Allele = boolean;
{Алель - позиция в битовой строке }
Chromosome
= array [1..LenChrome * Dim] of Allele; { Битовая строка }
Fenotype =
array [1..Dim] of double;
Individual =
record
Chrom:
Chromosome; { Генотип = битовая строка }
x: Fenotype; { Фенотип = массив вещественных
координат точки в пространстве поиска }
Fitness: double; {
Значение целевой функции }
end;
Population =
array [1..maxpop] of Individual;
const
{массив максимальных значений для координат
точки в пространстве поиска}
xMax: Fenotype = ( 5.12, 5.12);
{массив минимальных значений для координат
точки в пространстве поиска}
xMin: Fenotype = (-5.12, -5.12);
var
{ Три непересекающихся популяции - старая,
новая и промежуточная }
OldPop, NewPop, IntPop: Population;
{ Глобальные целые переменные}
PopSize,
Gen, h, s, b: integer;
{ Счетчики
мутаций, скрещиваний и количество поколений }
NMutation, NCross, NGen: integer;
{ Статистические переменные }
Avg,
Min, Max, BestMin, Result, SumFitness: double;
{ Функция }
function ObjFunc(x: Fenotype): double;
begin
ObjFunc :=
Sqr(x[1]) + Sqr(x[2]);
end;
{
Подбрасывание монетки - true если орел
}
function Flip(Probability: double): boolean;
begin
Flip := Random
<= Probability;
end;
{
Декодирование строки в массив вещественных
координат в пространстве поиска }
procedure Decode(Chrom: Chromosome; var x: fenotype);
var i, j, f, accum: longint;
begin
for i := 1 to
Dim do
begin
Accum := 0;
f := 1;
for j := 1 +
LenChrome * (i - 1) to LenChrome + LenChrome * (i - 1) do
begin
if
Chrom[j] then Inc(Accum, f);
f := f *
2;
end;
x[i] :=
xmin[i] + (xmax[i] - xmin[i]) * Accum / (f - 1);
end
end;
{ Расчет
статистических величин }
procedure Statistics(var Max, Avg, Min: double; Pop:
Population);
var j :integer;
SumFitness:
double;
begin
SumFitness :=
Pop[1].Fitness;
Min :=
Pop[1].Fitness;
Max :=
Pop[1].Fitness;
for j := 2 to
PopSize do
with
Pop[j]
do
begin
{ Накопление суммы значений функции
пригодности }
SumFitness
:= SumFitness + Fitness;
if Fitness
> Max then Max := Fitness; { Новое значение Max }
if Fitness
< Min then Min := Fitness; { Новое значение Min }
end;
Avg :=
SumFitness / PopSize; { Расчет
среднего }
end;
{ Инициализация
начальной популяции случайным образом }
procedure InitPop;
var i, j:
integer;
begin
for i := 1 to
PopSize do
with
OldPop[i] do
begin
for j := 1
to LenChrome * Dim do
Chrom[j]
:= Flip(0.5); { Бросок монеты }
Decode(Chrom, x); {
Декодирование строки }
{ Вычисление начальных значений функции
пригодности }
Fitness
:= ObjFunc(x);
end;
end;
{ Оператор
отбора (селекции) }
procedure Select;
var ipick, i: integer;
{ Процедура перемешивания популяции в
процессе отбора }
procedure
Shuffle(var pop: Population);
var
i, j:
integer;
ind0:
Individual;
begin
for i := 1
to PopSize do
begin
j := 1 +
Random(i);
{
Перемешиваем }
ind0 :=
pop[i];
pop[i] :=
pop[j];
pop[j] :=
ind0;
end;
end;
{ Отбор
наилучших особей для популяции для перехода в следующее поколение }
function
Select1: integer;
var i, j, m:
integer;
begin
if ipick
> PopSize then
begin
Shuffle(OldPop);
ipick :=
1;
end;
i := ipick;
j := ipick +
1;
if
OldPop[j].Fitness < OldPop[i].Fitness then
m := j
else
m := i;
Inc(ipick,
2);
Select1 :=
m;
end;
begin
ipick := 1;
for i := 1 to
PopSize do
IntPop[i] :=
OldPop[Select1];
OldPop := IntPop;
end;
{ Оператор
инверсионной мутации }
function Mutation(alleleval: Allele; var
NMutation:integer): Allele;
begin
Mutation :=
alleleval;
if
Flip(PMutation) then { Мутация с вероятностью PMutation }
begin
Inc(NMutation); { Наращиваем
счетчик мутаций }
Mutation :=
not alleleval; { Совершаем мутацию }
end;
end;
{ Оператор
одноточечного скрещивания }
procedure Crossover(var Parent1, Parent2, Child1,
Child2: Chromosome;
flchrom: integer; var NCross, NMutation: integer);
var i, jcross: integer;
begin
if
Flip(PCross) then { Выполняется скрещивание с вероятностью PCross }
begin
{ Определение точки сечения в диапазоне
между 1 и flchrom-1 }
jcross := 1 + Random(flchrom);
Inc(NCross); { Наращивание счетчика скрещиваний }
{ Первая часть обмена, 1 в 1 и 2 в 2 }
{ Обмениваем часть до точки сечения }
for
i := 1 to jcross do
begin
{ Заодно и
мутируем с вероятностью pmutation }
{
Первый потомок }
Child1[i]
:= Mutation(Parent1[i], NMutation);
{ Второй
потомок }
Child2[i]
:= Mutation(Parent2[i], NMutation);
end;
{ Вторая часть обмена, 1 в 2 и 2 в 1 }
{ Обмениваем часть после точки сечения }
for
i := jcross + 1 to flchrom do
begin
{ Заодно и мутируем с вероятностью pmutation }
{
Первый потомок }
Child1[i]
:= Mutation(Parent2[i], NMutation);
{ Второй
потомок }
Child2[i]
:= Mutation(Parent1[i], NMutation);
end;
end;
end;
{
Генерирование нового поколения при помощи отбора, скрещивания и мутации }
{
Предполагается, что популяция имеет четный размер }
procedure Generation;
var i: integer;
begin
Select;
i := 1;
repeat
{ Выполняются отбор, скрещивание и мутация
пока полностью не
сформируется новая популяция newpop }
{ Скрещивание и мутация - мутация вставлена
в процедуру скрещивания }
Crossover(OldPop[i].Chrom,
OldPop[i + 1].Chrom,
NewPop[i].Chrom, NewPop[i + 1].Chrom,
LenChrome * Dim, NCross, NMutation);
{ Декодирование строки и вычисление
пригодности }
with
NewPop[i] do
begin
Decode(Chrom, x);
Fitness :=
ObjFunc(x);
end;
with
Newpop[i + 1] do
begin
Decode(Chrom, x);
Fitness :=
ObjFunc(x);
end;
Inc(i, 2);
until i >
PopSize;
end;
begin
ClrScr; { Очистка экрана }
Randomize; { Инициализация генератора случайных
чисел }
for
h := 1 to 2 do { Цикл
выбора количества поколений }
begin
If
h = 1 then NGen := P1; {
Количество поколений }
If h
= 2 then NGen := P2;
for
s := 1 to 3 do { Цикл выбора размера популяции }
begin
If s = 1
then PopSize := S1; { Размеры популяций }
If s = 2
then PopSize := S2;
If s = 3
then PopSize := S3;
Result := 0; { Инициализация переменной ответа }
for
b := 1 to N
do { Прогоняется N раз для повышения достоверности }
begin
NMutation := 0; {
Инициализация счетчика мутация }
NCross := 0; { Инициализация
счетчика скрещиваний }
InitPop; { Создание
начальной популяции }
Statistics(Max, Avg, Min, OldPop);
BestMin := Min;
Gen := 1; { Установка
счетчика поколений в 0 }
repeat { Главный
итерационный цикл }
Generation;
Statistics(Max, Avg, Min, NewPop);
if Min
< BestMin then BestMin := Min;
OldPop := NewPop;
{переход на новое поколение }
Inc(Gen);
until
Gen > PopSize;
Result
:= Result + Min;
end;
Writeln('Количество
поколений -', NGen);
Result := Result / N; { Находим среднее значение ответа }
WriteLn('Размер
популяции, особей - ', PopSize);
WriteLn('Средний
минимум вещественной функции = ', Result: 12);
WriteLn('Лучший минимум вещественной функции = ', BestMin: 12);
end; { Цикл
выбора количества популяций }
end; { Цикл
выбора количества поколений }
Write('Для
завершения программы нажмите любую клавишу');
ReadKey;
End.