Хромосома

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

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

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

Обозначим число экземпляров схемы Н в поколении с номером t через ДН, t). Введем также следующие обозначения Л - размер (число хромосом) популяции Q - множество номеров членов популяции, в хромосомах которых имеется схема Н /)(Н) - длина схемы Н, т.е. расстояние (число позиций) между крайними локусами схемы, так, в случае (2.5) имеем ДН) = 8-4 = 4 Х(Н) - порядок схемы Н (число локусов в Н), в примере (2.5) порядок равен 3 п - длина хромосомы. [c.215]

Тогда, если выбор родителей осуществляется по формуле (2.4), то число Кр схем Н, усредненное по N актам выбора родителей, в выбираемых родительских хромосомах равно [c.215]

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

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

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

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

П р и м е р 6. Пусть в задаче о назначениях требуется распределить п работ между п исполнителями так, чтобы каждый исполнитель вьшолнял одну работу и общая стоимость вьшолнения работ была минимальной. Можно сформировать хромосому из п генов так, чтобы гены соответствовали исполнителям, а их значениями были номера работ. На рис. 2.15 показаны возможные пары хромосом родителей и потомков для случая и = 10. Видно, что хромосомы потомков некорректны, так как в первой из них работы 7 и 9 назначены двум исполнителям каждая, а работы 1 и 2 вообще не назначены. Во второй хромосоме противоположная [c.218]

Пример . Рассмотрим задачу разбиения графа на два подграфа так, чтобы число верщин в подграфах и бьшо равно заданным значениям N a при этом целевая функция имела экстремальное значение. Будем считать, что если аллель А -го гена равен 1, то вершина к находится в А , если же аллель к-то гена равен о, то - в Aj. Очевидно, что число единиц в хромосоме должно равняться N , число нулей - N . Однако это условие для хромосом потомков, получающихся в результате кроссовера или мутаций, в общем случае не соблюдается, причем по-прежнему вероятность получения корректного потомка крайне мала. [c.219]

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

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

Типичная структура программы выбора оптимального решения на основе НСМ приведена на рис. 2.16. Слева показаны блоки инвариантной к приложениям части программного обеспечения, ие-полняющей операторы генетического и/или локального поиска. Процедуры эвристик служат для решения подзадач, в них определяются локальные целевые функции В модели приложения вычисляется общая целевая функция (Х) для каждой хромосомы, генерируемой при формировании начального поколения или в процессе локального поиска. При переходе к новому приложению достаточно заменить показанные на рис. 2.16 справа блоки модели и эвристик. [c.224]

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

В итоге хромосома включает п = генов, значениями генов являются номера эвристик. [c.228]

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

Ау Самонастраивающийся алгоритм, при котором q. для Л-го поколения определяется по формуле (2.6), в которой /, подсчитано по лучшей хромосоме к - 1)-го поколения. [c.234]

Сначала формируется исходное поколение. При этом фильтр Ф осуществляет среди генерируемых случайным образом хромосом отбор тех, у которых целевая функция лучше некоторого порогового значения Г51, т.е. F < TS. Отобранные в Ф хромосомы подвергаются процедуре П локального улучшения с некоторой глубиной локального поиска и поступают на фильтр Ф2, в котором отбираются члены исходного поколения по условию F < TS2. [c.238]

В процессе локально-генетического поиска могут использоваться также фильтры Ф3 и Ф4, аналогичные по своему назначению фильтрам Ф, и Фз- В Фз проходят отбор дочерние хромосомы, получаемые в результате кроссовера, по условию F < TS3. В Ф4 фильтруются хромосомы, которые после Ф3 прошли также через процедуру П2 локального спуска. [c.238]

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

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

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

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

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

Корректировка хромосомы заключается в принудительном изменении значений некоторых генов в хромосоме потомка. Например, в задаче разбиения графа (см. пример 7) левый участок хромосомы, который взят от одного из родителей, можно оставить без изменений, а в правом участке, взятом от другого родителя, нужно согласовать число единиц с требуемым тем или ршым способом. [c.219]

Преодолеть этот недостаток можно, если использовать идею представления в хромосоме информации о синтезируемом объекте в неявной форме. Гены в этом случае не представляют сами структурные параметры, а указывают на способ определения этих параметров. Например, при синтезе расписаний гены должны представлять не номера работ или обслуживающих агшаратов, а правила генерации очередного варианта расписания. Эта идея неявного описания параметров реализована в методе, названном методом комбинирования эвристик (НСМ - Heuristi s ombination Method) [63]. [c.221]

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

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

F = fitfun( ) /" tfun - процедура вычисления значения целевой функции, реализует структурно-критериальную модель, СС - хромосома / i = 0 [c.231]

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

Пояснить все три способа позиционирования можно с помощью рис. 2.18, на котором хромосома для многостадийных задач синтеза расписаний представлена в виде матрицы С. Ее элемент Q, есть ген, относящийся к /-му шагу синтеза на -й стадии. В LGA2 одновременной мутации подвергается R генов с последовательными номерами /, что и обусловливает название горизонтальный поиск . В LGA3, наоборот, мутируют гены с последовательными номерами к, т.е. вертикально раеположенные в матрице С. [c.236]

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

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

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

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

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