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

#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("|");
    }
}

Гибкость генетического алгоритма

#алгоритм #нейронные_сети #теория #генетический_алгоритм

Как сделать правильно гибкость генетического алгоритма (умоляю не советуйте A*),
ну вот на примитивном примере движении машины к цели, обходя препятствие:

Что у нас есть :


  
  У нас есть машина, она может двигать вперёд, влево, вправо, назад.
  Есть препятствие, если машина в него въезжает она ломается.
  Ещё есть цель, до которой наша машина должна добраться.
  




Так вот, вопрос в чём, как я понимаю наш генетический алгоритм проложит определённый
маршрут нашей машины до цели (рис. 1), но если мы изменим карту (рис. 2), то этот же
генетический алгоритм не доберётся до нашего места назначения, он просто сначала пойдёт
по тому же пути и потом опять начнёт грубо говоря подбором (скрещиванием) подбирать
маршрут, а как сделать чтобы он уже мог уверенно идти к цели основываясь на опыте (рис. 3) ?





UPD :


    

Ответы

Ответ 1

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

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

Конкретно для этой задачи можно просто брать за первоначальный маршрут прямую линию
из начальной в конечную точку, дальше начинать "мутировать" этот маршрут: добавлять/удалять
узлы, смещать их, и т.д. В простых случаях "скрещивать" маршруты между собой не обязательно,
но для сложных лабиринтов это может дать какие-то бонусы (можно с этим поэкспериментировать).
В общем-то, если в исходном пути по прямой нет препятствий, то этот маршрут в итоге
и выиграет. Если препятствия попадутся, то за счет штрафа за пересечение препятствий
будет выбран другой маршрут, где препятствий нет.

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

Для простых карт приемлемое решение будет находиться достаточно быстро (зависит от
силы отклонений от исходного маршрута при "мутациях").

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

Гибкость генетического алгоритма

Как сделать правильно гибкость генетического алгоритма (умоляю не советуйте A*), ну вот на примитивном примере движении машины к цели, обходя препятствие:
Что у нас есть :
У нас есть машина, она может двигать вперёд, влево, вправо, назад. Есть препятствие, если машина в него въезжает она ломается. Ещё есть цель, до которой наша машина должна добраться.

Так вот, вопрос в чём, как я понимаю наш генетический алгоритм проложит определённый маршрут нашей машины до цели (рис. 1), но если мы изменим карту (рис. 2), то этот же генетический алгоритм не доберётся до нашего места назначения, он просто сначала пойдёт по тому же пути и потом опять начнёт грубо говоря подбором (скрещиванием) подбирать маршрут, а как сделать чтобы он уже мог уверенно идти к цели основываясь на опыте (рис. 3) ?


UPD :

Ответ

Генетический алгоритм - это оптимизационный алгоритм. В отличие от алгоритмов машинного обучения (тех же нейронных сетей) он никак не опирается на "предыдущий опыт", а просто оптимизирует (т.е. максимизирует или минимизирует, в зависимости от задачи) какую-то целевую функцию при помощи подбора значений параметров этой функции.
При изменении исходных условий (изменение карты, расположение исходных и конечных точек) генетический алгоритм просто каждый раз с нуля будет строить маршрут.
Конкретно для этой задачи можно просто брать за первоначальный маршрут прямую линию из начальной в конечную точку, дальше начинать "мутировать" этот маршрут: добавлять/удалять узлы, смещать их, и т.д. В простых случаях "скрещивать" маршруты между собой не обязательно, но для сложных лабиринтов это может дать какие-то бонусы (можно с этим поэкспериментировать). В общем-то, если в исходном пути по прямой нет препятствий, то этот маршрут в итоге и выиграет. Если препятствия попадутся, то за счет штрафа за пересечение препятствий будет выбран другой маршрут, где препятствий нет.
Целевая функция - длина пути + штраф за пересечение препятствий (можно задать, что он будет зависеть от расстояния до края препятствия). Можно еще добавить штраф за количество узлов (чтобы они не сильно "плодились"), но он должен быть намного меньше штрафа за препятствия, иначе маршрут будет сходиться к прямой линии вне зависимости от наличия препятствий (тоже можно поэкспериментировать величиной штрафа).
Для простых карт приемлемое решение будет находиться достаточно быстро (зависит от силы отклонений от исходного маршрута при "мутациях").
Использовать нейросеть для этой задачи я бы не советовал, это как раз тот случай, когда самые "простецкие" алгоритмы работают достаточно хорошо при намного меньших усилиях со стороны программиста. Нейросети побеждают в других областях: классификация, распознавание, некоторые задачи, для которых вообще проблематично найти четкий алгоритм, но которые человек относительно легко решает интуитивно.