|
Читайте также: |
Комбинированный алгоритм позволяет найти оптимальный путь, не строя граф и не вычисляя все длины дуг этого графа. Определяются только те длины дуг, которые в процессе расчета принимают нулевые значения. В данном примере для поиска оптимального пути не считается только дуга / 2в - Но для: расчета по объекту, имеющему до 50 скважин и более, эффективность предложенного метода более значима.
Разработано немало комбинированных алгоритмов, использующих регулярные приемы прогноза будущего движения одновременно со случайными отклонениями от выбранных начальных отклонений. Методы случайного поиска широко применяются в системах САПР, так как вероятность успеха при попытках не зависит от размерности рассматриваемого пространства, а также от вида целевой функции.
Под комбинированными алгоритмами понимаются параметризованные алгоритмы, управляющие параметры которых определяются в процессе решения задачи. В соответствии с этим под комбинированным алгоритмом будем понимать алгоритм, в котором на различных этапах вычислительного процесса имеется возможность выбора на программном уровне одного из нескольких алгоритмов для решения исходной задачи или ее подзадач.
В комбинированных алгоритмах направление поиска выбирается по-разному в зависимости от приближения к оптимуму. Вдали от оптимума целесообразны направления, обеспечивающие улучшение значений целевой функции. По мере приближения к оптимуму более предпочтительными становятся направления максимального улучшения. Вблизи оптимума наиболее эффективны направления в сторону вероятного расположения оптимума.
В комбинированных алгоритмах могут применяться как общие правила отсева, применяемые в методе ветвей и границ (при поиске точных и приближенных решений), так и правила отсева, использующие специфику задачи. Примером может служить отсев с использованием принципа оптимальности Беллмана для задачи коммивояжера. Разумеется, применение отсева с учетом специфики задачи требует дополнительных вычислительных ресурсов.
Другой класс комбинированных алгоритмов предполагает разделение процесса интегрирования на серии последовательно выполняемых шагов. По характеру серий алгоритмы этого класса можно разделить на две группы: алгоритмы с разными сериями, причем внутри каждой серии используются методы интегрирования одного и того же типа (например, явные или неявные), и циклические алгоритмы с одинаковыми сериями, причем внутри каждой серии используются методы разных типов.
Задача конструирования комбинированных алгоритмов сложна и не решается однозначно. Учитывая это, а также многообразие методов и их модификаций, трудно выбрать наилучшую комбинацию даже при наличии априорной информации о свойствах задачи оптимизации и имеющихся в наличии ЭВМ.
Вычислительная реализация комбинированного алгоритма ставит ряд вопросов об информационной согласованности его элементов. Поскольку заранее не известно, к какому из элементов (алгоритмов) будет совершен переход, в каждом из алгоритмов должна быть предусмотрена подготовка информации для работы других алгоритмов. Эта подготовка может потребовать дополнительных вычислительных ресурсов (время, память), что должно учитываться при формировании списков алгоритмов.
Задача конструирования комбинированных алгоритмов сложна и не решается однозначно. Учитывая это, а также многообразие методов и их модификаций, трудно выбрать наилучшую комбинацию даже при наличии априорной информации о свойствах задачи оптимизации и имеющихся в наличии ЭВМ.
При конструировании комбинированных алгоритмов поиска предпочтение следует отдавать комбинациям методов, которые не требуют
Дата добавления: 2015-02-16; просмотров: 97 | Поможем написать вашу работу | Нарушение авторских прав |