Формирование тестовых заданий

Состав тестовых заданий формируется в соответствии с генетическим алгоритмом. В этом случае процесс формирования задания рассматривается как последовательная смена популяций. Переход от популяции Х0 к Х: и затем последовательно от X к X производится путем поэтапного применения выбранных механизмов репродукции и сравнения качества вновь создаваемых популяций с критериями оптимальности:

selection crossing mutation              survival              ‘ИеТ0

X, нgt; х; н» х; н* х,т н* Х,ч1 н* У.

generation i*i*1 J '¦'«'¦'л

где selection, crossing, mutation и survival - соответственно операторы отбора, скрещивания, мутации и выживания.

Создание новой популяции в начале эволюционного периода подразумевает формирование множества из N векторов:

х* = {Л/^л1, Nlt;i2—Nq. ,...Nqrn},

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

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

Zri е 1, Nqz - sVgrjt /=1

Nq,^ =Zrj, 1 lt;Ztlt; NqnMXi, Nqr_,,Z,r,i- целое, Z = rnd(X);

где zr, - случайная величина, удовлетворяющая заданным условиям; Nqr, - количество вопросов в i-й теме;              - максималь

ное количество вопросов в i-й теме.

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

Р,=Р^-11Р.г ¦ = 1, = 1

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

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

N

±F,-F,

к:=^—-gt;              lt;zlt;

1F,

1=1

где Кр - коэффициент, учитывающий вероятность участия особи в скрещивании; GL, G* ~ границы интервалов, соответствующих наступлению вероятности включения особи в пару:

, = LKt gt; G,              ft = 1,2,...,n-1.

1=1              1=1

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

Скрещивание выполняют таким образом, чтобы особи обменивались генами на участках от первого гена до гена с координатой t{ и от гена с координатой t2 до конечного гена, а гены на участке от до f2 оставались бы неизменными:

I

n              1 с2              2              •              . -I .              1

*,./ = х,.г хы = х..,’ при i = t\+              2+!;

*4 =              *1              =              *',gt; ПРИ i =              12~п-

В случае если в результате скрещивания образовалась нежизнеспособная особь (особь, для которой не выполняются ус-

П

ловия Nqt lt; Nqmнх и Х^9г., - Nlt;!'_)gt; то возможен один из двух вариантов работы оператора скрещивания.

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

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

N4i-lNqr., =0;

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

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

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

Вероятность применения оператора мутации проверяется из условия

Рти, gt; Z,

гдePmut - вероятность мутации, Рти1 = 0,001...0,01; Z - случайная

величина.

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

41, gt;

xT.i = xi.r ПРИ j * fv h-

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

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

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