|
тимальцым. Более того, м ож но показать, что для данной задачи описанны й алгоритм всегда дает глобально оптимальное решение. Обобщением метода локальной оптимизации являются та к называемые генетические алгоритмы. В этих алгоритмах окрестность определяется не для одного решения, а для пары реш ений (родителей) и даже для нескольких реш ений. И з полученной окрестности отбираются наиболее перспективные «дети» и ф ормируются новые пары (возм ожно с привлечение д р уги х реш ений) и т.д. Н апример, на основе перестановок (1,2,3,4) и (3,4,2,1) м ож но получить окрестность, беря очередность пары соседних элементов из первой перестановки, а очередность оставшейся пары —из второй, а потом наоборот, очередность пары соседних элементов из второй перестановки, а очередность другой пары из первой. Получаем шесть детей: (1,2,3,4), (2,3,4,1), (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,1) и (3,2,1,3) наиболее перспективны. Н а основе этой пары м ож но получить новую окрестность и т.д. М е т о д в е т в л е н и й В основе метода ветвлений леж ит процедура последовательного получения решения. еРазобьсм множество всех реш ений на подмножства, каждое подмножество на другие подмножества и т.д. до получения отдельных реш ений (Рис. 1.5) [20, 23, 24, 26, 27]. 54 |
ется локально оптимальным. Более того, можно показать, что для данной задачи описанный алгоритм всегда дает глобально оптимальное решение. Обобщением метода локальной оптимизации являются так называемые генетические алгоритмы. В этих алгоритмах окрестность определяется не для одного решения, а для пары решений (родителей) и даже для нескольких решений. Из полученной окрестности отбираются наиболее перспективные «дети» и формируются новые пары (возможно с привлечение других решений) и т.д. Например, на основе перестановок (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 |