Ниже рассмотрены примеры постановки задач оптимизации и структурного синтеза для решения генетическими методами. В каждом из представленных ниже классов задач применение HCM позволило получить значительно лучшее приближение к экстремуму по сравнению с альтернативными одноэвристическими методами.
Компоновка
Содержательной сутью задачи компоновки может быть распределение работ по исполнителям, оборудования по помещениям, прикладного программного обеспечения и баз данных по подсетям виртуальной локальной вычислительной сети и т.п.
Рассмотрим задачу компоновки оборудования. В частности, это может быть задача размещения микросхем по модулям (платам или типовым элементам замены), модулей по панелям, панелей по шкафам радиоэлектронной аппаратуры или приборов по отсекам корабля и т.п.
Пусть задача характеризуется следующими исходными данными:
Опишем множество альтернатив . Оно представляется матрицей размера , элемент которой , если конструктив включен в блок , иначе . Некоторое распределение единиц и нулей по клеткам матрицы представляет одну конкретную компоновку, т.е. одно проектное решение. Но только такие варианты распределения 1 и 0 по клеткам матрицы допустимы, которые удовлетворяют следующим ограничениям:
 (1)

где суммирование производится для конструктива по всем от до ;
 (2)

где суммирование производится для блока по от до , — максимальное число элементов, помещающихся в один блок.
Первое из этих условий говорит о том, что элемент может быть помещен только в один блок. Второе условие свидетельствует об ограниченном объеме блоков.
В общем случае в задачах компоновки может быть несколько критериев. В частном случае используется единственный критерий — число межблочных связей. Число таких связей нужно минимизировать.
Для вычисления критерия применяют следующую модель.
Формируются матрицы и . Матрица размера есть матрица связей блоков и конструктивов, элемент этой матрицы равен числу связей -го блока с -м конструктивом. Матрица имеет размер , ее элемент равен числу связей между блоками и , — транспонированная матрица . Так как число межблочных (внешних) связей равно общему числу связей минус число внутренних связей , то в качестве целевой функции, подлежащей максимизации, можно принять суммарное число внутренних связей, т.е. функцию
 (3)

где суммирование выполняется по от до .
Таким образом, задача компоновки представлена как задача дискретного (булева) математического программирования с целевой функцией (3), ограничениями (1), (2) и множеством управляемых параметров .
Аналогичным образом, формулируется ряд других задач структурного синтеза.
При решении задачи компоновки генетическим методом может быть принята хромосома следующей структуры — гены соответствуют конструктивам, значение -го гена есть номер блока, в который помещен -й конструктив.
В случае применения HCM декомпозиция общей задачи приводит к локальным подзадачам, в каждой из которых выбирается один из еще не распределенных конструктивов и назначается в один из блоков. Нужно сформулировать правила выбора в каждой подзадаче конструктива и правила выбора блока для этого конструктива. Каждая эвристика включает по одному правилу и .
Формулировка правил — ответственная задача, от качества решения которой зависит эффективность поиска оптимума. Однако ее решение в HCM оказывается проще, чем в традиционных эвристических методах.
Действительно, в традиционном эвристическом методе нужно сформулировать единственную комплексную эвристику, в которой с некоторыми весами были бы учтены все требования к синтезируемому решению. Но для получения решения, близкого к оптимальному, эти веса должны изменяться от шага к шагу (от подзадачи к подзадаче), а найти корректный алгоритм изменения весов в рамках обычных эвристических методов невозможно. Веса принимаются постоянными, решение оказывается далеким от оптимума.
Метод HCM можно рассматривать именно как генетический метод определения оптимальной последовательности весов. Но вместо комплексной эвристики проще и удобнее использовать множество простых правил и вместо изменения весов производить замену правил при переходе от шага к шагу, что и делается в HCM. Формирование таких правил не представляет существенных трудностей, так как не нужно назначать веса. Важно лишь обеспечить разнообразие правил, чтобы рациональные решения не оказались за пределами поискового пространства.
В многокритериальных задачах оптимизации проблема формирования эвристик часто решается довольно просто: каждое правило должно соответствовать одному из имеющихся критериев оптимальности. Конечно, метод HCM предоставляет возможности использования любых разумных правил и, следовательно, формирования набора эвристик по предпочтениям пользователя. Это обстоятельство успешно используется, когда исходные критерии оптимальности нелегко трансформировать в частные критерии локальных подзадач.
Примеры правил в задаче компоновки для выбора конструктива:
Примеры правил выбора блока:
Пару правил и называют эвристикой . В случае задачи с приведенными выше примерами правил имеем возможных эвристик.
Кластеризация
Иногда требуется равномерное распределение элементов по имеющимися блокам. Тогда возникает задача кластеризации, которую можно рассматривать как разновидность задачи компоновки, отличающуюся типом ограничений: вместо ограничения типа неравенства на объем внутренних для кластера (блока) связей вводится ограничение типа равенства на число элементов (компонентов) в кластере. Т.е. ограничение (2) принимает вид

 (4)


где — число элементов в -м кластере, — целая часть частного от деления числа элементов на число кластеров . Другими словами, требуется равномерное распределение элементов по кластерам, минимизирующее связность кластеров друг с другом. В частности, в некоторых алгоритмах размещения микросхем на платах предварительно решается задача дихотомической кластеризации — разделения множества микросхем на два минимально связанных подмножества одинаковой (при четном ) мощности.
Очевидно, что в задаче кластеризации после соответствующей корректировки можно использовать правила выбора очередного элемента и его размещения в одном из кластеров, аналогичные правилам в задаче компоновки. Так, в правиле загрузка кластера будет оцениваться не его внутренним трафиком (связностью), а числом размещенных в нем элементов, во всех правилах , и возможным кластером-кандидатом может быть только тот кластер, в котором еще не исчерпан лимит на размещение. Правила используются без изменений. При вычислении целевой функции штрафы за нарушение ограничений не предусматриваются, так как учет ограничений введен в эвристики.
Возможны и другие варианты множества эвристик. Например, можно использовать правила, в которых очередным размещаемым элементом выбирается элемент:
Для выбранного по одному из правил элемента определяется кластер, в котором:
Из этих правил можно скомбинировать 6 разных эвристик и добавить эвристику, в которой сначала определяется кластер по признаку минимальной загруженности, а затем для него выбирается элемент по признаку максимальной связности с уже размещенными в элементами. Ограничения на максимально допустимое число элементов в кластере введены в эвристики.
Синтез расписаний
Задачи синтеза расписаний требуется решать во многих приложениях, например, при планировании различных производственных процессов, распределении ресурсов, выборе числа и типов процессоров для многопроцессорных специализированных комплексов и т.п.
Рассмотрим постановку и подход к решению одной из основных разновидностей задач синтеза расписаний, обозначаемой JSSP (Job Shop Scheduling Problem). К исходным данным относятся:
Требуется составить расписание, при котором минимизируются затраты на выполнение всех работ с учетом штрафов.
В других разновидностях задач синтеза расписаний могут быть те или иные усложняющие решение отличия. Примерами отличий могут быть:
  1. многостадийность — наличие нескольких стадий обслуживания каждой работы;
  2. разделение работ на несколько групп и учет дополнительных затрат на переналадку машин, требующейся при последовательном обслуживании работ разных групп;
  3. частичная упорядоченность работ, т.е. для некоторых пар работ , введены ограничения вида:

    где — время начала -й работы, — время окончания -й работы.
Каждая эвристика при применении для синтеза расписаний метода HCM включает два правила: одно для выбора очередной работы, другое для выбора машины, обслуживающей эту работу.
Например, при синтезе многостадийных расписаний в качестве очередной может выбираться работа:
  1. с наименьшим ;
  2. с наименьшим временем окончания обслуживания на предыдущей стадии .
Примеры правил выбора машин:
  1. выбирается машина, на которой обслуживание данной работы будет наиболее дешевым;
  2. выбирается машина, на которой работа будет обслужена за наименьшее время.
Маршрутизация транспортных средств
Среди задач маршрутизации транспортных средств при перевозке различных грузов одной из наиболее трудных для решения считается задача VRPTW (Vehicle Routing Problem with Time Windows) — задача маршрутизации транспортных средств с временными окнами. Временным окном здесь называют временной интервал, в который нужно выполнить заказ на перевозку. В задаче заданы:
Кроме того, для узлов-потребителей и узлов-источников заданы объемы соответственно заказанного и имеющегося продукта каждого типа, для серверов — максимальный объем перевозимого продукта, скорость движения, цена за единицу расстояния пробега, штрафы за нарушение временных ограничений (выход за пределы временных окон), причем штрафы зависят от цены единицы продукта каждого типа и от степени нарушения ограничений.
Требуется найти график движения транспортных средств для выполнения всех заказов с минимальными затратами.
Каждая эвристика при использовании HCM включает правила для выбора заказа (узла-потребителя), узла-источника продукта и транспортного средства (не исключено, что для выполнения конкретного заказа привлекается более чем по одному источнику и/или серверу).
Для выбора узла-потребителя можно использовать следующие правила:
В правилах выбора узла-источника продукта предпочтение может отдаваться источнику:
Эвристика дополняется правилом, в котором выбирается сервер:
Синтез топологии каналов передачи данных в вычислительных сетях
Задачи определения топологии сетей различного рода и распределения в них трафика относятся к сложным задачам структурного синтеза. Задачи, подобные рассматриваемой ниже задаче синтеза сети каналов передачи данных, встречаются во многих приложениях при синтезе сетей и распределения в них материальных, транспортных, информационных потоков.
Рассматривается следующая задача. Дано:
Нужно минимизировать общие затраты на построение сети, складывающиеся из затрат на прокладку и аренду связей и на обслуживающее оборудование.
Решение задачи включает две процедуры:
  1. выбор системы связей — каркаса сети;
  2. перенос трафика связей, не вошедших в каркас и называемых хордами, в те или и иные связи каркаса.
В первой процедуре рассматривается полный граф , — множество ребер (связей) полного графа. Каркас выбирается в виде остовного дерева, в дальнейшем к нему могут добавляться некоторые другие связи.
Алгоритм выбора дерева основан на последовательном подключении к подмножеству вершин, уже включенных в дерево, очередной вершины из подмножества вершин, еще не включенных в дерево. Правило выбора подключаемой вершины — ее максимальная близость к дереву, т.е. в дерево включается связь при условии

где
Начало исполнения алгоритма — включение в двух вершин и , которым соответствует минимальный элемент матрицы .
По окончании процедуры устраняются висячие вершины путем их соединения между собой. Для этого достаточно построить еще одно дерево, но уже на графе, включающем только висячие вершины. Таким образом, каркас будет включать связи двух построенных деревьев.
Алгоритм второй процедуры основан на классификации связей. Связи первого ранга — это связи каркаса. Связь второго ранга — это хорда такая, что имеется вершина и связи и включены в каркас. Хорда -го ранга — это хорда такая, что имеется вершина и связи и являются связями ранга меньше , причем одна из них имеет ранг .
Результаты классификации хорд составляют матрицу , ее элемент , где — ранг связи .
Заполнение матрицы происходит по следующему алгоритму. Сначала всем связям первого уровня присваивается ранг , т.е. принимаем . Далее если и имеется такое, что , то . Алгоритм выполняется при последовательном увеличении до полного заполнения .
Перенос трафика из хорд в связи каркаса происходит по эвристикам, выбираемым генетическим методом.
Начиная со связей высшего ранга и кончая связями ранга 2, последовательно к каждой связи применяется одна из следующих эвристик.
  1. Если (, то трафик из связи переносится в связи и ;
  2. Выбирается , соответствующее минимальной сумме при условии ; трафик из связи переносится в связи и ;
  3. То же, что и правило 2, но с измененным условием ;
  4. То же, что и 3, но перенос трафика осуществляется только, если , иначе связь присоединяется к каркасу.