|
55 О о Рис. 1.5. Разбиение множества всех реш ений на подмиожства Если теперь для каж дой верш ины полученного дерева определить некоторую ф ункцию оценки соответствую щ его подмножества (ф ункция приоритета), качественно характеризую щ ую вероятность того, что в данном подмножестве найдется оптимальное или хотя бы «достаточно хорошее» решение, то мы получаем алгоритм поиска решения, двигаясь по ветви дерева, имею щ ей м аксимальное значение ф ункции оценки (или минимальное, если вероятность наличия достаточно хорош его реш ения тем больше чем меньше значение ф ункции оценки). В задачах календарного планирования метод ветвлений реализуется в так называемых эвристических алгоритмах распределения ресурсов [7, 10, 19, 26, 27]. М е т о д ве т ве й и г р а н и ц М етод ветвей и границ это метод ветвлений, в котором в качестве ф ункции оценки подмножеств берутся оценки снизу (ил и сверху) целевой ф ункции задачи на данном подмножестве реш ений. Основное преимущ ество этого метода по сравнению с методом ветвлений в том, что возможна оценка близости получаемого решения к оптимальному. Действительно, если мы получили решение п со значением целевой ф ункции ф(д), а оценки снизу остальных подмножеств |
ется локально оптимальным. Более того, можно показать, что для данной задачи описанный алгоритм всегда дает глобально оптимальное решение. Обобщением метода локальной оптимизации являются так называемые генетические алгоритмы. В этих алгоритмах окрестность определяется не для одного решения, а для пары решений (родителей) и даже для нескольких решений. Из полученной окрестности отбираются наиболее перспективные «дети» и формируются новые пары (возможно с привлечение других решений) и т.д. Например, на основе перестановок (1,2,3,4) и (3,4,2,1) можно получить окрестность, беря очередность пары соседних элементов из первой перестановки, а очередность оставшейся пары — из второй, а потом наоборот, очередность пары соседних элементов из второй перестановки, а очередность другой пары из первой. Получаем шесть детей: (1,2,3,4), (2,3,4,!), (3,4,2,1), (3,4,1,2), (4,2,1,3) и (2,1,3,4). Из них двое полностью идентичны одному из родителей. Исключая их, получаем окрестность из четырех перестановок: (2,3,4,1), (3,4,1.2), (4,2,1.3) и (2,1,3,4) Предположим, что «дети» (2,3,4,!) и (3,2,1,3) наиболее перспективны. На основе этой пары можно получить новую окрестность и т.д. Метод ветвлений В основе метода ветвлений лежит процедура последовательного получения решения. Разобьем множество всех решений на подмножества, каждое подмножество на другие подмножества и т.д. до получения отдельных решений (Рис. 1.5) [20, 23,224, 26, 27]. Если теперь для каждой вершины полученного дерева определить некоторую функцию оценки соответствующего подмножества (функция приоритета), качественно характеризующую вероятность того, что в данном подмножестве найдется оптимальное или хотя бы «достаточно хорошее» решение, то мы получаем алгоритм поиска решения, двигаясь по ветви дерева, имеющей максимальное значение функции оценки (или минимальное, если вероятность наличия достаточно хорошего решения тем больше чем меньше значение функции оценки). В задачах календарного планирования метод ветвлений реализуется в так называемых эвристических алгоритмах распределения ресурсов [7, 10, 19, 26, 27]. 47 о оРис. 1.5. Метод ветвей и границ Метод ветвей и границ это метод ветвлений, в котором в качестве функций оценки подмножеств берутся оценки снизу (или сверху) целевой функции задачи на данном подмножестве решений. Основное преимущество этого метода по сравнению с методом ветвлений в том, что возможна оценка близости получаемого решения к оптимальному. Действительно, если мы получили решение я со значением целевой функции ф(я), а оценки снизу остальных подмножеств ri(Q) > ф(с) (рассматриваем задачу на минимум), то очевидно, полученное решение оптимально. Если наилзшшая оценка t](Q) < ф(я), то разность Д = ф (я)-Т1(0) определяет погрешность полученного решения [22, 25, 27,28]. Эффективность метода ветвей и границ в существенной степени зависит от «качества» нижних оценок. При плохих оценках это фактически полный перебор, при достижимой нижней оценке это получение оптимального решения за один проход по дереву ветвлений. Заметим, что функция приоритета, основанная на степени критичности работ фронта в эвристических алгоритмах распределения ресурсов, является оценкой снизу продолжительности проекта (насколько хороша 48 |