Эта задача имеет следующую неформальную простую постановку [4,5]. Имеется рюкзак объемом $$C$$ и $$n$$ различных предметов. Каждый предмет $$i$$ имеет известный объем $$W_i$$ и стоимость $$P_i(i=1,\dots,n)$$. В рюкзак можно положить целое число различных предметов. Нужно упаковать рюкзак так, чтобы полная стоимость уложенных предметов была максимальной, а их общий объем не превышал заданный объем $$C$$. Форма предметов здесь не учитывается.
Формальная постановка задачи: для данного множества весов $$W_i$$, стоимостей $$P_i$$ и объема $$C$$ надо найти двоичный вектор $$X=(x_1,\dots,x_n)\mbox{, где}\ x_i=\begin{cases}1,\mbox{если предмет помещается в рюкзак,}\\0,\mbox{в противном случаи.}\end{cases}$$
и при этом должно выполняться условие:
$$V=\sum_{i=1}^n W_i\le C\mbox{ и }\sum_{i=1}^n P_i=\max$$Так как решение задачи можно представить двоичным вектором $$X= (x_1,\dots, x_n)$$, то очевидно при его поиске можно применить простой ГА со стандартными операторами скрещивания и мутации. Но при этом на каждом шаге итерации надо следить за тем, чтобы новые решения, полученные в результате скрещивания или мутации, удовлетворяли требуемому ограничению $$V\le C$$. В случае невыполнения ограничения "неправильное" потенциальное решение должно быть уничтожено, что ведет к сокращению популяции.
В качестве фитнесс-функции в простейшем случае можно взять $$P(X)=\sum_{i=1}^n x_i\cdot P_i,$$ но в этом случае, как указано выше, есть проблемы с неправильными решениями.
Данная задача относится к классу задач с ограничениями, при решении которых применяются следующие подходы [4,5]: 1) введение в фитнесс-функцию дополнительного штрафа; 2) использование алгоритмов "восстановления" некорректных решений.
Разработано множество методов назначения штрафных значений, из которых ниже рассмотрено только три вида, когда рост значения штрафной функции относительно степени нарушения ограничения имеет логарифмический, линейный и квадратичный характер:
Здесь для всех трех случаев $$\rho = \max_{1 \le i \le n} {P_i/w_i}$$.
Второй подход к решению задач с ограничениями основан на специальных алгоритмах "восстановления" некорректных решений. Следует отметить, что многие алгоритмы восстановления требуют значительных вычислительных ресурсов, и полученные решения иногда требуют адаптации к конкретным практическим приложениям.
В этом случае в качестве фитнесс-функции используется $$f(X')=\sum_{i=1}^n x_i'P_i,$$ где вектор $$X'$$– восстановленная версия исходного вектора $$X$$. Здесь следует отметить, по крайней мере, два аспекта. Во-первых, можно использовать различные алгоритмы восстановления. Во-вторых, восстановленные особи могут замещать только некоторую часть исходных особей в популяции. Процент замещаемых особей может варьироваться от 0% до 100% и его значение является важнейшим параметром метода восстановления. В некоторых работах отмечается, что наилучшие результаты получаются при 5%, во всяком случае, лучше, чем в двух крайних случаях – 0% (без замещения) и 100% (любая восстановленная особь заменяет исходную). Ниже приведен простой алгоритм восстановления.
При этом используются два основных способа выбора объекта:
Третий подход к решению задач с ограничениями использует специальное отображение (декодирование) особей, которое гарантирует генерацию допустимого решения (с учетом ограничений), или используют проблемно-ориентированные генетические операторы, сохраняющие корректность решения.
Рассмотрим один из возможных вариантов алгоритма декодирования, который основан на кодировании решения вектором целых чисел, так называемом "упорядоченном представлении" (ordinal representation), подробно описанном в разделе 3.3.2. Здесь каждая хромосома кодируется вектором $$e$$ целых чисел, где $$i$$-я компонента вектора – есть целое число в диапазоне от 1 до $$n-i+1$$. "Упорядоченное представление" использует для ссылок (базовый) список предметов $$L$$. Вектор $$e$$ фактически содержит указатели на базовый список $$L$$. Декодирование вектора осуществляется путем выбора соответствующего предмета из текущего списка и удаления его из базового списка. Например, при базовом списке предметов $$L=(1,2,3,4,5,6)$$ текущий вектор $$e=(4,3,4,1,1,1)$$ декодируется в следующую последовательность предметов: 4, 3, 6, 1,2, 5. Первым в рюкзак включается четвертый элемент списка $$L$$- 4, который устраняется из $$L$$. Далее в рюкзак включается третий элемент из текущего списка $$L$$. Затем включается 6 - четвертый элемент текущего $$L$$ и т.д. Подробнее описание этого представления и выполнение кроссинговера на нем описано в разделе 2.3.2. В данном методе хромосома может интерпретироваться как стратегия (порядок) включения предметов в решение. Отметим, что основным достоинством данного кодирования хромосомы является то, что на нем работает одноточечный кроссинговер. То есть для двух допустимых решений –родителей кроссинговер порождает также допустимое решение–потомок. Оператор мутации при данном представлении выполняется путем замены $$i$$-го гена (целочисленной компоненты вектора) на случайное целое число из диапазона $$[1,\dots,n-i+1]$$.
Очевидно, что представленный алгоритм зависит от способа генерации списка предметов $$L$$. Обычно используются два метода генерации этого списка:
Очевидно, здесь решение можно также представить двоичным вектором
$$X=(x_1,\dots,x_n)$$, где
$$x_i=1$$, если подмножество $$F_i$$ входит в покрытие;
$$x_i=0$$, если $$F_i$$ не входит в покрытие;
и при этом
$$\bigcup_{i=1,\dots,n} x_i F_i=S,$$$$\sum_{i=1}^n x_i=\min$$
Поскольку решение задачи, как было показано выше, представляется двоичным вектором, то при его поиске можно использовать простой ГА со стандартными операторами кроссинговера и мутации.
Напомним неформальную постановку этой классической задачи. Коммивояжер (бродячий торговец) должен выйти из первого города, посетить по одному разу в некотором порядке все города и вернуться в исходный город. На рис.2.1 приведен пример задачи для четырех городов.
Расстояния между городами известны. В каком порядке следует обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим?
(рис 2.1) Задача коммивояжера
В формальной постановке задачи коммивояжера (ЗК): имеется полный взвешенный ориентированный граф $$G$$ без петель с множеством вершин $$N=\{1,2,\dots,n\}$$; веса всех дуг неотрицательны; в этом графе требуется найти гамильтонов цикл с минимальной длиной. Исходная информация по ЗК представляется в виде $$n\times n$$ матрицы $$S=[s_{i,j}],s_{i,j}$$ вес дуги $$(i,j)$$ графа $$G$$, $$i=\overline{1,n}$$, $$j=\overline{1,n}$$, $$i\ne j$$; все элементы главной диагонали нулевые $$s_{ii}=0$$(но в некоторых постановках полагаются $$s_{ii}=\infty$$). Обычно $$s_{ij}$$ интерпретируется как расстояние между городами $$i$$ и $$j$$. С учетом других возможных интерпретаций на матрицу $$S$$ требование симметричности не налагается. Например, в случае интерпретации $$s_{ij}$$ как стоимости проезда, в общем случае может быть $$s_{ij}\ne s_{ji}$$. В общем случае не считается обязательным и выполнение неравенства треугольника $$s_{ij}+ s_{jk}\ge s_{ik}$$.
Тур коммивояжера может быть описан циклической перестановкой $$t=(j_1,j_2,\dots,j_n,j_1)$$, причём все $$j_1,\dots,j_n$$– попарно различны; повторяющийся в начале и в конце номер города $$j_1$$, показывает, что перестановка циклическая. Пространством поиска решений этой задачи является множество перестановок $$n$$ городов. Любая простая (одиночная) перестановка $$n$$ городов даёт решение, являющееся полным туром из $$n$$ городов. Оптимальным решением является перестановка, которая даёт минимальную стоимость тура. Очевидно, размерность пространства поиска для несимметричной задачи равна $$(n-1)!$$. Известно, что эта задача является NP – полной, т.е. переборной. Она имеет многочисленные практические приложения, в которых число "городов" может быть достаточно большим. Например, при производстве сложных деталей задача сверления отверстий может иметь сотни и тысячи "городов". При производстве СБИС возникают задачи (например, по внесению примесей в полупроводник) с числом "городов" около миллиона. За последние десятилетия разработано достаточно много алгоритмов решения этой задачи, дающих субоптимальное решение. В последнее десятилетие эта задача является базовой для исследования ГА в области
Очевидно, что двоичное представление тура при решении ЗК нецелесообразно. Действительно если мы интересуемся оптимальной перестановкой городов, т.е. $$(i_1,i_2, \dots , i_n)$$ и используем двоичное представление в виде одного бинарного вектора, то изменение даже в одном бите двоичного кода перестановки может дать двоичный вектор, не принадлежащий к области решения, т.е. не являющейся перестановкой $$n$$ городов.
Для решения ЗК с помощью генетических алгоритмов разработаны специальные методы представления (кодирования) решений и соответствующие
В этом случае тур представляется списком из n городов, где $$i$$-й элемент списка имеет номер от 1 до $$n-i+1$$. При этом используется базовый упорядоченный список городов $$L$$, который служит для ссылок упорядоченного представления. Фактически мы рассматривали этот метод кодирования решения при решении
Рассмотрим его на конкретном примере тура $$T$$= (1-2-4-3-8-5-9-6-7), для которого упорядоченный список $$L$$= (1 2 3 4 5 6 7 8 9). Тогда данный тур при этом упорядоченном списке представляется следующим списком ссылок $$e$$=(1 1 2 1 4 1 3 1 1), который интерпретируется следующим образом. Здесь жирным курсивом выделен текущий указатель в списке $$e$$.
Первый номер из списка $$e$$ равен 1, поэтому помещаем в тур 1-й город из базового списка $$L$$, удаляем его из $$L$$ и сдвигаем указатель по $$e$$. Тогда получаем:
тур $$T_1$$=(1), базовый список $$L_1$$= (2 3 4 5 6 7 8 9) , указатель $$e$$=(1 1 2 1 4 1 3 1 1).
Следующий номер по указателю $$e$$ также равен 1, поэтому снова помещаем в тур 1-й город из базового списка $$L$$, удаляем его из $$L$$ и сдвигаем указатель по $$e$$.
В результате получаем :
текущий тур $$T_2$$=( 1-2), $$L_1$$= (3 4 5 6 7 8 9) и указатель в e сдвигается на третью позицию $$e$$= (1 1 2 1 4 1 3 1 1). Следующий номер списка е равен 2, поэтому мы берем и удаляем 2-й город из текущего базового списка $$L$$ и добавляем его в тур и передвигаем указатель по $$e$$. Имеем:
текущий тур $$T_3$$=(1-2-4), $$L$$ = (3 5 6 7 8 9), $$e$$ = (1 1 2 1 4 1 3 1 1).
Продолжая этот процесс, в результате декодирования по данному коду $$e$$=(1 1 2 1 4 1 3 1 1), базовому списку $$L$$= (1 2 3 4 5 6 7 8 9) будет построен тур $$T$$= (1-2-4-3-8-5-9-6-7) .
Основное преимущество упорядоченного представления в том, что в этом случае работает классический кроссинговер (над векторами целых чисел). То есть для двух допустимых решений кроссинговер производит два допустимых решения – потомка.
Например, для родителей
$$e_1$$= (1 1 2 1 | 4 1 3 1 1) и $$e_2$$ = (5 1 5 5 | 5 3 3 2 1),
которые соответствуют турам
$$T_1$$=(1-2-4-3-8-5-9-6-7) и $$T_2$$=(5-1-7-8-9-4-6-3-2),
имеем следующих потомков при скрещивании
$$O_1$$= (1 1 2 1 5 3 3 2 1) и $$O_2$$= (5 1 5 5 4 1 3 1 1),
которые представляют туры
$$T_3$$=(1-2-4-3-9-7-8-6-5) и $$T_4$$=(5-1-7-8-6-2-9-3-4).
Очевидно, что частичные туры слева от точки кроссинговера не изменяются, в тоже время частичные туры справа от нее разрываются случайным образом (сохраняя корректность решения). К сожалению, машинные эксперименты по решению ЗК на основе этого представления решений с использованием классического кроссинговера показывают посредственные результаты [4].
В этом случае тур представляется списком соседних городов. Город $$j$$ находится в позиции $$i$$ если и только если в туре после города $$i$$ посещается город $$j$$, что показано на рис.2.2
(рис 2.2) Следование городов в туре
Например, вектор $$n_1$$=(2 4 8 3 9 7 1 5 6) представляет следующий тур $$T_1$$=(1-2-4-3-8-5-9-6-7). При этом любой тур имеет единственное представление списком соседства. Однако некоторые "списки соседей" могут представлять "неправильные" туры. Например, список соседства $$n_2$$=(2 4 8 1 9 3 5 7 6) содержит "частичный" тур $$T_2$$=(1-2-4-1). Поэтому представление списком соседей не поддерживает классический оператор кроссинговера, поскольку при перестановке частей списков могут получаться неправильные ("частичные") туры. В этом случае необходим некоторый алгоритм восстановления полного тура.
Для данного способа кодирования решения были предложены и исследованы 3 основных оператора кроссинговера: 1) обмен ребер (дуг) графа; 3) обмен подтуров; 3) эвристический кроссинговер [2,3,4]. Далее рассмотрим их детально.
Этот тип кроссинговера строит потомка (случайным) выбором ребра (пары городов $$i-j$$) из первого родителя, затем выбором соответствующего ребра из второго родителя и т.д. Оператор наращивает тур выбором ребер из различных родителей. Если новое ребро (взятое у одного из родителей) образует преждевременный (частичный) цикл в текущем (ещё не полном) туре, то оператор выбирает (случайно) вместо этого ребра одно из оставшихся ребер, которое не дает преждевременного цикла.
Например, для 2-х родителей $$n_1$$= (2 3 8 7 9 4 1 5 6), представляющего тур $$T_1$$=(1-2-3-8-5-9-6-4-7-1), и $$n_2$$= (7 5 1 6 9 2 8 4 3), представляющего тур $$T_2$$=(1-7-8-4-6-2-5-9-3-1), получаем следующего потомка $$\sigma_1$$= (2 5 8 7 9 4 3 1 6). Здесь произведен обмен (случайный) ребер $$3\leftrightarrow 5$$ во второй позиции, далее при попытке обмена $$3\leftrightarrow 5$$ в седьмой позиции возникает конфликт (два ребра входят в 8), поэтому случайно выбирается 3 в позиции 7 ( из оставшихся 6, 1, 3), 1 – в позиции 8 и 6 в позиции 9. В результате порождается потомок $$\sigma_1$$, который соответствует туру $$T_3$$=(1-2-5-9-6-4-7-3-8-1).
Этот оператор строит потомки путём выбора (случайной длины) подтура из первого родителя, затем выбора подтура (опять случайной длины) из второго родителя и их обмена. Как и ранее, в случае конфликта оператор случайно выбирает другое ребро (город) из не вошедших в построенный тур.
Данный оператор строит потомка случайным выбором города в качестве начальной точки для формирования тура. Затем сравниваются два ребра, исходящие из этого города, имеющихся в двух родителях, и из них выбирается лучшее с меньшей стоимостью. Полученный город (в него входит выбранное ребро на предыдущем этапе), используется в качестве начальной точки при выборе следующего ребра и т.д. Как и ранее, в случае возникновения преждевременного цикла, следующий город выбирается случайно из городов, еще не вошедших в текущий тур. Известна следующая модификация этого оператора.
Если оптимальное (с меньшей стоимостью) ребро дает преждевременный цикл в потомке, то проверяется альтернативное ребро (с большей стоимостью) на генерацию преждевременного цикла. Если это ребро не генерирует цикл, то оно включается в тур, иначе выбирается минимальное из $$q$$ ребер (где $$q$$–параметр пула выбора) случайно выбранных из оставшихся городов.
Преимущество этого кодирования в том, что в этом случае анализ схем (шаблонов) можно проводить по аналогии с двоичным случаем. Например, схема (* * * 3 *7 * * *) представляет множество всех туров с ребрами (4-3) и (6-7). Однако основной недостаток этого представления в весьма посредственных результатах тестовых задач для всех трех рассмотренных операторов. Кроссинговер обмена ребер часто разрывает хорошие туры при обмене ребер родителей. Кроссинговер обмена подтуров даёт лучшие результаты, чем предыдущий, так как "отношение разрыва" здесь меньше. Эвристический оператор даёт несколько лучшие результаты за счет учета стоимости исходящих ребер и локального выбора лучшего варианта из двух возможных. Однако эксперименты показывают также посредственные результаты [4].
Это представление, возможно, самое естественное для тура. Например, тур (5-1-7-8-9-4-6-2-3) представляется просто упорядоченным списком (5 1 7 8 9 4 6 2 3) городов, входящих в тур.
Для данного представления были определены и исследованы три типа кроссинговера [2,3,4]:
Рассмотрим их по порядку.
Частично соответствующий ОК (РМХ) строит потомок путем выбора последовательности тура из одного родителя и сохранения порядка и позиции городов из другого родителя насколько это возможно. Подпоследовательность из тура выбирается случайно с помощью двух "секущих" точек, которые служат границами для операции обмена. Например, для родителей $$P_1$$=(1 2 3 | 4 5 6 7| 8 9) и $$P_2$$= (4 5 2 | 1 8 7 6 | 9 3) потомок строится следующим образом.
Сначала производим обмен выделенными подтурами и в результате получаем $$T_1$$ = (X X X | 1 8 7 6 | X X) и $$T_2$$= (X X X | 4 5 6 7 | X X), где "X" означает еще незаполненную позицию (допускающую произвольное значение). Этот обмен определяет также отображение $$1\leftrightarrow 4,8\leftrightarrow 5,7\leftrightarrow 6$$. Далее (вместо "Х") вставляем города из исходных родителей, для которых нет конфликтов (не образуются преждевременный цикл): $$O_1$$= (X 2 3 | 1 8 7 6 | X 9), $$O_2$$= (X X 2 | 4 5 6 7 | 9 3).
Далее первый "Х" в $$O_1$$, заменяем на "4" согласно отображению $$1\leftrightarrow 4$$. Аналогично второй "Х" в потомке $$O_1$$ заменяется "5", и во втором потомке $$O_2$$ оставшиеся неопределенные позиции "Х" заменяются соответственно на 1 и 8. В результате получаем два потомка: $$O_1$$= (4 2 3 | 1 8 7 6 | 5 9) и $$O_2$$= ( 1 8 2 | 4 5 6 7 | 9 3).
Упорядоченный ОК строит потомок выбором подтура из одного родителя и сохранением относительного порядка городов из другого родителя. Например, для родителей $$P_1$$= (1 2 3 | 4 5 6 7 | 8 9), $$P_2$$= (4 5 2 | 1 8 7 6 | 9 3) потомок строится следующим образом.
Сначала сегменты между двумя секущими точками копируется в потомки: $$O_1$$= (X X X | 4 5 6 7 | X X), $$O_2$$= (X X X | 1 8 7 6 | X X).
Далее, в первом родителе, начиная со второй секущей точки, копируются города из другого родителя, пропуская уже присутствующие в построенном подтуре. По достижению конца списка этот процесс продолжается с первой позиции и до первой точки сечения (по кольцу).
Для нашего примера после второй точки сечения во втором родителе мы имеем следующую последовательность: 9 – 3 – 4 – 5 – 2 – 1 – 8 – 7 – 6. Удаляем из нее города 4, 5, 6, 7, поскольку они уже есть в первом потомке, и в результате получаем последовательность 9 – 3 – 2 – 1 – 8. Ее мы помещаем в первый потомок, начиная со второй точки сечения (по кольцу) и получаем потомок $$O_1$$= (2 1 8 | 4 5 6 7 | 9 3). Аналогично получаем второго потомка $$O_2$$ = (3 4 5 | 1 8 7 6 | 9 2).
Оператор кроссинговера ОХ опирается на то, что при представлении тура прежде всего важен порядок городов, например, два тура (9–3–4–5–2–1–8–7–6) и (4–5–2–1–8–7–6–9–3) идентичны.
Циклический ОК строит потомки таким образом, что каждый город вместе со своей позицией идет от одного из родителей. Например, для родителей $$P_1$$= (1 2 3 4 5 6 7 8 9) и $$P_2$$= (4 1 2 8 7 6 9 3 5) сначала получаем путем выбора первого города из родителя $$O_1$$= (1X X X X X X X X). Выбор следующего города определяет текущая позиция второго родителя. В нашем примере это город 4, что дает $$O_1$$= (1 X X 4 X X X X X). Город 4 в свою очередь имплицирует город 8 (из второго родителя), что дает $$O_1$$= (1 X X 4 X X X 8 X).
Аналогично получаем города 3, 2 в $$O_1$$= (1 2 3 4 X X X 8 X). Здесь мы вынуждены прервать этот процесс, так как выбор $$2\to 1$$ ведет к преждевременному циклу. Поэтому оставшиеся города берутся из другого родителя $$P_2$$(с сохранением порядка) и в результате получаем потомков $$O_1$$= (1 2 3 4 7 6 9 8 5 ) и $$O_2$$= (4 1 2 8 5 6 7 3 9). Таким образом, оператор ОК СХ сохраняет абсолютные позиции потомков и родителей.
Опубликовано достаточно много работ [2,3,4,5,6], где для решения
В матрице смежности элемент $$m_{ij}=1$$ в том и только случае, если в туре после города $$i$$ посещается город $$j$$(в графе есть ребро от вершины $$i$$ в вершину $$j$$). Например, табл.2.1 содержит матрицу смежности для тура $$T_1$$=(1-2-4-3-8-6-5-7-9) и табл.2.2 – матрицу смежности для тура $$T_2$$=(1-4-3-6-5-7-2-8-9).
Отметим, что в этом случае каждая строка и столбец матриц содержат одну единицу. Для матрицы смежности можно использовать одно- или двуточечный кроссинговер, где обмен производится, например, столбцами. Но в этом случае необходим дополнительный алгоритм восстановления, который позволяет восстанавливать полученные потомки до полных туров.
Рассмотрим, этот подход на примере двухточечного вертикального кроссинговера с точками скрещивания 2 и 6. При этом производится обмен столбцами (3,4,5,6) матриц смежности (табл.2.1 и табл.2.2). В результате получаем промежуточный результат в виде матриц, которые представлены табл.2.3 и табл.2.4. Обе матрицы не представляют правильных решений, но заметим, что суммарное число единиц в каждой из этих промежуточных матриц правильное (9 единиц).
На первом шаге алгоритма восстановления передвигаем 1 в матрице таким образом, чтобы каждая строка и столбец имели одну единицу. Например, в матрице табл.2.3 первая строка имеет две 1 (вместо одной). Поэтому "передвинем" $$m_{14}=1$$ в позицию $$m_{84}=1$$, а элемент $$m_{24}=1$$ в $$m_{34}=1$$, аналогично $$m_{86}=1$$ в $$m_{16}=1$$. В результате после выполнения первого этапа алгоритма восстановления получаем правильный тур для первого потомка $$T_3$$=(1-2-8-4-3-6-5-7-9), в то время как второй потомок содержит два подтура $$T_4$$=(1-6-5-7-2-8-9) (3-4).
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
| 4 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 5 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| 6 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| 7 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| 8 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| 9 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
| 3 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| 4 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 5 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| 6 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| 7 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 8 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| 9 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 3 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 |
| 4 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 5 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| 6 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| 7 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| 8 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 9 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 |
| 3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 4 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 5 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| 6 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| 7 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 8 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |
| 9 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Поэтому на втором этапе алгоритма восстановления обрабатываем только второй потомок. При этом необходимо разорвать частичные подтуры и объединить их в единый правильный тур. Это можно сделать, например, с помощью ребра 2-4, которое присутствует у одного из родителей. В результате получаем полный тур для второго потомка $$T_5$$=(1-6-5-7-2-4-3-8-9).
Рассмотрим представление тура в виде двоичной матрицы предшествования [4]. В этом случае элемент матрицы $$m_{ij}$$ равен 1, если и только если город $$i$$ предшествует (встречается в туре раньше) городу $$j$$. В противном случае $$m_{ij}=0$$. Отметим, что здесь имеется в виду не только непосредственное предшествование (город $$i$$ связан непосредственно с городом $$j$$) но и более "глубокое". Например, тур $$T_3$$=(3-1-2-8-7-4-6-9-5) представляется бинарной матрицей предшествования, которая показана в табл.2.5 Здесь элементы главной диагонали $$m_{ij}=0$$ и $$m_{ij}=1$$, если $$i$$-й город предшествует в туре $$j$$-му городу. Например, в первой строке город 1 предшествует в туре городам 2, 4, ….,9, но не предшествует городу 3.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
| 3 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
| 4 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 |
| 5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 6 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 |
| 7 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 |
| 8 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 1 |
| 9 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
В этом представлении тура матрица $$M$$ размерности $$n\times n$$ обладает следующими свойствами:
Если число единиц в матрице меньше чем $$\frac{n(n-1)}{2}$$, а два других требования выполняются, то города частично упорядочены. Это означает, что можно получить матрицу (по крайней мере одним способом), которая представляет правильный тур. На этой форме представления вводятся два новых генетических оператора кроссинговера: пересечение и объединение.
Оператор пересечения основан на том, что побитовое пересечение матриц дает матрицу, где:
Таким образом, можно получить матрицу, представляющую правильный тур. Например, для двух родителей $$P_1$$= (1-2-3-4-5-6-7-8-9) и $$P_2$$= (4-1-2-8-7-6-9-3-5), представляемых матрицами табл.2.6 и табл.2.7 соответственно, поэлементное пересечение этих матриц дает матрицу табл.2.8.
Частичный порядок городов определяемый матрицей табл.2.4 следующий:
Город 1 предшествует городам 2, 3, 5, 6, 7, 8, 9;
Город 2 предшествует городам 3, 5, 6, 7, 8, 9;
Город 3 предшествует 5;
Город 4 – 5, 6, 7, 8, 9
Города 6, 7, 8 предшествуют 9.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 3 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
| 4 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| 5 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 6 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| 7 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 8 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| 9 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
На заключительном этапе выполнения этого оператора выбирается один из родителей и в промежуточную матрицу (полученную после пересечения) добавляются некоторые единицы (чтобы их число было равно $$\frac{n(n-1)}{2}$$) путем анализа сумм строк и столбцов, которые восстанавливают полный тур с учетом соответствующего родителя.
В табл.2.8 для удобства показано число единиц по строкам и столбцам матрицы, которое, например, позволяет города разбить на подтуры или в некотором смысле эквивалентные группы. Анализ числа единиц в строках показывает, что тур должен начинаться с (1-2-4), остальные города можно разбить на группы (3,6,7,8) и (5,9). Анализ числа единиц по столбцам позволяет "выстроить" подтур (3-5-9), а для остальных трех городов можно выбрать, например, порядок (8-7-6). В результате получаем для потомка полный тур (1-2-4-8-7-6-3-5-9), который представлен матрицей табл.2.9, которая может быть получена из предыдущей табл.2.8.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| 1 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 |
| 2 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 |
| 3 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| 4 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 |
| 5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 6 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 1 |
| 7 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 |
| 8 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 |
| 9 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | N1 | |
| 1 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 7 |
| 2 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 6 |
| 3 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
| 4 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 5 |
| 5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 6 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 7 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 8 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 9 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| N1 | 0 | 1 | 2 | 0 | 4 | 3 | 3 | 3 | 6 |
Оператор объединения основан на том, что подмножество бит из одной матрицы может быть комбинировано с подмножеством бит из другой матрицы без потери свойства быть туром, если эти подмножества имеют пустое пересечение. Оператор разбивает множество городов на две непересекающиеся группы. При этом для первой группы городов копируются биты из первой матрицы, а для второй группы копируются биты из второй матрицы.
На заключительном этапе матрица достраивается путем анализа сумм для строк и столбцов аналогично операции пересечения. Например, два родителя $$P_1$$ и $$P_2$$, которые представлены табл.2.6 и табл.2.7, и разбиения городов {1, 2, 3, 4,} и {5, 6, 7, 8, 9} порождают матрицу табл.2.10.
Таким образом, для решения
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| 1 | 0 | 1 | (1) | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 0 | 0 | 1 | (1) | 1 | 1 | 1 | 1 | 1 |
| 3 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | (1) |
| 4 | 0 | 0 | (1) | 0 | 1 | 1 | 1 | 1 | 1 |
| 5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | (1) |
| 6 | 0 | 0 | (1) | 0 | (1) | 0 | 0 | 0 | 1 |
| 7 | 0 | 0 | (1) | 0 | (1) | (1) | 0 | 0 | 1 |
| 8 | 0 | 0 | (1) | 0 | (1) | (1) | (1) | 0 | 0 |
| 9 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| 1 | 0 | 1 | 1 | 1 | X | X | X | X | X |
| 2 | 0 | 0 | 1 | 1 | X | X | X | X | X |
| 3 | 0 | 0 | 0 | 1 | X | X | X | X | X |
| 4 | 0 | 0 | 0 | 0 | X | X | X | X | X |
| 5 | X | X | X | X | 0 | 0 | 0 | 0 | 0 |
| 6 | X | X | X | X | 1 | 0 | 0 | 0 | 1 |
| 7 | X | X | X | X | 1 | 1 | 0 | 0 | 1 |
| 8 | X | X | X | X | 1 | 1 | 1 | 0 | 1 |
| 9 | X | X | X | X | 1 | 0 | 0 | 0 | 0 |
Процесс диагностирования цифровых устройств (ЦУ) требует использования так называемой диагностической информации (ДИ). Для современных ЦУ эта информация имеет очень большой объем, что порождает значительные трудности при локализации неисправностей.
Если множество тестов $$T$$ таково, что для каждой пары неисправностей $$f_i,f_k\in F$$ найдется хотя бы один тестовый набор $$t_j\in T$$ такой, что $$R_{ij}\ne R_{kj}$$, то все строки ТФН попарно различны. Такое множество $$T$$ называется диагностическим тестом.
Понятно, что полная ТФН, содержащая информацию о реакциях ЦУ на все ее возможные входные наборы, имеет, как правило, очень большой объем и является избыточной для локализации рассматриваемых неисправностей. При диагностировании ЦУ обычно используется не ТФН, а $$T$$–ТФН, где $$T$$ – минимальное подмножество всех входных наборов ЦУ, позволяющее диагностировать неисправности из $$F$$. Заметим, что и $$T$$-ТФН также может содержать много избыточной информации. Упомянутую таблицу будем именовать словарем полной реакции (СПР) диагностируемого ЦУ.
Один из возможных способов сокращения объема СПР, в котором для каждого технического состояния ЦУ сохраняется часть полной реакции устройства в этом состоянии на тест $$T$$, выделенная с помощью некоторого шаблона, называемого маской [8].
Назовем точкой проверки номер выхода ЦУ, по которому будет наблюдаться реакция на тестовые наборы. Тогда маской $$h$$ назовем любую совокупность точек проверки.
С помощью маски $$h$$ из СПР можно выделить некоторую его часть. Содержательно выделение такой информации поясним следующим образом. В каждой клетке $$(i,j)$$ СПР расположена двоичная последовательность длины $$m$$, где $$m$$ – число выходов диагностируемого ЦУ, являющейся реакцией ЦУ в состоянии $$s_i$$ на $$j$$-й тестовый набор $$t_j$$ из множества $$T$$. Тогда маска $$h$$ соответствует"окошечкам" в битовой строке СПР, которые следует "прорезать", чтобы увидеть выделяемые маской биты реакции ЦУ на каждый тестовый набор из $$T$$.
Отметим, что СПР формируется с использованием логического моделирования до процесса диагностирования ЦУ. После завершения процесса диагностирования фиксируется реакция ЦУ на каждый тестовый набор $$t_i\in T$$. Затем с помощью используемой маски "фильтруется" как СПР, так и полученная реакция ЦУ на тестовое множество $$T$$, и выполняется сравнение соответствующих строк в них. Те из состояний $$s_i\in S$$, для которых произошло совпадение, заносятся в список подозреваемых неисправностей (СПН).
Пусть $$\{S_i\}$$, где $$S_i\subseteq S$$, есть множество всех возможных СПН, которые могут возникнуть при диагностировании ЦУ с использованием маски $$h$$, а $$P(S)$$- их количество. Понятно, что число таких СПН и число входящих в них неисправностей определяют достигаемую при диагностировании степень детализации и состав имеющихся в ЦУ неисправностей. Эту степень детализации называют разрешающей способностью диагностирования и вычисляют ее по формуле
$$\rho (h)=\frac{1}{P(S)}\sum_{S_i\subseteq S}|S_i|$$Из формулы следует, что $$\rho (h)$$ есть средняя длина всех возможных СПН.
Через $$\rho$$ обозначим разрешающую способностью диагностирования ЦУ, обеспечиваемую словарем полной реакции (СПР) с использованием того же теста $$T$$, что подразумевался и в формуле (2.1).
Из изложенного выше следует, что "фильтрация" исходного СПР с помощью некоторой маски $$h$$(обозначим его как $$СПР_h$$) может привести к существенному уменьшению объема исходного СПР.
Теперь сформулируем задачу сокращения ДИ, которая рассматривается далее. Для множества технических состояний $$S$$ диагностируемого ЦУ требуется найти такую маску $$h$$ минимальной длины, чтобы объем полученного с ее помощью $$СПР_h$$ был минимальным и при этом разрешающая способность $$\rho (h)$$ по маске $$h$$ равнялась разрешающей способности $$\rho$$ диагностирования, обеспечиваемой полным СПР.
Сформулированная задача является комбинаторныйи точное ее решение можно получить только с помощью перебора. Однако для современных ЦУ в связи с большим объемомдля них СПР реализация получения точного решения невозможна из-за чрезвычайно большой трудоемкости. По этой причине были предприняты попытки поиска иных подходов к решению упомянутой задачи.Одним из перспективных методов ее решения основан на использовании простого ГА, к детализации которого мы и перейдем.
Начнем с описания структуры хромосомы, применяемой в предлагаемом простом ГА[9]. Хромосому, соответствующую маске $$h$$, будем представлять в виде битовой последовательности $$\eta (h)$$ длины $$m$$:
$$\eta (h)=\eta_1(h)\eta_2(h)\dots \eta_m(h)$$где $$m$$- количество выходов ЦУ.Для каждой точки проверки $$i$$, входящей в состав маски $$h$$, значение $$\eta_i(h)$$ в (2.2) полагается равным 1. Все остальные разряды в $$\eta(h)$$ полагаются равными нулю.
Длиной маски $$h$$ будем называть величину $$|h|=\sum_{i=1}^m \eta_i(h)$$
Введем в рассмотрение величину $$V(h)=|h|/m$$, которая равна доли длины маски $$h$$ от длины реакции на любой тестовый набор по всем выходам ЦУ.
Для решения рассматриваемой задачи с применением простого ГА будем использовать следующую фитнесс-функцию:
$$d(\eta (h))=C\cdot(\rho-\rho(h))+V(h)$$где $$C$$— достаточно большая константа.
Поясним содержательный смысл функции (2.3). Поскольку по условиям задачи требуется найти такую маску $$h$$, которая должна обеспечить выполнение равенства $$\rho=\rho(h)$$, то первое слагаемое в (2.3) должно обратиться в ноль. Тогда максимальное сокращение ДИ будет, очевидно, достигнуто при минимальном значении $$V(h)$$, т.е. для маски минимальной длины. Таким образом, искомым решением будет такая маска, для которой фитнесс-функция (2.3) достигает минимального значения.
Из изложенного вытекает, что в процессе выполнения простого ГА близость очередной полученной маски к искомому решению (при большой константе $$C$$) будет определяться прежде всего значением первого слагаемого в (2.3), поскольку значение второго слагаемого не превышает 1. Иными словами, первое слагаемое при подходящем значении константы $$C$$ может служить индикатором удаленности полученной на очередном этапе выполнения ПГА маскиот искомой.
Описываемый ниже простой ГА содержит следующие этапы:
В предлагаемом ПГА начальная популяция (масок) формируется с использованием датчиков случайных величин. На втором этапе для каждой особи вычисляется значениефитнесс-функции (2.3). Отбор особей-кандидатов для участия в репродукции осуществляется по принципу: чем выше значение фитнесс-функции, тем выше вероятность ее участия в процессе скрещивания.На третьем этапе осуществляется скрещивание с использованием оператора однородного кроссинговера отобранных на предыдущем этапе особей, в результате которого производится два новых потомка путем обмена генами родительских особей. Полученные особи формируют новую популяцию. На четвертом этапе происходит мутация особей: случайным образом выбираются две позиции в маске, содержащие несовпадающие двоичные значения, и затем производится их перестановка. На пятом этапе из особей текущего поколения масок, а также полученных после скрещивания потомков, на основе метода элитного отбора формируется следующее поколение масок. В качестве условия окончания используется заранее определенное предельное число этапов эволюции (длина жизненного цикла популяции). В качестве решения принимается особь из последнего поколения с минимальным значением фитнесс-функции.
Для оценки эффективности предложенного ПГА были проведены численные эксперименты, в которых размер популяции подбирался опытным путем с целью ускорения сходимости к искомому решению. На втором этапе ПГА, связанном с селекцией особей, были опробованы различные методы и выбор был сделан в пользу линейного ранжированияю
Численные эксперименты проводились для реальных ЦУ из каталога $$ISKAS'89$$[10] при моделировании одиночных константных неисправностей на всех линиях ЦУ на вероятностных тестах. Каждый такой тест был составлен из 100 входных наборов.
В качестве примера в табл. 2.11 представлена динамика нахождения решения рассматриваемой задачи сокращения ДИ для четырех схем из названного выше каталога. Представленные в ней данные, а также статистические данные для других ЦУ из того же каталога показывают, что оптимальная численность популяции для предложенного ПГА – 100 особей, а для получения приемлемого по качеству решения достаточно 70 поколений. Поясним обозначения столбцов табл. 2.11. В первом ее столбце указаны имена ЦУ из названного каталога, во втором-длина реакции ЦУ на его выходах (в любом его техническом состоянии) на случайную входной тест из 100 входных наборов (в битах), в третьем – число всех возможных СПН, возникающих при диагностировании ЦУ, в четвертом – объем в битах, $$\rho_2(h)$$- значение ожидаемой разрешающей способности диагностирования (средней длины СПН) с использованием найденной лучшей маски.
| Схема | $$m|\tau|$$ | $$|S|$$ | Объем полной ДИ | Результат после 40 поколений | Результат после 60 поколений | Результат после 80 поколений | Доля сокращенной информации по отношению к полной | |||
|---|---|---|---|---|---|---|---|---|---|---|
| Длина маски | $$\rho_2(h)$$ | Длина маски | $$\rho_2(h)$$ | Длина маски | $$\rho_2(h)$$ | |||||
| S382 | 600 | 32 | 19 200 | 20 | 1.063 | 20 | 1.000 | 20 | 1.000 | 3.33% |
| S386 | 700 | 136 | 95 200 | 55 | 1.059 | 55 | 1.044 | 55 | 1.000 | 7.86% |
| S400 | 600 | 33 | 19 800 | 20 | 1.121 | 20 | 1.060 | 20 | 1.000 | 3.33% |
| S510 | 700 | 447 | 312 900 | 70 | 1.027 | 70 | 1.000 | 70 | 1.000 | 10.00% |
Приведенные результаты получены на PC Pentium III, 1024 MHz, 256 Mb RAM. Что касается временных затрат на работу ПГА, то они находились в диапазоне от нескольких секунд до 30 минут при объема СПР от 5 Kb до 2Mb.Как показала статистика, доля "сжатой" ДИ во всех названных экспериментах от объема полного СПР составляла от 3% до 15%, что несомненно является хорошим результатом. Таким образом, на основе приведенных данных можно говорить о достаточной эффективности предложенного ПГА и высоком его быстродействии.
Заметим, что подробно с задачами сокращения ДИ и методами их решения можно ознакомиться в [11].
| № варианта | Название функции | Вид представления |
|---|---|---|
| 1 | Wi29.tsp | Представление соседства |
| 2 | Dj89.tsp | Представление соседства |
| 3 | Att48.tsp | Представление соседства |
| 4 | Bayg29.tsp | Представление соседства |
| 5 | Bayg29.tsp | Представление соседства |
| 6 | Berlin52.tsp | Представление соседства |
| 7 | Eil51.tsp | Представление соседства |
| 8 | Eil76.tsp | Представление соседства |
| 9 | Wi29.tsp | Представление порядка |
| 10 | Dj89.tsp | Представление порядка |
| 11 | Att48.tsp | Представление порядка |
| 12 | Bayg29.tsp | Представление порядка |
| 13 | Bayg29.tsp | Представление порядка |
| 14 | Berlin52.tsp | Представление порядка |
| 15 | Eil51.tsp | Представление порядка |
| 16 | Eil76.tsp | Представление порядка |
| 17 | Wi29.tsp | Представление пути |
| 18 | Dj89.tsp | Представление пути |
| 19 | Att48.tsp | Представление пути |
| 20 | Bayg29.tsp | Представление пути |
| 21 | Bayg29.tsp | Представление пути |
| 22 | Berlin52.tsp | Представление пути |
| 23 | Eil51.tsp | Представление пути |
| 24 | Eil76.tsp | Представление пути |
Тестовые наборы (benchmarks) к упражнению представлены в трех формах:
Тип данных: эвклидовы координаты городов 1 20833.3333 17100.0000 2 20900.0000 17066.6667 3 21300.0000 13016.6667 4 21600.0000 14150.0000 5 21600.0000 14966.6667 6 21600.0000 16500.0000 7 22183.3333 13133.3333 8 22583.3333 14300.0000 9 22683.3333 12716.6667 10 23616.6667 15866.6667 11 23700.0000 15933.3333 12 23883.3333 14533.3333 13 24166.6667 13250.0000 14 25149.1667 12365.8333 15 26133.3333 14500.0000 16 26150.0000 10550.0000 17 26283.3333 12766.6667 18 26433.3333 13433.3333 19 26550.0000 13850.0000 20 26733.3333 11683.3333 21 27026.1111 13051.9444 22 27096.1111 13415.8333 23 27153.6111 13203.3333 24 27166.6667 9833.3333 25 27233.3333 10450.0000 26 27233.3333 11783.3333 27 27266.6667 10383.3333 28 27433.3333 12400.0000 29 27462.5000 12992.2222 EOF
Тип данных: эвклидовы координаты городов 1 11511.3889 42106.3889 2 11503.0556 42855.2778 3 11438.3333 42057.2222 4 11438.3333 42057.2222 5 11438.3333 42057.2222 6 11785.2778 42884.4444 7 11785.2778 42884.4444 8 11785.2778 42884.4444 9 11785.2778 42884.4444 10 12363.3333 43189.1667 11 11846.9444 42660.5556 12 11503.0556 42855.2778 13 11963.0556 43290.5556 14 11963.0556 43290.5556 15 12300.0000 42433.3333 16 11973.0556 43026.1111 17 11973.0556 43026.1111 18 11461.1111 43252.7778 19 11461.1111 43252.7778 20 11461.1111 43252.7778 21 11461.1111 43252.7778 22 11600.0000 43150.0000 23 12386.6667 43334.7222 24 12386.6667 43334.7222 25 11595.0000 43148.0556 26 11595.0000 43148.0556 27 11569.4444 43136.6667 28 11310.2778 42929.4444 29 11310.2778 42929.4444 30 11310.2778 42929.4444 31 11963.0556 43290.5556 32 11416.6667 42983.3333 33 11416.6667 42983.3333 34 11595.0000 43148.0556 35 12149.4444 42477.5000 36 11595.0000 43148.0556 37 11595.0000 43148.0556 38 11108.6111 42373.8889 39 11108.6111 42373.8889 40 11108.6111 42373.8889 41 11108.6111 42373.8889 42 11183.3333 42933.3333 43 12372.7778 42711.3889 44 11583.3333 43150.0000 45 11583.3333 43150.0000 46 11583.3333 43150.0000 47 11583.3333 43150.0000 48 11583.3333 43150.0000 49 11822.7778 42673.6111 50 11822.7778 42673.6111 51 12058.3333 42195.5556 52 11003.6111 42102.5000 53 11003.6111 42102.5000 54 11003.6111 42102.5000 55 11522.2222 42841.9444 56 12386.6667 43334.7222 57 12386.6667 43334.7222 58 12386.6667 43334.7222 59 11569.4444 43136.6667 60 11569.4444 43136.6667 61 11569.4444 43136.6667 62 11155.8333 42712.5000 63 11155.8333 42712.5000 64 11155.8333 42712.5000 65 11155.8333 42712.5000 66 11133.3333 42885.8333 67 11133.3333 42885.8333 68 11133.3333 42885.8333 69 11133.3333 42885.8333 70 11133.3333 42885.8333 71 11003.6111 42102.5000 72 11770.2778 42651.9444 73 11133.3333 42885.8333 74 11690.5556 42686.6667 75 11690.5556 42686.6667 76 11751.1111 42814.4444 77 12645.0000 42973.3333 78 12421.6667 42895.5556 79 12421.6667 42895.5556 80 11485.5556 43187.2222 81 11423.8889 43000.2778 82 11423.8889 43000.2778 83 11715.8333 41836.1111 84 11297.5000 42853.3333 85 11297.5000 42853.3333 86 11583.3333 43150.0000 87 11569.4444 43136.6667 88 12286.9444 43355.5556 89 12355.8333 43156.3889 EOF
Тип данных: координаты городов 1 6734 1453 2 2233 10 3 5530 1424 4 401 841 5 3082 1644 6 7608 4458 7 7573 3716 8 7265 1268 9 6898 1885 10 1112 2049 11 5468 2606 12 5989 2873 13 4706 2674 14 4612 2035 15 6347 2683 16 6107 669 17 7611 5184 18 7462 3590 19 7732 4723 20 5900 3561 21 4483 3369 22 6101 1110 23 5199 2182 24 1633 2809 25 4307 2322 26 675 1006 27 7555 4819 28 7541 3981 29 3177 756 30 7352 4506 31 7545 2801 32 3245 3305 33 6426 3173 34 4608 1198 35 23 2216 36 7248 3779 37 7762 4595 38 7392 2244 39 3484 2829 40 6271 2135 41 4985 140 42 1916 1569 43 7280 4899 44 7509 3239 45 10 2676 46 6807 2993 47 5185 3258 48 3023 1942 EOF
1 8 38 31 44 18 7 28 6 37 19 27 17 43 30 36 46 33 20 47 21 32 39 48 5 42 24 10 45 35 4 26 2 29 34 41 16 22 3 23 14 25 13 11 12 15 40 9 -1 EOF
Тип данных – транспонированная диагональная матрица 97 205 139 86 60 220 65 111 115 227 95 82 225 168 103 266 205 149 120 58 257 152 52 180 136 82 34 145 129 103 71 105 258 154 112 65 204 150 87 176 137 142 204 148 148 49 41 211 226 116 197 89 153 124 74 219 125 175 386 269 134 184 313 201 215 267 248 271 274 236 272 160 151 300 350 239 322 78 276 220 60 167 182 180 162 208 39 102 227 60 86 34 96 129 69 58 60 120 119 192 114 110 192 136 173 173 51 296 150 42 131 268 88 131 245 201 175 275 218 202 119 50 281 238 131 244 51 166 95 69 279 114 56 150 278 46 133 266 214 162 302 242 203 146 67 300 205 111 238 98 139 52 120 178 328 206 147 308 172 203 165 121 251 216 122 231 249 209 111 169 72 338 144 237 331 169 151 227 133 104 242 182 84 290 230 146 165 121 270 91 48 158 200 39 64 210 172 309 68 169 286 242 208 315 259 240 160 90 322 260 160 281 57 192 107 90 140 195 51 117 72 104 153 93 88 25 85 152 200 104 139 154 134 149 135 320 146 64 68 143 106 88 81 159 219 63 216 187 88 293 191 258 272 174 311 258 196 347 288 243 192 113 345 222 144 274 124 165 71 153 144 86 57 189 128 71 71 82 176 150 56 114 168 83 115 160 61 165 51 32 105 127 201 36 254 196 136 260 212 258 234 106 110 56 49 91 153 91 197 136 94 225 151 201 205 215 159 64 126 128 190 98 53 78 218 48 127 214 61 155 157 235 47 305 243 186 282 261 300 252 105 100 176 66 253 183 146 231 203 239 204 113 152 127 150 106 52 235 112 179 221 79 163 220 119 164 135 152 153 114 236 201 90 195 90 127 84 91 273 226 148 296 238 291 269 112 130 286 74 155 291 130 178 38 75 180 281 120 205 270 213 145 36 94 217 162
Тип данных: полная матрица 0 107 241 190 124 80 316 76 152 157 283 133 113 297 228 129 348 276 188 150 65 341 184 67 221 169 108 45 167 107 0 148 137 88 127 336 183 134 95 254 180 101 234 175 176 265 199 182 67 42 278 271 146 251 105 191 139 79 241 148 0 374 171 259 509 317 217 232 491 312 280 391 412 349 422 356 355 204 182 435 417 292 424 116 337 273 77 190 137 374 0 202 234 222 192 248 42 117 287 79 107 38 121 152 86 68 70 137 151 239 135 137 242 165 228 205 124 88 171 202 0 61 392 202 46 160 319 112 163 322 240 232 314 287 238 155 65 366 300 175 307 57 220 121 97 80 127 259 234 61 0 386 141 72 167 351 55 157 331 272 226 362 296 232 164 85 375 249 147 301 118 188 60 185 316 336 509 222 392 386 0 233 438 254 202 439 235 254 210 187 313 266 154 282 321 298 168 249 95 437 190 314 435 76 183 317 192 202 141 233 0 213 188 272 193 131 302 233 98 344 289 177 216 141 346 108 57 190 245 43 81 243 152 134 217 248 46 72 438 213 0 206 365 89 209 368 286 278 360 333 284 201 111 412 321 221 353 72 266 132 111 157 95 232 42 160 167 254 188 206 0 159 220 57 149 80 132 193 127 100 28 95 193 241 131 169 200 161 189 163 283 254 491 117 319 351 202 272 365 159 0 404 176 106 79 161 165 141 95 187 254 103 279 215 117 359 216 308 322 133 180 312 287 112 55 439 193 89 220 404 0 210 384 325 279 415 349 285 217 138 428 310 200 354 169 241 112 238 113 101 280 79 163 157 235 131 209 57 176 210 0 186 117 75 231 165 81 85 92 230 184 74 150 208 104 158 206 297 234 391 107 322 331 254 302 368 149 106 384 186 0 69 191 59 35 125 167 255 44 309 245 169 327 246 335 288 228 175 412 38 240 272 210 233 286 80 79 325 117 69 0 122 122 56 56 108 175 113 240 176 125 280 177 266 243 129 176 349 121 232 226 187 98 278 132 161 279 75 191 122 0 244 178 66 160 161 235 118 62 92 277 55 155 275 348 265 422 152 314 362 313 344 360 193 165 415 231 59 122 244 0 66 178 198 286 77 362 287 228 358 299 380 319 276 199 356 86 287 296 266 289 333 127 141 349 165 35 56 178 66 0 112 132 220 79 296 232 181 292 233 314 253 188 182 355 68 238 232 154 177 284 100 95 285 81 125 56 66 178 112 0 128 167 169 179 120 69 283 121 213 281 150 67 204 70 155 164 282 216 201 28 187 217 85 167 108 160 198 132 128 0 88 211 269 159 197 172 189 182 135 65 42 182 137 65 85 321 141 111 95 254 138 92 255 175 161 286 220 167 88 0 299 229 104 236 110 149 97 108 341 278 435 151 366 375 298 346 412 193 103 428 230 44 113 235 77 79 169 211 299 0 353 289 213 371 290 379 332 184 271 417 239 300 249 168 108 321 241 279 310 184 309 240 118 362 296 179 269 229 353 0 121 162 345 80 189 342 67 146 292 135 175 147 249 57 221 131 215 200 74 245 176 62 287 232 120 159 104 289 121 0 154 220 41 93 218 221 251 424 137 307 301 95 190 353 169 117 354 150 169 125 92 228 181 69 197 236 213 162 154 0 352 147 247 350 169 105 116 242 57 118 437 245 72 200 359 169 208 327 280 277 358 292 283 172 110 371 345 220 352 0 265 178 39 108 191 337 165 220 188 190 43 266 161 216 241 104 246 177 55 299 233 121 189 149 290 80 41 147 265 0 124 263 45 139 273 228 121 60 314 81 132 189 308 112 158 335 266 155 380 314 213 182 97 379 189 93 247 178 124 0 199 167 79 77 205 97 185 435 243 111 163 322 238 206 288 243 275 319 253 281 135 108 332 342 218 350 39 263 199 0
1 1150.0 1760.0 2 630.0 1660.0 3 40.0 2090.0 4 750.0 1100.0 5 750.0 2030.0 6 1030.0 2070.0 7 1650.0 650.0 8 1490.0 1630.0 9 790.0 2260.0 10 710.0 1310.0 11 840.0 550.0 12 1170.0 2300.0 13 970.0 1340.0 14 510.0 700.0 15 750.0 900.0 16 1280.0 1200.0 17 230.0 590.0 18 460.0 860.0 19 1040.0 950.0 20 590.0 1390.0 21 830.0 1770.0 22 490.0 500.0 23 1840.0 1240.0 24 1260.0 1500.0 25 1280.0 790.0 26 490.0 2130.0 27 1460.0 1420.0 28 1260.0 1910.0 29 360.0 1980.0 EOF
1 28 6 12 9 26 3 29 5 21 2 20 10 4 15 18 14 17 22 11 19 25 7 23 8 27 16 13 24 -1 EOF
bays29: лучший тур 1 28 6 12 9 26 3 29 5 21 2 20 10 4 15 18 14 17 22 11 19 25 7 23 8 27 16 13 24 -1 EOF
Тип данных: эвклидовы координаты 1 565.0 575.0 2 25.0 185.0 3 345.0 750.0 4 945.0 685.0 5 845.0 655.0 6 880.0 660.0 7 25.0 230.0 8 525.0 1000.0 9 580.0 1175.0 10 650.0 1130.0 11 1605.0 620.0 12 1220.0 580.0 13 1465.0 200.0 14 1530.0 5.0 15 845.0 680.0 16 725.0 370.0 17 145.0 665.0 18 415.0 635.0 19 510.0 875.0 20 560.0 365.0 21 300.0 465.0 22 520.0 585.0 23 480.0 415.0 24 835.0 625.0 25 975.0 580.0 26 1215.0 245.0 27 1320.0 315.0 28 1250.0 400.0 29 660.0 180.0 30 410.0 250.0 31 420.0 555.0 32 575.0 665.0 33 1150.0 1160.0 34 700.0 580.0 35 685.0 595.0 36 685.0 610.0 37 770.0 610.0 38 795.0 645.0 39 720.0 635.0 40 760.0 650.0 41 475.0 960.0 42 95.0 260.0 43 875.0 920.0 44 700.0 500.0 45 555.0 815.0 46 830.0 485.0 47 1170.0 65.0 48 830.0 610.0 49 605.0 625.0 50 595.0 360.0 51 1340.0 725.0 52 1740.0 245.0 EOF
1 49 32 45 19 41 8 9 10 43 33 51 11 52 14 13 47 26 27 28 12 25 4 6 15 5 24 48 38 37 40 39 36 35 34 44 46 16 29 50 20 23 30 2 7 42 21 17 3 18 31 22 -1 EOF
Тип данных: эвклидовы координаты городов 1 37 52 2 49 49 3 52 64 4 20 26 5 40 30 6 21 47 7 17 63 8 31 62 9 52 33 10 51 21 11 42 41 12 31 32 13 5 25 14 12 42 15 36 16 16 52 41 17 27 23 18 17 33 19 13 13 20 57 58 21 62 42 22 42 57 23 16 57 24 8 52 25 7 38 26 27 68 27 30 48 28 43 67 29 58 48 30 58 27 31 37 69 32 38 46 33 46 10 34 61 33 35 62 63 36 63 69 37 32 22 38 45 35 39 59 15 40 5 6 41 10 17 42 21 10 43 5 64 44 30 15 45 39 10 46 32 39 47 25 32 48 25 55 49 48 28 50 56 37 51 30 40 EOF
1 22 8 26 31 28 3 36 35 20 2 29 21 16 50 34 30 9 49 10 39 33 45 15 44 42 40 19 41 13 25 14 24 43 7 23 48 6 27 51 46 12 47 18 4 17 37 5 38 11 32 -1 EOF
Тип данных: эвклидовы координаты городов 1 22 22 2 36 26 3 21 45 4 45 35 5 55 20 6 33 34 7 50 50 8 55 45 9 26 59 10 40 66 11 55 65 12 35 51 13 62 35 14 62 57 15 62 24 16 21 36 17 33 44 18 9 56 19 62 48 20 66 14 21 44 13 22 26 13 23 11 28 24 7 43 25 17 64 26 41 46 27 55 34 28 35 16 29 52 26 30 43 26 31 31 76 32 22 53 33 26 29 34 50 40 35 55 50 36 54 10 37 60 15 38 47 66 39 30 60 40 30 50 41 12 17 42 15 14 43 16 19 44 21 48 45 50 30 46 51 42 47 50 15 48 48 21 49 12 38 50 15 56 51 29 39 52 54 38 53 55 57 54 67 41 55 10 70 56 6 25 57 65 27 58 40 60 59 70 64 60 64 4 61 36 6 62 30 20 63 20 30 64 15 5 65 50 70 66 57 72 67 45 42 68 38 33 69 50 4 70 66 8 71 59 5 72 35 60 73 27 24 74 40 20 75 40 37 76 40 40 EOF
1 33 63 16 3 44 32 9 39 72 58 10 31 55 25 50 18 24 49 23 56 41 43 42 64 22 61 21 47 36 69 71 60 70 20 37 5 15 57 13 54 19 14 59 66 65 38 11 53 7 35 8 46 34 52 27 45 29 48 30 4 75 76 67 26 12 40 17 51 6 68 2 74 28 62 73 -1 EOF
Эта задача имеет следующую неформальную простую постановку [4,5]. Имеется рюкзак объемом $$C$$ и $$n$$ различных предметов. Каждый предмет $$i$$ имеет известный объем $$W_i$$ и стоимость $$P_i(i=1,\dots,n)$$. В рюкзак можно положить целое число различных предметов. Нужно упаковать рюкзак так, чтобы полная стоимость уложенных предметов была максимальной, а их общий объем не превышал заданный объем $$C$$. Форма предметов здесь не учитывается.
Формальная постановка задачи: для данного множества весов $$W_i$$, стоимостей $$P_i$$ и объема $$C$$ надо найти двоичный вектор $$X=(x_1,\dots,x_n)\mbox{, где}\ x_i=\begin{cases}1,\mbox{если предмет помещается в рюкзак,}\\0,\mbox{в противном случаи.}\end{cases}$$
и при этом должно выполняться условие:
$$V=\sum_{i=1}^n W_i\le C\mbox{ и }\sum_{i=1}^n P_i=\max$$Так как решение задачи можно представить двоичным вектором $$X= (x_1,\dots, x_n)$$, то очевидно при его поиске можно применить простой ГА со стандартными операторами скрещивания и мутации. Но при этом на каждом шаге итерации надо следить за тем, чтобы новые решения, полученные в результате скрещивания или мутации, удовлетворяли требуемому ограничению $$V\le C$$. В случае невыполнения ограничения "неправильное" потенциальное решение должно быть уничтожено, что ведет к сокращению популяции.
В качестве фитнесс-функции в простейшем случае можно взять $$P(X)=\sum_{i=1}^n x_i\cdot P_i,$$ но в этом случае, как указано выше, есть проблемы с неправильными решениями.
Данная задача относится к классу задач с ограничениями, при решении которых применяются следующие подходы [4,5]: 1) введение в фитнесс-функцию дополнительного штрафа; 2) использование алгоритмов "восстановления" некорректных решений.
Разработано множество методов назначения штрафных значений, из которых ниже рассмотрено только три вида, когда рост значения штрафной функции относительно степени нарушения ограничения имеет логарифмический, линейный и квадратичный характер:
Здесь для всех трех случаев $$\rho = \max_{1 \le i \le n} {P_i/w_i}$$.
Второй подход к решению задач с ограничениями основан на специальных алгоритмах "восстановления" некорректных решений. Следует отметить, что многие алгоритмы восстановления требуют значительных вычислительных ресурсов, и полученные решения иногда требуют адаптации к конкретным практическим приложениям.
В этом случае в качестве фитнесс-функции используется $$f(X')=\sum_{i=1}^n x_i'P_i,$$ где вектор $$X'$$– восстановленная версия исходного вектора $$X$$. Здесь следует отметить, по крайней мере, два аспекта. Во-первых, можно использовать различные алгоритмы восстановления. Во-вторых, восстановленные особи могут замещать только некоторую часть исходных особей в популяции. Процент замещаемых особей может варьироваться от 0% до 100% и его значение является важнейшим параметром метода восстановления. В некоторых работах отмечается, что наилучшие результаты получаются при 5%, во всяком случае, лучше, чем в двух крайних случаях – 0% (без замещения) и 100% (любая восстановленная особь заменяет исходную). Ниже приведен простой алгоритм восстановления.
При этом используются два основных способа выбора объекта:
Третий подход к решению задач с ограничениями использует специальное отображение (декодирование) особей, которое гарантирует генерацию допустимого решения (с учетом ограничений), или используют проблемно-ориентированные генетические операторы, сохраняющие корректность решения.
Рассмотрим один из возможных вариантов алгоритма декодирования, который основан на кодировании решения вектором целых чисел, так называемом "упорядоченном представлении" (ordinal representation), подробно описанном в разделе 3.3.2. Здесь каждая хромосома кодируется вектором $$e$$ целых чисел, где $$i$$-я компонента вектора – есть целое число в диапазоне от 1 до $$n-i+1$$. "Упорядоченное представление" использует для ссылок (базовый) список предметов $$L$$. Вектор $$e$$ фактически содержит указатели на базовый список $$L$$. Декодирование вектора осуществляется путем выбора соответствующего предмета из текущего списка и удаления его из базового списка. Например, при базовом списке предметов $$L=(1,2,3,4,5,6)$$ текущий вектор $$e=(4,3,4,1,1,1)$$ декодируется в следующую последовательность предметов: 4, 3, 6, 1,2, 5. Первым в рюкзак включается четвертый элемент списка $$L$$- 4, который устраняется из $$L$$. Далее в рюкзак включается третий элемент из текущего списка $$L$$. Затем включается 6 - четвертый элемент текущего $$L$$ и т.д. Подробнее описание этого представления и выполнение кроссинговера на нем описано в разделе 2.3.2. В данном методе хромосома может интерпретироваться как стратегия (порядок) включения предметов в решение. Отметим, что основным достоинством данного кодирования хромосомы является то, что на нем работает одноточечный кроссинговер. То есть для двух допустимых решений –родителей кроссинговер порождает также допустимое решение–потомок. Оператор мутации при данном представлении выполняется путем замены $$i$$-го гена (целочисленной компоненты вектора) на случайное целое число из диапазона $$[1,\dots,n-i+1]$$.
Очевидно, что представленный алгоритм зависит от способа генерации списка предметов $$L$$. Обычно используются два метода генерации этого списка:
Очевидно, здесь решение можно также представить двоичным вектором
$$X=(x_1,\dots,x_n)$$, где
$$x_i=1$$, если подмножество $$F_i$$ входит в покрытие;
$$x_i=0$$, если $$F_i$$ не входит в покрытие;
и при этом
$$\bigcup_{i=1,\dots,n} x_i F_i=S,$$$$\sum_{i=1}^n x_i=\min$$
Поскольку решение задачи, как было показано выше, представляется двоичным вектором, то при его поиске можно использовать простой ГА со стандартными операторами кроссинговера и мутации.
Напомним неформальную постановку этой классической задачи. Коммивояжер (бродячий торговец) должен выйти из первого города, посетить по одному разу в некотором порядке все города и вернуться в исходный город. На рис.2.1 приведен пример задачи для четырех городов.
Расстояния между городами известны. В каком порядке следует обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим?
(рис 2.1) Задача коммивояжера
В формальной постановке задачи коммивояжера (ЗК): имеется полный взвешенный ориентированный граф $$G$$ без петель с множеством вершин $$N=\{1,2,\dots,n\}$$; веса всех дуг неотрицательны; в этом графе требуется найти гамильтонов цикл с минимальной длиной. Исходная информация по ЗК представляется в виде $$n\times n$$ матрицы $$S=[s_{i,j}],s_{i,j}$$ вес дуги $$(i,j)$$ графа $$G$$, $$i=\overline{1,n}$$, $$j=\overline{1,n}$$, $$i\ne j$$; все элементы главной диагонали нулевые $$s_{ii}=0$$(но в некоторых постановках полагаются $$s_{ii}=\infty$$). Обычно $$s_{ij}$$ интерпретируется как расстояние между городами $$i$$ и $$j$$. С учетом других возможных интерпретаций на матрицу $$S$$ требование симметричности не налагается. Например, в случае интерпретации $$s_{ij}$$ как стоимости проезда, в общем случае может быть $$s_{ij}\ne s_{ji}$$. В общем случае не считается обязательным и выполнение неравенства треугольника $$s_{ij}+ s_{jk}\ge s_{ik}$$.
Тур коммивояжера может быть описан циклической перестановкой $$t=(j_1,j_2,\dots,j_n,j_1)$$, причём все $$j_1,\dots,j_n$$– попарно различны; повторяющийся в начале и в конце номер города $$j_1$$, показывает, что перестановка циклическая. Пространством поиска решений этой задачи является множество перестановок $$n$$ городов. Любая простая (одиночная) перестановка $$n$$ городов даёт решение, являющееся полным туром из $$n$$ городов. Оптимальным решением является перестановка, которая даёт минимальную стоимость тура. Очевидно, размерность пространства поиска для несимметричной задачи равна $$(n-1)!$$. Известно, что эта задача является NP – полной, т.е. переборной. Она имеет многочисленные практические приложения, в которых число "городов" может быть достаточно большим. Например, при производстве сложных деталей задача сверления отверстий может иметь сотни и тысячи "городов". При производстве СБИС возникают задачи (например, по внесению примесей в полупроводник) с числом "городов" около миллиона. За последние десятилетия разработано достаточно много алгоритмов решения этой задачи, дающих субоптимальное решение. В последнее десятилетие эта задача является базовой для исследования ГА в области
Очевидно, что двоичное представление тура при решении ЗК нецелесообразно. Действительно если мы интересуемся оптимальной перестановкой городов, т.е. $$(i_1,i_2, \dots , i_n)$$ и используем двоичное представление в виде одного бинарного вектора, то изменение даже в одном бите двоичного кода перестановки может дать двоичный вектор, не принадлежащий к области решения, т.е. не являющейся перестановкой $$n$$ городов.
Для решения ЗК с помощью генетических алгоритмов разработаны специальные методы представления (кодирования) решений и соответствующие
В этом случае тур представляется списком из n городов, где $$i$$-й элемент списка имеет номер от 1 до $$n-i+1$$. При этом используется базовый упорядоченный список городов $$L$$, который служит для ссылок упорядоченного представления. Фактически мы рассматривали этот метод кодирования решения при решении
Рассмотрим его на конкретном примере тура $$T$$= (1-2-4-3-8-5-9-6-7), для которого упорядоченный список $$L$$= (1 2 3 4 5 6 7 8 9). Тогда данный тур при этом упорядоченном списке представляется следующим списком ссылок $$e$$=(1 1 2 1 4 1 3 1 1), который интерпретируется следующим образом. Здесь жирным курсивом выделен текущий указатель в списке $$e$$.
Первый номер из списка $$e$$ равен 1, поэтому помещаем в тур 1-й город из базового списка $$L$$, удаляем его из $$L$$ и сдвигаем указатель по $$e$$. Тогда получаем:
тур $$T_1$$=(1), базовый список $$L_1$$= (2 3 4 5 6 7 8 9) , указатель $$e$$=(1 1 2 1 4 1 3 1 1).
Следующий номер по указателю $$e$$ также равен 1, поэтому снова помещаем в тур 1-й город из базового списка $$L$$, удаляем его из $$L$$ и сдвигаем указатель по $$e$$.
В результате получаем :
текущий тур $$T_2$$=( 1-2), $$L_1$$= (3 4 5 6 7 8 9) и указатель в e сдвигается на третью позицию $$e$$= (1 1 2 1 4 1 3 1 1). Следующий номер списка е равен 2, поэтому мы берем и удаляем 2-й город из текущего базового списка $$L$$ и добавляем его в тур и передвигаем указатель по $$e$$. Имеем:
текущий тур $$T_3$$=(1-2-4), $$L$$ = (3 5 6 7 8 9), $$e$$ = (1 1 2 1 4 1 3 1 1).
Продолжая этот процесс, в результате декодирования по данному коду $$e$$=(1 1 2 1 4 1 3 1 1), базовому списку $$L$$= (1 2 3 4 5 6 7 8 9) будет построен тур $$T$$= (1-2-4-3-8-5-9-6-7) .
Основное преимущество упорядоченного представления в том, что в этом случае работает классический кроссинговер (над векторами целых чисел). То есть для двух допустимых решений кроссинговер производит два допустимых решения – потомка.
Например, для родителей
$$e_1$$= (1 1 2 1 | 4 1 3 1 1) и $$e_2$$ = (5 1 5 5 | 5 3 3 2 1),
которые соответствуют турам
$$T_1$$=(1-2-4-3-8-5-9-6-7) и $$T_2$$=(5-1-7-8-9-4-6-3-2),
имеем следующих потомков при скрещивании
$$O_1$$= (1 1 2 1 5 3 3 2 1) и $$O_2$$= (5 1 5 5 4 1 3 1 1),
которые представляют туры
$$T_3$$=(1-2-4-3-9-7-8-6-5) и $$T_4$$=(5-1-7-8-6-2-9-3-4).
Очевидно, что частичные туры слева от точки кроссинговера не изменяются, в тоже время частичные туры справа от нее разрываются случайным образом (сохраняя корректность решения). К сожалению, машинные эксперименты по решению ЗК на основе этого представления решений с использованием классического кроссинговера показывают посредственные результаты [4].
В этом случае тур представляется списком соседних городов. Город $$j$$ находится в позиции $$i$$ если и только если в туре после города $$i$$ посещается город $$j$$, что показано на рис.2.2
(рис 2.2) Следование городов в туре
Например, вектор $$n_1$$=(2 4 8 3 9 7 1 5 6) представляет следующий тур $$T_1$$=(1-2-4-3-8-5-9-6-7). При этом любой тур имеет единственное представление списком соседства. Однако некоторые "списки соседей" могут представлять "неправильные" туры. Например, список соседства $$n_2$$=(2 4 8 1 9 3 5 7 6) содержит "частичный" тур $$T_2$$=(1-2-4-1). Поэтому представление списком соседей не поддерживает классический оператор кроссинговера, поскольку при перестановке частей списков могут получаться неправильные ("частичные") туры. В этом случае необходим некоторый алгоритм восстановления полного тура.
Для данного способа кодирования решения были предложены и исследованы 3 основных оператора кроссинговера: 1) обмен ребер (дуг) графа; 3) обмен подтуров; 3) эвристический кроссинговер [2,3,4]. Далее рассмотрим их детально.
Этот тип кроссинговера строит потомка (случайным) выбором ребра (пары городов $$i-j$$) из первого родителя, затем выбором соответствующего ребра из второго родителя и т.д. Оператор наращивает тур выбором ребер из различных родителей. Если новое ребро (взятое у одного из родителей) образует преждевременный (частичный) цикл в текущем (ещё не полном) туре, то оператор выбирает (случайно) вместо этого ребра одно из оставшихся ребер, которое не дает преждевременного цикла.
Например, для 2-х родителей $$n_1$$= (2 3 8 7 9 4 1 5 6), представляющего тур $$T_1$$=(1-2-3-8-5-9-6-4-7-1), и $$n_2$$= (7 5 1 6 9 2 8 4 3), представляющего тур $$T_2$$=(1-7-8-4-6-2-5-9-3-1), получаем следующего потомка $$\sigma_1$$= (2 5 8 7 9 4 3 1 6). Здесь произведен обмен (случайный) ребер $$3\leftrightarrow 5$$ во второй позиции, далее при попытке обмена $$3\leftrightarrow 5$$ в седьмой позиции возникает конфликт (два ребра входят в 8), поэтому случайно выбирается 3 в позиции 7 ( из оставшихся 6, 1, 3), 1 – в позиции 8 и 6 в позиции 9. В результате порождается потомок $$\sigma_1$$, который соответствует туру $$T_3$$=(1-2-5-9-6-4-7-3-8-1).
Этот оператор строит потомки путём выбора (случайной длины) подтура из первого родителя, затем выбора подтура (опять случайной длины) из второго родителя и их обмена. Как и ранее, в случае конфликта оператор случайно выбирает другое ребро (город) из не вошедших в построенный тур.
Данный оператор строит потомка случайным выбором города в качестве начальной точки для формирования тура. Затем сравниваются два ребра, исходящие из этого города, имеющихся в двух родителях, и из них выбирается лучшее с меньшей стоимостью. Полученный город (в него входит выбранное ребро на предыдущем этапе), используется в качестве начальной точки при выборе следующего ребра и т.д. Как и ранее, в случае возникновения преждевременного цикла, следующий город выбирается случайно из городов, еще не вошедших в текущий тур. Известна следующая модификация этого оператора.
Если оптимальное (с меньшей стоимостью) ребро дает преждевременный цикл в потомке, то проверяется альтернативное ребро (с большей стоимостью) на генерацию преждевременного цикла. Если это ребро не генерирует цикл, то оно включается в тур, иначе выбирается минимальное из $$q$$ ребер (где $$q$$–параметр пула выбора) случайно выбранных из оставшихся городов.
Преимущество этого кодирования в том, что в этом случае анализ схем (шаблонов) можно проводить по аналогии с двоичным случаем. Например, схема (* * * 3 *7 * * *) представляет множество всех туров с ребрами (4-3) и (6-7). Однако основной недостаток этого представления в весьма посредственных результатах тестовых задач для всех трех рассмотренных операторов. Кроссинговер обмена ребер часто разрывает хорошие туры при обмене ребер родителей. Кроссинговер обмена подтуров даёт лучшие результаты, чем предыдущий, так как "отношение разрыва" здесь меньше. Эвристический оператор даёт несколько лучшие результаты за счет учета стоимости исходящих ребер и локального выбора лучшего варианта из двух возможных. Однако эксперименты показывают также посредственные результаты [4].
Это представление, возможно, самое естественное для тура. Например, тур (5-1-7-8-9-4-6-2-3) представляется просто упорядоченным списком (5 1 7 8 9 4 6 2 3) городов, входящих в тур.
Для данного представления были определены и исследованы три типа кроссинговера [2,3,4]:
Рассмотрим их по порядку.
Частично соответствующий ОК (РМХ) строит потомок путем выбора последовательности тура из одного родителя и сохранения порядка и позиции городов из другого родителя насколько это возможно. Подпоследовательность из тура выбирается случайно с помощью двух "секущих" точек, которые служат границами для операции обмена. Например, для родителей $$P_1$$=(1 2 3 | 4 5 6 7| 8 9) и $$P_2$$= (4 5 2 | 1 8 7 6 | 9 3) потомок строится следующим образом.
Сначала производим обмен выделенными подтурами и в результате получаем $$T_1$$ = (X X X | 1 8 7 6 | X X) и $$T_2$$= (X X X | 4 5 6 7 | X X), где "X" означает еще незаполненную позицию (допускающую произвольное значение). Этот обмен определяет также отображение $$1\leftrightarrow 4,8\leftrightarrow 5,7\leftrightarrow 6$$. Далее (вместо "Х") вставляем города из исходных родителей, для которых нет конфликтов (не образуются преждевременный цикл): $$O_1$$= (X 2 3 | 1 8 7 6 | X 9), $$O_2$$= (X X 2 | 4 5 6 7 | 9 3).
Далее первый "Х" в $$O_1$$, заменяем на "4" согласно отображению $$1\leftrightarrow 4$$. Аналогично второй "Х" в потомке $$O_1$$ заменяется "5", и во втором потомке $$O_2$$ оставшиеся неопределенные позиции "Х" заменяются соответственно на 1 и 8. В результате получаем два потомка: $$O_1$$= (4 2 3 | 1 8 7 6 | 5 9) и $$O_2$$= ( 1 8 2 | 4 5 6 7 | 9 3).
Упорядоченный ОК строит потомок выбором подтура из одного родителя и сохранением относительного порядка городов из другого родителя. Например, для родителей $$P_1$$= (1 2 3 | 4 5 6 7 | 8 9), $$P_2$$= (4 5 2 | 1 8 7 6 | 9 3) потомок строится следующим образом.
Сначала сегменты между двумя секущими точками копируется в потомки: $$O_1$$= (X X X | 4 5 6 7 | X X), $$O_2$$= (X X X | 1 8 7 6 | X X).
Далее, в первом родителе, начиная со второй секущей точки, копируются города из другого родителя, пропуская уже присутствующие в построенном подтуре. По достижению конца списка этот процесс продолжается с первой позиции и до первой точки сечения (по кольцу).
Для нашего примера после второй точки сечения во втором родителе мы имеем следующую последовательность: 9 – 3 – 4 – 5 – 2 – 1 – 8 – 7 – 6. Удаляем из нее города 4, 5, 6, 7, поскольку они уже есть в первом потомке, и в результате получаем последовательность 9 – 3 – 2 – 1 – 8. Ее мы помещаем в первый потомок, начиная со второй точки сечения (по кольцу) и получаем потомок $$O_1$$= (2 1 8 | 4 5 6 7 | 9 3). Аналогично получаем второго потомка $$O_2$$ = (3 4 5 | 1 8 7 6 | 9 2).
Оператор кроссинговера ОХ опирается на то, что при представлении тура прежде всего важен порядок городов, например, два тура (9–3–4–5–2–1–8–7–6) и (4–5–2–1–8–7–6–9–3) идентичны.
Циклический ОК строит потомки таким образом, что каждый город вместе со своей позицией идет от одного из родителей. Например, для родителей $$P_1$$= (1 2 3 4 5 6 7 8 9) и $$P_2$$= (4 1 2 8 7 6 9 3 5) сначала получаем путем выбора первого города из родителя $$O_1$$= (1X X X X X X X X). Выбор следующего города определяет текущая позиция второго родителя. В нашем примере это город 4, что дает $$O_1$$= (1 X X 4 X X X X X). Город 4 в свою очередь имплицирует город 8 (из второго родителя), что дает $$O_1$$= (1 X X 4 X X X 8 X).
Аналогично получаем города 3, 2 в $$O_1$$= (1 2 3 4 X X X 8 X). Здесь мы вынуждены прервать этот процесс, так как выбор $$2\to 1$$ ведет к преждевременному циклу. Поэтому оставшиеся города берутся из другого родителя $$P_2$$(с сохранением порядка) и в результате получаем потомков $$O_1$$= (1 2 3 4 7 6 9 8 5 ) и $$O_2$$= (4 1 2 8 5 6 7 3 9). Таким образом, оператор ОК СХ сохраняет абсолютные позиции потомков и родителей.
Опубликовано достаточно много работ [2,3,4,5,6], где для решения
В матрице смежности элемент $$m_{ij}=1$$ в том и только случае, если в туре после города $$i$$ посещается город $$j$$(в графе есть ребро от вершины $$i$$ в вершину $$j$$). Например, табл.2.1 содержит матрицу смежности для тура $$T_1$$=(1-2-4-3-8-6-5-7-9) и табл.2.2 – матрицу смежности для тура $$T_2$$=(1-4-3-6-5-7-2-8-9).
Отметим, что в этом случае каждая строка и столбец матриц содержат одну единицу. Для матрицы смежности можно использовать одно- или двуточечный кроссинговер, где обмен производится, например, столбцами. Но в этом случае необходим дополнительный алгоритм восстановления, который позволяет восстанавливать полученные потомки до полных туров.
Рассмотрим, этот подход на примере двухточечного вертикального кроссинговера с точками скрещивания 2 и 6. При этом производится обмен столбцами (3,4,5,6) матриц смежности (табл.2.1 и табл.2.2). В результате получаем промежуточный результат в виде матриц, которые представлены табл.2.3 и табл.2.4. Обе матрицы не представляют правильных решений, но заметим, что суммарное число единиц в каждой из этих промежуточных матриц правильное (9 единиц).
На первом шаге алгоритма восстановления передвигаем 1 в матрице таким образом, чтобы каждая строка и столбец имели одну единицу. Например, в матрице табл.2.3 первая строка имеет две 1 (вместо одной). Поэтому "передвинем" $$m_{14}=1$$ в позицию $$m_{84}=1$$, а элемент $$m_{24}=1$$ в $$m_{34}=1$$, аналогично $$m_{86}=1$$ в $$m_{16}=1$$. В результате после выполнения первого этапа алгоритма восстановления получаем правильный тур для первого потомка $$T_3$$=(1-2-8-4-3-6-5-7-9), в то время как второй потомок содержит два подтура $$T_4$$=(1-6-5-7-2-8-9) (3-4).
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
| 4 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 5 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| 6 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| 7 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| 8 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| 9 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
| 3 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| 4 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 5 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| 6 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| 7 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 8 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| 9 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 3 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 |
| 4 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 5 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| 6 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| 7 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| 8 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 9 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 |
| 3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 4 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 5 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| 6 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| 7 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 8 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |
| 9 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Поэтому на втором этапе алгоритма восстановления обрабатываем только второй потомок. При этом необходимо разорвать частичные подтуры и объединить их в единый правильный тур. Это можно сделать, например, с помощью ребра 2-4, которое присутствует у одного из родителей. В результате получаем полный тур для второго потомка $$T_5$$=(1-6-5-7-2-4-3-8-9).
Рассмотрим представление тура в виде двоичной матрицы предшествования [4]. В этом случае элемент матрицы $$m_{ij}$$ равен 1, если и только если город $$i$$ предшествует (встречается в туре раньше) городу $$j$$. В противном случае $$m_{ij}=0$$. Отметим, что здесь имеется в виду не только непосредственное предшествование (город $$i$$ связан непосредственно с городом $$j$$) но и более "глубокое". Например, тур $$T_3$$=(3-1-2-8-7-4-6-9-5) представляется бинарной матрицей предшествования, которая показана в табл.2.5 Здесь элементы главной диагонали $$m_{ij}=0$$ и $$m_{ij}=1$$, если $$i$$-й город предшествует в туре $$j$$-му городу. Например, в первой строке город 1 предшествует в туре городам 2, 4, ….,9, но не предшествует городу 3.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
| 3 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
| 4 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 |
| 5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 6 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 |
| 7 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 |
| 8 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 1 |
| 9 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
В этом представлении тура матрица $$M$$ размерности $$n\times n$$ обладает следующими свойствами:
Если число единиц в матрице меньше чем $$\frac{n(n-1)}{2}$$, а два других требования выполняются, то города частично упорядочены. Это означает, что можно получить матрицу (по крайней мере одним способом), которая представляет правильный тур. На этой форме представления вводятся два новых генетических оператора кроссинговера: пересечение и объединение.
Оператор пересечения основан на том, что побитовое пересечение матриц дает матрицу, где:
Таким образом, можно получить матрицу, представляющую правильный тур. Например, для двух родителей $$P_1$$= (1-2-3-4-5-6-7-8-9) и $$P_2$$= (4-1-2-8-7-6-9-3-5), представляемых матрицами табл.2.6 и табл.2.7 соответственно, поэлементное пересечение этих матриц дает матрицу табл.2.8.
Частичный порядок городов определяемый матрицей табл.2.4 следующий:
Город 1 предшествует городам 2, 3, 5, 6, 7, 8, 9;
Город 2 предшествует городам 3, 5, 6, 7, 8, 9;
Город 3 предшествует 5;
Город 4 – 5, 6, 7, 8, 9
Города 6, 7, 8 предшествуют 9.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 3 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
| 4 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| 5 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 6 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| 7 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 8 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| 9 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
На заключительном этапе выполнения этого оператора выбирается один из родителей и в промежуточную матрицу (полученную после пересечения) добавляются некоторые единицы (чтобы их число было равно $$\frac{n(n-1)}{2}$$) путем анализа сумм строк и столбцов, которые восстанавливают полный тур с учетом соответствующего родителя.
В табл.2.8 для удобства показано число единиц по строкам и столбцам матрицы, которое, например, позволяет города разбить на подтуры или в некотором смысле эквивалентные группы. Анализ числа единиц в строках показывает, что тур должен начинаться с (1-2-4), остальные города можно разбить на группы (3,6,7,8) и (5,9). Анализ числа единиц по столбцам позволяет "выстроить" подтур (3-5-9), а для остальных трех городов можно выбрать, например, порядок (8-7-6). В результате получаем для потомка полный тур (1-2-4-8-7-6-3-5-9), который представлен матрицей табл.2.9, которая может быть получена из предыдущей табл.2.8.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| 1 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 |
| 2 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 |
| 3 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| 4 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 |
| 5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 6 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 1 |
| 7 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 |
| 8 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 |
| 9 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | N1 | |
| 1 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 7 |
| 2 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 6 |
| 3 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
| 4 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 5 |
| 5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 6 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 7 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 8 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 9 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| N1 | 0 | 1 | 2 | 0 | 4 | 3 | 3 | 3 | 6 |
Оператор объединения основан на том, что подмножество бит из одной матрицы может быть комбинировано с подмножеством бит из другой матрицы без потери свойства быть туром, если эти подмножества имеют пустое пересечение. Оператор разбивает множество городов на две непересекающиеся группы. При этом для первой группы городов копируются биты из первой матрицы, а для второй группы копируются биты из второй матрицы.
На заключительном этапе матрица достраивается путем анализа сумм для строк и столбцов аналогично операции пересечения. Например, два родителя $$P_1$$ и $$P_2$$, которые представлены табл.2.6 и табл.2.7, и разбиения городов {1, 2, 3, 4,} и {5, 6, 7, 8, 9} порождают матрицу табл.2.10.
Таким образом, для решения
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| 1 | 0 | 1 | (1) | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 0 | 0 | 1 | (1) | 1 | 1 | 1 | 1 | 1 |
| 3 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | (1) |
| 4 | 0 | 0 | (1) | 0 | 1 | 1 | 1 | 1 | 1 |
| 5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | (1) |
| 6 | 0 | 0 | (1) | 0 | (1) | 0 | 0 | 0 | 1 |
| 7 | 0 | 0 | (1) | 0 | (1) | (1) | 0 | 0 | 1 |
| 8 | 0 | 0 | (1) | 0 | (1) | (1) | (1) | 0 | 0 |
| 9 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| 1 | 0 | 1 | 1 | 1 | X | X | X | X | X |
| 2 | 0 | 0 | 1 | 1 | X | X | X | X | X |
| 3 | 0 | 0 | 0 | 1 | X | X | X | X | X |
| 4 | 0 | 0 | 0 | 0 | X | X | X | X | X |
| 5 | X | X | X | X | 0 | 0 | 0 | 0 | 0 |
| 6 | X | X | X | X | 1 | 0 | 0 | 0 | 1 |
| 7 | X | X | X | X | 1 | 1 | 0 | 0 | 1 |
| 8 | X | X | X | X | 1 | 1 | 1 | 0 | 1 |
| 9 | X | X | X | X | 1 | 0 | 0 | 0 | 0 |
Процесс диагностирования цифровых устройств (ЦУ) требует использования так называемой диагностической информации (ДИ). Для современных ЦУ эта информация имеет очень большой объем, что порождает значительные трудности при локализации неисправностей.
Если множество тестов $$T$$ таково, что для каждой пары неисправностей $$f_i,f_k\in F$$ найдется хотя бы один тестовый набор $$t_j\in T$$ такой, что $$R_{ij}\ne R_{kj}$$, то все строки ТФН попарно различны. Такое множество $$T$$ называется диагностическим тестом.
Понятно, что полная ТФН, содержащая информацию о реакциях ЦУ на все ее возможные входные наборы, имеет, как правило, очень большой объем и является избыточной для локализации рассматриваемых неисправностей. При диагностировании ЦУ обычно используется не ТФН, а $$T$$–ТФН, где $$T$$ – минимальное подмножество всех входных наборов ЦУ, позволяющее диагностировать неисправности из $$F$$. Заметим, что и $$T$$-ТФН также может содержать много избыточной информации. Упомянутую таблицу будем именовать словарем полной реакции (СПР) диагностируемого ЦУ.
Один из возможных способов сокращения объема СПР, в котором для каждого технического состояния ЦУ сохраняется часть полной реакции устройства в этом состоянии на тест $$T$$, выделенная с помощью некоторого шаблона, называемого маской [8].
Назовем точкой проверки номер выхода ЦУ, по которому будет наблюдаться реакция на тестовые наборы. Тогда маской $$h$$ назовем любую совокупность точек проверки.
С помощью маски $$h$$ из СПР можно выделить некоторую его часть. Содержательно выделение такой информации поясним следующим образом. В каждой клетке $$(i,j)$$ СПР расположена двоичная последовательность длины $$m$$, где $$m$$ – число выходов диагностируемого ЦУ, являющейся реакцией ЦУ в состоянии $$s_i$$ на $$j$$-й тестовый набор $$t_j$$ из множества $$T$$. Тогда маска $$h$$ соответствует"окошечкам" в битовой строке СПР, которые следует "прорезать", чтобы увидеть выделяемые маской биты реакции ЦУ на каждый тестовый набор из $$T$$.
Отметим, что СПР формируется с использованием логического моделирования до процесса диагностирования ЦУ. После завершения процесса диагностирования фиксируется реакция ЦУ на каждый тестовый набор $$t_i\in T$$. Затем с помощью используемой маски "фильтруется" как СПР, так и полученная реакция ЦУ на тестовое множество $$T$$, и выполняется сравнение соответствующих строк в них. Те из состояний $$s_i\in S$$, для которых произошло совпадение, заносятся в список подозреваемых неисправностей (СПН).
Пусть $$\{S_i\}$$, где $$S_i\subseteq S$$, есть множество всех возможных СПН, которые могут возникнуть при диагностировании ЦУ с использованием маски $$h$$, а $$P(S)$$- их количество. Понятно, что число таких СПН и число входящих в них неисправностей определяют достигаемую при диагностировании степень детализации и состав имеющихся в ЦУ неисправностей. Эту степень детализации называют разрешающей способностью диагностирования и вычисляют ее по формуле
$$\rho (h)=\frac{1}{P(S)}\sum_{S_i\subseteq S}|S_i|$$Из формулы следует, что $$\rho (h)$$ есть средняя длина всех возможных СПН.
Через $$\rho$$ обозначим разрешающую способностью диагностирования ЦУ, обеспечиваемую словарем полной реакции (СПР) с использованием того же теста $$T$$, что подразумевался и в формуле (2.1).
Из изложенного выше следует, что "фильтрация" исходного СПР с помощью некоторой маски $$h$$(обозначим его как $$СПР_h$$) может привести к существенному уменьшению объема исходного СПР.
Теперь сформулируем задачу сокращения ДИ, которая рассматривается далее. Для множества технических состояний $$S$$ диагностируемого ЦУ требуется найти такую маску $$h$$ минимальной длины, чтобы объем полученного с ее помощью $$СПР_h$$ был минимальным и при этом разрешающая способность $$\rho (h)$$ по маске $$h$$ равнялась разрешающей способности $$\rho$$ диагностирования, обеспечиваемой полным СПР.
Сформулированная задача является комбинаторныйи точное ее решение можно получить только с помощью перебора. Однако для современных ЦУ в связи с большим объемомдля них СПР реализация получения точного решения невозможна из-за чрезвычайно большой трудоемкости. По этой причине были предприняты попытки поиска иных подходов к решению упомянутой задачи.Одним из перспективных методов ее решения основан на использовании простого ГА, к детализации которого мы и перейдем.
Начнем с описания структуры хромосомы, применяемой в предлагаемом простом ГА[9]. Хромосому, соответствующую маске $$h$$, будем представлять в виде битовой последовательности $$\eta (h)$$ длины $$m$$:
$$\eta (h)=\eta_1(h)\eta_2(h)\dots \eta_m(h)$$где $$m$$- количество выходов ЦУ.Для каждой точки проверки $$i$$, входящей в состав маски $$h$$, значение $$\eta_i(h)$$ в (2.2) полагается равным 1. Все остальные разряды в $$\eta(h)$$ полагаются равными нулю.
Длиной маски $$h$$ будем называть величину $$|h|=\sum_{i=1}^m \eta_i(h)$$
Введем в рассмотрение величину $$V(h)=|h|/m$$, которая равна доли длины маски $$h$$ от длины реакции на любой тестовый набор по всем выходам ЦУ.
Для решения рассматриваемой задачи с применением простого ГА будем использовать следующую фитнесс-функцию:
$$d(\eta (h))=C\cdot(\rho-\rho(h))+V(h)$$где $$C$$— достаточно большая константа.
Поясним содержательный смысл функции (2.3). Поскольку по условиям задачи требуется найти такую маску $$h$$, которая должна обеспечить выполнение равенства $$\rho=\rho(h)$$, то первое слагаемое в (2.3) должно обратиться в ноль. Тогда максимальное сокращение ДИ будет, очевидно, достигнуто при минимальном значении $$V(h)$$, т.е. для маски минимальной длины. Таким образом, искомым решением будет такая маска, для которой фитнесс-функция (2.3) достигает минимального значения.
Из изложенного вытекает, что в процессе выполнения простого ГА близость очередной полученной маски к искомому решению (при большой константе $$C$$) будет определяться прежде всего значением первого слагаемого в (2.3), поскольку значение второго слагаемого не превышает 1. Иными словами, первое слагаемое при подходящем значении константы $$C$$ может служить индикатором удаленности полученной на очередном этапе выполнения ПГА маскиот искомой.
Описываемый ниже простой ГА содержит следующие этапы:
В предлагаемом ПГА начальная популяция (масок) формируется с использованием датчиков случайных величин. На втором этапе для каждой особи вычисляется значениефитнесс-функции (2.3). Отбор особей-кандидатов для участия в репродукции осуществляется по принципу: чем выше значение фитнесс-функции, тем выше вероятность ее участия в процессе скрещивания.На третьем этапе осуществляется скрещивание с использованием оператора однородного кроссинговера отобранных на предыдущем этапе особей, в результате которого производится два новых потомка путем обмена генами родительских особей. Полученные особи формируют новую популяцию. На четвертом этапе происходит мутация особей: случайным образом выбираются две позиции в маске, содержащие несовпадающие двоичные значения, и затем производится их перестановка. На пятом этапе из особей текущего поколения масок, а также полученных после скрещивания потомков, на основе метода элитного отбора формируется следующее поколение масок. В качестве условия окончания используется заранее определенное предельное число этапов эволюции (длина жизненного цикла популяции). В качестве решения принимается особь из последнего поколения с минимальным значением фитнесс-функции.
Для оценки эффективности предложенного ПГА были проведены численные эксперименты, в которых размер популяции подбирался опытным путем с целью ускорения сходимости к искомому решению. На втором этапе ПГА, связанном с селекцией особей, были опробованы различные методы и выбор был сделан в пользу линейного ранжированияю
Численные эксперименты проводились для реальных ЦУ из каталога $$ISKAS'89$$[10] при моделировании одиночных константных неисправностей на всех линиях ЦУ на вероятностных тестах. Каждый такой тест был составлен из 100 входных наборов.
В качестве примера в табл. 2.11 представлена динамика нахождения решения рассматриваемой задачи сокращения ДИ для четырех схем из названного выше каталога. Представленные в ней данные, а также статистические данные для других ЦУ из того же каталога показывают, что оптимальная численность популяции для предложенного ПГА – 100 особей, а для получения приемлемого по качеству решения достаточно 70 поколений. Поясним обозначения столбцов табл. 2.11. В первом ее столбце указаны имена ЦУ из названного каталога, во втором-длина реакции ЦУ на его выходах (в любом его техническом состоянии) на случайную входной тест из 100 входных наборов (в битах), в третьем – число всех возможных СПН, возникающих при диагностировании ЦУ, в четвертом – объем в битах, $$\rho_2(h)$$- значение ожидаемой разрешающей способности диагностирования (средней длины СПН) с использованием найденной лучшей маски.
| Схема | $$m|\tau|$$ | $$|S|$$ | Объем полной ДИ | Результат после 40 поколений | Результат после 60 поколений | Результат после 80 поколений | Доля сокращенной информации по отношению к полной | |||
|---|---|---|---|---|---|---|---|---|---|---|
| Длина маски | $$\rho_2(h)$$ | Длина маски | $$\rho_2(h)$$ | Длина маски | $$\rho_2(h)$$ | |||||
| S382 | 600 | 32 | 19 200 | 20 | 1.063 | 20 | 1.000 | 20 | 1.000 | 3.33% |
| S386 | 700 | 136 | 95 200 | 55 | 1.059 | 55 | 1.044 | 55 | 1.000 | 7.86% |
| S400 | 600 | 33 | 19 800 | 20 | 1.121 | 20 | 1.060 | 20 | 1.000 | 3.33% |
| S510 | 700 | 447 | 312 900 | 70 | 1.027 | 70 | 1.000 | 70 | 1.000 | 10.00% |
Приведенные результаты получены на PC Pentium III, 1024 MHz, 256 Mb RAM. Что касается временных затрат на работу ПГА, то они находились в диапазоне от нескольких секунд до 30 минут при объема СПР от 5 Kb до 2Mb.Как показала статистика, доля "сжатой" ДИ во всех названных экспериментах от объема полного СПР составляла от 3% до 15%, что несомненно является хорошим результатом. Таким образом, на основе приведенных данных можно говорить о достаточной эффективности предложенного ПГА и высоком его быстродействии.
Заметим, что подробно с задачами сокращения ДИ и методами их решения можно ознакомиться в [11].
| № варианта | Название функции | Вид представления |
|---|---|---|
| 1 | Wi29.tsp | Представление соседства |
| 2 | Dj89.tsp | Представление соседства |
| 3 | Att48.tsp | Представление соседства |
| 4 | Bayg29.tsp | Представление соседства |
| 5 | Bayg29.tsp | Представление соседства |
| 6 | Berlin52.tsp | Представление соседства |
| 7 | Eil51.tsp | Представление соседства |
| 8 | Eil76.tsp | Представление соседства |
| 9 | Wi29.tsp | Представление порядка |
| 10 | Dj89.tsp | Представление порядка |
| 11 | Att48.tsp | Представление порядка |
| 12 | Bayg29.tsp | Представление порядка |
| 13 | Bayg29.tsp | Представление порядка |
| 14 | Berlin52.tsp | Представление порядка |
| 15 | Eil51.tsp | Представление порядка |
| 16 | Eil76.tsp | Представление порядка |
| 17 | Wi29.tsp | Представление пути |
| 18 | Dj89.tsp | Представление пути |
| 19 | Att48.tsp | Представление пути |
| 20 | Bayg29.tsp | Представление пути |
| 21 | Bayg29.tsp | Представление пути |
| 22 | Berlin52.tsp | Представление пути |
| 23 | Eil51.tsp | Представление пути |
| 24 | Eil76.tsp | Представление пути |
Тестовые наборы (benchmarks) к упражнению представлены в трех формах:
Тип данных: эвклидовы координаты городов 1 20833.3333 17100.0000 2 20900.0000 17066.6667 3 21300.0000 13016.6667 4 21600.0000 14150.0000 5 21600.0000 14966.6667 6 21600.0000 16500.0000 7 22183.3333 13133.3333 8 22583.3333 14300.0000 9 22683.3333 12716.6667 10 23616.6667 15866.6667 11 23700.0000 15933.3333 12 23883.3333 14533.3333 13 24166.6667 13250.0000 14 25149.1667 12365.8333 15 26133.3333 14500.0000 16 26150.0000 10550.0000 17 26283.3333 12766.6667 18 26433.3333 13433.3333 19 26550.0000 13850.0000 20 26733.3333 11683.3333 21 27026.1111 13051.9444 22 27096.1111 13415.8333 23 27153.6111 13203.3333 24 27166.6667 9833.3333 25 27233.3333 10450.0000 26 27233.3333 11783.3333 27 27266.6667 10383.3333 28 27433.3333 12400.0000 29 27462.5000 12992.2222 EOF
Тип данных: эвклидовы координаты городов 1 11511.3889 42106.3889 2 11503.0556 42855.2778 3 11438.3333 42057.2222 4 11438.3333 42057.2222 5 11438.3333 42057.2222 6 11785.2778 42884.4444 7 11785.2778 42884.4444 8 11785.2778 42884.4444 9 11785.2778 42884.4444 10 12363.3333 43189.1667 11 11846.9444 42660.5556 12 11503.0556 42855.2778 13 11963.0556 43290.5556 14 11963.0556 43290.5556 15 12300.0000 42433.3333 16 11973.0556 43026.1111 17 11973.0556 43026.1111 18 11461.1111 43252.7778 19 11461.1111 43252.7778 20 11461.1111 43252.7778 21 11461.1111 43252.7778 22 11600.0000 43150.0000 23 12386.6667 43334.7222 24 12386.6667 43334.7222 25 11595.0000 43148.0556 26 11595.0000 43148.0556 27 11569.4444 43136.6667 28 11310.2778 42929.4444 29 11310.2778 42929.4444 30 11310.2778 42929.4444 31 11963.0556 43290.5556 32 11416.6667 42983.3333 33 11416.6667 42983.3333 34 11595.0000 43148.0556 35 12149.4444 42477.5000 36 11595.0000 43148.0556 37 11595.0000 43148.0556 38 11108.6111 42373.8889 39 11108.6111 42373.8889 40 11108.6111 42373.8889 41 11108.6111 42373.8889 42 11183.3333 42933.3333 43 12372.7778 42711.3889 44 11583.3333 43150.0000 45 11583.3333 43150.0000 46 11583.3333 43150.0000 47 11583.3333 43150.0000 48 11583.3333 43150.0000 49 11822.7778 42673.6111 50 11822.7778 42673.6111 51 12058.3333 42195.5556 52 11003.6111 42102.5000 53 11003.6111 42102.5000 54 11003.6111 42102.5000 55 11522.2222 42841.9444 56 12386.6667 43334.7222 57 12386.6667 43334.7222 58 12386.6667 43334.7222 59 11569.4444 43136.6667 60 11569.4444 43136.6667 61 11569.4444 43136.6667 62 11155.8333 42712.5000 63 11155.8333 42712.5000 64 11155.8333 42712.5000 65 11155.8333 42712.5000 66 11133.3333 42885.8333 67 11133.3333 42885.8333 68 11133.3333 42885.8333 69 11133.3333 42885.8333 70 11133.3333 42885.8333 71 11003.6111 42102.5000 72 11770.2778 42651.9444 73 11133.3333 42885.8333 74 11690.5556 42686.6667 75 11690.5556 42686.6667 76 11751.1111 42814.4444 77 12645.0000 42973.3333 78 12421.6667 42895.5556 79 12421.6667 42895.5556 80 11485.5556 43187.2222 81 11423.8889 43000.2778 82 11423.8889 43000.2778 83 11715.8333 41836.1111 84 11297.5000 42853.3333 85 11297.5000 42853.3333 86 11583.3333 43150.0000 87 11569.4444 43136.6667 88 12286.9444 43355.5556 89 12355.8333 43156.3889 EOF
Тип данных: координаты городов 1 6734 1453 2 2233 10 3 5530 1424 4 401 841 5 3082 1644 6 7608 4458 7 7573 3716 8 7265 1268 9 6898 1885 10 1112 2049 11 5468 2606 12 5989 2873 13 4706 2674 14 4612 2035 15 6347 2683 16 6107 669 17 7611 5184 18 7462 3590 19 7732 4723 20 5900 3561 21 4483 3369 22 6101 1110 23 5199 2182 24 1633 2809 25 4307 2322 26 675 1006 27 7555 4819 28 7541 3981 29 3177 756 30 7352 4506 31 7545 2801 32 3245 3305 33 6426 3173 34 4608 1198 35 23 2216 36 7248 3779 37 7762 4595 38 7392 2244 39 3484 2829 40 6271 2135 41 4985 140 42 1916 1569 43 7280 4899 44 7509 3239 45 10 2676 46 6807 2993 47 5185 3258 48 3023 1942 EOF
1 8 38 31 44 18 7 28 6 37 19 27 17 43 30 36 46 33 20 47 21 32 39 48 5 42 24 10 45 35 4 26 2 29 34 41 16 22 3 23 14 25 13 11 12 15 40 9 -1 EOF
Тип данных – транспонированная диагональная матрица 97 205 139 86 60 220 65 111 115 227 95 82 225 168 103 266 205 149 120 58 257 152 52 180 136 82 34 145 129 103 71 105 258 154 112 65 204 150 87 176 137 142 204 148 148 49 41 211 226 116 197 89 153 124 74 219 125 175 386 269 134 184 313 201 215 267 248 271 274 236 272 160 151 300 350 239 322 78 276 220 60 167 182 180 162 208 39 102 227 60 86 34 96 129 69 58 60 120 119 192 114 110 192 136 173 173 51 296 150 42 131 268 88 131 245 201 175 275 218 202 119 50 281 238 131 244 51 166 95 69 279 114 56 150 278 46 133 266 214 162 302 242 203 146 67 300 205 111 238 98 139 52 120 178 328 206 147 308 172 203 165 121 251 216 122 231 249 209 111 169 72 338 144 237 331 169 151 227 133 104 242 182 84 290 230 146 165 121 270 91 48 158 200 39 64 210 172 309 68 169 286 242 208 315 259 240 160 90 322 260 160 281 57 192 107 90 140 195 51 117 72 104 153 93 88 25 85 152 200 104 139 154 134 149 135 320 146 64 68 143 106 88 81 159 219 63 216 187 88 293 191 258 272 174 311 258 196 347 288 243 192 113 345 222 144 274 124 165 71 153 144 86 57 189 128 71 71 82 176 150 56 114 168 83 115 160 61 165 51 32 105 127 201 36 254 196 136 260 212 258 234 106 110 56 49 91 153 91 197 136 94 225 151 201 205 215 159 64 126 128 190 98 53 78 218 48 127 214 61 155 157 235 47 305 243 186 282 261 300 252 105 100 176 66 253 183 146 231 203 239 204 113 152 127 150 106 52 235 112 179 221 79 163 220 119 164 135 152 153 114 236 201 90 195 90 127 84 91 273 226 148 296 238 291 269 112 130 286 74 155 291 130 178 38 75 180 281 120 205 270 213 145 36 94 217 162
Тип данных: полная матрица 0 107 241 190 124 80 316 76 152 157 283 133 113 297 228 129 348 276 188 150 65 341 184 67 221 169 108 45 167 107 0 148 137 88 127 336 183 134 95 254 180 101 234 175 176 265 199 182 67 42 278 271 146 251 105 191 139 79 241 148 0 374 171 259 509 317 217 232 491 312 280 391 412 349 422 356 355 204 182 435 417 292 424 116 337 273 77 190 137 374 0 202 234 222 192 248 42 117 287 79 107 38 121 152 86 68 70 137 151 239 135 137 242 165 228 205 124 88 171 202 0 61 392 202 46 160 319 112 163 322 240 232 314 287 238 155 65 366 300 175 307 57 220 121 97 80 127 259 234 61 0 386 141 72 167 351 55 157 331 272 226 362 296 232 164 85 375 249 147 301 118 188 60 185 316 336 509 222 392 386 0 233 438 254 202 439 235 254 210 187 313 266 154 282 321 298 168 249 95 437 190 314 435 76 183 317 192 202 141 233 0 213 188 272 193 131 302 233 98 344 289 177 216 141 346 108 57 190 245 43 81 243 152 134 217 248 46 72 438 213 0 206 365 89 209 368 286 278 360 333 284 201 111 412 321 221 353 72 266 132 111 157 95 232 42 160 167 254 188 206 0 159 220 57 149 80 132 193 127 100 28 95 193 241 131 169 200 161 189 163 283 254 491 117 319 351 202 272 365 159 0 404 176 106 79 161 165 141 95 187 254 103 279 215 117 359 216 308 322 133 180 312 287 112 55 439 193 89 220 404 0 210 384 325 279 415 349 285 217 138 428 310 200 354 169 241 112 238 113 101 280 79 163 157 235 131 209 57 176 210 0 186 117 75 231 165 81 85 92 230 184 74 150 208 104 158 206 297 234 391 107 322 331 254 302 368 149 106 384 186 0 69 191 59 35 125 167 255 44 309 245 169 327 246 335 288 228 175 412 38 240 272 210 233 286 80 79 325 117 69 0 122 122 56 56 108 175 113 240 176 125 280 177 266 243 129 176 349 121 232 226 187 98 278 132 161 279 75 191 122 0 244 178 66 160 161 235 118 62 92 277 55 155 275 348 265 422 152 314 362 313 344 360 193 165 415 231 59 122 244 0 66 178 198 286 77 362 287 228 358 299 380 319 276 199 356 86 287 296 266 289 333 127 141 349 165 35 56 178 66 0 112 132 220 79 296 232 181 292 233 314 253 188 182 355 68 238 232 154 177 284 100 95 285 81 125 56 66 178 112 0 128 167 169 179 120 69 283 121 213 281 150 67 204 70 155 164 282 216 201 28 187 217 85 167 108 160 198 132 128 0 88 211 269 159 197 172 189 182 135 65 42 182 137 65 85 321 141 111 95 254 138 92 255 175 161 286 220 167 88 0 299 229 104 236 110 149 97 108 341 278 435 151 366 375 298 346 412 193 103 428 230 44 113 235 77 79 169 211 299 0 353 289 213 371 290 379 332 184 271 417 239 300 249 168 108 321 241 279 310 184 309 240 118 362 296 179 269 229 353 0 121 162 345 80 189 342 67 146 292 135 175 147 249 57 221 131 215 200 74 245 176 62 287 232 120 159 104 289 121 0 154 220 41 93 218 221 251 424 137 307 301 95 190 353 169 117 354 150 169 125 92 228 181 69 197 236 213 162 154 0 352 147 247 350 169 105 116 242 57 118 437 245 72 200 359 169 208 327 280 277 358 292 283 172 110 371 345 220 352 0 265 178 39 108 191 337 165 220 188 190 43 266 161 216 241 104 246 177 55 299 233 121 189 149 290 80 41 147 265 0 124 263 45 139 273 228 121 60 314 81 132 189 308 112 158 335 266 155 380 314 213 182 97 379 189 93 247 178 124 0 199 167 79 77 205 97 185 435 243 111 163 322 238 206 288 243 275 319 253 281 135 108 332 342 218 350 39 263 199 0
1 1150.0 1760.0 2 630.0 1660.0 3 40.0 2090.0 4 750.0 1100.0 5 750.0 2030.0 6 1030.0 2070.0 7 1650.0 650.0 8 1490.0 1630.0 9 790.0 2260.0 10 710.0 1310.0 11 840.0 550.0 12 1170.0 2300.0 13 970.0 1340.0 14 510.0 700.0 15 750.0 900.0 16 1280.0 1200.0 17 230.0 590.0 18 460.0 860.0 19 1040.0 950.0 20 590.0 1390.0 21 830.0 1770.0 22 490.0 500.0 23 1840.0 1240.0 24 1260.0 1500.0 25 1280.0 790.0 26 490.0 2130.0 27 1460.0 1420.0 28 1260.0 1910.0 29 360.0 1980.0 EOF
1 28 6 12 9 26 3 29 5 21 2 20 10 4 15 18 14 17 22 11 19 25 7 23 8 27 16 13 24 -1 EOF
bays29: лучший тур 1 28 6 12 9 26 3 29 5 21 2 20 10 4 15 18 14 17 22 11 19 25 7 23 8 27 16 13 24 -1 EOF
Тип данных: эвклидовы координаты 1 565.0 575.0 2 25.0 185.0 3 345.0 750.0 4 945.0 685.0 5 845.0 655.0 6 880.0 660.0 7 25.0 230.0 8 525.0 1000.0 9 580.0 1175.0 10 650.0 1130.0 11 1605.0 620.0 12 1220.0 580.0 13 1465.0 200.0 14 1530.0 5.0 15 845.0 680.0 16 725.0 370.0 17 145.0 665.0 18 415.0 635.0 19 510.0 875.0 20 560.0 365.0 21 300.0 465.0 22 520.0 585.0 23 480.0 415.0 24 835.0 625.0 25 975.0 580.0 26 1215.0 245.0 27 1320.0 315.0 28 1250.0 400.0 29 660.0 180.0 30 410.0 250.0 31 420.0 555.0 32 575.0 665.0 33 1150.0 1160.0 34 700.0 580.0 35 685.0 595.0 36 685.0 610.0 37 770.0 610.0 38 795.0 645.0 39 720.0 635.0 40 760.0 650.0 41 475.0 960.0 42 95.0 260.0 43 875.0 920.0 44 700.0 500.0 45 555.0 815.0 46 830.0 485.0 47 1170.0 65.0 48 830.0 610.0 49 605.0 625.0 50 595.0 360.0 51 1340.0 725.0 52 1740.0 245.0 EOF
1 49 32 45 19 41 8 9 10 43 33 51 11 52 14 13 47 26 27 28 12 25 4 6 15 5 24 48 38 37 40 39 36 35 34 44 46 16 29 50 20 23 30 2 7 42 21 17 3 18 31 22 -1 EOF
Тип данных: эвклидовы координаты городов 1 37 52 2 49 49 3 52 64 4 20 26 5 40 30 6 21 47 7 17 63 8 31 62 9 52 33 10 51 21 11 42 41 12 31 32 13 5 25 14 12 42 15 36 16 16 52 41 17 27 23 18 17 33 19 13 13 20 57 58 21 62 42 22 42 57 23 16 57 24 8 52 25 7 38 26 27 68 27 30 48 28 43 67 29 58 48 30 58 27 31 37 69 32 38 46 33 46 10 34 61 33 35 62 63 36 63 69 37 32 22 38 45 35 39 59 15 40 5 6 41 10 17 42 21 10 43 5 64 44 30 15 45 39 10 46 32 39 47 25 32 48 25 55 49 48 28 50 56 37 51 30 40 EOF
1 22 8 26 31 28 3 36 35 20 2 29 21 16 50 34 30 9 49 10 39 33 45 15 44 42 40 19 41 13 25 14 24 43 7 23 48 6 27 51 46 12 47 18 4 17 37 5 38 11 32 -1 EOF
Тип данных: эвклидовы координаты городов 1 22 22 2 36 26 3 21 45 4 45 35 5 55 20 6 33 34 7 50 50 8 55 45 9 26 59 10 40 66 11 55 65 12 35 51 13 62 35 14 62 57 15 62 24 16 21 36 17 33 44 18 9 56 19 62 48 20 66 14 21 44 13 22 26 13 23 11 28 24 7 43 25 17 64 26 41 46 27 55 34 28 35 16 29 52 26 30 43 26 31 31 76 32 22 53 33 26 29 34 50 40 35 55 50 36 54 10 37 60 15 38 47 66 39 30 60 40 30 50 41 12 17 42 15 14 43 16 19 44 21 48 45 50 30 46 51 42 47 50 15 48 48 21 49 12 38 50 15 56 51 29 39 52 54 38 53 55 57 54 67 41 55 10 70 56 6 25 57 65 27 58 40 60 59 70 64 60 64 4 61 36 6 62 30 20 63 20 30 64 15 5 65 50 70 66 57 72 67 45 42 68 38 33 69 50 4 70 66 8 71 59 5 72 35 60 73 27 24 74 40 20 75 40 37 76 40 40 EOF
1 33 63 16 3 44 32 9 39 72 58 10 31 55 25 50 18 24 49 23 56 41 43 42 64 22 61 21 47 36 69 71 60 70 20 37 5 15 57 13 54 19 14 59 66 65 38 11 53 7 35 8 46 34 52 27 45 29 48 30 4 75 76 67 26 12 40 17 51 6 68 2 74 28 62 73 -1 EOF
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.