НАУКА и ОБРАЗОВАНИЕ

Оптимизация выбора эвристик при решении сложных задач проектирования и логистики

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

К числу подобных задач относятся многие проектные и логистические задачи, например,  синтез топологии вычислительных сетей и распределение в них трафика, частотное планирование для систем мобильной связи, раскрой материалов, компоновка оборудования, синтез  расписаний производственных процессов, маршрутизация транспортных средств и др.    

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

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

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

Метод  комбинирования эвристик применялся для решения ряда задач и показал высокую эффективность. Возможности метода иллюстрируют приводимые ниже примеры. 

В задачах синтеза расписаний типа JSSP или OSSP требуется минимизировать затраты на выполнение  множества работ путем распределения их обслуживания во времени и между несколькими заданными серверами при соблюдении временных ограничений и ряда дополнительных условий.  В тестовой задаче (105 работ и 15 серверов) были сформулированы около 10 эвристик. Решение выполнялось в два этапа. На первом этапе оценивалась эффективность эвристик. На втором проводился генетический поиск при комбинировании отобранных 3-5 эвристик. Решение занимает около 1-2 мин счета на Pentium 833 МГц. Стоимость реализации получающихся расписаний оказывается на 8-12% меньше, чем расписания, полученного при использовании лучшей (но единственной) эвристики. 

В задачах   компоновки оборудования и маршрутизации транспортных средств выигрыш в качестве получающихся решений оказывался еще более существенным - полученные в задачах минимизации значения функции полезности в 1,5-2 раза оказывались меньше, чем при одноэвристическом подходе или при использовании простого генетического алгоритма. 

 При проектировании сетей передачи данных SDH (синхронной цифровой иерархии) ставилась задача минимизации затрат на прокладку линий передачи  и выбор типа оборудования в узлах сети. Выбор оборудования того или иного уровня  иерархии (Е1, Е4 или Е16) определялся величиной трафика. Дополнительным усложняющим условием было проведение синтеза с учетом возможных одиночных отказов линий и оборудования.   Характер генетического поиска для тестовой задачи (сеть с 24 узлами) иллюстрирует рис. 1, на котором показано несколько траекторий поиска, S - функция полезности, Е - число обращений к процедуре вычисления этой функции.

Рис. 1. Характер изменения  функции полезности в процессе ее минимизации

Сведения о применении метода комбинирования эвристик в задачах частотного планирования в системах мобильной радиосвязи и задачах раскроя материалов приведены в статьях [2,3]  соответственно. Следует отметить, что по данным А.С.Мухачевой по мере роста размерности задач раскроя значимость метода комбинирования эвристик повышается и при определенном пороге размерности метод по своей эффективности оказывается вне конкуренции. 

Литература

1.     Норенков И.П. Эвристики и их комбинации в генетических методах дискретной оптимизации. //Информационные технологии, 1999, № 1.

2.     Писаренко Г.К. Алгоритмы частотного планирования в телекоммуникационных системах радиосвязи. // Информационные технологии, 2000, № 7.

3.     Мухачева А.С., Чиглинцев А.В. Генетический алгоритм поиска минимума в задачах двумерного гильотинного раскроя. // Информационные технологии, 2001, № 3.