95 представлен на рис. 3.17. Полученные результаты подтверждают выводы, сделанные в 3.21. Для сложных многоэксгремальных функций (например, для исследуемой функции Растригина) целесообразно использовать следующие генетические операторы: кроссинговер рекомбинация; мутация инверсия; селекция "дальнее родство", а для унимодальных (например, функции Розенброка): кроссинговер одноточечный или двухточечный; мутация генная; селекция "ближнее родство". Применение полученных с помощью внешнего алгоритма параметров ГА, используемых для оптимизации функций Розенброка, позволило сократить число итераций при поиске до ¿=10-15 (по сравнению с ¿=25 в предыдущих экспериментах), а функции Растригина до ¿=20-25 (по сравнению с к=50) при той же точности. 3.2. Разработ ка и исследование комбинированного алгоритма обучения НС на основе ГА и имитации отжига Алгоритм имитации отжига (АИО) относится к классу глобальных алгоритмов оптимизации и основывается на понятии тепловой энергии, введенной С. Кирпатриком. Автор алгоритма использовал "тепловой шум" для выхода из локальных минимумов и для повышения вероятности попадания в более глубокие минимумы. Этот процесс Кирпатрик назвал "имитацией отжига" (по аналогии с процессом отжига металла, в результате которого появляются его новые свойства) [27]. Использование алгоритма АИО в процедуре обучения НС позволит повысить вероятность нахождении глобального минимума ошибки распознавания и классификации. Рассмотрим организацию процедуры оптимизации на основе имитации отжига. Пусть задано конечное множество возможных конфигураций П. Обозначим через № возможную конфигурацию; 1^1число конфигураций; ¡=1, И. • . , . Пусть также задана стоимостная функция Р(Н), которая каждой кон |
Пример результатов работы предложенного Конструктора при выборе генетических операторов для оптимизации функций Розенброка и Растригина представлен на рис. 3.17. Полученные результаты подтверждают выводы, сделанные в 3.21. Для сложных многоэкстремальных функций (например, для исследуемой функции Растригина) целесообразно использовать следующие генетические операторы: кроссинговер рекомбинация; мутация инверсия; селекция "дальнее родство", а для унимодальных (например, функции Розенброка): кроссинговер одноточечный или двухточечный; мутация генная; селекция "ближнее родство". N А V»*!'Ч V»V/.Л • >, ••.уп* . * * •! *• • 1м ». * V • / ••• • ч •-ч-.чч.•► .• Размер популяции:82 Вид отбора:Злитный Тип мутации:Инверсия Вероятность мутации:0.05 Выбор родительской пары;Дальнее родство на фенотипе Коэффициент изменения мутации:3.69 Кроссинговер:Рекомбинация л*.* На какой Функции л >. поколении Лучшее значение ф ' \ мм Размер популяции:41 Вид отбора:С вытеснением Тип мутации:Генная Вероятность мугации:0.44 Выбор родительской парьгБлижнее родство на генотипе Коэффициент изменения мугации:4.44 Кроссинговер:2*х точечный фиггнесса ш: ш » « ■ ч М 1 ■ ш пм 111Ц м Ц п>>11ц и 1ц ^эд цш ш м На какой Функции1 * ,** * •> 1 • * Количество поколений Розенброка •V. т м м т ш * * * * * — * * * * ' / * * * * * ^ « ^ ^ ; • > * * ---------------------------— — г . г . у ^ш4• * » к ч ч * • ; » * » * • * > * • < * ■ * • * / ^ * . * » * < > * . . * . Лучшее значение Рис.3.17. Результаты работы внешнего генетического алгоритма ГА Применение полученных с помощью внешнего алгоритма параметров ГА, используемых для оптимизации функций Розенброка, позволило сократить число итераций при поиске ~ до £=10-15 (по сравнению с к=25 в предыдущих экспериментах), а функции Растригина до &=20-25 (по сравнению с к=50) при той же точности. 172 40 35 30 25 20 о Q. С 15 10 5 0 1000 2000 5000 10000 ВР ИВР1 □ ВР2 Число итераций Рис. 4.4. Зависимость процента ошибок от числа итераций ВР стандартный алгоритм Back Propagation ВР1алгоритм ВР с динамическим шагом ВР2 модифицированный ВР с коррекцией h и п Достижение той же ошибки обучения (25 %) было достигнуто для ВР2 при числе итераций в пять раз меньше, а для ВР1 в три раза меньше. 4.1.2. Комбинированный алгоритм обучения МНС с использованием генетического алгоритма и имитации отжига В данном разделе разрабатывается комбинированный алгоритм обучения МНС: на основе генетического алгоритма (ГА) и алгоритма имитации отжига. Создание такого алгоритма открывает возможность динамически менять скорость сходимости ГА на различных этапах поиска оптимума с целью снижения временных затрат и повышения вероятности нахождения глобального экстремума (минимальной ошибки сети). Алгоритм имитации отжига (АИО) основывается на понятии тепловой энергии, введенной С. Кирпатриком [119]. Автор алгоритма использовал "тепловой шум" для выхода из локальных минимумов и для повышения вероят200 ности попадания в более глубокие минимумы. Этот процесс Кирпатрик назвал "имитацией отжига" (по аналогии с процессом отжига металла, в результате которого появляются его новые свойства). Рассмотрим организацию процедуры оптимизации на основе имитации отжига. Пусть задано конечное множество возможных конфигураций £>. Обозначим через Я/ возможную конфигурацию; Я число конфигураций; 1=1, ... , О . Пусть также задана стоимостная функция Р(Н), которая каждой конфигурации Я, е Яставит в соответствие оценку (в простейшем случае действительное число). АИО может быть сформулирован как некоторая последовательность смены цепей Маркова [120]. Каждая цепь представляет собой последовательность конфигураций Я, а вероятность перехода к новой конфигурации (от / кУ) определяется следующим образом: Рк Ь„(0Ру, если Ю,1 1 2 *,(О *. если / = / (4.5) /,у=1 где ру вероятность получения конфигурации Ну из Я,в результате воздействия "теплового шума", Ьу вероятность принятия конфигурации; / управляемый параметр отжига (аналог уровня теплового шума), начальное значение которого задается априорно и изменяется в процессе работы алгоритма по определенному закону. Для каждой конфигурации Я,подпространство конфигураций Я, определяется как множество возможных Ну, которые дос201 |