Учебная САПР электронных средств. Асланянц В.Р. - 10 стр.

      • метод случайного поиска;
      • эвристические алгоритмы (последовательные итерационные, ди-
хотомические, генетические и др.). В этом случае можно говорить об эври-
стическом программировании.
      Эвристическое программирование. Если решение задачи точными
методами трудоемко, то довольствуются приближенным достаточно хо-
рошим для практики решением, которое отыскивается с использованием
специальных приемов – эвристик, позволяющих сокращать число про-
сматриваемых вариантов. Эвристики разрабатываются на основе изучения
и использования специфики конкретных задач.
      Потребности практики автоматизированного конструирования ЭС
обусловили развитие и широкое использование методов оптимизации, в
которых ценой отказа от получения точного решения экстремальной зада-
чи существенно уменьшается высокая трудоемкость, присущая описанным
выше методам решения задач дискретного программирования. Для этого
направления характерны два принципиально разных подхода: методы слу-
чайного поиска и эвристические методы.
      Эвристические подход основан на использовании совокупности эв-
ристик – приемов, обеспечивающих в процессе поиска приближение к оп-
тимальному решению, хотя и не гарантирующих его достижение.
      Примером эвристических алгоритмов могут служить последователь-
ные алгоритмы размещения конструктивных элементов и разбиения схем
ЭС [1, 3, 5, 6], а также комбинаторные аналоги градиентных методов, рас-
смотренные в подразделе 4.1. Действительно, как известно градиентные
методы основаны на свойстве непрерывности целевой функции, и приме-
нение идей градиентных методов к дискретным задачам может дать хоро-
шие результаты только для определенного класса задач, что определяется
экспериментально.
      Один из путей построения эвристических алгоритмов – анализ про-
цесса решения задачи некоторым точным методом и введение эвристик в
этот процесс, обеспечивающих существенное сокращение объема вычис-
лительной работы. Так, например, если в методе ветвей и границ после ка-
ждого ветвления сохранять лишь одно (или небольшое число) наиболее
перспективных подмножеств решений, то процесс быстро сходится. Одна-
ко гарантий получения оптимального решения уже нет: оно может ока-
заться в отброшенном подмножестве решений.




                                                                      10