Алгоритм генетический

Важнейшим частным случаем ЭМ являются генетические методы и алгоритмы. Генетические алгоритмы основаны на поиске лучших решений с помощью наследования и усиления полезных свойств множества объектов определенного приложения в процессе имитации их эволюции. [c.185]

Методы структурного синтеза для многих практически важных приложений, включая концептуальное проектирование и логистику, могут быть созданы на базе генетических алгоритмов, к которым поэтому в настоящее время проявляется заметный интерес. [c.204]

Важным и обширным множеством приложений, в которых для синтеза целесообразно применять генетические алгоритмы, является планирование производства и распределение ресурсов, включая задачи проектирования технологических процессов производства изделий. Возникающие здесь задачи можно трактовать как задачи синтеза расписаний. Другими примерами приложений генетических методов синтеза могут служить компоновка и размещение оборудования, диспетчирование потоков работ, распределение частот в радиоканалах сетей мобильной связи, проектирование подвески автомобиля и др. [c.205]

Генетические алгоритмы и методы отжига. Генетические алгоритмы относятся к наиболее универсальным подходам к решению сложных задач структурного синтеза и подробно обсуждаются далее. Методы отжига можно рассматривать как реализацию идеи повышения вероятности определения глобального экстремума в других статистических методах оптимизации, таких, как генетические или локальные методы поиска, [c.208]

Базовый генетический алгоритм [c.211]

Таким образом, цель генетического поиска - найти экземпляр хромосомы, имеющий значение функции полезности, максимально близкое к ее экстремальному значению. Направленный поиск малой окрестности экстремума осуществляется в генетическом алгоритме с помощью генетических операторов выбора родителей, кроссовера, мутации, селекции, переупорядочения, поясняемых далее. [c.212]

Генетические алгоритмы имитируют эволюционный процесс приближения к оптимальному результату, начиная с некоторого исходного поколения структур, представленных экземплярами хромосом. Этот процесс в базовом генетическом алгоритме является вложенным циклическим вычислительным процессом. Внешний цикл имитирует смену поколений. Во внутреннем цикле формируются члены очередного поколения. [c.212]

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

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

Селекция - это отбор членов нового поколения среди потомков, полученных в результате кроссовера и мутаций в данном поколении. В базовом генетическом алгоритме в новое поколение включается лучший из двух потомков, порожденных после кроссовера. Внутренний цикл заканчивается, когда окажется сформированным новое поколение, т.е. в нем будет N членов. [c.214]

Генетические алгоритмы выражают эволюцию популяции в направлении от полезности начального поколения к окрестностям экстремума. Обоснование этого положения содержится в основной теореме генетического подхода - теореме шаблонов. В этой теореме вводится понятие схемы (шаблона), которая определяется как совокупность фиксированных значений генов в определенных локусах. Например, в хромосоме с 10 генами одна из схем Н, включающая единицы в четвертом и восьмом локусах и нуль в седьмом локусе, может быть записана в виде [c.214]

Возможны разные способы выбора объекта мутации. В соответствии с одним из способов обращение к процедуре мутации происходит с некоторой постоянной вероятностью, как в базовом генетическом алгоритме. В соответствии с другим способом ради снижения опасности стагнации вероятность мутации увеличивают, когда две выбранные родительские хромосомы различаются значениями не более чем к генов, обычно /г = 0... 2. [c.216]

Обычно возможность появления недопустимых хромосом связана с наличием зависимостей между генами. Тогда независимый случайный выбор значений генов, как это происходит при кроссовере и мутациях в базовом генетическом алгоритме, становится некорректным. [c.218]

НСМ свободен от необходимости корректировки дочерних хромосом. В нем аллелями служат не значения проектных параметров, а имена эвристик, используемых для определения этих значений. Выполнение условий допустимости переносится в сами эвристики, что делает собственно генетический алгоритм инвариантным к различным задачам. Простой сменой набора эвристик легко осуществляется адаптация имеющихся программ синтеза к особенностям конкретного класса задач. [c.222]

Другими словами, в случае НСМ г-й ген соответствует г-й подзадаче, а 1-й аллель есть номер (имя) процедуры (эвристики), реализующей локальную целевую функцию и ограничения г-й подзадачи. Согласно НСМ для каждой подзадачи должно быть сформулировано несколько альтернативных постановок (процедур), именно среди них генетический алгоритм или алгоритм локального поиска будет выбирать члены последовательности, приближаясь к оптимальной последовательности эвристик. [c.222]

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

Задачам синтеза расписаний (ЗСР) посвящено большое число работ, в том числе и по генетическим алгоритмам синтеза. ЗСР заключается в распределении заданного множества работ во времени и между исполнителями (в пространстве). [c.224]

Генетические методы могут быть свободными от привязки к определенному правилу. Например, если гены хромосомы соответствуют работам, а значение гена отражает приоритет работы в ее назначении на обслуживание, то порядок назначения работ может стать близким к оптимальному в той степени, в какой это допускают генетические принципы. Однако выбор сервера в этом варианте алгоритма приходится все-таки осуществлять по некоторому фиксированному правилу. [c.226]

Если прогнозируется получение решения с нарушением ограничений, приводящим к незначительным штрафам, то отбор эвристик в задачах синтеза расписаний следует проводить, ориентируясь на значения 2 (табл. 2.2). В противном случае нужно усиливать роль эвристик с временной ориентацией. В задаче N25 прогноз благоприятен, и в набор были включены эвристики Э , и Э . При этом целесообразно для более перспективных эвристик увеличивать вероятности их выбора в операторах мутаций и генерации начального поколения. В экспериментах в случае задачи N25 вероятности выбора эвристик Э,, Э , и взяты в отношениях 2 1 1 4. При этом средний по нескольким вариантам результат применения простого генетического алгоритма оказался Е = 5371. вто время как равновероятное использование всех восьми эвристик дало F = 5536. [c.233]

Простой генетический алгоритм 543 578 593 598 663 595 [c.235]

В разрабатываемых для НСМ локально-генетических алгоритмах можно использовать несколько стадий фильтрации, причем одним из требований является экономичность - малые затраты времени на возникающие дополнительные вычисления. [c.238]

Простой генетический алгоритм со всеми восемью эвристиками без фильтрации 77 =70 5524, 5547, 5538 5536 22607 [c.239]

Достигается высокая степень обобщения задач структурного синтеза, что обусловлено единством структуры хромосом для разных приложений в НСМ. В то же время в обычных генетических методах семантика генов, их типы меняются от задачи к задаче и, следовательно, меняется алгоритм генетического поиска. Кроме того, в ряде приложений имеет место взаимозависимость разных генов и, как следствие, велика вероятность появления недопустимых хромосом после вьшолнения генетических операторов кроссовера и мутации. Для устранения подобного явления приходится применять дополнительные операторы корректировки хромосом, например метод РМХ. При применении НСМ отсутствует понятие недопустимых хромосом, не требуется корректировка хромосом, все гены относятся к одному типу integer. [c.223]

Адекватность 86 Алгебраизация 96 Алгоритм -генетический 185 [c.325]

Конструкторское проектирование СБИС включает ряд процедур. Разрезание (partitioning или компоновка) заключается в группировании компонентов по критерию связности, что нужно или для размещения формируемых групп в отдельных чипах при многокристальной реализации, или для определения их взаимного расположения в одном кристалле в процессе выполнения последующей процедуры планировки (floorplanning) кристалла. Группы при планировании представляются в виде прямоугольников, их расположение обычно определяется в интерактивном режиме, но находят применение также генетические алгоритмы. [c.134]

Во многих приложениях между генами существуют зависимости, приводящие к некорректности некоторых экземпляров хромосом, генерируемьк случайным образом. Некорректность, в частности, выражается в том, что для некорректньк хромосом не удается правильно определить значение целевой функции. Другими словами, в процессе генетического поиска нельзя допустить, чтобы в популяции появлялись некорректные хромосомы. Поскольку и кроссовер, и мутации могут приводить к формированию недопустимых потомков, приходится вводить в генетический алгоритм дополнительные операторы корректировки хромосом. Это обстоятельство усложняет алгоритм. [c.218]

Эффективность генетического метода определяется степенью приближения значения целевой функции 7 при стагнации к ее оптимальному значению. В ряде приложений со сложными структурнокритериальными моделями ввиду ограничений на время решения расчеты приходится прерывать до достижения стагнации, поэтому эффективность генетического алгоритма характеризуется также скоростью достижения уровня стагнации. [c.223]

Исходная задача декомпозируется, и каждая подзадача рассматривается как состоящая из двух частей. В первой части определяется очередная работа, во второй части эта работа назначается на обслуживание, т.е. для нее выбирается один из серверов. Каждая часть может вьшолняться с помощью некоторых эвристических и/или генетических алгоритмов. [c.227]

В известных генетических алгоритмах при решении сложных задач большой размерности типичным является характер приближения к решению, в котором скорость улучшения значений целевой функции в процессе поиска экстремума постепенно уменьшается и может наступить стагнация популяции при значениях целевой функции, существенно отличаюшихся от оптимальных. Поэтому необходимо использовать различные способы как ускорения сходимости, так и преодоления стагнации на уровнях, далеких от экстремума. [c.230]

Наиболее радикальным направлением преодоления ранней стагнации является применение многопопуляционных генетических алгоритмов и/или гибридных алгоритмов. [c.230]

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

Очевидно, что многопопуляционные генетические алгоритмы могут обеспечить более высокую степень приближения к глобальному экстремуму хотя бы потому, что при стагнации вблизи ло- [c.230]

Под гибридным алгоритмом понимают сочетание алгоритмов двух типов первый тип представлен генетическим алгоритмом, ко второму типу отнесены алгоритмы локальной оптимизации, оперирующие единственной хромосомой (или популяцией хромосом, но без применения кроссовера). Поэтому гибридные алгоритмы назьшают также локально-генетическими. [c.231]

В локально-генетических алгоритмах после каждого акта генерации двух потомков к каждому из них (или только к лучшему) применяется процедура локального поиска. Она заключается в выполнении макромутации и оценке целевой функции F для мутированной хромосомы. Если F улучшилась, то выполненная макромутация принимается, иначе делается новая попытка улучшить хромосому с помощью новой макромутации. Локальный поиск завершается после К неудачных попыток улучшения потомка. [c.231]

Для иллюстрации преимуществ локально-генетического подхода сравнивались результаты решения задач с помощью генетических алгоритмов простого однопопуляционного (ОГА), многопопуляционного (МГА) и локально-генетического алгоритма (ЛГА). Сопоставление ОГА и ЛГА на задаче синтеза расписаний N21 при ограничении числа вычислений целевой функции Р в проводимых экспериментах значением 10 000 дало значения Р, приведенные в табл. 2.1, где N - размер популяции. Отметим, что в этой задаче синтеза расписаний Р есть цена расписания, которая минимизируется. [c.232]

В то же время десять вариантов решения той же задачи N105 с помощью ЛГА при использовании локально-генетического алгоритма LGA1 сК = 120 и размером популяции 13 дало значения целевой функции Г в диапазоне 21 956.. .22 053 со средним значением 22 005. [c.232]

Эффективность локально-генетических алгоритмов существенно зависит от ряда факторов. Основными среди них следует назвать используемый набор эвристик, вероятности их выбора в операторах мутации и формирования начального поколения, глубину локального поиска, размер макромутаций. [c.232]

Аналогичные результаты получены и при решении задачи N105. Равновероятное применение всех восьми эвристик в простом генетическом алгоритме дало после 100 смен поколений значение целевой функции Р, усредненное по нескольким вариантам расчета, равное 22 607, а использование набора из трех перспективных эвристик - значение 22 424. [c.233]

Макромутация - одновременное изменение в хромосоме значений более чем одного гена. Макромутации лежат в основе локального поиска в эволюционно-генетических алгоритмах, они предназначены для улучшения целевой функции между операциями кроссовера. [c.235]

В некоторых задачах, имеющих то или иное секционирование, возможны дополнительные схемы позиционирования. Примерами таких задач могут служить многостадийные задачи синтеза расписаний. Для них используют также локально-генетический алгоритм LGA3, реализующий распределенный регулярный способ позиционирования. [c.236]

Рис.2.18. Хромосома - матрица С и подмножества мутируемых локусов в 088Р при использовании локально-генетических алгоритмов

Идея фильтрации используется достаточно широко. Например, такой необходимый в генетическом алгоритме оператор, как селекция, фактически реализует фильтрацию - отбрасьшание неудачных хромосом, генерируемьгх в операторах кроссовера или мутации. Одним из примеров фильтрации может служить упомянутый выше макрооператор Re-старт, который предназначен для преодоления ранней стагнации и заключается в переходе от текущего поколения к новому начальному поколению путем полной или частичной замены значений генов во всех хромосомах., [c.238]

Так, в задаче маршрутизации транспортных средств локально-генетический метод позволил повысить точность решения примерно на 10 %. Локальногенетические алгоритмы также превосходят по эффективности случайный метод поиска (метод Монте-Карло). [c.240]

Энциклопедия по машиностроению XXL

Оборудование, материаловедение, механика и ...