Метод комбинирования эвристик

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

Первый из них основан на использовании в качестве генов проектных параметров. Например, в задаче размещения микросхем на плате локусы соответствуют посадочным местам на плате, а генами являются номера (имена) микросхем. Другими словами, значением -го гена будет номер микросхемы в -й позиции. Область значений вещественных параметров аппроксимируется множеством целых чисел. Часто управляемые параметры кодируют двоичными числами, тогда. хромосомы представляются битовыми строками, а параметры — частями этих строк.

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

Второй подход относится к генетическому программированию и реализован в методе, названном методом комбинирования эвристик (или мультиметодным генетическим алгоритмом). Этот метод оказывается предпочтительным во многих случаях. Например, в задачах синтеза расписаний распределяется заданное множество работ во времени и между обслуживающими устройствами — серверами, т.е. проектными параметрами для каждой работы будут номер сервера и порядковый номер в очереди на обслуживание. Пусть — число работ, — число серверов. Если гены соответствуют номерам работ, то в первом подходе в хромосоме нужно иметь генов и общее число отличающихся друг от друга хромосом заметно превышает наибольшее из чисел и .

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

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

Список литературы