Реферат: Оптимизация отбора оптимальных признаков на основе приме-нения методов моделирования эволюции для задачи распозна-вания текста

Оператор Мутации (ОМ): соответствует случайному нарушению последовательности битов в стринге; например, применяя ёоператор мутации к X', можно получить X''₁ :x₁ x₂ x₃ x₄ x₅ y₂ y₃ y₁ или X''₂ :x₁ x₃ x₂ x₄ x₅ y₃ y₂ y₁ и т.д. Обычно выбирают одну мутацию на 1000 бит. Считается, что мутация - вторичный механизм в ГА.

Для оптимизации поиска оптимальных признаков использование ГА может быть описано следующим образом.

Сначала определяется соответствие между хромосомой и полосовым признаком. В данном случае полосовой признак (растровое изображение) "вытягивается" в вектор (стринг). Далее случайным образом генерируется некоторое множество возможных полосовых признаков - начальная популяция P₀ =X⁰ ₁ , X⁰ ₂ , … X⁰ _n . Затем для каждой хромосомы вычисляется функция фитности, которая в данном случае представляет собой комплексную оценку, вычисляемую с учетом критериев отбора оптимальных признаков первого рода.

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

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

Список литературы

Ефимов Ю.Н. Распознавание изображений с использованием оптимальных признаков АВТ.-1992.-№2.-С. 69-75.

1531115 СССР. Устройство для распознавания образов/ Ефимов Ю.Н. -заявлено 08.10.87// Открытия. Изобретения. Пром. образцы. Товар. знаки.-1989.-№47.- С.162.

1799359 СССР. Устройство для распознавания образов/ Ефимов Ю.Н. -заявлено 12.12.89// Открытия. Изобретения. Пром. образцы. Товар. знаки.-1992.-№4.- С.195.

Holland. I. Adaptation in Natural and Artifical Systems. University of Michigan Press, Ann Arbor, 1975.

Курейчик В. М. Применение генетических методов для компоновки схем СБИС. сб. Интеллектуальные САПР №4, 1994.

Хант Э. Искусственный интеллект, «Мир», М. 1978.

Rosenblatt F. The perceptron: A probalistic model for information storage and organization in the brain, Psychol. Rev., 65, 386-408, 1958.

Rosenblatt F. Principles of neurodynamics, Baltimore, 1962, (Русскийперевод: РозенблаттФ., Принципынейродинамики, «Мир», М., 1966).

Selfridge O. Pandemonium. A paradigm for learning, всб. «Proceedings of the Symposium on the Mechanization of Tought Processes» подред. Blake D., Utteley A., London, 1959.

McCulloch W., Pitts W. A logical calculus of the ideas imminent in nervous activiti, Bull. Math. Biophys., 5, 115-137., (Русский перевод в сб. «Автоматы» под ред. Маккарти Дж. и Шеннона К., ИЛ. М., 1956).

Hebb D. The organization of behavior, New York, 1948.