§ 5. Метод случайного поиска с адаптацией (алгоритм СПА) [82,108]
Разобьем отрезок (0-1) на
одинаковых участков и сопоставим каждый участок своему признаку: 1-й участок соответствует первому признаку, 2-й — второму и т. д. Каждый участок имеет ширину
. Запускается датчик случайных чисел с равномерным распределением в диапазоне (0-1). Если число попадает в
-й участок, то
-й признак включается в испытуемый набор признаков. После
шагов работы датчика выбранными оказываются
признаков. Качество этой случайно выбранной подсистемы оценивается по одному из критериев, например по числу получаемых ошибок распознавания
.
Описанная процедура случайного выбора
-мерных подсистем признаков и оценки их качества повторяется
раз. Рассмотрение полученного списка оценок
позволяет выбрать наилучшую и наихудшую из подсистем. На этом основании делается процедура «поощрения» и «наказания»: участки, соответствующие признакам, попавшим в наилучшую подсистему, поощряются путем расширения их границ на величину
, а участки, соответствующие признакам из самой неинформативной подсистемы, наказываются тем, что их ширина уменьшается на величину
. Суммарная длина всех участков по-прежнему равна единице.
После этого случайным образом выбираются и испытываются
новых подсистем. Но теперь вероятность попадания признаков в эти подсистемы не одинакова: поощренные признаки, представленные более широкими отрезками, имеют больше шансов войти в очередную подсистему, чем наказанные. По результатам испытания этой партии подсистем процедура адаптации (наказания и поощрения) повторяется. Если некоторый признак случайно попадает и в самую лучшую и самую худшую подсистемы, то длина его участка остается неизменной. Если же он регулярно оказывается в составе самой информативной подсистемы, то длина его участка растет с каждым шагом адаптации. Точно так же признак, систематически попадающий в самую неинформативную подсистему, с каждым шагом сокращает длину своего участка и тем самым уменьшает вероятность включения в испытуемые подмножества признаков.
После некоторого количества
циклов поиска и адаптации процесс стабилизируется: участки удачливых признаков занимают практически весь отрезок (0-1) и в испытуемую подсистему выбираются одни и те же признаки. Этот факт служит сигналом к окончанию процесса выбора
-мерной подсистемы наиболее информативных признаков.
Скорость сходимости и качество получаемого решения зависят от величины
. При больших значениях
процесс останавливается раньше, но качество полученного решения обычно хуже, чем при малых
. Малые значения
соответствуют более мягкой стратегии поощрений и наказаний. Это иллюстрирует рис. 24. Если исходить из того, что признак, наказываемый на всех
шагах адаптации, все еще сохраняет ненулевое значение
длины своего участка, то величина
должна выбираться из соотношения
. Практически приемлемые результаты получаются при
и
.
В более сложных случаях, где полный перебор был невозможен, качество подсистемы признаков, выбранных методом СПА, сравнивались с качеством исходной системы из
признаков. Как правило, за приемлемое время алгоритм СПА выбирал подсистему, которая по информативности мало уступала исходной системе, что позволяет считать выбранную подсистему близкой к оптимальной. На одних и тех же примерах алгоритм СПА показывает лучшие результаты, чем описанные алгоритмы Del и Add.