|
ли. Для второго имеем Т = 20. Это решение, как легко показать, является локально оптимальным. Более того, можно показать, что для данной задачи описанный алгоритм всегда дает глобально оптимальное решение. »»<•»••<•• ••■■■<»»••I• **<#»•• »»*•% I I [19] [17] [22] Рис. 1.4.4 Обобщением метода локальной оптимизации являются так называемые генетические алгоритмы. В этих алгоритмах окрестность определяется не для одного решения, а для пары решений (родителей) и даже для нескольких решений. Из полученной окрестности отбираются наиболее перспективные «дети» и формируются новые пары (возможно с привлечение других решений) и т.д. Например, на основе перестановок (1,2,3,4) и (3,4,2,1) можно получить окрестность, беря очередность пары соседних элементов из первой перестановки, а очередность оставшейся пары из второй, а потом наоборот, очередность пары соседних элементов из второй перестановки, а очередность другой пары из первой. Получаем шесть детей: Из них двое полностью идентичны одному из родителей. Исключая их, получаем окрестность из четырех перестановок: Предположим, что «дети» (2,3,4,1) и (3,2,1,3) наиболее перспективны. На основе этой парыможно получить новую окрестность ит.д. (2,3,4,1), (3,4,1,2), (4,2,1,3) и (2,1,3,4) |
второго имеем Т = 20. Это решение, как легко показать, является локально оптимальным. Более того, можно показать, что для данной задачи описанный алгоритм всегда дает глобально оптимальное решение. Обобщением метода локальной оптимизации являются так называемые генетические алгоритмы. В этих алгоритмах окрестность определяется не для одного решения, а для пары решений (родителей) и даже для нескольких решений. Из полученной окрестности отбираются наиболее перспективные «дети» и формируются новые пары (возможно с привлечение других решений) и т.д. На4 пример, на основе перестановок (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) наиболее перспективны. На основе этой пары можно получить новую окрестность и т.д. 2. Метод ветвлений В основе метода ветвлений лежит процедура последовательного получения решения. Разобьем множество всех решений на подмножества, каждое подмножество на другие подмножества и т.д. до получения отдельных решений (Рис. 1.5) [20,23,24, 26,27]. Если теперь для каждой вершины полученного дерева определить некоторую функцию оценки соответствующего подмножества (функция приоритета), 81 |