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

В отделе математических методов регионального программирования ФИЦ ИУ РАН ведутся работы по формализации процесса стратегического управления регионом [1, 2] как дальнейшего развития в современных условиях традиционной для отдела проблематики долгосрочного регионального планирования, прежде всего для нефтегазовой отрасли [2].

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

(с) А. Н. Соломатин, 2024

• (с) Федеральное государственное автономное образовательное учреждение высшего образования

  «Московский физико-технический институт (национальный исследовательский университет)», 2024

и дисфункций, и рассмотрены различные свойства таких систем [3]. Для диагностики допустимости систем и анализа уровня патологий и дисфункций было предложено использовать аппарат когнитивных моделей [4, 5].

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

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

Настоящая работа лежит на стыке двух таких актуальных направлений искусственного интеллекта, как когнитивное моделирование и генетические алгоритмы [6, 7], которые предлагается использовать для решения оптимизационных задач общего вида на когнитивных моделях. Учитывая специфику решаемой задачи оптимизации на когнитивных моделях, было предложено использовать генетические алгоритмы вещественного кодирования [8, 9].

1.    Когнитивное моделирование

Приведем основные положения когнитивного моделирования в соответствии с [4, 5]. Когнитивная модель (КМ) предоставляет собой нагруженный ориентированный функциональный граф, отражающий причинно-следственные связи и функциональную зависимость между различными факторами влияния (концептами) моделируемой системы и обеспечивающий принятие решений при решении различных практических задач.

Вершинами КМ являются различные концепты — факторы, цели, проблемы, свойства и т.д., среди которых можно выделить: а) управляющие концепты — концепты, на которые можно воздействовать, подавая управляющий импульс; б) целевые концепты — концепты, изменение которых является целью управления. Для концептов задаются количественные значения — объективно измеряемые либо нечеткие.

Когнитивная модель задается матрицей смежности, отражающей силу взаимного влияния концептов, причем значения в матрице принадлежат сегменту [—1, +1] (отображения являются сжимающими). При связи между концептами со знаком «плюс» усиление концепта-причины ведет к усилению концепта-следствия (положительная связь), при связи со знаком «минус» — к его ослаблению (отрицательная связь).

Веса связей КМ обычно отражают преобразование процентных изменений причин в процентные изменения следствий: так, связь на КМ между концептами А и В со значением «+0.6» означает, что при увеличении концепта А на. 100% концепт В увеличится на 60%.

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

При когнитивном моделировании наиболее часто используется модель суммирования действия концептов. В этом случае состояние г-го концепта в момент времени t + 1 является функцией от состояния данного концепта в предыдущий момент времени t, внешнего управляющего воздействия на него в момент t + 1 и изменений в момент t состояния других концептов, влияющих на г-й. То есть динамика КМ описывается следующим образом:

п

Xi(t + 1) = Xi(t) + p*(t + 1) + ^ Wi,kpk(t), k=1

где Xi(t), Xi(t + 1) — значения концепта Xi в моменть i времени tn t + 1;

p*(t + 1) — изменение в момент t + 1 г-го концепта за счет некоторого внешнего воздействия (внешний управляющий импульс концепта);

Рк (t) = Xk (t) —Xk(t — 1) — изменение к-то концепта с момента t — 1 до момента t для всех 'значений к. т.е. для всех п концептов. непосредственно влияющих на г-н копцепт: pk (0) = 0:

^wi,k — степень влияния к-то концепта на г-й концепт (значение матрицы смежности когнитивной модели).

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

Обычно решаются следующие задачи когнитивного моделирования.

• 1.    Статический анализ — это анализ текущей ситуации, позволяющий определять:

• — силу взаимного влияния между каждой произвольной парой концептов и степень доверия к знаку этого влияния (консонанс);

• 2.    Динамический анализ непосредственно обеспечивает решение задач когнитивного моделирования за счет генерации различных сценариев развития ситуации на КМ в динамике на основе модели импульсного процесса. Решаются следующие три основные задачи:

• —    саморазвитие: моделируется развитие ситуации на КМ в случае отсутствия каких-либо внешних управляющих импульсов, чтобы оценить последствия текущих тенденций на модели;

• —    прямая задача решается наиболее часто: требуется смоделировать развитие ситуации на КМ в случае наличия внешних управляющих воздействий, для чего следует выбрать совокупность управляющих концептов, моменты и силу воздействия на них;

2.    Оптимизационные задачи на когнитивных моделях

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

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

Результаты моделирования на КМ обычно выдаются в виде таблиц и графиков в разрезе концептов и моментов времени моделирования.

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

Рассматриваемый в настоящем пункте материал отражает результаты, полученные в [3]. Когнитивное моделирование, в первую очередь решение прямой задачи динамического анализа с использованием управляющих импульсов, не всегда может удовлетворить потребности конечного пользователя. Ведь решение такой задачи не позволяет ответить на вопрос: какова должна быть комбинация управляющих импульсов (состав и характеристики), чтобы получить наилучшую в некотором смысле совокупность значений целевых концептов?

Нетрудно видеть, что среди задач анализа и моделирования на КМ отсутствует стандартная задача оптимизации, а исследование КМ обычно происходит в режиме моделирования без решения оптимизационных задач, как это обычно имеет место при исследовании сложных систем. Очевидно, что отсутствие для КМ традиционного подхода «simulationoptimization», несомненно, уменьшает значимость когнитивных моделей для решения конкретных практических задач.

Можно предположить, что это связано с двумя взаимосвязанными причинами:

• —    оптимизационная задача на КМ наиболее общего вида является неполиномиальной (что будет показано ниже): «в какие вершины модели, в какие моменты времени моделирования и сколько единиц внешнего импульса следует подать, чтобы обеспечить экстремум заданной целевой функции»;

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

Пусть:

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

N — мощность множества U:

• k , k < N- максимальное число управляющих концептов, на которые можно подать управляющие импульсы при решении конкретной задачи;

• L    — количество единичных импульсов (количество уровней мощности импульсов), которые могут быть поданы на концепты; в их числе L/2 положительных импульсов и L/2 отрицательных;

Т — время, в течение которого могут быть поданы управляющие импульсы; при этом время Т должно быть таким, чтобы импульс, поданный в любой управляющий концепт, успел «пройти» по всей КМ.

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

При к = 1 внешний импульс некоторой мощности/знака может быть подан в любой из N концептов в некоторый момент времени. При к = 2 в каждый из двух концептов (либо только в один из них) импульс может быть подан в свой момент времени, своей мощности/знака и т.д.

Поэтому оценка вычислительной сложности данной оптимизационной задачи составит

k

£С^ (LT )ⁱ.

i=1

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

В работе [3] была рассмотрена возможность решения частных оптимизационных задач меньшей размерности. Широко используется подача только единичных импульсов и только на одну вершину, что во многом соответствует сложившейся практике управления, когда все ресурсы переносятся на некоторый наиболее важный участок. Соответствующая частная оптимизационная задача имеет вид: «на какой управляющий концепт и в какой момент времени следует подать единичный импульс, чтобы обеспечить экстремум заданной целевой функции». Оптимальное решение можно искать методом полного перебора, т.к. вычислительная сложность задачи составляет всего О(кТ).

Однако методом полного перебора можно решать и более содержательные задачи:

• —    параметр Т можно ограничить значением 6: в стандартных КМ число вершин редко превышает 20-30, и при больших значениях Т распространение импульсов может не обойти все вершины модели;

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

• —    для практических целей можно положить L = 4, что позволяет задать по два положительных и отрицательных импульса (сильный и слабый).

Например, при значениях параметров N = 6, к = 3, Т = 3, L = 4, что вполне приемлемо для многих практических задач, будет получено 36 782 варианта, которые могут 6bitb рассмотрены весьма быстро:

Е С6 (4 х 3)’ = 36 782.

’=1

Пусть:

• i = {1, 2, ... ,п} — номера вершин орграфа КМ, соответствующих целевым концептам модели;

• j — номер очередного рассчитываемого варианта при решении оптимизационной задачи;

• t = {1, 2,..., То} — номера моментов времени (шагов) периода моделирования, где То — максимальное количество шагов;

Vi,j (t) — значение i-ro концепта j-ro варианта в t-й момент времени процесса моделирования.

Рассмотрим некоторые особенности решения оптимизационных задач на КМ.

• 1.    Концепты КМ необходимо переименовать так, чтобы для всех них решалась оптимизационная задача либо на максимум, либо на минимум.

• 2.    Значения всех концептов должны быть нормированы — приведены к единой относительной шкале (в интервале значений от —1 до +1) для обеспечения их сопоставимости.

• 3.    Эффективность для каждого i-ro целевого концепта j-ro варианта рассчитывается либо как накопленная сумма, либо как среднее арифметическое значений по шагам периода моделирования, например:

• 4.    При решении классической оптимизационной задачи производится линейная свертка полученных значений целевых концептов; их нормированные веса С’ отражают значимость каждого концепта. Тогда обобщенный критерий эффективности каждого j-ro варианта есть

• 5.    Возникает проблема эффективного хранения значений обобщенного критерия эффективности для различных многочисленных вариантов. Предлагается сохранять не все полученные значения критерия эффективности и не единственное наилучшее текущее значение, a m наилучших значений (т задается), упорядоченных по убыванию заданного критерия эффективности: Vi, V2,..., Vm Каждое новое рас считанное решение V * сравнивается с Vm если V* < Vm (для задачи на максимум), то решение V* не сохраняется; иначе самое плохое в списке решение V_m отбрасывается, а решение V* вставляется на нужное по порядку место.

3.    Генетические алгоритмы

То

^V’,j = ^ ^Vi,j ^(t).

t=1

п

Vj = Е с^ .                          (1)

’=1

Для решения оптимизационных задач общего вида на когнитивных моделях было предложено использовать генетические алгоритмы [6, 7]. Генетические алгоритмы были выбраны, поскольку они позволяют решать сложные неполиномиальные многоэкстремальные задачи, а также достаточно универсальны и просты в реализации.

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

Генетический алгоритм представляет собой программную модель эволюции популяции искусственных «особей», которая имитирует процессы развития популяции. Обычно он применяется для решения задач оптимизации класса NP, задач поиска и управления. Этот метод оптимизации является стохастическим, эвристическим и позволяет находить субоптимальное (приближенное) решение за достаточно короткое время.

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

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

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

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

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

• —    хромосома (особь) — числовой вектор или цепочка символов, соответствующий некоторому решению задачи;

• —    ген — элемент хромосомы (нуль/единица, число, символ, вектор);

• —    аллель — позиция гена в хромосоме;

• —    эпоха — один этап функционирования генетического алгоритма.

4.    Кодирование информации о задаче

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

• —    в классическом целочисленном кодировании хромосома представляет собой битовую строку, в которой целочисленное значение каждого параметра кодируется последовательностью битов;

• —    при использовании вещественного кодирования значением каждого гена является вещественное число, а хромосома представляет собой вектор вещественных чисел.

ГА вещественного кодирования (RCGA — Real-Coded Genetic Algorithm) [8, 9] работают, в общем случае, с непрерывной областью допустимых значений переменных и имеют ряд преимуществ. Они обладают наглядностью, простотой реализации, позволяют сократить размер хромосом и уменьшить объем вычислений за счёт отсутствия двоично-десятичных преобразований при расчёте значений функций приспособленности. Генетические алгоритмы вещественного кодирования (ГАВК) существенно отличаются от алгоритмов целочис- ленного и бинарного кодирования набором генетических операторов, т.е. для ГАВК были разработаны собственник операторы скрещивания и мутации.

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

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

Пусть гены хромосомы соответствуют различным управляющим концептам (УК), тогда длина хромосомы равна N — числу всех УК.

Необходимо одновременно отразить:

• 1 . Различные комбинации непосредственно используемых при решении оптимизационной задачи УК (далее по тексту активные УК) как подмножества множества всех УК. Обычно для отображения подмножеств в ГА используются бытовые строки, в которых единица кодирует вхождение элемента в подмножество.

• 2 . Значения параметров каждого используемого УК, т.е. значения моментов времени подачи Т * и силу внешних управляющих воздействий L*.

Очевидно, что необходимые способы представления информации для п.1 и п.2 несовместимы друг с другом.

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

• —    значением гена является 0, если данный УК не используется в данном варианте решения;

• —    значением гена является вектор из двух чисел Т* и L*, если данный УК является активным.

В силу определённой сложности ГА векторного кодирования было предложено использовать ГАВК для нестандартного вида хромосом вещественного кодирования, где:

• —    значением гена (как и для ГА векторного кодирования) является 0, если соответствующий УК не является активным (на него не подается управляющий импульс);

• —    значением гена является целое число (как частный случай вещественного числа), кодирующее значения Т * и L*, если данный УК является активным.

Кодирование информации производится в зависимости от заданных значений Т и L (табл. 1). Например, при Т = 10 потребуется 4 бита для хранения значений моментов времени подачи управляющих импульсов (от 1 до 10), а при L = 4—2 бита для хранения значений силы импульса. Кодировка возможна следующая: 00 — сильный отрицательный импульс, 01 — слабый отрицательный импульс, 10 — слабый положительный импульс, 11 — сильный положительный импульс.

Таблица 1

Пример кодирования данных в хромосоме

Концепт	1	2	3	4	5	6	7	8
Значение	0	19	0	0	22	0	17	0

В данном примере N = 8, k = 3, а управляющие импульсы подаются на УК с номерами 2, 5 и 7.

При этом на 2-й концепт в момент времени 4 (двоичное число 100) подается сильный положительный импульс (двоичный код 11). Получаем

0100 * 11 ^ 10011 ^ 19.

5.    Специфика этапов генетического алгоритма

Генетические алгоритмы включают следующую последовательность основных этапов [6, 7]:

• 1.    Формирование начальной популяции.

• 2.    Расчет функций приспособленности для всех особей популяции.

• 3.    Отбор родителей для скрещивания.

• 4.    Скрещивание отобранных родителей.

• 5.    Мутации особей.

• 6.    Проверка допустимости полученных хромосом.

• 7.    Обновление популяции.

• 8.    Проверка на завершение работы.

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

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

• —    параметры решения задачи по возможности равномерно распределены по соответствующим областям допустимых значений;

• —    количество генов с ненулевыми значениями не должно превышать значения к, а сами эти значения должны соответствовать правилам кодирования; например, биты, кодирующие значение Т *, не могут все быть нулевыми;

• —    расстояние по Хэммингу между любой парой хромосом не равно нулю;

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

Размер популяции п задается в качестве сравнительно небольшого числа (в интервале 30-60 особей) и остается постоянным для всех поколений.

Функция приспособленности. Для каждой особи начальной популяции рассчитывается так называемая функция приспособленности (fitness function); значение этой функции определяет, насколько хорошо особь подходит для решения задачи. Функция приспособленности (ФП) должна принимать неотрицательные значения, причем непрерывность и дифференцируемость не требуются. В задачах максимизации в качестве ФП обычно выступает неотрицательная целевая функция.

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

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

Существует большое количество методов отбора родителей — пропорциональный отбор, турнирный отбор, ранговый отбор, панмиксия (случайный выбор родителей), элитный отбор и т.д. Для рассматриваемой задачи был использован популярный пропорциональный (пропорционально-вероятностный) отбор. Для каждой j-й особи рассчитывается значение pt, равное отношению ее приспособленности fi к суммарной приспособленности популяции (суммирование идет по всем п членам популяции):

Pi =

fi

Ъ f ’

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

Кроссовер. Четвертым этапом работы ГА является кроссовер (кроссинговер) или скрещивание отобранных особей. Результатом кроссовера является появление новых особей-потомков в количестве двух штук, которые являются модификацией родительских особей. Кроссовер обеспечивает получение разнообразия в процессе эволюции и передачу признаков от родителей к потомкам. Кроссовер применяется к отобранным особям не всегда, а с некоторой вероятностью Р_с — скоростью кроссовера, которая является одним из основных параметров любого ГА и обычно находится в диапазоне от 60% до 100%. При решении рассматриваемой задачи значение Р_с задается в пределах указанного диапазона.

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

Для задачи оптимизации на КМ ситуация осложняется тем, что у потомков по сравнению с родителями изменения должны производиться в двух направлениях:

• —    изменение набора активных УК;

• —    изменение параметров активных УК.

В связи с этим кроссовер предлагается осуществлять следующим образом, используя четыре метода кроссовера:

• —    для изменения набора активных УК с вероятностью 50% применяется простой или частично согласованный кроссовер;

• —    для изменения параметров активных УК с вероятностью 50% применяется арифметический или плоский кроссовер.

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

• 2.    Частично согласованный кроссовер (ГМХ). При применении ГМХ в родительских хромосомах случайным образом выбираются два места пересечения, а потом подстроки в родительских хромосомах между двумя местами пересечения меняются местами с получением двух новых дочерних особей.

• 3.    Арифметический кроссовер обеспечивает получение двух новых особей Н = (h1,h₂, ■ ■ ■ ,hN ) и G = (д1,д₂, ■ ■ ■ ,gN ) из родительских особей Р = (p1,p₂, ■ ■ ■ ,P n ) и Q = ( Q i ,Q 2 , ■ ■ ■, Q n ) путём вычисления значений генов по соотношениям

• 4.    Плоский кроссовер обеспечивает формирование новых особей из генов для активных УК, значения которых представляют собой случайно сгенерированные вещественные числа из интервала, границы которого определяются минимальным и максимальным значениями соответствующих генов родительских хромосом. То есть создаются потомки:

hi = api + (1 - a)qi,     gi = aqi + (1 - a)pi, где константа a G [0; 1] задается. Нетрудно видеть, что значения генов потомков лежат между значениями генов родителей.

Н = (h1, h2, ■ ■ ■ , hN), где                                                           ____ hi G [min(pi,qi), max(pt,qi)] Vi = 1,7V.

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

Как и для операторов кроссовера, мутации предлагается производить в двух направлениях:

• —    для мутаций в наборе активных УК используются операторы инверсии;

• —    для мутаций параметров активных УК используются собственно операторы мутации.

Таким образом:

• —    с заданной вероятностью Pi выполняются операторы инверсии — каждый из двух операторов инверсии выбирается случайным образом с 50% вероятностью;

• —    с заданной вероятностью Р_т выполняются операторы мутации — каждый из двух операторов мутации выбирается случайным образом с 50% вероятностью.

В отличие от оператора скрещивания, вероятности инверсии Pi и мутации Р_т выбираются достаточно малыми и являются фиксированными случайными числами в диапазоне (0, d]. г,те d задается nd ^ 1 (папример. d = 0,1).

• 1.    Инверсия. В хромосоме случайным образом выбираются две позиции (2 гена) ni и П2, после чего гены хромосомы от позиции ni и до позиции П2 включительно переставляются в обратном порядке.

• 2.    Фрагментарная инверсия является аналогом операции транслокации для ГА целочисленного кодирования. Она заключается во взаимной перестановке двух фрагментов родительской хромосомы, взятых в случайных позициях. Для этого случайным образом выбираются две позиции в хромосоме ni ип2, а также длина переставляемых фрагментов d. Очевидно, что должны выполняться соотношения ni + d — 1 < V и n₂ + d — 1 <  N, где N — длина хромосомы.

• 3.    Равномерная мутация. Она состоит в том, что в хромосоме выбирается случайный ген, значение которого заменяется на равномерно распределенное случайное число из интервала возможных значений гена. Так, для примера и. 4 эти значения могут меняться в интервале от 4 до 43.

• 4.    Мутация для вещественных хромосом. Его особенность состоит в том, что величина шага мутации (величина изменения гена при мутировании) изменяется в течение всего процесса работы ГА. Мутирующие гены определяются случайным образом и мутируют в соответствии со следующим правилом:

• х₂ = х1 ±а х ф

где Х2 — новое значение гена;

• х1 — старое значение гена;

• знаки + ил и — выбираются с равной вероятностью;

• а = 0.5:

• 5 = ^т=1 ^a(i) * 2^-id ^a(i) = 1 ^с вероятностью т, _в противном случае a(i) = 0;

т — параметр.

Для каждой новой особи-мутанта вычисляется ее функция приспособленности.

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

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

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

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

• —    для каждой пары полученных новых особей вычисляются ФП этих особей;

• —    из каждой четверки особей (двое родителей и двое потомков) выбирается две особи с наилучшими значениями ФП;

• —    если в эту пару входят дочерние особи (одна или две), то они пополняют состав популяции;

• —    если в эту пару не входят родительские особи (одна или две), то они удаляются из популяции.

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

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

• —    превышено ограничение на максимальное число эпох работы ГА;

• —    значения качества всех особей превысили заданный порог;

• —    ГА сходится, т.е. хромосомы всех особей популяции почти одинаковы и кроссовер их практически не изменяет; схождение популяции обычно означает, что найдено лучшее или близкое к нему решение.

6. Программная реализация

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

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

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

Перечислим основные параметры, которые задаются пользователем при решении задач когнитивного моделирования и оптимизации с использованием генетических алгоритмов:

• —    размер хромосомы TV:

• —    максимальное число генов для активных УК в хромосоме к',

• —    время, в течение которого могут быть поданы управляющие импульсы Т',

• —    количество уровней мощности импульсов L'

• —    размер популяции п;

• —    длительность процесса эволюции (количество эпох) Е'

• —    вероятность кроссовера Р_с;

• —    вероятность инверсии Рр,

• —    вероятность мутации Р_т.

Перечислим опции меню приложения (режимы работы):

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

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

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

• —    Загрузить. Сформированный граф когнитивной модели (а также приближенное оптимальное решение задачи, если оно уже найдено) загружаются из файла, граф модели визуализируется в рабочем окне.

• —    Оптимизация. С экрана вводятся значения параметров генетического алгоритма, после чего при нажатии кнопки «Старт» производится решение оптимизационной задачи; номер текущей эпохи выводится на экран.

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

Заключение

Приведем основные результаты настоящей работы:

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

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

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

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

• —    предложен способ кодирования информации о параметрах вариантов решения задачи в хромосомах генетического алгоритма;

• —    различные этапы генетического алгоритма конкретизированы с учетом специфики решаемой оптимизационной задачи;

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

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

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