Применение генетических алгоритмов в системах Автономного Адаптивного Управления Земских Леонид Вячеславович

к другим подсистемам УС

а) Ъ)

Рис.3 Соединение нейронов: а) схема соединения нейронов двунаправленными связями, Ь) схема соединения нейронов в сеть. Двунаправленные связи обозначены единой стрелкой, направление которой соответствует направлению распространения сигнала от датчиков.

Выходы Oi и 02 нейронов я/ и П2 соединены с входами нейрона щ. Эти связи обеспечивают прохождение сигналов в прямом направлении (от «; и я; к пз) для реализации процесса формирования образов. В обратном направлении распространяются сигналы, обеспечивающие отключение сигналов Oj=\ и (>2=\ в случае, если будет распознан образ О і.

Основное свойство описываемого нейрона состоит в его способности накапливать статистические данные относительно предъявляемых векторов и изменять свое функционирование при накоплении статистически достоверных оснований.

Таким образом, можно видеть, что система управления, реализующая метод ААУ, имеет очень много степеней свободы. Так, для каждой прикладной системы должны быть определены: состав и параметры датчиков, состав и топология нейроноподобных сетей для все подсистем УС, параметры отдельных нейронов, величины качественных оценок, состав и параметры актуаторов, и некоторые другие объекты. Как показывает опыт автора (исследования, проведенные в работе на соискание степени бакалавра), аналитический расчет этих параметров очень сложен. Система ААУ является адаптивной (поисковой) системой. Эти ее свойства обусловлены способностью используемых моделей нейронов к самообучению. Однако ее адаптивные (поисковые) возможности, какими бы широкими или узкими они не были, естественно ограничены составом и структурой (топологией) ее нейроноподобных сетей. Эти последние, в свою очередь, могут быть оптимизированы в результате применения некоторой поисковой процедуры. В связи с этим в настоящей работе предлагается расчет приведенных выше параметров, а также топологии сети нейроноподобных элементов, с помощью генетических алгоритмов.

3. Основные положения теории генетических алгоритмов, методы эволюционной оптимизации

3.1 Введение в тематику генетических алгоритмов

В настоящей работе используется относительно новое направление оптимизации, названное «генетическими алгоритмами», получившее активное развитие в последние годы. Алан Тьюринг еще в 40-е годы определил три основных подхода, в рамках которых возможно использование методов поиска для автоматического создания «разумной» компьютерной программы [18].

1-й подход, определенный Тьюрингом состоит в применении поиска в пространстве чисел, представляющих компьютерные программы-кандидаты. Этот подход отражает многое из предложенного самим Тьюрингом в области логического обоснования вычислительных алгоритмов.

2-й подход Тьюринг описал как «культурный» поиск, который опирается на знания, полученные экспертами в течение ряда лет от других экспертов. Этот подход во многом

соответствует современному, воплощенному, в частности, в виде систем, использующих базы знаний, и в виде экспертных систем.

3-й подход Тьюринг определил как «генетический или эволюционный поиск». В частности, он писал: «Существует генетический или эволюционный поиск, при котором отыскивается комбинация генов, а критерием является «значение выживания». Примечательные успехи этого метода в какой-то степени подтверждают идею о том, что умственная активность в основном связана с различными видами поиска».

Дальнейшее материалы, представленные в настоящей работе, относятся только к последнему из предложенных Тьюрингом подходов (генетическим алгоритмам).

Самое очевидное приложение методов поиска - это задачи оптимизации, причем не только однокритериальной, но и многокритериальной. Являясь стохастическими методами поиска нулевого порядка, генетические алгоритмы применимы на более широком классе оптимизируемых функций, чем большинство стандартных методов, к которым, в частности, относится градиентный спуск, и прочие методы оптимизации.

Генетические алгоритмы (ГА) основаны на аналогии с генетическими процессами биологических организмов. Биологические популяции развиваются в течение нескольких поколений, подчиняясь законам естественного отбора и в соответствии с принципом «выживает наиболее приспособленный» (survival of the fittest), открытым Чарльзом Дарвином.

Механизм развития состоит в следующих чертах. Свойства отдельно взятого индивида составляют его так называемый «фенотип». Выживание индивида в конкретных условиях окружающей среды зависит от того, удачным или не удачным оказался его фенотип, и определяется по факту - выжил или не выжил данный индивид в этих условиях. Если индивид выжил, именно - достиг репродукционного возраста, то при репродуцировании он передает информацию о своем фенотипе потомкам в виде кода, записанного в хромосоме половой клетки, что составляет его «генотип». При этом механизм кодирования информации в хромосоме сопровождается специальными процессами, обеспечивающими, во-первых, скрещивание фенотипических признаков обоих родителей (что дает вероятность передачи потомку удачных признаков от каждого из родителей), а, во-вторых, мутацию - дающую некоторое случайное изменение генотипа (что обеспечивает порождение новых фенотипических свойств у потомков с целью поиска новых возможностей). В целом, этот процесс реализует поисковый механизм приспособления организмов. Вначале ГА генерирует определенное количество потенциальных решений (гипотез, где каждая гипотеза здесь - это «организм»), а затем вычисляет для каждого потенциального решения «уровень выживаемости» (fitness), т.е. проверяется, насколько гипотеза (индивид) оказалась удачной,

приспособленной для выживания в данных условиях. Эти решения «дают потомство», наследующее признаки, возможно обеспечившие выживание предков. Те индивиды, которые имеют больший уровень приспособленности, имеют большие шансы дать потомство, а «слабые» индивиды постепенно отмирают.

Подражая этим генетическим процессам биологических организмов, генетические алгоритмы, как математический метод поисковой оптимизации, способны «развивать» решения реальных задач, если те соответствующим образом закодированы. ГА могут использоваться в инженерных задачах, при проектировании, например, структуры мостов, для поиска максимального отношения прочности/веса, или определять наименее расточительное размещение для нарезки форм из материала и т.п. Они могут также использоваться для интерактивного управления некоторыми технологическими процессами на производстве, или балансировании загрузки на многопроцессорном компьютере и т.п.

В природе особи в популяции конкурируют друг с другом за различные ресурсы, такие, например, как пища или вода. Те особи, которые наиболее приспособлены к окружающим условиям, будут иметь относительно больше шансов к производству потомков. Слабо приспособленные особи либо совсем не произведут потомства, либо их потомство будет очень немногочисленным. Это означает, что гены от высоко адаптированных или приспособленных особей будут распространятся в увеличивающемся количестве потомков на каждом последующем поколении. Комбинация хороших характеристик от различных родителей иногда может приводить к появлению «сверхприспособленного» потомка, чья приспособленность больше, чем приспособленность любого из его родителей. Таким образом, вид развивается, все лучше и лучше приспосабливаясь к среде обитания.

ГА используют прямую аналогию с таким механизмом. Они работают с совокупностью «индивидов» - популяцией, где каждый «индивид» представляет собой возможное решение данной задачи. Каждая особь оценивается мерой ее «приспособленности» согласно тому, насколько «хорошо» соответствующее ей решение задачи. В природе это эквивалентно оценке того, насколько эффективен организм при конкуренции за ресурсы. Наиболее приспособленные особи получают возможность «производить» потомство с помощью «перекрестного скрещивания» с другими особями популяции. Это приводит к появлению новых особей, которые сочетают в себе некоторые характеристики, наследуемые ими от родителей. Наименее приспособленные особи с меньшей вероятностью смогут воспроизвести потомков, а те свойства, которыми они обладали, будут постепенно исчезать из популяции в процессе эволюции.

Так воспроизводится вся новая популяция допустимых решений в процессе выбора лучших представителей предыдущего поколения, скрещивания их и получения множества новых особей. Каждое новое поколение содержит более высокое соотношение характеристик, которыми обладают удачные члены предыдущего поколения. Таким образом, из поколения в поколение, удачные, с точки зрения заданного критерия отбора, характеристики распространяются по всей популяции. Скрещивание наиболее приспособленных особей приводит к тому, что исследуются наиболее перспективные участки пространства поиска. В конечном итоге, популяция должна сходиться к оптимальному решению задачи.

Одним из самых больших недостатков генетических алгоритмов является неопределенность критерия останова. В большинстве случаев исследователи ограничиваются определенным количеством итераций, близостью точек в пространстве решений целевой функции согласно выбранной мере или превышением какого-то определенного значения целевой функцией для всего рассматриваемого множества аргументов. В этом случае нельзя гарантировать, что аргумент целевой функции из рассматриваемого множества, дающий наибольшее (наименьшее) значение целевой функции, доставляет максимум (минимум) функции. Однако неопределенность критерия останова компенсируется способностью ГА, при некоторых условиях, динамически отслеживать изменения экстремума, что может оказаться важным для адаптивных систем управления.

Другой проблемой, возникающей вследствие применения генетических алгоритмов, является вопрос о глобальности максимума, доставляемого полученным в результате работы алгоритма аргументом. Т.е. в отсутствие дополнительных знаний о целевой функции нельзя точно утверждать, что найденное ГА решение лежит близи глобального оптимума.

Еще одним важным вопросом является проблема кодирования точек в пространстве решений оптимизируемой функции для представления их в форме, необходимой для работы генетического алгоритма.

Рассмотрим далее типичную структуру генетического алгоритма и введем используемую в этой методологии терминологию, после чего обсудим и проиллюстрируем вынесенные в этом разделе вопросы.

3.2 Структура простейшего генетического алгоритма, терминология

Большинство традиционных методов оптимизации оперирует единственно аргументом целевой функции, принимая во внимание свойства последней (например, приращения) и получая новое значение аргумента на их основе. Генетический алгоритм, напротив, оперирует некоторым множеством элементов из области определения целевой функции

(потенциальными решениями), которое называется популяцией и не использует иных свойств целевой функции, кроме, собственно ее значений. Иными словами, генетические алгоритмы представляют собой метод оптимизации нулевого порядка.

Все преобразования, производимые с популяцией, основываются на значениях целевой функции на каждом элементе популяции, называемых также индивидами (рис.4), и производятся в соответствии с определением генетических операторов над индивидами и их наборами, определяющими правила рекомбинирования закодированной (генетической) информации и ее изменения.

Фитнес-функция

Значение приспособленности

Индивид

Популяция Рис. 4. Популяция и индивид на примере точек на действительной числовой оси

Рис. 4 иллюстрирует понятия, используемых в теории генетических алгоритмов. Индивид - допустимое решение задачи оптимизации. Некоторое множество индивидов -популяция. Фитнес-функция - целевая функция задачи оптимизации. Значение приспособленности - значение целевой функции в точке потенциального решения.

Традиционно, каждый индивид представлялся в виде хромосомы — результата отображения собственно элемента из области определения целевой функции в некоторое специальное представление посредством операции кодирования. Обычно хромосома подразделяется на гены, каждый из которых несет в себе некоторую информацию — как правило, символ (аллель). Например, если целевая функция является функцией одного аргумента, а множеством ее определения являются целые числа, то типичным примером представления целых чисел в виде хромосом может служить обычное бинарное представление (восьмеричное, десятичное, шести ад цатеричное, и т.д., а также любое

символьное). Для более сложных случаев возможно использование других методов представления аргументов целевой функции. Например, для функции двух аргументов каждый из аргументов может представляться соответствующей ему хромосомой, а получающаяся таким образом пара формирует индивид. Здесь же возможно объединение двух хромосом в одну, и индивид будет представлен одной хромосомой (рис.5) Совокупность хромосом принято называть геномом.

105 і 0 110 10 0 1

(233,105)

Рис. 5. Примеры представления потенциальных решений в виде хромосом.

При решении многих задач кодировки такого вида отсутствуют, а индивиды представляются в виде набора хромосом, число которых соответствует числу аргументов целевой функции и имеющих десятичную кодировку.

Вообще говоря, выбор способа кодирования является одним из центральных моментов при проектировании генетического алгоритма для решения какой-либо задачи, так как она определяет выбор и стохастических операторов, их сложность и, как следствие, скорость вычислений. Более детально процедура кодировки будет рассмотрена ниже.

Рассмотрим типичные операторы генетических преобразований. Основой для выбора названий и принципа действия этих операторов послужили процессы, происходящие внутри живой клетки, и составляющие хромосомный механизм передачи наследственности.

Для описания механизма передачи информации от родителей потомкам применяется терминология, заимствованная из биологии. В частности, параметры, характеризующие точку в области определения оптимизируемой функции, называются фенотипом (внешними характеристиками), закодированное представление этих свойств называют генотипом, а собственно объект, представляющий такой код, называют хромосомой.

В первом приближении, считается, что процессы передачи генетической информации, можно рассматривать как пару - процесс кроссинговера {скрещивания) и процесс мутации. Кроссинговер - это процесс, при котором происходит передача признаков обоих родителей потомку с одновременным перемешиванием этих признаков. Мутация - это процесс, определяющий изменения свойств потомка (конкретного индивида) в процессе жизни, т.е. такие процессы, которые изменяют генный материал (генотип) индивида вне зависимости от генетической информации, переданной ему родителями. Считается, что именно процесс мутации является причиной обретения новых признаков - причиной радикального изменения одного из свойств организма - которые могут как повысить приспособленность данного индивида к конкретным условиям обитания, так и понизить ее. Однако, с точки зрения теории генетических алгоритмов, кроссинговер обеспечивает сильное изменение свойств организма (по сравнению с родителями), степень которого зависит от степени различия генотипов родителей. Механизм мутации, в свою очередь, моделирует случайное изменение какого-либо свойства организма, т.е. части генотипа, полученного в результате скрещивания родительских генотипов. Следует также отметить, что процессы мутации происходят крайне редко.

Таким образом, процесс кроссинговера обеспечивает получение генотипа, приближенного в каком-то смысле к генотипам родителей. Если иметь в виду стратегию отбора индивидов для производства потомства, которую мы рассмотрим позже, то этот процесс обеспечивает сближение потенциальных решений задачи оптимизации в смысле метрики, определенной в пространстве потенциальных решений.

Процесс мутации происходит редко, но изменяет генотип (и, следовательно, фенотип) безотносительно свойств родителей, производя нового индивида, который в области определения оптимизируемой функции может отстоять далеко от прочих индивидов в популяции. В случае если основная масса индивидов находится в окрестности точки, доставляющей оптимизируемой функции локальный максимум, мутировавший индивид может попасть в окрестность точки, доставляющей оптимизируемой функции глобальный максимум, обеспечивая, таким образом, вывод алгоритма из локальных минимумов. Тем не менее, процедура мутации не гарантирует, что глобальный максимум будет найден, но повышает вероятность такого события.

Типичный генетический алгоритм призван моделировать собой процесс естественной эволюции, который, как принято считать, регламентируется вышеперечисленными процессами. При этом, согласно теории Дарвина, наивысшие шансы к выживанию имеют наиболее приспособленные индивиды популяции. Для реализации в генетических алгоритмах этой точки зрения, для каждого индивида применяется оценка приспособленности,

характеризующая степень его превосходства (в смысле приспособленности) над остальными индивидами популяции. В процессе эволюции наибольшую вероятность передачи своих свойств потомкам имеют в первую очередь индивиды с наибольшей приспособленностью. Оценка приспособленности, собственно и является оптимизируемой (целевой) функцией.

Операторами генетических преобразований являются оператор кроссииговера (crossover) и оператор мутации (mutation), воплощающие в каждой конкретной задаче процессы передачи признаков и спонтанного их изменения.

Для иллюстрации приведенных выше соображений, рассмотрим схему работы простейшего генетического алгоритма. Сразу заметим, что она лишь в общих чертах реализует суть метода. В каждой конкретной задаче эта схема может отличаться от приведенной в деталях. Здесь, для упрощения примера, рассмотрим случай, когда для производства нового индивида отбираются два родителя, от которых производится единственный потомок (рис.6).

Рис.6. Пример схемы работы простейшего генетического алгоритма.

Рассмотрим пример. Пусть необходимо найти

f(x) -> max, где D = (х = (x_h х₂, .... x_N) \ x_t e[a_it bj, i=l, 2, ...,N},

где /(*)- максимизируемая (целевая) скалярная функция N аргументов, которая может иметь несколько глобальных экстремумов, прямоугольная область D - область поиска, причем DcR^N. Параметры х обычно кодируются бинарной строкой s фиксированной длины.

Таким способом, в общем случае, каждое потенциальное решение генетического алгоритма имеет следующую структуру:

1. Точка в пространстве параметров (фенотип):
x = \\x_l,x₂,...,x_N\\eDQR^N;

2. Бинарная строка s фиксированной длины /, однозначно соответствующая х (генотип):
5 = Ъ_хЪ_г ...b, eS, где S - пространство представлений - бинарных строк длины /.

3. Скалярная величина т, соответствующая значению целевой функции в точке х
(приспособленность):

т = /(х).

В терминологии, принятой в теории ГА, такую структуру принято называть индивидом или особью. Совокупность индивидов принято называть популяцией.

Простой ГА случайным образом генерирует начальную совокупность (популяцию) структур (индивидов). Тем не менее, исследователь всегда может на основе некоторых эвристических соображений предложить алгоритм формирования стартовой популяции, которая при удачном ее создании располагает потенциальные решения в окрестности глобального оптимума, что значительно ускоряет работу алгоритма.

Работа ГА представляет собой итерационный процесс, который продолжается до тех пор, пока не выполнятся заданное число поколений или какой-либо иной критерий останова. В случае простейшего ГА на каждом шаге алгоритма реализуется отбор индивидов в репродуктивные множества (обычно просто пары) на основе их приспособленности, над репродуктивными множествами применяется оператор кроссинговера и оператор мутации.

Обычно, по биологическим соображениям размер репродуктивного множества, также иногда называемого семьей, ограничивается парой индивидов, а сами они выбираются из соображений наличия у них высокой приспособленности. В общем случае стратегия формирования репродуктивного множества (семьи) является частью проектирования самого генетического алгоритма и допускает большую свободу в ее определении.

При определении стратегии отбора, о которой также говорят как об операторе селекции, возможно использование различных критериев, которые, тем не менее, должны обязательно учитывать приспособленность индивидов в популяции, т.е. с наибольшей вероятностью в процедуре кроссинговера должны принимать участие индивиды с наивысшей приспособленностью. Одним из таких методов является, например, отбор индивидов согласно

вероятности скрещивания p_Ci рассчитываемой по формуле р_{с t} = -=г—, где fi -

і приспособленность /-го индивида в популяции, а сумма по/ — это сумма приспособленностей всех индивидов в популяции. Например, в стратегии «простейшего пропорционального отбора» - рулетки [19] - индивидов отбирают с помощью п «запусков» рулетки. Колесо рулетки содержит по одному сектору для каждого члена популяции. Размер /-ого сектора пропорционален соответствующей величине P_s(i). При таком отборе члены популяции с более высокой приспособленностью будут выбираться чаще, чем особи с низкой приспособленностью. В этой стратегии большинство семей будут сформированы из индивидов, демонстрирующих относительно высокую приспособленность (относительно индивида, имеющего максимальную приспособленность). Исследователь, в частности, должен определить - возможно ли допустить явление саморепродукции, когда семья строится с кратным вхождением в нее одного и того же индивида. Если такое явление допускается, то в худшем случае оператор кроссинговера уподобляется оператору мутации.

Альтернативой этому простому принципу может служить стратегия отбора, когда первым родителем в семье является индивид с высокой приспособленностью, а вторым родителем является индивид с низкой. Такая стратегия обеспечивает улучшение приспособленности популяции «в среднем».

Рассмотрим работу операторов кроссинговера (скрещивания) и мутации.

В случае традиционной кодировки одноточечный оператор кроссинговера конструируется следующим образом. Оператор является двухместным стохастическим оператором C(xi,X2), отображающим пару индивидов из текущей популяции Рі в множество, соответствующее промежуточной популяции Р2: C(xi,X2): PjxPj—>P2- Пусть с - случайная переменная, равномерно распределенная на отрезке отрезка [0,1]. Для каждой пары соответствующих хромосом определяется число L-c, где L — количество генов в хромосоме. Число L -с, округляемое до ближайшего целого, определяет границу между генами, по которой происходит скрещивание. Хромосомы разделяются, каждая на две части, по границе вычисляемой по Lc. Затем левые, либо правые части хромосом меняются местами. В результате получается новая пара хромосом, из которой отбирается одна, определяющая новый индивид в промежуточной популяции. Схема работы оператора проиллюстрирована на рис.7.

1 1 0 1 о

Lc

Рис. 7. Пример оператора кроссинговера (скрещивания).

Вообще говоря, процедура формирования нового индивида довольно свободна для регламентирования. Рассмотренная процедура построения оператора кроссинговера выбрана именно в связи с соображениями, заимствованными из области биологии. Ничто не мешает сконструировать «-местный оператор, производящий т потомков, реализующий аналогичную процедуру, при которой происходит, например, циклическая перестановка отделенных частей хромосом, при этом хромосома может быть разделана на несколько частей, или вообще процедура комбинирования может носить очень сложный характер.

Множество индивидов, отобранных для операции кроссинговера, образуют семью или репродуктивное множество. В случае производства т потомков из одной семьи говорят об осуществлении принципа «многодетной семьи».

Рассмотрим работу типичного оператора мутации в случае рассмотренного выше способа кодирования. Процедура мутации основывается на том, что каждый ген хромосомы может изменить свое значение с очень низкой вероятностью мутации р_м. Оператор мутации является одноместным стохастическим оператором М(х): ?2—>Рз- Одноместность здесь является принципиальным обстоятельством, так как в противном случае полученный оператор будет представлять собой разновидность оператора скрещивания, а это методически недопустимо. Результатом операции мутации является индивид, который заносится во множество, соответствующее новой популяции (рис.8).

і|о|і|і|о|о|і|Г

Мутирующий ген

1 0 | 0 | 1 | 1 | 0 | 1 О

Ген изменил значене

Рис. 8. Работа оператора мутации.

В соответствии с выбранными биологическими соображениями, вероятность осуществления мутации р_м устанавливается очень низкой. Если установить эту вероятность достаточно высокой, то гены в промежуточных хромосомах будут меняться очень часто, значительно подавляя наследственные признаки, получаемые от родителей. Если эта вероятность выбирается достаточно низкой, то в процессе эволюции признаки родителей успевают проявиться в необходимой степени в нескольких поколениях. Мутации, таким образом, позволяют избежать попаданий в локальные минимумы, побуждая проявление и индивидов новых признаков, часть из которых может привести к повышенной приспособленности новых индивидов.

В настоящее время исследователи ГА предлагают много других операторов отбора, кроссинговера и мутации. Вот лишь наиболее распространенные из них. Прежде всего, турнирный отбор [19, 20]. Турнирный отбор реализует п турниров, чтобы выбрать п особей. Каждый турнир построен на выборке к элементов из популяции, и выбора лучшей особи среди них. Наиболее распространен турнирный отбор с к=2.

Элитные методы отбора [22] гарантируют, что при отборе обязательно будут выживать лучший или лучшие члены популяции совокупности. Наиболее распространена процедура обязательного сохранения только одной лучшей особи, если она не прошла как другие через процесс отбора, кроссинговера и мутации. Это принцип, также называемый элитизмом может быть внедрен практически в любой стандартный метод отбора.

Двухточечный кроссинговер [21, 23] и равномерный кроссинговер [24] - вполне достойные альтернативы одноточечному оператору. При двухточечном кроссинговере выбираются две точки разрыва, и родительские хромосомы обмениваются сегментом, который находится между двумя этими точками. При равномерном кроссинговере, каждый бит первого родителя наследуется первым потомком с заданной вероятностью; в противном случае этот бит передается второму потомку. И наоборот.

Хотя внешне кажется, что ГА обрабатывает строки, на самом деле при этом неявно происходит обработка шаблонов - «шим» (shema), которые представляют собой шаблоны подобия между строками [23, 25]. ГА практически не может заниматься полным перебором всех представлений в пространстве поиска. Однако он может производить выборку значительного числа гиперплоскостей в областях поиска с высокой приспособленностью. Каждая такая гиперплоскость соответствует множеству похожих строк с высокой приспособленностью.

В случае бинарной кодировки потенциальных решений шима - это строка длины / (что и длина любой строки популяции), состоящая из знаков алфавита {0;1;*}, где {*} -неопределенный символ, подразумевающий наличие вместо себя либо {0}, либо {1}. Каждая шима определяет множество всех бинарных строк длины /, имеющих в соответствующих позициях либо 0, либо 1, в зависимости от того, какой бит находится в соответствующей позиции самой шимы. Например, шима, 10**1, определяет собой множество из четырех пятибитовых строк {10001; 10011; 10101; 10111}. У шим выделяют два свойства - порядок и определенная длина.

Порядок шимы - это число определенных битов («0» или «1») в шиме. Определенная длина - расстояние между крайними определенными битами в шиме. Например, вышеупомянутая шима имеет порядок о(10**1)=3, а определенная длина d(10**l) = 4.

Строящие блоки [23] - это шимы обладающие:

высокой приспособленностью,

низким порядком,

короткой определенной длиной.

Приспособленность шимы определяется как среднее приспособленностей примеров (членов популяции) стока представления которых ее содержат.

После процедуры отбора остаются только строки с более высокой приспособленностью. Следовательно, строки, которые являются примерами шим с высокой приспособленностью, выбираются чаще. Кроссинговер реже разрушает шимы с более короткой определенной длиной, а мутация реже разрушает шимы с низким порядком. В связи с этим, шимы, обладающие перечисленными свойствами, имеют больше шансов переходить из поколения в поколение. Голланд (1992) [25] показал, что, в то время как ГА явным образом обрабатывает п строк на каждом поколении, в тоже время неявно обрабатываются порядка п³ таких коротких шим низкого порядка и с высокой приспособленностью (полезных шим, "useful schemata"). Он называл это явление неявным параллелизмом. Для решения реальных

задач, присутствие неявного параллелизма означает, что большая популяция имеет больше возможностей локализовать решение экспоненциально быстрее популяции с меньшим числом особей.

Еще раз остановимся на списке основных параметров ГА:

мощность множества решений Ґ (численность популяции),

длина бинарных кодировок s (длина генотипов),

количество решений, генерируемых на каждой итерации,

вероятность применения оператора локального изменения решений (мутации) М,

правило В выбора решений для воспроизводства,

тип используемого оператора глобального поиска (кроссинговера) С,

тип используемого оператора локального изменения (мутации) М,

процедура отбора S.

Почти все из приведенных параметров (кроме длины генотипа) могут динамически изменяться от итерации к итерации.

Очевидно, что восемь параметров - это достаточно много для алгоритма. То, насколько удачным окажется применение ГА при решении той или иной задачи, во многом будет определяться их удачной настройкой. Вообще говоря, строгих правил, универсальных для всех задач, нет и быть не может (по теореме "не бывает бесплатных обедов" /"no free lunch" theorem [26]).

В настоящем разделе примеры операторов скрещивания и мутации приводились с использованием стандартной бинарной кодировки. Данной способ представления информации, как уже говорилось, не единственный, а проблема кодировки представляет собой особый раздел исследований, связанный с применением генетических алгоритмов. В следующем разделе приводится обзор основных проблем в этой области.

3.3 Проблемы кодировки

Проблема устойчивости и приспособленности кодировки давно указывается в литературе. Известны ситуации, когда для получения хороших результатов при решении не сильно различающихся задач требовалось применение абсолютно разных кодировок. В последнее время проблема устойчивости и надежности кодировки выходит на первый план,

так как такая кодировка останется эффективной для более широкого множества реализаций задачи, для которой она была разработана. Такая кодировка будет также устойчива к изменению или расширению для решения различных типов задач.

В этом разделе приводятся некоторые практические и теоретические доводы, являющиеся наиболее существенными при проектировании устойчивой кодировки. Одной из тем, которой будет уделено особое внимание в этом разделе, является сравнение физического представления кодирования (генотип) со свойствами потенциальных решений оптимизируемой генетическим алгоритмом задачи (фенотип). Известно, что для многих сложных задач применяется множественное отображение между этими двумя представлениями.

Еще раз напомним, что генетические алгоритмы — это возникшие из биологических предпосылок эвристические вычислительные модели, а большая часть терминологии была заимствована из генетики. Генотипом называется генный материал (набор генов) конкретного индивида. В генетике основными элементами передачи генетической информации являются молекулы дезоксирибонуклеиновой кислоты (ДНК). В клетках ДНК вместе с протеинами формируют генотип. В генетических алгоритмах генотип определяется как строка генов - хромосома. В генотипе гены располагаются в различных местах или локусах (loci) и имеют значение - аллель (allele).

В настоящее время в литературе указывается, что кодировка выбирается согласно следующим свойствам. Именно, кодировка:

1. включает фундаментальные «строительные блоки», важные для типа задачи;

2. подчинена набору генетических операторов, способных продвигать эти блоки из родительских генотипов в генотипы потомков при образовании последних;

3. не подвержена эпистазу (epistasis), когда аллель одного гена подавляет проявление аллелей других генов (аллелем называется одно из возможных структурных состояний гена);

4. эффективно осуществляет прослеживаемое отображение фенотипа, позволяющее вычислять значение приспособленности за минимальное количество шагов;

5. использует подходящую процедуру отображения, если простая процедура отображения на фенотип невозможна;

6. включает преимущественно возможные решения — при этом допустимо использование систем штрафов и стратегий восстановления, при появлении неудовлетворительных решений;

7. подавляет изоморфные формы, т.е. когда несколько генотипов отображаются в одну точку фенотипа;

8. использует значения генов из минимально возможного алфавита, при этом бинарная кодировка считается наилучшей при условии ее применимости в рассматриваемой задаче;

9. представляет задачу на достаточном уровне абстракции - от абсолютно конкретной точки в пространстве задачи, до множества собирательных признаков, представляющих семейство возможных решений.

Каждое из приведенных положений отражает идеальное свойство кодировки. При проектировании кодировки в инженерных приложениях многими из них приходится жертвовать.

В природе один ген может влиять на несколько признаков фенотипа. Это свойство называется плейотропией. Также наблюдается и обратное, когда один признак фенотипа контролируется и определяется несколькими генами. В природе эти свойства интенсивно используются, однако генетические алгоритмы являются существенным упрощением генетического механизма в природе и не используют многие из его свойств.

Бинарная кодировка является оптимальной для задач, где каждая точка из области определения естественно отображается в строку из нулей и единиц. Однако для многих задач бинарная кодировка не подходит. Это диктуется следующими причинами:

1. эпистаз - значение бита может подавлять вклад в приспособленность индивида других битов, В, в генотипе. Это может отразиться на приспособленности, так как генотип становится нечувствительным к значениям других битов в В;

2. естественное представление - если решаемая задача требует более емкого, чем бинарный, набора символов, и эти символы могут быть организованы в «строительные блоки», отображаемые в разложимые, специфические для решаемой задачи свойства, то в этом случае алфавиты символов более высокого порядка более эффективны;

3. неудовлетворительные решения - генетические операторы могут производить неудовлетворительные решения с бинарной кодировкой, в то время как бинарная кодировка может неестественно описывать точку из области определения задачи.

В задачах оптимизации функций с действительными значениями задается оптимизируемая функция /, например f(x, у, z). Типичная цель оптимизации найти максимальное (минимальное) значение функции в заданной области. В классических генетических алгоритмах, используемых при решении подобных задач, возможное решение задачи задается в виде битовой строки.

При решении комбинаторных задач требуется расставить оптимальным образом набор символов в списке. К таким задачам относится задача коммивояжера, где символ может представлять собой отдельный город, а порядок символов в кодировке — порядок, в котором коммивояжер объезжает все города. Комбинаторная кодировка может представлять собой последовательность целых чисел: х = [4,3,0, 1,2], при этом каждое число в списке обозначает какой-либо специфический для задачи объект. Такое представление:

1. исключает отсутствующие или дублирующие значения аллелей;

2. позволяет использование высокоэффективных генетических операторов;

3. реализует простой механизм декодирования генотипа в фенотип в задаче коммивояжера.

В некоторых приложениях требуется, чтобы один или несколько аллелей повторялись по несколько раз в одном и том же генотипе. К кодировкам таких приложений можно отнести, например, польскую запись.

Процесс создания генетического алгоритма на сегодняшний день скорее можно отнести к искусству, чем к формализованному процессу. Очень многое зависит от решаемой задачи и эффективность создаваемого алгоритма целиком зависит от понимания исследователем особенностей задачи и способности спроектировать эффективное представление данных и эффективные генетические операторы.

4. Цели и задачи диссертационной работы

В настоящей диссертационной работе представлена попытка разработать методику построения и оптимизации подсистем систем ААУ на основе генетических алгоритмов.

На сегодняшний день одной из основных проблем в методологии ААУ является отсутствие методики построения систем ААУ для конкретных прикладных задач — при

наличии разработанной методологии функционирования систем ААУ, наличии нейроноподобного базиса для построения блоков подсистем, нет четких рекомендаций относительно построения топологий сетей нейроноподобных элементов, конфигурирования блока датчиков и блока актуаторов. Основной целью настоящей диссертационной работы явилась разработка методики построения систем ААУ для прикладных задач.

Применение генетических алгоритмов для решения этой проблемы продиктовано двумя основными соображениями. Во-первых, этот метод оптимизации представляет собой метод нулевого порядка, не ориентированный на свойства оптимизируемой функции, что в случае оптимизации сложных систем, подобных системам ААУ, очень важно. Во-вторых, генетические алгоритмы берут начало в биологии по своей сути моделируют процесс эволюционного отбора. По отношению к системам ААУ последнее обстоятельство представляет особый интерес, так как метод автономного адаптивного управления относится к разряду бионических, и использование генетических алгоритмов как механизма оптимизации может рассматриваться как моделирование процесса эволюции систем ААУ.

Настоящая диссертационная работа, помимо введения включающего литературный обзор и постановку задачи, содержит 4 главы.

1-я глава целиком посвящена постановке в общем виде и решении на конкретном примере задачи оптимизации блока датчиков и актуаторов систем ААУ.

2-я глава посвящена проблеме формального описания процессов, происходящих в подсистеме формирования и распознавания образов (ФРО) и введению процедуры динамического формирования сети нейроноподобных элементов. В главе показаны свойства сетей нейроноподобных элементов, получаемых таким способом.

3-я глава посвящена постановке в общем виде и решению на примере автономного мобильного робота задачи оптимизации параметров процедуры динамического формирования сети нейроноподобных элементов. В главе в общем виде приведена постановка задачи оптимизации и приведены рекомендации по построению генетического алгоритма для ее решения. Для рассмотренного примера был предложен проблемно-ориентированный генетический алгоритм.

4-я глава представляет разработанные способы применения генетических алгоритмов для оптимизации подсистемы «база знаний» (Б3)в некоторых прикладных задачах.

Результатом диссертационной работы явилось создание формальной методики синтеза систем ААУ для прикладных задач, выработка рекомендаций по созданию генетических алгоритмов для оптимизации подсистем ААУ и проверка работоспособности предложенной

методики на практических примерах, именно - на программных моделей автономного мобильного робота и космического аппарата.

Принципы построения генетического алгоритма решения задачи

Для построения генетического алгоритма необходимо определить способ кодировки и генетические операторы, определить стратегию построения исходной популяции и принципы отбора индивидов для воспроизведения. Способ кодирования является основополагающим для построения операторов кроссинговера и мутации, так как последние оперируют именно закодированным представлением индивидов (хромосомами). В задаче (4а) при определении множества поиска Y существенным является то обстоятельство, что элементами множества являются наборы из п элементов, каждый из которых может принимать значения как из континуальных множеств, так и из дискретных. Для упрощения рассуждений все множества изменения параметров у обозначим как Y{. В случае если все Yt - континуальные множества, то точка у sY есть просто точка в некотором множестве в пространстве R". В этом случае кодирование рекомендуется осуществлять в тривиальном виде, а именно: Геном представляется п хромосомами - по размерности множества Y. Каждая хромосома представляет собой действительное число, принадлежащее соответствующему множеству F/. В случае осуществления такой кодировки операторы кроссинговера и мутации можно строить по следующей схеме [27]. Пусть _р, и у 2 - точки из Y.

Оператор кроссинговера C{ylty2): YxY - Y определим следующим образом: где /-случайная переменная, равномерно распределенная на отрезке [-0,5; 1,5]. Оператор (5) является частным случаем стандартного оператора «коробочного» кроссинговера (box crossover). Распределение случайной переменной берется на отрезке [-0,5; 1,5] для предотвращения «усредняющего» поведения — когда вся популяция сходится к некоторой «средней» точке. В случае, если результирующий вектор не попадает в множество поиска, то оператор кроссинговера применяется повторно к той же паре индивидов-родителей. Оператор мутации можно построить следующим образом: расстояние между границами множества поиска по /-и компоненте. В случае если какая-либо компонента вектора у попадает вне границы множества поиска, оператор мутации применяется повторно до получения вектора, принадлежащего множеству поиска. В случае если какое-либо (или все) множества У, дискретны, то для соответствующих компонент вектора у необходимо определить операции кроссинговера и мутации. Для каждого значения множества У, необходимо определить алфавит генов - символов, кодирующих значения множества У,. Обозначим такой алфавит Л(У,). При проектировании оператора кроссинговера, в соответствии со спецификой задачи можно определить множество правил Рс замены символов из А {У). В общем виде эти правила записываются как Рс :al,aj — ак, al,aj,ak eA(Yj).

Каждому правилу сопоставляется условие его выполнения. Совокупность правил и условий их применения определяют операции над компонентами вектора у, принимающими значения из соответствующих им дискретных множеств У). Оператор мутации в этом случае строится аналогично. Для каждого дискретного множества У) используется тот же алфавит A\Y-) и вводятся правила замены символов Pm Oj- akt at,ак є A{Yt). Для этих правил также определяются условия их применения. В случае, когда все множества Yt дискретны, следует применять классические операторы кроссинговера и мутации, которые, тем не менее, могут быть до- или переопределены в зависимости от специфики исследуемой задачи. 3 Пример постановки и решения задачи оптимизации блока датчиков и блока актуаторов автономного мобильного робота В настоящей работе, предложенная постановка задачи в виде (4), рассматривается на примере постановки и решения задачи оптимизации блока датчиков и блока актуаторов программной модели автономного мобильного робота, имеющего целевую функцию — выработка стереотипов поведения при обходе препятствий в лабиринте. Моделируемый автономный мобильный робот [28] представляет собой круглый в плане объект, снабженный реверсивным движителем и рулевым управлением, тремя визуальными и четырьмя тактильными датчиками. Робот движется с постоянной скоростью v по прямой, либо по дуге окружности радиуса р, центр которой находится на прямой, проходящей через центр робота и перпендикулярной прямолинейному направлению движения. Система управления работает в потактовом режиме (дискретное время). Один такт будем считать равным А/. Визуальные датчики локаторного типа характеризуются углом раскрытия и длиной зоны видимости. Каждый датчик реагирует на наличие или отсутствие препятствия в своем секторе обзора. Выходной сигнал датчик равен 1 при наличии препятствия и равен 0 в противном случае. Тактильные датчики расположены на корпусе робота и регистрируют факты соприкосновения корпуса робота с препятствиями. Визуальные датчики расположены таким образом, что ось симметрии центрального датчика направлена по направлению движения робота вперед, а боковые датчики направлены влево и вправо от него таким образом, что зоны обзора касаются, но не пересекаются. Общий угол раскрытия визуальных датчиков не превышает п. Три тактильных датчика расположены на корпусе у оснований секторов обзора и по своему положению совпадают с пересечением зонами обзора визуальных датчиков корпуса робота (Рис. 9). Четвертый датчик занимает оставшуюся часть корпуса. Примем следующие обозначения для датчиков

Формальное описание состава, строения и работы системы формирования и распознавания образов

Обычно при создании систем управления, в которых присутствуют системы распознавания образов, перед разработчиками стоит задача поиска оптимальной конфигурации распознающей системы. Здесь под оптимальностью системы распознавания понимается способность этой системы решать задачу распознавания так, чтобы по результатам решения этой задачи управляющая система могла бы обеспечить требуемое качество управления в соответствие с заданными критериями. В общем случае, на этапе проектирования систем распознавания, на основе имеющейся априорной информации требуется определить так называемые: рабочий словарь признаков, рабочий алфавит классов и рабочие решающие правила для распознавания образов. Такие «рабочие» конфигурационные и алгоритмические элементы находятся в несколько этапов, в процессе поиска компромисса между точностью ожидаемых решений и их стоимостью, определяемой стоимостью датчиков, платежной матрицей и т.д. Важным инструментом на этапе определения оптимальной конфигурации системы является построение математической модели системы распознавания и проведения ее статистических компьютерных испытаний. При разработке рассматриваемых нами систем «Автономного адаптивного управления» (ААУ) указанная задача оптимизации выражается в необходимости определения следующих элементов и параметров системы: a) оптимального состава датчиков, их параметров, способов кодировки и предварительной обработки информации, поступающей от датчиков на блок формирования и распознавания образов (ФРО) - системы автоматической классификации, что соответствует определению «рабочего словаря признаков» распознающей системы. b) оптимальной конфигурации сети нейроноподобных элементов блока ФРО и параметров нейронов, что соответствует определению правил формирования классов для самообучаемой системы распознавания.

В главе 1 были рассмотрены способы определения оптимальной конфигурации блока датчиков системы ААУ и критерии, по которым можно производить отбор. Теперь перейдем к рассмотрению предлагаемой процедуры определения оптимальной конфигурации сети нейроноподобных элементов блока ФРО и параметров нейронов для прикладной системы ААУ, а также проблеме определения соответствующих критериев отбора.

Пусть имеется некоторый процесс (объект управления (ОУ)), для контроля которого осуществляется построение автономной адаптивной системы управления. Согласно методологии ААУ, система управления состоит из блока, анализирующего данные о состоянии процесса, блока представления знаний, блока принятия решений некоторых других блоков. Управляемый процесс (ОУ) может принадлежать различным предметным областям, описываться различными параметрами и иметь произвольную сложность. В случае создания конкретной системы управления необходимо решить вопрос об определении текущего состояния контролируемого процесса. Эта задача представляет собой задачу распознавания образов. Такие задачи успешно решаются, в частности, в рамках нейросетевого подхода. Конкретная реализация нейронной сети для построения блока распознавания относится к области предварительной оптимизации структуры нейронной сети и/или некоторого набора характеризующих ее параметров.

В настоящей работе предлагается и рассматривается метод динамической организации системы распознавания образов, а также некоторых других блоков системы ААУ.

Задача системы распознавания в методологии ААУ сводится к обработке временной последовательностей двоичных векторов, которые представляют собой закодированную информацию, поступающую в систему управления от датчиков. Согласно введенной в 1-й главе терминологии, обозначим один из таких векторов, полученный системой управления в момент времени /, как rf. Управляющая система наблюдает за всем происходящим в системе «объект управления - среда» посредством векторов rf. Будем называть все, что находится за пределами УС, просто «средой». Если среда полностью хаотична, то хаотичны и векторы т] . Если же в среде имеются некоторые пространственно-временные объекты, отличающиеся от хаоса, то УС будет наблюдать их в виде некоторых регулярных последовательностей векторов т] . Информация о найденной УС такой регулярной последовательности векторов rf, снабженная своим индивидуальным идентификатором и зарегистрированная в памяти УС, называется «образом». Сама регулярная последовательность векторов rj , автоматически обнаруженная УС, называется в нашей системе «прообразом» данного образа.

В простейшем случае прообраз может представлять собой просто один вектор показаний датчиков в текущий момент или даже его часть, т.е. это может быть неслучайная, регулярная комбинация бинарных компонент вектора if. Например, для описанного мобильного робота образ, семантически соответствующий «образу находящейся спереди стенки» (рис. 17), имеет прообраз - вектор rf = jjl,l,l,0,0,0.0, и может иметь идентификатор О,, с очередным порядковым номером, например,/ = 10. Здесь if = IJZ-j,Z,2,/ ,7J,7 ,7 ,7 ,11.

Система может сформировать и образ некоторого динамического процесса. В этом случае прообразом такого образа будет являться уже определенная временная последовательность векторов if. Например, в случае с мобильным роботом, УС может сформировать «образ наезда на стенку левым бортом» (рис. 18), прообразом которого является, например, следующая последовательность векторов if :

Решение задачи оптимизации системы управления на примере автономного мобильного робота

Эту задачу можно решить двумя способами. Первый способ состоит в априорном выяснении такой совокупности образов, опираясь на содержательное знание семантики процессов, происходящих в заданной прикладной системе. Вторым способом является введение формальной автоматизированной процедуры определения топологии нейроноподобной сети для заданной прикладной системы.

1-й способ требует от исследователя самостоятельного решения задачи формирования нейроноподобной сети на этапе проектирования системы и на основе доступных содержательных знаний о той предметной области, к которой относится заданный объект управления. Если таких знаний нет, то в этом случае приходится определять требуемое множество образов-гипотез с некоторым запасом из множества всех возможных образов, соответствующих полному перебору всех сочетаний. Как было показано, рост размерности такой задачи имеет экспоненциальный характер с ростом числа последовательных векторов в искомой закономерной подпоследовательности. В условиях отсутствия каких-либо эвристических соображений, проблему понижения размерности задачи можно решить, уменьшая длины отслеживаемых подпоследовательностей входных векторов, т.е. ограничится, например, отслеживанием комбинаций из трех и менее входных векторов, вместо четырех, пяти и т.д. Здесь можно использовать априорные знания самого общего свойства, с большой вероятностью применимые ко многим практическим прикладным системам. Например, заметим, что на практике при построении систем управления, обычно пользуются данными только по текущему значению контролируемой величины и по ее 1-й производной (используемые при этом некоторые накопители информации, например, фильтры Калмана, применяются для более точного оценивания указанных данных). Этого, по-видимому, оказывается достаточным для построения контроллеров для большинства встречающихся на практике объектов управления. Например, это проявляется в широком использовании так называемых PDP-регуляторов (пропорционально-дифференциальные регуляторы), где используется информация только о текущей величине и ее 1-й производной.

Однако мы исходим из того, что при управлении следует стремиться к использованию большей информации, чем только информации о текущей контролируемой величине и ее 1-й производной. Чем более сложные и продолжительные закономерности в предыстории поведения системы удастся найти, тем точнее будет предсказание поведения системы в будущие, относительно текущего времени, моменты, тем эффективнее будет управление. Но попытка увеличить глубину просматриваемой предыстории и поиска там закономерностей, и приводит к проблеме увеличения размерности задачи автоматической классификации (у нас -формирования образов), решению которой во многом и посвящена настоящая работа.

Любые эвристические соображения, которые могут уменьшить размерность задачи, сводятся к знанию функционирования системы, т.е. к наличию математической модели заданной прикладной системы. Но даже в этом случае зачастую не удается достаточно понизить размерность по причинам либо сложности модели, либо изменению некоторых ее параметров в процессе функционирования системы. В связи со сказанным, большинство практических задач в рамках методологии ААУ ограничивается априорным введением в систему ограниченного набора образов, которые соответствуют последовательностям входных векторов всего из одного элемента (см. выше про PDP-контроллеры). Иными словами, строятся распознаватели, которые могут лишь распознать, который из возможных входных векторов в данный момент времени наблюдается системой.

2-й способ. Проблему уменьшения размерности можно решить за счет создания алгоритма, который позволит автоматически динамически размещать в системе ФРО только те нейроноподобные элементы, чьи образы понадобятся в процессе функционирования системы с наибольшей вероятностью. Такой алгоритм должен быть основан на наличии в системе обратных связей, регулирующих динамическую перестройку сети. До настоящего времени в рамках методологии ААУ такой алгоритм реализовать не удавалось. В данной работе предлагается и подробно рассматривается именно такой алгоритм.

Опишем принцип работы системы ФРО в случае, когда топология сети нейроноподобных элементов определена, и не меняется в процессе функционирования системы.

Будем считать, что объект управления снабжен блоком из No датчиков, каждый из которых отслеживает некоторое событие в системе «объект управления - среда». Каждый датчик снабжен двумя выходами - клеммами, одна из которых (прямая) выдает единичный сигнал в случае наблюдения датчиком соответствующего события, а другая (инверсная) выдает сигнал в противном случае. Одновременное срабатывание клемм исключено. Информация с датчиков считывается в дискретном времени с некоторым интервалом At. Этот временной интервал является характерным временем работы системы. В результате, в системе ФРО фактически имеется 2 No входных полюсов, однако в результате того, что на паре клемм одного датчика в любой момент времени не может наблюдаться двух единиц или двух нулей одновременно, на входных полюсах системы в каждый момент времени будет наблюдаться только No единиц. Таким образом, на 2 No входных полюсах можно пронаблюдать всего 2N сигналов.

Соединение нейроноподобного элемента с датчиками организуем таким способом, чтобы с пары клемм одного датчика к одному нейрону могла идти только одна связь. При таком построении, один нейроноподобный элемент может иметь только No входящих связей от датчиков. Организуя соединения нейроноподобных элементов с датчиками таким способом, можно получить 2N различных типов соединений отдельного нейроноподобного элемента с датчиками - по одному на каждую возможную комбинацию сигналов с датчиков. Такая организация связей необходима, чтобы система ФРО могла оперировать сигналами с датчиков (единицами), соответствующими факту отсутствия в данный момент времени события, для отслеживания которого они предназначены. Так как каждый нейроноподобный элемент в системе ФРО соответствует уникальному образу - некоторому явлению в среде, то способ подключения нейроноподобного элемента к датчикам определяет то явление, которое нейроноподобный элемент отслеживает, т.е. образ. Очевидно, что для системы распознавания элементарным явлением будет являться присутствие на клеммах датчиков сигнала, соответствующего некоторому входному вектору г]і. В дальнейшем под «образами» будем понимать последовательности входных векторов длины L \. Принимая изложенные соображения, для каждого входного вектора rjt можно организовать уникальный способ подключения нейроноподобного элемента к датчикам. Чтобы вектор входных сигналов г), вызывал срабатывание соответствующего ему нейрона, он соединяется с полюсами датчиков следующим способом. Еслиу -я компонента вектора rjt равна 1, то организуется соединение от прямого выходного полюса у -го датчика к нейрону. В противном случае организовывается соединение с инверсным выходным полюсом. Формально справедливо следующее определение.

Определение 8. Структурой связей і нейроноподобного элемента к датчикам будем называть такую организацию связей от полюсов датчиков к нейроноподобному элементу, при которой, при наличии на датчиках входного вектора Т]і все связи берут начало на полюсах, выдающих единичный сигнал, и оканчиваются на входе нейроноподобного элемента.

Для краткого описания события наблюдения на входах системы распознавания конкретного входного вектора rji введем следующее определение.

Альтернативные и дополнительные возможности применения генетических алгоритмов в системах автономного адаптивного управления

Для описания упомянутого выше множества, введем следующее определение. Определение 14. Расширением с предысторией множества Л будем называть множество А", получаемое из А по следующим правилам. Каждой последовательности rj є А поставим в соответствие набор последовательностей, получаемый последовательным применением оператора L , а именно Lrj,L r/,...,L г/. Сформируем множество А0 присоединением к А всех таких наборов. Множество А" есть расширение множества Д0, т.е. А" = А 0. Алгоритм динамического формирования сети приводит к тому, что получаемая в результате его работы сеть обладает свойством, сформулированным как следующее утверждение. Утверждение 3. Для некоторого множества А последовательностей входных векторов, сеть нейроноподобных элементов, создаваемая в результате работы алгоритма динамического формирования, имеющего в качестве правил формирования сети матрицу G, получаемую по А, способна распознавать все элементы множества расширения с предысторией А". Для доказательства Утверждения 3 формулируем и докажем следующую лемму. Лемма 1. Если все элементы множества А последовательностей входных векторов содержатся в потоке входных векторов, воспринимаемых системой ФРО, то в этом потоке также содержатся все элементы множеств А и А" . Доказательство Леммы 1. Так как по определению множества A V eA 3rj є A :rj cirj, то если rj содержится в потоке входных векторов, то там содержится и rj . Аналогично, так как по определению множества A" V eA" 3rj є A:rj" czrj, то если rj содержится в потоке входных векторов, то там содержится и rj".

Доказательство Утверждения 3. Рассмотрим некоторое множество Л последовательностей входных векторов. Сформируем по Л матрицу смежности G, а также множество Л". Пусть на входы системы ФРО поступает поток входных векторов, содержащий все элементы множества А. По Лемме 1 он содержит в себе и все элементы множества А". Пусть yjifTjjje А, тогда в матрице G элемент gtj=\. По алгоритму динамического формирования сети в ней должен существовать нейроноподобный элемент П2 второго слоя типау, имеющий входящую связь от нейрона типа і первого слоя. Допустим, что П2 обучился, а нейроноподобный элемент Гц типа/ первого слоя НЄ обуЧИЛСЯ. ТОТ фаКТ, ЧТО ЇІ2 обуЧИЛСЯ, Свидетельствует О ТОМ, ЧТО ВХОДНОЙ Вектор J]j поступил на входы системы ФРО как минимум Мраз. Тогда по алгоритму функционирования нейроноподобных элементов, «/, принадлежащий первому слою, обучится, так как сигнал от датчиков, соответствующий входному вектору ц поступил непосредственно на входы как минимум М раз. Получаем противоречие. Следовательно система ФРО способна распознать как последовательность входных векторов {?7,»77 }»так и последовательность \Tjj\, причем [rj \ распознается системой ФРО не позже, чем [TJ TJJ]. Так как \7J,,T]J}Є А, то ПО Определению 14 Yl,,Tjj}є А", а так как также справедливо соотношение \7,}= MV »7 -}) то (т, є А Так как нейроноподобный элемент П2 обучился, то необходимо обучился и нейроноподобный элемент типа / первого слоя. А последовательность \г}(} тоже принадлежит множеству А". Применяя аналогичные рассуждения к последовательностям произвольной длины из А получаем, что сеть нейроноподобных элементов, получаемая в результате процедуры динамического формирования, способна распознать все элементы множества А", что и требовалось доказать. Утверждение 3 отражает свойство сети нейроноподобных элементов, получаемой по алгоритму динамического формирования распознавать для любой последовательности длины / 1 из А все возможные предыстории относительно каждого ее члена.

С точки зрения методологии ААУ, алгоритм динамического формирования сети ФРО можно интерпретировать следующим способом. Нейроноподобные элементы, находящиеся в 1-м слое сети соответствуют образам состояния входов системы ФРО безотносительного того, какие входные векторы поступали на входы системы до этого. При обучении нейроноподобных элементов более высоких порядков, в системе ФРО формируется набор образов, соответствующий предысториям различной длины текущего состояния входов системы. Как показано в доказательстве Утверждения 3 формирование таких образов для каждого возможного состояния происходит последовательно. Следовательно, в системе ФРО последовательно возникают образы предыстории текущего состояния входов системы, т.е. можно говорить о постепенном накоплении способности системы распознавания к уточнению «исторического» контекста (предыстории) текущего состояния входов системы. Это свойство позволяет системе ААУ накапливать знания относительно образов текущей ситуации и результатах совершенных при этом действий с последующим «специализированием» знаний с учетом предыстории возникновения текущего состояния входов системы. При необходимости построения системы распознавания, в случае, когда состав множества Д не известен, матрица смежности G выступает в роли гипотезы относительно состава множества А". О степени удачности гипотезы можно судить на основании некоторого внешнего критерия, который эксперт принимает для оценки качества функционирования системы ААУ. При прочих равных, гипотезу Gj можно считать более удачной, чем гипотезу G2, если она приводит к более высокой оценке системы ААУ в смысле введенного исследователем критерия. В этой связи можно говорить о постановке задачи подбора матрицы G. Решать такую задачу можно многими методами, в том числе и методами полного перебора. В 3-й главе настоящей работы предлагается способ организации поискового алгоритма (генетического алгоритма), позволяющего строить сети нейроноподобных элементов, обеспечивая формирование и распознавание только необходимых системе управления образов неслучайных последовательностей входных векторов. Прежде чем перейти к формальной постановке задачи и введению алгоритма ее решения, рассмотрим строение и принцип работы блоков системы ААУ, ответственных за накопление знаний и принятие решений, а также и их работу в связи с введением алгоритма динамического формирования сети ФРО.

Похожие диссертации на Применение генетических алгоритмов в системах Автономного Адаптивного Управления

Метод и алгоритмы принятия решений при управлении сложными объектами на основе экспертных системНовиков, Дмитрий Борисович

Планирование выполнения заданий в распределенных вычислительных системах с применением генетических алгоритмовШаповалов, Тарас Сергеевич

Применение нейросетевых алгоритмов в системах поддержки принятия решений при решении бизнес-задачБолдырев, Михаил Николаевич

Иерархическое конфигурационное управление в системе автоматизации разработки крупных программных комплексовМаксимов, Андрей Вячеславович

Управление данными в системе Таблично-ориентированного программированияКрашенинников, Сергей Вениаминович

Управление памятью в системах автоматизированного распараллеливания программКонев Илья Михайлович

Управление данными во встроенных системахБульонкова, Анна Андреевна

Управление производительностью параллельной вычислительной системы при обработке запросовМьо Тант

Исследование и разработка интерактивной компьютерной системы поддержки принятия решений при управлении производством с неспециализированным оборудованием Андреев Алексей Сергеевич

Оперативное управление распределением нагрузки в неоднородных информационных системахМоисеев Тимур Николаевич