ПОИСК Статьи Чертежи Таблицы Генетический метод комбинирования эвристик из "Основы автоматизированного проектирования " Возможны два подхода к формированию хромосом. Первый из них основан на использовании в качестве генов проектных параметров. Например, в задаче размещения микросхем на плате локусы соответствуют посадочным местам на плате, а генами являются номера (имена) микросхем. Другими словами, значением -го гена будет номер микросхемы в к-й позиции. [c.190] Во втором подходе генами являются не сами проектные параметры, а номера эвристик, используемых для определения проектных параметров. Так, для задачи размещения можно применять несколько эвристик. По одной из них, в очередное посадочное место нужно помещать микросхему, имеющую наи-больщее число связей с уже размещенными микросхемами, по другой — микросхему с минимальным числом связей с еще не размещенными микросхемами и т. д. Генетический поиск в этом случае есть поиск последовательности эвристик, обеспечивающей оптимальный вариант размещения. [c.190] Второй подход получил название метод комбинирования эвристик. Этот метод оказывается предпочтительным во многих случаях. Например, в задачах синтеза расписаний распределяется заданное множество работ во времени и между обслуживающими устройствами — серверами, т. е. проектными параметрами для каждой работы будут номер сервера и порядковый номер в очереди на обслуживание. Пусть N— число работ, М— число серверов. Если гены соответствуют номерам работ, то в первом подходе в хромосоме нужно иметь 2N генов и общее число отличающихся друг от друга хромосом W заметно превьппает наибольшее из чисел Л и М . [c.190] Очевидно, что меньпшй размер хромосомы ведет к лучшей вычислительной эффективности, а меньшее значение Wпозволяет быстрее найти окрестности искомого экстремума. Кроме того, в методе комбинирования эвристик все хромосомы, генерируемые при кроссовере, будут допустимыми. В то же время при применении обычных генетических методов необходимо использовать процедуры типа РМХ для корректировки генов, относящихся к номерам в очереди на обслуживание, что также снижает эффективность поиска. [c.190] Вернуться к основной статье