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