Наиболее эффективным методом решения линейной однокритериальной задачи о назначениях является венгерский метод, по которому исходя из частичного плана перевозок, за конечное числа итераций можно построить оптимальный план перевозок. 3адача о назначениях имеет много интерпретаций: распределение работ между механизмами, распределение целей между огневыми средствами для максимизации математического ожидания числа пораженных целей или среднего ущерба и др.
Задачи комбинаторной оптимизации обычно рассматриваются в однoкритериальной постановке. Менее изученными, но важными в приложениях являются такие задачи, в которых множество допустимых решений соответствует классическому варианту, но выбор оптимального решения предполагает учет более одного параметра, или критерия. В этом случае мы имеем дело с NP-подлной задачей. Ясно, что изучение сложности возникающих таким образом задач представляет интерес лишь в случаях, когда соответствующие однокритериальные задачи полиномиально разрешимы.
В данной ситуации целесообразно применить генетический подход, неоднократно положительно зарекомендовавший себя при решении NP-полных задач. В теории моделирования эволюции структура и качество поколения потомков во многом зависит от того между какими особями происходит скрещивание. Поэтому в качестве одного из методов улучшения качества генерируемой новой популяции используется селекция или способ образования пар для скрещивания.
Система скрещивания, в которой любые две особи имеют равновероятную возможность образовать «родительскую» пару, называется панмиксией особей. При панмиксии частота P(xkt,xlt) образования пары (xkt,xlt) не зависит от вариабельных признаков этих особей, а полностью определяется численностью популяции v:
.
Хеммингово расстояние между особями определяется как число несовпадающих генов по своим значениям (аллелям) в соответствующих локусах в хромосомной строке.
Будем считать, что две особи являются «близкими родственниками», если Хеммингово расстояние между ними не превышает заданного положительного целого числа d, то есть хромосомы отличаются между собой не более, чем в d локусах. В частном случае d может равняться нулю.
Система скрещивания, в которой при образовании «родительской» пары используются особи, являющиеся «близкими родственниками», называется инбридингом. Подбор особей в «родительские пары» при инбридинге приводит к узкородственному размножению, при котором объединение «близких родственников» в пару происходит чаще, чем можно было бы ожидать при панмиксии. Инбридинг позволяет наиболее быстро выделить линию, несущую желаемые гены. Однако так как «близкие родственники» более сходны между собой в генетическом смысле, то у них большее число аллелей в отдельных генах совпадает между собой, что ведет при размножении к снижению разнообразия генофонда. Прямо противоположной к рассматриваемой системе скрещивания является аутбридинг - система скрещивания, в которой при образовании «родительской пары» предпочтение отдается генетически различным особям. При этом две особи имеют тем больше шансов для скрещивания, чем больше Хеммингово расстояние между ними.
Решения, выделенные какой-либо инбридной линией, оказываются неспособными к дальнейшему улучшению тем же способом скрещивания, что и раньше, и представляют собой локальные оптимумы, выйти из которых дает возможность аутбридинг.
В настоящей работе предлагается введение в генетический алгоритм макроэволюции, то есть развития нескольких субпопуляций. Трудностью при этом подходе является то, что после некоторого числа поколений хромосомы в отдельной популяции становятся очень похожими. Работа не с одной, а с несколькими начальными популяциями позволяет получить большее разнообразие генетического материала, позволяя вести эволюцию в отдельных субпопуляциях, в каждой из которых можно получить решения, недостижимые в одной популяции.
Если в пределах популяции свободное скрещивание особей нарушается на длительное время, то в процесс эволюции включается третий фактор - изоляция. В результате действия изоляции образуются генотипически отличающиеся друг от друга субпопуляции. Скрещивание представителей этих субпопуляций оказывает положительный эффект на процесс эволюции. Предлагается включение в схему ГА фактора изоляции и миграции, что позволяет во многих случаях выходить из локальных оптимумов для задач оптимизации