Диссертация (Методы и алгоритмы интеллектуализации принятия решений в условиях неопределенности на базе аппарата нейронных сетей и эволюционного моделирования), страница 12

Независимыми друг от другаусловиями завершения могут быть следующие: по количеству эпох; поисчерпанию времени эволюции (или количества обращений к функцииоптимизации); по достижению наилучшей комбинации генов; по выходу функцииприспособленности на «плато» - то есть по отсутствию ее изменения в течениезаданного количества эпох [70]. Если выполнено любое из условий, то алгоритмзавершает работу.

Иначе выполняется следующий шаг.5. Селекция. Стратегию поиска составляют механизмы селекции ирекомбинирования. Это вероятностные процессы, лежащие в основе процессанейроэволюции [71].Оператор отбора хромосом SL (selection) для новой популяции реализованвероятностным методом [66] в сочетании с методом «элит» [68]: наиболееудачные особи заносятся в пул «хороших» решений; остальные особи отбираютсядля рекомбинирования с вероятностью . () =∑=1 ,(2.14)где i, j – индексы особей.Пул «хороших» решений необходим для поддержания разнообразияпопуляции и предотвращения быстрой сходимости алгоритма к неоптимальномурешению (локальному оптимуму).Хромосома для фенотипа ∗ сохраняется впуле при выполнении условия(∀ ∈ )(((, ∗ ) = max ) ∩ ((∗ ) = max )),где max – максимальное в данную эпоху расстояние между особями;max – максимальная приспособленность в данную эпоху.(2.15)726.

Рекомбинирование – применение генетических операторов кроссинговераи мутации к отобранным на предыдущем шаге особям [72].Кроссинговер – генетический оператор, влияющий на размер популяции. Вданной реализации нейроэволюции предложен двухэтапный многоточечныйкроссинговер CR (crossingover) [4].Первый этап кроссинговера заключается в определении количества икоординат , ∈ [1, ]точек пересечения c последующим скрещиваниемисходных генотипов по заданным точкам.

В общем случае для D точекрезультатом скрещивания особей = {1 , 2 , … , }, = {1 , 2 , … , } ∈ эпохи t являются два генотипа эпохи t+1:+1 = {1 , … , 1 , 1+1 , … , 2 , 2 +1 , … , , … },+1 = {1 , … , 1 , 1+1 , … , 2 , 2 +1 , … , , … } ∈ +1 ,(2.16)где , ∈ [1, ] – точки пересечения генотипов; – количество точек пересечения.Количество точек пересечения определяется как случайное число на отрезке[1, min{1 , 2 }], где 1 и 2 – соответственно количество нейронов в первом ивтором генотипе, отобранных для кроссинговера.

Точки выбираются всоответствии с условием: = : (1 () = 2 ()) ∪ (1 () = 2 ()) ,(2.17)где – индекс, позиционирующий нейрон в первом и втором генотипах;1 (), 2 () и 1 (), 2 () – соответственно значения параметров и для -го нейрона в данных генотипах.В случае, если индексов c равными значениями параметров несколько,выбираются индексы с наиболее близкими значениями.

Таким образоминдексация нейронов в генотипе в совокупности с использованием параметров и снижает риск конкуренции представлений и предотвращает скрещиваниеучастков генотипов, несущих различную функциональную нагрузку.Второй этап кроссинговера состоит в корректировке синаптических связейсформированных в результате применения оператора генотипов, а именно в73удалении и перераспределении связей, соотнесенных с отсутствующими в новойконфигурации ИНС нейронами. Этап необходим для гарантии жизнеспособностиновых особей.Мутация (mutation)– генетический оператор, в данном методереализованный в восьми модификациях.

Вероятность применения мутации дляотдельного гена ( ) в эпоху t рассчитывается по формуле− 2 ( ) = √,(2.18)где , = ; L – длина хромосомы; N – размер популяции.Выбор формулы данного вида обусловлен тем, что для эффективнойэволюции вероятность мутации должна быть обратно зависима от размерапопуляции. При этом вероятность мутации с течением времени понижается.Одной из основных целей применения оператора мутации является поддержаниеразнообразия особей, но в маленьких популяциях частые мутации негативносказываютсянасхождениикоптимуму.Хромосомыбольшойдлиныобеспечивают вариативность популяции, поэтому значение тем выше, чемменьше параметров содержит хромосома.

Параметры , формулы выбираютсядо начала эволюции и необходимы для тонкой настройки процесса мутации.Особенности модификаций оператора и вероятности применения каждой измодификаций представлены в таблице 2.2. Индексирование узлов в генотипепредотвращает риск удаления из популяции новых элементов: при выполненииусловия = max , где – индекс данного узла, max – индекс последнегодобавленного в генотип узла, вероятность использования операторов удаленияравнанулю.Введениенезащищенностиумножаетсяданногоинноваций.вероятностьдляусловияВероятностныекаждойпозволяетрешитькоэффициенты,модификациинаоператора,проблемукоторыеявляютсяфиксированными и выбраны исходя из требования более частого изменениясуществующих параметров, чем добавления новых или удаления ранеенастроенных элементов.74Таблица 2.2 – Описание операторов мутацииОбозначение_ОписаниеПоследовательное добавлениенейрона (serial addition)Параллельное добавлениенейрона (parallel addition)Удаление нейрона (deletion)_____Добавление связи междунейронами (link addition)Удаление связи междунейронами (link deletion)Добавление входа,соотнесенного параметру изпула (input addition)Удаление входа, соотнесенногопараметру из пула(input deletion)Изменение параметровнейрона(alter): значения порога, вида функции активации() и ее параметровВероятность применения_ = 0.1 ( )_ = 0.1 ( )0, = max = {0.1 ( ), ≠ max_ = 0.1 ( )0, = max_ = {0.1 ( ), ≠ max_ = 0.05 ( )0, = max_ = {0.05 ( ), ≠ max = 0.2 ( )Описанные операторы селекции и рекомбинирования в совокупности сфункцией приспособленности и пулом «хороших» особей предназначены длясамоадаптации алгоритма к уровню сложности задачи.7.

Локальный поиск. Данный этап оптимизации особей популяции, наделяеталгоритм свойствами меметичности [44] и обосновывает использование прямогометода кодирования хромосом.Этап реализован при помощи алгоритмалокального поиска.8. Генерирование популяции +1 и переход на новую эпоху эволюции + 1:+1 = ( (( , )))Далее описан локальный поиск, осуществляемый на этапе 7.(2.19)752.3.2 Генетический алгоритм локального поискаЭтап локального поиска состоит из следующих шагов: эволюционнаядонастройка весов и параметров функций активации нейронов особей популяции,на предыдущем шаге преобразованных в фенотипы; пересчет функцийприспособленности; возвращение к предыдущим значениям параметров в случаеснижения приспособленности.

Данные шаги проиллюстрированы блок-схемой нарисунке 2.4.НачалоСохранение значений функцийприспособленности ипараметров особей популяцииИзменение параметров ИНСПересчет для ИНС функцийприспособленностиПриспособленностьповысилась?ДаНетВозвращение к предыдущимпараметрам ИНСКонецРисунок 2.4 – Блок-схема этапа локальной оптимизацииПреимуществами эволюционной донастройки параметров ИНС являютсяследующие:– независимость от топологии сети и характеристик функций активации;76– возможность определения, показывает ли данная особь низкуюприспособленность из-за неудачно сформированной топологии или неправильноподобранных весов;–выборочнаяоптимизацияпараметровнедавноизмененныхилидобавленных нейронов без затрагивания уже модифицированной на предыдущихитерациях работы алгоритма структуры.Таким образом, исследование пространства поиска осуществляется наэтапах 1-6, 8. На этапе 7 реализован алгоритм локального поиска, использующийнайденные «хорошие» решения.Предложенный метод может использоваться для создания нейросетейпроизвольной топологии, которые имеют различное назначение.2.4 Оценка сходимости алгоритмаСходимостьлюбогометодаоптимизациибазируетсянатеоремеВейерштрасса.

Сходимость канонического ГА доказана в теореме схем (теоремеХолланда) [78], которая тем не менее не применима для его модификаций. Всвязи с этим далее приведено исследование сходимости предложеннойреализации ГА, которая отличается от каноничного алгоритма.Для получения оценки сходимости алгоритма в зависимости от размерностии вида оптимизируемой функции предположим, что оптимизируемая функция() задана на множестве оптимизации размерности : ≠ ∅, то естьмножество решений удовлетворяет условию ненулевой меры.