Главная Обратная связь

Дисциплины:

Архитектура (936)
Биология (6393)
География (744)
История (25)
Компьютеры (1497)
Кулинария (2184)
Культура (3938)
Литература (5778)
Математика (5918)
Медицина (9278)
Механика (2776)
Образование (13883)
Политика (26404)
Правоведение (321)
Психология (56518)
Религия (1833)
Социология (23400)
Спорт (2350)
Строительство (17942)
Технология (5741)
Транспорт (14634)
Физика (1043)
Философия (440)
Финансы (17336)
Химия (4931)
Экология (6055)
Экономика (9200)
Электроника (7621)






Схема эволюционных вычислений



Формирование исходного поколения; While пока не выполнится условие останова {Определение перспективности членов популяции; For k от 1 до n {Формирование нововй хромосомы; Оценка целевой функции; Селекция;} Смена поколения;}

Вычисления начинаются с формирования множества информационных объектов =( , ,… ), =1,2,… , которые в соответствии с принятой в GA терминологией называют хромосомами (другие возможные названия – агенты, фреймы, кортежи). Хромосома состоит из генов , значения генов называют аллелями, а позиции генов в хромосоме - локусами. Обычно в задачах оптимизации гены отождествляют с управляемыми параметрами. Множество называют популяцией, а состав популяции в конкретный момент вычислений – поколением.

Эволюция представляет собой многошаговый процесс. На каждом шаге формируются новые хромосомы и N хромосом отбирается (селектируется) в новое поколение. Формирование хромосом нового поколения происходит с использованием генного материала текущего поколения и с учетом качества этого материала. Качество j-й хромосомы оценивается значением целевой функции F(Xj ), а качество каждого поколения – наилучшим (минимальным) значением Yopt целевой функции, полученным на данный момент вычислений.

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

Основная идея ГА заключается в эволюции популяции. Цель эволюции в ГА - получение экземпляров с наилучшими значениями определенных критериев, характеризующих качество экземпляра, т.е. синтезируемой структуры

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

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

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



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

34. Модель процесса упорядочения. Методы решения задач теории расписаний:лин пр-ния, дискретного пр-ния, методы ветвей и границ, сетевого планирования

Линейное программирование — математическая дисциплина, посвящённая теории и методам решения экстремальных задач на множествах -мерного векторного пространства, задаваемых системами линейных уравнений и неравенств.

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

Математическая формулировка

Нужно определить максимум линейной целевой функции (линейной формы)

при условиях

Иногда на Xi также накладывается некоторый набор ограничений в виде равенств, но от них можно избавиться, последовательно выражая одну переменную через другие и подставляя её во всех остальных равенствах и неравенствах (а также в функции f).

Такую задачу называют «основной» или «стандартной» в линейном программировании.

Примеры задач: Максимальное паросочетание Максимальный поток Транспортная задача Игра с нулевой суммой

Наиболее известным и широко применяемым на практике для решения общей задачи линейного программирования (ЛП) является симплекс-метод.


Эта страница нарушает авторские права

allrefrs.ru - 2019 год. Все права принадлежат их авторам!