Диссертация (792664), страница 13

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

Текст из файла (страница 13)

На Рисунке 4.9 приведенаклассификация алгоритмов кроссинговера [154] [155] [156].Классификация алгоритмовкроссинговераПо количеству потомковПо работе с аллелямиВведение новых аллелейиз множества допустимыхДва потомкаОдин потомокИспользованиепотомком толькоаллелей родителейВычисление аллелейпотомка на основеаллелей родителейСпособ организацииработы с данными аллелиРабота с аллельюкак со скаляромВозможность работыс аллелью как соскаляром и как свекторомОдноточечныйАрифметическийОдноточечныйАрифметическийОдноточечныйАрифметическийДвухточечныйЭвристическийДвухточечныйЭвристическийДвухточечныйЭвристическийРассеянныйРассеянныйПромежуточныйРассеянныйПромежуточныйПромежуточныйРисунок 4.6 – Классификация алгоритмов кроссинговераПри одноточечном и двухточечном кроссинговерах появляется два потомка.При одноточечном кроссинговере случайным образом определяется локус, левеекоторого, включая указанный локус, хромосома одного потомка является копиейхромосомы одного родителя, а правее – другого.

У второго потомка наоборот:108левее выбранного локуса, включая его самого, хромосома является копиейхромосомы второго родителя, а правее – первого (Рисунок 4.7).РодителиТочка кроссинговераПотомкиРисунок 4.7 – Одноточечный кроссинговерПри двухточечном кроссинговере случайным образом определяютсязначения двух локусов. У первого потомка между выбранными локусами,включая их самих, хромосома является копией хромосомы первого родителя, авне – второго. У второго потомка наоборот: между выбранными локусами,включая их самих, хромосома является копией хромосомы второго родителя, аправее – первого (Рисунок 4.8).РодителиТочки кроссинговераПотомкиРисунок 4.8 – Двухточечный кроссинговерПри арифметическом кроссинговере аллель гена потомка определяется каксреднее арифметическое аллелей генов родителей, имеющих тот же локус, сучетом ограничений на область допустимых значений.При эвристическом кроссинговере хромосома потомка является концомвектора, полученного путем умножения исходного вектора на константу,большую единицы.

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

Сумма весов аллейродителя равна единице, веса определяются пользователем алгоритма.При рассеянном (равномерном) кроссинговере аллель гена потомка равнааллели гена одного из родителей, имеющего тот же локус. Выбор родителяосуществляется случайным образом (Рисунок 4.9).РодителиПотомкиРисунок 4.9 – Равномерный кроссинговерКомпоненты кортежа = (, ), описывающего кандидата, имеют разнуюприроду: время ∶ и место ∶ .

При таких способах кроссинговера, какарифметический, эвристический и промежуточный, это необходимо учесть. Естьдва варианта реализации этих типов кроссинговера.При первом способе кроссинговер применяется непосредственно к номерамкандидата в множестве кандидатов, упорядоченном в лексикографическомпорядке. Значение аллели изменяется в пределах от 1 до .Для арифметического и промежуточного кроссинговеров выражения, всоответствии с которыми выполняется вычисление, имеют вид: = ∗ 1 + (1 − )2где 1, 2– значения аллелей родителей, причем(1) ≤ (2);(4.10)110 – значение фитнес функции; – результат вычисления значения аллели потомка без учета ограничения надиапазон изменения;- весовой коэффициент:   1 при арифметиче ском   h  1 при промежуточ номℎ – максимальное значение весового коэффициента, заданное пользователем.Для эвристического кроссинговера выражения, в соответствии с которымивыполняется вычисление, имеют вид: = 2 + (1 − 2)>1(4.11)Ограничение на диапазон изменения значения аллели потомка childреализуется следующим образом:, если 1 ≤ ≤ ℎ = { 1, если 1 > , если > (4.12)При втором (векторном) способе действия применяются отдельно ккаждому компоненту кортежа, а затем по полученным значениям определяетсяномер кандидата в упорядоченном множестве кандидатов, который определяетзначение аллели:ct, если time min  ct  time maxtime   time min , если time min  ct time , если ct  timemaxmax(4.13)111cp, если placemin  cp  placemaxplace   placemin , если placemin  cp place , если cp  placemaxmaxК компоненте время : применяется непосредственно используемый типкроссинговера (арифметический, эвристический и промежуточный).К компоненте место : применяется рассеянный (равномерный) типкроссинговера.При первом скалярном способе кроссинговер применяется к номерамкандидатов, как изображено на Рисунке 4.10 и Рисунке 4.11.scorescore2score1α1-αparent2сhildparent1candidateРисунок 4.10 – Арифметический и промежуточный кроссинговеры в скалярномвиде112ScoreScore2Score1α-11candidatminparent2candidateсhild candidatmaxparent1Рисунок 4.11 – Эвристический кроссинговер в скалярном видеПри втором векторном способе действия применяются к каждомукомпоненту отдельно, и по полученным результатам определяют номеркандидата, который определяет значение аллели, как изображено на Рисунке 4.12и Рисунке 4.13.placeplace1parent1сhildplaceCplace2parent2αtime11-αtimeCtime2timeРисунок 4.12 – Арифметический и промежуточный кроссинговеры ввекторном виде113placeplacemaxplaceCсhildparent1place1place2placeminparent2α-1timemin timeC1time1time2timemaxtimeРисунок 4.13 – Эвристический кроссинговер в векторном виде4.2.4МутацияМутации происходят в процессе эволюции в соответствии с определяемойпользователем вероятностью мутации [157].

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

В связи с ограниченным размером популяции, меньшимверхней границы, определенной в п. 4.2.2, вероятность того, что на какой-либо изитераций будет получен такой набор хромосом, из которого путем рекомбинацийне может быть получена любая возможная хромосома, отлична от нуля. Это такжеобуславливает необходимость мутаций [158] [105].114Найдем необходимую для восстановления утерянного разнообразиявероятность мутации одной хромосомы . Мутация хромосомы происходит,если подвергся мутации один из генов, т.е.:p mс  N с p m1(4.14)где 1 – вероятность мутации одного гена.В этом случае вероятность мутации определенного гена хромосомы равна1 =с.

Вероятность того, что данный ген хромосомы не мутирует, равна1 − 1 = 1 −с. Вероятность того, что данный ген не мутирует ни в одной изс хромосом, равна (1 − 1 ) = (1 −данныйлокусмутирует1 − (1 − 1 ) = 1 − (1 −хотябыс ) . Соответственно, вероятность того, что) .вДляоднойнадежностиизхромосом,равнанеобходимо,чтобывероятность мутации данного локуса хотя бы в одной из хромосом на порядокпревышала вероятность отсутствия в данном локусе во всех хромосомах какоголибо из значений. Тем более, что сам факт мутации еще не означает, чтопроизошла мутация, повышающая полноту использования набора аллелей. Такимобразом, необходимо:1  1  p m1   10 1  p N aN1  1  p m1 101  1  p m1 10NN 1  p Na 1   p Na1  1  p m1  1  p Na10N (4.15)115p Nap1  1  mсNс110NЕсли популяция большая, то мутации теряют смыслp1  1  mсNсNcN N  АN a   101 N  АN aa  N 1 (4.16)Отсюдаp mс1NNc N   АN a     N c 1  1  101  N  p  N c 1  1  10 1  p N  АN aa N 1     , mс    (4.17)1NaВ зависимости от типа генов выделяют следующие типы мутации: в случае, если гены, образующие хромосомы, представляют собойпоследовательность двоичныхразрядов,возможна«битовая мутация»–инвертирование группы случайно выбранных бит в гене (в предельных случаяхединственного или всех); для любых видов генов: замена значений генов на их максимально или минимальнодопустимоезначение,выборосуществляетсяслучайнымобразом;замена значения выбранного гена на значение случайнойвеличины,распределеннойпозаданному(равномерному,усеченному нормальному или др.) закону распределения вдиапазоне допустимых для заданного гена значений; перестановка двух случайно выбранных групп генов местами.1164.2.5Условия окончания работы генетического алгоритмаВ блоке 8 укрупненной схемы ГА, решающего задачу построения прототипаГО, (Рисунок 4.5) проверяется условие окончания работы алгоритма.

Характеристики

Список файлов диссертации