Простейшая
задача размещения
Тестовые
примеры
Примеры
на совершенных кодах
Расположение
локальных оптимумов
Для 9 000 случайных подмножеств множества I получено 8868 локальных оптимумов относительно окрестности добавить – удалить – заменить. На диаграмме каждый шар соответствует одному локальному оптимуму. Радиус шара равен числу локальных оптимумов, расположенных на расстоянии не более 10 от данного. Минимальный радиус равен 1, максимальный — 57, средний — 3. Для глобального оптимума радиус равен 52, значение целевой функции 48 227. Кроме глобального оптимума найдено еще 10 локальных оптимумов со значением целевой функции не более 49 000, хотя известно, что в данном примере их ровно 240. Каждый из них соответствует одному их совершенных кодов. Для каждого кода существует еще 7 других, которые с ним и попарно не пересекаются и имеют взаимное расстояние 32. Кроме того минимальное расстояние между кодами не менее 4. Максимальное расстояние между всеми полученными локальными оптимумами составило 55.
Ось x — расстояние Хэмминга до глобального оптимума,
ось y — значение целевой функции,
k = 3, код примера 534.