 |
Генетическая модификация МООП
|
|
|
|
В работе [4] описаны модели наследственности и эволюции из области популяционной генетики. Эволюция осуществляется в результате взаимодействия трех основных факторов: изменчивости, наследственности и естественного отбора.
Генетический алгоритм (ГА) - это поисковый алгоритм, основанный на моделировании механизмов естественной эволюции. На каждом шаге генетического алгоритма создается новое множество решений, в котором используются части предыдущих решений и добавляются новые части. Таким образом генетические алгоритмы используют историческую информацию.
Основные отличия ГА состоят в следующем:
ГА осуществляют поиск из множества (популяции) точек, а не из единственной точки;
ГА используют целевую функцию для оценки информации, а не ее различные приращения.
Рассмотрим механизм простого ГА (ПГА): сначала ГА случайно генерирует популяцию последовательностей (стрингов); далее он копирует последовательности и переставляет их части; затем ГА применяет некоторые операторы к начальной популяции и генерирует новые популяции.
В ПГА используется 3 оператора: репродукция, кроссовер, мутация. Поясним кратко действие некоторых используемых генетических операторов.
Оператор Репродукции (ОР): механизм репродукции включает копирование стргингов. Репродукция - процесс, в котором стринги воспроизводятся согласно их функции фитности. Стринги с большим значением функции фитности имеют большую вероятность попадания в следующую генерацию. Один из способов алгоритмической реализации ОР – моделирование колеса рулетки, в котором каждый стринг имеет сектор, величина которого пропорциональна значению функции фитности стринга.
|
|
|
Оператор Кроссовера (ОК): оператор кроссовера может выполниться в 2 шага. На первом шаге элементы множества стрингов случайно разбиваются на пары. Затем из каждой пары стрингов формируется новая пара по правилу: случайно выбирается целочисленная позиция вдоль стринга между 1 и длиной стринга L - точка скрещивания. Новая пара стрингов создается вследствие обмена частями исходных стрингов, относительно точки скрещивания. Например, X и Y представляют собой два стринга (родители). Если теперь случайным или заранее заданным способом выбрать точку скрещивания, то смешивая части исходных векторов можно получить два новых потомка:X' и Y'.
X: x1x2x3x4x5 | x6x7x8
Y: y8y7y6y5y4 | y3y2y1
X': x1x2x3x4x5 | y3y2y1
Y': y8y7y6y5y4 | x6x7x8
Возможно проводить операцию скрещивания не относительно одной точки (одноточечный кроссовер), а относительно нескольких точек (многоточечный кроссовер). В этом случае обеспечивается большее отличие потомков от предков.
Оператор Мутации (ОМ): соответствует случайному нарушению последовательности битов в стринге; например, применяя ёоператор мутации к X', можно получить X''1:x1x2x3x4x5y2y3y1 или X''2:x1x3x2x4x5y3y2y1 и т.д. Обычно выбирают одну мутацию на 1000 бит. Считается, что мутация - вторичный механизм в ГА.
Для оптимизации поиска оптимальных признаков использование ГА может быть описано следующим образом.
Сначала определяется соответствие между хромосомой и полосовым признаком. В данном случае полосовой признак (растровое изображение) "вытягивается" в вектор (стринг). Далее случайным образом генерируется некоторое множество возможных полосовых признаков - начальная популяция P0=X01, X02, … X0n. Затем для каждой хромосомы вычисляется функция фитности, которая в данном случае представляет собой комплексную оценку, вычисляемую с учетом критериев отбора оптимальных признаков первого рода.
Далее к популяции применяется оператор репродукции (ОР), который формирует новую популяцию, оставляя в ней хромосомы с вероятностью, пропорциональной значению функции фитности. На следующем шаге, используя случайный выбор, генерируются пары для применения к ним оператора кроссовера. Здесь возможно также использование оператора кроссовера для каждой пары с вероятностью pc, пропорциональной сумме значений функций фитности обеих хромосом. Это позволит воспроизвести некоторые из хромосом в следующем поколении и с большей вероятностью сохранить наиболее перспективные из них. Более эффективным является использование многоточечного скрещивания, так как это обеспечит большее разнообразие стрингов, что в данном случае весьма важно.
|
|
|
Так как при таком методе генерации решений существует возможность попадания в область локально-оптимальных решений, что для данной задачи будет характеризоваться тем, что для большого числа поколений не будет выполняться условие попарной совместной оптимальности стрингов (признаков), целесообразно использовать оператор мутации с некоторой вероятностью pm.
Список литературы
Ефимов Ю.Н. Распознавание изображений с использованием оптимальных признаков АВТ.-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.
|
|
|
