Автор работы: Пользователь скрыл имя, 04 Февраля 2013 в 16:23, курсовая работа
В нашей жизни мы регулярно сталкиваемся с необходимостью решения
оптимизационных и прогностических задач. Так, например, доход любой
компании определяется качеством этих решений - точностью прогнозов и
оптимальностью выбранных стратегий.
Введение:
1. Теория алгоритмов. Задача коммивояжера.
2. Генетические алгоритмы. Общее описание. Математический аппарат
3. Непрерывные генетические алгоритмы. Математический аппарат.
4. Заключение.
5. Список использованной литературы.
функционирование механизмов генетического алгоритма производится на уровне
генотипа,
позволяя обойтись без
что и
обуславливает его широкое
В наиболее
часто встречающейся
представления генотипа объекта применяются битовые строки. При этом
каждому
атрибуту объекта в фенотипе
соответствует один ген в
объекта.
Ген представляет собой
длины, которая представляет собой значение этого признака.
Кодирование признаков, представленных целыми числами
Для кодирования
таких признаков можно
битовое значение этого признака. Тогда нам будет весьма просто
использовать
ген определенной длины,
возможных значений такого признака. Но, к сожалению, такое кодирование не
лишено
недостатков. Основной
числа отличаются в значениях нескольких битов, так например числа 7 и 8 в
битовом представлении различаются в 4-х позициях, что затрудняет
функционирование
генетического алгоритма и
для его сходимости. Для того, чтобы избежать эту проблему лучше
использовать кодирование, при котором соседние числа отличаются меньшим
количеством позиций, в идеале значением одного бита. Таким кодом является
код Грея, который целесообразно использовать в реализации генетического
алгоритма. Значения кодов Грея рассмотрены в таблице ниже:
+-----------------------------
|
Двоичное кодирование
|-----------------------------
| Десятичный | Двоичное | Шестнадцатеричное | Десятичный | Двоичное | Шестнадцатеричное |
| код | значение | значение | код | значение | значение |
|------------+----------+-----
| 0 | 0000 | 0h | 0 | 0000 | 0h |
|------------+----------+-----
| 1 | 0001 | 1h | 1 | 0001 | 1h |
|------------+----------+-----
| 2 | 0010 | 2h | 3 | 0011 | 3h |
|------------+----------+-----
| 3 | 0011 | 3h | 2 | 0010 | 2h |
|------------+----------+-----
| 4 | 0100 | 4h | 6 | 0110 | 6h |
|------------+----------+-----
| 5 | 0101 | 5h | 7 | 0111 | 7h |
|------------+----------+-----
| 6 | 0110 | 6h | 5 | 0101 | 5h |
|------------+----------+-----
| 7 | 0111 | 7h | 4 | 0100 | 4h |
|------------+----------+-----
| 8 | 1000 | 8h | 12 | 1100 | Ch |
|------------+----------+-----
| 9 | 1001 | 9h | 13 | 1101 | Dh |
|------------+----------+-----
| 10 | 1010 | Ah | 15 | 1111 | Fh |
|------------+----------+-----
| 11 | 1011 | Bh | 14 | 1110 | Eh |
|------------+----------+-----
| 12 | 1100 | Ch | 10 | 1010 | Ah |
|------------+----------+-----
| 13 | 1101 | Dh | 11 | 1011 | Bh |
|------------+----------+-----
| 14 | 1110 | Eh | 9 | 1001 | 9h |
|------------+----------+-----
| 15 | 1111 | Fh | 8 | 1000 | 8h |
+-----------------------------
Таблица 1. Соответствие десятичных кодов и кодов Грея.
Таким
образом, при кодировании
тетрады и каждую тетраду преобразуем по коду Грея.
В практических
реализациях генетических
необходимости преобразовывать значения признака в значение гена. На
практике имеет место обратная задача, когда по значению гена необходимо
определить значение соответствующего ему признака.
Таким образом, задача декодирования значения генов, которым соответствуют
целочисленные признаки, тривиальна.
Кодирование признаков, которым соответствуют числа с плавающей точкой
Самый простой
способ кодирования, который
использовать битовое представление. Хотя такой вариант имеет те же
недостатки, что и для целых чисел. Поэтому на практике обычно применяют
следующую последовательность действий:
1. Разбивают весь интервал допустимых значений признака на участки с
требуемой точностью.
2. Принимают
значение гена как
интервала (используя код Грея)
3. В
качестве значения параметра
принимают число, являющиеся
этого интервала.
Рассмотрим
вышеописанную
Допустим, что значения признака лежат в интервале [0,1]. При кодировании
использовалось разбиение участка на 256 интервалов. Для кодирования их
номера нам потребуется таким образом 8 бит. Допустим значение гена:
00100101bG (заглавная буква G показывает, что используется кодирование по
коду Грея). Для начала, используя код Грея, найдем соответствующий ему
номер интервала: 0x01 graphic
. Теперь посмотрим, какой интервал ему соответствует… После несложных
подсчетов получаем интервал 0x01 graphic
. Значит
значение нашего параметра
.
Основные генетические операторы
Как известно в теории эволюции важную роль играет то, каким образом
признаки родителей передаются потомкам. В генетических алгоритмах за
передачу признаков родителей потомкам отвечает оператор, который
называется
скрещивание (его также
Этот оператор определяет передачу признаков родителей потомкам. Действует
он следующим образом:
1. из
популяции выбираются две
2. определяется
(обычно случайным образом)
3. потомок определяется как конкатенация части первого и второго
родителя.
Рассмотрим функционирование этого оператора:
+---------------------------+
| Хромосома_1: | 0000000000 |
|--------------+------------|
| Хромосома_2: | 1111111111 |
+---------------------------+
Допустим разрыв происходит после 3-го бита хромосомы, тогда
+-----------------------------
| Хромосома_1: | 0000000000 | >> | 000 | 1111111 | Результирующая_хромосома_1 |
|--------------+------------+-
| Хромосома_2: | 1111111111 | >> | 111 | 0000000 | Результирующая_хромосома_2 |
+-----------------------------
Затем с вероятностью 0,5 определяется одна из результирующих хромосом в
качестве потомка.
Следующий генетический оператор предназначен для того, чтобы поддерживать
разнообразие
особей с популяции. Он
использовании данного оператора каждый бит в хромосоме с определенной
вероятностью инвертируется.
Кроме того, используется еще и так называемый оператор инверсии, который
заключается в том, что хромосома делится на две части, и затем они
меняются местами.
Схематически это можно
+-----------------------------
| 000 | 1111111 | >> | 1111111 | 000 |
+-----------------------------
В принципе
для функционирования
двух
генетических операторов, но на
практике применяют еще и
дополнительные операторы или модификации этих двух операторов. Например,
кроссовер может быть не одноточечный (как было описано выше), а
многоточечный,
когда формируется несколько
точек разрыва (чаще всего две)
Кроме того, в некоторых реализациях алгоритма оператор мутации
представляет собой инверсию только одного случайно выбранного бита
хромосомы.
Схема
функционирования
Теперь,
зная как интерпретировать
функционирования генетического алгоритма. Рассмотрим схему
функционирования генетического алгоритма в его классическом варианте.
1. Инициировать начальный момент времени 0x01 graphic
. Случайным
образом сформировать
особей.
0x01 graphic
2. Вычислить
приспособленность каждой
и популяции в целом 0x01 graphic
(также иногда называемую
определяет насколько хорошо
подходит особь, описанная
хромосомой, для решения задачи.
3. Выбрать особь 0x01 graphic
из популяции. 0x01 graphic
4. С определенной вероятностью (вероятностью кроссовера 0x01 graphic
) выбрать вторую особь из
и произвести оператор кроссовера 0x01 graphic
.
5. С определенной вероятностью (вероятностью мутации 0x01 graphic
) выполнить оператор мутации. 0x01 graphic
.
6. С определенной вероятностью (вероятностью инверсии 0x01 graphic
) выполнить оператор инверсии 0x01 graphic
.
7. Поместить полученную хромосому в новую популяцию 0x01 graphic
.
8. Выполнить операции, начиная с пункта 3, k раз.
9. Увеличить номер текущей эпохи 0x01 graphic
.
10. Если выполнилось условие останова, то завершить работу, иначе переход
на шаг 2.
Теперь рассмотрим
подробнее отдельные этапы
Наибольшую роль в успешном функционировании алгоритма играет этап отбора
родительских хромосом на шагах 3 и 4. При этом возможны различные
варианты. Наиболее
часто используется метод
При использовании
такого метода вероятность
ее приспособленностью, то есть 0x01 graphic
. Использование этого метода приводит к тому, что вероятность передачи
признаков
более приспособленными
используемый
метод - турнирный отбор. Он
заключается в том, что
выбирается несколько особей из популяции (обычно 2) и победителем
выбирается
особь с наибольшей
реализациях
алгоритма применяется так
которая
заключается в том, что особи
с наибольшей
гарантировано переходят в новую популяцию. Использование элитизма обычно
позволяет
ускорить сходимость
использования стратегии элитизма в том, что повышается вероятность
попадания алгоритма в локальный минимум.
Другой важный момент - определение критериев останова. Обычно в качестве
них применяются
или ограничение на
функционирования
алгоритма, или определение
сравнивания приспособленности популяции на нескольких эпохах и остановки
при стабилизации этого параметра.
3. Непрерывные генетические алгоритмы.
Фиксированная длина хромосомы и кодирование строк двоичным алфавитом
преобладали
в теории генетических
когда были получены теоретические результаты о целесообразности
использования именно двоичного алфавита. К тому же, реализация такого
генетического алгоритма на ЭВМ была сравнительно легкой. Все же, небольшая
Информация о работе Генетические алгоритмы и их практическое применение