4.2.  Архитектуры и стратегии эволюционного моделирования

Необходимым условием эффективной работы интеллектуальных ИС с использованием ГА является ее автоматическая или автоматизированная адаптивная настройка на объект исследования.

Отметим, что решение инженерных задач осуществляется последовательными, итерационными, точными или комбинированными алгоритмами [116-118]. В основном эти алгоритмы выполняют совершенствование начального варианта решения, полученного одним из случайных методов. Такой подход, кроме известных преимуществ, обладает трудноразрешимыми недостатками:

•    все алгоритмы, кроме точных, часто останавливаются на локальных решениях, которые могут быть далеки от оптимальных, и с трудом осуществляют выход из локальных «ям»;

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

•    в качестве исходного используется лишь один вариант решения;

•    такие методы весьма чувствительны к выбору начальных условий.

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

Здесь блок эволюционной адаптации — это специальный блок, который на основе обратных связей с учетом синергетических и гомеостатических принципов позволяет управлять процессом генетического поиска. Согласно данной схемы на первом этапе случайным, направленным или комбинированным методом получают некоторое подмножество решений Р рассматриваемой задачи. Эти решения образуют текущую генерацию или популяцию исследуемых решений на шаге t (t = 0,1,..., No). Далее вводится или вычисляется ЦФ. Вычисление ЦФ является очень сложной задачей, причем от точности ЦФ зависит качество будущих решений.

Отметим, что для каждой оптимизационной задачи желательно строить свою ЦФ. При построении ЦФ необходимо использовать знания о конкретной задаче. На основе ЦФ производятся ранжирование и сортировка популяции решений Р. Затем в результате различных методов селекции в Р подбираются пары для применения различных генетических операторов. После применения операторов ОК, ОМ, инверсии, сегрегации, транслокации, удаления, вставки и т.д. получается новое подмножество решений Р'. Оно объединяется с первоначальным подмножеством решений. Получается новое множество Рга = Р U Р!. Используя ЦФ, производится анализ РГа- Все элементы в РГА (решения задачи), значения ЦФ которых хуже заданного порога, являются с нашей точки зрения неперспективными решениями и удаляются. Получается новое множество Р^А, причем \РуА\ = |Р|. Если данное условие не выполняется, например, |Р/Л| < \Р\, то в Р[А включается элемент с лучшими характеристиками из отброшенных. Множество РрА объявляется новой текущей популяцией решений и далее процесс может повторяться на основе блока эволюционной адаптации итерационно до получения подмножества или одного оптимального решения.

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

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

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

кусственной селекции [16-19,119], метагенетической параметрической оптимизации, стохастически-итерационные генетические и поисковые [120], методы «прерывистого равновесия» [121], объединения генетического поиска и моделирования отжига [122].

Часто в ЭМ сначала выполняется этап макроэволюции, т. е. создается не одна популяция, а некоторое множество. Генетический поиск здесь осуществляется путем объединения хромосом из различных популяций. Опишем модифицированную архитектуру генетического поиска с миграцией и искусственной селекцией (рис. 4.8). Здесь блоки 1-3 реализуют простой ГА. Заметим, что в каждом блоке выполняется своя искусственная селекция. В первом блоке — селекция на основе рулетки. Во втором блоке используется селекция на основе заданной шкалы. В третьем блоке — элитная селекция. В блок миграции каждый раз отправляется лучший представитель из популяции. Связь между блоками 1-3 осуществляется путем последовательной цепочки 1-2, 2-3. В блоке 4 осуществляется установление баланса на основе синергетических и гомеостатических принципов и управления всем процессом генетического поиска.

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

ресурсов может быть доведена до N блоков, причем 7V — 1 блоков могут параллельно осуществлять эволюционную адаптацию и через блоки миграции обмениваться лучшими представителями решений. Последний блок собирает лучшие решения, он может окончить работу алгоритма или продолжить генетическую оптимизацию. Для таких схем авторы предлагают использовать Платоновы графы [123,124], т. е. правильные многоугольники, которые, как считалось в древних учениях, обладают внутренней красотой и гармонией [51-56].

На рис. 4.9, а-д приведены упрощенные схемы организации связей при генетическом поиске на основе Платоновых графов. На рис. 4.9, а на основе тетраэдра; б—гексаэдра (куба); в — октаэдра; г — икосаэдра; д — додекаэдра. На рис. 4.9 использовано отношение вход-выход «1-многие». Отметим, что здесь могут быть использованы и другие отношения вход-выход: «1-1»; «многие-1»; «многие-мноше». Эффективность таких, отношений проверяется экспериментально.

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

 

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

 

 

На рис. 4.10, г приведена последовательная схема взаимосвязей ГА при генетическом поиске на основе треугольников. Здесь происходит моделирование идей, реализованных на основе треугольника Фреге, за счет создания устойчивых строительных блоков на высших иерархических уровнях. На рис. 4.10, д приведена последовательная схема поиска на основе модифицированного полного графа на пять вершин. Этот граф является

верхней оценкой минимально непланарного графа [123]. Он также состоит из треугольников. Такая схема генетического поиска применяется для решения комбинаторных оптимизационных задач, связанных с расположением ребер графа на плоскости. Отметим, что можно строить схемы генетического поиска на основе полных графов на любое количество вершин. На рис. 4.10, е приведена последовательная схема поиска на основе моделирования движения информационных потоков в пространстве. Она моделирует упрощенную схему реализации противоположностей ИНЬ-ЯН. На рис. 4.10, ж приведена последовательная схема поиска на основе ячеечной структуры. Здесь также используются строительные блоки, состоящие из треугольников, а также идеи самоорганизации, построение порядка из хаоса и создание фракталов.

Такие схемы, состоящие из нескольких ГА, выполняемых параллельно, последовательно-параллельно и параллельно-последовательно, в отличие от существующих позволяют во многих случаях выходить из локальных оптимумов.

Процесс метагенетической оптимизации заключается в следующем (рис. 4.11).

 

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

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

Метод прерывистого равновесия [121] основан на палеонтологической теории, которая описывает быструю эволюцию за счет вулканических и других изменений земной коры. Он аналогичен моделям эволюции де Фриза. Для применения данного метода предлагается после каждой генерации случайным образом «перемешивать» элементы в популяции, а затем формировать новые текущие популяции, применяя к ним стандартные и модифицированные генетические операторы. Здесь можно предложить, как аналог из ЕС, бессознательный отбор родительских пар и синтетический отбор «лучших» хромосом. Далее случайным образом смешать результаты обоих отборов и не оставлять размер популяции постоянным, а управлять им на основе блока эволюционной адаптации в зависимости от наличия «лучших» элементов. Такая модификация метода прерывистого равновесия может позволить сократить неперспективные популяции и расширить популяции, в которых находятся «лучшие» элементы. Метод прерывистого равновесия — это мощный стрессовый метод изменения окружающей среды, который используется для эффективного выхода из локальных оп- тимумов.

В 1953 г. Метрополис предложил вычислительную процедуру, воспроизводящую механизм отжига металлов, для моделирования состояния равновесия сложных систем при заданной конечной температуре. Суть этой процедуры состоит в следующем. На каждом шаге случайным образом осуществляется малое возмущение конфигурации и вычисляется изменение АЕ энергии системы. Новая конфигурация системы принимается с вероятностью 1, если АЕ ^ 0, и с вероятностью, равной ехр(—АЕ/Ы), если

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

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

Реализация вероятностного механизма в оптимизационном алгоритме на основе моделирования отжига осуществляется следующим образом. Если в результате перестановки элементов на дискретном рабочем пространстве произошло увеличение целевой функции F, то генерируется случайное равномерно распределенное число R в диапазоне [0,1] и проверяется условие

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

Объединение ГА и моделирования отжига позволяют получать более качественные результаты за счет усложнения процедуры оптимизации [107, 122]. Например, на основе ПГА можно получить некоторое подмножество родителей с лучшими характеристиками и для одного из них. (наилучшего) гаи некоторого подмножества применить оптимизационную процедуру моделирования отжига. Такое объединение можно делать различными способами. К сожалению, процедуры моделирования отжига требуют больших вычислительных затрат. Для повышения скорости такого поиска можно выбрать одну ветвь дерева решений и провести моделирование отжига, как усложненный поиск в глубину.

Перейдем к рассмотрению основных стратегий ЭМ. Комбинации теории эволюций Ч. Дарвина и Ж. Ламарка были использованы в генетическом поиске [18, 23-25]. Было показано, что эволюция Ж. Ламарка оказывается наиболее эффективной, когда популяция имеет сходимость в область локального минимума, в отличие от стандартного ГА. Опишем схему поиска, основанную на моделях указанных эволюций. Здесь эволюция Ч. Дарвина реализуется в виде ГА, в который встроен алгоритм эволюции Ж. Ламарка. Он содержит элемент (шкала, No), который используется для контроля эволюции Ж. Ламарка. Шкала — это действительное число от 0 до 1, опреде-

ляющее процентное соотношение хромосом в популяции, к которым будет применена эволюция Ж. Ламарка, а N с — число генераций ГА.

Модель эволюции Ж. Ламарка содержит пять предикатов, определяющих изменение ГА:

•    селекция. Этот предикат выбирает тип селекции;

•    генетические операторы. Этот предикат выбирает соответствующие генетические операторы согласно управляющим воздействиям из блока эволюционной адаптации;

•    целевая функция. Предикат применяет ЦФ для выбора подходящих хромосом;

•    адаптация. Этот предикат осуществляет подбор параметров генетического поиска на основе обратных связей и воздействия внешней среды;

•    цикл:

На рис. 4.12 показана упрощенная модель генетического поиска при совместной эволюции Ч. Дарвина и Ж. Ламарка. Первый элемент эволюции Ж. Ламарка предусматривает случай, когда ЛПР применяет ее ко всей популяции (шкала = 1). Этот элемент собирает полное множество номеров хромосом в популяции и для них вызывает алгоритм Ж. Ламарка. Второй элемент используется, если процентное соотношение в популяции больше 0. Тогда число хромосом для процесса вычисляется по параметру процентного соотношения и размеру популяции и соответственно обрабатывается набор номеров хромосом в популяции.

Второй элемент эволюции Ж. Ламарка вызывает предикат для выбора множества номеров хромосом, лежащих, в пределах от 1 до размера популяции. Для выполнения этого предикат многократно повторяется до тех пор, пока не будет набран требуемый, размер. Селекция по стандартному ГА используется для выбора хромосом. Заметим, что если большой процент популяции подвергается эволюции Ж. Ламарка, то этот процесс может быть медленным, так как выбор хромосом для данной, эволюции требует дополнительного времени. Если ЛПР не желает использовать эволюцию Ж. Ламарка, то выбираем шкалу равную 0.

Кроме основных введен предикат цикла, который контролирует эволюцию Ж. Ламарка перечнем выбранных хромосом. Для каждой, хромосомы определяются ЦФ. Затем выполняется локализованный поиск для заданного числа итераций, определяемых параметром Nq. Результатом этого локализованного поиска является, возможно, новая хромосома с новой ЦФ. Если новая ЦФ лучше, чем у исходной хромосомы, то она заменяется оптимизированным выражением. В противном случае замены не происходит. ЛПР на основе блока эволюционной адаптации может утвердить или отменить эволюцию Ж. Ламарка. При использовании поискового алгоритма исследуется фенотип и при достижении лучших результатов соответствующий. генотип (который, идентичен фенотипу в этой, задаче) исправляется.

Шаблоном локализованного поиска является метод горизонта, «первый наилучший» или поиска в глубину. Они анализируют хромосому с лучшей. ЦФ для поиска лучшего локального оптимума. Отметим, что оператор мутации разрешен для всего поискового пространства. Блок поиска по-

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

В схему совместного алгоритма эволюций можно включить любой набор поисковых алгоритмов. ГА использует гибридный устоявшийся подход, в котором генерации определяются для исследования эволюции Ж. Ламарка и накопления статистики. Это позволяет частично решать проблему предварительной сходимости алгоритмов. Экспериментальные исследования показали, что максимальное время при использовании эволюции Ж. Ламарка не пропорционально числу исследованных хромосом, и это используется при исследованиях на следующих поколениях ГА. Эффективность использования эволюции Ж. Ламарка с эволюцией Ч. Дарвина зависит от исследуемой проблемы. Локализованная оптимизация с использованием ламаркизма будет повышать среднюю ЦФ популяции и, следовательно, ускорять выполнение поиска в исходном ГА. Выполнение эволюции Ж. Ламарка может быть изменено в процессе поиска.

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

Здесь Р — начальная популяция альтернативных решений. На создание новой популяции Р' оказывают влияние не только ГА и блок эволюционной адаптации, но и внешняя среда. Из таких строительных блоков, как из «кирпичиков», может быть построена интеллектуальная ИС любой сложности.

Отметим, что принятие решений в неопределенных, расплывчатых условиях при решении инженерных задач — это генерация возможных альтернативных решений, их оценка и выбор лучшей альтернативы [125-127]. В последнее время интерес представляют компьютерные системы поддержки принятия решения, основанные на формализации методов входных решений, вычислении ЦФ и алгоритмизации процесса выработки решений. Важное назначение систем поддержки принятия решения состоит в том, чтобы находить скрытый порядок в хаосе возможных альтернативных решений, который окружает ЛПР. Поэтому выделение некоторого подмножества решений задач относится к проблемам выбора и принятия решений.

Задачей принятия решений называют кортеж Z = (N, Ѳ) (где N — множество вариантов решений задачи; Ѳ — принцип оптимальности, дающий представление о качестве вариантов, в простейшем случае правило предпочтения вариантов). Решением задачи а называют множество Non С С N, полученное на основе принципа оптимальности. Задачу Z решают следующим образом. Составляют множество N, если это возможно, т. е. определяют варианты, а затем решают задачу выбора. Стандартная структура система поддержки принятия решения состоит из следующих основных блоков [126]:

•    генерация возможных альтернатив решений (сценариев);

•    оценка решений (построения ЦФ));

•    согласование решений, анализ динамики развития ситуации;

•    выбор решения (группы решений), сценария;

•    оценка соответствия принятых решений заданным целям.

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

ПГА — простой генетический алгоритм, реализующий модель эволюции Ч. Дарвина. Блок эволюции Ч. Дарвина и эволюции Ж. Ламарка — это модель совместной их реализации. Эффектор объединяет свойства экспертной системы, ЛПР, блоков установления аналогий и повторителей. Компенсатор регулирует динамически изменяемый размер популяции решений, а именно, расширяя, сужая или оставляя ее постоянной. После реализации эволюции Ч. Дарвина и эволюции Ж. Ламарка компенсатор при взаимодействии с внешней средой реализует синергетические принципы, а эффектор поддерживает гомеостаз, при этом лучшие хромосомы отправляются для смешивания популяций и выхода из локальных оптимумов.

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

 

На рис. 4.16 приведена архитектура принятия решения генетического поиска с использованием блока эволюционной адаптации. Блоки сумматор, редуктор и фильтр позволяют повысить эффективность реализации эволюции и скорость принятия решения. Следует отметить, что в инженерных задачах большой размерности процесс решения резко усложняется, но параллельное выполнение ГА на порядок снижает время реализации алгоритма. Схемы с подобными обратными связями присутствуют в ЕС и эффективно функционируют.

 

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

В эволюции ЕС и ИС важное значение имеют объединения всех видов и форм эволюции. На рисунке 4.17 показана базовая структура генетического поиска на основе использования моделей эволюций Ч. Дарвина, Ж. Ламарка, де Фриза. Здесь на основе шкалы эволюции при взаимодействии с внешней средой вырабатываются сигналы 0 — на выполнение эволюции

Ч.   Дарвина; 1 — на реализацию эволюции Ж. Ламарка; 0,5 — на реализацию эволюции де Фриза. Повторение генетического поиска возможно при предварительной сходимости алгоритма или при достижении заданного значения ЦФ. Особенностью данной схемы является использование поисковых стратегий, описанных выше.

На рис. 4.18 приведена модификация базовой структуры генетического поиска на основе использования моделей эволюций Ч. Дарвина, Ж. Ламарка, де Фриза и К. Поппера. Здесь, в отличие от базисной структуры, шкала эволюции, взаимодействуя только с внешней средой, вырабатывает сигналы на выбор эволюции Ч. Дарвина (0), Ж. Ламарка (1), де Фриза (0,5). После этого выполняется модель эволюции К. Поппера, реализую

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

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

Взаимодействие противоположностей на одном структурном уровне и между смежными уровнями, как правило, подчинено методу золотого сечения. Модель интеллектуальной ИС в целом состоит из множества взаимодействующих, диалектических пар (ИНЬ-ЯН). Нормальное функционирование ЕС и ИС (их возможности и свойства) связано с равновесием в них полярных элементов ИНЬ-ЯН. На рис. 4.19 показана модель взаимодействия указанных полярных элементов в процессе генетического поиска.

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

В [91] предложена двухуровневая система ГА (DAGA2). Здесь реализована идея многоуровневой эволюции, когда ГА используются на двух уровнях. На первом уровне DAGA2 выполняет параллельный прогон ГА (обычных ПГА), пока они не начнут сходиться. Затем в наилучших решениях (хромосомах) каждой популяции определяются ближайшие друг к другу объекты (гены), которые образуют кластеры. На основе кластеров создается новая хромосома как объект для второго уровня DAGA2. Отметим, что DAGA2 может действовать как параллельный ГА со скрещиванием в локальной области или на основе «островов». DAGA2 действует как самоадаптируемый ГА в смысле «выживания» приспособленного решения. В этой архитектуре хромосомы из подпопуляций в грубой (неточной) модели задачи мигрируют в другие подпопуляции в негрубой (точной) модели задачи. Эта структура может быть модифицирована на любое число уровней, в зависимости от памяти и временных ограничений на получение результата.

Известны также параллельные ГА со скрещиванием в локальной области и на основе «островов» [91]. В первом случае хромосомы одной популяции моделируются как точки в некотором пространстве. Вводится отношение близости, и генетические операторы применяются к хромосомам, расположенным близко друг от друга. Во втором случае популяции эволюционируют в течение нескольких заданных генераций независимо на определенных «островах», а затем производится обмен генетическим материалом, и снова—независимая эволюция. Этот процесс может происходить в цикле разнообразными способами.

Я. Парми [128] ввел понятие кластерно-ориентированного ГА, основанного на стратегии быстрого разбиения поисковых пространств на области

высоких значений ЦФ. В кластерно-ориентированном ГА установлен режим мутации переменных ГА, введен адаптивный фильтр, отсекающий решения с низким значением ЦФ, причем нижняя граница ЦФ адаптивна в смысле зависимости от решений на каждой генерации. В качестве модификации кластерно-ориентированного ГА предлагается начальное структурирование популяции на основе ЦФ, реализация эволюции Ч. Дарвина, Ж. Ламарка, де Фриза и К. Поппера в каждом поисковом пространстве, использование эволюции ИНЬ-ЯН и адаптации. Выбор генетических операторов здесь осуществляется на основе динамической ЭС, с использованием статистических методов оптимизации.

Дж. Шаффер и Л. Эшельман предложили проблемно-ориентированные ГА, вырабатывающие решения (фенотипы) комбинаторных задач, представленных в виде задач параметрической оптимизации, состоящих из строк параметров (генотипов) [91]. В данных ГА создается проблемно- ориентированный генератор решений (хромосом). Кроме этого, строится эвристический генератор планов, состоящий из набора шаблонов решений. Далее на основе «жадной» эвристики и ЦФ строится возможный план решения задачи. Изменяя параметры, ГА заставляет «жадные» эвристики вырабатывать большое число разнообразных хромосом. Взаимодействие ГА и эвристического генератора планов позволяет устанавливать время генерации, производить адаптацию наборов параметров, фокусировать наилучшие решения.

К. Де Йонг [91, 128] предложил в популяциях, имеющих общие хромосомы, выбирать для дальнейшего поиска N • Nq элементов. Здесь Nq — число генераций, а N — мощность начальной популяции. Потомки размещаются в новые популяции. Хромосомы из популяции выбираются случайно. Следовательно, при выборе размера популяции нет точных рекомендаций — большая популяция дает потери хромосом; малая популяция дает большую возможность попасть в плохой локальный оптимум.

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

где dt — отрезок времени. При коэффициенте г = 0,05 популяция удваивает свою численность каждые 14 генераций. Для роста всегда существуют пределы, и приведенная зависимость справедлива на ограниченных промежутках времени.

В [11] сформулированы ограничение на рост популяции: любая внешняя среда способна обеспечить существование популяции только определенного размера, коэффициент прироста должен снижаться при приближении размера популяции к Np. Следовательно, переменный коэффициент г сделал процесс нелинейным. Приведем пример модели роста произвольной

популяции. Пусть Np — начальная численность популяции, Щ — ее численность через і генераций (t е Nq), коэффициент прироста по определению есть относительное изменение численности за одну генерацию (t = 1):

Пусть а — константа. Следуя [11, 64, 65, 88], сформулируем вытекающий из (4.2) закон динамики роста популяций:

Через і генераций численность популяции будет

При N^ = 0 и N^ = 1 роста популяции нет. Отметим, что параметр а влияет на детерминированность и хаотичность процесса изменения популяции. Использование выражений (4.2) и (4.3) помогает планировать генетический поиск и определять критерии окончания процесса поиска.

К. де Йонг предложил 5 вариантов планирования процесса генетического поиска [91, 128]:

•    элитная модель. Пусть p'(t) — лучшая хромосома, сгенерированная за время і. Если после генерации (t + 1) хромосома pf(t) не попала в (t + 1), то pf(t) включается в эту генерацию как Np + 1 член;

•    модель с ожидаемой величиной. Здесь для селекции выбирается хромосома и вычисляется ожидаемое число потомков для каждой популяции;

•    элитная модель с ожидаемой величиной. Это — объединение первой и второй моделей;

•    crowding factor (CF). Когда хромосома потомок появилась после генерации ГА, она анализируется на предмет выживания. Хромосомы с ЦФ ниже средней выбираются из подмножества CF и удаляются. Обычно CF = 2,3,4;

•    модель генерации генетических операторов.

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

Одной из наиболее простых технологий генетического поиска в отличие от ПГА является так называемая «устойчивая репродукция» (stady-state reproduction) [90]. Она соответствует следующему алгоритму:

1.   Создать к потомков (хромосом) из начальной популяции через репродукцию.

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

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

4.   Конец работы алгоритма.

При оценке хромосом используются два основных подхода: линейная нормализация, определение «окна». В первом случае производится упорядочивание хромосом по убыванию ЦФ. Создается ЦФ с постоянной величиной и шкала линейного уменьшения ЦФ. Во втором случае определяется хромосома с наименьшей ЦФ. Хромосомы, у которых значение ЦФ меньше определенного, не участвуют в репродукции. Такой метод показал эффективные результаты на детерминированных проблемах [89].

Дж. Шапиро, М. Реттрей, А. Прюгель-Беннетта [91] разработали теорию, которая на основе принципов статистической механики анализирует динамику ГА при решении комбинаторных задач. Статистическая механика используется в двух эвристиках: в первой — для надежного расчета ожидаемых результатов применения генетических операторов и для расчета отклонений от ожидаемых значений; во второй — для анализа информации, полученной из макропараметров методом максимума энтропии. В [91 ] введено понятие корреляции хромосом, т. е. оценки, насколько «похожи» между собой хромосомы. Очевидно, что для любой популяции на основе математического ожидания и распределения ЦФ можно вычислить корреляцию. Каждому значению корреляции ставится в соответствие энтропия, равная минус логарифму от числа популяций, на которых корреляция принимает данное значение. Тогда максимум энтропии, согласно [91], соответствует наиболее часто встречающемуся значению корреляции среди всех популяций фиксированного размера. Корреляция (сходство) между хромосомами рі и pj популяции Р, взвешенной в соответствии с относительной важностью элементов, определяется соотношением

где L — длина хромосом в популяции, Р = {р\,р2,.. -Pi,Pj, • • •}, \Р\ = = Np, t — номер генерации ГА, г, j — метки хромосомы в популяции. Тогда средняя корреляция

В работе [91] предлагается понятиям ЦФ и функции полезности (пригодности) (ФП) придать разный смысл. ЦФ — это средство измерения качества отдельно взятой хромосомы. ФП — описывает способ выбора хромосом из популяции. Тогда вероятность выбора хромосомы рі определяется ее ФП F1 в соответствии с выражением:

Конкретная форма отбора хромосом определяется функциональной зависимостью между ЦФ и ФП.

В [129] предложен групповой ГА с направленной мутацией. Он состоит из двух уровней. На верхнем уровне ведется групповой, а на нижнем — индивидуальный поиск. На первом этапе берется популяция размером в несколько раз больше, чем в ПГА, с целью большего охвата всего пространства поиска. Элементы в популяции оцениваются, затем хромосомы с ЦФ меньше средней отбрасываются, а из оставшихся хромосом составляются подпопуляции. Далее поиск ведется внутри отдельных групп. В отличие от [ 129] далее предлагается групповой ГА с направленным набором генетических операторов (ОК, ОМ, инверсии, сегрегации, транслокации, удаления, вставки и различными их модификациями) и блоком эволюционной адаптации. Приведем структуру модифицированного нечеткого алгоритма:

1.   Сконструировать начальную популяцию Р размера \Р\ = Np, pi Е Р,

і = мѵ

2.   Определить ЦФ для всех хромосом в популяции и вычислить

среднюю ЦФ по формуле:

3.   На этапе ОР (селекции) оставить в популяции хромосомы с ЦФ больше средней по всей популяции (j = 1, Np), f (pj) > /ср.

4.   С помощью шкалы эволюции на основе взаимодействия с внешней средой, блоками адаптации и ЭС выбрать модели эволюции Ч. Дарвина, Ж. Ламарка, де Фриза или К. Поппера.

5.   Образовать группы хромосом по принципу их. пространственной близости I pi —pj\ ^ ё, где 5 — параметр соседства: <5 = 2 Lk/Np, где — длина отрезка, на котором задана ^-компонента хромосом pi npj. При этом хромосомы с «малопригодной» ЦФ удаляются, и каждая группа как бы исследует отдельный локальный оптимум.

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

7.   Применить генетические операторы ко всем хромосомам следующим образом:

Здесь w — случайное число из интервала

где і — номер генерации ГА, і Е 1, Nq\ Nq — заданное число генераций; 6 — параметр соседства, не позволяющий хромосомам выходить из заданной группы после проведения генетических операторов. Генетические операторы реализуются, пока не будут выполнены условия остановки ГА.

8.   Конец работы алгоритма.

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

удовлетворяющим условию

Успех предложенного нечет

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

На рис. 4.21 показана укрупненная схема параллельного генетического поиска при разбиении популяции на две подпопуляции. Здесь в блоках генетических операторов выполняются операторы ОК, ОМ, инверсии, сегрегации, транслокации, удаления и вставки с учетом выражения (4.4). В блоке редукции производится удаление хромосом с ЦФ ниже средней.

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

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

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

Ч.   Дарвина, Ж. Ламарка, де Фриза и К. Поппера.