Устройство формирования начального плана поиска оптимального решения с использованием генетического алгоритма

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

Полезная модель относится к области обработки данных для специальных применений и может быть использовано, в частности, для формирования начального плана поиска оптимального решения с использованием генетического алгоритма.

Известно устройство, содержащее генераторы пилообразного напряжения, аналого-цифровые и цифро-аналоговые преобразователи, элементы ИЛИ, блоки памяти функций принадлежности, блоки определения минимума, блоки сравнения, блоки вычитания из единицы, регистры, счетчик и элементы задержки с соответствующими связями [SU 1791815, G06F 7/58, 1990].

Недостатком устройства являются относительно узкие функциональные возможности.

Известно устройство, содержащее n параллельных сумматоров, входы и выходы которых являются, соответственно, группой входов и группой выходов устройства, а также n блоков умножения на весовые коэффициенты, при этом, вход i-ого блока умножения на весовые коэффициенты (i=1N) соединен с выходом i-ого параллельного сумматора, а каждый из выходов j-ого блока умножения на весовые коэффициенты (j=1N) соединен с соответствующим ему входом взвешенного сигнала i-ого сумматора (i не=j) [А.В.Назаров, А.И.Лоскутов "Нейросетевые алгоритмы прогнозирования и оптимизации систем", Санкт-Петербург, "Наука и Техника", 2003 г., стр.231].

Недостатком устройства являются относительно узкие функциональные возможности.

Известно также устройство, содержащее N параллельных сумматоров, входы которых являются группой входов устройства, а также N блоков умножения на весовые коэффициенты, при этом, каждый из выходов j-ого блока умножения на весовые коэффициенты (j=1N) соединен с соответствующим ему входом взвешенного сигнала i-ого параллельного сумматора (i=1N, i не=j), а также N блоков сжатия отображения, причем, входы 1-ых блоков умножения на весовые коэффициенты (i=1N) соединены с выходами одноименных блоков сжатия отображения, входы которых соединены с выходами одноименных параллельных сумматоров, а выходы - являются группой выходов устройства [RU 45579, U1, H03М 7/14, 2005].

Кроме того, в этом техническом решении блоки сжатия отображения выполнены в виде функциональных преобразователей входного сигнала Х в выходной сигнал Y по закону Y=1/(1+exp(-X)).

Недостатком устройства является относительно узкие функциональные возможности.

Еще одним аналогом предлагаемого является устройство, содержащее блок выделения фрагментов изображения, выходы которого соединены с группой пороговых блоков, выходы которых через группу преобразователей соединены с группой сумматоров [Y.LeCun, L.Bottou, Y.Bengio, P.Haffner. Gradient-based learning applied to document recognition. Proceeding of the IEEE, November, 1998, p.23].

Недостатком устройства является относительно узкие функциональные возможности.

Наиболее близким по технической сущности к предлагаемому является устройство, содержащее блок выделения фрагментов изображения, выполненный в виде блока хранения массива пространственных векторов, взвешенных целевой функцией, блок формирования опорного плана поиска, формирователь особи-потомка, первый, второй и третий входы которого соединены, соответственно, с первым, вторым и третьим выходами блока формирования опорного плана поиска, а группа входов - объединена с группой входов блока формирования опорного плана поиска и соединена с группой выходов блока выделения фрагментов изображения, блок определения максимума, первый, второй и третий входы которого соединены, соответственно, с первым, вторым и третьим выходами формирователя особи-потомка, а также формирователь родительской пары, первый и второй выходы которого соединены, соответственно, с первым и вторым входами блока формирования опорного плана поиска, и формирователь рекомбинации, первый и второй входы которого соединены, соответственно с первым и вторым выходами формирователя родительской пары, а выход - соединен с третьим входом блока формирования опорного плана поиска [RU 60757, U1, G06F 19/00, 05.10.2006].

Недостатком устройства является относительно узкие функциональные возможности, обусловленные тем, что устройство в процессе функционирования позволяет сформировать опорный план для поиска наилучшего решения в случае двумерного массива, но не позволяет сформировать его для многомерного массива.

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

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

На чертеже представлена электрическая структурная схема устройства формирования начального плана поиска оптимального решения с использованием генетического алгоритма.

Устройство формирования начального плана поиска оптимального решения с использованием генетического алгоритма содержит блок 1 хранения массива пространственных векторов, взвешенных целевой функцией, и блок 2 формирования массива опорных планов, первый вход которого соединен с выходом блока 1 хранения массива пространственных векторов, взвешенных целевой функцией.

Кроме того, устройство формирования начального плана поиска оптимального решения с использованием генетического алгоритма содержит блок 3 хранения массива средств воздействия, выход которого соединен со вторым входом блока 2 формирования массива опорных планов, и последовательно соединенные блок 4 нормировки массива опорных планов поиска, блок 5 формирования нарастающих результатов воздействия и блок 6 формирования начальных точек воздействия.

Дополнительно устройство формирования начального плана поиска оптимального решения с использованием генетического алгоритма содержит блок 7 определения максимума, вход которого соединен с выходом блока 2 формирования массива опорных планов, а выход - соединен с входом блока 4 нормировки массива опорных планов поиска и с входом блока 4 нормировки массива опорных планов поиска.

Охарактеризованные на функциональном уровне блок 1 хранения массива пространственных векторов, взвешенных целевой функцией, блок 2 формирования массива опорных планов, блок 3 хранения массива средств воздействия, блок 4 нормировки массива опорных планов поиска, блок 5 формирования нарастающих результатов воздействия, блок 6 формирования начальных точек воздействия и блок 7 определения максимума могут быть выполнены в виде программируемых (настраиваемых) многофункциональных средств (специализированных средств вычислительной техники, миникомпьютеров, микропроцессоров и т.п.). Для подтверждения возможности выполнения такими средствами конкретных предписываемых им в составе данного устройства функции ниже при описании работы устройства приводятся сведения в виде алгоритма их работы или соответствующего математического выражения.

Работает устройство формирования начального плана поиска оптимального решения с использованием генетического алгоритма следующим образом.

В устройстве реализуется алгоритм формирования начального плана поиска оптимального решения с использованием генетического алгоритма для следующей проблемной ситуации.

На плоскости, которая условно разделена на элементарные участки с координатами [(x1, y1), (x2, y2), (хn, yn)], находятся объекты, каждый из которых характеризуется некоторым значением функции ценности F, заданной на элементах множества [(x1, y1), (х2, y2), (хn, yn)]. Предполагается, что на той же плоскости будут размещены средства воздействия на объекты. Каждое из средств воздействия способно нанести ущерб в общем случае всей совокупности находящихся на плоскости объектов в зависимости от точек их размещения. Оптимальным планом их размещения будет такой, при котором объектам будет нанесен максимальный суммарный ущерб находящимся на плоскости объектам. Этот план характеризуется соответствующей совокупностью координат точек их размещения, оптимальная из которых может быть найдена с использованием различных методов оптимизации, в том числе, основанных на генетическом алгоритме.

Практически для всех известных методик большую роль играет начальный план размещения средств, из которого путем улучшений формируется оптимальный или близкий к нему.

Определение начального плана производится следующим образом. В блоке 1 хранения массива пространственных векторов, взвешенных целевой функцией, хранится массив векторов, описывающих каждую точку пространства, элементами каждого из которых являются координата и значение функции F, заданной на элементах множества [(xj, yj), j=1n)], т.е. [(f1, x1, y1), (f2, x2, y2), (fn, xn, yn)].

В блоке 3 хранения массива средств воздействия хранятся параметры Xi каждого из средств воздействия, число которых равно m (i=1m). Элементы массива последовательно подаются в блок 2 формирования массива опорных планов, в котором для каждой точки [(x1, y1), (x2, y2),(хn, yn)] размещения средств воздействия определяется величина ущерба yij, который наносит i-oe средство воздействия, размещенное в j-ой точке плоскости с координатами (xj, yj). В блоке определения максимума определяется точка, для которой достигается максимальное значение ущерба по всем точкам пространства. Эта точка закрепляется за первым средством воздействия и информация о об этом фиксируется на выходе блока 2 и одновременно передается в блок 1 хранения массива пространственных векторов, взвешенных целевой функцией, в котором производится коррекция значений взвешенной функции F путем учета ущерба который может быть нанесен другим средством воздействия в различных точках пространства с учетом того, что одно из средств уже закреплено за соответствующей точкой. Этим самым удается учесть физическое уменьшение значения взвешенной функции F в соответствующей точке пространства, поскольку вклад последующего средства воздействия уменьшается при воздействии совместно с предыдущим.

Далее в блок 2 формирования массива опорных планов, в котором для каждой точки [(x1, y1), (x2, y2), (хn, yn)] размещения средств воздействия определяется величина ущерба yij, который наносит i-oe средство воздействия, размещенное в j-ой точке плоскости с координатами (xj, yj), подается второй и последующие элементы массива и описанные процессы повторяются для всех элементов массива.

Таким образом, на выходе блока 4 для каждого средства воздействия формируются значения ущерба, который оно наносит с учетом воздействия других средств из условия максимизации эффекта воздействия.

В блоке 4 нормировки массива опорных планов поиска величина ущерба yij, нормируется относительно суммарного ущерба для i-ого средства воздействия по всем точкам его размещения. Сумма этих нормированных величин для каждого средства воздействия равна единице, что позволяет условно рассматривать их как вероятности нанесения максимально возможного ущерба всей совокупности находящихся на плоскости объектов при размещении i-ого средства воздействия j-ой точке плоскости с координатами (xj, yj).

Эти нормированные величины для каждого из 1-х средств воздействия последовательно суммируются, начиная с первой точки, в результате чего на условной оси [01] формируются частные интервалы, длина каждого их которых соответствует вероятности нанесения максимально возможного ущерба всей совокупности находящихся на плоскости объектов при размещении i-ого средства воздействия между j-ой и (j+1)-ой точками на плоскости.

И, наконец, в блоке 6 формирования начальных точек воздействия производится формирование начального плана поиска оптимального решения, для чего используется процедура, присущая генетическому алгоритму, а именно - для каждого i-ого средства воздействия разыгрывается случайное число с равномерным распределение в интервале [01] и определяется, на какой частный интервал на условной оси [01] попадет это число. Номер интервала будет соответствовать номеру точки на плоскости, в которой следует разместить i-oe средство воздействия на начальном этапе поиска оптимального решения. Полная совокупность таких точек для всех средств воздействия определяет искомый начальный план поиска.

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

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