Задача о ранце. Генетический алгоритм - C#

Узнай цену своей работы

Формулировка задачи:

Доброго времени суток, коллеги. На днях выдалось относительно свободное время и я решил размять мозги. Выбор пал на задачу о ранце. Начать решил с поиска готовых решений. В нете нашёл простую реализацию решения методом перебора. Небольшой список предметов она решала относительно быстро, при увеличении время работы нелинейно возрастало: на 5 предметов решение находилось за 10 мс, 10 предметов - 4,5 секунды, 15 - задача крутилась 8 часов, после чего мне это надоело и я её вырубил. Вооружившись википедией и тематическими статьями решил реализовать решение генетическим алгоритмом. Вроде сделал, вроде работает, но что-то мне оно не особо нравится: 1) Пришлось хардкодить создание начальной популяции отбрасывая особи, у которых суммарный вес предметов выше максимально допустимого. Знаю, что это допускается условием задачи, но, ИМХО, по идее алгоритм должен их принимать, как и других, просто отсеивая. А по факту в итоге зачастую выживали именно с этим генотипом. 2) Гвоздями прибито условие, по которому популяция должна делиться надвое без остатка. 3) Иногда выживают особи с не самым оптимальным набором предметов, или даже имеющие кучу свободного места. Если подскажете, как можно довести до ума алгоритм буду благодарен. Модель данных:
Листинг программы 
  1.  public class Item
  2.     {
  3.         public String Name { get; private set; }
  4.         public int Weight { get; private set; }
  5.         public double Price { get; private set; }
  6.  
  7.         public Item (String Name, int Weight, double Price)
  8.         {
  9.             this.Name = Name;
  10.             this.Weight = Weight;
  11.             this.Price = Price;
  12.         }
  13.     }    public class BackPack
  14.     {
  15.         List<Item> Items = null;
  16.         public int Weight { get; private set; } = 0;
  17.         public double Price { get; private set; }
  18.         public double Fitness { get; private set; }
  19.         public double Probably { get; set; }
  20.  
  21.         public BackPack(int maxWeight, Item[] allItems, Random rnd)
  22.         {
  23.             int i;
  24.             int iterations = 0;
  25.             Items = new List<Item>();
  26.             while (Weight < maxWeight)
  27.             {
  28.                 iterations++;
  29.                 if (iterations > 100)
  30.                     break;
  31.                 i = rnd.Next(0, allItems.Length);
  32.                 if (Items.Contains(allItems[i]))
  33.                     continue;
  34.                 if (Weight + allItems[i].Weight > maxWeight)
  35.                     continue;
  36.                 Items.Add(allItems[i]);
  37.                 Weight += Items.Last().Weight;
  38.             }
  39.             Price = Items.Sum(x => x.Price);
  40.             Fitness = Math.Round(Price / Weight,3);
  41.         }
  42.  
  43.         public Item[] getItems()
  44.         {
  45.             return Items.ToArray();
  46.         }
  47.    
  48.     }
Алгоритм:
Листинг программы 
  1.     public partial class MainWindow : Window
  2.     {
  3.         Random rnd = new Random();
  4.         List<Item> BaseItems = new List<Item>();
  5.         public List<BackPack> population;
  6.         const int generationsCount = 1500;
  7.         const int populationCount = 60;
  8.         const int maxWeight = 15;
  9.  
  10.         public MainWindow()
  11.         {
  12.             InitializeComponent();                    
  13.         }
  14.  
  15.         private void Button_Click(object sender, RoutedEventArgs e)
  16.         {
  17.             InitItems();
  18.             CreatePopulation();
  19.             for (int i = 0; i < generationsCount; i++)
  20.             {
  21.                 Selection();
  22.                 Mutation();
  23.             }
  24.         }
  25.  
  26.         /// <summary>
  27.         /// Создаём набор предметов
  28.         /// </summary>
  29.         void InitItems()
  30.         {
  31.             BaseItems.Add(new Item("Книга", 1, 600));
  32.             BaseItems.Add(new Item("Бинокль", 2, 5000));
  33.             BaseItems.Add(new Item("Аптечка", 4, 1500));
  34.             BaseItems.Add(new Item("Ноутбук", 2, 40000));
  35.             BaseItems.Add(new Item("Котелок", 1, 500));
  36.  
  37.             BaseItems.Add(new Item("Книга1", 3, 500));
  38.             BaseItems.Add(new Item("Бинокль1", 2, 7000));
  39.             BaseItems.Add(new Item("Аптечка1", 5, 500));
  40.             BaseItems.Add(new Item("Ноутбук1", 6, 60000));
  41.             BaseItems.Add(new Item("Котелок1", 2, 300));
  42.  
  43.             BaseItems.Add(new Item("Книга2", 6, 650));
  44.             BaseItems.Add(new Item("Бинокль2", 3, 15000));
  45.             BaseItems.Add(new Item("Аптечка2", 1, 15000));
  46.             BaseItems.Add(new Item("Ноутбук2", 9, 440000));
  47.             BaseItems.Add(new Item("Котелок2", 2, 600));
  48.  
  49.             BaseItems.Add(new Item("Книга3", 6, 200));
  50.             BaseItems.Add(new Item("Бинокль3", 4, 500));
  51.             BaseItems.Add(new Item("Аптечка3", 4, 150));
  52.             BaseItems.Add(new Item("Ноутбук3", 7, 45000));
  53.             BaseItems.Add(new Item("Котелок3", 1, 500));
  54.  
  55.             BaseItems.Add(new Item("Книга4", 1, 400));
  56.             BaseItems.Add(new Item("Бинокль4", 2, 5500));
  57.             BaseItems.Add(new Item("Аптечка4", 2, 2000));
  58.             BaseItems.Add(new Item("Ноутбук4", 2, 32000));
  59.             BaseItems.Add(new Item("Котелок4", 2, 520));
  60.  
  61.             BaseItems.Add(new Item("Книга5", 7, 640));
  62.             BaseItems.Add(new Item("Бинокль5", 6, 5400));
  63.             BaseItems.Add(new Item("Аптечка5", 3, 1600));
  64.             BaseItems.Add(new Item("Ноутбук5", 2, 21000));
  65.             BaseItems.Add(new Item("Котелок5", 2, 500));
  66.         }
  67.  
  68.         /// <summary>
  69.         /// Создаём начальную популяцию
  70.         /// </summary>
  71.         void CreatePopulation()
  72.         {
  73.             population = new List<BackPack>();
  74.             for (int i = 0; i < populationCount; i++)
  75.                 population.Add(new BackPack(maxWeight, BaseItems.ToArray(), rnd));
  76.  
  77.         }
  78.  
  79.         /// <summary>
  80.         /// Выполняем селекцию
  81.         /// </summary>
  82.         void Selection()
  83.         {
  84.             double SumFitness = population.Sum(x => x.Fitness);
  85.             foreach (BackPack bp in population) // для каждого набора расчитываем вероятность быть избранным
  86.                 bp.Probably = 100 * bp.Fitness / SumFitness;    
  87.             population = population.OrderByDescending(x => x.Probably).ToList();
  88.             List<BackPack> parents = new List<BackPack>();
  89.             while (parents.Count != populationCount / 2)    // перебирая сортированный список наборов отбираем половину на роль родителей
  90.             {
  91.                 for (int i = 0; i < population.Count; i++)
  92.                 {
  93.                     if (population[i].Weight > maxWeight)   // отбрасываем нежиснеспособных особей
  94.                         continue;
  95.                     if ((rnd.Next(0, 100 + (int)population[i].Probably * 10)) < 50)
  96.                         continue;
  97.                     else
  98.                     {
  99.                         parents.Add(population[i]);
  100.                         population.RemoveAt(i);
  101.                         break;
  102.                     }
  103.                 }
  104.             }
  105.             population = new List<BackPack>();
  106.             population.AddRange(parents);
  107.             BackPack dad, mum, son1, son2;
  108.             List<Item> items;
  109.             while(parents.Count > 0)    // перебирая родителей отбираем случайным образом пары и создаём 2-х потомков
  110.             {
  111.                 dad = parents[rnd.Next(parents.Count)];
  112.                 parents.Remove(dad);
  113.                 mum = parents[rnd.Next(parents.Count)];
  114.                 parents.Remove(mum);
  115.                 items = new List<Item>();
  116.                 items.AddRange(dad.getItems());
  117.                 items.AddRange(mum.getItems());
  118.                 son1 = new BackPack(maxWeight, items.ToArray(), rnd);
  119.                 son1.Probably = 100 * son1.Fitness / SumFitness;
  120.                 son2 = new BackPack(maxWeight, items.ToArray(), rnd);
  121.                 son2.Probably = 100 * son2.Fitness / SumFitness;
  122.                 population.Add(son1);
  123.                 population.Add(son2);
  124.             }                       
  125.         }
  126.  
  127.         /// <summary>
  128.         /// Случайная мутация
  129.         /// </summary>
  130.         void Mutation()
  131.         {
  132.             BackPack rBp = population[rnd.Next(0, population.Count)];
  133.             int index = rnd.Next(0, rBp.getItems().Length);
  134.             Item newItem = BaseItems[rnd.Next(0, BaseItems.Count)];
  135.             rBp.getItems()[index] = newItem;
  136.         }
  137.     }
Исходники прилагаются (простое WPF приложение с одной кнопкой) BP_Problem.zip

Решение задачи: «Задача о ранце. Генетический алгоритм»

textual
Листинг программы 
  1.     public struct Backpack
  2.     {
  3.         public Backpack(ImmutableArray<Item> items)
  4.         {
  5.             Items = items;
  6.         }
  7.  
  8.         public ImmutableArray<Item> Items { get; }
  9.         public int TotalWorth => Items.Sum(x => x.Worth);
  10.     }

ИИ поможет Вам:

  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

8   голосов , оценка 4.25 из 5

Нужна аналогичная работа?

Оформи быстрый заказ и узнай стоимость

Бесплатно
Оформите заказ и авторы начнут откликаться уже через 10 минут
Похожие ответы