71 Для решения второй проблемы после наступления момента tv происходит ранжирование всех хромосом по функции Fit (по возрастанию). Из каждой популяции удаляется q r худших хромосом (q процент исключения; 0<£<1, г количество хромосом в популяции), и на их место включается q-r лучших хромосом из другой популяции. Выбор обменных хромосом из каждой популяции осуществляется с вероятностью; Условие останова многопопуляционного алгоритма ГА сумма разностей функций фитнесса разных популяций, участвующих в обмене, за с последних популяций меньше 5 (3.6). Так, если развиваются только две популяции, то условие останова может быть записано следующим образом : за последние с поколений. 2.9. Экспериментальное исследование генетического алгоритма Настроив соответствующим образом параметры системы, можно управлять процессом поиска в зависимости от поставленной задачи: поиск одного решения; определение нескольких или всех глобальных экстремумов; описание области поиска решения, включая выявление как глобальных, гак и локальных экстремумов. Для решения каждой из выделенных задач необходимо определять наиболее оптимальное сочетание параметров, позволяющее построить эффективный алгоритм. Для генетического алгоритма устойчивость связана с необходимостью постоянно увеличивать качество популяции от поколения к поколению, т.е. связана с возрастанием среднего значения Fit по популяции при переходе к следующему поколению. При практической реализации алгоритма возникает задача определения правил останова. В качестве критериев останова будем использовать следую(2.27). Z FitL -F itL /(c x m ax(F itL 5F itL ))< ^ (2.28) |
Шаг 12. Если 5Ус >6, то переход ш.4, иначе ш.13. Шаг 13. /у=/ Шаг 14. Останов. Если условие наступления события выполняется хотя бы для одной популяции, то происходит обмен хромосомами между этой популяцией и другой, выбранной случайным способом. Для решения второй проблемы после наступления момента Л, происходит ранжирование всех хромосом по функции Fit (по возрастанию). Из каждой популяции удаляется д г худших хромосом {д процент исключения; 0 <<7< 1; г количество хромосом в популяции), и на их место включается д г лучших хромосом из другой популяции. Выбор обменных хромосом из каждой популяции осуществляется с вероятностью: Условие останова миогопопуляционного алгоритма ГА сумма разностей функций фитнесса разных популяций, участвующих в обмене, за с последних популяций меньше 5 (3.6). Так, если развиваются только две популяции, то условие останова может быть записано следующим образом : Е И т « Р ‘С ч /(С Х та Х(Р11!пах»Р^та х ))< ^ (3*6) за последние с поколений. Исследование многопопуляционного ГА и сравнение его с другими алгоритмами проведено в 3 .2 .1. 149 3.2. Алгоритм обучения нейронной сети на основе генетического алгоритма и его оценка Одной из основных проблем стандартного алгоритма обучения нейронной сети Back Propagation (ВР), как было показано в главе 2, является проблема выхода из локального минимума функции ошибки обучения НС. Алгоритм ВР, использующий в стандартном варианте градиентные методы поиска экстремума, не всегда может выйти из локального минимума или обнаружить глобальный минимум. Одним из способов, позволяющих повысить вероятность нахождения глобального минимума и тем самым повысить адаптационные возможности нейронной сети, является использование глобальных алгоритмов оптимизации, к которым относится генетический алгоритм (ГА). Проведем экспериментальное исследование ГА с целью построения эффективного алгоритма обучения НС. 3.2.1. Экспериментальное исследование генетического алгоритма Представленный Конструктор ГА обладает достаточно широкими возможностями. Настроив соответствующим образом параметры системы, можно управлять процессом поиска в зависимости от поставленной задачи: поиск одного решения; определение нескольких или всех глобальных экстремумов; описание области поиска решения, включая выявление как глобальных, так и локальных экстремумов. Для решения каждой из выделенных задач необходимо определять наиболее оптимальное сочетание параметров, позволяющее построить эффективный алгоритм. 150 где к —число тестовых задач; р , —п:1п\ п — число начальных точек; «у — число решений задачи оптимизации; 2 ) среднее число необходимых вычислений целевой функции для класса тестовых задач 1 к т = ’ ( 3 8 ) к ] = \ где тj n F !п,, где nF —суммарное число необходимых вычислений для целевой функции при решении задачиj. Первый критерий (3.7) определяет степень устойчивости алгоритма к попаданию в точки экстремумов, а второй (3.8) скорость сходимости к экстремуму. Применение современных вычислительных средств приводит к тому, что второй критерии становится не столь важным, поэтому при сравнении ГА с другими алгоритмами будем в основном пользоваться первым критерием. Для генетического алгоритма устойчивость связана с необходимостью постоянно увеличивать качество популяции от поколения к поколению, т.е. связана с возрастанием среднего значения Fit по популяции при переходе к следующему поколению При практической реализации алгоритма возникает задача определения правил останова. В качестве критериев останова будем использовать следующие: 1. окончание выделенного лимита времени (заданного числа итераций) или 2. функция качества Fit "лучшей" хромосомы достигла определенного значения с заданной точностью. 152 |