Эвристика

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

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

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

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

Метод комбинирования эвристик [c.221]

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

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

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

Для выполнения очередного шага синтеза может быть использована одна из к возможных эвристик, /г > 1. [c.222]

Сокращаются размеры поискового пространства, а следовательно, повышается эффективность поиска, выражаемая как точностью, так и скоростью приближения к искомому результату. Действительно, мощность множества возможных альтернатив в НСМ равна V", где v - число эвристик, п - число генов. В то же время, например, в одностадийной задаче синтеза расписаний, рещаемой обычными генетическими методами, мощность множества альтернатив находится в диапазоне от и до л -с", где с - число серверов. Конечно, набор эвристик в НСМ должен быть разумным, иначе экстремум может оказаться вне пределов сокращенного пространства. [c.223]

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

Композиция множеств правил первой и второй частей синтеза порождает множество эвристик. [c.228]

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

Для второй части подзадач используются правила и по отношению к источникам с запасом продукта хотя бы одного типа большим, чем заказанный объем. Если таких источников нет, то применяется эвристика Qy В соответствии с этими правилами выбирается источник [c.229]

Алгоритмические способы повышения эффективности метода комбинирования эвристик [c.229]

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

Часто первоначальное включение эвристик в рабочий набор выполняется по субъективным предпочтениям. Однако в выбор эвристик можно вложить и объективное содержание. В частности, можно руководствоваться результатами применения приведенного далее алгоритма А , т.е. сравнением результатов автономного использования эвристик (см. такие результаты для задачи N25 в табл. 2.2, а для задачи - в табл. 2.3). [c.233]

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

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

А . Алгоритм выбора вероятности .использования г-й эвристики по результатам применения каждой эвристики в отдельности. Вероятность q. выбирается тем большей, чем лучше результат применения г-й эвристики [c.234]

Результаты расчетов целевой функции с помощью алгоритма Л соответствующие использованию каждой эвристики в отдельности, приведены в табл. 2.3, где Р. и 2 - значения целевой функции при использовании г-й эвристики с учетом и без учета штрафов соответственно. [c.234]

Обычный эвристический метод -использование единственной эвристики (лучшей из восьми) 6006 23377 [c.239]

Случайный выбор (метод Монте-Карло) со всеми восемью эвристиками 5585 22747 [c.239]

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

Как в № 3, но с использованием отобранного подмножества из четырех эвристик Яб Яг 2. Л А) 5356 5366, 5390 5371 22424 [c.239]

Случайный выбор по методу Монте-Карло с подмножеством из четырех эвристик 5430, 5387, 5409 5409 [c.239]

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

ЭВРИСТИКА - метод исследования, основанный на неформальных, интуитивных соображениях. Э - это догадки, основанные на общем опыте решения родственных задач. Попытка систематизировать Э принадлежит Р. Декарту, Г.В. Лейбницу, Б. Больцано и др. В большинстве случаев Э - прием, позволяющий сокращать количество просматриваемых вариантов при поиске решения задачи, причем этот прием обычно не гарантирует наилучшего решения задачи. Например, человек, играя в шахматы, пользуетсяэвристическими приемами выработки решения, т.к. продумать весь ход игры с начала до конца практически невозможно из-за слишком большого числа вариантов игры. [c.90]

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

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

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

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

Эвристика FвN25 ( целевая функция) 2 в N25 Р без учета штрафов) [c.233]

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

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

Моноэвристичные методы существенно уступают по точности решения методам комбинирования эвристик. [c.240]

Случайная комбинация эвристик может дать результат лучше, чем в моноэвристичном методе. [c.240]

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

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