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

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

Утверждение 2.15 Пусть О - булев тор, тогда в О существует гамильтонов цикл.

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

Прир = 0,р~ \ ир~ \ справедливость утверждения очевидна. Пусть утверждение доказано при всех р < т, покажем его справедливость при р - т. Рассмотрим два случая. Если в представлении (1) булева тора С I отлично от нуля, тогда существует булев тор С, степени вершин которого равны т - 1, такой, что О = С х К2. По предположению индукции, С гамильтонов. Из определения операции прямого произведения следует, что О содержит два подграфа изоморфных С. В каждом таком подграфе, по предположению индукции, есть гамильтонов цикл. Удалим из этих циклов по одному соответствующему ребру и соединим инцидентные им вершины в этих двух подграфах. Таким образом, мы нашли в С гамильтонов цикл.

Если в представлении (1) булева тора О I равно нулю. Очевидно, существуют булев тор С и цикл такой, что С = С х . Из определения операции прямого произведения следует, что С содержит | ц, | подграфов изо-

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

Библиографический список

1. Никонов, В.Г. Пороговые представления булевых функций / В.Г. Никонов // Обзоры прикладной и промышленной математики. - 1994. - № 3. -С. 402-458.

2. Никонов, В.Г. Покрытия булевых графов / В.Г. Никонов // Дискретная математика. - 1994. - № 4. -С. 21-34.

3. Горбатов, В.А. Теория графов и мографов / В.А. Горбатов И Фундаментальные основы дискретной математики. - М.: Наука, Физматлит, 2000. -С. 157-257.

4. Ope, О. Теория графов / О. Ope. - M.: Наука, 1980.

5. Зыков, A.A. Основы теории графов / A.A. Зыков. -М.: Наука, Физматлит, 1987.

6. Берж, К. Теория графов и ее применение / К. Берж. -М.: Изд-во иностр. литерах, 1962.

7. Зайцева, Ж.Н. Исследование графов, вложимых в «-куб и их применение в проектировании / Ж.Н. Зайцева, В.Г. Никонов, Д.С. Шевелев // РЭА. Методы искусственного интеллекта в САПР тезисы докладов. - Воронеж, 1990. - С. 49-52.

8. Никонов, В.Г. Булевы графы и функции / В.Г. Никонов, Д.С. Шевелев // Дискретная математика. - 1991,-№4.-С. 52-61.

ПРОБЛЕМА ВЫБОРА НАЧАЛЬНОЙ ПОПУЛЯЦИИ ГЕНЕТИЧЕСКОГО АЛГОРИТМА, ПРИМЕНЯЕМОГО ДЛЯ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ НЕРАВЕНСТВ С БУЛЕВЫМИ НЕИЗВЕСТНЫМИ

П.Н. СИТНИКОВ, науч. сотр. лаборатории ТВП, Москва

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

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

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

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

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

- осуществляют поиск из популяции точек, а не из единственной точки;

- используют целевую функцию, а не ее различные приращения для оценки информации;

- используют не детерминированные, а вероятностные правила.

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

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

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

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

Перечислим основные составляющие элементы традиционного ГА [2].

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

Далее в работе для того, чтобы наглядно продемонстрировать влияние на работу ГА параметров начальной популяции - ее размера и структуры, будем полагать, что в формировании популяции Х,+1 из Х; участвуют только операторы скрещивания и репродукции.

Оператор репродукции Я создает из исходной популяции X, новую X', присутствие в которой той или иной хромосомы определяется мерой ее приспособленности, т.е. значением ЦФ. Данный оператор направлен на сохранение хромосом с лучшими значе-

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

Отбор особей в популяцию X' осуществляется на основании вероятностей Р] (х;'0' вычисленных для каждого вектора множества X, в рамках выбранного механизма репродукции. Существует несколько вариантов данного оператора (например, пропорциональная, турнирная репродукции с упорядочиванием), отличающихся правилами отбора решений для новой популяции, т.е. правилами назначения вероятностей выбора особей в новое множество векторов.

С помощью оператора скрещивания происходит наследование генетической информации и производится поиск более приспособленных решений. При применении данного оператора из множества X' создается новая популяция X,", в которой каждый индивидуум будет нести в себе частично информацию некоторых двух решений из предыдущей популяции, т.е. будет являться «ребенком» некоторых двух «родителей». В то же время часть особей может переходить в новую популяцию без изменений. Вариантов данного оператора несколько (одноточечное, г-точечное, равномерное скрещивание). В общем виде механизм скрещивания представляется следующим образом. Задается вероятность рс, которая показывает долю особей популяции X', участвующих в скрещивании, определяется правило набора пар "родителей" (х^, х^ и в соответствии с выбранным механизмом скрещивания 5 : У„ х V —» У„ х У получают потом-

" - и у„', = х„, , либо У, - "

' т, _ш,/ У1,

7Г5Г1"

' т.1

т,]

И

=

для всех у = 1, п. Отметим, что если

на некоторой итерации в популяции X, вы-

(0 (0 (<) полняется х,^ = х\', =... = Хд/, = а, то есть у-е

координаты всех векторов одинаковые, то и

после применения операторов репродукции и

скрещивания у всех векторов в популяции X,"

у'-я координата будет равняться а. Тогда в ходе

поиска невозможно будет получить вектора с

координатой х= а.

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

Примером оператора мутации М: О —> служит инвертирование битов с заданной вероятностью рт, т.е.

и

Р(М (*« ) = х«])=1-рт,х = \,М1] = и.

Таким образом, переход от популяции X,, к Х/+1в традиционном ГА осуществляется путем последовательного применения выбранных механизмов репродукции Я, скрещивания 5 и мутации М.

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

Рассмотрим систему линейных псевдобулевых неравенств вида

+ Чп^А

а + ... + а х V Ъ

. ш 11 тп п т т ?

где

а., 6. е Ъ, х. е {0,1}, V ,е {<, >, <, >}. (1) Под невязкой /-го неравенства для вектора х = (хр..., хп) будем понимать следующую величину

п п

£ - Ьиесли £ а^х^ - Ц > 0, иУ,- е {< <}

М И

6г- - ^Г а^Хрвспи ^ а^х^-Ь^ < 0,мУг- е {>,>

Н Н

О- в - противном - случае

Невязка системы неравенств для вектора х равна сумме невязки всех неравенств

£(*) = £ и,, (х).

i=i

Нетрудно видеть, что если вектор х0 является решением системы (1) ,то £(х0) = 0. Как показали экспериментальные исследования, возможны различные способы задания ЦФ для решения системы линейных неравенств (например, выбор в качестве ЦФ числа невыполнившихся неравенств, значение максимальной невязки неравенства системы и т.д.), однако использование невязки системы в качестве ЦФ оказалось предпочтительнее; данный подход изложен в [3, 4].

Перечислим основные этапы ГА, предназначенного для решения системы (1).

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

2. Вычисление целевой функции для всех особей (в качестве ЦФ в данном случае выступает невязка), если решение присутствует, выход из алгоритма с указанием решения, иначе - шаг 3).

3. Скрещивание каждого с каждым (причем можно использовать как одноточечное скрещивание, так и скрещивание с несколькими точками разрыва).

4. Вычисление целевой функции для всех особей, если решение присутствует, выход из алгоритма с указанием решения, иначе - шаг 5).

5. При помощи оператора пропорциональной репродукции на основании значений ЦФ особей формируется новая популяция, мощность которой совпадает с мощностью начальной популяции.

6. Если число итераций алгоритма больше фиксированной константы, то выход, иначе - шаг 3).

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

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

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

Рассмотрим начальную популяцию X, сформированную из двоичных векторов длины п, | Х\ =Л'. Не ограничивая общности, будем полагать, что к векторам из X применяется оператор одноточечного скрещивания [1]. Пусть для скрещивания выбраны векторы х.,х, еХ, г,]е{1,..,М},

т - точка скрещивания, тогда результат действия оператора

Skrl(xi, х) = •

= Гх

•

Заметим, что d(xp х.) = d(xt, у.) + d(yif х) =

= d

где d(a, b) - расстояние Хемминга между векторами а = (ej,..., ап)и b = (bv bn) е Vn, которое определяется как число таких i е {1,.., п}, что <х ф Ь. и является метрикой на F.

Утверждение 1 Пусть для всех векторов популяции X выполняется неравенство d{x., х) < р0, р0ф0, тогда вектор, полученный в результате применения операции скрещивания к любым двум векторам из X, удален от каждого из них на расстояние, меньшее или равное р0.

Доказательство Из (3) (4): для любых х , х. е Xdix., х). = d(Xp у^ + d(y.., х), т.к. по условию d(x., хр < р0, то d(x., ytj) + d(y.., х) < р0. Поскольку по определению d{xt, у.р > 0, d(ytj, х.) > 0, то утверждение доказано.

Следствие 1 Путем однократного применения оператора скрещивания нельзя получить потомка, удаленного от одного из элементов начальной популяции на расстояние, большее р0.

Геометрический аспект утверждения 1 исключительно важен для понимания логики ГА. Если базовая популяция окажется локализованной в некотором булевом гипершаре

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

Определение 1 Базовую популяцию из т векторов длины п назовем координатно вырожденной, если существует у е 1 ,п, такое что х, = х2. = ...= =х = 8.

mJ

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

М-

л

21'

2п

Хт\' •">Хт

V У

Утверждение 2

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

"-»ЛцрСОД-»!-

Доказательство

Полагаем, что начальная популяция формируется случайно равновероятно. Пусть А - случайное событие, заключающееся в том, что в матрице М содержится хотя бы один нулевой или единичный столбец (условие координатного вырождения), элементарное событие А- в у'-м столбце либо все нули, либо единицы; Р(А) - вероятность того, что произошло случайное событие А. Для доказательства исходного утверждения необходимо показать, что при фиксированном т, при п -» оо Р(А) —> 1. Действительно,

Р(А) = Р(А1иА2и..иА„) = \-Р(А) = 1-

Р(А,) = Р(Еи=0,Е21=0,.....,ЕпЛ =0 ) + Р(Еи

= 1Е21=\,.....,Ет1 = 1)=Д

\т

то Р(А) = 1

= 1-(1—

4 о"'-1

т.к. п е Ы,то (1 -

1

т-\

О <1 =

при п оо (!__)"

а следовательно, Р(А) —> 1. Утверждение доказано.

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

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

Приведем ряд определений и утверждений теории кодирования, в которых содержатся оценки кодового расстояния для линейных кодов [5-7]. Этими оценками предлагается руководствоваться при построении начальных популяций ГА из элементов кодов с максимальным кодовым расстоянием.

Определение 2 Кодом длины п в конечном алфавите  называется произвольное подмножество К с: О.", при этом элементы К, называются кодовыми словами.

Определение 3 Кодовым расстоянием, или расстоянием Хемминга кода К называют параметр с1(К) = = тт{с1(а, Ь)\ а, ЬеК, а* Ь},ъ терминах имитационных алгоритмов данное выражение назовем минимальным расстоянием популяции.

Определение 4 Код К длины п в алфавите О, имеющий мощность С и расстояние с1, назовем (и, С, ¿/)п-кодом.

Определение 5 В том случае, если мощность кода ха-

-Р(АХ и^2и..и^л)-1 Р(А 1 и А2 и..иАп), растеризуется параметром к = log¡п11К|, то

поскольку элементарные события А незави- говорят, что К- [п, к, ¿/]п-код, или [п, к, ¿1] -код,

симы и

Определение 6

Линейным [п, А^-кодом над полем Р называется подпространство К < Р" размерности к.

Расстояние Хемминга d(K) кода К характеризует возможность кода К замечать и исправлять ошибки. Если d(K) > г, то говорят, что код К замечает г ошибок. Если d{K) > 2г, то говорят, что К исправляет г ошибок. Определение 7 Весом Хемминга слова ае К < Р" называется число | \а\ | = d(a, 0) ненулевых координат в слове а.

Утверждение 3 Для любого линейного кода К <Р" справедливо равенство d(K) = min{||a|| : аеЮ0} Теорема 1 (граница Синглтона). Если К есть [п, к, </]п-код, то

d<n-k+l.

Определение 8 Код £ называется кодом с максимально достижимым расстоянием, или МДР-кодом, если неравенство (5) обращается в равенство, т.е. если К есть [п, к, п-к + 1]-код

Теорема 2 (граница Хемминга) Если К есть [п, &]-код в алфавите Q мощности q и d(K) > 2г, то

qk < q" Isq

где

sq(n,r) =\+(q-l)n +

+ (q-\y

/V м

о + ... + (q-l)r

К2) J У

Определение 9

Правая часть неравенства (6) называется границей Хемминга, или границей сферической упаковки для мощности кода. Код К называется совершенным, если для него неравенство (6) обращается в равенство (в этом случае d(K) = 2г+ 1).

Теорема 3 (граница Плоткина) Для произвольного [п, к]-кода К в алфавите О, мощности q, справедлива оценка

d<

nq

п.

дК-1 д \K\-\ Замечание. Для того чтобы код достигал границы (8), необходимо, чтобы его ми-

нимальное расстояние равнялось среднему расстоянию

1

d = -

I d(a,b).

М(М-1)а%К

Последнее равносильно тому, что расстояние между любыми различными кодовыми словами одинаково. Такие коды называются эквидистантными, и в качестве примера можно рассмотреть симплексный код. Пусть Р - ОР(ц) - поле из ц элементов, V - пространство размерности к над Р с нулем 0 и VIО = {у,,...^}, п — цК — 1. Обозначим через V* множество линейных отображений g :У—> Р (сопряженное пространство к V) и поставим в соответствие каждому отображению g е V* строку

g = (g(vl),,g(vJ)eP".

Тогда множество = V*}

есть линейный систематический эквидистантный

[п,к, —-(п + 1)]-код, Ч

достигающий границы Плоткина. Теорема 4

Обозначим через Ач(п,ф максимальное значение С, для которого существует (п, С > d)¡¡ код в алфавите О мощности |Г2| Тогда

4-1 Г „\

i=0

Чг/

(Я-1)'

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

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

Библиографический список

1. Батшцев, Д.И. Генетические алгоритмы решения экстремальных задач / Д.И. Батшцев. - Воронеж, 1995.

2. Кисляков, A.B. Генетические алгоритмы: операторы скрещивания и мутации / A.B. Кисляков // Информационные технологии. - 2001.- № 1. -С. 29-34.

3. Кисляков, A.B. Самообучающийся генетический алгоритм решения систем булевых уравнений / A.B. Кисляков, В.Г. Никонов // Научный вестник МГТУ ГА. Серия «Информатика». - 2001. - № 38. -С. 28-33.

4. Кисляков, A.B. О применении генетических алгоритмов для решения систем линейных неравенств

/ А.В. Кисляков, В.Г. Никонов // Труды школы-семинара "Новые информационные технологии в науке, образовании, телекоммуникации и бизнесе": по материалам докладов XXVII международной конференции IT+SE'2000 "New Information technology in Science, Education, Telecommunications and Business". Информационные технологии в науке, образовании, телекоммуникации и бизнесе. - Запорожье, 2000. - С. 40.

5. Питерсон У. Уэлдон. Коды, исправляющие ошибки / У. Питерсон, Уэлдон. - М., 1976.

6. Бородин, Л.Ф. Введение в теорию помехоустойчивого кодирования / Л.Ф. Бородин. - М., 1968.

7. Кассами, Т. Теория кодирования / Т. Кассами, Н. Токура, Е. Ивадари и др. - М., 1978.

МЕТОДЫ И МОДЕЛИ СОЗДАНИЯ И ОЦЕНКИ КАЧЕСТВА ОБРАЗОВАТЕЛЬНЫХ ИНФОРМАЦИОННЫХ РЕСУРСОВ

В.Г. ДОМРАЧЕВ, проф., зав. каф. электроники и микропроцессорной техники МГУЛ, д-р техн. наук,

О.М. ПОЛЕЩУК, проф. каф. высшей математики МГУЛ, д-р техн. наук,

Н.Г. ПОЯРКОВ, ст. преподаватель каф. информационно-измерительных систем МГУЛ

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

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

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

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

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