УСТРОЙСТВО СЛУЧАЙНОГО ПОИСКА НА ОСНОВЕ ГЕНЕТИЧЕСКОГО АЛГОРИТМА

Изобретение относится к области обработки данных для специальных применений и может быть использовано, в частности, для определения на основе модифицированного генетического алгоритма координат точки с максимальным значением целевой функции в локальной области двумерного массива.
Известно устройство, содержащее генераторы пилообразного напряжения, аналого-цифровые и цифро-аналоговые преобразователи, элементы ИЛИ, блоки памяти функций принадлежности, блоки определения минимума, блоки сравнения, блоки вычитания из единицы, регистры, счетчик и элементы задержки с соответствующими связями [SU 1791815, G 06 F 7/58, 1990].
Недостатком устройства являются относительно узкие функциональные возможности.
Известно устройство, содержащее n параллельных сумматоров, входы и выходы которых являются, соответственно, группой входов и группой выходов устройства, а также n блоков умножения на весовые коэффициенты, при этом, вход i-ого блока умножения на весовые коэффициенты (i=1...N) соединен с выходом i-ого параллельного сумматора, а каждый из выходов j-ого блока умножения на весовые коэффициенты (j=1...N) соединен с соответствующим ему входом взвешенного сигнала i-ого сумматора (i нe=j), [А.В.Назаров, А.И.Лоскутов "Нейросетевые алгоритмы прогнозирования и оптимизации систем", Санкт-Петербург, "Наука и Техника", 2003 г., стр.231].
Недостатком устройства являются относительно узкие функциональные возможности.
Известно также устройство, содержащее N параллельных сумматоров, входы которых являются группой входов устройства, а также N блоков умножения на весовые коэффициенты, при этом, каждый из выходов j-ого блока умножения на весовые коэффициенты (j=1...N) соединен с соответствующим ему входом взвешенного сигнала i-ого параллельного сумматора (i=1...N, i не=j), а также N блоков сжатия отображения, причем, входы i-ых блоков умножения на весовые коэффициенты (i=1...N) соединены с выходами одноименных блоков сжатия отображения, входы которых соединены с выходами одноименных параллельных сумматоров, а выходы - являются группой выходов устройства [RU 45 579, U1, H 03 М 7/14, 2005].
Кроме того, в этом техническом решении блоки сжатия отображения выполнены в виде функциональных преобразователей входного сигнала Х в выходной сигнал Y по закону Y=1/(1+ехр(-X)).
Недостатком устройства является относительно узкие функциональные возможности, обусловленные тем, что, устройство позволяет формировать взвешенный код, характеризующий анализируемое изображение, но не позволяет определить в двумерном изображении координаты с максимальным значением целевой функции, например, максимума сигнала в анализируемом изображении.
Наиболее близким по технической сущности к предлагаемому является устройство, содержащее блок выделения фрагментов изображения, выходы которого соединены с группой пороговых блоков, выходы которых через группу преобразователей соединены с группой сумматоров [Y.LeCun, L.Bottou, Y.Bengio, P.Haffner. Gradient-based learning applied to document recognition. Proceeding of the IEEE, November, 1998, p.23].
Недостатком устройства является относительно узкие функциональные возможности, обусловленные тем, что, устройство позволяет формировать
сигнал распознавания изображения, но не позволяет определить в двумерном изображении координаты с максимальным значением целевой функции, например, максимума сигнала в анализируемом изображении.
Требуемый технический результат заключается в расширении функциональных возможностей путем определения в локальной области двумерного изображении координат точки с максимальным значением целевой функции и ее значение.
Требуемый технический результат достигается тем, что, в устройство, содержащее блок выделения фрагментов изображения, введены блок формирования опорного плана поиска, формирователь особи-потомка, первый, второй и третий входы которого соединены, соответственно, с первым, вторым и третьим выходами блока формирования опорного плана поиска, а группа входов - объединена с группой входов блока формирования опорного плана поиска и соединена с группой выходов блока выделения фрагментов изображения, блок определения максимума, первый, второй и третий входы которого соединены, соответственно, с первым, вторым и третьим выходами формирователя особи-потомка, а также формирователь родительской пары, первый и второй выходы которого соединены, соответственно, с первым и вторым входами блока формирования опорного плана поиска, и формирователь рекомбинации, первый и второй входы которого соединены, соответственно с первым и вторым выходами формирователя родительской пары, а выход - соединен с третьим входом блока формирования опорного плана поиска.
На чертеже представлены: на фиг.1 - электрическая структурная схема устройства случайного поиска на основе генетического алгоритма, на фиг.2 - рисунок, поясняющий его работу.
Устройство случайного поиска на основе генетического алгоритма (фиг.1) содержит блок 1 выделения фрагментов изображения, блок 2 формирования опорного плана поиска и формирователь 3 особи-потомка, первый, второй и третий входы которого соединены, соответственно, с
первым, вторым и третьим выходами блока 2 формирования опорного плана поиска, а группа входов - объединена с группой входов блока 2 формирования опорного плана поиска и соединена с группой выходов блока 1 выделения фрагментов изображения.
Устройство содержит также блок 4 определения максимума, первый, второй и третий входы которого соединены, соответственно, с первым, вторым и третьим выходами формирователя 3 особи-потомка, а также формирователь 5 родительской пары, первый и второй выходы которого соединены, соответственно, с первым и вторым входами блока 2 формирования опорного плана поиска, и формирователь 6 рекомбинации, первый и второй входы которого соединены, соответственно с первым и вторым выходами формирователя 5 родительской пары, а выход - соединен с третьим входом блока 2 формирования опорного плана поиска.
Блок 1 выделения фрагментов изображения как и в устройстве-прототипе может быть выполнено в виде блока памяти изображения (блока памяти видеокамеры, цифрового фотоаппарата и т.п.).
Охарактеризованные на функциональном уровне блок 2 формирования опорного плана поиска, формирователь 3 особи-потомка, блок 4 определения максимума, формирователь 5 родительской пары и формирователь 6 рекомбинации могут быть выполнены в виде программируемых (настраиваемых) многофункциональных средств (специализированных средств вычислительной техники, миникомпьютеров, микропроцессоров и т.п.). Для подтверждения возможности выполнения такими средствами конкретных предписываемых им в составе данного устройства функции ниже при описании работы устройства приводятся сведения в виде алгоритма их работы или соответствующего математического выражения.
Работает устройство случайного поиска на основе генетического алгоритма следующим образом.
Предварительно проведем теоретическое обоснование его работы.
Генетический алгоритм (ГА) представляет собой метод оптимизации, основанный на концепциях естественного отбора и генетики. ГА оперирует конечным множеством решений (популяцией) - генерирует новые решения как различные комбинации частей решений популяции, используя такие операторы, как отбор, рекомбинация (кроссинговер) и мутация. Новые решения позиционируются в популяции в соответствии с их положением на поверхности исследуемой функции.
n
n
Допустим нам нужно оптимизировать некоторую целевую функцию F, заданную на элементах множества [(x1, y1), (x2, y2),...(х, y)], соответствующих пространству изображения. Предположим также, что функция в исследуемой области имеет один глобальный максимум и не имеет локальных максимумов. Координаты максимума, позволяющие провести оптимизацию, не известны.
Тогда предлагаемый модифицированный генетический алгоритм будет состоять из следующих шагов (фиг.2):
p1
p1
р2
р2
1. Генерация начальной популяции - задание координат двух точек (x, y) и (х, y), соответствующих родительской паре.
к
к
к
p1
к
р2
2. Кроссинговер или рекомбинация - задание третьей точки, связанной с родительской парой, например, (х, y), где х=х, y=y), соответствующих родительской паре.
n
n
3. Получение особи-потомка, путем ее генерации взамен самой «плохой» из трех точек по величине функции F[(x1, y1), (x2, y2),...(х, y)] путем отражения этой «плохой» точки в противоположную вершину квадрата, вершинами которой являются три предыдущие точки (на фиг.2 показан частный случай, когда «плохой» точкой является точка (хк, yк).
4. Если самое лучшее решение в популяции нас не удовлетворяет, то осуществляется переход на шаг 3 для трех новых точек (с исключением «плохой» точки). При этом могут быть наложены ограничения в
продолжительности поиска, например, ограничения на число отражений.
Указанный алгоритм может быть реализован в предложенном устройстве следующим образом.
...
...
n
n
n
n
n
В блоке 1 выделения фрагментов изображения формируется массив взвешенный целевой функцией пространственных векторов, описывающих каждую точку изображения, элементами каждого из которых являются координата и значение функции F, заданной на элементах множества [(x1 y1) (x2,у2),(x, y)], т.е. [(f1, x1, y1), (f2, x2, y2), (f, x, y)].
Формирователь 2 родительской пары, выполненный, например, в виде датчика случайных чисел, формирует две точки, например [(x1, y1), (x2, y2)], которые могут быть рассмотрены как родительская пара.
к
к
к
1
к
2
По этим точкам формирователь 6 рекомбинации формирует третью точку, связанной с родительской парой, например, (х, y), где x=x, y=у), соответствующих родительской паре.
Все три сигнала поступают на вход блока 2 формирования опорного плана поиска, который работает по следующему алгоритму: для каждой тройки сигналов (x1, y1), (x2, y2), (xк=x1, yк=y2) блок 2 выделяет из блока 1 тройку взвешенных сигналов (f1, x1, y1), (f2, х2, y2), (f12, x1, y2) и транслирует их на выход - на вход формирователя 3 особи-потомка.
Формирователь 3 работает по следующему алгоритму:
к
к
- из трех взвешенных сигналов (f1, x1, y1), (f2, х2, y2), (f12, x=x1, y=y2) выделяется сигнал с меньшим значением первой составляющей f, т.е. самая «плохая» из трех точек;
отр
отр
к
к
к
к
- самая «плохая» из трех точек отражается в точку (х, y), которая соответствует противоположной вершине квадрата, вершинами которой являются три предыдущие точки (f1, x1, y1), (f2, х2, y2), (f12, x=x1, y=y2) (на фиг.2 показан частный случай, когда «плохой» точкой является точка (х, y);
отр
отр
- для отраженной точки (х, y) формируется значение целевой функции foтp в этой точке по сигналам, поступающим от блока 1 выделения фрагментов изображения;
отр
отр
отр
- все три сигнала (f1, x1, y1), (f2, х2, y2), (f, х, y) поступают на вход блока 4 определения максимума.
отр
отр
отр
отp
Блок 4 который работает по алгоритму, в соответствии с которым из трех сигналов (f1, x1, y1), (f2, х2, y2), (f, х, y) выделяется сигнал, имеющий максимальное значение целевой функции max [f1, f2, f], и формирует на своем выходе значение этого максимума и его координаты, т.е. искомое относительно лучшее в искомой локальной области решение.
Таким образом, в предложенной устройстве достигается требуемый технический результат, заключающийся в расширении функциональных возможностей, поскольку формируемый на его выходе сигнал может быть использован для определения координат точки с максимальным значением целевой функции в локальной области двумерного массива.