Задача с радио башнями

К решению предлагается следующая задача. Есть квадратное поле n на m клеток. На поле отмечены возможные точки, где можно установить башни определенного радиуса покрытия.

Необходимо оптимизировать расположение башень на поле, используя различные критерии (по вариантам).

Параметры задачи

Входные данные:

• Ширина и высота поля

• Список башен, в каждой точке поля может стоять одна башня с параметрами:

  • положение по оси X

  • положение по оси Y

  • радиус башни в количестве клеток

Параметры эволюции:

• Шанс мутации индивида

• Доля лучших индивидов из популяции, которая копируется без изменения в следующее поколение (доля элиты)

• Максимальное число поколений, после которого эволюционный процесс прерывается

• Число популяций

• Число индивидов в одной популяции

Входные данные модели и параметры эволюции задаются через графический интерфейс:

Поле радиус отвечает за текущий радиус башень, которые ставятся на поле.

Написание фитнес функции

Необходимо, в соответствии с вариантом, определить фитнес функцию для оптимизации расположения башень на поле. Фитнес функция реализовывается с помощью языка JavaScript.

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

Пример фитнес функции, которая отсеивает решения с числом поставленных башень не больше 5:

function(coverage, usedCount, towerUsedGetter, totalCount, towerTotalGetter, fieldWidth, fieldHeight, fieldGetter)
{
    if (usedCount > 5) return 0.0;
    else return 1.0
}

Или функция, которая поощряет выбор башень с максимальным радиусом:

function(coverage, usedCount, towerUsedGetter, totalCount, towerTotalGetter, fieldWidth, fieldHeight, fieldGetter)
{
    var radiusSumm = 0;
    for(var i = 0; i < usedCount; i++)
    {
        radiusSumm += towerUsedGetter(i).towerRadius;
    }
    return radiusSumm;
}

Данные функции вводятся в текстовое поле:

Описание параметров функции:

• coverage - дробное число от 0.0 до 1.0, обозначающее процент поля, покрытое башнями.

• usedCount - число башень, использованных в решении

• towerUsedGetter - функция, которая принимает в себя индекс башни и возвращает использованную башню в решении под этим индексом. Индексы должны быть в диапазоне от 0 до usedCount-1. Пример использования:

for(var i = 0; i < usedCount; i++)
{
    var tower = towerUsedGetter(i);
    // код, использующий tower
}

• totalCount - число башень, которые доступны на поле. Включает в себя и башни, которые были выбраны в решении, так и не выбранные.

• towerTotalGetter - функция, которая принимает в себя индекс башни и возвращает башню на поле под этим индексом. Индексы должны быть в диапазоне от 0 до totalCount-1. Пример использования:

for(var i = 0; i < totalCount; i++)
{
    var tower = towerTotalGetter(i);
    // код, использующий tower
}

• fieldWidth - ширина поля

• fieldHeight - высота поля

• fieldGetter - функция, которая принимает в себя два индекса, соответствующие координатам X и Y. X может принимать значения от 0 до fieldWidth. Y может принимать значения от 0 до fieldHeight. Возвращает количество башень, которые покрывают точку (X,Y). Пример использования:

for(var x = 0; x < fieldWidth; x++)
{
    for(var y = 0; y < fieldHeight; y++)
    {
        var towerCount = fieldGetter(x, y);
    }
}

Экран эволюционного процесса

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

Экран результатов

Финальный экран показывает лучшее найденное решение. Зеленный цвет показывает какие клетки поля покрыты поставленными башнями (непоставленные башни отображены светло-серым цветом). Чем больше башень покрывает клетку, тем темнее тон зеленого цвета.

Также на экране отображается график фитнес функции, если система работает корректно, то график должен быть монотонно неубывающий.

Также ниже графика имеется дополнительная информация о решении, такая как:

• используемые входные данные и параметры эволюции

• поставленные башни

• значение фитнес функции лучшего индивида

• сколько башен использовано в лучшем решении

• лучшее покрытие поля

Порядок выполнения

• Открыть веб приложение

• Задать размеры поля, значения ширины и высоты поля должны быть в диапазоне от 15 до 20 клеток.

• Реализовать фитнес функцию в соответствии с вариантом. Каждому студенту необходимо реализовать 2 фитнес функции, одну из первых четырех вариантов, вторую из второй четверки.

Номер функции из первой четверки считается так: 1 + ((n - 1) mod 4), где n - номер студента в списке, mod - операция взятия остатка от деления.

Номер функции из второй четверки считается так: 4 - ((n - 1) mod 4). Соответственно, если вам выпала 1ая функция (1ый в списке, или 5ый, или 9ый и т.д.) из первой четверки, то из второй выпадет 4ая. 2ая из первой, 3ая из второй, и так далее.

Первая четверка:

1. Максимизировать покрытие поля, используя не больше 10 башень.

2. Максимизировать покрытие поля, используя минимальное число башень.

3. Можно поставить 1 башню с радиусом 5, 2 башни с радиусом 4, 3 башни с радиусом 3. Максимизировать покрытие поля.

4. Стоимость башни пропорциональна площади покрытия этой башни. Задать максимальный "бюджет" C (выбрать для демонстрации), максимизировать покрытие поля.

Вторая четверка:

1. Максимизировать покрытие поля, не допуская покрытие клетки больше чем одной башней.

2. Максимизировать покрытие поля, не менее 30% клеток должно покрываться более чем одной башней.

3. Максимизировать покрытие поля, каждая башня должна быть покрыта полем действия другой. Максимальное число башен N (выбрать подходящее для демонстрации)

4. Максимизировать покрытие поля, каждая башня не должна быть покрыта полем действия другой.

• Подобрать подходящие входные данные, которые продемонстрируют работоспособность реализованной фитнес функции. Показать преподавателю.

• Сохранить/сделать скриншот первого и последнего экрана для отчета.