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

Всем доброго времени суток!
Прошу помощи с разработкой генетического алгоритма, хотя, если говорить конкретнее, с самой начальной стадией его разработки.
Существует такая задача (опишу более-менее вкратце; см. рисунок 1): пусть имеется несколько автоматических пожарных станций, оснащённых некоторым количеством пожарных дронов. Один пожарный дрон может только взлететь со своей станции, добраться до заданного очага возгорания, ликвидировать его, и вернуться обратно, после чего он должен будет уйти на зарядку/заправку. Станции расположены на такой местности, что использование обычных пожарных частей невозможно, а пожарных вертолётов - нецелесообразно (дорого и долго), однако эта местность имеет высокую тенденцию к появлению новых очагов возгорания. Друг относительно друга станции расположены так, их зоны покрытия местности зачастую пересекаются. Реагировать эти дроны должны на два (это упрощение с целью просто разобраться) вида возгораний - подтверждённое (точно уже горит, само не потухнет, пора тушить) и неподтверждённое (неясно, горит ли, и/или неясно, потухнет ли само). Очевидно, что распространяющийся по тайге пожар нужно остановить максимально быстро. Очевидно также и то, что при относительно большом количестве известных очагов и сравнимом количестве пожарных дронов становится далеко не очевидным, какой именно вариант распределения дронов по очагам (обоих типов) позволит остановить распространение пожара в кратчайшие сроки.
Таким образом, вкратце задача описывается следующим образом: найти оптимальный вариант распределения всех дронов со всех станций по всем известным очагам возгорания таким образом, чтобы время, требуемое для ликвидации этих очагов, было минимальным. При этом, "оптимальный" вариант подчиняется некоторому набору критериев:
1. высшим приоритетом являются подтверждённые очаги - сначала должна производиться максимизация числа вылетов дронов именно к ним;
2. вторым приоритетом является максимизация числа вылетов дронов к неподтверждённым очагам;
3. и, наконец, третьим приоритетом является минимизация времени исполнения поставленной дронам задачи, что в целях упрощения я "округляю" до критерия минимальной суммарной дистанции их (всех дронов) полёта до соответствующих очагов.

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

Итак, с предисловием мы закончили
Я решил использовать для решения генетический алгоритм (или, быть может, у кого-нибудь будет идея получше?) и смог разобраться с тем, как его применять на примере всем известной задачи коммивояжёра. Тем не менее, это не сильно помогло мне с точки зрения решения вышеописанной задачи - в коммивояжёре нет подобных строго последовательных в своём применении критериев.
Тем не менее, я не прошу выкатить мне решение, а прошу помощи с указанием мест, где я окажусь неправ, предполагая далее то, как следует решать эту задачу. (По большому счёту, я не уверен лишь в кодировке хромосомы, а там уж разберёмси.)
Как я понял, хромосома должна содержать набор данных, который может называться решением. В данном случае, как я понимаю, это вектор-строка с номерами очагов, которые необходимо посетить. Мне неясно лишь то, как именно в этой вектор-строке должно происходить прикрепление очагов к станциям, ведь не все очаги могут посетить дроны с одной станции. Предположу, что можно закодировать хромосому так, как показано на рисунке 2 - отдельные позиции в векторе заранее присваиваются определённым станциям по количеству дронов на них. Мне не кажется, что это удачная идея, поскольку при тасовке генов в процессе работы алгоритма придётся тщательно следить за особями и исключать/исправлять/штрафовать некорректные хромосомы, но ничего лучше я пока не придумал.
Отдельный вопрос у меня и к длине хромосомы, ведь, как я понял, её нужно задавать заранее, а в процессе решения, по-хорошему, нужно бы дать ответ и на вопрос о количестве посещаемых очагов, то есть, определить длину хромосомы. Думается мне, что придётся придумать инструмент, рассчитывающий её длину ДО начала работы ген. алгоритма, но мало ли кто-нибудь что-нибудь подскажет.
Опять же, как можно было бы установить жёсткое ограничение на последовательное исполнение критериев, о которых я писал выше? Что если алгоритм решит вообще не летать к подтверждённым очагам, предпочтя им неподтверждённые? Снова система штрафов и/или исправлений? А если исправить нельзя, либо исправление лишь усугубит ситуацию? Либо же нужно исключать такое поведение оценкой качества решения - фитнесс-функцией - давая уменьшенную ценность полётам к неподтверждённым очагам?
Теперь, думаю, можно и о фитнесс-функции. Я придумал такую формулу: . Цель - максимизация этой функции.
Формула кривенькая, но я её опишу - для каждой особи (хромосомы) вычисляется её качество: в векторе находится количество подтверждённых очагов и умножается на коэф. "1", после чего это число складывается с количеством неподтверждённых очагов, умноженным на коэффициент, заведомо принижающий их значимость, например, "0.1"; в конце всё это дело делится на суммарное расстояние от каждого очага (в векторе) до соответствующей пожарной станции. Теоретически, такой подход должен призвать алгоритм не променивать подтверждённые очаги на НЕподтверждённые (однако в соотношении 1 к 10 это, всё же, может произойти при большом количестве очагов, я думаю), а также устремить его в сторону поиска оптимального, с точки зрения расстояния, варианта.
Вроде, всё.
Всем спасибо за внимание и заранее ОГРОМНОЕ спасибо за любую помощь!

Миниатюры

   

0

Здравствуйте! Немного знаком с генетическим алгоритмом и задачей коммивояжёра, поэтому откликаюсь на известные понятия.
Ваш вопрос очень объемный и, если честно, он в общем не совсем ясно изложен. Быть может,следует по пунктам расписать, что вас интересует?
Что касается предметной части, про метод кодирования решений, самое простое, что приходит на ум - составить строку из n чисел от 1 до m, где n - число очагов, а m - число свободных дронов (быть может, вы это и предложили в своем вопросе уже сами).
Не знаю, читали вы или нет, но про эволюционные вычисления и про генетический алгоритм в частности есть отличная книга Evolutionary Optimization Algorithms за авторством Dan Simon (ни в коем случае не брать переводное издание, исключительно оригинал). Если не читали - очень советую, там вполне интересно и понятно изложены эволюционные подходы к решению многих задач.

0

danascully, Добрый день!
В целом, задачу я уже решил, просто попробовав сделать так, как и написал в топике.
Благодарю Вас за отклик, тем не менее!
За рекомендуемую книгу - отдельное спасибо - обязательно ознакомлюсь.

0

Мои поздравления с успешным решением задачи!

0