В классической диагностической задаче для линейных автоматов предполагается, что каждая выходная реакция в момент времени $$t$$ - это вектор $$\bar y(t)=[y_1(t), \dots, y_m(t)]'$$, координаты $$y_i(t)$$ которого представляют собой точные значения. Поскольку практически значения координат наблюдаемой реакции автомата получаются в результате измерений, они неизбежно содержат погрешности, размеры которых зависят от точности измерительных приборов. Поэтому более реальной по сравнению с классической задачей является
Решением интервальной
Понятно, что чем больше ширина интервалов в выходных векторах, тем сложнее найти начальное состояние автомата. Если же интервалы в выходных векторах полностью покрывают поле $$GF(p) $$, то нахождение начальных состояний становится невозможным. Такая ситуация вполне может иметь место при малых значениях $$p$$, поэтому далее предполагается, что $$p \ge 5$$.
Для решения
В классическом случае каждое состояние автомата любого сигма-множества $$A$$ -группы имеет единственного преемника в одном и только одном сигма-множестве преемника упомянутой $$A$$ -группы. Отсюда следует, что в классическом случае каждая $$A$$ -группа, связанная с любой ветвью диагностического дерева, содержит в своих сигма-множествах одно и то же суммарное число состояний, равное мощности множества допустимых начальных состояний автомата.
Построение преемника сигма-множества $$A$$ -группы по некоторому входному сигналу в интервальном диагностическом дереве будем осуществлять следующим образом. Сначала вычисляем все состояния-преемники этого сигма-множества по упомянутому входному сигналу и соответствующие "интервальные" реакции автомата. Каждая "интервальная" реакция ЛА заменяется множеством точных реакций, которое представляет собой все возможные комбинации из точных значений, принадлежащих соответствующему интервалу. Таким образом, каждому состоянию-преемнику будет соответствовать некоторое конечное множество точных реакций. Cостояния-преемники будут помещаться в одно и то же сигма-множество, если в соответствующих им множествах точных реакций есть совпадающие между собой. Это правило формирования сигма-множеств $$A$$ -группы следующего уровня может привести к тому, что одно сигма-множество предшествующего уровня в следующем уровне дерева попадает в несколько сигма-множеств. Таким образом, в двух новых сигма-множествах может находиться одно и то же состояние-преемник. Отсюда вытекает, что общее число состояний в преемнике $$A$$ -группы в интервальном диагностическом дереве может оказаться больше мощности множества допустимых начальных состояний автомата.
Что касается правил, по которым некоторая ветвь интервального диагностического дерева становится оконечной, то они остаются теми же, что и в классическом диагностическом дереве. Проиллюстрируем построение интервального диагностического дерева на примере.
Рассмотрим ЛА над полем $$GF(7) $$, заданный с помощью следующих характеристических матриц:
$$A= \left [ \begin {matrix} 214\\ 526\\ 301 \end {matrix} \right ], B= \left [ \begin {matrix} 3\\ 4\\ 1 \end {matrix} \right ], C= \left [ \begin {matrix} 503\\ 146 \end {matrix} \right ], D= \left [ \begin {matrix} 6\\ 1 \end {matrix} \right ] $$Пусть множество допустимых начальных состояний этого ЛА содержит два следующих состояния: $$[456]' [105]'$$. Классическое диагностическое дерево для рассматриваемого автомата представлено на рис.20.1. Над каждой $$A$$ -группой на этом рисунке в прямоугольнике помещена информация о состояниях-преемниках $$(\bar s)$$ и выходных реакциях $$(\bar y)$$. Ниже помещены сигма-множества (в фигурных скобках), составляющие $$A$$ -группу. Из этого рисунка следует, что рассматриваемый автомат имеет 7 диагностических последовательностей длины 1: $$u=0, u=1, \dots, u=6$$.
(рис 20.1) Теперь построим фрагменты интервального диагностического дерева (одну его ветвь для входного сигнала $$u=0$$ ) в предположении, что при измерении реакции ЛА по каждой координате выходного вектора может произойти ее искажение на одну единицу как в меньшую, так и в большую сторону. Этот фрагмент представлен на рис.20.2.
(рис 20.2) При переходах ЛА из состояний $$[456]', [105]'$$ в состояния $$[234]', [101]'$$ соответственно вычисляемые точные реакции есть $$[34]', [63]' $$. При наличии оговоренных выше погрешностей измерения эти точные реакции превращаются в интервальные реакции $$[[2,4]', [3,5]]', [[5,0], [2,4]]'$$. Каждую из этих реакций заменяем соответственно множеством всех возможных комбинаций величин из приведенных интервалов:
$$\left \{ \left [ \begin {matrix} 2\\ 3 \end {matrix} \right ], \left [ \begin {matrix} 2\\ 4 \end {matrix} \right ], \left [ \begin {matrix} 2\\ 5 \end {matrix} \right ], \left [ \begin {matrix} 3\\ 3 \end {matrix} \right ], \left [ \begin {matrix} 3\\ 4 \end {matrix} \right ], \left [ \begin {matrix} 3\\ 5 \end {matrix} \right ], \left [ \begin {matrix} 4\\ 3 \end {matrix} \right ], \left [ \begin {matrix} 4\\ 4 \end {matrix} \right ], \left [ \begin {matrix} 4\\ 5 \end {matrix} \right ] \right \} ,\\ \left \{ \left [ \begin {matrix} 5\\ 2 \end {matrix} \right ], \left [ \begin {matrix} 5\\ 3 \end {matrix} \right ], \left [ \begin {matrix} 5\\ 4 \end {matrix} \right ], \left [ \begin {matrix} 6\\ 2 \end {matrix} \right ], \left [ \begin {matrix} 6\\ 3 \end {matrix} \right ], \left [ \begin {matrix} 6\\ 4 \end {matrix} \right ], \left [ \begin {matrix} 0\\ 2 \end {matrix} \right ], \left [ \begin {matrix} 0\\ 3 \end {matrix} \right ], \left [ \begin {matrix} 0\\ 4 \end {matrix} \right ] \right \} $$С использованием этих множеств построим теперь сигма-множества $$A$$ -группы. Так, поскольку реакция $$[23]'$$ из первого множества не совпадает ни с одной реакцией из второго, то соответствующее ей состояние-преемник $$[234]'$$ образует простое, т. е. одноэлементное, сигма-множество. Аналогичная ситуация имеет место для всех остальных элементов обоих множеств. Следовательно, преемником множества допустимых начальных состояний является $$A$$ -группа, содержащая 18 одноэлементных сигма-множеств, среди которых по 9 штук содержит одно и то же состояние.
Вернемся теперь к интервальной диагностической задаче. Для нахождения неизвестного начального состояния $$\bar s(0)=[s_1(0), \dots, s_n(0)]'$$ по известной ДП $$\bar u(0), \bar u(1), \dots, \bar u(k)$$ и наблюдаемой в процессе проведения эксперимента с ЛА выходной последовательности $$\bar y(0), \bar y(1), \dots, \bar y(k)$$, сформируем следующую СЛАУ:
$$\begin {cases} C\bars(0)=\bar y(0)-D\bar u(0),\\ CA\bar s(0)=\bar y(1)-CB \bar u(0)-D\bar u(1),\\ ………………………………………………….\\ CA^k\bar s(0)=\bar y(k)-CA^{k-1}B\bar u(0)- \dots -CB\bar u(k-1)-D\bar u(k) \end {cases} $$Эта система получена на основе формулы полной реакции ЛА для $$t=\overline {0,k}$$.
Поскольку выходные реакции $$\bar y(0), \bar y(1)m \dots, \bar y(k)$$ представляют собой интервальные вектора, то правые части системы (20.2) также являются интервальными векторами, тогда как матрица системы (20.2) является точной.
В общем случае число уравнений в системе (20.2), которое обозначим через $$\nu$$, может не совпадать с числом неизвестных, равным размерности $$n$$ ЛА. Если $$\nu < n,$$ то, как известно из алгебры, общее решение такой системы представляется с использованием свободных переменных и матрица системы приводится к квадратной. Если $$\nu >n$$, то из факта существования у ЛА диагностической последовательности вытекает существование решения системы (20.2). Последнее означает, что ее ранг равен n и поэтому матрица системы и в этом случае может быть приведена к квадратной.
Исходя из сказанного, решение рассматриваемой интервальной
Представим такую систему в общем виде:
$$Ax=B$$где $$A=|a_{ij}|_{n \times n}$$ - матрица, элементами которой являются элементы поля $$GF(p), B=[B_1, \dots, B_n]'$$, а каждое $$B_i$$ является интервалом или мультиинтервалом (объединением нескольких интервалов).
Тривиальный способ нахождения всех решений системы (20.3) состоит в замене ее интервальной правой части всевозможными конкретными значениями из соответствующих интервалов и поиска решений получающихся при этом обычных систем линейных уравнений одним из известных методов. Однако такой способ является трудоемким, поскольку ведет к необходимости решения $$z$$ штук систем, где
$$z=w(B_1) \dots w(B_n)=\Pi_{i=1}^nw(B_i)$$Доказываемая ниже теорема позволяет значительно уменьшить трудоемкость нахождения всех решений системы (20.3).
Предварительно введем следующие обозначения:
$$\{e_k\}= \begin {cases} 0, если i \ne k, 1, если i=k \end {cases}, k=\overline {1,0}; i=\overline {1,n} ;\\ \underline B=[\underline B_1, \underline B_2, \dots \underline B_n]',$$где
$$\underline B_i=\alpha_i, \alpha_i \in B_i, \forall \beta_i \in B_i (\alpha \le \beta), i=\overline {1,n}$$Теорема 20.1. Пусть $$(\xi_1, \dots, \xi_n)'$$ есть решение системы
$$A \xi=\underline B$$а $$(\delta_1^{(k)}, \dots, \delta_n^{(k)})'$$ есть решения n штук систем
$$Ax=e_k, k=\overline {1,n}$$Тогда решение $$x=(x_1, \dots, x_n')$$ системы (20.3) имеет вид
$$x_j=\xi_j + \sum_{k=1}^n m_k \delta_j^{(k)}, j=\overline {1,n}$$где $$\underline B_k+m_k \in B_k$$ т. е. $$m_k$$ пробегают независимо все значения от 0 до $$p$$ -1, при этом из них точно $$w(B_k)$$
Доказательство. Рассмотрим $$i$$ -ю строку системы (20.3):
$$(Ax)_i=\sum_{j=1}^n a_{ij}x_j=\sum_{j=1}^n a_{ij} \left ( \xi_j +\sum_{k=1}^n m_k \delta_j^{(k)} \right )= \sum_{j=1}^n \left (a_{ij} \xi_j+ \sum_{k=1}^n m_k \delta_j^{(k)} \right )\\ =\sum_{j=1}^n a_{ij} \xi_j+\sum_{j=1}^n \sum_{k=1}^n m_k \delta_j^{(k)}= \underline B_i +\sum_{k=1}^n m_k \sum_{j=1}^n a_{ij}\delta_j^{(k)}= \underline B_1+m_i,$$поскольку
$$\sum_{j=1}^{n}a_{ij}\delta_j^{(k)}= \begin {cases} 0, если i \ne k,\\ 1, если i=k \end {cases} $$Таким образом, $$(Ax)_i=\underline B_i +m_i$$, a $$\underline B_i+m_i \in B_i$$, следовательно, $$(Ax)_i=B_i$$, откуда и вытекает справедливость теоремы.
Из этой теоремы следует, что в действительности для построения всех решений системы (20.3) необходимо решить только $$(n+1)$$ систему линейных уравнений, а не $$w(B_1) \dots w(B_n)$$ систем, как это было в тривиальном способе.
В качестве примера рассмотрим применение этого метода для решения СЛАУ с точной матрицей и интервальной правой частью.
Пусть $$p = 37$$ и необходимо найти все решения системы
$$\begin {cases} 3x_1+5x_2=[30,36],\\ 5x_1+2x_2=[20,30] \end {cases}$$Вначале рассмотрим систему вида (20.4):
$$\begin {cases} 3x_1+5x_2=30,\\ 5x_1+2x_2=20 \end {cases}$$Решение этой системы есть пара $$(\xi_1, \xi_2)=(6,32)$$.
Теперь рассмотрим две системы вида (20.5):
$$\begin {cases} 3 \delta_1^{(1)}+5 \delta_1^{(2)}=1,\\ 5\delta_1^{(1)}+2\delta_2^{(1)}=0, \end {cases} \begin {cases} 3\delta_1^{(2)}+5\delta_2^{(2)}=0,\\ 5\delta_1^{(2)}+2\delta_2^{(2)}=1 \end {cases}$$Их решениями являются $$\delta ^{(1)}=(\delta_1^{(1)}, \delta_2^{(1)})=(33, 10), \delta^{(2)}=(\delta_1^{(2)}, \delta_2^{(2)})=(10,31)$$.
Тогда все множество решений системы таково:
$$x_1=\xi_1+i\delta_1^{(1)}+j\delta_1^{(2)}, x_2=\xi_2+i\delta_2^{(1)}+j\delta_2^{(2)},$$где
Таким образом, получаем:
$$x_1=6+33i+10j, где 0 \le i \le 6, 0 \le j \le 10$$Все эти решения представлены в следующей таблице:
| $$b_1\b_2$$ | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 30 | (6, 32 | (16, 26) | (26, 20) | (36, 14) | (9, 8) | (19, 2) | (29, 33) | (2, 27) | (12, 21) | (22, 15) | (32, 9) | |
| 31 | (2, 5) | (12, 36) | (22, 30) | (32, 24) | (5, 18) | (15, 12) | (25, 6) | (35, 0) | (8, 31) | (18, 25) | (28, 19) | |
| 32 | (35, 15) | (8, 9) | (18, 3) | (28, 34) | (1, 28) | (11, 22) | (21, 16) | (31, 10) | (4, 4) | (14, 35) | (24, 29) | |
| 33 | (31, 25) | (4, 19) | (14, 13) | (24, 7) | (34, 1) | (7, 32) | (17, 26) | (27, 20) | (0, 14) | (10, 8) | (20, 2) | |
| 34 | (27, 35) | (0, 29) | (10, 23) | (20, 17) | (30, 11) | (3, 5) | (13, 36) | (23, 30) | (33, 24) | (6, 18) | (16, 12) | |
| 35 | (23, 8) | (33, 2) | (6, 33) | (16, 27) | (26, 21) | (36, 15) | (9, 9) | (19, 3) | (29, 34) | (2, 28) | (12, 22) | |
| 36 | (19, 18) | (29, 12) | (2, 6) | (12, 0) | (22, 31) | (32, 25) | (5, 19) | (15, 13) | (25, 7) | (35, 1) | (8, 32) |
Таким образом, в рассмотренном примере предлагаемый метод отыскания всех решений СЛАУ потребовал решения 3 систем линейных уравнений вместо 77 при использовании тривиального метода.
Теперь проиллюстрируем применение метода решения СЛАУ на конкретной диагностической задаче.
Рассмотрим ЛА над полем $$GF(7)$$, заданный с помощью характеристических матриц, которые приведены выше в этом разделе. Пусть множество допустимых начальных состояний содержит 4 состояния:
$$\{[203]', [001]', [456]', [105]'\}$$Диагностическая последовательность для заданного множества допустимых начальных состояний, построенная с использованием описанного выше диагностического дерева, такова: $$u(0)=[0], u(1)=[0], u(2)=[0]$$. Предположим, что измерения выходной реакции ЛА на эту диагностическую последовательность дали следующие результаты:
$$y(0)= \left [ \begin {matrix} [5,6]\\ [2,4] \end {matrix} \right ], y(1)= \left [ \begin {matrix} [0,2]\\ [0,1] \end {matrix} \right ], y(2)= \left [ \begin {matrix} [0,1]\\ [3,5] \end {matrix} \right ]$$Заметим, что эти результаты получены в несколько иных предположениях об искажениях при измерении, чем были сделаны при построении фрагмента интервального диагностического дерева на рис.20.2.
Для решения интервальной
Заметим, что для нахождения решения этой интервальной системы уравнений тривиальным способом необходимо решить 216 систем.
Для приведенной системы количество неизвестных равно 3, а число уравнений равно 6. Приводя матрицу к квадратной, получаем следующую систему:
$$\left [ \begin {matrix} 503\\ 146\\ 552 \end {matrix} \right ] \left [ \begin {matrix} s_1(0)\\ s_2(0)\\ s_3(0) \end {matrix} \right ]= \left [ \begin {matrix} [5,6]\\ [2,4]\\ [0,2] \end {matrix} \right ]$$Обозначим матрицу полученной системы (20.8) через $$F$$. В соответствии с описанным выше методом необходимо решить следующие 4
Решая их, получаем следующие результаты:
$$(\xi_1, \xi_2, \xi_3)=(0,0,0)\\ (\delta_1^{(1)}, \delta_2^{(1)}, \delta_3^{(1)})=(1,0,1)\\ (\delta_1^{(2)}, \delta_2^{(2)}, \delta_3^{(3)})=(6,5,4),\\ (\delta_1{(3)}, \delta_2^{(3)}, \delta_3^{(3)})=(6,5,1)$$Теперь в соответствии с формулой (20.6) выпишем решение системы (20.7) в параметрическом виде:
$$s_1(0)=\xi_1+i_1 \delta_1^{(1)}+i_2 \delta_1^{(2)}+i_3\delta_1^{(3)},\\ s_2(0)=\xi_2+i_1\delta_2^{(1)}+i_2\delta_2^{(2)}+i_3\delta_2^{(3)},\\ s_3(0)=\xi_3+i_1\delta_3^{(1)}+i_2\delta_3^{(2)}+i_3\delta_3^{(3)}$$где $$5 \le i_1 \le 6, 2 \le i_2 \le 4, 0 \le i_3 \le 2$$
Таким образом, получаем 18 решений системы уравнений (20.8), представленных в формате $$s(0)=[s_1(0), s_2(0), s_3(0)]'$$:
$$[336]', [120]', [611]', [213]', [004]', [565]', [160]', [651]', [442]',$$ $$[430]', [221]', [012]', [314]', [105]', [666]', [261]', [052]', [543].$$Полученные решения интервальной системы уравнений (20.8) являются "кандидатами" в решение интервальной системы уравнений (20.7). Подставляя их в систему (20.7), можно убедиться, что только одно из этих 18 решений, $$s(0)=[105]'$$, удовлетворяет всем уравнениям (20.7). Поскольку это решение принадлежит множеству допустимых начальных состояний рассматриваемого ЛА, то оно и есть искомое решение интервальной
В предыдущем разделе было указано, что мощность множества всех решений интервальной системы уравнений с квадратной матрицей равна величине $$z=\Pi_{i=1}^{n}w(B_i)$$. Из формулы видно, что эта мощность быстро растет с ростом ширины интервалов в правой части системы (20.3). Даже при сравнительно небольших значениях упомянутых параметров величина $$z$$ может быть столь велика, что множество всех решений системы становится практически необозримым. В [24] отмечается, что это свойство является атрибутом труднорешаемой задачи, причем не менее важным, чем экспоненциальное время ее решения. По этой причине, если мощность множества всех "кандидатов" в решение системы очень велика, возникает проблема нахождения среди них единственного решения интервальной
Простейшим способом поиска какого-либо решения рассматриваемой задачи является перебор всех возможных допустимых начальных состояний ЛА и проверка того, удовлетворяют ли эти состояния системе линейных уравнений (20.3). Поскольку для ЛА, заданного над полем $$GF(p) $$, число таких всевозможных начальных состояний $$p^n$$, где $$n$$ - размерность ЛА, то уже при $$n = 30$$ и $$p=2$$ число состояний, подлежащих проверке, превышает $$10^9$$. Учитывая, что
Накопленный опыт практического решения задач переборного типа показал достаточно высокую эффективность применения
Заметим, что используемые далее, но не определенные здесь понятия, связанные с
Принцип работы
Применение
В данной работе используется простой
Остановимся подробнее на отмеченных нами узловых точках построения генетического алгоритма. Обратимся вначале к способу кодирования решения в рассматриваемой интервальной диагностической задаче.
Большая часть существующей теории
Каждому допустимому решению $$s$$ сопоставим битовую строку, представляющую собой хромосому. Сопоставление осуществим следующим образом: вектору $$s=[s_1, s_2, \dots, s_n]'$$ ' поставим в соответствие число в двоичной системе, которое равно числу $$s_1, s_2, \dots, s_n$$ в системе счисления с основанием $$p$$. Такая схема сопоставления является взаимно-однозначной, что позволяет проводить как кодирование, так и декодирование
Заметим, что при $$p=2$$ используются системы счисления по основанию 2 и перевод производить не требуется. Если $$p>2$$, то число бит, необходимых для представления решения, отличается от $$n$$ в сторону увеличения.
При таком способе кодирования длина
Пример 1.
Пусть $$p=2, n=4$$, тогда $$l = 4$$. Решению $$s=[1, 0, 1, 1]' $$ соответствует
Пусть $$p=3, n=4$$, тогда $$l = 7$$. Решению $$s=[1, 0, 2, 1]' $$ соответствует
Следующим важным моментом при реализации генетического алгоритма является определение целевой функции, которая "направляет" поиск решения.
Целевая функция используется для оценивания приспособленности
Пусть $$s=[s_1, s_2, \dots, s_N]'$$ - решение, которое необходимо оценить. Так как это решение представляет собой предполагаемое начальное состояние, то получаем $$s(0)=s$$. Осуществляя подстановку $$s(t)$$ в систему уравнений (1.1)-(1.2) при $$t=\overline {0, t_{max}}$$ где $$t_{max}+1$$ равно длине диагностической последовательности, получим набор из $$t_{max}+1$$ выходных векторов размерности $$m: y_c(0), y_c (1), \dots, y_c(t_{max})$$.
Целевую функцию определим следующим образом:
$$Q(s)=\sum_{t=0}^{t_{max}}Q_t(y_c(t))$$где
$$Q_t(y_c(t))= \begin {cases} 0, если\ y_c(t) \in y(t),\\ \sum_{t=1}^n min (|\bar y(t) - y_c(t)|, | \underline {y_i}(t)-y_c(t)|), если\ y_c (t) \notin y(t) \end {cases}$$При таком выборе целевая функция будет неотрицательной во всей области допустимых значений и принимать значение 0 лишь на решениях интервальной
Однако в классическом понимании целевой функции как функции приспособленности необходимо, чтобы более приспособленные особи оценивались выше, чем менее приспособленные. Этого легко достичь, если произвести нормализацию целевой функции и обратить ее:
$$Q(s)=\sum_{t=0}^{t_{max}}Q_t'(y_c(t))$$где
$$Q_t'(y_c(t))=1-\frac {Q_t(y_c(t))}{n(p-1)}$$Таким образом, целевая функция $$Q(s)$$ будет принимать значения в диапазоне от 0 до 1. При этом большему значению целевой функции соответствует большая степень приспособленности
Теперь коснемся вопроса определения вероятностей применения операторов ПГА. Как же их определять? На этот вопрос пока нет простого и однозначного ответа. В докторской диссертации де Джонга (1975), посвященной исследованию
Размер популяции и максимальное количество поколений определяют объем
В ходе исследования поставленной интервальной
SGA-C реализует простой SGA-C позволяет исследователю сделать настройку для решения его специфических задач с помощью набора функций в файле app.c. Для решения поставленной интервальной
objfunc (): производит вычисление функции $$Q(s)$$ по формулам (20.10)-(20.12).app_report (): производит печать всех найденных в ходе работы программы решений и их количества.chrom2matrix (): производит декодирование matrix_sum (), matrix_mult (): реализуют операции сложения и умножения матриц.Эта программа для нахождения решения интервальной
Рассмотрим ряд примеров решения сформулированной
Пример 2.
Решим интервальную
Согласно описанной выше рекомендации, вероятность оператора кроссинговера $$p_c$$ положим равной 0.1, а вероятность оператора
Как было сказано выше, вероятности операторов играют большую роль при работе генетического алгоритма. Чтобы проиллюстрировать это, данная задача решалась при разных вероятностях оператора скрещивания ( $$p_c$$ ) и оператора
Из этой таблицы можно сделать следующие выводы:
| $$p_c \p_m$$ | 0.00 | 0.01 | 0.02 | 0.03 | 0.04 | 0.05 | 0.06 | 0.07 | 0.08 | 0.09 | 0.10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0.00 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 |
| 0.05 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 |
| 0.10 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
| 0.15 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 0.20 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 0.25 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 0.30 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 0.35 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 0.40 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 0.45 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 0.50 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
Пример 3.
Рассмотрим ЛА из примера 1. Входные векторы оставим без изменений, а выходные векторы сделаем точными, т. е. рассмотрим случай вырожденных интервалов:
$$y(0)= \left [ \begin {matrix} [3,3]\\ [4,4] \end {matrix} \right ], y(1)= \left [ \begin {matrix} [1,1]\\ [3,3] \end {matrix} \right ], y(2)= \left [ \begin {matrix} [5,5]\\ [5,5] \end {matrix} \right ] $$Заметим, что хотя выходные векторы заданы с помощью интервалов, однако представляют собой векторы с точными значениями. Таким образом, данный пример является примером классической
Используя таблицу из примера 2, положим вероятность оператора кроссинговера $$p_c$$ равной 0.15, а вероятность оператора
Таким образом, пример 3 иллюстрирует тот факт, что
Главными преимуществами генетического алгоритма при решении разнообразных задач являются небольшой объем используемой памяти и высокая скорость получения решения. Например, при $$p=2, n=30$$, программа с применением ГА нашла решение менее чем за 1 секунду своей работы (был взят компьютер с процессором Celeron 900 MHz). Другая программа, которая осуществляла поиск решения полным перебором, это же решение нашла только через несколько десятков часов при использовании того же компьютера. Таким образом, генетический подход к решению интервальной
В классической диагностической задаче для линейных автоматов предполагается, что каждая выходная реакция в момент времени $$t$$ - это вектор $$\bar y(t)=[y_1(t), \dots, y_m(t)]'$$, координаты $$y_i(t)$$ которого представляют собой точные значения. Поскольку практически значения координат наблюдаемой реакции автомата получаются в результате измерений, они неизбежно содержат погрешности, размеры которых зависят от точности измерительных приборов. Поэтому более реальной по сравнению с классической задачей является
Решением интервальной
Понятно, что чем больше ширина интервалов в выходных векторах, тем сложнее найти начальное состояние автомата. Если же интервалы в выходных векторах полностью покрывают поле $$GF(p) $$, то нахождение начальных состояний становится невозможным. Такая ситуация вполне может иметь место при малых значениях $$p$$, поэтому далее предполагается, что $$p \ge 5$$.
Для решения
В классическом случае каждое состояние автомата любого сигма-множества $$A$$ -группы имеет единственного преемника в одном и только одном сигма-множестве преемника упомянутой $$A$$ -группы. Отсюда следует, что в классическом случае каждая $$A$$ -группа, связанная с любой ветвью диагностического дерева, содержит в своих сигма-множествах одно и то же суммарное число состояний, равное мощности множества допустимых начальных состояний автомата.
Построение преемника сигма-множества $$A$$ -группы по некоторому входному сигналу в интервальном диагностическом дереве будем осуществлять следующим образом. Сначала вычисляем все состояния-преемники этого сигма-множества по упомянутому входному сигналу и соответствующие "интервальные" реакции автомата. Каждая "интервальная" реакция ЛА заменяется множеством точных реакций, которое представляет собой все возможные комбинации из точных значений, принадлежащих соответствующему интервалу. Таким образом, каждому состоянию-преемнику будет соответствовать некоторое конечное множество точных реакций. Cостояния-преемники будут помещаться в одно и то же сигма-множество, если в соответствующих им множествах точных реакций есть совпадающие между собой. Это правило формирования сигма-множеств $$A$$ -группы следующего уровня может привести к тому, что одно сигма-множество предшествующего уровня в следующем уровне дерева попадает в несколько сигма-множеств. Таким образом, в двух новых сигма-множествах может находиться одно и то же состояние-преемник. Отсюда вытекает, что общее число состояний в преемнике $$A$$ -группы в интервальном диагностическом дереве может оказаться больше мощности множества допустимых начальных состояний автомата.
Что касается правил, по которым некоторая ветвь интервального диагностического дерева становится оконечной, то они остаются теми же, что и в классическом диагностическом дереве. Проиллюстрируем построение интервального диагностического дерева на примере.
Рассмотрим ЛА над полем $$GF(7) $$, заданный с помощью следующих характеристических матриц:
$$A= \left [ \begin {matrix} 214\\ 526\\ 301 \end {matrix} \right ], B= \left [ \begin {matrix} 3\\ 4\\ 1 \end {matrix} \right ], C= \left [ \begin {matrix} 503\\ 146 \end {matrix} \right ], D= \left [ \begin {matrix} 6\\ 1 \end {matrix} \right ] $$Пусть множество допустимых начальных состояний этого ЛА содержит два следующих состояния: $$[456]' [105]'$$. Классическое диагностическое дерево для рассматриваемого автомата представлено на рис.20.1. Над каждой $$A$$ -группой на этом рисунке в прямоугольнике помещена информация о состояниях-преемниках $$(\bar s)$$ и выходных реакциях $$(\bar y)$$. Ниже помещены сигма-множества (в фигурных скобках), составляющие $$A$$ -группу. Из этого рисунка следует, что рассматриваемый автомат имеет 7 диагностических последовательностей длины 1: $$u=0, u=1, \dots, u=6$$.
(рис 20.1) Теперь построим фрагменты интервального диагностического дерева (одну его ветвь для входного сигнала $$u=0$$ ) в предположении, что при измерении реакции ЛА по каждой координате выходного вектора может произойти ее искажение на одну единицу как в меньшую, так и в большую сторону. Этот фрагмент представлен на рис.20.2.
(рис 20.2) При переходах ЛА из состояний $$[456]', [105]'$$ в состояния $$[234]', [101]'$$ соответственно вычисляемые точные реакции есть $$[34]', [63]' $$. При наличии оговоренных выше погрешностей измерения эти точные реакции превращаются в интервальные реакции $$[[2,4]', [3,5]]', [[5,0], [2,4]]'$$. Каждую из этих реакций заменяем соответственно множеством всех возможных комбинаций величин из приведенных интервалов:
$$\left \{ \left [ \begin {matrix} 2\\ 3 \end {matrix} \right ], \left [ \begin {matrix} 2\\ 4 \end {matrix} \right ], \left [ \begin {matrix} 2\\ 5 \end {matrix} \right ], \left [ \begin {matrix} 3\\ 3 \end {matrix} \right ], \left [ \begin {matrix} 3\\ 4 \end {matrix} \right ], \left [ \begin {matrix} 3\\ 5 \end {matrix} \right ], \left [ \begin {matrix} 4\\ 3 \end {matrix} \right ], \left [ \begin {matrix} 4\\ 4 \end {matrix} \right ], \left [ \begin {matrix} 4\\ 5 \end {matrix} \right ] \right \} ,\\ \left \{ \left [ \begin {matrix} 5\\ 2 \end {matrix} \right ], \left [ \begin {matrix} 5\\ 3 \end {matrix} \right ], \left [ \begin {matrix} 5\\ 4 \end {matrix} \right ], \left [ \begin {matrix} 6\\ 2 \end {matrix} \right ], \left [ \begin {matrix} 6\\ 3 \end {matrix} \right ], \left [ \begin {matrix} 6\\ 4 \end {matrix} \right ], \left [ \begin {matrix} 0\\ 2 \end {matrix} \right ], \left [ \begin {matrix} 0\\ 3 \end {matrix} \right ], \left [ \begin {matrix} 0\\ 4 \end {matrix} \right ] \right \} $$С использованием этих множеств построим теперь сигма-множества $$A$$ -группы. Так, поскольку реакция $$[23]'$$ из первого множества не совпадает ни с одной реакцией из второго, то соответствующее ей состояние-преемник $$[234]'$$ образует простое, т. е. одноэлементное, сигма-множество. Аналогичная ситуация имеет место для всех остальных элементов обоих множеств. Следовательно, преемником множества допустимых начальных состояний является $$A$$ -группа, содержащая 18 одноэлементных сигма-множеств, среди которых по 9 штук содержит одно и то же состояние.
Вернемся теперь к интервальной диагностической задаче. Для нахождения неизвестного начального состояния $$\bar s(0)=[s_1(0), \dots, s_n(0)]'$$ по известной ДП $$\bar u(0), \bar u(1), \dots, \bar u(k)$$ и наблюдаемой в процессе проведения эксперимента с ЛА выходной последовательности $$\bar y(0), \bar y(1), \dots, \bar y(k)$$, сформируем следующую СЛАУ:
$$\begin {cases} C\bars(0)=\bar y(0)-D\bar u(0),\\ CA\bar s(0)=\bar y(1)-CB \bar u(0)-D\bar u(1),\\ ………………………………………………….\\ CA^k\bar s(0)=\bar y(k)-CA^{k-1}B\bar u(0)- \dots -CB\bar u(k-1)-D\bar u(k) \end {cases} $$Эта система получена на основе формулы полной реакции ЛА для $$t=\overline {0,k}$$.
Поскольку выходные реакции $$\bar y(0), \bar y(1)m \dots, \bar y(k)$$ представляют собой интервальные вектора, то правые части системы (20.2) также являются интервальными векторами, тогда как матрица системы (20.2) является точной.
В общем случае число уравнений в системе (20.2), которое обозначим через $$\nu$$, может не совпадать с числом неизвестных, равным размерности $$n$$ ЛА. Если $$\nu < n,$$ то, как известно из алгебры, общее решение такой системы представляется с использованием свободных переменных и матрица системы приводится к квадратной. Если $$\nu >n$$, то из факта существования у ЛА диагностической последовательности вытекает существование решения системы (20.2). Последнее означает, что ее ранг равен n и поэтому матрица системы и в этом случае может быть приведена к квадратной.
Исходя из сказанного, решение рассматриваемой интервальной
Представим такую систему в общем виде:
$$Ax=B$$где $$A=|a_{ij}|_{n \times n}$$ - матрица, элементами которой являются элементы поля $$GF(p), B=[B_1, \dots, B_n]'$$, а каждое $$B_i$$ является интервалом или мультиинтервалом (объединением нескольких интервалов).
Тривиальный способ нахождения всех решений системы (20.3) состоит в замене ее интервальной правой части всевозможными конкретными значениями из соответствующих интервалов и поиска решений получающихся при этом обычных систем линейных уравнений одним из известных методов. Однако такой способ является трудоемким, поскольку ведет к необходимости решения $$z$$ штук систем, где
$$z=w(B_1) \dots w(B_n)=\Pi_{i=1}^nw(B_i)$$Доказываемая ниже теорема позволяет значительно уменьшить трудоемкость нахождения всех решений системы (20.3).
Предварительно введем следующие обозначения:
$$\{e_k\}= \begin {cases} 0, если i \ne k, 1, если i=k \end {cases}, k=\overline {1,0}; i=\overline {1,n} ;\\ \underline B=[\underline B_1, \underline B_2, \dots \underline B_n]',$$где
$$\underline B_i=\alpha_i, \alpha_i \in B_i, \forall \beta_i \in B_i (\alpha \le \beta), i=\overline {1,n}$$Теорема 20.1. Пусть $$(\xi_1, \dots, \xi_n)'$$ есть решение системы
$$A \xi=\underline B$$а $$(\delta_1^{(k)}, \dots, \delta_n^{(k)})'$$ есть решения n штук систем
$$Ax=e_k, k=\overline {1,n}$$Тогда решение $$x=(x_1, \dots, x_n')$$ системы (20.3) имеет вид
$$x_j=\xi_j + \sum_{k=1}^n m_k \delta_j^{(k)}, j=\overline {1,n}$$где $$\underline B_k+m_k \in B_k$$ т. е. $$m_k$$ пробегают независимо все значения от 0 до $$p$$ -1, при этом из них точно $$w(B_k)$$
Доказательство. Рассмотрим $$i$$ -ю строку системы (20.3):
$$(Ax)_i=\sum_{j=1}^n a_{ij}x_j=\sum_{j=1}^n a_{ij} \left ( \xi_j +\sum_{k=1}^n m_k \delta_j^{(k)} \right )= \sum_{j=1}^n \left (a_{ij} \xi_j+ \sum_{k=1}^n m_k \delta_j^{(k)} \right )\\ =\sum_{j=1}^n a_{ij} \xi_j+\sum_{j=1}^n \sum_{k=1}^n m_k \delta_j^{(k)}= \underline B_i +\sum_{k=1}^n m_k \sum_{j=1}^n a_{ij}\delta_j^{(k)}= \underline B_1+m_i,$$поскольку
$$\sum_{j=1}^{n}a_{ij}\delta_j^{(k)}= \begin {cases} 0, если i \ne k,\\ 1, если i=k \end {cases} $$Таким образом, $$(Ax)_i=\underline B_i +m_i$$, a $$\underline B_i+m_i \in B_i$$, следовательно, $$(Ax)_i=B_i$$, откуда и вытекает справедливость теоремы.
Из этой теоремы следует, что в действительности для построения всех решений системы (20.3) необходимо решить только $$(n+1)$$ систему линейных уравнений, а не $$w(B_1) \dots w(B_n)$$ систем, как это было в тривиальном способе.
В качестве примера рассмотрим применение этого метода для решения СЛАУ с точной матрицей и интервальной правой частью.
Пусть $$p = 37$$ и необходимо найти все решения системы
$$\begin {cases} 3x_1+5x_2=[30,36],\\ 5x_1+2x_2=[20,30] \end {cases}$$Вначале рассмотрим систему вида (20.4):
$$\begin {cases} 3x_1+5x_2=30,\\ 5x_1+2x_2=20 \end {cases}$$Решение этой системы есть пара $$(\xi_1, \xi_2)=(6,32)$$.
Теперь рассмотрим две системы вида (20.5):
$$\begin {cases} 3 \delta_1^{(1)}+5 \delta_1^{(2)}=1,\\ 5\delta_1^{(1)}+2\delta_2^{(1)}=0, \end {cases} \begin {cases} 3\delta_1^{(2)}+5\delta_2^{(2)}=0,\\ 5\delta_1^{(2)}+2\delta_2^{(2)}=1 \end {cases}$$Их решениями являются $$\delta ^{(1)}=(\delta_1^{(1)}, \delta_2^{(1)})=(33, 10), \delta^{(2)}=(\delta_1^{(2)}, \delta_2^{(2)})=(10,31)$$.
Тогда все множество решений системы таково:
$$x_1=\xi_1+i\delta_1^{(1)}+j\delta_1^{(2)}, x_2=\xi_2+i\delta_2^{(1)}+j\delta_2^{(2)},$$где
Таким образом, получаем:
$$x_1=6+33i+10j, где 0 \le i \le 6, 0 \le j \le 10$$Все эти решения представлены в следующей таблице:
| $$b_1\b_2$$ | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 30 | (6, 32 | (16, 26) | (26, 20) | (36, 14) | (9, 8) | (19, 2) | (29, 33) | (2, 27) | (12, 21) | (22, 15) | (32, 9) | |
| 31 | (2, 5) | (12, 36) | (22, 30) | (32, 24) | (5, 18) | (15, 12) | (25, 6) | (35, 0) | (8, 31) | (18, 25) | (28, 19) | |
| 32 | (35, 15) | (8, 9) | (18, 3) | (28, 34) | (1, 28) | (11, 22) | (21, 16) | (31, 10) | (4, 4) | (14, 35) | (24, 29) | |
| 33 | (31, 25) | (4, 19) | (14, 13) | (24, 7) | (34, 1) | (7, 32) | (17, 26) | (27, 20) | (0, 14) | (10, 8) | (20, 2) | |
| 34 | (27, 35) | (0, 29) | (10, 23) | (20, 17) | (30, 11) | (3, 5) | (13, 36) | (23, 30) | (33, 24) | (6, 18) | (16, 12) | |
| 35 | (23, 8) | (33, 2) | (6, 33) | (16, 27) | (26, 21) | (36, 15) | (9, 9) | (19, 3) | (29, 34) | (2, 28) | (12, 22) | |
| 36 | (19, 18) | (29, 12) | (2, 6) | (12, 0) | (22, 31) | (32, 25) | (5, 19) | (15, 13) | (25, 7) | (35, 1) | (8, 32) |
Таким образом, в рассмотренном примере предлагаемый метод отыскания всех решений СЛАУ потребовал решения 3 систем линейных уравнений вместо 77 при использовании тривиального метода.
Теперь проиллюстрируем применение метода решения СЛАУ на конкретной диагностической задаче.
Рассмотрим ЛА над полем $$GF(7)$$, заданный с помощью характеристических матриц, которые приведены выше в этом разделе. Пусть множество допустимых начальных состояний содержит 4 состояния:
$$\{[203]', [001]', [456]', [105]'\}$$Диагностическая последовательность для заданного множества допустимых начальных состояний, построенная с использованием описанного выше диагностического дерева, такова: $$u(0)=[0], u(1)=[0], u(2)=[0]$$. Предположим, что измерения выходной реакции ЛА на эту диагностическую последовательность дали следующие результаты:
$$y(0)= \left [ \begin {matrix} [5,6]\\ [2,4] \end {matrix} \right ], y(1)= \left [ \begin {matrix} [0,2]\\ [0,1] \end {matrix} \right ], y(2)= \left [ \begin {matrix} [0,1]\\ [3,5] \end {matrix} \right ]$$Заметим, что эти результаты получены в несколько иных предположениях об искажениях при измерении, чем были сделаны при построении фрагмента интервального диагностического дерева на рис.20.2.
Для решения интервальной
Заметим, что для нахождения решения этой интервальной системы уравнений тривиальным способом необходимо решить 216 систем.
Для приведенной системы количество неизвестных равно 3, а число уравнений равно 6. Приводя матрицу к квадратной, получаем следующую систему:
$$\left [ \begin {matrix} 503\\ 146\\ 552 \end {matrix} \right ] \left [ \begin {matrix} s_1(0)\\ s_2(0)\\ s_3(0) \end {matrix} \right ]= \left [ \begin {matrix} [5,6]\\ [2,4]\\ [0,2] \end {matrix} \right ]$$Обозначим матрицу полученной системы (20.8) через $$F$$. В соответствии с описанным выше методом необходимо решить следующие 4
Решая их, получаем следующие результаты:
$$(\xi_1, \xi_2, \xi_3)=(0,0,0)\\ (\delta_1^{(1)}, \delta_2^{(1)}, \delta_3^{(1)})=(1,0,1)\\ (\delta_1^{(2)}, \delta_2^{(2)}, \delta_3^{(3)})=(6,5,4),\\ (\delta_1{(3)}, \delta_2^{(3)}, \delta_3^{(3)})=(6,5,1)$$Теперь в соответствии с формулой (20.6) выпишем решение системы (20.7) в параметрическом виде:
$$s_1(0)=\xi_1+i_1 \delta_1^{(1)}+i_2 \delta_1^{(2)}+i_3\delta_1^{(3)},\\ s_2(0)=\xi_2+i_1\delta_2^{(1)}+i_2\delta_2^{(2)}+i_3\delta_2^{(3)},\\ s_3(0)=\xi_3+i_1\delta_3^{(1)}+i_2\delta_3^{(2)}+i_3\delta_3^{(3)}$$где $$5 \le i_1 \le 6, 2 \le i_2 \le 4, 0 \le i_3 \le 2$$
Таким образом, получаем 18 решений системы уравнений (20.8), представленных в формате $$s(0)=[s_1(0), s_2(0), s_3(0)]'$$:
$$[336]', [120]', [611]', [213]', [004]', [565]', [160]', [651]', [442]',$$ $$[430]', [221]', [012]', [314]', [105]', [666]', [261]', [052]', [543].$$Полученные решения интервальной системы уравнений (20.8) являются "кандидатами" в решение интервальной системы уравнений (20.7). Подставляя их в систему (20.7), можно убедиться, что только одно из этих 18 решений, $$s(0)=[105]'$$, удовлетворяет всем уравнениям (20.7). Поскольку это решение принадлежит множеству допустимых начальных состояний рассматриваемого ЛА, то оно и есть искомое решение интервальной
В предыдущем разделе было указано, что мощность множества всех решений интервальной системы уравнений с квадратной матрицей равна величине $$z=\Pi_{i=1}^{n}w(B_i)$$. Из формулы видно, что эта мощность быстро растет с ростом ширины интервалов в правой части системы (20.3). Даже при сравнительно небольших значениях упомянутых параметров величина $$z$$ может быть столь велика, что множество всех решений системы становится практически необозримым. В [24] отмечается, что это свойство является атрибутом труднорешаемой задачи, причем не менее важным, чем экспоненциальное время ее решения. По этой причине, если мощность множества всех "кандидатов" в решение системы очень велика, возникает проблема нахождения среди них единственного решения интервальной
Простейшим способом поиска какого-либо решения рассматриваемой задачи является перебор всех возможных допустимых начальных состояний ЛА и проверка того, удовлетворяют ли эти состояния системе линейных уравнений (20.3). Поскольку для ЛА, заданного над полем $$GF(p) $$, число таких всевозможных начальных состояний $$p^n$$, где $$n$$ - размерность ЛА, то уже при $$n = 30$$ и $$p=2$$ число состояний, подлежащих проверке, превышает $$10^9$$. Учитывая, что
Накопленный опыт практического решения задач переборного типа показал достаточно высокую эффективность применения
Заметим, что используемые далее, но не определенные здесь понятия, связанные с
Принцип работы
Применение
В данной работе используется простой
Остановимся подробнее на отмеченных нами узловых точках построения генетического алгоритма. Обратимся вначале к способу кодирования решения в рассматриваемой интервальной диагностической задаче.
Большая часть существующей теории
Каждому допустимому решению $$s$$ сопоставим битовую строку, представляющую собой хромосому. Сопоставление осуществим следующим образом: вектору $$s=[s_1, s_2, \dots, s_n]'$$ ' поставим в соответствие число в двоичной системе, которое равно числу $$s_1, s_2, \dots, s_n$$ в системе счисления с основанием $$p$$. Такая схема сопоставления является взаимно-однозначной, что позволяет проводить как кодирование, так и декодирование
Заметим, что при $$p=2$$ используются системы счисления по основанию 2 и перевод производить не требуется. Если $$p>2$$, то число бит, необходимых для представления решения, отличается от $$n$$ в сторону увеличения.
При таком способе кодирования длина
Пример 1.
Пусть $$p=2, n=4$$, тогда $$l = 4$$. Решению $$s=[1, 0, 1, 1]' $$ соответствует
Пусть $$p=3, n=4$$, тогда $$l = 7$$. Решению $$s=[1, 0, 2, 1]' $$ соответствует
Следующим важным моментом при реализации генетического алгоритма является определение целевой функции, которая "направляет" поиск решения.
Целевая функция используется для оценивания приспособленности
Пусть $$s=[s_1, s_2, \dots, s_N]'$$ - решение, которое необходимо оценить. Так как это решение представляет собой предполагаемое начальное состояние, то получаем $$s(0)=s$$. Осуществляя подстановку $$s(t)$$ в систему уравнений (1.1)-(1.2) при $$t=\overline {0, t_{max}}$$ где $$t_{max}+1$$ равно длине диагностической последовательности, получим набор из $$t_{max}+1$$ выходных векторов размерности $$m: y_c(0), y_c (1), \dots, y_c(t_{max})$$.
Целевую функцию определим следующим образом:
$$Q(s)=\sum_{t=0}^{t_{max}}Q_t(y_c(t))$$где
$$Q_t(y_c(t))= \begin {cases} 0, если\ y_c(t) \in y(t),\\ \sum_{t=1}^n min (|\bar y(t) - y_c(t)|, | \underline {y_i}(t)-y_c(t)|), если\ y_c (t) \notin y(t) \end {cases}$$При таком выборе целевая функция будет неотрицательной во всей области допустимых значений и принимать значение 0 лишь на решениях интервальной
Однако в классическом понимании целевой функции как функции приспособленности необходимо, чтобы более приспособленные особи оценивались выше, чем менее приспособленные. Этого легко достичь, если произвести нормализацию целевой функции и обратить ее:
$$Q(s)=\sum_{t=0}^{t_{max}}Q_t'(y_c(t))$$где
$$Q_t'(y_c(t))=1-\frac {Q_t(y_c(t))}{n(p-1)}$$Таким образом, целевая функция $$Q(s)$$ будет принимать значения в диапазоне от 0 до 1. При этом большему значению целевой функции соответствует большая степень приспособленности
Теперь коснемся вопроса определения вероятностей применения операторов ПГА. Как же их определять? На этот вопрос пока нет простого и однозначного ответа. В докторской диссертации де Джонга (1975), посвященной исследованию
Размер популяции и максимальное количество поколений определяют объем
В ходе исследования поставленной интервальной
SGA-C реализует простой SGA-C позволяет исследователю сделать настройку для решения его специфических задач с помощью набора функций в файле app.c. Для решения поставленной интервальной
objfunc (): производит вычисление функции $$Q(s)$$ по формулам (20.10)-(20.12).app_report (): производит печать всех найденных в ходе работы программы решений и их количества.chrom2matrix (): производит декодирование matrix_sum (), matrix_mult (): реализуют операции сложения и умножения матриц.Эта программа для нахождения решения интервальной
Рассмотрим ряд примеров решения сформулированной
Пример 2.
Решим интервальную
Согласно описанной выше рекомендации, вероятность оператора кроссинговера $$p_c$$ положим равной 0.1, а вероятность оператора
Как было сказано выше, вероятности операторов играют большую роль при работе генетического алгоритма. Чтобы проиллюстрировать это, данная задача решалась при разных вероятностях оператора скрещивания ( $$p_c$$ ) и оператора
Из этой таблицы можно сделать следующие выводы:
| $$p_c \p_m$$ | 0.00 | 0.01 | 0.02 | 0.03 | 0.04 | 0.05 | 0.06 | 0.07 | 0.08 | 0.09 | 0.10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0.00 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 |
| 0.05 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 |
| 0.10 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
| 0.15 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 0.20 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 0.25 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 0.30 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 0.35 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 0.40 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 0.45 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 0.50 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
Пример 3.
Рассмотрим ЛА из примера 1. Входные векторы оставим без изменений, а выходные векторы сделаем точными, т. е. рассмотрим случай вырожденных интервалов:
$$y(0)= \left [ \begin {matrix} [3,3]\\ [4,4] \end {matrix} \right ], y(1)= \left [ \begin {matrix} [1,1]\\ [3,3] \end {matrix} \right ], y(2)= \left [ \begin {matrix} [5,5]\\ [5,5] \end {matrix} \right ] $$Заметим, что хотя выходные векторы заданы с помощью интервалов, однако представляют собой векторы с точными значениями. Таким образом, данный пример является примером классической
Используя таблицу из примера 2, положим вероятность оператора кроссинговера $$p_c$$ равной 0.15, а вероятность оператора
Таким образом, пример 3 иллюстрирует тот факт, что
Главными преимуществами генетического алгоритма при решении разнообразных задач являются небольшой объем используемой памяти и высокая скорость получения решения. Например, при $$p=2, n=30$$, программа с применением ГА нашла решение менее чем за 1 секунду своей работы (был взят компьютер с процессором Celeron 900 MHz). Другая программа, которая осуществляла поиск решения полным перебором, это же решение нашла только через несколько десятков часов при использовании того же компьютера. Таким образом, генетический подход к решению интервальной
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.