Программная система автоматического формирования нечеткого логического контроллера
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
?ий.
Равновероятная селекция. Самая простая, но менее эффективная модель селекции. При данном виде селекции вероятности выбора индивидов в качестве родителя равны, вне зависимости от пригодности индивида.
Преимуществами данного вида селекции является:
нет преждевременной сходимости,
нет стагнации,
индивиды популяции охватывают большую площадь поискового пространства.
Недостаток: низкая эффективность поиска.
Пропорциональная селекция. Пропорциональная селекция является наиболее распространенной и используемой в ГА. Вероятность отбора индивида для скрещивания при данной селекции пропорциональна его пригодности и определяется следующим образом:
pi = ,
где fi - пригодность i - го индивида, - средняя пригодность популяции и N - объем популяции.
Однако данная модель селекции обладает двумя отрицательными чертами:
преждевременная сходимость - если на ранних поколениях был получен индивид с fi >>, но fi << fmax , то гены такого индивида быстро распространятся на всю популяцию и рекомбинация не сможет более производить новых индивидов, т.е. fi << fmax навсегда;
стагнация - ближе к концу работы алгоритма все индивиды получают относительно высокую и примерно равную пригодность, т.е. , поэтому наилучшее решение будет предпочитаться лишь немного больше, чем наихудшее. Это приводит к очень маленькому селективному давлению.
Ранговая (линейная) селекция. Первоначально происходит упорядочивание индивидов по их пригодности (по возрастанию), т.е. fi fj для i > j. Затем каждому индивиду, в зависимости от его места в упорядоченном ряду, назначается вероятность pi быть отобранным. Для линейной ранговой селекции используется следующее распределение вероятностей: pi = ai + b (a <0), причем Si pi = 1. Здесь, i - номер индивида в ранжированном ряде, a и b - параметры линейной ранговой селекции.
Основные преимущества данной модели селекции:
нет преждевременной сходимости,
нет стагнации,
нет необходимости в явном вычислении пригодностей индивидов, поскольку для их упорядочивания достаточно лишь иметь возможность их попарного сравнения.
Недостатками ранговой селекции являются значительные накладные расходы на переупорядочивание индивидов и трудность теоретического анализа сходимости.
Турнирная селекция. Одна из самых эффективных схем селекции, используемая для решения большинства задач оптимизации. Для отбора индивида в качестве родителя из текущей популяции случайным образом набирается группа в M индивидов (M - размер турнира и 2 M). Затем из данной группы выбирается индивид с наибольшей пригодностью, а остальные индивиды возвращаются в популяцию.
Преимущества турнирной селекции:
нет преждевременной сходимости,
нет стагнации,
не требуется глобальное переупорядочивание,
не требуется явное вычисление функции пригодности.
Элитарная селекция. Набирается группа из M наилучших индивидов из всей популяции (M - размер элиты и 2 M). Затем отобранная элита переносится в новую популяцию, а оставшиеся (N - M) индивидов новой популяции получаются при скрещивании индивидов элитарной группы между собой. Индивиды, не вошедшие в элиту, игнорируются и не участвуют ни в каких операциях.
Преимуществом элитарной селекции является то, что есть гарантия сходимости ГА к глобальному экстремуму, если таковой будет обнаружен в ходе оптимизации.
Недостатки данной селекции является большой риск захвата локальным минимумом.
Рекомбинация. В ГА за передачу признаков родителей потомкам отвечает оператор рекомбинации, который также называют скрещиванием, кроссовером. Наиболее распространенными являются одноточечная, двухточечная и равномерная рекомбинации.
Одноточечная рекомбинация представляет собой разбиение родительских хромосом в одной точке, выбранной случайным образом, и обмен правыми частями хромосом. Схематически одноточечная рекомбинация отображена на рис. 2.3.1.
Рис. 2.3.1 Пример одноточечной рекомбинации
При двухточечной рекомбинации разбиение родительских хромосом происходит уже в двух точках. После разбиение для получения потомков родители обмениваются центральными частями хромосом.
Равномерная рекомбинация предполагает, что каждый ген потомка выбирается случайным образом из соответствующих генов родителей.
Мутация. Оператор мутации предназначен для поддержания разнообразия особей в популяции и является методом восстановления потерянной генетической информации. Он состоит из выполнения небольших изменений в значениях одного или нескольких генов в хромосоме. В двоичных хромосомах мутация состоит в инвертировании случайным образом выбранного бита генотипа, например, 101000101 100000101.
Хорошим эмпирическим правилом iитается выбор вероятности мутации из соотношения pm = , где H - число бит в хромосоме. На основе этого правила можно произвести классификацию мутации по трем типам:
-слабая (pm < ),
-средняя (pm =),
-сильная (pm > ).
Схема работы генетического алгоритма:
- Инициализация популяции случайными значениями;
- Оценивание популяции;
- Повторять, пока не выполнится условие останова:
Селекция. Отбор по определенной методике части популяции для воспроизводства;
Рекомбинация. Формирование индивидов новой популяции путем обмена частей хромосом отобранных родителей;
Мутация. Изме
Copyright © 2008-2014 geum.ru рубрикатор по предметам рубрикатор по типам работ пользовательское соглашение