1626434812-e667f6b6e7e69d3a0798830a58e9075b (844135), страница 43
Текст из файла (страница 43)
В этом и заключается основной смысл работы генетического алгоритма — улучшить популяцию решений по сравнению с исходной. После завершения работы генетического алгоритма из конечной популяции выбирается та особь, которая дает максимальное (или минимальное) значение целевой функции и является, таким образом, результатом работы генетического алгоритма. За счет того, что конечная популяция лучше исходной, полученный результат представляет собой улучшенное решение. 8.3 Примеры решения задач Описав смысл терминов, понятий и характеристик генетического алгоритма, а также процесс его работы, рассмотрим примеры решения некоторых оп- Глава 8.
Генетические алгоритмы тимизационных задач с использованием генетических алгоритмов, чтобы про- иллюстрировать рассмотренные положения. Таблица 3.1. Значение целевой функции Вероятность участия в процессе размножения № строки Код 01100 12 Предположим, что оператор отбора выбрал для производства потомков две пары строк (1, 2) и (2, 4). Работа оператора скрещивания проиллюстрирована в таблице 3.2. При этом в каждой паре разбиение на подстроки происходит независимо. Поиск максимума одномерной функции Пусть имеется набор натуральных чисел от 0 до 31 и функция, определенная на этом наборе чисел, й;х) = х.
Требуется найти максимальное значение функции. Задача, конечно, тривиальна и не требует применения столь изощренных методов поиска, но мы решаем ее лишь для иллюстрации функционирования генетического алгоритма 1521. В качестве кода будем использовать двоичное представление аргументов функции. Это положение представляет собой фенотип нашего алгоритма. Сам код будет представлять собой двоичную строку из 5 бит. Это генотип алгоритма Целевой функцией будет непосредственно сама рассматриваемая функция, аргументом которой является число, чье двоичное представление использует алгоритм.
Определим некоторые характеристики генетического алгоритма. Пусть размер популяции будет 4, вероятность мутации 0,001, сам процесс мутации заключается в инверсии одного из битов строки, выбираемого случайно по равномерному закону. Оператор скрещивания и отбора аналогичны описанным выше. Поскольку задача является простейшей, будем считать, что алгоритм не использует элитизм. Пусть на основе равномерного распределения создана исходная популяция из четырех особей, представленная в таблице 3.1. Таблица 8.2.
Потомки Значение целевой функции для потомков № строки Родители О ~ 1011 00010 2 1 ~ 0010 11011 27 100 1 10 10000 16 011 1 00 01110 14 Пусть оператор мутации, несмотря на низкую вероятность, сработал для младшего бита потомка в строке 3, и данный код изменил свое значение с 10000 на 10001. Таким образом, популяция за счет порожденных потомков расширилась до восьми особей, представленных в таблице 8.3. Значение целевой функции Код Исходная популяция 01011 10010 18 00010 2 01100 Порожденные потомки 00010 2 11011 27 10001 17 01110 Оператор редукции далее сократит популяцию до исходного числа особей, исключив из нее те, чье значение целевой функции минимально.
То есть будут исключены строки 1, 3, 4 и 5, и популяция первого поколения примет вид, представленный в таблице 8.4. Таблица 8.3. № строки Базы данных. Интеллектуапьная обработка информации Глава 8. Генетические алгарит'ны Таблица 8.4. № строки Код Значение целевой Вероятность участия функции в процессе размножения 10010 18 На этом шаг работы генетического алгоритма закончится.
Очевидно, что даже за эту одну итерацию качество популяции значительно возросло. Если в исходной популяции среднее значение целевой функции было 10,75, а ее минимальное значение составляло 2. то в популяции первого поколения среднее значение возросло до 19, а минимальное значение составило 14. Лучшее же решение увеличилось с 18 до 27 при оптимальном решении 31. Таким образом, данный пример наглядно иллюстрирует процесс улучшения как популяции в целом, так и наилучшего решения в частности в результате работы генетического алгоритма.
Решение задачи каммивояжера. Задача коммивояжера является классической оптимизационной задачей. Суть ее заключается в следующем. Дано множество из п городов и матрица расстояний между ними или стоимостей переезда (в зависимости от интерпретации). Цель коммивояжера — объехать все эти города по кратчайшему пути или с наименьшими затратами на поездку. Причем в каждом городе он должен побывать один раз и свой путь закончить в том же городе, откуда начал. Для решения предлагается следующая задача: имеется пять городов, стоимость переезда между которыми представлена следующей матрицей 1521: 04629 40329 б 3 О 5 9 2 2 5 О 8 99980 Для решения задачи применим следующий генетический алгоритм. Решение представим в виде перестановки чисел от 1 до 5, отображающей последовательность посещения городов.
А значение целевой функции будет равно сто- в за Базы данных. Интеллектуальная обработка информации имости всей поездки, вычисленной в соответствии с вышеприведенной матрицей. Сразу заметим, что одним из оптимальных решений задачи является последовательность 514235 стоимостью 25.
В качестве оператора отбора будем использовать традиционный оператор, применявшийся в предыдущем примере. При этом заметим, что чем меньше значение целевой функции, тем лучше. В качестве оператора скрещивания выберем более изощренную процедуру, похожую на двухточечный оператор скрещивания. Поясним его работу на примере. Пусть есть две родительские перестановки (12345) и (34521). Случайно и равновероятно выбираются две точки разрыва, Для примера возьмем ситуацию, когда первая точка разрыва находится между первым и вторым элементами перестановки, а вторая точка — между четвертым и пятым: (Ц234~5), (3~452~ Ц. На первом этапе перестановки обмениваются фрагментами, заключенными между точками разрыва: (~~452~~), (~~234Г).
На втором этапе вместо звездочек вставляются соответствующие числа из исходной родительской перестановки, начиная со второго числа выделенного фрагмента и пропуская уже имеющиеся в новой перестановке числа. В данном случае в первой перестановке (1~234~5) таким начальным числом является 3, за ним идет 4, которое есть в новой перестановке, и мы его пропускаем, также пропускаем число 5, переходим на начало перестановки и выбираем число 1, В итоге вместо (~~452~~) получаем «34521), аналогично из (3~452~1) и (~~234~~) получаем (52341). Оператор мутации будет представлять собой случайную перестановку двух чисел в хромосоме, также выбранных случайно по равномерному закону. Вероятность мутации 0,01.
Размер популяции выберем равным 4. Исходная популяция представлена в таблице 8.5. Таблица 8.5. № строки Код Значение целевой Вероятность участия функции в процессе размножения 29/122 Пусть для скрещивания были выбраны следующие пары: (1, 3) и (2, 4). В результате были получены потомки, представленные в таблице 8.6. Глава 8. Генетические алгоритмы Таблица 8.6. Значение целевой функции для потомков № строки Родители Потомки 1123145 5 ~ 43 1 12 51431 12 1123154 мутация 13254 2 1 143 ) 5 4 ~ 31215 4~312~5 2114315 Пусть для потомка 112354) сработал оператор мутации и обменялись местами числа 2 и 3. В данном случае строка (12354) изменилась и приняла значение (13254). Популяция первого поколения после отсечения худших особей в результате работы оператора редукции приняла вид, представленный в таблице 8.7.
3 (н) 28/111 Пусть для получения второго поколения были выбраны следующие пары строк: ~1, 4) и (2, 3). И в результате были получены потомки, показанные в таблице 8.8. Таблица 8.8. №строки Родители Потомки Значение целевой функции для потомков 1123~45 1214~35 29 1214135 1123~45 29 1211435 113 1 452 32 1131254 1 211354 29 Таблица 8.7. № строки Код Значение целевой Вероятность участия функции в процессе размножения Базы даннык.
Интеллектуальная обработка информации Популяция второго поколения после отсечения худших особей приняла вид, показанный в таблице 8.9. Таблица 8.9. № строки Код Значение целевой Вероятность участия функции в процессе размножения Таким образом, после двух итераций значение целевой функции для лучшего решения изменилось с 29 на 28, среднее значение изменилось с 30,5 до 28,75, а общее качество с 122 до ! 11. То есть также налицо незначительное, но улучшение популяции Обучение нейронной сети Обучение нейронных сетей является одной из основных областей приме- нения генетических алгоритмов [54]. Для дальнейшего описания рассмотрим в общем виде, что представляет собой задача обучения нейронной сети. Для построения и обучения нейронной сети обычно создается набор при- меров, который представляет собой совокупность векторов вида (Х,У), где Х = (х,, х,, ..., х ) — значения всех входов нейронной сети, а У = (у,, у„..., у„)— значения всех выходов нейронной сети, которые должны получаться в процес- се ее работы.
Структура эталонных векторов задает одновременно количество входных и выходных нейронов (в данном случае и и ш соответственно). Целью обучения нейронной сети является достижение такой ситуации, когда при подаче на вход сети любого вектора Х из набора примеров на ее выходе получается выходной вектор У'„отличающийся от эталонного вектора У не более чем на заданную заранее и вычисляемую определенным образом величину Ь. Процесс обучения нейронной сети заключается в подборе значений всех ее характеристик таким образом, чтобы отличия выходных векторов от эталон- ных не превышали заранее установленной величины.
Основными характеристиками нейронной сети являются: ° количество скрытых слоев, количество нейронов в каждом из скрытых слоев, ° веса входов каждого из скрытых и выходных нейронов ~ж, Ц ° функция активации Г.0 для каждого скрытого и выходного нейрона. l Глава 8. Генетические алгоритмы Таким образом, мы можем обобщенно сформулировать оптимизационную задачу обучения нейронной сети.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
