§ 5. Метод случайного поиска с адаптацией (алгоритм СПА) [82,108]

Разобьем отрезок (0-1) на  одинаковых участков и сопоставим каждый участок своему признаку: 1-й участок соответствует первому признаку, 2-й — второму и т. д. Каждый участок имеет ширину . Запускается датчик случайных чисел с равномерным распределением в диапазоне (0-1). Если число попадает в -й участок, то -й признак включается в испытуемый набор признаков. После  шагов работы датчика выбранными оказываются  признаков. Качество этой случайно выбранной подсистемы оценивается по одному из критериев, например по числу получаемых ошибок распознавания .

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

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

После некоторого количества  циклов поиска и адаптации процесс стабилизируется: участки удачливых признаков занимают практически весь отрезок (0-1) и в испытуемую подсистему выбираются одни и те же признаки. Этот факт служит сигналом к окончанию процесса выбора -мерной подсистемы наиболее информативных признаков.

Скорость сходимости и качество получаемого решения зависят от величины . При больших значениях  процесс останавливается раньше, но качество полученного решения обычно хуже, чем при малых . Малые значения  соответствуют более мягкой стратегии поощрений и наказаний. Это иллюстрирует рис. 24. Если исходить из того, что признак, наказываемый на всех  шагах адаптации, все еще сохраняет ненулевое значение  длины своего участка, то величина  должна выбираться из соотношения . Практически приемлемые результаты получаются при  и .

В более сложных случаях, где полный перебор был невозможен, качество подсистемы признаков, выбранных методом СПА, сравнивались с качеством исходной системы из  признаков. Как правило, за приемлемое время алгоритм СПА выбирал подсистему, которая по информативности мало уступала исходной системе, что позволяет считать выбранную подсистему близкой к оптимальной. На одних и тех же примерах алгоритм СПА показывает лучшие результаты, чем описанные алгоритмы Del и Add.