Задача о ранце. Генетический алгоритм - C#
Формулировка задачи:
Доброго времени суток, коллеги.
На днях выдалось относительно свободное время и я решил размять мозги. Выбор пал на задачу о ранце. Начать решил с поиска готовых решений. В нете нашёл простую реализацию решения методом перебора. Небольшой список предметов она решала относительно быстро, при увеличении время работы нелинейно возрастало: на 5 предметов решение находилось за 10 мс, 10 предметов - 4,5 секунды, 15 - задача крутилась 8 часов, после чего мне это надоело и я её вырубил.
Вооружившись википедией и тематическими статьями решил реализовать решение генетическим алгоритмом. Вроде сделал, вроде работает, но что-то мне оно не особо нравится:
1) Пришлось хардкодить создание начальной популяции отбрасывая особи, у которых суммарный вес предметов выше максимально допустимого. Знаю, что это допускается условием задачи, но, ИМХО, по идее алгоритм должен их принимать, как и других, просто отсеивая. А по факту в итоге зачастую выживали именно с этим генотипом.
2) Гвоздями прибито условие, по которому популяция должна делиться надвое без остатка.
3) Иногда выживают особи с не самым оптимальным набором предметов, или даже имеющие кучу свободного места.
Если подскажете, как можно довести до ума алгоритм буду благодарен.
Модель данных:
Алгоритм:
Исходники прилагаются (простое WPF приложение с одной кнопкой)
BP_Problem.zip
public class Item
{
public String Name { get; private set; }
public int Weight { get; private set; }
public double Price { get; private set; }
public Item (String Name, int Weight, double Price)
{
this.Name = Name;
this.Weight = Weight;
this.Price = Price;
}
} public class BackPack
{
List<Item> Items = null;
public int Weight { get; private set; } = 0;
public double Price { get; private set; }
public double Fitness { get; private set; }
public double Probably { get; set; }
public BackPack(int maxWeight, Item[] allItems, Random rnd)
{
int i;
int iterations = 0;
Items = new List<Item>();
while (Weight < maxWeight)
{
iterations++;
if (iterations > 100)
break;
i = rnd.Next(0, allItems.Length);
if (Items.Contains(allItems[i]))
continue;
if (Weight + allItems[i].Weight > maxWeight)
continue;
Items.Add(allItems[i]);
Weight += Items.Last().Weight;
}
Price = Items.Sum(x => x.Price);
Fitness = Math.Round(Price / Weight,3);
}
public Item[] getItems()
{
return Items.ToArray();
}
} public partial class MainWindow : Window
{
Random rnd = new Random();
List<Item> BaseItems = new List<Item>();
public List<BackPack> population;
const int generationsCount = 1500;
const int populationCount = 60;
const int maxWeight = 15;
public MainWindow()
{
InitializeComponent();
}
private void Button_Click(object sender, RoutedEventArgs e)
{
InitItems();
CreatePopulation();
for (int i = 0; i < generationsCount; i++)
{
Selection();
Mutation();
}
}
/// <summary>
/// Создаём набор предметов
/// </summary>
void InitItems()
{
BaseItems.Add(new Item("Книга", 1, 600));
BaseItems.Add(new Item("Бинокль", 2, 5000));
BaseItems.Add(new Item("Аптечка", 4, 1500));
BaseItems.Add(new Item("Ноутбук", 2, 40000));
BaseItems.Add(new Item("Котелок", 1, 500));
BaseItems.Add(new Item("Книга1", 3, 500));
BaseItems.Add(new Item("Бинокль1", 2, 7000));
BaseItems.Add(new Item("Аптечка1", 5, 500));
BaseItems.Add(new Item("Ноутбук1", 6, 60000));
BaseItems.Add(new Item("Котелок1", 2, 300));
BaseItems.Add(new Item("Книга2", 6, 650));
BaseItems.Add(new Item("Бинокль2", 3, 15000));
BaseItems.Add(new Item("Аптечка2", 1, 15000));
BaseItems.Add(new Item("Ноутбук2", 9, 440000));
BaseItems.Add(new Item("Котелок2", 2, 600));
BaseItems.Add(new Item("Книга3", 6, 200));
BaseItems.Add(new Item("Бинокль3", 4, 500));
BaseItems.Add(new Item("Аптечка3", 4, 150));
BaseItems.Add(new Item("Ноутбук3", 7, 45000));
BaseItems.Add(new Item("Котелок3", 1, 500));
BaseItems.Add(new Item("Книга4", 1, 400));
BaseItems.Add(new Item("Бинокль4", 2, 5500));
BaseItems.Add(new Item("Аптечка4", 2, 2000));
BaseItems.Add(new Item("Ноутбук4", 2, 32000));
BaseItems.Add(new Item("Котелок4", 2, 520));
BaseItems.Add(new Item("Книга5", 7, 640));
BaseItems.Add(new Item("Бинокль5", 6, 5400));
BaseItems.Add(new Item("Аптечка5", 3, 1600));
BaseItems.Add(new Item("Ноутбук5", 2, 21000));
BaseItems.Add(new Item("Котелок5", 2, 500));
}
/// <summary>
/// Создаём начальную популяцию
/// </summary>
void CreatePopulation()
{
population = new List<BackPack>();
for (int i = 0; i < populationCount; i++)
population.Add(new BackPack(maxWeight, BaseItems.ToArray(), rnd));
}
/// <summary>
/// Выполняем селекцию
/// </summary>
void Selection()
{
double SumFitness = population.Sum(x => x.Fitness);
foreach (BackPack bp in population) // для каждого набора расчитываем вероятность быть избранным
bp.Probably = 100 * bp.Fitness / SumFitness;
population = population.OrderByDescending(x => x.Probably).ToList();
List<BackPack> parents = new List<BackPack>();
while (parents.Count != populationCount / 2) // перебирая сортированный список наборов отбираем половину на роль родителей
{
for (int i = 0; i < population.Count; i++)
{
if (population[i].Weight > maxWeight) // отбрасываем нежиснеспособных особей
continue;
if ((rnd.Next(0, 100 + (int)population[i].Probably * 10)) < 50)
continue;
else
{
parents.Add(population[i]);
population.RemoveAt(i);
break;
}
}
}
population = new List<BackPack>();
population.AddRange(parents);
BackPack dad, mum, son1, son2;
List<Item> items;
while(parents.Count > 0) // перебирая родителей отбираем случайным образом пары и создаём 2-х потомков
{
dad = parents[rnd.Next(parents.Count)];
parents.Remove(dad);
mum = parents[rnd.Next(parents.Count)];
parents.Remove(mum);
items = new List<Item>();
items.AddRange(dad.getItems());
items.AddRange(mum.getItems());
son1 = new BackPack(maxWeight, items.ToArray(), rnd);
son1.Probably = 100 * son1.Fitness / SumFitness;
son2 = new BackPack(maxWeight, items.ToArray(), rnd);
son2.Probably = 100 * son2.Fitness / SumFitness;
population.Add(son1);
population.Add(son2);
}
}
/// <summary>
/// Случайная мутация
/// </summary>
void Mutation()
{
BackPack rBp = population[rnd.Next(0, population.Count)];
int index = rnd.Next(0, rBp.getItems().Length);
Item newItem = BaseItems[rnd.Next(0, BaseItems.Count)];
rBp.getItems()[index] = newItem;
}
}Решение задачи: «Задача о ранце. Генетический алгоритм»
textual
Листинг программы
public struct Backpack
{
public Backpack(ImmutableArray<Item> items)
{
Items = items;
}
public ImmutableArray<Item> Items { get; }
public int TotalWorth => Items.Sum(x => x.Worth);
}