Длина бинарных кодировок

Для поиска оптимального разбиения пространства параметров на гиперкубы [3], кодируемые хромосомными наборами соответствующей длины N*L (N — размерность задачи, L — длина кодировки одного гена), проводились испытания для L₁=4, L₂=8, L₃=12. Эффективность поиска (при численности популяции 300 особей) определялась по отношению к двум показателям:

• — суммарному количеству холостых гипотез по 20 запускам;
• — времени работы ГА.

Результаты эксперимента для нескольких деревьев БЗ с 15-ю гипотезами и 4-мя уровнями при 300 особях в популяции приведены в табл. 2 и 3 и на рис. 5, 6.

Таблица 2 — Влияние длины бинарных кодировок на количество холостых гипотез.

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

Очевидно, такая особенность объясняется разбросом значений приспособленности особей, имеющих одинаковые генотипы, этот разброс тем больше, чем крупнее гиперкубы разбиения пространства [3, 4]. Поэтому в процессе поиска для таких функций сложнее определить хромосомные наборы, которые бы соответствовали оптимальному решению.

Рисунок 5 — Влияние длины кода на количество холостых гипотез Осторожное отношение к увеличению длины кодировки вызывает и тот факт, что оно ускоряет процесс сходимости всех членов популяции к лучшему найденному решению. Такой эффект очень часто нежелателен из-за того, что большая часть пространства поиска остается неисследованной, а преждевременная сходимость может не привести к оптимальному решению, кроме того, быстрая сходимость к одной области не гарантирует обнаружения нескольких равных экстремумов. Поэтому в вопросе выбора оптимальной длины кодировки нужно достичь некоторого компромиссного решения: с одной стороны, L должно быть достаточно большим, чтобы все-таки обеспечить быстрый поиск, с другой стороны, — по возможности малым, чтобы не допускать преждевременной сходимости и оставить алгоритму шанс отыскать несколько оптимальных значений.

Таблица 3 — Влияние длины кода гена на время выполнения ГА.

Рисунок 6 — Влияние длины кода гена на время выполнения ГА Здесь уместно еще раз отметить, что ландшафт ЦФ при работе с ЭС продукционного типа, как правило, неизвестен, и, более того, — у каждой гипотезы он индивидуален [2,5]. Как раз выяснению характерных деталей ландшафтов во многом способствуют экспериментальные исследования с использованием ПИК «Поиск». И в отношении длины бинарной кодировки гена единственный выход — ее экспериментальное определение — такое, которое, будучи использовано для всех ГА, обеспечит в целом лучшую эффективность метода ГС.

Таким образом, экспериментально опробовав ряд режимов для сформированного выше дерева БЗ, необходимо сделать вывод, что по обоим анализируемым параметрам предпочтительнее установить бинарную длину гена L=4.