Алгоритм не работает так как нужно

#c_sharp #оптимизация #генетический_алгоритм

Вот задача:


  Вы работаете с компанией по доставке товаров, которая ежедневно пользуется платной
  автомобильной дорогой. 
  
  Плата за путешествие взимается на 10-и пунктах оплаты
  расположенных вдоль дороги. Водителям компании необходимо преодолеть весь путь,
  оплатив комиссию за проезд на каждом из пунктов.
  
  Сложность состоит в том, что по правилам, комиссию можно оплачивать только одной
  единственной монетой. В случае, если ее номинал выше, чем стоимость проезда,
  водитель сдачу не получает и остаток сгорает. Если же монета, наоборот, не полностью
  покрывает стоимость проезда, то вашей компании насчитывается долг. 
  
  При этом
  стоимость проезда на каждом из пунктов абсолютно произвольно изменяется в конце дня,
  и может варьироваться в диапазоне от 1-ой до 10-и копеек включительно. Также
  известно, что несколько пунктов оплаты могут выставлять одну и ту же стоимость
  проезда, а общая сумма проезда через все пункты будет всегда больше 55-и копеек.
  
  Каждому водителю в начале пути выдается 10 монет, по одной монете каждого
  достоинства (т.е. одна монета достоинством в копейку, одна монета достоинством в две
  копейки, одна - три, и так далее, до десяти копеек включительно). 
  
  Используя генетический
  алгоритм, вам необходимо найти такую стратегию оплат путешествия, при которой долг
  водителя в конце пути будет минимальным. Алгоритм будет применяться компанией в
  начале каждого дня, и использовать данные по новым, только что установленным,
  размерам комиссий на пунктах оплат для получения новой стратегии для водителей.
  
  Входящие параметры:
  Массив из десяти произвольных чисел от 1 до 10, представляющих собой размеры
  комиссий на каждом из пунктов. Числа в массиве могут повторятся, и их сумма будет
  всегда больше чем 55.
  
  Выходные данные:
  Массив из десяти чисел, представляющих собой достоинства монет, расположенные в
  порядке, оптимальном для оплат на каждом из пунктов (так чтобы долг компании после
  всех оплат был минимальным).


Я скорее всего справился. В смысле алгоритма, но он не работает.

Вот код:

    class Program
{
    static void Main(string[] args)
    {
        Random rand = new Random();
        //bool weNeedContinue = true;          
        int[] propuski1 = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
        int[] bestWay = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
        int[] propuski = PropuskiPrice(propuski1);
        int[] car0 = {0,0,0,0,0,0,0,0,0,0};
        int[] car1 = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
        int[] car2 = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
        int[] car3 = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
        int[] car4 = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
        int[] car5 = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
        int[] car6 = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
        int[] car7 = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
        int[] car8 = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
        int[] car9 = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
        GenerateCar(car0,bestWay);
        int[] moneyChange = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };                    
        for(int i = 0;i <10;i++)
        {
            GettingBest(moneyChange, car0, propuski, bestWay);
            GenerateCar(car0, bestWay);
            GenerateCar(car1, bestWay);

            GenerateCar(car2, bestWay);
            GenerateCar(car3, bestWay);
            GenerateCar(car4, bestWay);
            GenerateCar(car5, bestWay);
            GenerateCar(car6, bestWay);
            GenerateCar(car7, bestWay);
            GenerateCar(car8, bestWay);
            GenerateCar(car9, bestWay);

            //tournament begin
            int[] car23 = GenerateWinner(car2, car3, propuski);
            int[] car45 = GenerateWinner(car4, car5, propuski);
            int[] car67 = GenerateWinner(car6, car7, propuski);
            int[] car89 = GenerateWinner(car8, car9, propuski);

            int[] car2345 = GenerateWinner(car23, car45, propuski);
            int[] car6789 = GenerateWinner(car67, car89, propuski);

            int[] winner = GenerateWinner(car2345, car6789, propuski);
            int sumWinner = 0;
            for (int j = 0;j < 10; j++)
            {
                Console.WriteLine("stoimost proezda na punkte " + j + " " + propuski[j]);
                Console.WriteLine("deneg v karmane nomer " + j + " " + winner[j]);
                sumWinner = sumWinner + (winner[j] - propuski[j]);
            }
            Console.WriteLine("summa dolga= "+sumWinner);



            Console.ReadKey();
        }          

    }

    public static int[] PropuskiPrice(int[] a)
    {
        Random rand = new Random();
        int summa = 0;
        for (var i = 0; i < a.Length; i++)
        {
            a[i] = rand.Next(10) + 1;
            summa += a[i];
            if (i == 9 && summa <= 55)
            {
                PropuskiPrice(a);
            }
        }
        return a;
    }

    /////////////////////////////////////////////////////
    ////Создаем водителя/////////////////////////////////
    /////////////////////////////////////////////////////


    public static int[]  GenerateCar(int[] a,int[] c)
    {
        Random rand = new Random();

        for (int i = 0; i < a.Length; i++)
        {
            if(c[i] != 0)
            {
                a[i] = c[i];
                continue;
            }
            int b = rand.Next(1, 11);
            if (!a.Contains(b))
            {
                a[i] = b;
            }
            else
                i--;
            if(i == a.Length - 1 )
            {

            }
        }
        return a;
    }

    ////////////////////////////////////////////////////
    ////INIT////////////////////////////////////////////
    ////////////////////////////////////////////////////

    static void GettingBest(int[] change,int[] car,int[] propuski,int[] bestOne)
    {
        int changeSum = 0;
        for (int i = 0; i< 10; i++)
            {
                change[i] = car[i] - propuski[i];
                changeSum += change[i];
                if (change[i] == 0)
                {
                    bestOne[i] = car[i];
                Console.WriteLine("Карман" + car[i]);
                Console.WriteLine("Цена" + propuski[i]);
                Console.WriteLine("Лучший путь"+ bestOne[i]);
                }
            }




    }


    public static int[] GenerateWinner(int[] a, int[] b,int[] prises)
    {
        int[] changeA = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
        int[] changeB = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
        int[] result = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
        for (int i = 0;i < 10; i++)
        {
            changeA[i] = a[i] - prises[i];
            changeB[i] = b[i] - prises[i];
            if(Math.Abs(changeA[i]) > Math.Abs(changeB[i]))
            {
                result[i] = b[i];
            }
            else
            {
                result[i] = a[i];
            }
        }
        return result;
    }

}


В итоге, вот эту часть:

     for(int i = 0;i <10;i++)
        {
            GettingBest(moneyChange, car0, propuski, bestWay);
            GenerateCar(car0, bestWay);
            GenerateCar(car1, bestWay);

            GenerateCar(car2, bestWay);
            GenerateCar(car3, bestWay);
            GenerateCar(car4, bestWay);
            GenerateCar(car5, bestWay);
            GenerateCar(car6, bestWay);
            GenerateCar(car7, bestWay);
            GenerateCar(car8, bestWay);
            GenerateCar(car9, bestWay);

            //tournament begin
            int[] car23 = GenerateWinner(car2, car3, propuski);
            int[] car45 = GenerateWinner(car4, car5, propuski);
            int[] car67 = GenerateWinner(car6, car7, propuski);
            int[] car89 = GenerateWinner(car8, car9, propuski);

            int[] car2345 = GenerateWinner(car23, car45, propuski);
            int[] car6789 = GenerateWinner(car67, car89, propuski);

            int[] winner = GenerateWinner(car2345, car6789, propuski);
            int sumWinner = 0;


Начиная с 3-го, GenerateCar программа игнорирует. Посмотрите, в чем проблема?
    

Ответы

Ответ 1

Попробовал запустить код. 

У вас постоянно крутится один и тот же цикл внутри GenerateCar и из него не хочет
выходить. Почему? Подумайте какое у вас условие выхода из цикла и почему оно не выполняется.
Это первое замечание.

Второе - вам нужно почитать очень популярный вопрос на сайте, с которым многие сталкиваются
- о том, что Random всегда выдаёт одни и те же данные при одинаковом начальном значении.
Подумайте: вы пытаетесь искать разные пути, но каждый раз перебираете одни и те же
варианты.

Третье. Почему вы генерируете 1..11 а не 0..11? Вы никогда не сгенерируете 0 - а
потому вы не выйдете из цикла:

int b = rand.Next(1, 11); // maybe should be int b = rand.Next(0, 10);


Поправив я сразу выскочил из бесконечного цикла.

PS У вас много копипасты. Программист не будет писать car0... car9 и копипастить
подряд 10 раз GenerateCar. Нужно писать циклы, нужно использовать списки и массивы...
а жать ctrl+c, ctrl+v -- это подход не программиста. В остальном -- нужно понимать,
что за алгоритм вы реализуете или быть в теме "генетических алгоритмов". Я например
имею только общие понятия о этой теме, поэтому вы в этом коде больше понимаете, чем
я. Попробуйте словами описать, что тут к чему в коде.


Ответ 2

Чего-то такое получается


Так как у нас по сути позиционная задача, будем использовать такой класс

/// 

/// ДНК с фиксацией
/// 
public class DNA
{
    public bool Locked;
    public int Value;

    public override string ToString()
    {
        return $"{Value}->{Locked}";
    }
}


т.е. если данный ДНК с нужным значением буден находится в нужной позиции, то для
того, чтобы его в дальнейших мутациях не трогать мы полю Lock будем присваивать true.
Следующий класс будет у нас геном или хромосомой :) я биологию совсем уже забыл...

public class PaymentsState
{
    public enum InitPayments
    {
        ForOffspring,
        ForHighway,
        ForDriver,
    }

    private readonly Random _random;

    public List Payments { get; private set; }
    public int Overpayment { get; private set; }//Fitness

    //ctor
    public PaymentsState(Random random, InitPayments init = InitPayments.ForOffspring)
    {
        _random = random ?? throw new ArgumentNullException(nameof(random));

        Payments = new List(10);
        if (init == InitPayments.ForHighway)
        {
            GetPaymentsForHighway();
        }
        else if (init == InitPayments.ForDriver)
        {
            GetPaymentsForDriver();
        }
        else
        { }
    }

    /// 

    /// Заполнение списка оплат для Водителя
    /// все типы монет 1..10 предствлены в отдном экземпляре
    /// в случайном порядке
    /// 
    private void GetPaymentsForDriver()
    {
        var values = Enumerable.Range(1, 10).OrderBy(n => _random.Next(1, 10))
                                                          .ToList();
        //заполняем список
        foreach (var val in values)
            Payments.Add(new DNA { Value = val, Locked = false });
    }

    /// 

    /// Создание списка оплат для Автострады
    /// 
    /// 
    private void GetPaymentsForHighway()
    {
        //сгенирируем массив из десяти чисел от 1 до 10 рассположенных в случ.порядке
        List values = Enumerable.Range(1, 10).OrderBy(n => _random.Next(1, 10))
                                           .ToList();

        //скорректируем под требование суммы
        int sum = 0;
        do
        {
            var index = _random.Next(0, 8);
            //просто копируем соседний элемент
            values[index] = values[index + 1];

            sum = values.Sum();

        } while (sum <= 55);

        //заполняем список
        foreach (var val in values)
            Payments.Add(new DNA { Value = val, Locked = false });
    }

    /// 

    /// Подсчет переплаты на основании переданного списка оплат
    /// 
    /// список оплат у автотрассы
    /// значение переплаты
    public int CalcOverpayment(List highwayPayments)
    {
        if (highwayPayments.Count == 0) return 0;

        for (int i = 0; i < highwayPayments.Count; i++)
        {
            //если это ранее уже зафиксированный ген,
            //то пропускаем его
            if (Payments[i].Locked) continue;

            int val = highwayPayments[i].Value - Payments[i].Value;
            //в случае равенства (самая выгодная оплата) 
            if (val == 0)
            {
                Payments[i].Locked = true; // фиксируем эту ДНК
            }
            else if (val < 0)
            {
                //В случае, если ее номинал выше, чем стоимость проезда,
                //водитель сдачу не получает и остаток сгорает.
                Overpayment += Math.Abs(val);
            }
            else // в случае полож.остатка он идет в долг, т.е. все равно в переплату
            {
                Overpayment += val;
            }
        }

        return Overpayment;
    }

    /// 

    /// Скрещивание с другим геном и получение потомка
    /// 
    /// другой PaymentState
    /// 
    public PaymentsState Crossover(PaymentsState secondParent)
    {
        if (secondParent == null) throw new ArgumentNullException(nameof(secondParent));

        //Здесь сложное наследование, т.к. каждая
        //монета должна быть представлена единожды и обязательно
        //т.е. если берем от мамы в позиции 1 монету 10,
        //то у папы мы уже не можем взять монету с этим же достоинством 10

        //словарь для хранения использованных достоинств монет
        Dictionary usedCoins = Enumerable.Range(1, 10)
                                                    .ToDictionary(n => n, n => false);

        //теперь у потомка должны быть гены от обоих родителей
        //зафиксированные гены должны занять те же самые позиции и значение
        //незафиксированные гены должны взять значение из словаря достоинств монет
        List offspringPayments = Enumerable.Range(1, 10).Select(n => new DNA
{ Value = 0 })
                                                             .ToList();

        //определим у мамы(this) зафиксированные ДНК, 
        //т.е. те, кот. не следует изменять
        var motherLockedDNAs = Payments.Where(p => p.Locked == true);
        //пробежимся по ним и включим их в словарь использованных монет
        //и добавим их в список для потомка
        foreach (DNA locked in motherLockedDNAs)
        {
            int index = Payments.IndexOf(locked);
            offspringPayments[index] = locked;

            //отмечаем использование монеты
            usedCoins[locked.Value] = true;
        }

        //определим у папы(secondParent) тоже
        var fatherLockedDNAs = secondParent.Payments.Where(p => p.Locked == true);
        foreach (DNA locked in fatherLockedDNAs)
        {
            //определим индекс который занимает
            int index = secondParent.Payments.IndexOf(locked);

            //если у матери такой монеты не было,
            //и этот индекс еще свободен
            if (!usedCoins[locked.Value] && offspringPayments[index].Value == 0)
            {
                offspringPayments[index] = locked;

                usedCoins[locked.Value] = true;
            }
        }

        //теперь нужно заполнить оставшиеся гены
        foreach (var payment in offspringPayments)
        {
            if (payment.Value == 0)
            {
                int val = usedCoins.First(kv => kv.Value == false).Key;
                payment.Value = val;
                usedCoins[val] = true;
            }
        }


        //готовим потомока
        var offspring = new PaymentsState(_random, InitPayments.ForOffspring);
        foreach (var payment in offspringPayments)
            offspring.Payments.Add(payment);

        return offspring;
    }

    /// 

    /// Мутирование гена
    /// 
    /// 
    public void Mutate(double mutationRate)
    {
        //Сложное мутирование, т.к. каждое достоинстово монеты
        //должно быть обязательно и один раз

        for (int i = 0; i < Payments.Count; i++)
        {
            //если это ранее уже зафиксированный ген,
            //то пропускаем его
            if (Payments[i].Locked) continue;

            if (_random.NextDouble() < mutationRate)
            {
                //запоминаем монету
                int coinInner = Payments[i].Value;
                //новое случайное значение монеты
                int coinRandomValue = _random.Next(1, 10);

                //находим ген монеты с таким же значением
                DNA dna = Payments.First(p => p.Value == coinRandomValue);
                //если этот ген имеет статус зафиксированного
                //то ничего с ним делать не будем
                if (dna.Locked) continue;

                //находим индекс этого гена
                int index = Payments.IndexOf(dna);

                //запоминаем по этому индексу новый ген
                Payments[index] = new DNA { Value = coinInner };
                //а по текущему индексу полученную из случайного знач.
                Payments[i] = dna;
            }
        }
    }
}


Класс автотрассы

/// 

/// Автотрасса
/// 
public class Highway
{
    private readonly Random _random;
    private readonly PaymentsState _paymentsState;

    //ctor
    public Highway(Random random)
    {
        _random = random ?? throw new ArgumentNullException(nameof(random));

        _paymentsState = new PaymentsState(_random, PaymentsState.InitPayments.ForHighway);
    }

    public List Payments => _paymentsState.Payments;

    public int PaymentSum => Payments.Select(p => p.Value).Sum();

    public int MinOverpayment => PaymentSum - 55;

}


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

public class PaymentGeneticAlgorithm
{
    private readonly Random _random;
    private List _tmpNewPopulation = new List();
    private PaymentsState _bestPaymentsState; //лучшая позиция

    public List Population { get; set; } = new List();
    public int Generation { get; private set; } //номер поколения
    public double MutationRate { get; private set; } //коэффициент мутации

    //ctor
    public PaymentGeneticAlgorithm(Random random, int populationSize, double mutationRate
= 0.5)
    {
        _random = random ?? throw new ArgumentNullException(nameof(random));
        MutationRate = mutationRate;

        for (int i = 0; i < populationSize; i++)
        {
            Population.Add(new PaymentsState(_random, PaymentsState.InitPayments.ForDriver));
        }

        //в первый раз у нас лучшим будет просто первый
        _bestPaymentsState = Population[0];
    }

    //--

    public int BestOverpayment => _bestPaymentsState.Overpayment; //значение лучшей
переплаты

    public List BestPayments => _bestPaymentsState.Payments.Select(p => p.Value).ToList();
//лучшие оплаты

    //--

    /// 

    /// Создание нового поколения популяции
    /// 
    /// 
    public void CreateNewGeneration(List highwayPayments)
    {
        //проверка входных данных
        if (highwayPayments == null) throw new ArgumentNullException(nameof(highwayPayments)); 
        if (highwayPayments.Count <= 0) return;
        if (Population.Count <= 0) return;

        //выбор из популяции наиболее пригодного экземпляра
        _bestPaymentsState = CalculateFitness(highwayPayments);

        //готовим новую популяцию
        _tmpNewPopulation.Clear();

        //будем скрещивать лучшего с оставшемися в популяции
        for (int i = 0; i < Population.Count; i++)
        {
            //выбор родителя
            var parent = Population[i];
            //производим наследование или скрещивание
            var child = _bestPaymentsState.Crossover(parent);
            //подвергнем потомка мутации
            child.Mutate(MutationRate);
            //вносим потомка в новую коллекцию
            _tmpNewPopulation.Add(child);
        }

        //заменяем старую популяцию на новую
        var tmpList = Population;
        Population = _tmpNewPopulation;
        _tmpNewPopulation = tmpList;
        //увеличиваем счетчик поколений
        Generation++;
    }

    /// 

    /// Проверка текущего поколения на пригодность
    /// Выявление лучшего гена наиболее подходящего под образец
    /// 
    private PaymentsState CalculateFitness(List highwayPayments)
    {
        var best = _bestPaymentsState;

        for (int i = 0; i < highwayPayments.Count; i++)
        {
            var fitness = Population[i].CalcOverpayment(highwayPayments);

            //если переплата меньше, берем этот вариант
            if (fitness < best.Overpayment)
                best = Population[i];
        }

        return best;
    }
}


Пользоваться всем этим счастьем можно так

class Program
{
    static void Main(string[] args)
    {
        Console.WriteLine("==Программа планирования платежей==");
        Console.WriteLine();

        var random = new Random();
        var populationSize = 100;
        var mutationRate = 0.2;

        var highway = new Highway(random);
        var pga = new PaymentGeneticAlgorithm(random, populationSize, mutationRate);

        Console.WriteLine("Текущая ситуация на трассе");
        PrintHighway(highway);
        Console.WriteLine();
        Console.WriteLine("Для начала расчета нажмите любую клавишу");
        Console.ReadKey(true);

        do
        {
            pga.CreateNewGeneration(highway.Payments.ToList());
            Console.WriteLine("Трасса");
            PrintHighway(highway);
            Console.WriteLine("Платежи");
            PrintBestGenes(pga.BestPayments);
            Console.WriteLine($"Поколение: {pga.Generation}, Переплата: {pga.BestOverpayment}");
            Console.WriteLine(new string('-', 80));
            Console.WriteLine();

            //Thread.Sleep(700);
            if (pga.Generation > 1000) break;

        } while (pga.BestOverpayment > highway.MinOverpayment);


        Console.ReadKey();
    }

    private static void PrintBestGenes(IEnumerable bestGenes)
    {
        var payments = bestGenes.ToList();
        var names = Enumerable.Range('A', payments.Count).ToList();

        Console.Write("|");
        Console.Write(new string('=', 5));
        for (int i = 0; i < payments.Count; i++)
        {
            Console.Write($"[{(char)names[i]}:${payments[i]}]");
            Console.Write(new string('=', 3));
        }
        Console.Write(new string('=', 2));
        Console.WriteLine("|");
    }

    private static void PrintHighway(Highway highway)
    {
        var payments = highway.Payments.ToList();
        var names = Enumerable.Range('A', payments.Count).ToList();

        Console.WriteLine($"Общая сумма оплаты: {highway.PaymentSum}, минимально
возможная переплата: {highway.MinOverpayment}");

        Console.Write("|");
        Console.Write(new string('=', 5));
        for (int i = 0; i < payments.Count; i++)
        {
            Console.Write($"[{(char)names[i]}:${payments[i].Value}]");
            Console.Write(new string('=', 3));
        }
        Console.Write(new string('=', 2));
        Console.WriteLine("|");
    }
}