русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Шима (Schema)


Дата добавления: 2013-12-23; просмотров: 352; Нарушение авторских прав


26.11.2011

Работа простого генетического алгоритма

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

Скрещивание бывает одноточечное, двухточечное и равномерное (основано на вероятностях).

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

Schema – строка длины l, состоящая из 0 или 1 и неопределенных символов.

Пример:

 

Каждая шима имеет 2 свойства – порядок и определенная длина.

· Порядок – число определенных битов;

· Определенная длина – расстояние между крайними определенными битами;

 

Строящие блоки – шимы, обладающие следующими свойствами:

· Высокая приспособленность;

· Низкий порядок;

· Короткая определенная длина;

 

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

Теорема шим



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

- число примеров шимы в поколении .

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

- вероятность того, что шима переживет скрещивание (2).

- вероятность того, что шима переживет мутацию.

- данная форма верна при малом .

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

Вероятность того, что шимаHпереживет мутацию равна (2).

Тогда ожидаемое число примером шимыH в поколении будет равно:

 

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

Теорема шим описывает следующие аспекты поведения генетического алгоритма:

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

2) Когда происходит отбор, популяция сходится пропорционально отношению приспособленности лучшей особи к средней приспособленности популяции. Это отношение называется мерой давления отбора;

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

4) Уменьшение вероятности скрещивания или вероятности мутации, или увеличение давления отбора ведет к улучшению использования найденныхшим, но тормозит исследование пространства поиска новых хороших шим;

5) Генетический алгоритм должен поддерживать равновесие между тем и другим, что известно как проблема баланса исследования и использования;


 



<== предыдущая лекция | следующая лекция ==>
Символьная модель простого генетического алгоритма | Программные реализации аналитических технологий


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Полезен материал? Поделись:

Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.003 сек.