Одно из главных предназначений информационных технологий — способствовать принятию решений, близких к оптимальным, на важнейших этапах жизненного цикла промышленной продукции. Большинство актуальных задач, подлежащих решению на этапах проектирования и производства изделий, характеризуется высокой размерностью, наличием трудно формализуемых ограничений, нечисловым характером части переменных. В этих условиях формализация задач принятия решений при планировании, распределении ресурсов, проектировании сложных изделий в различных приложениях вызывает известные трудности. В частности, затруднения связаны с дискретным характером проектных параметров и с отсутствием эффективных методов решения NP-трудных задач дискретного математического программирования.
К числу подобных задач относятся многие проектные и логистические задачи, например, синтез топологии вычислительных сетей и распределение в них трафика, частотное планирование для систем мобильной связи, раскрой материалов, компоновка оборудования, синтез расписаний производственных процессов, маршрутизация транспортных средств и др.
Как правило, попытки решения NP-трудных задач дискретной оптимизации большой размерности связаны с использованием тех или иных эвристических методов. Выбор эвристик носит субъективный характер и обычно отражает лишь часть предъявляемых требований к объекту синтеза. В результате решения оказываются далекими от оптимальных, а иногда и вообще неприемлемыми.
В последние годы разработчики методов и программ для решения сложных проектных и логистических задач структурного синтеза все чаще обращают внимание на генетические методы. В этих методах проектные решения представляются в виде фреймов (хромосом), являющихся упорядоченными множествами значений (аллелей) проектных параметров (генов). Использование принципов естественного отбора, аналогичных действующим в живой природе, по отношению к подмножествам (популяциям) хромосом приводит к постепенной концентрации полезных свойств у передовых членов популяции, т.е. к приближению к экстремуму функции полезности. Однако широкому применению генетических методов препятствует высокая вероятность получения некорректных (нежизнеспособных) хромосом в процессе генетического поиска в связи со случайным характером процедур мутации и кроссовера. Необходимость отбраковки или корректировки таких хромосом отрицательно сказывается на эффективности поиска.
Сохранить высокую эффективность генетического поиска позволяет предложенный нами генетический метод комбинирования эвристик [1]. Сущность метода заключается в совместном использовании множества альтернативных эвристик, последовательность применения которых оптимизируется с помощью генетического поиска. Каждая эвристика отражает ограничение, условие работоспособности или локальную целевую функцию, т.е. то или иное частное требование к свойствам проектируемого объекта, а генами при комбинировании эвристик являются номера эвристик. Программу, реализующую метод комбинирования эвристик, можно представить как некоторую экспертную систему, в которой база знаний содержит множество эвристик, а интерпретатор выбирает эвристики по генетическому алгоритму.
Метод комбинирования эвристик применялся для решения ряда задач и показал высокую эффективность. Возможности метода иллюстрируют приводимые ниже примеры.
В задачах синтеза расписаний типа JSSP или OSSP требуется минимизировать затраты на выполнение множества работ путем распределения их обслуживания во времени и между несколькими заданными серверами при соблюдении временных ограничений и ряда дополнительных условий. В тестовой задаче (105 работ и 15 серверов) были сформулированы около 10 эвристик. Решение выполнялось в два этапа. На первом этапе оценивалась эффективность эвристик. На втором проводился генетический поиск при комбинировании отобранных 3-5 эвристик. Решение занимает около 1-2 мин счета на Pentium 833 МГц. Стоимость реализации получающихся расписаний оказывается на 8-12% меньше, чем расписания, полученного при использовании лучшей (но единственной) эвристики.
В задачах компоновки оборудования и маршрутизации транспортных средств выигрыш в качестве получающихся решений оказывался еще более существенным — полученные в задачах минимизации значения функции полезности в 1,5-2 раза оказывались меньше, чем при одноэвристическом подходе или при использовании простого генетического алгоритма.
При проектировании сетей передачи данных SDH (синхронной цифровой иерархии) ставилась задача минимизации затрат на прокладку линий передачи и выбор типа оборудования в узлах сети. Выбор оборудования того или иного уровня иерархии (Е1, Е4 или Е16) определялся величиной трафика. Дополнительным усложняющим условием было проведение синтеза с учетом возможных одиночных отказов линий и оборудования. Характер генетического поиска для тестовой задачи
Загрузка...
