Разработка и исследование метода компараторной идентификации модели многофункционального оценивания
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
?ледний подход в большей степени соответствует задаче формализации процессов интеллектуальной деятельности вообще и оценивания, в частности, в зависимости от имеющейся исходной информации.
Независимо от принятого подхода, идентификация заключается в итерационной процедуре выдвижения гипотезы о структуре РM, количественной оценке ее параметров АM и проверке адекватности синтезированной модели результатам эксперимента.
1.4 Описание генетического алгоритма
На практике подчас сложно, а порой и невозможно, зафиксировать свойства функциональной зависимости выходных параметров от входных величин, еще сложнее привести аналитическое описание такой зависимости. Это обстоятельство значительно затрудняет применение классических методов оптимизации, поскольку большинство из них основывается на использовании априорной информации о характере поведения целевой функции, а задача определения принадлежности функции тому или другому классу сопоставима по сложности с исходной. В связи с этим встает задача построения таких методов оптимизации, которые были бы способны отыскивать решения практически при полном отсутствии предположений о характере исследуемой функции. Одними из таких методов являются так называемые эволюционные методы поиска и, в частности, генетические алгоритмы (ГА), моделирующие процессы природной эволюции.
Генетические алгоритмы являются одними из эволюционных алгоритмов, применяемых для поиска глобального экстремума функции многих переменных. Принцип работы генетических алгоритмов основан на моделировании некоторых механизмов популяционной генетики: манипулирование хромосомным набором при формировании генотипа новой биологической особи путем наследования участков хромосомных наборов родителей (кроссинговер), случайное изменения генотипа, известное в природе как мутация. Другим важным механизмом, заимствованным у природы, является процедура естественного отбора, направленная на улучшение от поколения к поколению приспособленности членов популяции путем большей способности к "выживанию" особей, обладающих определенными признаками.
Реализацию базового генетического алгоритма можно представить как итерационный процесс, включающий несколько этапов:
) генерация начальной популяции;
) воспроизводство "потомков":
а) выбор родительской пары;
б) выбор и реализация одного из операторов кроссовера;
в) выбор и реализация одного из операторов мутации;
) создание репродукционной группы;
) процедура отбора и формирование на его основе нового поколения;
) если не выполнено условие останова, то перейти к п. 2).
Операторы кроссовера и мутации
Одной из особенностей рассматриваемого ГА является отход от традиционной схемы "размножения", используемой в большинстве реализованных ГА [5] и повторяющих классическую схему. Классическая схема предполагает ограничение численности потомков путем использования так называемой вероятности кроссовера. Такая модель придает величине, соответствующей численности потомков недетерминированный характер. Предполагается вместо вероятности кроссовера использовать фиксированное число брачных пар на каждом поколении, при этом каждая брачная пара порождает двух потомков. Такой подход хорош тем, что делает процесс поиска более управляемым и предсказуемым в смысле вычислительных затрат [4].
В качестве генетических операторов получения новых генотипов "потомков", используя генетическую информацию хромосомных наборов родителей применяются два типа кроссоверов - одно- и двухточечный. Вычислительные эксперименты показали, что даже для простых функций нельзя говорить о преимуществе того или иного оператора [7, 8], поэтому в дальнейшем рассматривается более простой одиночный оператор.
Далее необходимо реализовать размножение внутри исходной популяции. Для этого случайно отбираются несколько пар особей, производится скрещивание между хромосомами в каждой паре, а полученные новые хромосомы помещаются в популяцию нового поколения. В генетическом алгоритме сохраняется основной принцип естественного отбора - чем приспособленнее особь (чем больше соответствующее ей значение целевой функции), тем с большей вероятностью она будет участвовать в скрещивании. Затем производятся мутации - в нескольких случайно выбранных особях нового поколения изменяются некоторые гены.
Старая популяция частично или полностью уничтожается и далее рассматривается следующее поколение особей. Популяция следующего поколения в большинстве реализаций ГА содержит столько же особей, сколько начальная, но, вследствие отбора, приспособленность в ней в среднем выше.
Описанные выше процессы отбора, скрещивания и мутации повторяются уже для новой популяции и т.д.
В каждом следующем поколении наблюдается появление совершенно новых решений задачи. Среди них имеются как плохие, так и хорошие, но благодаря отбору количество хороших решений будет возрастать.
При этом возникает вопрос о том, каким образом из всего многообразия возможных пар выбрать лишь несколько. Это проблема отбора перспективных и неперспективных решений. Как уже отмечалось, метод отказывается от использования вероятности кроссовера в качестве одного из параметров алгоритма, ограничивая число воспроизводимых потомков фиксированным числом брачных пар. Рассмотрим несколько наиболее интересных подходов к решению этой задачи.