Лабораторная работа № 20

«Применение генетического метода для решения задачки размещения элементов»

Цель работы:целью работы является исследование принципов построения

генетических алгоритмов, получение способностей работы с

реализующим их программным пакетом на примере

решения прикладной задачки конструирования.

Генетические методы (ГА) - это адаптивные способы поиска, построенные с внедрением принципов теории био эволюции Ч. Дарвина. По аналогии с эволюционным механизмом, ГА работают Лабораторная работа № 20 с популяцией, в какой любая из входящих в нес хромосом представляет собой вероятное решение данной задачки. Любая хромосома оценивается мерой её приспособленности (fill ness function), которую именуют также функцией пригодности. Более адаптированные особи получают возможность «воспроизвести» потомство при помощи перекрестного скрещивания (crossingover) с другими особями (индивидуумами Лабораторная работа № 20) популяции. В итоге возникают новые особи, сочетающие внутри себя свойства, наследуемые от родителей.

Менее адаптированные особи равномерно исчезают из популяции в процессе естественного отбора («выживает более приспособленный»). Новое поколение обладает наилучшими чертами по сопоставлению с предшествующим. Скрещивание более адаптированных особей приводит к тому, что эволюция ищет многообещающие решения в пространстве Лабораторная работа № 20 поиска. В итоге, популяция сходится к хорошему либо практически хорошему решению задачки.

Популяция решений может состоять как из одной, так и из большего количества хромосом. Обычно, хромосома - это битовая строчка (набор генов), хотя ГА могут использовать не только лишь бинарное представление решения. Био термин «генотип» соответствует структуре хромосомы Лабораторная работа № 20 в ГА. Термин «фенотип» относится к низшим наблюдаемым признакам и соответствует вектору в пространстве характеристик задачки.

Пример хромосомы, кодирующей четыре параметра (х1, х2, х3, х4) представлен на рисунке 1.

_ x1_____ x2_____ x3____ _ x4____

Рис. 1 - Пример хромосомы для 4 характеристик

В качестве функции пригодности в ГА может употребляться мотивированная функция оптимизации. Стандартный ГА генерирует исходную Лабораторная работа № 20 популяцию структур случайным образом и повторяется до того времени, пока не выполнится данное число поколений либо некий аспект останова.

В процессе выполнения ГА осуществляется последовательное выполнение последующих генетических операций:

1) отбор (селекция). В общем случае, отбор делается на базе вероятностей Pi(si), вычисленных для каждого из индивидуумов .s', популяции, i Лабораторная работа № 20 = 1,2, ..., М). Более нередко используются последующие схемы отбора:

-пропорциональный отбор:

(1)

-линейное ранжирование:

(2)

где =2- и 1

-равномерное ранжирование:

(3)

где - некое фиксированное число первых членов популяции.

Одним из методов преодоления этого недочета является внедрение элитного отбора, при котором всегда сохраняется лучшая хромосома популяции;

2) кроссовер (кроссинговер). Одноточечный кроссовер (скрещивание) представляет собой оператор рекомбинации и Лабораторная работа № 20 применяется по отношению к паре хромосом из популяции S(t), прошедших отбор. Назначается возможность выполнения кроссовера Ркр. Дальше, для случаем избранной пары хромосом определяется случайное число k {1, 2, ..., n - 1}, называемое местом (либо позицией) кроссовера, и потом биты из 2-ух избранных хромосом изменяются местами после k-го бита с вероятностью Ркр Лабораторная работа № 20 (см. рис. 2). Этот процесс повторяется для других избранных хромосом до того времени, пока популяция S(t) не окажется пустой. Обычно, Ркр [0,6; 0,99].

В общем случае, ГА с рекомбинацией (m,k) употребляет оператор кроссовера по схеме m:k (m родителей, k потомков).

Есть также схемы двухточечного, трехточечного и т.д. кроссовера Лабораторная работа № 20. Предельным случаем является равномерный кроссовер, когда любая пара бит снутри хромосом-родителей обмениваются битами в согласовании с определенной вероятностью;

3) мутация. Оператор мутации, как и кроссовер, заносит дополнительное обилие в популяцию, накладывая стохастический шум на процесс эволюции и стимулируя тем исследование разных частей места поиска, что понижает в Лабораторная работа № 20 итоге риск «застревания» процесса поиска в локальных оптимумах.

Обычно мутация представляет собой случайное изменение бита, ве­роятность которого достаточно низкая (Рмут [0,001; 0,01]) (см. рис. 3).


Рис. 3 - Операция мутации

Постановка задачки размещения разногабаритных частей в пространстве обычно формулируется последующим образом:

-заданы ограничения на объем размещения (к примеру - габариты определенного корпуса);

-заданы габариты (размеры Лабораторная работа № 20) частей размещения;

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

Начальными данными задачки являются: а, b - габариты монтажного поля; {(а1, Ь Лабораторная работа № 201), ...,(аi, 6i),…, (аn, 6n)} - огромное количество габаритов частей размещения; С - матрица связей частей, представляющая собой матрицу связности. Нужно отыскать таковой вариант размещения частей на монтажном поле: Z= {(x1, y1), …,(xi,yi), …,(xn,yn)},где (xi,yi) - координаты центра масс установочной площади i-го элемента размещения, при котором площадь Лабораторная работа № 20 перекрытия размещения частей была бы равна нулю.

Решение задачки размещения сводится к решению задачки оптимизации мотивированной функции, представляющей собой сумму штрафа за перекрытие площадей размещаемых частей.

Размножение (Скрещивание)

Размножение в различных методах определяется по-разному — оно, естественно, находится в зависимости от представления данных. Главное требование к размножению — чтоб потомок либо потомки Лабораторная работа № 20 имели возможность унаследовать черты обоих родителей, «смешав» их любым методом.

Контрольные вопросы:

1. Дайте определение генетического метода.

Генетические методы (ГА) - это адаптивные способы поиска, построенные с внедрением принципов теории био эволюции Ч. Дарвина. По аналогии с эволюционным механизмом, ГА работают с популяцией, в какой любая из входящих в Лабораторная работа № 20 нес хромосом представляет собой вероятное решение данной задачки.

2. Что понимается под стандартным генетическим методом?

Копирование естественных процессов, происходящих в мире живых организмов, а именно, эволюции, связанной с ней селекции (естественного отбора) популяции живых созданий.

3. В чем отличие стандартного генетического метода от стандартных алгоритмов оптимизации?

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

4.Какие главные характеристики употребляются в стандартном генетическом методе?

5.Каковы отличия стандартного генетического метода от метода с рекомбинацией? 

Кроссовер (кроссинговер). Одноточечный кроссовер (скрещивание) представляет собой оператор рекомбинации и применяется Лабораторная работа № 20 по отношению к паре хромосом из популяции S(t), прошедших отбор.

Вывод: в процессе лабораторной работы были исследованы принципы построения генетических алгоритмов, получены способности работы с реализующим их программным пакетом на примере решения прикладной задачки конструирования. Генети́ческий алгори́тм (англ. genetic algorithm) — это эвристический метод поиска, применяемый для Лабораторная работа № 20 решения задач оптимизации и моделирования оковём случайного подбора, комбинирования и варианты разыскиваемых характеристик с внедрением устройств, подобных естественному отбору в природе.


laboratornaya-rabota-kak-forma-uchebnogo-proektirovaniya.html
laboratornaya-rabota-laboratornie-raboti-po-kulinarii.html
laboratornaya-rabota-mnogokvartirnij-zhiloj-dom-s-nezhilimi-pomesheniyami.html