4.11.1. Примеры оптимизации функции с помощью программы EvolverПрежде чем перейти к примерам, дадим характеристику генетическим операторам, используемым программой Evolver в задачах оптимизации функции. Скрещивание. Это равномерное скрещивание (uniform crossover), определенное аналогично примененному в п. 4.8.3, но для хромосом, состоящих из генов с действительными аллелями. Скрещивание производится в соответствии с так называемым показателем скрещивания (crossover rate), определяющим, какой процент генов потомок унаследует от каждого родителя. В программе Evolver показатель скрещивания вводится пользователем и представляет собой число из интервала от 0,01 до 1,0. Например, значение показателя скрещивания 0,8 означает, что потомок получит около 80 % генов со значениями (аллелями) такими же, как у первого родителя, а оставшееся количество (порядка 20 %) - унаследует от второго родителя. Если показатель скрещивания равен 1, то никакого скрещивания практически не происходит, а образуются только так называемые клоны, т.е. хромосомы, идентичные родителям. По умолчанию в программе Evolver применяется значение показателя скрещивания, равное 0,5, что означает наследование примерно одинакового количества генов от каждого родителя. Мутация. Каждый ген в хромосоме представляет один параметр задачи. Следовательно, аллели соответствуют фенотипам, т.е. значениям конкретных переменных. Для каждого гена случайным образом выбирается число из интервала от 0 до 1, которое сравнивается с так называемым показателем мутации (mutation rate). Если разыгранное число меньше введенного значения показателя или равно ему, то выполняется мутация данного гена. Эта операция заключается в замене значения гена другим, случайно выбранным числом из области допустимых значений параметра, соответствующего мутирующему гену. Вводимое пользователем значение показателя мутации представляет собой число из интервала от 0,0 до 1,0. Чем больше это значение, тем большее количество генов подвергается мутации. Если показатель мутации равен 1, то мутации подвергаются 100% генов, выбираемых случайным образом. С учетом того, что в программе Evolver мутация всегда производится после скрещивания, задание показателя мутации равным 1 означает, что в этом случае эффект скрещивания не имеет никакого значения. Очевидно, что если показатель мутации равен 0, то мутация вообще не производится. Как правило, значение показателя мутации задается в пределах от 0,06 до 0,2. Отметим, что определяемый таким образом показатель мутации представляет собой аналог вероятности мутации В классическом генетическом алгоритме на каждой итерации обновляется вся популяция, что соответствует формированию очередного поколения. Применительно к программе Evolver можно говорить о последовательных «тактах» (trials) ее выполнения, причем на каждом такте изменяется только одна особь. Если популяция насчитывает Пример 4.21 С помощью программы Evolver найти минимум функции для целочисленных Вычисления производились для популяции размерностью С помощью программы Evolver сформирована следующая исходная популяция:
После шести «тактов», т.е. для Рис. 4.68. Популяция особей для Отметим, что в популяцию не входит особь Рис. 4.69. Популяция особей для Рис. 4.70. Популяция особей для На последнем месте (№ п/п = 6) размещается «наилучшая к данному моменту» особь, имеющая наименьшее значение функции приспособленности. На первом месте (№ п/п = 1) показана вновь введенная в популяцию особь. На рис. 4.69 это копия особи На рис. 4.71 и 4.72 представлены популяции для Рис. 4.71. Популяция особей для Рис. 4.72. Популяция особей для На рис. 4.73 показана популяция для Рис. 4.73. Популяция особей для Получение «наилучшего» решения, равного Следующий пример представляет собой обобщение предыдущего примера за счет увеличения количества переменных и расширения пространства поиска. Пример 4.22 С помощью программы Evolver найти минимум функции для целочисленных Вычисления производились для популяции размерностью Рис. 4.74. Начальные значения переменных и значение функции для примера 4.22, представленные в табличном процессоре Excel. В исходную популяцию включены 50 особей, первая из которых содержит гены со значениями, показанными на рис. 4.74, а остальные хромосомы сгенерированы случайным образом (гены имеют действительные значения из интервала от -10 до 10). Длина каждой хромосомы равна 6 и совпадает с количеством переменных Рис. 4.75. Изменение «наилучшего» (вверху) и среднего (внизу) значения функции приспособленности для примера 4.22. Рис. 4.76. Столбчатая диаграмма значений функции приспособленности особей в популяции при Рис. 4.77. Значения переменных и функции для примера 4.22 при Рис. 4.78. Значения переменных и функции для примера 4.22 при Рис. 4.79. Значения переменных и функции для примера 4.22 при Рис. 4.80. Значения переменных и функции для примера 4.22 при Повторное возобновление этого алгоритма при тех же начальных данных (рис. 4.74), но других случайных значениях остальных членов исходной популяции дает совершенно иной набор «наилучших» значений переменных Следующие примеры связаны с минимизацией более сложной функции 9 переменных, а именно - функции погрешности нейронной сети, реализующей логическую систему XOR. Пример 4.23 С помощью программы Evolver найти оптимальный набор весов нейронной сети, изображенной на рис. 4.2 (пример 4.3), если значения весов лежат в интервале от -5 до 5. Решение этой задачи заключается в подборе такого комплекса значений весов относительно определенных выше девяти весов, где Примем, что Задача моделировалась в табличном процессоре Excel, а оптимизация выполнялась при помощи генетического алгоритма программы Evolver. Для популяции с размерностью, равной 50, при значениях показателя скрещивания равного 0,5 и показателя мутации равного 0,06 после примерно 30000 «тактов» получено «наилучшее решение» в виде набора весов, показанного на рис. 4.81. Минимальное значение абсолютной погрешности Рис. 4.81. «Наилучший» набор весов из интервала Необходимо отметить, что полученное «наилучшее решение» близко набору весов Рис. 4.82. Другой «наилучший» набор весов для примера 4.23. Следующие примеры относятся к той же задаче, однако при расширенном диапазоне изменения весов. Пример 4.24 С помощью программы Evolver найти оптимальный набор весов нейронной сети, изображенной на рис. 4.2 (пример 4.3), если значения весов лежат в интервале от -10 до 10. При начальных значениях, совпадающих с приведенными в примере 4.23, было проведено три сеанса вычислений. Через 30000 «тактов» в первом, втором и третьем сеансах получены «наилучшие» решения, показанные на рис. 4.83, 4.84 и 4.86 соответственно. На рис. 4.85 изображены графики изменения «наилучшего» (нижняя кривая) и среднего (верхняя кривая) значения функции приспособленности для этого примера после 505 «тактов». Функция приспособленности для системы XOR задается формулой расчета погрешности Рис. 4.83. «Наилучший» набор весов из интервала Рис. 4.84. Другой «наилучший» набор весов для примера 4.24. Рис. 4.85. Изменение «наилучшего» и среднего значения функции приспособленности для примера 4.22. Рис. 4.86. Еще один «наилучший» набор весов для примера 4.24. Заметим, что минимальная погрешность во всех трех случаях (рис. 4.83, 4.84 и 4.86) оказывается значительно меньше, чем для интервала изменения от -5 до 5, рассмотренного в примере 4.23 (рис. 4.81 и 4.82). Пример 4.25 С помощью программы Evolver найти оптимальный набор весов нейронной сети, изображенной на рис. 4.2 (пример 4.3), если значения весов лежат в интервале от -15 до 15. Применялся тот же генетический алгоритм программы Evolver, что и в предыдущих примерах, но для расширенного интервала изменения весов. После 30000 «тактов» получено «наилучшее решение», показанное на рис. 4.87. Рис. 4.87. «Наилучший» набор весов из интервала Повторное выполнение того же алгоритма при тех же начальных условиях через 30000 «тактов» дало «наилучший» набор весов, представленный на рис. 4.88. Главное различие между решениями на рис. 4.87 и 4.88 заключается в том, что в первом случае веса Рис. 4.88. Другой «наилучший» набор весов для примера 4.25. Рис. 4.89. Еще один «наилучший» набор весов для примера 4.25 (получен после примерно 12000 «тактов»). Пример 4.26 С помощью программы Evolver найти оптимальный набор весов нейронной сети, изображенной на рис. 4.2 (пример 4.3), если значения весов лежат в интервале от -20 до 20. Это та же задача, что и в предыдущих примерах, однако интервал изменения весов значительно расширен. Задача решалась при той же размерности популяции и таких же значениях показателей скрещивания и мутации, как и в предыдущих примерах. Столбчатая диаграмма на рис. 4.90 демонстрирует значения функции приспособленности особей в популяции после примерно 1500 «тактов». Конечно, это значения в интервале от 0 до 1. На рис. 4.91 изображены графики изменения «наилучшего» (нижняя кривая) и среднего (верхняя кривая) значения функции приспособленности для этого примера после примерно 1500 «тактов». Единица на временной оси этого графика соответствует 20 «тактам». «Наилучшее на данный момент» (после 1502 «тактов») значение функции приспособленности составляет Рис. 4.90. Столбчатая диаграмма значений функции приспособленности особей в популяции при Рис. 4.91. Изменение «наилучшего» (внизу) и среднего (вверху) значения функции приспособленности для примера 4.26. Рис. 4.92. «Наилучший» набор весов из интервала Рис. 4.93. «Наилучший» набор весов из интервала Рис. 4.94. Другой «наилучший» набор весов для примера 4.26. Отметим, что «наилучшее решение» на рис. 4.94 тоже представляет собой одну из допустимых комбинаций весов системы XOR [31], поскольку оно стремится к оптимальному решению, в котором Из примеров 4.23 - 4.26 следует вывод, что чем больше интервал изменения весов, тем меньше минимальное значение погрешности. Поэтому для получения нейронной сети, которая сможет наиболее точно реализовать систему XOR (т.е. для которой разность между эталонным и расчетным выходными значениями будет минимальной), необходимо подбирать веса из как можно более широкого интервала допустимых значений. Очевидно, что подбор этих весов должен быть оптимальным и минимизировать погрешность так, как это делалось в примерах 4.23 - 4.26. Если бы требовалось выбирать значения весов из интервала, более узкого, чем Рис. 4.95. «Наилучший» набор весов из интервала Пример 4.27 С помощью программы Evolver найти оптимальный набор весов нейронной сети, изображенной на рис. 4.2 (пример 4.3), если значения весов лежат в интервале от -7 до 8. Начальные значения весов, составляющие генотип одной из особей исходной популяции, представлены на рис. 4.96. Видно, что значения Рис. 4.96. Начальные значения весов для примера 4.27. Для решения задачи применялся тот же генетический алгоритм при той же размерности популяции и тех же показателях скрещивания и мутации, что и в предыдущих примерах. Всего лишь через 96 «тактов» получены наилучшие значения функции приспособленности конкретных особей в популяции, показанные на рис. 4.97 (столбчатая диаграмма). В свою очередь, на рис. 4.98 представлена таблица, содержащая генотипы всех 50 особей этой популяции (состоящие из девяти действительных чисел, соответствующих конкретным весам) и значения их функции приспособленности, размещенные в первой колонке. Рис. 4.97. Столбчатая диаграмма значений функции приспособленности особей в популяции при Рис. 4.98. Популяция особей при Обратим внимание на то, что начальная хромосома с аллелями, равными значениям весов из рис. 4.96, расположена в средней части этой таблицы и обозначена «Организм 25». Следует помнить, что особи в популяции упорядочены от «наихудшего» к «наилучшему». Последняя особь («Организм 50») – это хромосома, «наилучшая на данный момент», т.е. после 96 «тактов». Значения весов, входящих в состав этой хромосомы, показаны на рис. 4.99 вместе с выходными значениями для конкретных пар входов и значением минимизируемой погрешности. Итак, после 96 «тактов» получен исключительно хороший результат. Рис. 4.99. Набор весов, полученный при При повторном выполнении этой же программы с самого начала при том же исходном наборе весов (рис. 4.96) через примерно 10000 «тактов» получена погрешность Рис. 4.100. Результат, полученный после 24000 «тактов» при повторном запуске программы Evolver для примера 4.27. Рис. 4.101. «Наилучший» набор весов, полученный для случая рис. 4.100, после 40000 «тактов». Таким образом, процессы выполнения одного и того же алгоритма при одинаковой размерности популяции и повторяющихся значениях показателей скрещивания и мутации оказываются совершенно различными. Это, конечно, определяется случайным набором особей исходной популяции и случайным проведением скрещивания и мутации. Для случая на рис. 4.99 получен результат, подобный представленному на рис. 4.101, причем веса При использовании генетического алгоритма программы Evolver для решения задач, аналогичных рассмотренным в примерах 4.23 - 4.27, генетические операторы изменяют значения отдельных весов (мутация) и осуществляют обмен значений весов, выбранных случайным образом, между двумя хромосомами (скрещивание). В то же время, в программе FlexTool (пример 4.20) генетические операторы рекомбинируют гены внутри хромосом, которые представляют собой двоичные последовательности, соответствующие закодированным значениям конкретных весов. В программе Evolver хромосомы состоят из генов, имеющих действительные значения, совпадающие со значениями весов. Программа Evolver - это прекрасный инструмент для оптимизации функции нескольких переменных, при этом она может применяться для поиска максимума или минимума функции двух и даже одной переменной. Заметим, что в случае только одной переменной скрещивание практически не производится, и выполняется только операция мутации, что характерно для так называемого эволюционного программирования (см. разд. 4.10). Все примеры, решенные в разд. 4.9 при помощи программы FlexTool, можно решать также и средствами программы Evolver. Например, на рис. 4.102 показано изменение «наилучшего» и среднего значения функции приспособленности в случае поиска максимума функции, представленной на рис. 4.23. Одно деление на временной оси соответствует 20 «тактам». Вычисления проводились с принятыми по умолчанию значениями показателей скрещивания (0,5) и мутации (0,06), а также размерности популяции (50). Графики и «наилучшие» решения регистрировались после 700 «тактов» Рис. 4.102. Изменение «наилучшего» и среднего значения функции приспособленности в случае поиска максимума функции, изображенной на рис 4.23, с помощью программы Evolver. Пример 4.28 С помощью программы Evolver найти минимум функции из примера 4.18. График этой функции изображен на рис. 4.40. В примере 4.18 приведены координаты четырех точек, в которых эта функция имеет минимальное значение, равное 0. Генетический алгоритм должен найти одну из этих точек. Применяется программа Evolver с принятыми по умолчанию значениями показателей скрещивания (0,5) и мутации (0,06). Размерность популяции выбрана равной 30. На рис. 4.103 представлены начальные значения переменных Рис. 4.103. Начальные значения для примера 4.28. Рис. 4.104. Популяция особей при
Рис. 4.105. Популяция особей при На рис. 4.106 представлены те же графики после 150 «тактов» Рис. 4.106. Популяция особей и график функции приспособленности при Еще меньшая разнородность популяции наблюдается на рис. 4.107, который содержит также столбчатую диаграмму и значения генов конкретных хромосом популяции. «Наименьшее» значение функции приспособленности здесь составляет 5,83 для Рис. 4.107. Популяция особей и график функции приспособленности при На рис. 4.108 представлены те же графики после 8000 «тактов» Рис. 4.108. График функции приспособленности при На рис. 4.109 изображена столбчатая диаграмма особей популяции для Рис. 4.109. Столбчатая диаграмма значений функции приспособленности особей в популяции при «Наилучшее» решение показано на рис. 4.110. Это хромосома со значениями переменных Рис. 4.110. «Наилучшее» решение для примера 4.28 (полученное при
|