Вот задача:
Вы работаете с компанией по доставке товаров, которая ежедневно пользуется платной
автомобильной дорогой.
Плата за путешествие взимается на 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("|");
}
}
В итоге по всем "возможностям" pagespeed ругается на эти изображения и ругается на
img-1-2x.jpg Т.е. на телефонах вместо того чтобы отображать img-1-1x.jpg отображается
большая картинка.
И такие проблемы только для моб. девайсов:
Для десктопа все отлично, скорость 90+!
По совету использую Echo.js lazy load, но этот lazy load на телефонах (особенно при
плохом интернете) не все фото грузит.
Update:
Как оказалось запись:
