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

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

Доброго времени суток, коллеги. На днях выдалось относительно свободное время и я решил размять мозги. Выбор пал на задачу о ранце. Начать решил с поиска готовых решений. В нете нашёл простую реализацию решения методом перебора. Небольшой список предметов она решала относительно быстро, при увеличении время работы нелинейно возрастало: на 5 предметов решение находилось за 10 мс, 10 предметов - 4,5 секунды, 15 - задача крутилась 8 часов, после чего мне это надоело и я её вырубил. Вооружившись википедией и тематическими статьями решил реализовать решение генетическим алгоритмом. Вроде сделал, вроде работает, но что-то мне оно не особо нравится: 1) Пришлось хардкодить создание начальной популяции отбрасывая особи, у которых суммарный вес предметов выше максимально допустимого. Знаю, что это допускается условием задачи, но, ИМХО, по идее алгоритм должен их принимать, как и других, просто отсеивая. А по факту в итоге зачастую выживали именно с этим генотипом. 2) Гвоздями прибито условие, по которому популяция должна делиться надвое без остатка. 3) Иногда выживают особи с не самым оптимальным набором предметов, или даже имеющие кучу свободного места. Если подскажете, как можно довести до ума алгоритм буду благодарен. Модель данных:

 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;
        }
    }

Исходники прилагаются (простое WPF приложение с одной кнопкой) BP_Problem.zip

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

textual
                            Листинг программы 
                        

                                public struct Backpack
    {
        public Backpack(ImmutableArray<Item> items)
        {
            Items = items;
        }
 
        public ImmutableArray<Item> Items { get; }
        public int TotalWorth => Items.Sum(x => x.Worth);
    }
                        