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

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

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

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

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

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

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

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

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

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

_ x1_____ x2_____ x3____ _ x4____

Рис. 1 — Пример хромосомы для четырех параметров

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

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

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

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

Лабораторная работа № 20 (1)

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

Лабораторная работа № 20 Лабораторная работа № 20 (2)

где Лабораторная работа № 20 =2- Лабораторная работа № 20 и 1 Лабораторная работа № 20

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

Лабораторная работа № 20 (3)

где Лабораторная работа № 20 — некоторое фиксированное число первых членов популяции.

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

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

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

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

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

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

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

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

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

-заданы габариты (размеры) элементов размещения;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Лабораторная работа № 1 -\


Похожие статьи.

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