2010 Лекции МОТП. Записки (2010 Лекции МОТП. Записки.pdf), страница 8

Сама процедура поиска основана на аналогии и моделированиипроцессов селекции в природе, когда происходит выживание и появлениеобъектов с более высокими показателями, за счет отбора, скрещивания имутации объектов. Ниже в круглых скобках приводятся наименованиятерминов, принятые в генетике.Имеется множество объектовцели~O = {O} , на котором задана функцияf :O ⇒ R.Определяетсяпредставлений) иконечноемножествофункция кодирования~Σ = {Σ}(пространствоe:O ⇒ Σ.Элементыпространства представлений называются представлениями (генотипами,хромосомами).

Функция, обратная к функции кодирования, называетсяфункциейдекодированияиобозначаетсякакe −1 : Σ ⇒ O .Декодирование может быть неоднозначным и одному представлению можетсоответствовать множество объектов, имеющих одно и то же представление.Если для некоторого представления не существует элементаe −1 (Σ) ,данное представление считается недопустимым.45Считаетсязаданнойтакжефункцияµ :Σ⇒ R .(приспособленность)µ (Σ) = f (e −1 (Σ)) .НабороценкипредставленийОбычно{O, Σ, µ}полагаютназываетсяособью.Совокупность особей называется популяцией.Основная задача состоит в нахожденииS * = arg maxµ (Σ) .~Σ∈ΣТаким образом, предварительным этапом решения основной задачи являетсясоздание символьной модели, элементами которой являются:- пространство решений~O = {O} ;- пространство представлений~Σ = {Σ} ;- функции кодирования и декодирования;- функция цели;- функция оценки представлений.Опишем общую схему генетического алгоритма.Пустьзаданасимвольнаямодельзадачи,гдепространствопредставлений есть дискретный единичный куб размерностипредставления являются строками длиныN,аN.Генетический алгоритм начинается со случайной генерациисовокупности особей – популяции.

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

Считаем, что число особей четное. Популяцияслучайно разбивается на m/2 пар особей (родителей).1.Оператор кроссовер.46Выбирается некоторая пара особей и к ней с вероятностьюприменяется следующий оператор. ПустьΣ 2 = (σ 21 , σ 22 ,..., σ 2 N )pcΣ1 = (σ 11 , σ 12 ,...,σ 1N )и- коды родителей.Случайно выбирается натуральное l< N и создаются два новых кода(определяющие новые особи - потомки) :Σ1∗ = (σ 11 ,σ 12 ,...,σ 1l ,σ 2,l +1 ,σ 2,l + 2 ,..., σ 2 N ) ,Σ∗2 = (σ 21 ,σ 22 ,...,σ 2l ,σ 1,l +1 ,σ 1,l + 2 ,...,σ 1N ) .Пример.Родители110110|0000110101010|1110000Потомки110110|1110000101010|0000110Данный способ «разрыва и склеивания» называется одноточечнымкроссовером.

Имеются и другие подходы. Например, в двухточечномкроссовере происходит между родителями «обмен» некоторыхцентральных фрагментов, имеющих одинаковые номера генов.Полученные потомки включаются в имеющуюся популяцию.2.Оператор мутации.Во всех генотипах популяции с вероятностьюpmосуществляетсязамена значений всех генов на противоположные (1 на 0, 0 на 1).3.Оператор отбора.Пусть в результате применения операторов кроссовера и мутацииполучено m потомков, а общее число особей данного поколениясоставило 2m.

Следующее поколение из m особей формируется врезультате случайного выбора m особей из имеющихся 2m особей,причем вероятность попадания в новую популяцию некоторогоимеющегося множестваΣ1 , Σ 2 ,..., Σ 2 mΣiиз2mравнаµ ( Σ i ) / ∑ µ (Σ j ) .j =16.2. Генетический алгоритм поиска логических закономерностей.47Построим символьную модель генетического алгоритма поискалогическихзакономерностейнекоторогообозначим эталоны данного класса какПусть~S = {Si1 , Si2 ,..., Sik }S1 , S 2 ,..., S NДля.Kλ.P(c1 , c 2 , x) = & Pj (c1j , c 2j , x j ) ,c1j = min~ {x j ( Si )} , c 2j = max~ { x j ( Si )} .Si ∈Sпростоты,- подмножество эталонов классаПоставим ему в соответствие предикатгдеKλ.класса(15)Si ∈SЕсли некоторый предикат (1) является логической закономерностью, тосуществует эквивалентный ему предикат (т.е.

условия 1-3 предикатовполностьюсовпадают),длякоторогоконстантыc1j , c 2j , j = 1,2,..., nопределяются согласно (15). Следовательно, пространство решений можноограничитьмножествомвсевозможнымипредикатовподмножествами(1),~Sскоторыеопределяютсявычислениемконстантc1j , c 2j , j = 1,2,..., n , согласно (15).Пространство представлений определим как множество бинарныхвекторовΣi = (σ i1 , σ i 2 ,...,σ iN ) ,гдеN –число эталонов классаKλ,а~1, S j ∈ S ,σ ij = ~0, S j ∉ S .Функции кодирования и декодирования описаны выше. Очевидно,имеется взаимнооднозначное соответствие между пространством решений ипространством представлений.48Функцией цели для нас является стандартный функционал качествапредикатов.Функция оценки представлений определяется следующим образом.Пусть представлениеΣi = (σ i1 , σ i 2 ,...,σ iN )~S = {Si1 , Si2 ,..., Sik } ,которомусоответствует подмножествусоответствуеттакжепредикатPi (c1 , c 2 , x) .Положим ϕ ( Pi (c1 , c 2 , S j )),Pi (c1 , c 2 , S j ) = 0, ∀S j ∉ K λ ,µ (Σ i ) = 12иначе.ϕ ( Pi (c , c , S j ) /(1 + ψ ),Здесь ψ= {S j ∉ K λ , Pi (c1 , c 2 , S j ) = 1} .Генетический алгоритм строится согласно общей схеме сдвухточечным кроссовером.Строится начальная популяция хромосом, «покрывающих» всеэталоны рассматриваемого класса.

Размер популяции m может бытьразличным в зависимости от типа решаемой задачи. В данной задачепринималось m =N/2. Начальный вид хромосом также может бытьразличным. Выбирается фиксированный номер хромосомы, которая будетявляться «лидером» популяции. Лидер популяции – это хромосома, имеющаянаибольшее значение целевой функции. Лидер популяции не можетподвергаться никаким изменениям и операциям, кроме замены на хромосомус большим значением целевой функции.При решении данной задачи оптимальное значение вероятности мутациинаходится в пределах pm ∈  ;  , где N- длина хромосомы.N N 1 3Экспериментальные вычисления на таблицах обучения различныхзадач распознавания показали, что при длине хромосомы L порядканескольких сотен алгоритм работает надежно и находит оптимальныйпредикат за 50-100 итераций.ЛЕКЦИЯ № 1149РанеебылизакономерностейрассмотреныклассаалгоритмыпоискаKλ ,т.е.P Ω (c1 , c 2 , x) = & Pj (c1j , c 2j , x j ) ,j∈Ωудовлетворяющихлогическихпредикатовспециальнымограничениям, причем по построению Ω = {1,2,..., n} .

Рассмотрим вопроспоиска логических закономерностей с минимальными по мощностимножествами Ω .Рассмотримследующуюзадачуцелочисленноголинейногопрограммирования.n∑yj =1jn∑βj =1ij→ min ,y j ≥ 1, для всех Si ∉ K λ ,(1)y j ∈{0,1}.12Здесь β ij = 1 − Pj (c j , c j , aij ) . Множество всех единичных компонентрешения ( y1 , y2 ,..., yn ) определяет соответствующее подмножество признаковΩ . Действительно, полученный предикатP Ω (c1 , c 2 , x) = & Pj (c1j , c 2j , x j )j∈Ωудовлетворяет условиям 1, 3 определения логической закономерности, авыполнение линейных ограничений в (1) соответствует выполнению второгоусловия основного определения. Множество всех единиц построенногопредиката является аналогом максимального интервала для булевскогослучая.6.

Обобщение знаний по выборкам прецедентовВ настоящем разделе будет рассмотрена задача обобщения знаний(множества логических закономерностей), под которой понимаетсянахождение и вычисление обобщенных характеристик признаков и классовна основе ранее полученных множеств логических закономерностей классов.KλПусть для классавычислено множество логическихΩзакономерностей Pt ( x), t ∈ T .Определение. Логическим описанием класса K λ назовем логическуюPt Ω ( x) .сумму Dλ ( x) = t∨∈TЯсно, что Dλ ( St ) = 1 для всех обучающих объектов из класса K λ (еслиобучающая выборка не противоречива), и Dλ ( St ) = 0 для всех эталонныхобъектов, не принадлежащих классу K λ . Таким образом, Dλ (x) совпадает намножестве описаний эталонных объектов с характеристической функциейкласса K λ .tt50Очевидно, Dλ (x) является прямым аналогом сокращенных ДНФ длябулевых функций.

Тогда естественно рассмотреть и аналоги минимальных икратчайших ДНФ.Определение. Минимальным логическим описанием класса K λΩmназовем логическую сумму Dλ ( x) = t∈T∨'⊆T Pt ( x) , в которойt∑Ωt∈T 't→ min , афункция Dλm (x) совпадает с Dλ (x) на обучающей выборке.По аналогии с булевым случаем величину Ωt можно назвать рангомсоответствующего предиката.Определение. Кратчайшим логическим описанием класса K λ назовемΩsлогическую сумму Dλ ( x) = t∈T∨''⊆T Pt ( x) , в которой T ' ' → min , а функция Dλs (x)совпадает с Dλ (x) на обучающей выборке.tРис.3. Покрытие эталонных объектов класса «белый кружок»множеством его логических закономерностей.51Рис.4.

Кратчайшее покрытие эталонных объектов класса «белыйкружок» множеством его логических закономерностейЛогические (кратчайшие, минимальные) описания классов являютсяаналогами представлений частичных булевых функций в виде сокращенныхдизъюнктивных нормальных форм (кратчайших, минимальных), агеометрические образы логических закономерностей классов - аналогамимаксимальных интервалов [6,7].Задачи поиска минимальных и кратчайших логических описанийформулируются как задачи на покрытия:∑a yt∈Tt∑Pt∈TtΩtt→ ⋅ min,(10)( S t ) yt ≥ 1,⋅ ⋅ ⋅ ∀S t ∈ K λ ,⋅ yt ∈{0,1}.(11)Тогда при at =1 единичные компоненты решения задачи (10-11)определяют кратчайшее логическое описание Dλs (x) класса K λ , а при at = Ωt ,- минимальное логическое описание.ΩОтметим, что исходные множества Pt ( x), t ∈ T могут содержать равныеили близкие элементы, «вырожденные» решения, соответствующиелокальным максимумам с малыми абсолютными значениями, мощностьданных множеств может быть весьма велика (что однако являетсяблагоприятным в процедурах распознавания).