Процедуры рационального поиска

Теории, позволяющие сравнивать достоинства альтернативных процедур поиска, разработаны далеко за пределами сферы экономической науки. Ряд таких теорий предложен в последние 30 лет специалистами в области управления и проблем искусственного интеллекта. Важная часть этой работы была выполнена на основе целочисленного программирования.

Задачи целочисленного (дискретного) программирования аналогичны задачам линейного программирования (максимизировать некую величину при ограничениях в виде линейных уравнений и неравенств), но при этом вводится дополнительное условие, что определенные переменные могут принимать только целочисленные значения. Это ограничение делает неприменимыми большинство наиболее мощных вычислительных методов, используемых в линейном программировании. В результате задачи целочисленного программирования гораздо сложнее в вычислительном аспекте, нежели аналогичные по числу переменных задачи линейного программирования.

Для решения задач целочисленного программирования используются различные виды высокоселективного поиска — например, метод «ветвей и границ», устанавливающий последовательно сужающиеся границы, в которых может находиться оптимальное значение и благодаря этому позволяющий вести поиск только в «перспективных» областях пространства. Значительный практический и теоретический интерес приобретает оценка относительной вычислительной эффективности конкурирующих процедур поиска, а также анализ того, как возрастает стоимость поиска в зависимости от размера поставленной задачи. До недавнего времени оценка алгоритмов поиска производилась по большей части эмпирически: они испытывались на модельных задачах. Однако в последние годы получила развитие так называемая теория вычислительной сложности, так что стало возможным отвечать на некоторые из этих вопросов более систематическим образом.

Я не могу изложить здесь теорию вычислительной сложности или рассказать обо всех возможностях ее применения для анализа рациональности прцедур. Хорошим введением к этой теме может быть работа Aho et al., 1974. Но одна группа важных результатов, полученных благодаря этой теории, заслуживает хотя бы краткого упоминания. Они показывают, как именно увеличивается объем вычислений, необходимых для решения данного класса задач, в зависимости от размера задачи — например, от количества переменных ¹⁰.

В тех областях, где объем необходимых вычислений резко возрастает с увеличением размера задачи, мы можем решать только небольшие задачи; там, где объем вычислений растет медленно, — задачи более сложные. Проблемы, которые ставит перед нами реальный мир, как правило, огромны по сравнению с возможностями даже самых мощных наших компьютеров. Следовательно, наши вычислительные модели — это всегда грубые приближения к реальности, и нам остается лишь надеяться, что, несмотря на свою неточность, они все же окажутся полезны. Для нас особенно важно, чтобы с увеличением размера задач не происходило быстрого роста вычислительных затрат.

В теории вычислительной сложности задачи данного размера принято считать «решаемыми», если необходимый объем вычислений растет не быстрее, чем размер, возводимый в некоторую фиксированную степень. Такие классы задач получили название «полиномиально сложных». Задачи, вычислительная сложность которых возрастает экспоненциально с увеличением размера, не относятся к классу полиномиально сложных, так как скорость роста объема необходимых вычислений превышает показатель их размера, возводимого в любую фиксированную степень.

Для большого и важного класса задач, включающего и общую задачу целочисленного программирования, а также стандартные задачи планирования, показано, что все входящие в него задачи имеют одинаковый уровень сложности. Если какая-то из них является полиномиально сложной, то и все остальные — тоже; если хоть одна из них — не полиномиально сложная, то это относится ко всем задачам данного класса. Такие задачи называются «NP-полными». Предполагается, хотя еще не доказано, что класс NP-полных задач является не полиномиально, а, вероятно, экспоненциально сложным.

Значение этих открытий и предположений состоит в доказательстве того, что сложности, связанные с вычислением, а также необходимость в аппроксимации — это не какое-то второстепенное досадное свойство нашего мира, с которым можно совладать, создавая более мощные компьютеры или воспитывая людей с более высоким интеллектом. Сложность глубоко присуща самой природе вещей, и разработка приемлемых аппроксимирующих процедур и эвристических методов, позволяющих проводить высокоселективный поиск в огромных пространствах, составляет самую сердцевину интеллекта, как человеческого, так и искусственного. Теория рациональности, не берущая в расчет всей сложности решения задач, заведомо несовершенна. Хуже, чем несовершенна: она может ввести в серьезное заблуждение, поставляя «решения» экономических проблем, неприложимые к реальной жизни.

Интересное и важное направление исследований вычислительной сложности связано с демонстрацией того, что сложность задач может быть уменьшена за счет снижения требований к их решению: то есть мы ограничиваемся решениями, аппроксимирующими оптимум, или заменяем критерий оптимальности на критерий удовлетворительности. Результаты этих исследований пока носят фрагментарный характер, но уже известно, что существуют случаи, где указанные модификации позволяют свести экспоненциальные и NP-полные классы задач к полиномиально-полным классам.

Теория эвристического поиска, созданная применительно к проблемам искусственного интеллекта и психологии обработки информации, занимается разработкой или идентификацией процедур поиска, которые позволили бы системам с ограниченными вычислительными возможностями принимать сложные решения и решать трудные задачи (общий обзор этой теории см. в: Nilsson, 1971). Когда операционная среда задачи имеет стереотипную структуру (так что решения задачи поиска не разбросаны случайным образом, а локализованы в соответствии с этой структурой), мыслящая система способна распознать стереотип и использовать его для высокоселективного поиска решений.

Например, одна из разновидностей селективного эвристического поиска, так называемый метод наилучшего приближения, состоит в следующем. Для каждой вершины, расположенной в области поиска, оценивается расстояние от этой вершины до решения. Каждый очередной шаг поиска начинают из той вершины среди найденных ранее, которая расположена на наименьшем расстоянии от искомого решения (см., например, Simon and Kadane, 1975). В других случаях, когда задача состоит в поиске хорошего или лучшего решения, можно установить верхнюю и нижнюю границы величин для решений, находящихся в определенной зоне области поиска. Если верхняя граница в зоне А ниже, чем нижняя граница в какой-либо другой зоне, значит, в зоне А вообще нет смысла вести поиск.

Этими отрывочными замечаниями я и ограничу обсуждение проблем вычислительной сложности и эвристического поиска. Какое значение эти достижения теории рациональности процедур могут иметь для экономической теории, определяемой как «наука, изучающая деятельность человека по созданию и использованию богатств», покажет будущее. Но то, что они являются неотъемлемой частью экономической теории как «науки, изучающей процесс распределения ограниченных ресурсов», вполне очевидно. Ограниченный ресурс — это вычислительные способности, то есть интеллект. Возможность человека решать сложные задачи и объем средств, которые необходимо мобилизовать для их решения, зависят от эффективности использования именно этого ресурса, человеческого интеллекта.

Date: 2015-10-21; view: 392; Нарушение авторских прав